title: Cannon matrix multiplication in MPI
body: <p>I'm trying to implement Cannon's matrix multiplication algorithm in C using MPI and nonblocking communication. I've tried the example code at <a href="http://siber.cankaya.edu.tr/ozdogan/GraduateParallelComputing.old/ceng505/node133.html" rel="nofollow">http://siber.cankaya.edu.tr/ozdogan/GraduateParallelComputing.old/ceng505/node133.html</a>, but I can't get it to work.</p>
  
  <p>It works fine when executed with a single node, but more than that and it's not finishing.</p>
  
  <p>I'm trying to use a randomized 4*4 matrix on 4 nodes. From what I can gather with absolutely no debugging tools aside from printf process with rank 0 finishes executing the function, but other processes get stuck at MPI_Wait on line 68. I'm pretty new to C and parallel programming and can't figure out what's wrong.</p>
  
  <p>EDIT: During debugging I found one incredibly baffling thing - calling MPI_Barrier seems to hang the whole program.</p>
  
  <p>I call MPI_Barrier in main after the multiplication function is completed. To make debugging a little easier i decided to split the function code into parts and separate them with barriers. placing the barrier at the end of main computation loop ( so that every process has to complete one iteration for any process to start the next one ) resulted in the loop not even reaching second iteration. </p>
  
  <p>It seems that when a single process reaches the barrier after non blocking sends/receives and consequent calls to MPI_Wait it causes other processes to wait indefinitely and never reach the barrier.</p>
  
  <p>Here's an example code:</p>
  
  <pre><code>void generateArray(int * vector, int size){
  int i;
  for (i = 0; i &lt; size; i ++){
      vector[i] = rand()%10 + 1;
  }
  }
  
  int test_size = 4;
  
  int main( int argc, char **argv )
  {
  MPI_Init (&amp;argc, &amp;argv); 
  
  int comm_size, myrank;
  int my2drank, mycoords[2]; 
  MPI_Comm_size(MPI_COMM_WORLD, &amp;comm_size); 
  MPI_Comm_rank(MPI_COMM_WORLD, &amp;myrank);
  
  
  MPI_Request requests[4];
  MPI_Status status[4];
  
  MPI_Comm comm_2d;
  int dims[2], periods[2];
  dims[0] = dims[1] = sqrt(comm_size);
  periods[0] = periods[1] = 1; 
  MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, 1, &amp;comm_2d);
  
  int sizelocal = test_size/dims[0];
  
  srand(time(NULL));
  int a[sizelocal*sizelocal], b[sizelocal*sizelocal];
  generateArray(a, sizelocal*sizelocal);                              
  generateArray(b, sizelocal*sizelocal);
  
  MPI_Comm_rank(comm_2d, &amp;my2drank); 
  MPI_Cart_coords(comm_2d, my2drank, 2, mycoords); 
  
  int uprank, downrank, leftrank, rightrank; 
  MPI_Cart_shift(comm_2d, 0, -1, &amp;rightrank, &amp;leftrank);
  MPI_Cart_shift(comm_2d, 1, -1, &amp;downrank, &amp;uprank); 
  
  int *buffersA[2], *buffersB[2];
  
  buffersA[0] = a; 
  buffersA[1] = (int *)malloc(sizelocal*sizelocal*sizeof(int)); 
  buffersB[0] = b; 
  buffersB[1] = (int *)malloc(sizelocal*sizelocal*sizeof(int));
  
  int shiftsource, shiftdest; 
  MPI_Cart_shift(comm_2d, 0, -mycoords[0], &amp;shiftsource, &amp;shiftdest); 
  MPI_Sendrecv_replace(buffersA[0], sizelocal*sizelocal, MPI_INT,shiftdest, 1, shiftsource, 1, comm_2d, &amp;status[0]); 
  
  MPI_Cart_shift(comm_2d, 1, -mycoords[1], &amp;shiftsource, &amp;shiftdest); 
  MPI_Sendrecv_replace(buffersB[0], sizelocal*sizelocal, MPI_INT,shiftdest, 1, shiftsource, 1, comm_2d, &amp;status[0]);
  
  printf("Rank %d at point 1\n", my2drank);    
  
  int i;
  for (i = 0; i &lt; 2; i ++){
      printf("Rank %d started iteration %d\n", my2drank, i);
      MPI_Isend(buffersA[i%2], sizelocal*sizelocal, MPI_INT,leftrank, 1, comm_2d, &amp;requests[0]); 
      MPI_Isend(buffersB[i%2], sizelocal*sizelocal, MPI_INT,uprank, 1, comm_2d, &amp;requests[1]); 
      MPI_Irecv(buffersA[(i+1)%2], sizelocal*sizelocal, MPI_INT,rightrank, 1, comm_2d, &amp;requests[2]); 
      MPI_Irecv(buffersB[(i+1)%2], sizelocal*sizelocal, MPI_INT,downrank, 1, comm_2d, &amp;requests[3]);
  
      MPI_Waitall(4, requests, status);
      printf("Rank %d stopped waiting in iteration %d\n", my2drank, i);
      MPI_Barrier(comm_2d);
  }
  
  printf("Rank %d at point 2\n", my2drank);
  
  MPI_Barrier(MPI_COMM_WORLD);
  MPI_Finalize();
  return 0;
  }
  </code></pre>
  
  <p>And here's the output:</p>
  
  <pre><code>Rank 0 at point 1
  Rank 0 started iteration 0
  Rank 1 at point 1
  Rank 1 started iteration 0
  Rank 2 at point 1
  Rank 2 started iteration 0
  Rank 3 at point 1
  Rank 3 started iteration 0
  Rank 0 stopped waiting in iteration 0
  </code></pre>