西安交大并行计算论赵银亮课件第五章.ppt

Analytical Modeling of Parallel Systems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar Topic Overview Sources of Overhead in Parallel Programs Performance Metrics for Parallel Systems Effect of Granularity on Performance Scalability of Parallel Systems Minimum Execution Time and Minimum Cost-Optimal Execution Time Asymptotic Analysis of Parallel Programs Other Scalability Metrics Analytical Modeling - Basics A sequential algorithm is evaluated by its runtime (in general, asymptotic runtime as a function of input size). The asymptotic runtime of a sequential program is identical on any serial platform. The parallel runtime of a program depends on the input size, the number of processors, and the communication parameters of the machine. An algorithm must therefore be analyzed in the context of the underlying platform. A parallel system is a combination of a parallel algorithm and an underlying platform. Analytical Modeling - Basics A number of performance measures are intuitive. Wall clock time - the time from the start of the first processor to the stopping time of the last processor in a parallel ensemble. But how does this scale when the number of processors is changed of the program is ported to another machine altogether? How much faster is the parallel version? This begs the obvious followup question - whats the baseline serial version with which we compare? Can we use a suboptimal serial program to make our parallel program look Raw FLOP count - What good are FLOP counts when they dont solve a problem? Sources of Overhead in Parallel Programs If I use two processors, shouldnt my program run twice as fast? No - a number of overheads, including wasted computation, communication, idling, and contention cause degradation in performance. Sources of Overheads in Parallel Programs Interprocess interactions: Processors working on any non-trivial parallel problem will need to talk to each other. Idling: Processes