Data Distribution at Run-Time: Re-Using Execution Plans

		   Olav Beckmann and Paul H J Kelly

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

				 In:
			    Euro-Par '98,
	     Southampton, U.K., September 1st - 4th, 1998


			      Abstract:
			      ---------

This paper shows how data  placement optimisation techniques which are
normally only found in   optimising  compilers can be made   available
efficiently  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-flow 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.