{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T17:10:06Z","timestamp":1741021806678,"version":"3.38.0"},"reference-count":23,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Supercomputer Applications and High Performance Computing"],"published-print":{"date-parts":[[1995,9]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1177\/109434209500900303","type":"journal-article","created":{"date-parts":[[2007,3,5]],"date-time":"2007-03-05T01:17:47Z","timestamp":1173057467000},"page":"205-219","source":"Crossref","is-referenced-by-count":5,"title":["Evaluating Array Expressions On Massively Parallel Machines With Communication\/ Computation Overlap"],"prefix":"10.1177","volume":"9","author":[{"given":"Vincent","family":"Bouchitt\u00e9","sequence":"first","affiliation":[{"name":"LABORATOIRE LIP, CNRS (U.R.A. N\u00b0 1398) ECOLE NORMALE\rSUPERIEURE DE LYON LYON CEDEX, FRANCE"}]},{"given":"Pierre","family":"Boulet","sequence":"additional","affiliation":[{"name":"LABORATOIRE LIP, CNRS (U.R.A. N\u00b0 1398) ECOLE NORMALE\rSUPERIEURE DE LYON LYON CEDEX, FRANCE"}]},{"given":"Alain","family":"Darte","sequence":"additional","affiliation":[{"name":"LABORATOIRE LIP, CNRS (U.R.A. N\u00b0 1398) ECOLE NORMALE\rSUPERIEURE DE LYON LYON CEDEX, FRANCE"}]},{"given":"Yves","family":"Robert","sequence":"additional","affiliation":[{"name":"LABORATOIRE LIP, CNRS (U.R.A. N\u00b0 1398) ECOLE NORMALE\rSUPERIEURE DE LYON LYON CEDEX, FRANCE"}]}],"member":"179","published-online":{"date-parts":[[1995,9,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/173262.155101"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58430-7_62"},{"volume-title":"Optimal evaluation of array expressions on massively parallel machines","year":"1992","author":"Chatterjee, S.","key":"atypb3"},{"volume-title":"Proceedings of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","author":"Chatterjee, S.","key":"atypb4"},{"key":"atypb5","unstructured":"South Carolina: pp. 16-28."},{"volume-title":"Machines parall\u00e8les actuelles","year":"1994","author":"Cosnard, M.","key":"atypb6"},{"volume-title":"A graph-theoretic approach to the alignment problem. Technical Report 93-20","year":"1993","author":"Darte, A.","key":"atypb7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78348-7_13"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626494000235"},{"volume-title":"Computers and intractability, a guide to the theory of NP-Completeness","year":"1991","author":"Garey, M.R.","key":"atypb10"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90109-M"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1007\/BFb0038665"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90086-5"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206043"},{"volume-title":"Fourth International Workshop on Compilers for Parallel Computers","author":"Kremer, U.","key":"atypb15"},{"volume-title":"Index domain alignment: minimizing cost of cross-referencing between distributed arrays","year":"1990","author":"Li, J.","key":"atypb16"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90090-V"},{"key":"atypb18","unstructured":"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."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-2001-2"},{"volume-title":"Program and data transformations for efficient execution on distributed memory architectures. Ph.D. thesis","year":"1992","author":"O'Boyle, M.","key":"atypb20"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/SHPCC.1992.232671"},{"volume-title":"The Fourth Symposium on the Frontiers of Massively Parallel Computation","author":"Palmer, J.","key":"atypb22"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/71.97903"}],"container-title":["The International Journal of Supercomputer Applications and High Performance Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/109434209500900303","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/109434209500900303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T16:00:43Z","timestamp":1741017643000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/109434209500900303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["10.1177\/109434209500900303"],"URL":"https:\/\/doi.org\/10.1177\/109434209500900303","relation":{},"ISSN":["1078-3482"],"issn-type":[{"type":"print","value":"1078-3482"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}