{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:44:49Z","timestamp":1783035889279,"version":"3.54.6"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T00:00:00Z","timestamp":1716249600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1725672, CCF-1725679, CCF-1150013, CCF-1439126, CCF-1908504, CCF-1919197, CCF-2216978"],"award-info":[{"award-number":["CCF-1725672, CCF-1725679, CCF-1150013, CCF-1439126, CCF-1908504, CCF-1919197, CCF-2216978"]}]},{"name":"DOE","award":["DE-SC0010295"],"award-info":[{"award-number":["DE-SC0010295"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            Many applications are designed to perform traversals on\n            <jats:italic>tree-like<\/jats:italic>\n            data structures. Fusing and parallelizing these traversals enhance the performance of applications. Fusing multiple traversals improves the locality of the application. The runtime of an application can be significantly reduced by extracting parallelism and utilizing multi-threading. Prior frameworks have tried to fuse and parallelize tree traversals using coarse-grained approaches, leading to missed fine-grained opportunities for improving performance. Other frameworks have successfully supported fine-grained fusion on heterogeneous tree types but fall short regarding parallelization. We introduce a new framework\n            <jats:sc>Orchard<\/jats:sc>\n            built on top of\n            <jats:sc>Grafter<\/jats:sc>\n            .\n            <jats:sc>Orchard<\/jats:sc>\n            \u2019s novelty lies in allowing the programmer to transform tree traversal applications by automatically applying\n            <jats:italic>fine-grained<\/jats:italic>\n            fusion and extracting\n            <jats:italic>heterogeneous<\/jats:italic>\n            parallelism.\n            <jats:sc>Orchard<\/jats:sc>\n            allows the programmer to write general tree traversal applications in a simple and elegant embedded Domain-Specific Language (eDSL). We show that the combination of fine-grained fusion and heterogeneous parallelism performs better than each alone when the conditions are met.\n          <\/jats:p>","DOI":"10.1145\/3652605","type":"journal-article","created":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T12:00:37Z","timestamp":1710504037000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Orchard: Heterogeneous Parallelism and Fine-grained Fusion for Complex Tree Traversals"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6912-3840","authenticated-orcid":false,"given":"Vidush","family":"Singhal","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5796-4066","authenticated-orcid":false,"given":"Laith","family":"Sakka","sequence":"additional","affiliation":[{"name":"Meta, Menlo Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6384-062X","authenticated-orcid":false,"given":"Kirshanthan","family":"Sundararajah","sequence":"additional","affiliation":[{"name":"Virginia Tech, Blacksburg, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3934-9165","authenticated-orcid":false,"given":"Ryan","family":"Newton","sequence":"additional","affiliation":[{"name":"Meta and Purdue University, Menlo Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6827-345X","authenticated-orcid":false,"given":"Milind","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,21]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209958"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507751"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291199"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.1999.807510"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80041-1"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1816"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1026171"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645671.665526"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.53993"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.03.019"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772763"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442535"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062346"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183401.1183437"},{"key":"e_1_3_3_17_1","first-page":"468","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Rajbhandari S.","year":"2016","unstructured":"S. Rajbhandari, J. Kim, S. Krishnamoorthy, L. Pouchet, F. Rastello, R. J. Harrison, and P. Sadayappan. 2016. A domain-specific compiler for a parallel multiresolution adaptive numerical simulation environment. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 468\u2013479."},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892228"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133900"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314626"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","unstructured":"Dipanwita Sarkar Oscar Waddell and R. Kent Dybvig. 2005. EDUCATIONAL PEARL: A Nanopass framework for compiler education. J. Funct. Program. 15 5 (2005) 653\u2013667. 10.1017\/S0956796805005605","DOI":"10.1017\/S0956796805005605"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018758"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90147-A"},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737972"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190248"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3652605","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3652605","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3652605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:30Z","timestamp":1750291410000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3652605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,21]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3652605"],"URL":"https:\/\/doi.org\/10.1145\/3652605","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,21]]},"assertion":[{"value":"2023-07-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}