Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Parallel Programming in C with MPI and OpenMP Michael J Quinn Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Chapter 4 Message Passing Programming Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Learning Objectives Understanding how MPI programs execute Familiarity with fundamental MPI functions Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Outline Message passing model Message Passing Interface MPI Coding MPI programs Compiling MPI programs Running MPI programs Benchmarking MPI programs Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Message passing Model Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Task Channel vs Message passing Task Channel Message passing Task Process Explicit channels Any to any communication Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Processes Number is specified at start up time Remains constant throughout execution of program All execute same program Each has unique ID number Alternately performs computations and communicates Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Advantages of Message passing Model Gives programmer ability to manage the memory hierarchy Portability to many architectures Easier to create a deterministic program Simplifies debugging Copyright The McGraw Hill Companies Inc Permission required for reproduction or display The Message Passing Interface Late 1980s vendors had unique libraries 1989 Parallel Virtual Machine PVM developed at Oak Ridge National Lab 1992 Work on MPI standard begun 1994 Version 1 0 of MPI standard 1997 Version 2 0 of MPI standard Today MPI is dominant message passing library standard Copyright The McGraw Hill Companies Inc Permission required for reproduction or display 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Circuit Satisfiability 0 Not satisfied Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Solution Method Circuit satisfiability is NP complete No known algorithms to solve in polynomial time We seek all solutions We find through exhaustive search 16 inputs 65 536 combinations to test Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Partitioning Functional Decomposition Embarrassingly parallel No channels between tasks Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Agglomeration and Mapping Properties of parallel algorithm Fixed number of tasks No communications between tasks Time needed per task is variable Consult mapping strategy decision tree Map tasks to processors in a cyclic fashion Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Cyclic interleaved Allocation Assume p processes Each process gets every pth piece of work Example 5 processes and 12 pieces of work P 0 5 10 0 P 1 6 11 1 P2 2 7 P 3 8 3 P4 4 9 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Pop Quiz Assume n pieces of work p processes and cyclic allocation What is the most pieces of work any process has What is the least pieces of work any process has How many processes have the most pieces of work Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Summary of Program Design Program will consider all 65 536 combinations of 16 boolean inputs Combinations allocated in cyclic fashion to processes Each process examines each of its combinations If it finds a satisfiable combination it will print it Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Include Files include mpi h MPI header file include stdio h Standard I O header file Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Local Variables int main int argc char argv int i int id Process rank int p Number of processes void check circuit int int Include argc and argv they are needed to initialize MPI One copy of every variable for each process running this program Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Initialize MPI MPI Init argc argv First MPI function called by each process Not necessarily first executable statement Allows system to do any necessary setup Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Communicators Communicator opaque object that provides message passing environment for processes MPI COMM WORLD Default communicator Includes all processes Possible to create new communicators Will do this in Chapters 8 and 9 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Communicator Communicator Name Communicator MPI COMM WORLD Processes 0 5 2 Ranks 1 4 3 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Determine Number of Processes MPI Comm size MPI COMM WORLD p First argument is communicator Number of processes returned through second argument Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Determine Process Rank MPI Comm rank MPI COMM WORLD id First argument is communicator Process rank in range 0 1 p 1 returned through second argument Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Replication of Automatic Variables id p id 0 id 1 p 6 p 6 4 id 2 p 6 id 3 p 6 6 id 5 p 6 Copyright The McGraw Hill Companies Inc Permission required for reproduction or display What about External Variables int total int main int argc char argv int i int id int p Where is variable total stored Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Cyclic Allocation of Work for i id i 65536 i p check circuit id i Parallelism is outside function check circuit It can be an ordinary sequential function Copyright The McGraw Hill Companies Inc Permission required for reproduction or display Shutting Down MPI MPI Finalize Call after all other MPI library calls Allows system to free up MPI resources Copyright The McGraw Hill Companies Inc Permission required for reproduction or display include mpi h include stdio h int main int argc char argv int i int id int p