Distributed Memory Programming with MPI

Introduction to distributed memory programming with MPI. C++ examples on MPI functions, Single-Program Multiple-Data. and collective communication.

1. Distributed Memory Programming with MPI Slides extended from An Introduction to Parallel Programming by Peter Pacheco Dilum Bandara [email protected]

2. Distributed Memory Systems We discuss about developing programs for these systems using MPI MPI – Message Passing Interface Are set of libraries that can be called from C, C++, & Fortran Copyright © 2010, Elsevier Inc. All rights Reserved

3. Why MPI? Standardized & portable message-passing system One of the oldest libraries Wide-spread adoption Minimal requirements on underlying hardware Explicit parallelization Achieves high performance Scales to a large no of processors Intellectually demanding Copyright © 2010, Elsevier Inc. All rights Reserved

4. Our First MPI Program Copyright © 2010, Elsevier Inc. All rights Reserved

5. Compilation Copyright © 2010, Elsevier Inc. All rights Reserved mpicc -g -Wall -o mpi_hello mpi_hello.c wrapper script to compile turns on all warnings source file create this executable file name (as opposed to default a.out ) produce debugging information

6. Execution Copyright © 2010, Elsevier Inc. All rights Reserved mpiexec -n <no of processes> <executable> mpiexec -n 1 ./ mpi_hello mpiexec -n 4 ./ mpi_hello run with 1 process run with 4 processes

7. Execution Copyright © 2010, Elsevier Inc. All rights Reserved mpiexec -n 1 ./ mpi_hello mpiexec -n 4 ./ mpi_hello Greetings from process 0 of 1 ! Greetings from process 0 of 4 ! Greetings from process 1 of 4 ! Greetings from process 2 of 4 ! Greetings from process 3 of 4 !

8. MPI Programs Need to add mpi.h header file Identifiers defined by MPI start with “MPI_” 1 st letter following underscore is uppercase For function names & MPI-defined types Helps to avoid confusion Copyright © 2010, Elsevier Inc. All rights Reserved

9. 6 Golden MPI Functions Copyright © 2010, Elsevier Inc. All rights Reserved

10. MPI Components MPI_Init Tells MPI to do all necessary setup e.g., allocate storage for message buffers, decide rank of a process argc_p & argv_p are pointers to argc & argv arguments in main( ) Function returns error codes Copyright © 2010, Elsevier Inc. All rights Reserved

11. MPI_Finalize Tells MPI we’re done, so clean up anything allocated for this program MPI Components (Cont.) Copyright © 2010, Elsevier Inc. All rights Reserved

12. Communicators Collection of processes that can send messages to each other Messages from others communicators are ignored MPI_Init defines a communicator that consists of all processes created when the program is started Called MPI_COMM_WORLD Copyright © 2010, Elsevier Inc. All rights Reserved

13. Communicators (Cont.) Copyright © 2010, Elsevier Inc. All rights Reserved My rank (process making this call) No of processes in the communicator

14. Single-Program Multiple-Data (SPMD) We compile 1 program Process 0 does something different Receives messages & prints them while the other processes do the work if-else construct makes our program SPMD We can run this program on any no of processors e.g., 4, 8, 32, 1000, … Copyright © 2010, Elsevier Inc. All rights Reserved

15. Communication msg_buf_p, msg_size, msg_type Determines content of message dest – destination processor’s rank tag – use to distinguish messages that are identical in content Copyright © 2010, Elsevier Inc. All rights Reserved

16. Data Types Copyright © 2010, Elsevier Inc. All rights Reserved

17. Communication (Cont.) Copyright © 2010, Elsevier Inc. All rights Reserved MPI_ANY_SOURCE to receive messages (from any source) in order for arrival

18. Message Matching Copyright © 2010, Elsevier Inc. All rights Reserved MPI_Send src = q MPI_Recv dest = r r q

19. Receiving Messages Receiver can get a message without knowing Amount of data in message Sender of message Tag of message How can those be found out? Copyright © 2010, Elsevier Inc. All rights Reserved

20. How Much Data am I Receiving? Copyright © 2010, Elsevier Inc. All rights Reserved

