| Abstract |
|---|
| This paper shows how data placement optimisation techniques which arenormally only found in optimising compilers can be madeavailable efficiently in runtime systems. We study the example of adelayed-evaluation, self-optimizing (DESO) numerical library for adistributed-memory multicomputer. Delayed evaluation allows us tocapture the control-flow of a user program from within the library atruntime, and to construct an optimised execution plan by propagatingdata placement constraints backwards through the DAG representing thecomputation to be performed. In loops, essentially identical DAGs are likely to recur. The mainconcern of this paper is recognising opportunities where an executionplan can be re-used. We have adapted conventional parallelising compiler techniques and use run-time techniques analogous to branchprediction and register renaming in order to ensure thatour runtime optimisations need not perform any more workthan a parallelising compiler would have to do unless there is aprospect of better performance. |
| Contact |
| Olav Beckmann Department of Computing ,Imperial College of Science, Technology and Medicine ,180 Queen's Gate ,London SW7 2BZ, ,U.K. ob3@doc.ic.ac.uk |