{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:45:24Z","timestamp":1763459124049,"version":"3.45.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,10,3]],"date-time":"2015-10-03T00:00:00Z","timestamp":1443830400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0811457, 0811781, 0926687, 0926688, 0904549"],"award-info":[{"award-number":["0811457, 0811781, 0926687, 0926688, 0904549"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006751","name":"U.S. Army","doi-asserted-by":"publisher","award":["W911NF-10-1-0004"],"award-info":[{"award-number":["W911NF-10-1-0004"]}],"id":[{"id":"10.13039\/100006751","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-FC02-06ER25755"],"award-info":[{"award-number":["DE-FC02-06ER25755"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2014,10,3]]},"abstract":"<jats:p>Many scientific applications spend significant time within loops that are parallel, except for dependences from associative reduction operations. However these loops often contain data-dependent control-flow and array-access patterns. Traditional optimizations that rely on purely static analysis fail to generate parallel code in such cases.<\/jats:p>\n                  <jats:p>This article proposes an approach for automatic parallelization for distributed memory environments, using both static and runtime analysis. We formalize the computations that are targeted by this approach and develop algorithms to detect such computations. We also describe algorithms to generate a parallel inspector that performs a runtime analysis of control-flow and array-access patterns, and a parallel executor to take advantage of this information. The effectiveness of the approach is demonstrated on several benchmarks that were automatically transformed using a prototype compiler. For these, the inspector overheads and performance of the executor code were measured. The benefit on real-world applications was also demonstrated through similar manual transformations of an atmospheric modeling software.<\/jats:p>","DOI":"10.1145\/2660251","type":"journal-article","created":{"date-parts":[[2014,10,7]],"date-time":"2014-10-07T08:57:47Z","timestamp":1412672267000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Automatic parallelization of a class of irregular loops for distributed memory systems"],"prefix":"10.1145","volume":"1","author":[{"given":"Mahesh","family":"Ravishankar","sequence":"first","affiliation":[{"name":"Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Eisenlohr","sequence":"additional","affiliation":[{"name":"Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louis-No\u00ebl","family":"Pouchet","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Ramanujam","sequence":"additional","affiliation":[{"name":"Louisiana State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atanas","family":"Rountev","sequence":"additional","affiliation":[{"name":"Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Sadayappan","sequence":"additional","affiliation":[{"name":"Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207157"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2013.6494992"},{"key":"e_1_2_1_3_1","unstructured":"Balay S. Brown J. Buschelman K. Gropp W. D. Kaushik D. Knepley M. G. Mcinnes L. C. Smith B. F. and Zhang H. 2012. PETSc http:\/\/www.mcs.anl.gov\/petsc."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(97)00183-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Baskaran M. M. Ramanujam J. and Sadayappan P. 2010. Automatic C-to-CUDA code generation for affine programs. In Compiler Construction 264--263. 10.1007\/978-3-642-11970-5_14","DOI":"10.1007\/978-3-642-11970-5_14"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1088149.1088174"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122971.1122990"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","unstructured":"Benabderrahmane M.-W. Pouchet L.-N. Cohen A. and Bastoul C. 2010. The polyhedral model is more widely applicable than you think. In Compiler Construction 283--303. 10.1007\/978-3-642-11970-5_16","DOI":"10.1007\/978-3-642-11970-5_16"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330030303"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854317"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_2_1_12_1","unstructured":"Catalyurek U. V. and Aykanat C. 2009. PaToH: Partitioning Tool for Hypergraphs."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224420"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Das R. Saltz J. and Von Hanxleden R. 1993. Slicing analysis and indirect access to distributed arrays. Tech. Rep. CRPC-TR93319-S Rice University.","DOI":"10.1007\/3-540-57659-2_9"},{"key":"e_1_2_1_15_1","first-page":"42","article-title":"University of Florida sparse matrix collection","volume":"92","author":"Davis T. A.","year":"1994","unstructured":"Davis, T. A. 1994. University of Florida sparse matrix collection. NA Digest 92, 42.","journal-title":"NA Digest"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301670"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.1993.59"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"volume-title":"Automatic Parallelization of Loop Programs for Distributed Memory Architectures. FMI","author":"Griebl M.","key":"e_1_2_1_19_1","unstructured":"Griebl, M. 2004. Automatic Parallelization of Loop Programs for Distributed Memory Architectures. FMI, University of Passau."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13374-9_4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2006.88"},{"volume-title":"Tech. Rep. SAND2009-5574","author":"Heroux M. A.","key":"e_1_2_1_22_1","unstructured":"Heroux, M. A., Doerfler, D. W., Crozier, P. S., Willenbring, J. M., Edwards, H. C., Williams, A., Rajan, M., Keiter, E. R., Thornquist, H. K., and Numrich, R. W. 2009. Improving performance via mini-applications. Tech. Rep. SAND2009-5574, Sandia National Laboratories."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2013.6495001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73588"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/239230"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/645605.663225"},{"key":"e_1_2_1_27_1","volume-title":"Tech. Rep. CS-10-102","author":"Lamielle A.","year":"2010","unstructured":"Lamielle, A. and Strout, M. 2010. Enabling code generation with sparse polyhedral framework. Tech. Rep. CS-10-102, Colorado State University."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/155332.155341"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263719"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/520793.825758"},{"volume-title":"Radiative Heat Transfer","author":"Modest M. F.","key":"e_1_2_1_31_1","unstructured":"Modest, M. F. 2003. Radiative Heat Transfer. Academic Press."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Neiplocha J. Tipparaju V. Krishnan M. and Panda D. K. 2006. High performance remote memory access communication: The ARMCI approach. Int. J. High Perform. Comput. Appl. 10.1177\/1094342006064504","DOI":"10.1177\/1094342006064504"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254124"},{"key":"e_1_2_1_34_1","unstructured":"Par4All 2012. Par4all. www.par4all.org."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/169627.169752"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(92)90027-K"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207148"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.4000184"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1274971.1275008"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90129-D"},{"key":"e_1_2_1_41_1","first-page":"6","article-title":"Multiprocessors and run-time compilation","volume":"3","author":"Saltz J. H.","year":"1991","unstructured":"Saltz, J. H., Berryman, H., and Wu, J. 1991. Multiprocessors and run-time compilation. Concurrency and Computation: Pract. Exper. 3, 6.","journal-title":"Concurrency and Computation: Pract. Exper."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Schloegel K. Karypis G. and Kumar V. 2002. Parallel static and dynamic multi-constraint graph partitioning. Concurrency and Computation: Pract. Exper. 14.","DOI":"10.1002\/cpe.605"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781142"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/11596110_7"},{"volume-title":"Proceedings of the International Conference on Languages and Compilers for Parallel Computing.","author":"Strout M. M.","key":"e_1_2_1_45_1","unstructured":"Strout, M. M., George, G., and Olschanowsky, C. 2012. Set and relation manipulation for the sparse polyhedral framework. In Proceedings of the International Conference on Languages and Compilers for Parallel Computing."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065895.1065899"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/645670.665370"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1175\/2008MWR2522.1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/647476.727753"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2009.10"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660251","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2660251","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2660251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:39:41Z","timestamp":1763458781000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,3]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,10,3]]}},"alternative-id":["10.1145\/2660251"],"URL":"https:\/\/doi.org\/10.1145\/2660251","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2014,10,3]]},"assertion":[{"value":"2013-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}