Data Parallel Languages and Irregular Computation
Guy E. Blelloch
Scalable High-Performance Computing Conference
May, 1994

Data-parallel languages are attractive as high-level portable
languages for parallel computers for several reasons: they are
easy to program in, easy to understand, easy to debug, are
portable to a wide variety of machines (e.g. MIMD, SIMD and
Vector), and abstract away from details of data layout and
processor allocation.  On the other hand, it is generally agreed
that although existing data-parallel languages are ideally
suited for computations on dense matrices or regular meshes,
they are not as well suited for applications with irregular
structures.  Examples of such irregular structures include
unstructured sparse matrices, graphs and trees.

In this talk I will discuss how this limitation is not so much a
limitation of data-parallel languages in general, but rather to
a class of data-parallel languages that only allow flat
structures (arrays or sequences of atomic values).  This class
includes the data-parallel extensions in C* and High Performance
Fortran (HPF).  I will show how several problems on irregular
structures can be expressed naturally and concisely in
data-parallel languages that allow for nested structures.  I
will also show that it is difficult to base a nested
data-parallel language on C or Fortran, and discuss some issues
in the implementation of nested data-parallel languages.