A Linear Algebra Formulation for Optimising Replication
		      in Data Parallel Programs

		   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 LCPC'99:
	   Twelfth International Workshop on Languages and
		   Compilers for Parallel Computing
			   August 4-6, 1999
	     Computer Science and Engineering Department,
	       The University of California, San Diego,
			  La Jolla, CA, USA


			       Abstract
			       --------

In this  paper, we present  an efficient technique for optimising data
replication under the data   parallel programming model. We  propose a
precise mathematical representation for  data replication which allows
handling  replication as an explicit,  separate  stage in the parallel
data placement   problem.  This representation   takes the form  of an
invertible mapping. We argue that this property is  key to making data
replication amenable to good  mathematical optimisation algorithms. We
further outline an algorithm for optimising data replication, based on
this   representation, which  performs interprocedural  data placement
optimisation over a  sequence of loop  nests.  We have implemented the
algorithm and show performance figures.