DocumentCode :
2454510
Title :
On the power of randomization for the common PRAM
Author :
Berkman, Omer ; Gibbons, Phillip B. ; Matias, Yossi
Author_Institution :
Algorithmic Res. Ltd., Givaat Shmuel, Israel
fYear :
1995
fDate :
4-6 Jan 1995
Firstpage :
229
Lastpage :
240
Abstract :
Recent years have seen a dramatic increase in the number of nearly-constant time parallel algorithms. Paradigms and techniques have been developed to exploit the power of randomization and to obtain O(lg*n) time, linear work algorithms for quite a few problems, including linear approximate compaction, load balancing, approximate prefix sums, and range-minima. These algorithms run on most of the popular CRCW PRAM models which allow conflict in concurrent write. However, none of the newly-developed log-star algorithms run on the COMMON CRCW PRAM, one of the more studied CRCW models in the literature on parallel algorithms. The COMMON model requires processors writing simultaneously into the same memory cell to write the same value only. This restriction, which forbids conflicts in concurrent write, makes it difficult to claim resources at random - an operation which is at the heart of the fast randomized algorithms mentioned above-and it may have led to the belief that randomization has limited utility on the COMMON. In this paper we show that in many cases this inherent difficulty can be circumvented, and we present the first log-star COMMON algorithms for a number of fundamental problems. Thus, our results provide the first broad demonstration of the power of randomization for the COMMON model
Keywords :
computational complexity; parallel algorithms; randomised algorithms; CRCW PRAM models; approximate prefix sums; common PRAM; linear approximate compaction; load balancing; log-star COMMON algorithms; log-star algorithms; nearly-constant time parallel algorithms; power of randomization; range-minima; Compaction; Computer science; Heart; Linear approximation; Load management; Parallel algorithms; Phase change random access memory; Power engineering and energy; Read-write memory; Writing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Theory of Computing and Systems, 1995. Proceedings., Third Israel Symposium on the
Conference_Location :
Tel Aviv
Print_ISBN :
0-8186-6915-2
Type :
conf
DOI :
10.1109/ISTCS.1995.377027
Filename :
377027
Link To Document :
بازگشت