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 Chat terjee 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 re striction and allow for simultaneous computations and communications. This simple modification has a tre mendous effect on the complexity of the optimal eval uation 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.
Get full access to this article
View all access options for this article.
References
1.
Anderson, J.M., and Lam, M.S.1993. Global optimizations for parallelism and locality on scalable parallel machines. ACM Sigplan Notices28(6): 112-125.
2.
Bouchitté, V., Boulet, P., Darte, A., and Robert, Y.1994. Evaluating array expressions on massively parallel machines with communication/computation overlap. In Parallel Processing: CONPAR 94-VAPP VI, edited by B. Buchberger and J. Volkert. Berlin, Germany: Springer-Verlag, pp. 713—724 . (Extended version available as TR94-10, LIP, ENS Lyon.)
3.
Chatterjee, S., Gilbert, J.R., Schreiber, R.S., and Tseng, S.-H.1992. Optimal evaluation of array expressions on massively parallel machines. In Proceedings of the Second Workshop on Languages, Compilers, and Runtime Environments for Distributed Memory Multiprocessors. Boulder, Colorado.
4.
Chatterjee, S., Gilbert, J.R., Schreiber, R.S., and Tseng, S.-H.1993. Automatic array alignment in data-parallel programs. In Proceedings of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Charleston, 46 Allée d'Italie, 69364 Lyon Cedex 07, France, phone (+33-72) 72 83 89, e-mail: Yves. Robert@ Lip.ens-lyon.fr
5.
South Carolina: pp. 16-28.
6.
Cosnard, M., and Desprez, F.1994. Machines parallèles actuelles. In Algorithmes parallèles: Analyse et conception. Hermhs (French).
7.
Darte, A., and Robert, Y.1993. A graph-theoretic approach to the alignment problem. Technical Report 93-20. Lyon: Ecole Normale Supérieure, Laboratoire de l'Informatique de Parallélisme.
8.
Esser, R., and Knetcht, R.1993. Intel Paragon XP/ S—architecture and software environment . Technical Report KFA-ZAM-IB-9305, Zentralinstitut fur Angewandte Mathematik, Forschungszentrum Julich.
9.
Feautrier, P.1994. Towards automatic distribution. Parallel Processing Letters, 4(3):233-244.
10.
Garey, M.R., and Johnson, D.S.1991. Computers and intractability, a guide to the theory of NP-Completeness. New York: W. H. Freeman and Company.
11.
Gilbert, J.R., and Schreiber, R.S.1991. Optimal expression evaluation for data parallel architectures . Journal of Parallel and Distributed Computing13(1):58-64.
12.
Huang, C.H., and Sadayappan, P.1991. Communication-free hyperplane partitioning of nested loops . In Languages and Compilers for Parallel Computing, vol. 589 of Lecture Notes in Computer Science , edited by Banerjee, Gelernter, Nicolau, and Padua.Berlin, Germany: Springer-Verlag, pp. 186-200.
13.
Knobe, K., Lukas, J.D., and Steele, G.L.1990. Data optimization: allocation of arrays to reduce communication on SIMD machines. Journal of Parallel and Distributed Computing8(2):102-118.
14.
Knobe, K., and Natarajan, V.1993. Automatic data allocation to minimize data motion on SIMD machines. Journal of Supercomputing7(4): 387-415.
15.
Kremer, U.1993. NPcompleteness of dynamic remapping. In Fourth International Workshop on Compilers for Parallel Computers , edited by H. J. Sips. TU Delft: pp. 135-141.
16.
Li, J., and Chen, M.1990. Index domain alignment: minimizing cost of cross-referencing between distributed arrays. In Frontiers 90: The 3rd Symposium on the Frontiers of Massively Parallel Computation. College Park, Maryland.
17.
Li, J., and Chen, M.1991. The data alignment phase in compiling programs for distributed memory machines. Journal of Parallel and Distributed Computing13:213-221.
18.
Lukas, J.D., and Knobe, K.1992. Data optimization and its effect on communication costs in MIMD Fortran code. In Fifth SIAM Conference on Parallel Processing for Scientific Computing, edited by Dongarra, Kennedy, Messina, Sorensen, and Voigt.Philadelphia, Penna .: SIAM Press, pp. 478-483.
O'Boyle, M.1992. Program and data transformations for efficient execution on distributed memory architectures. Ph.D. thesis, Computer Science Department, University of Manchester, U.K.
21.
O'Boyle, M., and Hedayat, G.A.1992. Data alignment: transformations to reduce communications on distributed memory architectures. In Scalable High-Performance Computing Conference SHPCC-92. Los Alamitos, CA: IEEE Computer Society Press, pp. 366-371.
22.
Palmer, J., and Steele, G.L.1992. Connection Machine model CM-5 overview. In The Fourth Symposium on the Frontiers of Massively Parallel Computation , edited by H.J. Siegel. Los Alamitos, CA: IEEE Computer Society Press, pp. 474-483.
23.
Ramanujam, J., and Sadayappan, P.1991. Compile-time techniques for data distribution in distributed memory machines. IEEE Trans. Parallel Distributed Systems2(4): 472-482.
