Abstract Implementation of a Portable Nested Data-Parallel Language

This paper gives an overview of the implementation of Nesl, a portable nested data-parallel language. This language and its implementation are the rst to fully support nested data structures as well as nested dataparallel function calls. These features allow theconcise description of parallel algorithms on irregular data, such as sparse matrices and graphs. In addition, they maintain the advantages of data-parallel languages: a simple programming model and portability. The current Nesl implementation is based on an intermediate language called Vcode and a library of vector routines called Cvl. It runs on the Connection Machine CM-2, the Cray Y-MP C90, and serial machines. We compare initial benchmark results of Nesl with those of machine-speci c code on these machines for three algorithms: least-squares line- tting, median nding, and a sparse-matrix vector product. These results show that Nesl's performance is competitive withthatof machine-speci c codes for regular dense data, and is often superior for irregular data