• Root directory contains three sub-directories namely ’Sequential’, ’OpenMP’ and ’MPI’.

• Each subdirectory has source code in the form of ** ’*.c’** file.

• Matrix is generated in a manner that it decomposes into a L and U containing only 1s and 0s.

• To submit jobs for various configurations run ’./submit.sh’ on terminal. This will automatically submit all the jobs in the subdirectory to the general-compute queue of the ccr cluster.

• Outputs are generated in the output.txt file. Sample outputs are included.

• In the corresponding subdirectory run ./plot.sh on the linux terminal to generate a graphical visualization of the output. gnuplot is required to generate graph.

• Graphs are generated as ’Plot.pdf’. Please wait for the job run to finish and outputs to accumulate.

• Gaussian elimination algorithm was implemented that sequentially decomposes the square matrix.

• Algorithm was evaluated on input matrix size of 1000, 5000, 10000, 20000.

• Time taken to decompose the matrix grew exponentially with the increase in size.

• Since, this was a sequential implementation increase in compute nodes won’t do anything.

• Since I was using Gaussian elimination that computes L and U matrices separately, I ran out of memory when matrix size of 50,000 was tried. This implementation makes two copies of the matrix of same size as input.

• Gaussian elimination algorithm was implemented that uses the block wise decomposition in parallel.

• The for loops are parallelized in a manner that blocks of matrices are decomposed by dividing the work among parallel threads.

• Algorithm was evaluated for input matrix of sizes 1000, 5000, 10000, 20000 with a combination of 2, 4, 8, 16, 32 threads executing in parallel.

• On a fixed workload the decompostion was faster when more threads are executing in parallel. The execution was comparatively faster on larger workload due to the fact, parallelism was more effective.

• For a fixed number of cores the time increased exponentially with increase in matrix size.

• The parallelism was ineffective on relatively smaller loads.

• Since I was using Gaussian elimination that computes L and U matrices separately, I ran out of memory when matrix size of 50,000 was tried. This implementation makes two copies of the matrix of same size as input.

• Cyclic distribution was used to accomplish LU factorization of the input square matrix.

• Each node is responsible for computing its own block and broadcast the result to rest of the nodes.

• Algorithm was evaluated for input matrix of sizes 1000, 5000, 10000 with a combination of 8, 16, 32 compute nodes working in parallel.

• For a fixed number of compute nodes the algorithm showed uniform behavior.

• For fixed workload the parallelism was more effective for larger workloads on maximum compute nodes.

• Since, MPI involves communication overhead between different nodes, it was slower as compared to OpenMP.

  

• As expected sequential algorithm turns out to be the worst performer of the three.

  

LU factorization algorithm has a great extent of parallelization when scaled appropriately.