next up previous
Next: Work and Depth Up: Front Page

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:

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.





next up previous
Next: Work and Depth Up: Front Page



Guy Blelloch, blelloch@cs.cmu.edu