HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Parallelizing Structural Transformations on Tarbres

Paul Iannetta 1 Laure Gonnord 1 Gabriel Radanne 1
1 CASH - CASH - Compilation and Analysis, Software and Hardware
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Trees are used everywhere, yet their internal operations are nowhere as optimized as arrays are. Our work is in the continuity of the research on cache-oblivious algorithms for trees. In this article, we investigate the parallel properties of Tarbres–an implicit representation for AVL trees. Our first contribution is a new set of structural low-level operations which are needed to efficiently manipulate Tarbres in-place. These operations expose opportunities for further optimisations and parallelization. We provide as a second contribution new implementations which take advantage of these opportunities and proceed to a comparison with the actual expressivity of the polyhedral model framework for loop optimisation. Finally, experimental evaluation highlights the performance advantages of Tarbres.
Complete list of metadata

Contributor : Paul Iannetta Connect in order to contact the contributor
Submitted on : Tuesday, April 27, 2021 - 3:41:07 PM
Last modification on : Monday, May 16, 2022 - 3:06:02 PM


Files produced by the author(s)


  • HAL Id : hal-03208466, version 1



Paul Iannetta, Laure Gonnord, Gabriel Radanne. Parallelizing Structural Transformations on Tarbres. [Research Report] RR-9405, ENS Lyon, CNRS & INRIA. 2021, pp.21. ⟨hal-03208466⟩



Record views


Files downloads