21. Exact behavior is determined by MPI implementation MPI_Send may behave differently with regard to buffer size, cutoffs, & blocking Cutoff if message size < cutoff  buffer if message size ≥ cutoff  MPI_Send will block MPI_Recv always blocks until a matching message is received Preserve message ordering from a sender Know your implementation Don’t make assumptions! Issues With Send & Receive Copyright © 2010, Elsevier Inc. All rights Reserved

22. Trapezoidal Rule Copyright © 2010, Elsevier Inc. All rights Reserved

23. Trapezoidal Rule (Cont.) Copyright © 2010, Elsevier Inc. All rights Reserved

24. Serial Pseudo-code Copyright © 2010, Elsevier Inc. All rights Reserved

25. Parallel Pseudo-Code Copyright © 2010, Elsevier Inc. All rights Reserved

26. Tasks & Communications for Trapezoidal Rule Copyright © 2010, Elsevier Inc. All rights Reserved

27. First Version Copyright © 2010, Elsevier Inc. All rights Reserved

28. First Version (Cont.) Copyright © 2010, Elsevier Inc. All rights Reserved

29. First Version (Cont.) Copyright © 2010, Elsevier Inc. All rights Reserved

30. Collective communication Copyright © 2010, Elsevier Inc. All rights Reserved

31. Collective Communication Copyright © 2010, Elsevier Inc. All rights Reserved A tree-structured global sum

32. Alternative Tree-Structured Global Sum Copyright © 2010, Elsevier Inc. All rights Reserved Which is most optimum? Can we do better?

33. MPI_Reduce Copyright © 2010, Elsevier Inc. All rights Reserved

34. Predefined Reduction Operators Copyright © 2010, Elsevier Inc. All rights Reserved

35. Collective vs. Point-to-Point Communications All processes in the communicator must call the same collective function e.g., a program that attempts to match a call to MPI_Reduce on 1 process with a call to MPI_Recv on another process is erroneous Program will hang or crash Arguments passed by each process to an MPI collective communication must be “compatible” e.g., if 1 process passes in 0 as dest_process & another passes in 1, then the outcome of a call to MPI_Reduce is erroneous Program is likely to hang or crash Copyright © 2010, Elsevier Inc. All rights Reserved

36. Collective vs. P-to-P Communications (Cont.) output_data_p argument is only used on dest_process However, all of the processes still need to pass in an actual argument corresponding to output_data_p , even if it’s just NULL Point-to-point communications are matched on the basis of tags & communicators Collective communications don’t use tags Matched solely on the basis of communicator & order in which they’re called Copyright © 2010, Elsevier Inc. All rights Reserved

37. MPI_Allreduce Useful when all processes need result of a global sum to complete some larger computation Copyright © 2010, Elsevier Inc. All rights Reserved

38. Copyright © 2010, Elsevier Inc. All rights Reserved Global sum followed by distribution of result MPI_Allreduce (Cont.)

39. Butterfly-Structured Global Sum Copyright © 2010, Elsevier Inc. All rights Reserved Processes exchange partial results

40. Broadcast Data belonging to a single process is sent to all of the processes in communicator Copyright © 2010, Elsevier Inc. All rights Reserved

41. Tree-Structured Broadcast Copyright © 2010, Elsevier Inc. All rights Reserved

42. Data Distributions – Compute a Vector Sum Copyright © 2010, Elsevier Inc. All rights Reserved Serial implementation

43. Partitioning Options Copyright © 2010, Elsevier Inc. All rights Reserved Block partitioning Assign blocks of consecutive components to each process Cyclic partitioning Assign components in a round robin fashion Block-cyclic partitioning Use a cyclic distribution of blocks of components

44. Parallel Implementation Copyright © 2010, Elsevier Inc. All rights Reserved

45. MPI_Scatter Can be used in a function that reads in an entire vector on process 0 but only sends needed components to other processes Copyright © 2010, Elsevier Inc. All rights Reserved

46. Reading & Distributing a Vector Copyright © 2010, Elsevier Inc. All rights Reserved

47. MPI_Gather Collect all components of a vector onto process 0 Then process 0 can process all of components Copyright © 2010, Elsevier Inc. All rights Reserved

48. MPI_Allgather Concatenates contents of each process’ send_buf_p & stores this in each process’ recv_buf_p recv_count is the amount of data being received from each process Copyright © 2010, Elsevier Inc. All rights Reserved

49. Summary Copyright © 2010, Elsevier Inc. All rights Reserved Source: https://computing.llnl.gov/tutorials/mpi/