Synchronous Computing

Linh B. Ngo

Synchronous Computation

In a (fully) synchronous computation, all the processes synchronized at regular points, usually to exchange data or to make sure that every process has gone through the same set of procedures (to update their own data) before proceeding.



In [1]:

    
%%writefile codes/openmpi/nobarrier.c
#include <stdio.h>
#include <unistd.h>
#include <mpi.h>
int main(int argc, char *argv[]){
  int rank;

  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);

  if (rank == 0){
    sleep(5);
  }
  printf("Process %d is awake! \n", rank);
  MPI_Finalize();
  return 0;
}









    



Overwriting codes/openmpi/nobarrier.c



In [2]:

    
!mpicc codes/openmpi/nobarrier.c -o ~/nobarrier
!mpirun -np 8 --map-by core:OVERSUBSCRIBE ~/nobarrier









    



Process 1 is awake! 
Process 6 is awake! 
Process 5 is awake! 
Process 4 is awake! 
Process 2 is awake! 
Process 7 is awake! 
Process 3 is awake! 
Process 0 is awake!



In [3]:

    
%%writefile codes/openmpi/barrier.c
#include <stdio.h>
#include <unistd.h>
#include <mpi.h>
int main(int argc, char *argv[]){
  int rank;

  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);

  if (rank == 0){
    sleep(5);
  }
  MPI_Barrier(MPI_COMM_WORLD);
  printf("Process %d is awake! \n", rank);
  MPI_Finalize();
  return 0;
}









    



Overwriting codes/openmpi/barrier.c



In [4]:

    
!mpicc codes/openmpi/barrier.c -o ~/barrier
!mpirun -np 8 --map-by core:OVERSUBSCRIBE ~/barrier









    



Process 0 is awake! 
Process 2 is awake! 
Process 1 is awake! 
Process 3 is awake! 
Process 4 is awake! 
Process 5 is awake! 
Process 6 is awake! 
Process 7 is awake!

Barrier

A basic mechanism for synchronizing processes - inserted at the point in each process where it must wait
All processes can continue from this point when all the processes have reached it.

Comm.Barrier()

Parameters:

Comm (MPI comm) – communicator on which we are to block processes

_{Wilkinson, Barry, and Michael Allen. Parallel programming. 2nd Ed. 2003.}

Prefix Sum Problem

Given a list of numbers, $x_0, ..., x_{n-1}$, compute all partial summations, i.e:

$x_0 + x_1$
$x_0 + x_1 + x_2$
$x_0 + x_1 + x_2 + x_3$
$x_0 + x_1 + x_2 + x_3 + x_4$
...

Widely studied with practical applications in process allocation, data compaction, sorting, and polynomial evaluation.

_{Wilkinson, Barry, and Michael Allen. Parallel programming. 2nd Ed. 2003.}



In [7]:

    
%%writefile codes/openmpi/prefix.c
#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
#include <math.h>

int main(int argc, char** argv){
  int rank, size;
  MPI_Status status;
  int local_sum, tmp;
  int i, iter;
  int distance;

  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD,&rank);
  MPI_Comm_size(MPI_COMM_WORLD,&size);

  local_sum = rank;
  tmp = 0;

  iter = log(size) / log(2);
  printf("Process %d has prefix sum %d\n", rank, local_sum);
  MPI_Barrier(MPI_COMM_WORLD);
  for (i = 0; i < iter; i++){
    distance = pow(2,i);

    if (rank == 0){
      printf("iter %d and distance %d\n", i, distance);
    }      
    if (rank < (size - distance)){
      MPI_Send(&local_sum, 1, MPI_INT, rank + distance, 0, MPI_COMM_WORLD);
      printf("%d send to %d value %d\n",rank, rank+distance, local_sum);

    }
    if (rank >= distance){
      printf("%d receive from %d \n", rank, rank - distance);
      MPI_Recv(&tmp, 1, MPI_INT, rank - distance, 0, MPI_COMM_WORLD, &status);
      printf("%d receive from %d value %d\n",rank, rank-distance, tmp);
      local_sum += tmp;
    }
    printf("Process %d has prefix sum %d\n", rank, local_sum);
    MPI_Barrier(MPI_COMM_WORLD);
  }
  MPI_Finalize();
  return 0;
}









    



Overwriting codes/openmpi/prefix.c



In [8]:

    
!mpicc codes/openmpi/prefix.c -lm -o ~/prefix
!mpirun -np 8 --map-by core:OVERSUBSCRIBE ~/prefix









    



Process 0 has prefix sum 0
Process 1 has prefix sum 1
Process 2 has prefix sum 2
Process 3 has prefix sum 3
Process 5 has prefix sum 5
Process 7 has prefix sum 7
Process 4 has prefix sum 4
7 receive from 6 
7 receive from 6 value 6
Process 7 has prefix sum 13
Process 6 has prefix sum 6
6 send to 7 value 6
6 receive from 5 
5 send to 6 value 5
5 receive from 4 
2 send to 3 value 2
2 receive from 1 
4 send to 5 value 4
4 receive from 3 
4 receive from 3 value 3
Process 4 has prefix sum 7
3 send to 4 value 3
3 receive from 2 
3 receive from 2 value 2
Process 3 has prefix sum 5
1 send to 2 value 1
1 receive from 0 
1 receive from 0 value 0
Process 1 has prefix sum 1
5 receive from 4 value 4
Process 5 has prefix sum 9
iter 0 and distance 1
0 send to 1 value 0
Process 0 has prefix sum 0
2 receive from 1 value 1
Process 2 has prefix sum 3
5 send to 7 value 9
5 receive from 3 
7 receive from 5 
7 receive from 5 value 9
Process 7 has prefix sum 22
6 receive from 5 value 5
Process 6 has prefix sum 11
6 receive from 4 
2 send to 4 value 3
2 receive from 0 
4 send to 6 value 7
4 receive from 2 
4 receive from 2 value 3
Process 4 has prefix sum 10
1 send to 3 value 1
Process 1 has prefix sum 1
6 receive from 4 value 7
Process 6 has prefix sum 18
iter 1 and distance 2
0 send to 2 value 0
Process 0 has prefix sum 0
2 receive from 0 value 0
Process 2 has prefix sum 3
2 send to 6 value 3
Process 2 has prefix sum 3
5 receive from 3 value 5
Process 5 has prefix sum 14
3 send to 5 value 5
3 receive from 1 
3 receive from 1 value 1
Process 3 has prefix sum 6
4 receive from 0 
4 receive from 0 value 0
Process 4 has prefix sum 10
6 receive from 2 
6 receive from 2 value 3
Process 6 has prefix sum 21
iter 2 and distance 4
0 send to 4 value 0
Process 0 has prefix sum 0
7 receive from 3 
5 receive from 1 
5 receive from 1 value 1
Process 5 has prefix sum 15
1 send to 5 value 1
Process 1 has prefix sum 1
3 send to 7 value 6
Process 3 has prefix sum 6
7 receive from 3 value 6
Process 7 has prefix sum 28