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 signifi-
cance 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.
pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.