We study the effect of limited communication throughput on parallel computa
tion in a setting where the number of processors is much smaller than the l
ength of the input. Our model has p processors that communicate through a s
hared memory of size rn. The input has size n and can be read directly by a
ll the processors. We will be primarily interested in studying cases where
n much greater than p much greater than m. As a test case we study the list
reversal problem. For this problem we prove a time lower bound of Omega(n/
root mp). (A similar lower bound holds also for the problems of sorting, fi
nding all unique elements, convolution, and universal hashing.) This result
demonstrates that limiting the communication (i.e., small m) could have si
gnificant effect on parallel computation. We show an almost matching upper
bound of O((n/root mp) log (O(1))n). The upper bound requires the developme
nt of a few interesting techniques which can alleviate the limited communic
ation in some general settings.
Specifically, we show how to emulate a large shared memory on a limited sha
red memory efficiently. The lower bound applies even to randomized machines
, and the upper bound is a randomized algorithm. We also argue that some st
andard methodology for designing parallel algorithms appears to require a r
elatively high level of communication throughput. Our results suggest that
new alternative methodologies that need a lower such level must be invented
for parallel machines that enable a low level of communication throughput,
since otherwise those machines will be severly handicapped as general purp
ose parallel machines. Although we do not rule that out, we cannot offer an
y encouraging evidence to suggest that such new methodologies are likely to
be found. (C) 1999 Academic Press.