Runtime Interprocedural Data Placement Optimisation for Lazy Parallel
		    Libraries (extended abstract)

		   Olav Beckmann and Paul H J Kelly

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


				 In:
	 Euro-Par'97 Parallel Processing, Proceedings of the
       Third International Euro-Par Conference, Passau, Germany
			     August 1997


We are  developing a    lazy,   self-optimising parallel   library  of
vector-matrix  routines.   The aim is to  allow  users  to parallelise
certain  computationally expensive   parts  of  numerical programs  by
simply  linking  with a  parallel   rather than sequential library  of
subroutines.   The library  performs   interprocedural  data placement
optimisation at runtime,  which requires the   optimiser itself to  be
very efficient. We achieve this firstly by working from aggregate loop
nests which have been optimised in isolation, and  secondly by using a
carefully  constructed mathematical formulation for data distributions
and the distribution requirements  of library operators, which  allows
us largely to replace searching with calculation in our algorithm.