{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:57:07Z","timestamp":1777676227116,"version":"3.51.4"},"reference-count":28,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2004,5,1]],"date-time":"2004-05-01T00:00:00Z","timestamp":1083369600000},"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 High Performance Computing Applications"],"published-print":{"date-parts":[[2004,5]]},"abstract":"<jats:p>Because of the increasing gap between the speeds of processors and main memories, compilers must enhance the locality of applications to achieve high performance. Loop fusion enhances locality by fusing loops that access similar sets of data. Typically, it is applied to loops at the same level after loop interchange, which first attains the best nesting order for each local loop nest. However, since loop interchange cannot foresee the overall optimization effect, it often selects the wrong loops to be placed outermost for fusion, achieving suboptimal performance globally. Building on traditional unimodular transformations on perfectly nested loops, we present a novel transformation, dependence hoisting, that effectively combines interchange and fusion for arbitrarily nested loops. We present techniques to simultaneously interchange and fuse loops at multiple levels. By evaluating the compound optimization effect beforehand, we have achieved better performance than was possible by previous techniques, which apply interchange and fusion separately.<\/jats:p>","DOI":"10.1177\/1094342004038956","type":"journal-article","created":{"date-parts":[[2004,5,27]],"date-time":"2004-05-27T08:40:00Z","timestamp":1085647200000},"page":"237-253","source":"Crossref","is-referenced-by-count":12,"title":["Improving Memory Hierarchy Performance through Combined Loop Interchange and                Multi-Level Fusion"],"prefix":"10.1177","volume":"18","author":[{"given":"Qing","family":"Yi","sequence":"first","affiliation":[{"name":"COMPUTER SCIENCE DEPARTMENT, RICE UNIVERSITY MS-132, HOUSTON, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ken","family":"Kennedy","sequence":"additional","affiliation":[{"name":"COMPUTER SCIENCE DEPARTMENT, RICE UNIVERSITY MS-132, HOUSTON, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2004,5,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Ahmed, N., Mateev, N., and Pingali, K., May 2000. Synthesizing transformations for locality enhancement of imperfectlynested loop nests . In Proceedings of the 2000 ACM International Conference on Supercomputing, Santa Fe, NM.","DOI":"10.1145\/335231.335245"},{"key":"atypb2","unstructured":"Allen, R., and Kennedy, K. 2001. Optimizing Compilers for Modern Architectures, Morgan Kaufmann, San Francisco, CA ."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"Banerjee, U. 1988. Dependence Analysis for Supercomputing, Kluwer Academic, Boston .","DOI":"10.1007\/978-1-4684-6894-6"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/197320.197366"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"Coleman, S., and McKinley, K.S., June 1995. Tile size selection using cache organization . In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, La Jolla, CA.","DOI":"10.1145\/207110.207162"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00034-X"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"Dongarra, J., Bunch, J., Moler, C., and Stewart, G. 1979. LINPACK Users\u2019 Guide, Society for Industrial and Applied Mathematics .","DOI":"10.1137\/1.9781611971811"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/1026003"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(88)90014-7"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Gao, G., Olsen, R., Sarkar, V., and Thekkath, R. 1992. Collective loop fusion for array contraction. In The 5th Workshop on Languages and Compiler for Parallelism, Springer-Verlag, Berlin .","DOI":"10.1007\/3-540-57502-2_53"},{"key":"atypb11","unstructured":"Golub, G.H., and Van Loan, C.F. 1989. Matrix Computations, 2nd edition, Johns Hopkins University Press, Baltimore, MD ."},{"key":"atypb12","unstructured":"Kelly, W., Maslov, V., Pugh, W., Rosser, E., Shpeisman, T., and Wonnacott, D. April 1996. The Omega Library Interface Guide. Technical Report, Department of Computer Science, University of Maryland ."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"Kelly, W., Pugh, W., Rosser, E., and Shpeisman, T. 1996b. Transitive closure of infinite graphs and its applications . International Journal of Parallel Programming 24(6).","DOI":"10.1007\/BF03356760"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Kennedy, K., May 2000. Fast greedy weighted fusion . In Proceedings of the International Conference on Supercomputing, Santa Fe, NM.","DOI":"10.1145\/335231.335244"},{"key":"atypb15","unstructured":"Kennedy, K., and McKinley, K.S. August 1993. Typed fusion with applications to parallel and sequential code generation. Technical Report TR93-208, Department of Computer Science, Rice University (also available as CRPCTR94370)."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"Kodukula, I., Ahmed, N., and Pingali, K., June 1997. Data-centric multi-level blocking . In Proceedings of the SIGPLAN \u201997 Conference on Programming Language Design and Implementation, Las Vegas, NV.","DOI":"10.1145\/258915.258946"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"Lam, M., Rothberg, E., and Wolf, M.E., April 1991. The cache performance and optimizations of blocked algorithms . In Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IV), Santa Clara, CA.","DOI":"10.1145\/106972.106981"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Lim, A.W., Cheong, G.I., and Lam, M.S., June 1999. An affine partitioning algorithm to maximize parallelism and minimize communication . In Proceedings of the 13th ACM SIGARCH International Conference on Supercomputing, Rhodes, Greece.","DOI":"10.1145\/305138.305197"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/71.577265"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/233561.233564"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"Pugh, W., June 1991. Uniform techniques for loop optimization . In Proceedings of the 1991 ACM International Conference on Supercomputing, Cologne, Germany.","DOI":"10.1145\/109025.109108"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"Pugh, W., and Rosser, E. July 1999. Iteration space slicing for locality. In LCPC 99.","DOI":"10.1007\/3-540-44905-1_11"},{"key":"atypb23","unstructured":"Rosser, E.J., 1998. Fine grained analysis of array computations. PhD thesis, Department of Computer Science, University of Maryland."},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"Wolf, M.E., and Lam, M., June 1991. A data locality optimizing algorithm . In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, Toronto, Canada.","DOI":"10.1145\/113445.113449"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"Wolfe, M.J., November 1989. More iteration space tiling . In Proceedings of Supercomputing \u201989, Reno, NV.","DOI":"10.1145\/76263.76337"},{"key":"atypb26","unstructured":"Wolfe, M.J. 1989. Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA ."},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"Yi, Q., Adve, V., and Kennedy, K., June 2000. Transforming loops to recursion for multi-level memory hierarchies . In ACM SIGPLAN Conference on Programming Language Design and Implementation, Vancouver, BC, Canada.","DOI":"10.1145\/349299.349323"},{"key":"atypb28","unstructured":"Yi, Q., and Kennedy, K. February 2002. Transforming complex loop nests for locality. Technical Report TR02-386, Computer Science Department, Rice University ."}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342004038956","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342004038956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:18:04Z","timestamp":1777450684000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342004038956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,5]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,5]]}},"alternative-id":["10.1177\/1094342004038956"],"URL":"https:\/\/doi.org\/10.1177\/1094342004038956","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,5]]}}}