Concurrent Programming in Java
© 1996-1999 Doug Lea
4.4 Parallel Decomposition
Follow-ups
Readings and Resources
For a survey of approaches to high-performance parallel processing, see
-
Skillicorn, David, and Domenico Talia, "Models and Languages for
Parallel Computation", Computing Surveys, June 1998.
Most texts on parallel programming concentrate on algorithms
designed for use on fine-grained parallel machine architectures, but
also cover design techniques and algorithms that can be implemented
using the kinds of stock multiprocessors most amenable to supporting
a JVM. See, for example:
-
Foster, Ian. Designing and Building Parallel Programs,
Addison Wesley, 1995. (Also see on-line version.)
- Roosta, Seyed. Parallel Processing and Parallel Algorithms,
Springer-Verlag, 1999.
- Wilson, Gregory. Practical Parallel Programming, MIT Press,
1995.
- Zomaya, Albert (ed.). Parallel and Distributed Computing
Handbook, McGraw-Hill, 1996.
- Parascope,
the IEEE web site for parallel computing.
Pattern-based accounts of parallel programming include:
-
Massingill, Berna, Timothy Mattson, and Beverly Sanders. A Pattern
Language for Parallel Application Programming, Technical report,
University of Florida, 1999.
-
MacDonald, Steve, Duane Szafron, and Jonathan
Schaeffer. "Object-Oriented Pattern-Based Parallel Programming
with Automatically Generated Frameworks", in Proceedings of the
5th USENIX Conference on Object-Oriented Tools and Systems
(COOTS), 1999.
The FJTask framework internally relies on a work-stealing task
scheduler based on the one in Cilk, a C-based parallel programming
framework. In work-stealing schedulers, each worker thread normally
runs (in LIFO order) tasks that it constructs, but when idle steals
(in FIFO order) those constructed by other worker threads. More
details, including explanations of the senses in which this scheme
is optimal for recursive fork/join programs, may be found in:
-
Frigo, Matteo, Charles Leiserson, and Keith Randall. "The
Implementation of the Cilk-5 Multithreaded Language", Proceedings
of 998 ACM SIGPLAN Conference on Programming Language Design and
Implementation (PLDI), 1998.
Similar packages and frameworks in other languages include:
- Cilk -- This
project pioneered efforts to implement and analyze efficient
work-stealing designs.
- Hood -- a
C++ follow-on to Cilk that includes more support for
general-purpose concurrent programming using threads.
-
Filaments -- This C-based package contains specialized support
for barrier-based iterative tasks.
- StackThreads
A similar package that runs under gcc on many platforms.
Doug Lea
Last modified: Sat Nov 13 19:59:18 EST 1999