Understanding Language Support for Irregular Parallelism

Abstract:

While software support for array-based, data-parallel algorithms has been
studied extensively, less attention has been devoted to irregular parallel
applications. The majority of these applications are unstructured, that is,
they possess asynchronous components that do not fit the data-parallel model.
Examples of unstructured applications include sparse matrix and n-body
problems. Previous research, such as Parti and CHAOS, has concentrated on
extending the array-based data-parallel model to handle structured irregular
algorithms. For unstructured irregular applications, however, the
appropriate language abstractions, compiler technology, and runtime
techniques have yet to be discovered.
In this paper, we analyze, under a systematic framework,
implementations of a representative set of algorithms--- Blocked
Sparse Cholesky, Barnes-Hut, and EMD3 --- on Tempest/Blizzard, a
platform that supports both shared memory and message passing. Using our
framework and corroborating experiments, we isolate a set of
abstractions that allows easy and efficient expression of our
benchmarks. The philosophy behind this set is to provide, for each
component of a parallel language, mechanisms that support user
control, along with good default behavior. Our contributions are
the following: a framework for the evaluation of abstractions, a set
of recommendations for language support for irregular applications,
and an analysis of the ability of current languages to support them.

This technical report has been published as

"Understanding Language Support for Irregular Parallelism." Mukund
Raghavachari and Anne Rogers in Parallel Symbolic
Languages and Systems, edited by R. Halstead,
T. Ito and C. Queninnec, Springer Verlag LNCS 1068
(1996).