Programming parallel algorithms
Communications of the ACMPublished 1 March 1996Open access
Guy E. Blelloch
Citations449
SJR quartileQ1
SJR score1.15
SNIP3.34
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 research on parallel algorithms has not only improved the general understanding of par-allelism but in several cases has led to improvements in sequential algorithms.
Abstract
article Free Access Share on Programming parallel algorithms Author: Guy E. Blelloch Carnegie Mellon Univ., Pittsburgh, PA Carnegie Mellon Univ., Pittsburgh, PAView Profile Authors Info & Claims Communications of the ACMVolume 39Issue 3March 1996 pp 85–97https://doi.org/10.1145/227234.227246Published:01 March 1996Publication History 301citation3,378DownloadsMetricsTotal Citations301Total Downloads3,378Last 12 Months168Last 6 weeks41 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 Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Mathematics of ComputationComputational Geometry--An Introduction.
4,264 Citations1986Mikhail J. Atallah, Franco P. Preparata +1 more
Computational Geometry
3,606 Citations1985Franco P. Preparata, Michael Ian Shamos
This book clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics and points the way to the solution of the more challenging problems in dimensions higher than two.
The MIT Press eBooksThe Definition of Standard ML
2,411 Citations1997Robin Milner, Robert Harper +2 more
This book provides a formal definition of Standard ML for the benefit of all concerned with the language, including users and implementers, and the authors have defined their semantic objects in mathematical notation that is completely independent of StandardML.
An introduction to parallel algorithms
1,602 Citations1992Joseph F. JáJá
This book provides an introduction to the design and analysis of parallel algorithms with special attention to the selection of relevant data structures and to algorithm design principles that have proved to be useful.
Communications of the ACMData parallel algorithms
891 Citations1986W. Daniel Hillis, Guy L. Steele
The success of data parallel algorithms—even on problems that at first glance seem inherently serial—suggests that this style of programming has much wider applicability than was previously thought.
ACM SIGPLAN Fortran ForumHigh performance Fortran language specification
820 Citations1993CORPORATE Rice University
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.
Vector models for data-parallel computing
464 Citations1990Guy E. Blelloch
A model of parallelism that extends and formalizes the Data-Parallel model on which the Connection Machine and other supercomputers are based is described, and it is argued that data-parallel models are not only practical and can be applied to a surprisingly wide variety of problems, they are also well suited for very-high-level languages and lead to a concise and clear description of algorithms and their complexity.
ACM Transactions on Programming Languages and SystemsI-structures: data structures for parallel computing
363 Citations1989Arvind Arvind, Rishiyur S. Nikhil +1 more
It is difficult to achieve elegance, efficiency, and parallelism simultaneously in functional programs that manipulate large data structures, and it is shown that even in the context of purely functional languages, I-structures are invaluable for implementing functional data abstractions.
Medical Entomology and ZoologyProgramming with Sets: An Introduction to SETL
295 Citations1986Jacob T. Schwartz, Robert Dewar +2 more
SETL improves programmer speed and pro ductivity significantly, and also enhances program clarity and readability, and the classroom consequence is that students, freed of some of the burden of petty programming detail, can advance their knowledge of significant algorithms and of broader strategic issues in program development more rapidly than with more conventional programming languages.
Parallel Algorithms for Shared-Memory Machines.
273 Citations1990Richard M. Karp, Vijaya Ramachandran
Journal of Parallel and Distributed ComputingImplementation of a Portable Nested Data-Parallel Language
229 Citations1994Guy E. Blelloch, Jonathan C. Hardwick +3 more
Journal of AlgorithmsAn O(n2log n) parallel max-flow algorithm
226 Citations1982Yossi Shiloach, Uzi Vishkin
A synchronized parallel algorithm for finding maximum flow in a directed flow network is presented, whose depth is O( n 3 ( log n) p) where p (p ≤ n) is the number of processors used.
Journal of Parallel and Distributed ComputingA report on the sisal language project
212 Citations1990John Feo, D.C. Cann +1 more
Four significant results of the Sisal project are compilation techniques for high-performance parallel applicative computation, a microtasking environment that supports dataflow on conventional shared-memory architectures, execution times comparable to those of Fortran, and cost-effective speedup on shared-memory multiprocessors.
Programming with Sets
200 Citations1986Jacob T. Schwartz, Robert Dewar +2 more
SIAM Journal on ComputingHigh-Probability Parallel Transitive-Closure Algorithms
156 Citations1991Jeffrey D. Ullman, Mihalis Yannakakis
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)NESL: A Nested Data-Parallel Language (Version 2.6)
114 Citations1993Guy E. Blelloch
SIAM Journal on ComputingDeterministic Sampling–A New Technique for Fast Pattern Matching
100 Citations1991Uzi Vishkin
Foundations of computer science
93 Citations1995Alfred V. Aho, Jeffrey D. Ullman
This text combines the theoretical foundations of computing with essential discrete mathematics with all examples and exercises in C.H. Freeman's Foundations of Computer Science.
Parallelism in sequential functional languages
90 Citations1995Guy E. Blelloch, John Greiner
A complexity model, the PAL, based on the call-by-value A-calculus, that measures complexity in terms of the total work and the parallel depth of a computation is introduced and tree-based versions of quicksort and merge sort are described and analyzed.
Proceedings of the IEEECollection-oriented languages
73 Citations1991Jay Sipelstein, Guy E. Blelloch
The authors outline, compare, and contrast the collections and operations found in many collection-oriented languages by putting them into a common framework, and many problems that can occur in specifying such languages are elucidated.
Object recognition using the Connection Machine
49 Citations2003Lewis W. Tucker, Carl R. Feynman +1 more
A model-based object recognition system that uses massively parallel hypotheses generation and parameter space clustering in place of serial constraint propagation to recognize two-dimensional objects in a scene, given a reasonably large database of known objects.
Theoretical Computer ScienceA parallel-design distributed-implementation (PDDI) general-purpose computer
45 Citations1984Uzi Vishkin
The implementation space of an efficient general-purpose parallel computer is presented as a scheme of a synchronous distributed machine which is not more involved than a sorting network followed by a merging network.
Prototyping parallel and distributed programs in Proteus
27 Citations2002Peter H. Mills, Lars Nyland +3 more
Proteus is a high-level imperative notation based on sets and sequences with a single construct for the parallel composition of processes that allows prototypes to be tested, evolved and finally implemented through refinement techniques targeting specific architectures.
A critique of the programming language C*
15 Citations1992Walter F. Tichy, Michæl Philippsen +1 more
The purpose of this note is to make the relevant issues accessible to a wider audience and to make speci c recommendations for improving C.
Class Notes: Programming Parallel Algorithms CS 15-840B (Fall 1992)
4 Citations1993Guy E. Blelloch, Jonathan C. Hardwick
These are the lecture notes for CS 15-840B, a hands-on class in programming parallel algorithms, taught in the fall of 1992 by Guy Blelloch, using the programming language NESL.