Run-time optimization using delayed evaluation, execution plan reuse and 
incremental re-optimization

Paul Kelly, Imperial College, London visiting UCSD til July/August

(joint work with Olav Beckmann)

  Many interesting applications domains are characterised by run-time
  composition of pre-existing software components - on the command line, in
  data visualisation, browsing, dynamically-linked libraries (DLLs)
  and Java class files.  A key issue is how to optimise the performance of
  such composite programs.

  As an example, in this talk I show how data placement optimisation
  techniques which are normally only found in optimising compilers can be
  made available efficiently at run-time.  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 data 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, identical DAGs are likely to recur.  We recognise opportunities
  where an execution plan can be re-used, and have adapted both conventional
  compiler techniques and hardware dynamic branch prediction ideas in order
  to ensure that our run-time optimisations need perform no more work than a
  compiler would have to do unless there is a prospect of better
  performance.
  
  I will show some results running both on MPPs and workstation clusters,
  and say something about our plans to extend the idea, to heterogenous
  and wide-area networks, access to files, and generalise it to optimise
  Java remote method invocation automatically.