{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:12:09Z","timestamp":1740136329321,"version":"3.37.3"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/100004351","name":"Cisco Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004351","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Adaptive Computing"},{"DOI":"10.13039\/100004316","name":"International Business Machines Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0926127"],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"name":"New Faculty Seed Grant"},{"DOI":"10.13039\/501100003845","name":"Indian Institute of Technology Madras","doi-asserted-by":"publisher","award":["CSE\/11-12\/567\/NFSC\/NANV"],"id":[{"id":"10.13039\/501100003845","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Texas Medical Center"},{"name":"Center for Domain-Specific Computing"},{"name":"Qlogic"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2013,4]]},"abstract":"Task parallelism has increasingly become a trend with programming models such as OpenMP 3.0, Cilk, Java Concurrency, X10, Chapel and Habanero-Java (HJ) to address the requirements of multicore programmers. While task parallelism increases productivity by allowing the programmer to express multiple levels of parallelism, it can also lead to performance degradation due to increased overheads. In this article, we introduce a transformation framework for optimizing task-parallel programs with a focus on task creation and task termination operations. These operations can appear explicitly in constructs such as async, finish in X10 and HJ, task, taskwait in OpenMP 3.0, and spawn, sync in Cilk, or implicitly in composite code statements such as foreach and ateach loops in X10, forall and foreach loops in HJ, and parallel loop in OpenMP.<\/jats:p>\n \n Our framework includes a definition of data dependence in task-parallel programs, a happens-before analysis algorithm, and a range of program transformations for optimizing task parallelism. Broadly, our transformations cover three different but interrelated optimizations: (1)\n finish-elimination<\/jats:italic>\n , (2)\n forall-coarsening<\/jats:italic>\n , and (3)\n loop-chunking<\/jats:italic>\n . Finish-elimination removes redundant task termination operations, forall-coarsening replaces expensive task creation and termination operations with more efficient synchronization operations, and loop-chunking extracts useful parallelism from ideal parallelism. All three optimizations are specified in an iterative transformation framework that applies a sequence of relevant transformations until a fixed point is reached. Further, we discuss the impact of exception semantics on the specified transformations, and extend them to handle task-parallel programs with precise exception semantics. Experimental results were obtained for a collection of task-parallel benchmarks on three multicore platforms: a dual-socket 128-thread (16-core) Niagara T2 system, a quad-socket 16-core Intel Xeon SMP, and a quad-socket 32-core Power7 SMP. We have observed that the proposed optimizations interact with each other in a synergistic way, and result in an overall geometric average performance improvement between 6.28\u00d7 and 10.30\u00d7, measured across all three platforms for the benchmarks studied.\n <\/jats:p>","DOI":"10.1145\/2450136.2450138","type":"journal-article","created":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T19:47:09Z","timestamp":1367437629000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["A Transformation Framework for Optimizing Task-Parallel Programs"],"prefix":"10.1145","volume":"35","author":[{"given":"V. Krishna","family":"Nandivada","sequence":"first","affiliation":[{"name":"IIT Madras"}]},{"given":"Jun","family":"Shirako","sequence":"additional","affiliation":[{"name":"Rice University"}]},{"given":"Jisheng","family":"Zhao","sequence":"additional","affiliation":[{"name":"Rice University"}]},{"given":"Vivek","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Rice University"}]}],"member":"320","published-online":{"date-parts":[[2013,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1229428.1229471"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155102"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125925"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1504176.1504215"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/209937.209958"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE International Workshop on Productivity and Performance in High-End Computing. IEEE, 66--75","author":"Chamberlain B. L.","year":"2004","unstructured":"Chamberlain , B. L. , Eun Choi , S. , Deitz , S. J. , And Snyder , L. 2004 . The high-level parallel language ZPL improves productivity and performance . In Proceedings of the IEEE International Workshop on Productivity and Performance in High-End Computing. IEEE, 66--75 . Chamberlain, B. L., Eun Choi, S., Deitz, S. J., And Snyder, L. 2004. The high-level parallel language ZPL improves productivity and performance. In Proceedings of the IEEE International Workshop on Productivity and Performance in High-End Computing. IEEE, 66--75."},{"key":"e_1_2_1_7_1","unstructured":"Chapel. 2005. Chapel. 2005. The chapel language specification version 0.4. http:\/\/chapel.cray.com\/spec\/spec-0.4.pdf. Chapel. 2005. Chapel. 2005. The chapel language specification version 0.4. http:\/\/chapel.cray.com\/spec\/spec-0.4.pdf."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094852"},{"volume-title":"Proceedings of the ACM\/IEEE Conference on Supercomputing (Supercomputing\u201990)","author":"Cytron R.","key":"e_1_2_1_9_1","unstructured":"Cytron , R. , Lipkis , J. , and Schonberg , E . 1990. A compiler-assisted approach to SPMD execution . In Proceedings of the ACM\/IEEE Conference on Supercomputing (Supercomputing\u201990) . IEEE Computer Society Press, Los Alamitos, CA, 398--406. Cytron, R., Lipkis, J., and Schonberg, E. 1990. A compiler-assisted approach to SPMD execution. In Proceedings of the ACM\/IEEE Conference on Supercomputing (Supercomputing\u201990). IEEE Computer Society Press, Los Alamitos, CA, 398--406."},{"volume-title":"Proceedings of the 9th European Conference on Object-Oriented Programming (ECOOP\u201995)","author":"Dean J.","key":"e_1_2_1_10_1","unstructured":"Dean , J. , Grove , D. , and Chambers , C . 1995. Optimization of object-oriented programs using static class hierarchy analysis . In Proceedings of the 9th European Conference on Object-Oriented Programming (ECOOP\u201995) . Springer, 77--101. Dean, J., Grove, D., and Chambers, C. 1995. Optimization of object-oriented programs using static class hierarchy analysis. In Proceedings of the 9th European Conference on Object-Oriented Programming (ECOOP\u201995). Springer, 77--101."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263718"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/120807.120811"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2009.64"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/258492.258493"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13374-9_30"},{"key":"e_1_2_1_16_1","unstructured":"Flynn L. E. and Hummel S. F. 1990. Scheduling variable-length parallel subtasks. Tech. rep. RC 15492 IBM. Flynn L. E. and Hummel S. F. 1990. Scheduling variable-length parallel subtasks. Tech. rep. RC 15492 IBM."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.868026"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297033"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161079"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/70082.68187"},{"key":"e_1_2_1_21_1","unstructured":"Habanero. 2009. Habanero Java. http:\/\/habanero.rice.edu\/hj. Habanero. 2009. Habanero Java. http:\/\/habanero.rice.edu\/hj."},{"key":"e_1_2_1_22_1","unstructured":"Heinz E. A. and Philippsen M. 1993. Synchronization barrier elimination in synchronous foralls. Tech. rep. 13\/93 Department of Informatics University of Karlruhe. Heinz E. A. and Philippsen M. 1993. Synchronization barrier elimination in synchronous foralls. Tech. rep. 13\/93 Department of Informatics University of Karlruhe."},{"key":"e_1_2_1_23_1","unstructured":"JGF. 2000. The java grande forum benchmark suite. http:\/\/www.epcc.ed.ac.uk\/javagrande\/javag.html. JGF. 2000. The java grande forum benchmark suite. http:\/\/www.epcc.ed.ac.uk\/javagrande\/javag.html."},{"key":"e_1_2_1_24_1","unstructured":"Kennedy K. and Allen J. R. 2002. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan Kaufmann San Francisco CA. Kennedy K. and Allen J. R. 2002. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan Kaufmann San Francisco CA."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1985.231547"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675439"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Larus J. R. and Rajwar R. 2006. Transactional Memory. Morgan and Claypool. Larus J. R. and Rajwar R. 2006. Transactional Memory . Morgan and Claypool.","DOI":"10.1007\/978-3-031-01719-3"},{"volume-title":"Proceedings of the 12th International Conference on Compiler Construction (CC\u201903)","author":"Lhotak O.","key":"e_1_2_1_29_1","unstructured":"Lhotak , O. and Hendren , L . 2003. Scaling java points-to analysis using spark . In Proceedings of the 12th International Conference on Compiler Construction (CC\u201903) . Springer, 153--169. Lhotak, O. and Hendren, L. 2003. Scaling java points-to analysis using spark. In Proceedings of the 12th International Conference on Compiler Construction (CC\u201903). Springer, 153--169."},{"key":"e_1_2_1_30_1","unstructured":"Metcalfe M. and Reid J. 1990. Fortran 90 Explained. Oxford Science Publishers. Metcalfe M. and Reid J. 1990. Fortran 90 Explained . Oxford Science Publishers."},{"volume-title":"Advanced Compiler Design and Implementation. Morgan Kaufmann","author":"Muchnick S. S.","key":"e_1_2_1_31_1","unstructured":"Muchnick , S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann , San Francisco, CA . Muchnick, S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2005.105"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542275.1542303"},{"volume-title":"Proceedings of the 12th International Conference on Compiler Construction (CC\u201903)","author":"Nystrom N.","key":"e_1_2_1_34_1","unstructured":"Nystrom , N. , Clarkson , M. R. , and Myers , A. C . 2003. Polyglot: An extensible compiler framework for Java . In Proceedings of the 12th International Conference on Compiler Construction (CC\u201903) . Springer, 138--152. Nystrom, N., Clarkson, M. R., and Myers, A. C. 2003. Polyglot: An extensible compiler framework for Java. In Proceedings of the 12th International Conference on Compiler Construction (CC\u201903). Springer, 138--152."},{"key":"e_1_2_1_35_1","unstructured":"OpenMP. 2008. OpenMP application program interface version 3.0. http:\/\/www.openmp.org\/mpdocuments\/spec30.pdf OpenMP. 2008. OpenMP application program interface version 3.0. http:\/\/www.openmp.org\/mpdocuments\/spec30.pdf"},{"key":"e_1_2_1_36_1","unstructured":"Peierls T. Goetz B. Bloch J. Bowbeer J. Lea D. and Holmes D. 2005. Java Concurrency in Practice. Addison-Wesley Professional. Peierls T. Goetz B. Bloch J. Bowbeer J. Lea D. and Holmes D. 2005. Java Concurrency in Practice. Addison-Wesley Professional."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.5009495"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30579-8_14"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55426"},{"volume-title":"Proceedings of the 7th International Euro-Par Conference on Parallel Processing (Euro-Par\u201901)","author":"Sarkar V.","key":"e_1_2_1_40_1","unstructured":"Sarkar , V. and Fink , S. J . 2001. Efficient dependence analysis for Java arrays . In Proceedings of the 7th International Euro-Par Conference on Parallel Processing (Euro-Par\u201901) . Springer, 273--277. Sarkar, V. and Fink, S. J. 2001. Efficient dependence analysis for Java arrays. In Proceedings of the 7th International Euro-Par Conference on Parallel Processing (Euro-Par\u201901). Springer, 273--277."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375527.1375568"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542275.1542304"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209952"},{"volume-title":"Proceedings of the Conference of the Centre for Advanced Studies on Collaborative Research (CASCON\u201999)","author":"Vallee-Rai R.","key":"e_1_2_1_44_1","unstructured":"Vallee-Rai , R. , Co , P. , Gagnon , E. , Hendren , L. , Lam , P. , and Sundaresan , V . 1999. Soot - A java bytecode optimization framework . In Proceedings of the Conference of the Centre for Advanced Studies on Collaborative Research (CASCON\u201999) . IBM Press, 125--135. Vallee-Rai, R., Co, P., Gagnon, E., Hendren, L., Lam, P., and Sundaresan, V. 1999. Soot - A java bytecode optimization framework. In Proceedings of the Conference of the Centre for Advanced Studies on Collaborative Research (CASCON\u201999). IBM Press, 125--135."},{"volume-title":"High Performance Compilers for Parallel Computing","author":"Wolfe M.","key":"e_1_2_1_45_1","unstructured":"Wolfe , M. 1996. High Performance Compilers for Parallel Computing . Addison-Wesley . Wolfe, M. 1996. High Performance Compilers for Parallel Computing. Addison-Wesley."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01379099"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278177.1278183"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/11946441_36"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2095050.2095103"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854298"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2450136.2450138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T06:09:01Z","timestamp":1672380541000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450136.2450138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1145\/2450136.2450138"],"URL":"https:\/\/doi.org\/10.1145\/2450136.2450138","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"2011-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}