EVALUATING ARRAY EXPRESSIONS ON MASSIVELY-PARALLEL MACHINES WITH COMMUNICATION/COMPUTATION OVERLAP

This paper deals with the problem of evaluating High Performance Fortran (HPF) style array expressions on massively parallel distributed-memory computers (DMPCs). This problem has been addressed by Chatterjee et al,, 1992, 1993 under the strict hypothesis that computations and communications cannot overlap. As such a model appears to be unnecessarily restrictive for modeling state-of-the-art DMPCs, we relax the restriction and allow for simultaneous computations and communications. This simple modification has a tremendous effect on the complexity of the optimal evaluation of array expressions. We first show that even a simple version of the problem is NP-complete. Then, we present some heuristics that we can guarantee in some important cases in practice, namely, for coarse-grain or fine-grain computations.