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 machines, 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 expression evaluation. The choice of where to perform the operation then affects the cost. They present algorithms based on dynamic programming to solve this problem efficiently for a wide variety of interconnection schemes, including multidimensional grids and rings, hypercubes, and fat-trees. They also consider expressions containing operations that change the shape of the arrays, and show that their approach extends naturally to handle this case. (Copyright (c) 1992 Xerox Corporation. All rights reserved.)