A Review of Data Placement Optimisation for Data-Parallel
			Component Composition

		   Olav Beckmann and Paul H J Kelly

	      Department of Computing, Imperial College,
		  180 Queen's Gate, London SW7 2BZ,
			   United Kingdom.
		       {ob3,phjk}@doc.ic.ac.uk}


			       Abstract
			       ========

Constructive methods for parallel programming are characterised by the
composition of optimised, parallel software components.  This paper
concerns data placement, a key cross-component optimisation for
regular data-parallel programs.

This article is a survey of data placement optimisation techniques.
The main contributions are (1) a uniform terminology, which identifies
analyses of the problem which have proven fruitful, (2) a taxonomy of
versions of the problem, distinguished by the efficiency with which
they can be solved, (3) a discussion of open problems, challenges and
opportunities for further progress in the area, and (4) a discussion
of the significance of these results for constructive methods in
parallel programming.  We observe, in particular, the role of
skeletons in restricting program graph structure to ensure that
optimisation is tractable.