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 <>
Submitted on : Tuesday, April 27, 2021 - 3:41:07 PM
Last modification on : Wednesday, April 28, 2021 - 3:36:26 AM


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