A more practical PRAM model
Published 1 March 1989Open access
Phillip B. Gibbons
Citations228
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper introduces the Asynchronous PRAM model of computation, a variant of the PRAM in which the processors run asy ~chronously and there is an explicit charge for synchronization.
Abstract
Article Free Access Share on A more practical PRAM model Author: P. B. Gibbons Computer Science Division, University of California, Berkeley, CA Computer Science Division, University of California, Berkeley, CAView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 158–168https://doi.org/10.1145/72935.72953Online:01 March 1989Publication History 117citation1,266DownloadsMetricsTotal Citations117Total Downloads1,266Last 12 Months116Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Keywords
Computer Science
Journal of the ACMThe Parallel Evaluation of General Arithmetic Expressions
818 Citations1974Richard P. Brent
It is shown that arithmetic expressions with n ≥ 1 variables and constants; operations of addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated in time 4 log 2 + 10(n - 1) using processors which can independently perform arithmetic operations in unit time.
Matrix multiplication via arithmetic progressions
635 Citations1987Don Coppersmith, S. Winograd
A new method for accelerating matrix multiplication asymptotically is presented, by using a basic trilinear form which is not a matrix product, and making novel use of the Salem-Spencer Theorem.
SIAM Journal on ComputingAn Efficient Parallel Biconnectivity Algorithm
523 Citations1985Robert E. Tarjan, Uzi Vishkin
A new algorithm for finding the blocks (biconnected components) of an undirected graph and a general algorithmic technique that simplifies and improves computation of various functions on trees is introduced.
COMBINATORICASorting inc logn parallel steps
513 Citations1983Miklós Ajtai, János Komlós +1 more
A sorting network withcn logn comparisons where in thei-th step of the algorithm the contents of registersRj, andRk, wherej, k are absolute constants then change their contents or not according to the result of the comparison.
Information and ControlDeterministic coin tossing with applications to optimal parallel list ranking
424 Citations1986Richard Cole, Uzi Vishkin
The algorithms apply a novel “random-like” deterministic technique that provides for a fast and efficient breaking of an apparently symmetric situation in parallel and distributed computation.
SIAM Journal on ComputingTowards an Architecture-Independent Analysis of Parallel Algorithms
387 Citations1990Christos H. Papadimitriou, Mihalis Yannakakis
A Survey of Parallel Algorithms for Shared-Memory Machines
322 Citations1988Richard M. Karp
A survey of the growing body of theory concerned with parallel algorithms and the complexity of parallel computation, which considers the parallel random-access machine (PRAM), in which it is assumed that each processor has random access in unit time to any cell of a global memory.
Theoretical Computer ScienceA complexity theory of efficient parallel algorithms
228 Citations1990Clyde P. Kruskal, Larry Rudolph +1 more
The relationship between various models of parallel computation is investigated, using a newly defined concept of efficient simulation, and it is proved that the class PE is invariant across the shared memory models (PRAM's) and fully connected message passing machines.
How to emulate shared memory
219 Citations1987Abhiram Ranade
This work presents a simple algorithm for emulating an N processor CRCW PRAM on an N node butterfly that improves the result of Pippenger by routing permutations with bounded queues in logarithmic time, without the possibility of deadlock.
Approximate and exact parallel scheduling with applications to list, tree and graph problems
176 Citations1986Richard Cole, Uzi Vishkin
A novel scheduling problem is defined; it is solved by repeated, rapid, approximate reschedulings, which leads to a first optimal PRAM algorithm for list ranking, which runs in logarithmic time.
The APRAM: incorporating asynchrony into the PRAM model
164 Citations1989Richard Cole, O. Zajicek
The PRAM model provides an abstraction that strips away problems of synchronization, reliability and communication delays, thereby permitting algorithm designers to focus first and foremost on the structure of the computational problem at hand, rather than the architecture of a currently available machine.
Lecture notes in computer scienceDeterministic parallel list ranking
120 Citations2006Richard Anderson, Gary L. Miller
Parallel hashing---an efficient implementation of shared memory
103 Citations1986Anna R. Karlin, Eli Upfal
Towards an architecture-independent analysis of parallel algorithms
102 Citations1988Christos H. Papadimitriou, Mihalis Yannakakis
A simple and efficient method for evaluating the performance of an algorithm, rendered as a directed acyclic graph, on any parallel computer is presented and its application to several common algorithms shows that it is surprisingly accurate.
Theoretical Computer ScienceOn describing the behavior and implementation of distributed systems
89 Citations1981Nancy Lynch, Michael J. Fischer
A simple, basic and general model for describing both the (input-output) behavior and the implementation of distributed systems is presented and potentially useful for design specification of systems and of subsystems.
SIAM Journal on ComputingEfficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
75 Citations1988Gary L. Miller, Vijaya Ramachandran +1 more
A new parallel algorithm is given to evaluate a straight line program over a commutative semi-ring R of degree d and size n in time O(log n( log nd)) using M(n) processors, where M( n) is the number of processors required for multiplying n×n matrices over the semi- ring R in O (log n) time.