Virtual shared memory: Algorithms and complexity (Q1333257)

The paper deals with the study of parallel computers and analyzes how assumptions on the cost of access to memory affect the choice of algorithm. In particular, the authors study the block PRAM model of Agarwal et al. In this model a processor can access a block of \(b\) bit in global memory in time \(\ell + b\) where \(\ell\) is a function of the number of processors \(p\). Two particular popular functions to use as \(\ell\) are \(\sqrt{p}\) and \(\log p\). This models the mesh and the hypercube respectively with unit delays on wires. The PRAM is also assumed to be EREW (exclusive read and exclusive write). The problems studied are list ranking and prefix sums which are two problems which are commonly used as subroutines in parallel algorithms and hence they are of fundamental importance. For prefix sum an algorithm is given that runs in time \(O(n/p + \ell \log n /\log \ell)\) which is known to be optimal from general results. For list ranking a lower bound of \[ \Omega(\min(\ell n/p, (n\log p)/(p \log (n/\ell p)))) \] is given for any algorithm that is shortcut-based, a term that is defined in the paper ad encompasses all standard parallel algorithms for the problem. Thus, for instance, for the case \(\ell p = n\) this indicates that list ranking is more difficult than prefix sums and thus the authors suggest to replace the former by the latter as a subroutine for instance in integer sorting, tree contraction and finding connected components.