Programming Parallel Algorithms

Guy E. Blelloch

Communications of the ACM, 39(3), March, 1996.

In the past 20 years there has been tremendous progress in developing and analyzing parallel algorithms. Researchers have developed efficient parallel algorithms to solve most problems for which efficient sequential solutions are known. Although some of these algorithms are efficient only in a theoretical framework, many are quite efficient in practice or have key ideas that have been used in efficient implementations. This research on parallel algorithms has not only improved our general understanding of parallelism, but in several cases has led to improvements in sequential algorithms. Unfortunately there has been less success in developing good languages for programming parallel algorithms, particularly languages that are well suited for teaching and prototyping algorithms. There has been a large gap between languages that are too low level, requiring specification of many details that obscure the meaning of the algorithm, and languages that are too high-level, making the performance implications of various constructs unclear. In sequential computing many standard languages such as C or Pascal do a reasonable job of bridging this gap, but in parallel languages building such a bridge has been significantly more difficult.

Our research involves developing a parallel language that is useful for teaching as well as for implementing parallel algorithms. To achieve this, an important goal has been to develop a language that allows high-level descriptions of parallel algorithms while also having a well understood mapping onto a performance model (i.e. bridges the gap). Based on our research, we believe that the following two features are important for achieving this goal:

• A language-based performance model that uses work and depth rather than a machine-based model that uses ``running time''.
• Support for nested data-parallel constructs. This is the ability to apply a function in parallel to each element of a collection of data, and the ability to nest such parallel calls.

In this article we describe these features and explain why they are important for programming parallel algorithms. To make the ideas concrete, we describe the programming language NESL [5], which we designed based on the features, and go through several examples of how to program and analyze parallel algorithms using the language. We have been using NESL for three years in undergraduate and graduate courses on parallel algorithms [8]. The algorithms we cover in this article are relatively straightforward. Many more algorithms can be found through the Web version of this article.

• Work and Depth
  • Why Work and Depth?
  • Relationship of Work and Depth to Running Time
• Nested Data-Parallelism and NESL
  • NESL
  • The Performance Model
• Examples of Parallel Algorithms
  • Primes
  • Sparse Matrix Multiplication
  • Planar Convex-Hull
  • Three Other Algorithms
• Summary
• References
• About this document ...