{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:28:45Z","timestamp":1763458125560,"version":"3.45.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,28]],"date-time":"2017-12-28T00:00:00Z","timestamp":1514419200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"U.S. Department of Energy's (DOE) Office of Science"},{"name":"Battelle for DOE","award":["DE-AC05-76RL01830"],"award-info":[{"award-number":["DE-AC05-76RL01830"]}]},{"DOI":"10.13039\/100011661","name":"Pacific Northwest National Laboratory","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100011661","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1319420 and CCF-1629392"],"award-info":[{"award-number":["CCF-1319420 and CCF-1629392"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"The Ohio State University"},{"name":"Office of Advanced Scientific Computing Research","award":["63823"],"award-info":[{"award-number":["63823"]}]},{"DOI":"10.13039\/100000015","name":"Department of Energy","doi-asserted-by":"crossref","award":["DE-SC0014135"],"award-info":[{"award-number":["DE-SC0014135"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2016,12,28]]},"abstract":"<jats:p>\n                    The emergence of the multi-core era has led to increased interest in designing effective yet practical parallel programming models. Models based on task graphs that operate on\n                    <jats:italic toggle=\"yes\">single-assignment<\/jats:italic>\n                    data are attractive in several ways. Notably, they can support dynamic applications and precisely represent the available concurrency. However, for efficient execution, they also require nuanced algorithms for scheduling and memory management. In this article, we consider memory-efficient dynamic scheduling of task graphs. Specifically, we present a novel approach for dynamically recycling the memory locations assigned to data items as they are produced by tasks. We develop algorithms to identify memory-efficient store recycling functions by systematically evaluating the validity of a set of user-provided or automatically generated alternatives. Because recycling functions can be input data-dependent, we have also developed support for continued correct execution of a task graph in the presence of a potentially incorrect store recycling function.\n                  <\/jats:p>\n                  <jats:p>Experimental evaluation demonstrates that this approach to automatic store recycling incurs little to no overheads, achieves memory usage comparable to the best manually derived solutions, often produces recycling functions valid across problem sizes and input parameters, and efficiently recovers from an incorrect choice of store recycling functions.<\/jats:p>","DOI":"10.1145\/3018111","type":"journal-article","created":{"date-parts":[[2016,12,28]],"date-time":"2016-12-28T08:20:40Z","timestamp":1482913240000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["User-Assisted Store Recycling for Dynamic Task Graph Schedulers"],"prefix":"10.1145","volume":"13","author":[{"given":"Mehmet Can","family":"Kurt","sequence":"first","affiliation":[{"name":"Quantcast Corporation, San Francisco, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sriram","family":"Krishnamoorthy","sequence":"additional","affiliation":[{"name":"Pacific Northwest National Laboratory, Richland, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gagan","family":"Agrawal","sequence":"additional","affiliation":[{"name":"The Ohio State University, Neil Avenue Columbus, OH"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Ren","sequence":"additional","affiliation":[{"name":"The College of William and Mary, Williamsburg, VA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,12,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00722-4_15"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470403"},{"volume-title":"Proceedings of the 8th Annual Symposium on Computer Architecture (ISCA\u2019 81)","year":"1981","key":"e_1_2_1_3_1","unstructured":"Arvind. 1981. Data flow languages and architecture. In Proceedings of the 8th Annual Symposium on Computer Architecture (ISCA\u2019 81). 1."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1631"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30961-8_8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1155\/2010\/521797"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1481839.1481846"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"A. Bui Kwang-Ting Cheng J. Cong L. Vese Yi-Chu Wang Bo Yuan and Yi Zou. 2012. Platform characterization for domain-specific computing. In ASP-DAC. 94--99.","DOI":"10.1109\/ASPDAC.2012.6165071"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2009.5306797"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-06859-7_145"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626411000151"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.66"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2248418.2248426"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/318593.318660"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/HIPC.2009.5433201"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","unstructured":"Mehmet Can Kurt Sriram Krishnamoorthy Kunal Agrawal and Gagan Agrawal. 2014. Fault-tolerant dynamic task graph scheduling. In SC. 719--730. 10.1109\/SC.2014.64","DOI":"10.1109\/SC.2014.64"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/344588.344618"},{"key":"e_1_2_1_18_1","unstructured":"Malcolm Yoke Hean Low Weiguo Liu and Bertil Schmidt. 2007. A parallel BSP algorithm for irregular dynamic programming. In APPT. 151--160."},{"key":"e_1_2_1_19_1","unstructured":"Nicholas D. Matsakis. 2012. Parallel closures: A new twist on an old idea. In HotPar. 5--5."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00070-8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2400682.2400712"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1988915.1988918"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","unstructured":"Veselin Raychev Martin Vechev and Manu Sridharan. 2013. Effective race detection for event-driven programs. In OOPSLA. 151--166. DOI:http:\/\/dx.doi.org\/10.1145\/2509136.2509538 10.1145\/2509136.2509538","DOI":"10.1145\/2509136.2509538"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Dragos Sbirlea Zoran Budimlic and Vivek Sarkar. 2014. Bounded memory scheduling of dynamic task graphs. In PACT. 343--356. DOI:http:\/\/dx.doi.org\/10.1145\/2628071.2628090 10.1145\/2628071.2628090","DOI":"10.1145\/2628071.2628090"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","unstructured":"Dragos Sbirlea Kathleen Knobe and Vivek Sarkar. 2012. Folding of tagged single assignment values for memory-efficient parallelism. In Euro-Par. 601--613. 10.1007\/978-3-642-32820-6_60","DOI":"10.1007\/978-3-642-32820-6_60"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380231102"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Sagnak Tasirlar and Vivek Sarkar. 2011. Data-driven tasks and their implementation. In ICPP. 652--661. DOI:http:\/\/dx.doi.org\/10.1109\/ICPP.2011.87 10.1109\/ICPP.2011.87","DOI":"10.1109\/ICPP.2011.87"},{"key":"e_1_2_1_28_1","unstructured":"Asim YarKhan Jakub Kurzak and Jack Dongarra. 2011. Quark users guide: Queueing and runtime for kernels. University of Tennessee Innovative Computing Laboratory Technical Report ICL-UT-11-02."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3018111","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3018111","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3018111","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:18:08Z","timestamp":1763457488000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3018111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,28]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12,28]]}},"alternative-id":["10.1145\/3018111"],"URL":"https:\/\/doi.org\/10.1145\/3018111","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2016,12,28]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}