Computational bounds for fundamental problems on general-purpose parallel models
PHILIP D. MACKENZIE, Vijaya Ramachandran · 1998
We present lower bounds for time needed to solve basic problems on three general-purpose models of parallel computation: the shared-memory models qsm and s-qsm, and the distributed-memory model, the bsp. For each of these models, we also obtain lower bounds for the number of rounds needed to solve these problems using a randomized algorithm on a p-processor machine. Our results on `rounds' is of special interest in the context of designing work-efficient algorithms on a machine where latency and synchronization costs are high. Many of our lower bound results are complemented by upper bounds that match the lower bound or are close to it. 1 Introduction Recently, there has been a great deal of interest in developing general-purpose models of parallel computation that incorporate features of real machines such as bandwidth limitations and the resulting cost for global memory accesses. The bsp [24] and logp [5] models are distributed memory models of this type, and the qsm [10] and s-qsm...