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. 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. 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: