Trade-offs between depth and width in parallel computation. (English) Zbl 0573.68015

Based on the Concurrent-Read Concurrent-Write PRAM and the Concurrent- Read Exclusive-Write PRAM models of parallel computation several results are derived concerning the trade-off between the time complexity T (or depth) and the size m of the common memory (or communication width). For a wide variety of problems (including parity, majority, and summation) it is shown that \(mT^ 2=\Omega (n)\) holds for the CRCW PRAM regardless of the number of processors and that for a class of simpler functions \(mT^ 3=\Omega (n)\) holds for the CREW PRAM where n is the size of the input. The proofs use an interesting new technique for proving nontrivial lower bounds for parallel computation called circumvention. It allows to restrict attention to classes of inputs leading to ”easy to analyze” computations, thereby circumventing the analysis of more difficult situations. The lower bound for the CRCW PRAM is shown to be tight for all values of width m in \(O(n/\log^ 2n).\)
By carefully motivating definitions and informally discussing ideas of proofs the authors succeed in making the paper a pleasure to read.
Reviewer: H.Schmeck


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI