{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T13:15:48Z","timestamp":1791206148451,"version":"4.1.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2007,10,1]],"date-time":"2007-10-01T00:00:00Z","timestamp":1191196800000},"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":[[2007,10]]},"abstract":"<jats:p>We present a unified mathematical framework for analyzing the tradeoffs between parallelism and storage allocation within a parallelizing compiler. Using this framework, we show how to find a good storage mapping for a given schedule, a good schedule for a given storage mapping, and a good storage mapping that is valid for all legal (one-dimensional affine) schedules. We consider storage mappings that collapse one dimension of a multidimensional array, and programs that are in a single assignment form and accept a one-dimensional affine schedule. Our method combines affine scheduling techniques with occupancy vector analysis and incorporates general affine dependences across statements and loop nests. We formulate the constraints imposed by the data dependences and storage mappings as a set of linear inequalities, and apply numerical programming techniques to solve for the shortest occupancy vector. We consider our method to be a first step towards automating a procedure that finds the optimal tradeoff between parallelism and storage space.<\/jats:p>","DOI":"10.1145\/1286821.1286825","type":"journal-article","created":{"date-parts":[[2007,11,15]],"date-time":"2007-11-15T14:26:02Z","timestamp":1195136762000},"page":"34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["A step towards unifying schedule and storage optimization"],"prefix":"10.1145","volume":"29","author":[{"given":"William","family":"Thies","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Vivien","sequence":"additional","affiliation":[{"name":"INRIA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saman","family":"Amarasinghe","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277691"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007500431910"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237578.237617"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/646347.690242"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 5th International Euro-Par Conference. 375--382","author":"Cohen A.","unstructured":"Cohen , A. and Lefebvre , V . 1999. Storage mapping optimization for parallel programs . In Proceedings of the 5th International Euro-Par Conference. 375--382 . Cohen, A. and Lefebvre, V. 1999. Storage mapping optimization for parallel programs. In Proceedings of the 5th International Euro-Par Conference. 375--382."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(91)90026-H"},{"key":"e_1_2_1_7_1","volume-title":"Algorithms for Parallel Processing","author":"Darte A.","unstructured":"Darte , A. 1998. Mathematical tools for loop transformations: From systems of uniform recurrence equations to the polytope model . In Algorithms for Parallel Processing , M. H. Heath, A. Ranade, and R. S. Schreiber, Eds. IMA Volumes in Mathematics and its Applications, vol. 105 . Springer-Verlag , 147--183. Darte, A. 1998. Mathematical tools for loop transformations: From systems of uniform recurrence equations to the polytope model. In Algorithms for Parallel Processing, M. H. Heath, A. Ranade, and R. S. Schreiber, Eds. IMA Volumes in Mathematics and its Applications, vol. 105. Springer-Verlag, 147--183."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Darte A. Robert Y. and Vivien F. 2000. Scheduling and Automatic Parallelization. Birkh\u00e4user Boston MA.   Darte A. Robert Y. and Vivien F. 2000. Scheduling and Automatic Parallelization. Birkh\u00e4user Boston MA.","DOI":"10.1007\/978-1-4612-1362-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.167"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626497000383"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/784893.784997"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(97)00089-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55406"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407931"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_17_1","volume-title":"The Data Parallel Programming Model. LNCS Tutorial","author":"Feautrier P.","unstructured":"Feautrier , P. 1996. The Data Parallel Programming Model. LNCS Tutorial , vol. 1132 Chapter Automatic Parallelization in the Polytope Model. Springer Verlag , 79--103. Feautrier, P. 1996. The Data Parallel Programming Model. LNCS Tutorial, vol. 1132 Chapter Automatic Parallelization in the Polytope Model. Springer Verlag, 79--103."},{"key":"e_1_2_1_18_1","volume-title":"Compiler Optimizations for Scalable Parallel Systems: Languages, Compilation Techniques, and Run Time Systems","author":"Feautrier P.","unstructured":"Feautrier , P. 2001a. Array dataflow analysis . In Compiler Optimizations for Scalable Parallel Systems: Languages, Compilation Techniques, and Run Time Systems , D. P. Agrawal and S. Pande, Eds. Lecture Notes in Computer Science, vol. 1808 . Springer , 173--220. Feautrier, P. 2001a. Array dataflow analysis. In Compiler Optimizations for Scalable Parallel Systems: Languages, Compilation Techniques, and Run Time Systems, D. P. Agrawal and S. Pande, Eds. Lecture Notes in Computer Science, vol. 1808. Springer, 173--220."},{"key":"e_1_2_1_19_1","volume-title":"June, 2001.","author":"Feautrier P.","year":"2001","unstructured":"Feautrier , P. 2001 b. The use of Farkas lemma in memory optimization. Unpublished note , June, 2001. Feautrier, P. 2001b. The use of Farkas lemma in memory optimization. Unpublished note, June, 2001."},{"key":"e_1_2_1_20_1","unstructured":"Feautrier P. Collard J.-F. Barreteau M. Barthou D. Cohen A. and Lefebvre V. 1998. The interplay of expansion and scheduling in PAF. Tech. rep. PRiSM University of Versailles.  Feautrier P. Collard J.-F. Barreteau M. Barthou D. Cohen A. and Lefebvre V. 1998. The interplay of expansion and scheduling in PAF. Tech. rep. PRiSM University of Versailles."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73588"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(98)00029-5"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(98)00021-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/379539.379586"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025117523902"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158515"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.908427"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/989995.989999"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/135226.135233"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/365151.365152"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007554627716"},{"key":"e_1_2_1_35_1","volume-title":"Automata Networks in Computer Science","author":"Quinton P.","unstructured":"Quinton , P. 1987. Automata Networks in Computer Science , Chapter The systematic design of systolic arrays, 229--260. Manchester University Press . Quinton, P. 1987. Automata Networks in Computer Science, Chapter The systematic design of systolic arrays, 229--260. Manchester University Press."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02477176"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/21095.21125"},{"key":"e_1_2_1_39_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","unstructured":"Schrijver , A. 1986. Theory of Linear and Integer Programming . John Wiley and Sons , New York . Schrijver, A. 1986. Theory of Linear and Integer Programming. John Wiley and Sons, New York."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 14th International Workshop on Languages and Compilers for Parallel Computing. 254--273","author":"Sheldon J. W.","unstructured":"Sheldon , J. W. , Lee , W. , Greenwald , B. , and Amarasinghe , S . 2001. Strength reduction of integer divison and modulo operations . In Proceedings of the 14th International Workshop on Languages and Compilers for Parallel Computing. 254--273 . Sheldon, J. W., Lee, W., Greenwald, B., and Amarasinghe, S. 2001. Strength reduction of integer divison and modulo operations. In Proceedings of the 14th International Workshop on Languages and Compilers for Parallel Computing. 254--273."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/291069.291015"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626497000218"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPPS.1992.223033"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1286821.1286825","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1286821.1286825","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:57:49Z","timestamp":1750258669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1286821.1286825"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1145\/1286821.1286825"],"URL":"https:\/\/doi.org\/10.1145\/1286821.1286825","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10]]},"assertion":[{"value":"2007-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}