The Library
An optical simulation of shared memory
Tools
UNSPECIFIED (1999) An optical simulation of shared memory. SIAM JOURNAL ON COMPUTING, 28 (5). pp. 1829-1847. ISSN 0097-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
We present a work-optimal randomized algorithm for simulating a shared memory machine (pram) on an optical communication parallel computer (OCPC). The OCPC model is motivated by the potential of optical communication for parallel computation. The memory of an OCPC is divided into modules, one module per processor. Each memory module only services a request on a timestep if it receives exactly one memory request.
Our algorithm simulates each step of an n lg lg n-processor EREW pram on an n-processor OCPC in O(lg lg n) expected delay. (The probability that the delay is longer than this is at most n(-alpha) for any constant alpha.) The best previous simulation, due to Valiant, required Theta(lg n) expected delay.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | SIAM JOURNAL ON COMPUTING | ||||
Publisher: | SIAM PUBLICATIONS | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 26 May 1999 | ||||
Dates: |
|
||||
Volume: | 28 | ||||
Number: | 5 | ||||
Number of Pages: | 19 | ||||
Page Range: | pp. 1829-1847 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |