Parallélisation de transformations structurelles sur les Tarbres

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.Les arbres sont partout, et pourtant les opérations internes des arbres restent encore moins optimisées que celles des tableaux. Notre travail s’inscrit dans la continuité de la recherche sur les algorithmes d’arbres indépendants du cache. Dans cet article, nous nous proposons d’analyser les propriétés relatives au parallélisme des Tarbres–une représentation implicite des arbres AVL. Notre première contribution se compose d’un ensemble d’opérations bas-niveau nécessaire à une maintenance efficace des Tarbres en place. Ces opérations ouvrent la porte à de nouvelles optimisations ainsi qu’à une parallélisation de leur fonctionnement interne. Notre deuxième contribution est une nouvelle implémentation qui tire profit de ces opportunités, suivie d’une comparaison avec l’expressivité du modèle polyédrique, telle qu’elle est aujourd’hui. Finalement, nous présentons nos résultats expérimentaux qui mettent en avant les performances des Tarbres