Programming parallel algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Programming parallel algorithms

Full text

Pdf (1.43 MB)

Source

Communications of the ACM archive
Volume 39 , Issue 3 (March 1996) table of contents

Pages: 85 - 97

Year of Publication: 1996

ISSN:0001-0782

Author

Guy E. Blelloch

Carnegie Mellon Univ., Pittsburgh, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 36, Downloads (12 Months): 324, Citation Count: 45

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/227234.227246 What is a DOI?

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	Alfred V. Aho , Jeffrey D. Ullman, Foundations of computer science, Computer Science Press, Inc., New York, NY, 1992
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
	4	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	5	Guy E. Blelloch, NESL: A Nested Data-Parallel Language (Version 2.6), Carnegie Mellon University, Pittsburgh, PA, 1993
	6	Guy Blelloch , John Greiner, Parallelism in sequential functional languages, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.226-237, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224210]
	7	Guy E. Blelloch , Jonathan C. Hardwick, Class Notes: Programming Parallel Algorithms CS 15-840B (Fall 1992), Carnegie Mellon University, Pittsburgh, PA, 1993
	8	Guy E. Blelloch , Jonathan C. Hardwick , Jay Sipelstein , Marco Zagha , Siddhartha Chatterjee, Implementation of a portable nested data-parallel language, Journal of Parallel and Distributed Computing, v.21 n.1, p.4-14, April 1994 [doi>10.1006/jpdc.1994.1038]
	9	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	10	K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	11	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	12	John T. Feo , David C. Cann , Rodney R. Oldehoeft, A report on the Sisal language project, Journal of Parallel and Distributed Computing, v.10 n.4, p.349-366, Dec. 1990 [doi>10.1016/0743-7315(90)90035-N]
	13	Hatcher, P., Tichy, W.F., and Philippsen, M. A critique of the programming language C*. Commun, ACM 35. 6 (June 1992), 21-24.
	14	High Performance Fortran Forum. High Performance Fortran Language Specification, May 1993.
	15	W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
	16	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	17	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	18	Mills, PH., Nyland, I.S., Prins, J.F., Reif. J.H., and Wagner, R.A. Prototyping parallel and distributed programs in Proteus. Tech. Rep. UNC-CH TR90-041, Computer Science Dept., Univ. of North Carolina, 1990.
	19	Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
	20	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	21	Rose, J.R., and Steele, G.I., Jr. C*: An extended C language for data parallel programming. In Proceedings of the 2d International Conference on Supercomputing, Vol. 2 (May) 1987, pp. 2-16.
	22	J. T. Schwartz , R. B. Dewar , E. Schonberg , E. Dubinsky, Programming with sets; an introduction to SETL, Springer-Verlag New York, Inc., New York, NY, 1986
	23	Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
	24	Sipelslein, J. and Blelloch, G.E. Collection-oriented languages. In Proceedings of the IEEE 79, 4 (Apr. 1991), pp. 504- 523.
	25	Uzi Vishkin, A parallel-design distributed-implementation (PDDI) general-purpose computer, Theoretical Computer Science, v.32 n.1-2, p.157-172, July 1984 [doi>10.1016/0304-3975(84)90028-8]

