Nested Data Parallelism and Irregular Computation

Jan F. Prins
UNC Chapel Hill


As the size and resolution of scientific simulations increase, sparse and
adaptive problem representation techniques with matching solution methods
become increasingly important to keep the computational work tractable.
However the work and data accesses required by such irregular computations
are statically unpredictable and may vary in time and space, posing
challenges to high performance execution.  In particular, locality of
reference and parallel load balance can be difficult to achieve.

I will describe an approach to the expression of irregular computations
using nested data parallelism.  Nested data parallel programs can be
expressed in mainstream performance-oriented languages like Fortran 90, but
they do not achieve high performance using current compilers.  Some
alternative compilation strategies will be described that target improved
performance of nested data parallel programs on different underlying
parallel architectures.

A compile-time program restructuring technique called flattening maximizes
the available parallelism and enables all parallel work to be partitioned
independently of the original computational structure, but thereby
decreases locality.  Using a high-bandwidth memory system, of the form
found in the Tera MTA, or in parallel vector processors from Cray or NEC, a
flattened computation can hide the latency due to lack of locality and
achieve high performance through precise load balance.

An example of a problem with both regular and irregular computation is the
NAS Conjugate Gradient parallel benchmark that solves an unstructured
linear system using the method of conjugate gradients.  The expression and
implementation of this benchmark in Fortran 90 will be considered, and the
performance on two different shared-memory parallel processors (SGI O200
and the NEC SX-4) will be described.




Biographical Sketch

Jan Prins is associate professor of Computer Science at UNC Chapel Hill.
His current research interests center on high-performance computing,
including algorithm design, computer architecture and programming
languages.  He is a member of the NIH research resource for parallel
computing in structural biology located at UNC.  He received his Ph.D. in
1987 from Cornell University, and was at Oxford University and the
University of Wisconsin at Madison before coming to UNC.  He was a founding
member of Digital Effects, one of the first commercial computer animation
firms (and one of the early casualties).  He spent the 1996-97 academic
year at the Institute for Theoretical Computer Science at the ETH Zurich in
Switzerland, working with the NEC SX-4 supercomputer.