Message-Passing Programming参考.ppt

Parallel Programmingin 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 Outline Message-passing model Message Passing Interface (MPI) Coding MPI programs Compiling MPI programs Running MPI programs Benchmarking MPI programs Message-passing Model Task/Channel vs. Message-passing 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 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 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? Summa