Parallel Programming in C with the Message Passing Interface

Parallel Programming in C with the Message Passing Interface

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. 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. Circuit Satisfiability 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 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 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 P0: 0, 5, 10 P1: 1, 6, 11 P2: 2, 7 P3: 3, 8 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 header file #include 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 messagepassing 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 0 id

id p id p 4 6 p p 6 6

3 id 2 1 6 p id 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 #include

int main (int argc, char *argv[]) { int i; int id; int p; void check_circuit (int, int); MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &id); MPI_Comm_size (MPI_COMM_WORLD, &p); for (i = id; i < 65536; i += p) check_circuit (id, i); printf ("Process %d is done\n", id); fflush (stdout); MPI_Finalize(); return 0; }

Put fflush() after every printf() Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. /* Return 1 if 'i'th bit of 'n' is 1; 0 otherwise */ #define EXTRACT_BIT(n,i) ((n&(1<

&& (v[6] || !v[15]) && (v[7] || !v[8]) && (!v[7] || !v[13]) && (v[8] || v[9]) && (v[8] || !v[9]) && (!v[9] || !v[10]) && (v[9] || v[11]) && (v[10] || v[11]) && (v[12] || v[13]) && (v[13] || !v[14]) && (v[14] || v[15])) { printf ("%d) %d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d\n", id, v[0],v[1],v[2],v[3],v[4],v[5],v[6],v[7],v[8],v[9], v[10],v[11],v[12],v[13],v[14],v[15]); fflush (stdout); } } Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Compiling MPI Programs mpicc -O -o foo foo.c mpicc: script to compile and link C+MPI programs Flags: same meaning as C compiler -O optimize -o where to put executable Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Running MPI Programs mpirun -np

-np

number of processes executable command-line arguments

Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Specifying Host Processors File .mpi-machines in home directory lists host processors in order of their use Example .mpi_machines file contents band01.cs.ppu.edu band02.cs.ppu.edu band03.cs.ppu.edu band04.cs.ppu.edu Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Enabling Remote Logins MPI needs to be able to initiate processes on other processors without supplying a password Each processor in group must list all other processors in its .rhosts file; e.g., band01.cs.ppu.edu band02.cs.ppu.edu band03.cs.ppu.edu band04.cs.ppu.edu student student student

student Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Execution on 1 CPU % mpirun -np 1 sat 0) 1010111110011001 0) 0110111110011001 0) 1110111110011001 0) 1010111111011001 0) 0110111111011001 0) 1110111111011001 0) 1010111110111001 0) 0110111110111001 0) 1110111110111001

Process 0 is done Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Execution on 2 CPUs % mpirun -np 2 sat 0) 0110111110011001 0) 0110111111011001 0) 0110111110111001 1) 1010111110011001 1) 1110111110011001 1) 1010111111011001 1) 1110111111011001 1) 1010111110111001 1) 1110111110111001

Process 0 is done Process 1 is done Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Execution on 3 CPUs % mpirun -np 3 sat 0) 0110111110011001 0) 1110111111011001 2) 1010111110011001 1) 1110111110011001 1) 1010111111011001 1) 0110111110111001 0) 1010111110111001 2) 0110111111011001

2) 1110111110111001 Process 1 is done Process 2 is done Process 0 is done Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Deciphering Output Output order only partially reflects order of output events inside parallel computer If process A prints two messages, first message will appear before second If process A calls printf before process B, there is

no guarantee process As message will appear before process Bs message Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Enhancing the Program We want to find total number of solutions Incorporate sum-reduction into program Reduction is a collective communication Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Modifications Modify function check_circuit

Return 1 if circuit satisfiable with input combination Return 0 otherwise Each process keeps local count of satisfiable circuits it has found Perform reduction after for loop Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. New Declarations and Code int count; /* Local sum */ int global_count; /* Global sum */ int check_circuit (int, int); count = 0;

for (i = id; i < 65536; i += p) count += check_circuit (id, i); Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Prototype of MPI_Reduce() int MPI_Reduce ( void *operand, /* addr of 1st reduction element */ void *result, /* addr of 1st reduction result */ int count, /* reductions to perform */ MPI_Datatype type, /* type of elements */ MPI_Op operator, /* reduction operator */

int root, /* process getting result(s) */ MPI_Comm comm /* communicator */ ) Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. MPI_Datatype Options MPI_CHAR MPI_DOUBLE MPI_FLOAT MPI_INT MPI_LONG MPI_LONG_DOUBLE MPI_SHORT

MPI_UNSIGNED_CHAR MPI_UNSIGNED MPI_UNSIGNED_LONG MPI_UNSIGNED_SHORT Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. MPI_Op Options MPI_BAND MPI_BOR MPI_BXOR MPI_LAND MPI_LOR MPI_LXOR MPI_MAX

