Optimal evaluation of array expressions on massively parallel machines (extended abstract)
Siddhartha Chatterjee, John R. Gilbert, Robert Schreiber, Shang‐Hua Teng · ACM SIGPLAN Notices · 1993
We investigate the problem of optimal evaluation of Fortran-90 style array expressions on a massively parallel distributed-memory machine. On such machines, an elementwise operation can be performed in unit time for arrays whose corresponding elements are in the same processor. If the arrays are not aligned in this manner, the cost of alignment is part of the cost of expression evaluation. The choice of where to perform the operation then affects this cost. We demonstrate how a dynamic programming technique can be applied to solve this problem efficiently for a wide variety of interconnection schemes, including multidimensional grids and rings, hypercubes, and fat-trees. We also consider the variant where the operations may change the shape of the arrays, and show that our approach extends naturally to handle this case.