Orchard: Heterogeneous Parallelism and Fine-grained Fusion for Complex Tree Traversals
Open Access
- 21 May 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 21 (2) , 1-25
Abstract
Many applications are designed to perform traversals on tree-like 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 Orchard built on top of Grafter . Orchard ’s novelty lies in allowing the programmer to transform tree traversal applications by automatically applying fine-grained fusion and extracting heterogeneous parallelism. Orchard 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.Keywords
Funding Information
- NSF (CCF-1725672, CCF-1725679, CCF-1150013, CCF-1439126, CCF-1908504, CCF-1919197, CCF-2216978)
- DOE (DE-SC0010295)
This publication has 23 references indexed in Scilit:
- MADNESS: A Multiresolution, Adaptive Numerical Environment for Scientific SimulationSIAM Journal on Scientific Computing, 2016
- Compositions of extended top-down tree transducersInformation and Computation, 2008
- A practical automatic polyhedral parallelizer and locality optimizer2008
- Stream fusion2007
- Extracting queries by static analysis of transparent persistence2007
- Profitable loop fusion and tiling using model-driven empirical search2006
- A nanopass infrastructure for compiler education2004
- Output String Languages of Compositions of Deterministic Macro Tree TransducersJournal of Computer and System Sciences, 2002
- Deforestation: transforming programs to eliminate treesTheoretical Computer Science, 1990
- Tree acceptors and some of their applicationsJournal of Computer and System Sciences, 1970