gauss_forward_improved_linux.c	Gaussian Elimination Compatible Optimized for Linux GCC compiler
gauss_forward_not_improved_linux.c	Gaussian Elimination Compatible Not Optimized
improved.c	Matrix Multiplication Optimized for Windows GCC compiler
improved_linux.c	Matrix Multiplication Optimized for Linux GCC compiler
not_improved.c	Matrix Multiplication Not Optimized for Windows GCC compiler
not_improved_linux.c	Matrix Multiplication Not Optimized for Linux GCC compiler

Some useful Guidelines:

Optimizing for the serial processors

Lecture 2: Memory Hierarchies and Optimizing Matrix Multiplication

1. Write a Vanilla Matrix Multiply Program in C
1. Parameterize the data type to support, int float and double
2. initialize with random data
3. measure and display de run-time of the matrix multiply
2. Excute 3 executables version in, float and double, each with 4 compiler optimization settings(none, -o,-o2,-o3), use matrix sizes with  128x128 to 4096x4096
3. Rewrite your vanilla code by applying as many typical compiler transformation as you can: document the ones you applied in a list.
4. Repeat execution 2 with the other transformations.
5. Write a 1-Page Report, including a table to show runtime results of step 2 and 4.
6. Write Gaussian Elimination and repeat the same procedure.

• The Method called Loop Invariant Code motion:
• This Method is use to avoid using a variable that slightly changes within a loop, as an example I show the improvement within my code:
  
  
  as you can observe in the image, there is a multiplication within the k look, where it is performed the multiplication of N by c. N it is a constant and c is changed only by the c loop, thereby removing the multiplication from the k loop and moving it to the c loop. The unnecessary multiplication is just made N times instead of NxN times.
  
  
• Principle of Memory Locality.
• The cache is a fast memory access whereby the computer is capable of accessing often required data to perform different operations repeatedly. The cache is used to to reduce the time required by the processor to access local memory such as RAM. In order to exploit the principle of Memory Locality we must know how cache actually works when you are implementing loops and reading data from a array, so if we are able to read the values from the Matrix in a proper way to exploit computer's cache, we are going to increase in the performance of the matrix multiplication Algorithm.
• As the preview image shows, there are 3 loops, c loop , d loop , and k look.
• The first code (on the left): To illustrate the behavior of this code I will show 2 matrices, of 2x2
  

  A(0,0)	A(0,1)
  A(1,0)	A(1,1)

  x

  B(0,0)	B(0,1)
  B(1,0)	B(1,1)

  =
  

  C(0,0)	C(0,1)
  C(1,0)	C(1,1)

  
  First Iteration(d loop)
  C[0][0]+=A[0][0]*B[0][0];
  C[0][0]+=A[0][1]*B[1][0];  ==> Where C[0][0] was accessed N times
  
  Second Iteration(d loop)
  C[0][1]+=A[0][0]*B[0][1]; ==> Where C[0][0] was accessed N times
  C[0][1]+=A[0][1]*B[1][1];
  
  Third Iteration(d loop)
  C[1][0]+=A[1][0]*B[0][0]; ==> Where C[0][0] was accessed N times
  C[1][0]+=A[1][1]*B[1][0];
  
  Fourth Iteration(d loop)
  C[1][1]+=A[1][0]*B[0][1]; ==> Where C[0][0] was accessed N times
  C[1][1]+=A[1][1]*B[1][1];
  
  Now imagine what happens when you have a matrix of 4096 elements, you will naturally access C[0][0] ==> N(4096) times to write it which only gives to the cache an often data or an array of a sequence of data.
  Each element of the array A is being accessed N times each on the d loop, and each k loop there's a sequence from A[0][0] to A[0][N] where the array A could be stored on the cache memory, and then it could be replaced when the c loop changes.
  Each element of B will be hold each d loop
  
  Now if we compared the not improved algorithm with the improved one we have that:
  
  First Iteration(k loop)
  C[0][0]+=A[0][0]*B[0][0];
  C[0][1]+=A[0][0]*B[0][1];  ==> Where the Array is accessed in sequence C[0][0] --> C[0][n]
  
  Second Iteration(k loop)
  C[0][0]+=A[0][1]*B[1][0]; 
  C[0][1]+=A[0][1]*B[1][1];
  
  Third Iteration(k loop)
  C[1][0]+=A[1][0]*B[0][0]; 
  C[1][1]+=A[1][0]*B[0][1];
  
  Fourth Iteration(k loop)
  C[1][0]+=A[1][1]*B[1][0];
  C[1][1]+=A[1][1]*B[1][1];
  
  Where the array C is accessed in sequence and it will be stored on the cache memory because it stays steadily accessed using the c loop and d loop.
  On the other hand the array A is accessed in sequence as well and can be stored on the cache memory as well whereas the B array could be replaced every k loop
  
  
  Table of Results with Compiler Transformations

  	128x128	256x256	512x512	1024x1024	2048x2048	4096x4096
  --(us)	28930	230222	1843271	14975535	118977048	971977444
  -O1(us)	9640	74382	629343	4986690	41345095	330860175
  -O2(us)	9059	71859	572221	4700699	37936452	301893036
  -O3(us)	9073	72141	577498	4695937	37729592	303559212

  
  As the Runtime improvements table shows the performance has been rocketed up considerably, specially for the matrices of 1024x1024, 2048x2048 and 4096x4096 whereas the performance for the smallest matrices hasn't been dramatically increased, notwithstanding, there is a huge difference regarding the time reached by the matrix of 1024 (0.5 Seconds) compared with the matrix of 2048(4.7 seconds). Once more, the maximum performance was reached by using the -O2 using the matrix 2048x2048. The performance wasn't affected dramatically for the matrices under 2048 due to the cache size, the available space for those matrices allows them to fit without having cache misses which in comparison with the bigger sizes there are more cache misses as it was explained in the first table.
  
  
  Runtime Improvements or Terms of Speedup (With Compiler Transformations) 

  	128x128	256x256	512x512	1024x1024	2048x2048	4096x4096
  Not Improved /Improved --	1x	1.1x	1.5x	4.8x	6.7x	2.5x
  Not Improved /Improved --O1	1.3x	1.6x	2.6x	14.6x	18.9x	7.4x
  Not Improved /Improved --O2	1.3x	1.6x	2.6x	13.4x	19.3x	6.5x
  Not Improved /Improved --O3	1.3x	1.6x	2.6x	11.2x	18.6x	6.0x