CITED BY 45

	Uzi Vishkin , Shlomit Dascal , Efraim Berkovich , Joseph Nuzman, Explicit multi-threading (XMT) bridging models for instruction parallelism (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.140-151, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Manuel M. T. Chakravarty , Gabriele Keller, Functional array fusion, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Thomas Rauber , Gudula Rünger, A coordination language for mixed task and and data parallel programs, Proceedings of the 1999 ACM symposium on Applied computing, p.146-155, February 28-March 02, 1999, San Antonio, Texas, United States
	David B. Skillicorn , Domenico Talia, Models and languages for parallel computation, ACM Computing Surveys (CSUR), v.30 n.2, p.123-169, June 1998
	Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, ACM SIGPLAN Notices, v.31 n.6, p.213-225, June 15, 1996
	Wilhelm Hasselbring, Programming languages and systems for prototyping concurrent applications, ACM Computing Surveys (CSUR), v.32 n.1, p.43-79, March 2000
	Guy E. Blelloch , Margaret Reid-Miller, Pipelining with futures, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.249-259, June 23-25, 1997, Newport, Rhode Island, United States
	Lars S. Nyland , Jan F. Prins , Allen Goldberg , Peter H. Mills, A Design Methodology for Data-Parallel Applications, IEEE Transactions on Software Engineering, v.26 n.4, p.293-314, April 2000
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Can shared-memory model serve as a bridging model for parallel computation?, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.72-83, June 23-25, 1997, Newport, Rhode Island, United States
	Manuel M. T. Chakravarty , Gabriele Keller, More types for nested data parallel programming, ACM SIGPLAN Notices, v.35 n.9, p.94-105, Sept. 2000
	Jörg Nolte , Yutaka Ishikawa , Mitsuhisa Sato, TACO: prototyping high-level object-oriented programming constructs by means of template based programming techniques, ACM SIGPLAN Notices, v.36 n.12, December 2001
	Christoph W. Kessler , Jesper Larsson Träff, A library of basic PRAM algorithms and its implementation in FORK, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.193-195, June 24-26, 1996, Padua, Italy
	Umut A. Acar , Guy E. Blelloch , Robert D. Blumofe, The data locality of work stealing, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.1-12, July 09-13, 2000, Bar Harbor, Maine, United States
	Quentin Miller, BSP in a lazy functional context, Trends in functional programming, Intellect Books, Exeter, UK, 2002
	Christoph Kessler, A practical access to the theory of parallel algorithms, ACM SIGCSE Bulletin, v.36 n.1, March 2004
	H.-W. Loidl , F. Rubio , N. Scaife , K. Hammond , S. Horiguchi , U. Klusik , R. Loogen , G. J. Michaelson , R. Peña , S. Priebe , Á J. Rebón , P. W. Trinder, Comparing Parallel Functional Languages: Programming and Performance, Higher-Order and Symbolic Computation, v.16 n.3, p.203-251, September 2003
	David Blackston , Torsten Suel, Highly portable and efficient implementations of parallel adaptive N-body methods, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-20, November 15-21, 1997, San Jose, CA
	Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, An analysis of dag-consistent distributed shared-memory algorithms, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.297-308, June 24-26, 1996, Padua, Italy
	Mark W. Goudreau , Kevin Lang , Satish B. Rao , Torsten Suel , Thanasis Tsantilas, Portable and Efficient Parallel Computing Using the BSP Model, IEEE Transactions on Computers, v.48 n.7, p.670-689, July 1999
	Bradford L. Chamberlain , Sung-Eun Choi , E. Christopher Lewis , Calvin Lin , Lawrence Snyder , W. Derrick Weathersby, ZPL: A Machine Independent Programming Language for Parallel Computers, IEEE Transactions on Software Engineering, v.26 n.3, p.197-211, March 2000
	Zhongqiang Chen , Alex Delis , Henry L. Bertoni, Radio-wave propagation prediction using ray-tracing techniques on a network of workstations (NOW), Journal of Parallel and Distributed Computing, v.64 n.10, p.1127-1156, October 2004
	Marc Snir , David A. Bader, A Framework for Measuring Supercomputer Productivity, International Journal of High Performance Computing Applications, v.18 n.4, p.417-432, November 2004
	Thomas Rauber , Gudula Rünger, A Transformation Approach to Derive Efficient Parallel Implementations, IEEE Transactions on Software Engineering, v.26 n.4, p.315-339, April 2000
	Lutz Prechelt , Stefan U. Hánßgen, Efficient Parallel Execution of Irregular Recursive Programs, IEEE Transactions on Parallel and Distributed Systems, v.13 n.2, p.167-178, February 2002
	Christopher Olston , Benjamin Reed , Utkarsh Srivastava , Ravi Kumar , Andrew Tomkins, Pig latin: a not-so-foreign language for data processing, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Jan F. Prins , Siddhartha Chatterjee , Martin Simons, Irregular computations in Fortran - expression and implementation strategies, Scientific Programming, v.7 n.3-4, p.313-326, August 1999
	Sungwoo Park, Type-safe higher-order channels in ML-like languages, ACM SIGPLAN Notices, v.42 n.9, September 2007
	Clemens Grelck , Sven-Bodo Scholz, SAC: off-the-shelf support for data-parallelism on multicores, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.25-33, January 16-16, 2007, Nice, France
	Manuel M. T. Chakravarty , Roman Leshchinskiy , Simon Peyton Jones , Gabriele Keller , Simon Marlow, Data parallel Haskell: a status report, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.10-18, January 16-16, 2007, Nice, France
	Ralf Lämmel, Google's MapReduce programming model – Revisited, Science of Computer Programming, v.70 n.1, p.1-30, January, 2008
	Michael Isard , Mihai Budiu , Yuan Yu , Andrew Birrell , Dennis Fetterly, Dryad: distributed data-parallel programs from sequential building blocks, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007
	Matthew Fluet , Mike Rainey , John Reppy , Adam Shaw , Yingqi Xiao, Manticore: a heterogeneous parallel language, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.37-44, January 16-16, 2007, Nice, France
	Daniel E. Cooke , Vladik Kreinovich , Joseph E. Urban, Designing Interdisciplinary Approaches To Problem Solving Into Computer Languages, Journal of Integrated Design & Process Science, v.6 n.3, p.29-43, August 2002
	Rita Loogen , Yolanda Ortega-mallén , Ricardo Peña-marí, Parallel functional programming in Eden, Journal of Functional Programming, v.15 n.3, p.431-475, May 2005
	Clemens Grelck, Shared memory multiprocessor support for functional array processing in SAC, Journal of Functional Programming, v.15 n.3, p.353-401, May 2005
	Guy Blelloch , Hal Burch , Karl Crary , Robert Harper , Gary Miller , Noel Walkington, Persistent triangulations, Journal of Functional Programming, v.11 n.5, p.441-466, September 2001
	P. W. Trinder , K. Hammond , H.-W. Loidl , S. L. Peyton Jones, Algorithm + strategy = parallelism, Journal of Functional Programming, v.8 n.1, p.23-60, January 1998
	P. W. Trinder , H.-W. Loidl , R. F. Pointon, Parallel and Distributed Haskells, Journal of Functional Programming, v.12 n.5, p.469-510, July 2002
	Matthew Fluet , Mike Rainey , John Reppy , Adam Shaw, Implicitly-threaded parallelism in Manticore, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Matthew Fluet , Nic Ford , Mike Rainey , John Reppy , Adam Shaw , Yingqi Xiao, Status report: the manticore project, Proceedings of the 2007 workshop on Workshop on ML, October 05-05, 2007, Freiburg, Germany
	Daniel E. Cooke , J. Nelson Rushton , Brad Nemanich , Robert G. Watson , Per Andersen, Normalize, transpose, and distribute: An automatic approach for handling nonscalars, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.2, p.1-49, March 2008
	Ralf Lämmel, Google's MapReduce programming model — Revisited, Science of Computer Programming, v.68 n.3, p.208-237, October, 2007
	John O'Donnell, Supporting tasks with adaptive groups in data parallel programming, International Journal of Computational Science and Engineering, v.1 n.2-4, p.86-98, May 2005
	Sungwoo Park , Hyeonseung Im, Type-safe higher-order channels with channel locality1, Journal of Functional Programming, v.19 n.1, p.107-142, January 2009
	Aydin Buluç , Jeremy T. Fineman , Matteo Frigo , John R. Gilbert , Charles E. Leiserson, Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.0 General
Subjects: Parallel algorithms

Additional Classification:
C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Parallel processors**

General Terms:
Algorithms, Languages, Performance, Theory

REVIEW

"Lorie M. Liebrock : Reviewer"

Blelloch presents features of the language NESL that are the “most important for programming parallel algorithms”: a performance model based on work and depth, and nestable data-parallel constructs. The paper focuses on more...

Collaborative Colleagues:

Guy E. Blelloch: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player