MPI_MAXLOC MPI_MIN MPI_MINLOC MPI_PROD MPI_SUM Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Our Call to MPI_Reduce() MPI_Reduce (&count, &global_count, 1, MPI_INT, MPI_SUM, Only process 0 0,

will get the result MPI_COMM_WORLD); if (!id) printf ("There are %d different solutions\n", global_count); Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Execution of Second Program % mpirun -np 3 seq2 0) 0110111110011001 0) 1110111111011001 1) 1110111110011001 1) 1010111111011001 2) 1010111110011001 2) 0110111111011001 2) 1110111110111001

1) 0110111110111001 0) 1010111110111001 Process 1 is done Process 2 is done Process 0 is done There are 9 different solutions Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Benchmarking the Program MPI_Barrier barrier synchronization MPI_Wtick timer resolution MPI_Wtime current time Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Benchmarking Code double elapsed_time; MPI_Init (&argc, &argv); MPI_Barrier (MPI_COMM_WORLD); elapsed_time = - MPI_Wtime(); MPI_Reduce (); elapsed_time += MPI_Wtime(); Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Benchmarking Results Processors

Time (sec) 1 15.93 2 8.38 3 5.86

4 4.60 5 3.77 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Benchmarking Results 20 15 Execution Time

10 Perfect Speed Improvement 5 (msec) Time 0 1 2 3 Processors

4 5 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Summary (1/2) Message-passing programming follows naturally from task/channel model Portability of message-passing programs MPI most widely adopted standard Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Summary (2/2) MPI functions introduced MPI_Init MPI_Comm_rank MPI_Comm_size MPI_Reduce MPI_Finalize MPI_Barrier MPI_Wtime MPI_Wtick Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Chapter 6

Floyds Algorithm Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Chapter Objectives Creating 2-D arrays Thinking about grain size Introducing point-to-point communications Reading and printing 2-D matrices Analyzing performance when computations and communications overlap Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Outline

All-pairs shortest path problem Dynamic 2-D arrays Parallel algorithm design Point-to-point communication Block row matrix I/O Analysis and benchmarking Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. All-pairs Shortest Path Problem 4 A 3 B

6 C 5 1 1 D E 2 3

A B C D E A 0 6

3 6 4 B 4 0 7

10 8 C 12 6 0 3 1 D

7 3 10 0 11 E 9

5 12 2 0 Resulting Adjacency Matrix Containing Distances Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Floyds Algorithm for k 0 to n-1 for i 0 to n-1

for j 0 to n-1 a[i,j] min (a[i,j], a[i,k] + a[k,j]) endfor endfor endfor Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Why It Works Shortest path from i to k through 0, 1, , k-1 i Shortest path from i to j through 0, 1, , k-1

Computed in previous iterations j k Shortest path from k to j through 0, 1, , k-1 Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Dynamic 1-D Array Creation

Run-time Stack Heap A Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Dynamic 2-D Array Creation Run-time Stack Bstorage Heap B

Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Designing Parallel Algorithm Partitioning Communication Agglomeration and Mapping Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Partitioning Domain or functional decomposition? Look at pseudocode Same assignment statement executed n3 times No functional parallelism

Domain decomposition: divide matrix A into its n2 elements Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Communication Primitive tasks Iteration k: every task in row k broadcasts its value w/in task column

Updating a[3,4] when k=1 Iteration k: every task in column k broadcasts its value w/in task row Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Agglomeration and Mapping

Number of tasks: static Communication among tasks: structured Computation time per task: constant Strategy: Agglomerate tasks to minimize communication Create one task per MPI process Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Two Data Decompositions Rowwise block striped Columnwise block striped Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Comparing Decompositions Columnwise block striped Broadcast within columns eliminated Rowwise block striped Broadcast within rows eliminated Reading matrix from file simpler Choose rowwise block striped decomposition Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. File Input

File Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Pop Quiz Why dont we input the entire file at once and then scatter its contents among the processes, allowing concurrent message passing? Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Point-to-point Communication Involves a pair of processes

One process sends a message Other process receives the message Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Send/Receive Not Collective Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Function MPI_Send int MPI_Send ( ) void

*message, int count, MPI_Datatype datatype, int dest,

int tag, MPI_Comm comm Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Function MPI_Recv int MPI_Recv ( void *message,

int count, MPI_Datatype datatype, int source, int

tag, MPI_Comm comm, MPI_Status ) *status Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Coding Send/Receive

if (ID == j) { Receive from I } if (ID == i) { Send to j } Receive is before Send. Why does this work?

Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. variantes de send http://www.mcs.anl.gov/research/projects/mpi/ sendmode.html Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Inside MPI_Send and MPI_Recv Sending Process Program Memory MPI_Send

