Orchard: Heterogeneous Parallelism and Fine-grained Fusion for Complex Tree Traversals

dc.contributor.authorSinghal, Vidushen
dc.contributor.authorSakka, Laithen
dc.contributor.authorSundararajah, Kirshanthanen
dc.contributor.authorNewton, Ryanen
dc.contributor.authorKulkarni, Milinden
dc.date.accessioned2024-04-01T17:01:46Zen
dc.date.available2024-04-01T17:01:46Zen
dc.date.issued2024en
dc.date.updated2024-04-01T07:53:17Zen
dc.description.abstractMany 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 extract- ing 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.en
dc.description.versionPublished versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.1145/3652605en
dc.identifier.urihttps://hdl.handle.net/10919/118494en
dc.language.isoenen
dc.publisherACMen
dc.rightsIn Copyrighten
dc.rights.holderThe author(s)en
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleOrchard: Heterogeneous Parallelism and Fine-grained Fusion for Complex Tree Traversalsen
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
3652605.pdf
Size:
1.29 MB
Format:
Adobe Portable Document Format
Description:
Accepted version
License bundle
Now showing 1 - 1 of 1
Name:
license.txt
Size:
1.5 KB
Format:
Item-specific license agreed upon to submission
Description: