Data distribution at run-time: Re-using execution plans

Abstract. This paper shows how data placement optimisation tech-niques which are normally only found in optimising compilers can be made available eciently in run-time systems. We study the example of a delayed evaluation, self-optimising (DESO) numerical library for a distributed-memory multicomputer. Delayed evaluation allows us to capture the control- ow of a user program from within the library at run-time, and to construct an optimised execution plan by propagating data placement constraints backwards through the DAG representing the computation to be performed. In loops, essentially identical DAGs are likely to recur. The main concern of this paper is recognising opportunities where an execution plan can be re-used. We have adapted both conventional parallelising compiler techniques and hardware dynamic branch prediction techniques in order to ensure that our run-time optimisations need not perform any more work than a parallelising compiler would have to do unless there is a prospect of better performance.