Parallel-Algorithm-Desig课件

1、Parallel Programmingin C with MPI and OpenMPMichael J. QuinnChapter 3Parallel Algorithm DesignOutlineTask/channel modelAlgorithm design methodologyCase studiesTask/Channel ModelParallel computation = set of tasksTaskProgramLocal memoryCollection of I/O portsTasks interact by sending messages through

2、 channelsTask/Channel ModelTaskChannelFosters Design MethodologyPartitioningCommunicationAgglomerationMappingFosters MethodologyPartitioningDividing computation and data into piecesDomain decompositionDivide data into piecesDetermine how to associate computations with the dataFunctional decompositio

3、nDivide computation into piecesDetermine how to associate data with the computationsExample Domain DecompositionsExample Functional DecompositionPartitioning ChecklistAt least 10 x more primitive tasks than processors in target computerMinimize redundant computations and redundant data storagePrimit

4、ive tasks roughly the same sizeNumber of tasks an increasing function of problem sizeCommunicationDetermine values passed among tasksLocal communicationTask needs values from a small number of other tasksCreate channels illustrating data flowGlobal communicationSignificant number of tasks contribute

5、 data to perform a computationDont create channels for them early in designCommunication ChecklistCommunication operations balanced among tasksEach task communicates with only small group of neighborsTasks can perform communications concurrentlyTask can perform computations concurrentlyAgglomeration

6、Grouping tasks into larger tasksGoalsImprove performanceMaintain scalability of programSimplify programmingIn MPI programming, goal often to create one agglomerated task per processorAgglomeration Can Improve PerformanceEliminate communication between primitive tasks agglomerated into consolidated t

7、askCombine groups of sending and receiving tasksAgglomeration ChecklistLocality of parallel algorithm has increasedReplicated computations take less time than communications they replaceData replication doesnt affect scalabilityAgglomerated tasks have similar computational and communications costsNu

8、mber of tasks increases with problem sizeNumber of tasks suitable for likely target systemsTradeoff between agglomeration and code modifications costs is reasonableMappingProcess of assigning tasks to processorsCentralized multiprocessor: mapping done by operating systemDistributed memory system: ma

9、pping done by userConflicting goals of mappingMaximize processor utilizationMinimize interprocessor communicationMapping ExampleOptimal MappingFinding optimal mapping is NP-hardMust rely on heuristicsMapping Decision TreeStatic number of tasksStructured communicationConstant computation time per tas

10、kAgglomerate tasks to minimize commCreate one task per processorVariable computation time per taskCyclically map tasks to processorsUnstructured communicationUse a static load balancing algorithmDynamic number of tasksMapping StrategyStatic number of tasksDynamic number of tasksFrequent communicatio

11、ns between tasksUse a dynamic load balancing algorithmMany short-lived tasksUse a run-time task-scheduling algorithmMapping ChecklistConsidered designs based on one task per processor and multiple tasks per processorEvaluated static and dynamic task allocationIf dynamic task allocation chosen, task

12、allocator is not a bottleneck to performanceIf static task allocation chosen, ratio of tasks to processors is at least 10:1Case StudiesBoundary value problemFinding the maximumThe n-body problemAdding data inputBoundary Value ProblemIce waterRodInsulationRod Cools as Time ProgressesFinite Difference

13、 ApproximationPartitioningOne data item per grid pointAssociate one primitive task with each grid pointTwo-dimensional domain decompositionCommunicationIdentify communication pattern between primitive tasksEach interior primitive task has three incoming and three outgoing channelsAgglomeration and M

14、appingAgglomerationSequential execution time time to update elementn number of elementsm number of iterationsSequential execution time: m (n-1) Parallel Execution Timep number of processors message latencyParallel execution time m(n-1)/p+2)Finding the Maximum Error6.25%ReductionGiven associative ope

15、rator a0 a1 a2 an-1ExamplesAddMultiplyAnd, OrMaximum, MinimumParallel Reduction EvolutionParallel Reduction EvolutionParallel Reduction EvolutionBinomial TreesSubgraph of hypercubeFinding Global Sum4207-35-6-38123-446-1Finding Global Sum17-644582Finding Global Sum8-2910Finding Global Sum178Finding G

16、lobal Sum25Binomial TreeAgglomerationAgglomerationsumsumsumsumThe n-body ProblemThe n-body ProblemPartitioningDomain partitioningAssume one task per particleTask has particles position, velocity vectorIterationGet positions of all other particlesCompute new position, velocityGatherAll-gatherComplete Graph for All-gatherHypercube for All-gatherCommunication TimeHypercubeComplete graphAdding Data InputScatterScatter in log p Steps1234567856781234 56 12 7834Summary: Task/channel ModelParallel computationSet of tasksInteractions through channelsGood designsMaximize local