Pop QuizAssume 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?
Parallel Programming in C with MPI and OpenMP Michael J. Quinn
Chapter 4 Message-Passing Programming
Learning Objectives
Understanding how MPI programs execute
Familiarity with fundamental MPI functions
Task/Channel Message-passing Task Process Explicit channels Any-to-any communication
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
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
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
Circuit Satisfiability
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Not satisfied 0
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
Partitioning: Functional Decomposition
Embarrassingly parallel: No channels between tasks
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
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
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?
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
Include Files
#include Standard I/O header file #include MPI header file
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
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
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
Comments