《Performance Analysis》由会员分享，可在线阅读，更多相关《Performance Analysis（49页珍藏版）》请在金锄头文库上搜索。
1、Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Parallel Programming with MPI and OpenMPMichael J. QuinnCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Chapter 7Performance AnalysisCopyright The McGraw-Hill Companies
2、, Inc. Permission required for reproduction or display.Learning ObjectivesnPredict performance of parallel programsnUnderstand barriers to higher performanceCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.OutlinenGeneral speedup formulanAmdahls LawnGustafson
3、-Barsis LawnKarp-Flatt metricnIsoefficiency metricCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Speedup FormulaCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Execution Time ComponentsnInherently sequential computa
4、tions: (n)nPotentially parallel computations: (n)nCommunication operations: (n,p)Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Speedup ExpressionCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.(n)/pCopyright The Mc
5、Graw-Hill Companies, Inc. Permission required for reproduction or display.(n,p)Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.(n)/p + (n,p)Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Speedup Plot“elbowing out”Co
6、pyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.EfficiencyCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.0 (n,p) 1All terms 0 (n,p) 0Denominator numerator (n,p) 1Copyright The McGraw-Hill Companies, Inc. Permission re
7、quired for reproduction or display.Amdahls LawLet f = (n)/(n) + (n)Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Example 1n95% of a programs execution time occurs inside a loop that can be executed in parallel. What is the maximum speedup we should expect
8、from a parallel version of the program executing on 8 CPUs?Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Example 2n20% of a programs execution time is spent within inherently sequential code. What is the limit to the speedup achievable by a parallel versio
9、n of the program?Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Pop QuiznAn oceanographer gives you a serial program and asks you how much faster it might run on 8 processors. You can only find one function amenable to a parallel solution. Benchmarking on a
10、 single processor reveals 80% of the execution time is spent inside this function. What is the best speedup a parallel version is likely to achieve on 8 processors?Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Pop QuiznA computer animation program generate
11、s a feature movie frame-by-frame. Each frame can be generated independently and is output to its own file. If it takes 99 seconds to render a frame and 1 second to output it, how much speedup can be achieved by rendering the movie on 100 processors?Copyright The McGraw-Hill Companies, Inc. Permissio
12、n required for reproduction or display.Limitations of Amdahls LawnIgnores (n,p)nOverestimates speedup achievableCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Amdahl EffectnTypically (n,p) has lower complexity than (n)/pnAs n increases, (n)/p dominates (n,p
13、)nAs n increases, speedup increasesCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Illustration of Amdahl Effectn = 100n = 1,000n = 10,000SpeedupProcessorsCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Review of Amd
14、ahls LawnTreats problem size as a constantnShows how execution time decreases as number of processors increasesCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Another PerspectivenWe often use faster computers to solve larger problem instancesnLets treat time
15、 as a constant and allow problem size to increase with number of processorsCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Gustafson-Barsiss LawLet s = (n)/(n)+(n)/p)Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Gu
16、stafson-Barsiss LawnBegin with parallel execution timenEstimate sequential execution time to solve same problemnProblem size is an increasing function of pnPredicts scaled speedupCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Example 1nAn application running on 10 processors spends 3% of its time in serial code. What is t
