Understanding Language Support for Irregular Parallelism
Report ID: TR-506-96Author: Raghavachari, Mukund / Rogers, Anne
Date: 1996-01-00
Pages: 16
Download Formats: |Postscript|
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).