Trade-Offs between Depth and Width in Parallel Computation
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.
- Depth-size trade-offs for parallel prefix computation
- Time-work tradeoffs for parallel algorithms
- scientific article; zbMATH DE number 3940742
- Processor Allocation for Horizontal and Vertical Parallelism and Related Speedup Bounds
- Dimension-wise decompositions and their efficient parallelization
- On saving space in parallel computation
- scientific article; zbMATH DE number 4085015
- Modular-width: an auxiliary parameter for parameterized parallel complexity
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Separation and lower bounds for ROM and nondeterministic models of parallel computation
- Limits on the power of concurrent-write parallel machines
- Simulations among concurrent-write PRAMs
- Lower bound arguments with ``inaccessible numbers
- Some considerations about NPRIORITY(1) without ROM
- On saving space in parallel computation
- Processor-time tradeoffs in PRAM simulations
- PRAMs with variable word-size
- Separating the power of EREW and CREW PRAMs with small communication width
- Gossiping and broadcasting versus computing functions in networks.
- Processor-time tradeoffs under bounded-speed message propagation. II: Lower bounds
- Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
- On the space and access complexity of computation DAGs
- scientific article; zbMATH DE number 3940742 (Why is no real title available?)
- scientific article; zbMATH DE number 4060722 (Why is no real title available?)
- Lower bounds on the complexity of real-time branching programs
- Gossiping and broadcasting versus computing functions in networks
- Separating the power of EREW and CREW PRAMs with small communication width
- Properties of complexity measures for PRAMs and WRAMs
- On the power of concurrent-write PRAMs with read-only memory
- The power of multimedia: Combining point-to-point and multi-access networks
- Trade-offs between communication throughput and parallel time
- Compression using efficient multicasting
- Resource bounds for parallel computation of threshold and symmetric functions
- Parallel random access machines with bounded memory wordsize
- Lower bounds for recognizing small cliques on CRCW PRAM's
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)