Trade-Offs between Depth and Width in Parallel Computation

From MaRDI portal





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.




Cited in
(26)








This page was built for publication: Trade-Offs between Depth and Width in Parallel Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3691060)