Ecient Interprocedural Data Placement Optimisation in a Parallel Library

Abstract. This paper describes a combination of methods which make interprocedural data placement optimisation available to parallel libra-ries. We propose a delayed-evaluation, self-optimising (DESO) numerical library for a distributed-memory multicomputer. Delayed evaluation al-lows us to capture the control- ow of a user program from within the library at runtime, and to construct an optimised execution plan by propagating data placement constraints backwards through the DAG representing the computation to be performed. Our strategy for optimising data placements at runtime consists of an ecient representation for data distributions, a greedy optimisation al-gorithm, which because of delayed evaluation can take account of the full context of operations, and of re-using the results of previous run-time optimisations on contexts we have encountered before. We show performance gures for our library on a cluster of Pentium II Linux workstations, which demonstrate that the overhead of our delayed eval-uation method is very small, and which show both the parallel speedup we obtain and the benet of the optimisations we describe.