System Buffer Receiving Process System Buffer MPI_Recv Program Memory Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Return from MPI_Send Function blocks until message buffer free Message buffer is free when Message copied to system buffer, or Message transmitted Typical scenario Message copied to system buffer Transmission overlaps computation Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Return from MPI_Recv Function blocks until message in buffer If message never arrives, function never returns

Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Deadlock Deadlock: process waiting for a condition that will never become true Easy to write send/receive code that deadlocks Two processes: both receive before send Send tag doesnt match receive tag Process sends message to wrong destination process Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Function MPI_Bcast

int MPI_Bcast ( void *buffer, /* Addr of 1st element */ int count, /* # elements to broadcast */ MPI_Datatype datatype, /* Type of elements */ int root, MPI_Comm comm) /* ID of root process */ /* Communicator */ MPI_Bcast (&k, 1, MPI_INT, 0, MPI_COMM_WORLD);

Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Computational Complexity Innermost loop has complexity (n) Middle loop executed at most n/p times Outer loop executed n times Overall complexity (n3/p) Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Communication Complexity No communication in inner loop No communication in middle loop Broadcast in outer loop complexity is (n log p) Overall complexity (n2 log p)

Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Execution Time Expression (1) n n / p n + n log p ( + 4n / ) Message-passing time Messages per broadcast Iterations of outer loop Cell update time Iterations of inner loop Iterations of middle loop Iterations of outer loop Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Computation/communication Overlap Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Execution Time Expression (2) n n / p n + n log p + log p 4n / Message transmission Message-passing time Messages per broadcast Iterations of outer loop Cell update time Iterations of inner loop Iterations of middle loop

Iterations of outer loop Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Predicted vs. Actual Performance Execution Time (sec) Processes Predicted Actual 1 25.54

25.54 2 13.02 13.89 3 9.01 9.60

4 6.89 7.29 5 5.86 5.99 6 5.01

5.16 7 4.40 4.50 8 3.94 3.98

Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Summary Two matrix decompositions Rowwise block striped Columnwise block striped Blocking send/receive functions MPI_Send MPI_Recv Overlapping communications with computations

Recently Viewed Presentations

  • The Effects of New Technology on the Growth of a Teaching and ...

    The Effects of New Technology on the Growth of a Teaching and ...

    The Effects of New Technology on the Growth of a Teaching and Learning Network Roberta Spalter-Roth, Principal Investigator Olga Mayorova and Jean Shin, Co-Principal Investigators (NSF Award# 0837121) This National Science Foundation-funded study examines the adoption patterns of the American...
  • Digestive System Organs

    Digestive System Organs

    Lingual lipase. Salivary Glands. More . Secretions-Lysozyme- antibacterial. Lingual lipase- triglycerides in to fatty acids and monoglycerides (not activated until stomach is acidic) 2.Pharynx. Primary organ- passageway for food, liquid, and air.
  • Tips for Providing Positive and Concise Feedback on Student ...

    Tips for Providing Positive and Concise Feedback on Student ...

    Tips for Providing Positive and Concise Feedback on Student Writing. Javier Ospina & Ellen Ratajack. Department of Psychology . March 11, 2015
  • Transforming the Network - Ammannato

    Transforming the Network - Ammannato

    Transforming the Network: Implications for Telecom Power Marketing Intelec 2004 Chicago September 22, 2004 Wireless/Wireline Parity POTS to PIPES Major Telco Priorities DC Power Systems Local Exchange Carriers ILEC Network Before C2P ILEC Network After C2P Access Network Infrastructure Fiber-to-the-Node...
  • Role of SAIs in promoting and audit of

    Role of SAIs in promoting and audit of

    To date, SAO IT audit department has performed about four Information system audit and IT security audit engagements including Ministry of Finance's AFMIS and SIGTAS GRP systems and M-Power Grid system of Power Utility (a corporation) of the Government.
  • Aegean Culture and Early Greece - Pearson Education

    Aegean Culture and Early Greece - Pearson Education

    Orientalizing Period: ca. 700-600 B.C.E. - Ceramic designs influenced by trade from Near East. Sculpture inspired by Egyptian models. The Archaic period: ca. 600-480 B.C.E. - black-figure and red-figure pottery.
  • IGCSE: The USA, 1919-41 (Depth Study) - moodle2.bs-gc.net

    IGCSE: The USA, 1919-41 (Depth Study) - moodle2.bs-gc.net

    IGCSE: The USA, 1919-41 (Depth Study) How successful was the New Deal? Rebellion. The US was in a state of rebellion when FDR took office. Desperate people were not waiting for the government to help them; they were helping themselves,...
  • Math 2240 - Linear Algebra

    Math 2240 - Linear Algebra

    We can find the solutions to a system in row-echelon form using back substitution. Solving a system not in r-e form. We say that two systems of equations (or equations) are equivalent, if they have exactly the same solutions. One...