Index domain alignment: minimizing cost of cross-referencing between distributed arrays

Abstract

The issue of data movement between processors due to cross-references between multiple distributed arrays is addressed. The problem of index domain alignment is formulated as finding a set of suitable alignment functions that map the index domains of the arrays into a common index domain so as to minimize the cost of data movement due to cross-references between the arrays. The cost function and the machine model used are abstractions of the current generation of distributed-memory machines. The problem as formulated is shown to be NP-complete. A heuristic algorithm is devised and shown to be efficient and to provide excellent results.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>