|
 ABSTRACT
The power of shared-memory in models of parallel computation is studied, and a novel distributed data structure that eliminates the need for shared memory without significantly increasing the run time of the parallel computation is described. More specifically, it is shown how a complete network of processors can deterministically simulate one PRAM step in O(log n/(log log n)2) time when both models use n processors and the size of the PRAM's shared memory is polynomial in n. (The best previously known upper bound was the trivial O(n)). It is established that this upper bound is nearly optimal, and it is proved that an on-line simulation of T PRAM steps by a complete network of processors requires &OHgr;(T(log n/ log log n)) time.
A simple consequence of the upper bound is that an Ultracomputer (the currently feasible general-purpose parallel machine) can simulate one step of a PRAM (the most convenient parallel model to program) in O((log n)2log log n) steps.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
|
| |
2
|
AWERBUCH, B., ISRAELI, A., AND SHILOACH, V. Efficient simulation of PRAM by Ultracomputer. Preprint, Technion, Haifa, Israel. 1983.
|
| |
3
|
|
| |
4
|
|
| |
5
|
GABBER, O., AND GALIL, Z. Explicit construction of linear-sized superconcentrators. J. Comput. Syst. Sci. 22 ( 1981 ), 407-420.
|
| |
6
|
GOTTLIEB, A., GRISHMAN, R., KRUSKAL, C. P., MCAULIFFE, K. P., RUDOLPH, L., AND SN~R, M. The NYU Ultracomputer--Designing a MIMD shared memory parallel machine. 1EEE Trans. Comput. C-32, 2 (1983), 175-189.
|
| |
7
|
|
| |
8
|
|
| |
9
|
MELHORN, K., AND VlSHKIN, U. Randomized and deterministic simulation of PRAMs by parallel machines with restricted granularity of parallel memories. In 9th Workshop on Graph Theoretic Concepts in Computer Science. Fachbereich Mathematik, Univ. Osnabruck, Osnabruck, West Germany, June 1983.
|
| |
10
|
PIPPENGER, N. Superconcentrators. SlAM J. Cornput. 6, 2 (1977), 298-304.
|
| |
11
|
ROBERTS, A. W., AND VARBERG, D.E. Convex Analysis. Academic Press, Orlando, Fla., 1973.
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
VISHKIN, U. Implementation of simultaneous memory address access in models that forbid it. J. Algorithms 4, l (1983), 45-50.
|
CITED BY 23
|
|
Andrea Pietracaprina , Geppino Pucci , Jop F. Sibeyn, Constructive deterministic PRAM simulation on a mesh-connected computer, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.248-256, June 27-29, 1994, Cape May, New Jersey, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States
|
|
|
|
|
|
P. D. MacKenzie , C. G. Plaxton , R. Rajaraman, On contention resolution protocols and associated probabilistic phenomena, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.153-162, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
|
|
|
C. Greg Plaxton , Rajmohan Rajaraman , Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.311-320, June 23-25, 1997, Newport, Rhode Island, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
André Brinkmann , Kay Salzwedel , Christian Scheideler, Efficient, distributed data placement strategies for storage area networks (extended abstract), Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.119-128, July 09-13, 2000, Bar Harbor, Maine, United States
|
|
|
|
|
|
J. M. Francioni , D. A. Poplawski , S. Pahwa, Virtual memory for a hypercube multiprocessor, Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, p.575-579, January 19-20, 1988, Pasadena, California, United States
|
|
|
Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
Gregory Chockler , Seth Gilbert , Vincent Gramoli , Peter M. Musial , Alex A. Shvartsman, Reconfigurable distributed storage for dynamic networks, Journal of Parallel and Distributed Computing, v.69 n.1, p.100-116, January, 2009
|
|
|
|
|
|
|
REVIEW
"Hosagrahar V. Jagadish : Reviewer"
In this lucidly written paper, the authors consider a “Module Parallel
Computer” model in which memory is organized into modules with only one
access being possible per module at any one time. They suggest a scheme
to keep multiple c
more...
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.1