{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:15:31Z","timestamp":1750306531822,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,1,9]],"date-time":"2015-01-09T00:00:00Z","timestamp":1420761600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European FP7 project CARP id. 287767"},{"name":"U.S. National Science Foundation award CCF-1321147"},{"name":"French &ldquo;Investments for the Future&rdquo; grant ManycoreLabs"},{"name":"Intel's University Research Office Intel Strategic Research Alliance program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2015,1,9]]},"abstract":"<jats:p>Task-parallel languages are increasingly popular. Many of them provide expressive mechanisms for intertask synchronization. For example, OpenMP 4.0 will integrate data-driven execution semantics derived from the StarSs research language. Compared to the more restrictive data-parallel and fork-join concurrency models, the advanced features being introduced into task-parallel models in turn enable improved scalability through load balancing, memory latency hiding, mitigation of the pressure on memory bandwidth, and, as a side effect, reduced power consumption.<\/jats:p>\n          <jats:p>In this article, we develop a systematic approach to compile loop nests into concurrent, dynamically constructed graphs of dependent tasks. We propose a simple and effective heuristic that selects the most profitable parallelization idiom for every dependence type and communication pattern. This heuristic enables the extraction of interband parallelism (cross-barrier parallelism) in a number of numerical computations that range from linear algebra to structured grids and image processing. The proposed static analysis and code generation alleviates the burden of a full-blown dependence resolver to track the readiness of tasks at runtime. We evaluate our approach and algorithms in the PPCG compiler, targeting OpenStream, a representative dataflow task-parallel language with explicit intertask dependences and a lightweight runtime. Experimental results demonstrate the effectiveness of the approach.<\/jats:p>","DOI":"10.1145\/2687652","type":"journal-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T20:02:10Z","timestamp":1421092930000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Compiler\/Runtime Framework for Dynamic Dataflow Parallelization of Tiled Programs"],"prefix":"10.1145","volume":"11","author":[{"given":"Martin","family":"Kong","sequence":"first","affiliation":[{"name":"The Ohio State University"}]},{"given":"Antoniu","family":"Pop","sequence":"additional","affiliation":[{"name":"The University of Manchester"}]},{"given":"Louis-No\u00ebl","family":"Pouchet","sequence":"additional","affiliation":[{"name":"The Ohio State University"}]},{"given":"R.","family":"Govindarajan","sequence":"additional","affiliation":[{"name":"Indian Institute of Science"}]},{"given":"Albert","family":"Cohen","sequence":"additional","affiliation":[{"name":"INRIA"}]},{"given":"P.","family":"Sadayappan","sequence":"additional","affiliation":[{"name":"The Ohio State University"}]}],"member":"320","published-online":{"date-parts":[[2015,1,9]]},"reference":[{"volume-title":"Optimizing Compilers for Modern Architectures. Morgan Kaufmann","author":"Allen Randy","key":"e_1_2_1_1_1","unstructured":"Randy Allen and Ken Kennedy . 2002. Optimizing Compilers for Modern Architectures. Morgan Kaufmann , San Francisco, CA . Randy Allen and Ken Kennedy. 2002. Optimizing Compilers for Modern Architectures. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389051"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1594835.1504209"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025127.1025992"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379022.1375595"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2011.10.003"},{"key":"e_1_2_1_7_1","first-page":"3","article-title":"Concurrent collections. Sci","volume":"18","author":"Budimli Zoran","year":"2010","unstructured":"Zoran Budimli &cgrave;, Michael Burke , Vincent Cav\u00e9 , Kathleen Knobe , Geoff Lowney , Ryan Newton , Jens Palsberg , David Peixotto , Vivek Sarkar , Frank Schlimbach , and Sagnak Ta\u015firlar . 2010 . Concurrent collections. Sci . Program. 18 , 3 -- 4 , 203--217. http:\/\/portal.acm.org\/citation.cfm&quest;id=1938482.1938486 Zoran Budimli&cgrave;, Michael Burke, Vincent Cav\u00e9, Kathleen Knobe, Geoff Lowney, Ryan Newton, Jens Palsberg, David Peixotto, Vivek Sarkar, Frank Schlimbach, and Sagnak Ta\u015firlar. 2010. Concurrent collections. Sci. Program. 18, 3--4, 203--217. http:\/\/portal.acm.org\/citation.cfm&quest;id=1938482.1938486","journal-title":"Program."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093157.2093165"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025168022993"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407835"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-006-0012-3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007516818651"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2464996.2467268"},{"key":"e_1_2_1_14_1","volume-title":"Retrieved","author":"International ETI","year":"2014","unstructured":"ETI International . 2014 . SWARM (SWift Adaptive Runtime Machine) . Retrieved November 17, 2014 from http:\/\/www.etinternational.com\/index.php\/products\/swarmbeta. ETI International. 2014. SWARM (SWift Adaptive Runtime Machine). Retrieved November 17, 2014 from http:\/\/www.etinternational.com\/index.php\/products\/swarmbeta."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013208.1013209"},{"key":"e_1_2_1_16_1","unstructured":"Gilles Kahn. 1974. The semantics of a simple language for parallel programming. In IFIP\u201994 North Holland (Ed.). 471--475.  Gilles Kahn. 1974. The semantics of a simple language for parallel programming. In IFIP\u201994 North Holland (Ed.). 471--475."},{"key":"e_1_2_1_17_1","volume-title":"Technical Report OSU-CISRC-7\/14-TR14. Department of Computer Science and Engineering","author":"Kong Martin","year":"2014","unstructured":"Martin Kong , Antoniu Pop , R. Govindarajan , Louis-No\u00ebl Pouchet , Albert Cohen , and P. Sadayappan . 2014 . Compiler\/Run-Time Framework for Dynamic Data-Flow Parallelization of Tiled Programs . Technical Report OSU-CISRC-7\/14-TR14. Department of Computer Science and Engineering , The Ohio State University . Martin Kong, Antoniu Pop, R. Govindarajan, Louis-No\u00ebl Pouchet, Albert Cohen, and P. Sadayappan. 2014. Compiler\/Run-Time Framework for Dynamic Data-Flow Parallelization of Tiled Programs. Technical Report OSU-CISRC-7\/14-TR14. Department of Computer Science and Engineering, The Ohio State University."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462187"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2006.136"},{"key":"e_1_2_1_20_1","volume-title":"Padua","author":"Midkiff Samuel P.","year":"1986","unstructured":"Samuel P. Midkiff and David A . Padua . 1986 . Compiler generated synchronization for do loops. In ICPP. 544--551. Samuel P. Midkiff and David A. Padua. 1986. Compiler generated synchronization for do loops. In ICPP. 544--551."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009499"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342009106195"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400712"},{"key":"e_1_2_1_25_1","unstructured":"Louis-Noel Pouchet. 2012. PolyBench: The Polyhedral Benchmark suite. http:\/\/web.cse.ohio-state.edu\/&sim; pouchet\/software\/polybench.  Louis-Noel Pouchet. 2012. PolyBench: The Polyhedral Benchmark suite. http:\/\/web.cse.ohio-state.edu\/&sim; pouchet\/software\/polybench."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.14"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/263580.263637"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40047-6_63"},{"key":"e_1_2_1_29_1","volume-title":"ISL: An integer set library for the polyhedral model. In Mathematical Software--ICMS","author":"Verdoolaege Sven","year":"2010","unstructured":"Sven Verdoolaege . 2010 . ISL: An integer set library for the polyhedral model. In Mathematical Software--ICMS 2010. Springer , New York, NY , 299--302. Sven Verdoolaege. 2010. ISL: An integer set library for the polyhedral model. In Mathematical Software--ICMS 2010. Springer, New York, NY, 299--302."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400713"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1982.1653941"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2687652","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2687652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:14Z","timestamp":1750227134000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2687652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,9]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1,9]]}},"alternative-id":["10.1145\/2687652"],"URL":"https:\/\/doi.org\/10.1145\/2687652","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2015,1,9]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}