Optimal evaluation of array expressions on massively-parallel machines

The authors investigate the problem of evaluating Fortran 90-style array expressions on massively parallel distributed-memory machines. On such a machine, an elementwise operation can be performed in constant time for arrays whose corresponding elements are in the same processor. If the arrays are not aligned in this manner, the cost of aligning them is part of the cost of evaluating the expression tree. The choice of where to perfrom the operation then affects this cost. The authors describe the communication cost of the parallel machine theoretically as a metric space; they model the alignment problem as that of finding a minimum-cost embedding of the expression tree into this space. The authors present algorithms based on dynamic programming that solve the embedding problem optimally for several communication cost metrics: multidimensional grids and rings, hypercubes, fat-trees, and the discrete metric. They also extend out approach to handle operations that change the shape of the arrays.