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

This paper deals with the problem of evaluating High Performance Fortr an (HPF) style array expressions on massively parallel distributed-mem ory computers (DMPCs). This problem has been addressed by Chatterjee e t al,, 1992, 1993 under the strict hypothesis that computations and co mmunications cannot overlap. As such a model appears to be unnecessari ly restrictive for modeling state-of-the-art DMPCs, we relax the restr iction and allow for simultaneous computations and communications. Thi s simple modification has a tremendous effect on the complexity of the optimal evaluation of array expressions. We first show that even a si mple version of the problem is NP-complete. Then, we present some heur istics that we can guarantee in some important cases in practice, name ly, for coarse-grain or fine-grain computations.