{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:38:31Z","timestamp":1750307911873,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2006,11,1]],"date-time":"2006-11-01T00:00:00Z","timestamp":1162339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2006,11]]},"abstract":"<jats:p>We consider the analysis and optimization of code utilizing operations and functions operating on entire arrays. Models are developed for studying the minimization of the number of materializations of array-valued temporaries in basic blocks, each consisting of a sequence of assignment statements involving array-valued variables. We derive lower bounds on the number of materializations required, and develop several algorithms minimizing the number of materializations, subject to a simple constraint on allowable statement rearrangement. In contrast, we also show that when statement rearrangement is unconstrained, minimizing the number of materializations becomes NP-complete, even for very simple basic blocks.<\/jats:p>","DOI":"10.1145\/1186632.1186637","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"1145-1177","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On minimizing materializations of array-valued temporaries"],"prefix":"10.1145","volume":"28","author":[{"given":"Daniel J.","family":"Rosenkrantz","sequence":"first","affiliation":[{"name":"University of Albany---SUNY, Albany, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lenore R.","family":"Mullin","sequence":"additional","affiliation":[{"name":"University of Albany---SUNY, Albany, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harry B.","family":"Hunt III","sequence":"additional","affiliation":[{"name":"University of Albany---SUNY, Albany, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,11]]},"reference":[{"volume-title":"Compilers: Principles, Techniques, and Tools. Addison--Wesley","year":"1986","author":"Aho A. V.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","unstructured":"Allen R. and Kennedy K. 2002. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan-Kaufmann Publishers San Francisco CA.]]   Allen R. and Kennedy K. 2002. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan-Kaufmann Publishers San Francisco CA.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/197405.197406"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/579.357248"},{"key":"e_1_2_1_6_1","first-page":"481","volume-title":"Factor-join: A unique approach to compiling array languages for parallel machines. In Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing","author":"Chamberlain B. L.","year":"1996"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1155\/2000\/494281"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/3-540-57502-2_53","volume-title":"Proceedings of 5th International Workshop on Languages and Compilers for Parallel Computing","volume":"757","author":"Gao G. R."},{"first-page":"1","volume-title":"Conference Record of the 5th Annual ACM SIGACT--SIGPLAN Symposium on Principles of Programming Languages (POPL '78)","author":"Guibas L. J.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of Supercomputing '95","author":"Gupta M.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"Efficient evaluation of array subscripts of arrays","volume":"16","author":"Hassitt A.","year":"1972","journal-title":"IBM J. Res. Devl."},{"volume":"1343","volume-title":"Proceedings of the 1st International Conference on Scientific Computing in Object--Oriented Parallel Environments (ISCOPE '97)","author":"Humphrey W.","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of the 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming 30","year":"2099","author":"Hwang G.-H.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1481"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1680"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012241830762"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing","volume":"768","author":"Kennedy K.","year":"1993"},{"volume":"1033","volume-title":"Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing","author":"Kennedy K.","key":"e_1_2_1_20_1"},{"first-page":"107","volume-title":"Conference Record 25th ACM SIGACT--SIGPLAN Symposium on Principles of Programming Languages (POPL '98)","author":"Knobe K.","key":"e_1_2_1_21_1"},{"first-page":"50","volume-title":"Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation (Montreal, Que., Canada, June). ACM","author":"Lewis E. C.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","first-page":"96","volume-title":"ZPL: An array sublanguage. In Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing (Portland, OR, Aug.)","author":"Lin C.","year":"1993"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.577265"},{"volume-title":"Workshop on Compilers for Parallel Computers. TU Delft, Holland.]]","year":"1993","author":"Mullin L.","key":"e_1_2_1_25_1"},{"volume-title":"Dept. of Computer Science","author":"Roth G.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","series-title":"Lecture Notes in Computer Science","first-page":"219","volume-title":"Proceedings of the 9th International Compiler Construction Conference (CC '2000) (Berlin, Germany, Mar.)","author":"Roth G."},{"first-page":"1225","volume-title":"Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA '96)","author":"Roth G.","key":"e_1_2_1_29_1"},{"first-page":"125","volume-title":"Proceedings of the 12th International Conference on Supercomputing (ICS '98)","author":"Roth G.","key":"e_1_2_1_30_1"},{"volume-title":"Proceedings of the 1997 ACM\/IEEE Conference on Supercomputing (SC '97)","author":"Roth G.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0096-0551(75)90015-6","article-title":"Optimization of very high level languages---I. Value transmission and its corollaries","volume":"1","author":"Schwartz J. T.","year":"1975","journal-title":"Comput. Lang."},{"volume":"1505","volume-title":"Proceedings of the 2nd International Symposium on Computing in Object-Oriented Parallel Environments (ISCOPE '98)","author":"Siek J. G.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 2nd International Symposium on Scientific Computing in Object-Oriented Parallel Environments (ISCOPE '98)","volume":"1505","author":"Veldhuizen T. L.","year":"1998"},{"volume-title":"Proceedings of the SIAM Workshop on Object Oriented Methods for Interoperable Scientific and Engineering Computing (OO '98)","author":"Veldhuizen T. L.","key":"e_1_2_1_37_1"},{"volume-title":"High Performance Compilers for Parallel Computing","author":"Wolfe M.","key":"e_1_2_1_38_1"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1186632.1186637","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1186632.1186637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:51Z","timestamp":1750258071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1186632.1186637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2006,11]]}},"alternative-id":["10.1145\/1186632.1186637"],"URL":"https:\/\/doi.org\/10.1145\/1186632.1186637","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2006,11]]},"assertion":[{"value":"2006-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}