Access Restriction

Author Harris, Tim J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1994
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Bounded-degree networks ♦ Models of parallel computation ♦ Parallel complexity theory
Abstract The Parallel Random Access Machine (PRAM) is an abstract model of parallel computation which allows researchers to focus on the essential characteristics of a parallel architecture and ignore other details. The PRAM has long been acknowledged to be a useful tool for the study of parallel computing, but unfortunately it is not physically implementable in hardware. In order to take advantage of the broad base of algorithms and results regarding this high-level abstraction one needs general methods for allowing the execution of PRAM algorithms on more realistic machines. In the following we survey these methods, which we refer to as PRAM simulation techniques. The general issues of memory management and routing are discussed, and both randomized and deterministic solutions are considered. We show that good theoretical solutions to many of the subproblems in PRAM simulation have been developed, though questions still exist as to their practical utility. This article should allow those performing research in this field to become well acquainted with the current state of the art, while allowing the novice to get an intuitive feeling for the fundamental questions being considered. The introduction should provide a concise tutorial for those unfamiliar with the problem of PRAM simulation.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1994-06-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 26
Issue Number 2
Page Count 20
Starting Page 187
Ending Page 206

Open content in new tab

   Open content in new tab
Source: ACM Digital Library