Parallel Algorithm Design参考.ppt

Parallel Programmingin C with MPI and OpenMP Michael J. Quinn Chapter 3 Parallel Algorithm Design Outline Task/channel model Algorithm design methodology Case studies Task/Channel Model Parallel computation = set of tasks Task Program Local memory Collection of I/O ports Tasks interact by sending messages through channels Task/Channel Model Foster’s Design Methodology Partitioning Communication Agglomeration Mapping Foster’s Methodology Partitioning Dividing computation and data into pieces Domain decomposition Divide data into pieces Determine how to associate computations with the data Functional decomposition Divide computation into pieces Determine how to associate data with the computations Example Domain Decompositions Example Functional Decomposition Partitioning Checklist At least 10x more primitive tasks than processors in target computer Minimize redundant computations and redundant data storage Primitive tasks roughly the same size Number of tasks an increasing function of problem size Communication Determine values passed among tasks Local communication Task needs values from a small number of other tasks Create channels illustrating data flow Global communication Significant number of tasks contribute data to perform a computation Don’t create channels for them early in design Communication Checklist Communication operations balanced among tasks Each task communicates with only small group of neighbors Tasks can perform communications concurrently Task can perform computations concurrently Agglomeration Grouping tasks into larger tasks Goals Improve performance Maintain scalability of program Simplify programming In MPI programming, goal often to create one agglomerated task per processor Agglomeration Can Improve Performance Eliminate communication between primitive tasks agglomerated into consolidated task Combine groups of sending and receiving tasks Agglomeration Checklist Locality of parallel algorithm has increased Replicated computations take le