Analysis of parallel algorithms

This article discusses the analysis of parallel algorithms. Like in the analysis of "ordinary", sequential, algorithms, one is typically interested in asymptotic bounds on the resource consumption (mainly time spent computing), but the analysis is performed in the presence of multiple processor units that cooperate to perform computations. Thus, one can determine not only how many "steps" a computation takes, but also how much faster it becomes as the number of processors goes up.

Overview

Suppose computations are executed on a machine that has p processors. Let Tp denote the time that expires between the start of the computation and its end. Analysis of the computation's running time focuses on the following notions:

Several useful results follow from the definitions of work, span and cost:

Using these definitions and laws, the following measures of performance can be given:

Execution on a limited number of processors

Analysis of parallel algorithms is usually carried out under the assumption that an unbounded number of processors is available. This is unrealistic, but not a problem, since any computation that can run in parallel on N processors can be executed on p < N processors by letting each processor execute multiple units of work. A result called Brent's law states that one can perform such a "simulation" in time Tp, bounded by[5]

T_p \leq T_N + \frac{T_1 - T_N}{p},

or, less precisely,[1]

T_p = O \left( T_N + \frac{T_1}{p} \right) .

An alternative statement of the law bounds Tp above and below by

\frac{T_1}{p} \leq T_p < \frac{T_1}{p} + T_\infty.

showing that the span (depth) T and the work T1 together provide reasonable bounds on the computation time.[2]

References

  1. 1 2 3 4 5 6 Casanova, Henri; Legrand, Arnaud; Robert, Yves (2008). Parallel Algorithms. CRC Press. p. 10.
  2. 1 2 Blelloch, Guy (1996). "Programming Parallel Algorithms" (PDF). Communications of the ACM 39 (3): 85–97. doi:10.1145/227234.227246.
  3. Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. pp. 4–5.
  4. 1 2 3 4 5 6 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 779–784. ISBN 0-262-03384-4.
  5. Gustafson, John L. (2011). "Brent's Theorem". Encyclopedia of Parallel Computing. pp. 182–185.
This article is issued from Wikipedia - version of the Monday, September 21, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.