CSC 5001– High Performance Systems

Parallel algorithmics

Amdahl's law

We considere a LU factorization application (available here: lu.tgz).

This application first generates a random matrix, and then factorizes it. The factorization is parallelized with OpenMP.

Download lu.tgz and run the program with 1 thread with a matrix size of 2000. Based on this measurement, generate a plot that shows the maximum speedup that could be obtained by parallelizing the application with up to 64 threads.

Run the program with a varying number of threads with the same problem size, and generate a plot that compares the theoretical maximum speedup with the actual speedup you measure. Generate another plot that shows the program's parallel efficiency.

All-to-all broadcast

Write the all-to-all algorithm in pseudo-code

void all_to_all(int my_rank, message m, int m_size) {
}
	    

Each MPI rank executes this all_to_all function

You can send/receive messages using send(dest_rank, size, buffer) and recv(src_rank, size, buffer).

void all_to_all(int my_rank, message m, int m_size) {
  for(int i=0; i<log(n); i++) {
    int offset = 1<<i;
    int direction = my_rank & offset;
    int dest;
    if(direction == 0) {
      dest = my_rank + offset;
    } else {
      dest = my_rank - offset;
    }
    send(m, m_size, dest);
    recv(&m[m_size], m_size, dest);
    m_size *=2;
  }
}
		

Estimate the execution time of this function

sum 0..log n-1 (Ts + 2^i Tw.m) = Ts . log n + Tw . m.(n-1)

Matrix multiply

Let's mutliply NxN matrices (A . B = C) over 9 processes.

How to distribute matrices over 9 processes ?

Compute the memory footprint of matrices for each process