article

A practical access to the theory of parallel algorithms

Author:

Christoph KesslerAuthors Info & Claims

ACM SIGCSE Bulletin, Volume 36, Issue 1

Pages 397 - 401

https://doi.org/10.1145/1028174.971436

Published: 01 March 2004 Publication History

Abstract

We describe a parallel programming environment that implements the PRAM (Parallel Random Access Machine) model. The programming environment consists of a C-based PRAM programming language called FORK with a compiler, libraries and tools, and a fast PRAM simulator. The software is freely available for Unix workstations. The programming environment and a systematic way of writing structured parallel programs for the PRAM model are described in a recent textbook.Even though the programming environment was originally developed for a hardware research project, we show that the system is also especially suited for complementing classical theory courses on PRAM algorithms by programming exercises that allow students to experiment with PRAM-style parallelism and actually implement the algorithms as they appear in the theory textbooks.We describe how the environment was used in a recent graduate-level course on parallel algorithms, and report on feedback that we got from the participants.

References

[1]

F. Abolhassan, R. Drefenstedt, J. Keller, W. J. Paul, and D. Scheerer. On the physical design of PRAMs. Computer J., 36(8):756--762, Dec. 1993.

[2]

G. Blelloch. 15-499(b): Parallel algorithms and programming (spring 1996). www-2.cs.cmu.edu/~scandal/nesl.html, 1996.

[3]

G. Blelloch. Programming Parallel Algorithms. Comm. ACM, 39(3):85--97, Mar. 1996.

Digital Library

[4]

B. S. Chlebus and I. Vrto. Parallel Quicksort. J. Parallel and Distrib. Comput., 11:332--337, 1991.

Digital Library

[5]

M. I. Cole. Algorithmic Skeletons: Structured Management of Parallel Computation. Pitman and MIT Press, 1989.

Digital Library

[6]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge MA, 1990.

Digital Library

[7]

M. Heath and J. Etheridge. Visualizing the performance of parallel programs. IEEE Software, 8(5):29--39, 1991.

Digital Library

[8]

V. Herrarte and E. Lusk. Studying parallel program behaviour with upshot. Technical report, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, 1991.

[9]

J. Ja¿Ja¿. An Introduction to Parallel Algorithms. Addison-Wesley, 1992.

Digital Library

[10]

J. Keller, C. Kessler, and J. Traff. Practical PRAM Programming. Wiley, New York, 2000.

Digital Library

[11]

C. W. Keayler and H. Seidl. The Fork95 Parallel Programming Language: Design, Implementation, Application. Int. J. Parallel Programming, 25(1):17--50, Feb. 1997.

Digital Library

[12]

C. E. Leiserson. Programming Irregular Parallel Applications in Cilk. Proc. IRREGULAR'97, Springer LNCS vol. 1253, pp. 61--71, 1997.

Digital Library

[13]

C. E. Leiserson and H. Prokop. A minicourse on multithreaded programming. Unpublished, see theory.lcs.mit.edu/~cilk, 1998.

[14]

Pallas GmbH. VAMPIR User's Manual. Pallas GmbH, Brahl, Germany, 1996. www.pallas.de/pages/vampir.htm.

[15]

W. J. Paul, P. Bach, M. Bosch, J. Fischer, C. Lichtenau, and J. Rahrig. Real PRAM programming. In Proc. Int. Euro-Par Conf.'02, Aug. 2002.

Digital Library

[16]

S. Pelagatti. Structured Development of Parallel Programs. Taylor&Francis, 1998.

Digital Library

Cited By

Neeman HLee LMullen JNewman G(2006)Analogies for teaching parallel computing to inexperienced programmersWorking group reports on ITiCSE on Innovation and technology in computer science education10.1145/1189215.1189172(64-67)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.1145/1189215.1189172
Neeman HLee LMullen JNewman G(2006)Analogies for teaching parallel computing to inexperienced programmersACM SIGCSE Bulletin10.1145/1189136.118917238:4(64-67)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.1145/1189136.1189172
Brenner JKeller JKessler C(2012)Executing PRAM Programs on GPUsProcedia Computer Science10.1016/j.procs.2012.04.1989(1799-1806)Online publication date: 2012
https://doi.org/10.1016/j.procs.2012.04.198
Show More Cited By

Recommendations

A practical access to the theory of parallel algorithms
SIGCSE '04: Proceedings of the 35th SIGCSE technical symposium on Computer science education

We describe a parallel programming environment that implements the PRAM (Parallel Random Access Machine) model. The programming environment consists of a C-based PRAM programming language called FORK with a compiler, libraries and tools, and a fast PRAM ...
A Comparison of 12 Parallel FORTRAN Dialects

A simple program that approximates pi by numerical quadrature is rewritten to run on nine commercially available processors to illustrate the compilations that arise in parallel programming in FORTRAN. The machines used are the Alliant FX/8, BBN ...
Composable Parallel Patterns with Intel Cilk Plus

Intel Cilk Plus extends C and C++ to enable writing composable deterministic parallel software that can exploit both the thread and vector parallelism commonly available in modern hardware.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCSE Bulletin

ACM SIGCSE Bulletin Volume 36, Issue 1

March 2004

501 pages

ISSN:0097-8418

DOI:10.1145/1028174

Issue’s Table of Contents

SIGCSE '04: Proceedings of the 35th SIGCSE technical symposium on Computer science education
March 2004
544 pages
ISBN:1581137982
DOI:10.1145/971300
Conference Chairs:
Dan Joyce
Villanova University
,
Deborah Knox
The College of New Jersey
,
Program Chairs:
Wanda Dann
Ithaca College
,
Tom Naps
University of Wisconsin - Oshkosh

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2004

Published in SIGCSE Volume 36, Issue 1

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
749
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Neeman HLee LMullen JNewman G(2006)Analogies for teaching parallel computing to inexperienced programmersWorking group reports on ITiCSE on Innovation and technology in computer science education10.1145/1189215.1189172(64-67)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.1145/1189215.1189172
Neeman HLee LMullen JNewman G(2006)Analogies for teaching parallel computing to inexperienced programmersACM SIGCSE Bulletin10.1145/1189136.118917238:4(64-67)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.1145/1189136.1189172
Brenner JKeller JKessler C(2012)Executing PRAM Programs on GPUsProcedia Computer Science10.1016/j.procs.2012.04.1989(1799-1806)Online publication date: 2012
https://doi.org/10.1016/j.procs.2012.04.198
Hughes CBuckley JExton CO'Carroll D(SVCR Group) (2005)Towards a Framework for Characterising Concurrent ComprehensionComputer Science Education10.1080/0899340050005652215:1(7-24)Online publication date: Mar-2005
https://doi.org/10.1080/08993400500056522

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents