Virtual Shared Memory: Algorithms and Complexity

AbstractWe consider the Block PRAM model of Aggarwal et al. (in "Proceedings, First Annual ACM Symposium on Parallel Algorithms and Architectures, 1989," pp. 11-21). For a Block PRAM model with n/log n processors and communication latency l = O(log n), we show that prefix sums can be performed in time O(l log n/log l), but list ranking requires time Ω(l log n); these bounds are tight. These results justify an intuitive observation of Gazit et al. (in "Proceedings, 1987 Princeton Workshop on Algorithm, Architecture and Technology Issues for Models of Concurrent Computation," pp. 139-156) that algorithm designers should, when possible, replace the list ranking procedure with the prefix sums procedure. We demonstrate the value of this technique in choosing between two optimal PRAM algorithms for finding the connected components of dense graphs. We also give theoretical improvements for integer sorting and many other algorithms based on prefix sums, and suggest a relationship between the issue of graph density for the connected components problem and alternative approaches to integer sorting