Programming parallel algorithms

Reviewer: Lorie M. Liebrock

Blelloch presents features of the language NESL that are the “most important for programming parallel algorithms”: a performance model based on work and depth, and nestable data-parallel constructs. The paper focuses on work (total number of operations) and depth (longest chain of sequential dependencies) for computations. The author claims that “models based on work and depth are better than processor-based models for programming and analyzing parallel algorithms.” Motivation is based on the Quicksort algorithm and its analysis. The NESL code is simple, the analysis closely follows the code, and parallelism is expressed at a high level. Work, W , provides a measure of the running time for a single processor, while depth, D , provides a measure of the running time for an infinite number of processors. A bound for the time T on P processors is W D ?T< W P +D . Work and depth do not account for communication costs, which leads to poor predictions of runtime on machines with communication bottlenecks. With some modification, if network bandwidth is sufficient, then “reasonable predictions” result<__?__Pub Caret> (for example, for the Cray T3E and SGI Power Challenge). NESL algorithms and analysis are presented for a variety of problems with nested parallelism. This approach makes analysis of some algorithms, perhaps most algorithms, simpler. Therefore, work and depth analysis simplifies determination of how the running time grows as a function of the size of the input. Unfortunately, this analysis does not necessarily translate easily to performance predictions for a given machine architecture.