Programming Parallel Algorithms

Guy E. Blelloch.
Proceedings of the 1992 DAGS/PC Symposium.

60k compressed postscript

Abstract: In the past 20 years there have been a huge number of algorithms designed for parallel computers, most of which have been designed for one of the variants of the Parallel Random Access Machine (PRAM) model. Unfortunately there has been limited progress in getting practical implementations of the algorithm on any real parallel machine. Although discrepancies between the PRAM model and actual implementations of parallel machines (particularly as regards communication costs) has played a part in this lack of progress, another significant problem is the lack of good programming languages. With the languages that come with existing parallel machines it can be a major project to implement a simple algorithm, and once implemented the code is unlikely to port to any other parallel machine.

This paper describes a data-parallel language, NESL, designed for programming parallel algorithms. NESL currently runs on the Connection Machine CM-2 and the Cray Y-MP, and generates reasonably efficient code for both machines. The paper gives several examples of simple algorithms implemented in the language. All examples include the full code and run on both the CM-2 and Cray Y-MP.