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: