Realizing Hardware-Optimized General Tree-Based Data Structures for Heterogeneous System Classes

1 st Daniel Biebert, 2 nd Christian Hakert, 3 rd Jian-Jia Chen · 2025

Read Realizing Hardware-Optimized General Tree-Based Data Structures for Heterogeneous System Classes by 1 st Daniel Biebert, 2 nd Christian Hakert, 3 rd Jian-Jia Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-17434.txt.

Description

Biebert, Hakert, and Chen show how the layout of tree data in memory can exploit hardware traits to speed up access. Tree structures appear across computing, and many versions exist. Almost all share one pattern: walks start at the root and head toward a leaf. Memory types differ widely in speed and access cost, though. Those traits can be treated in parallel ways across systems. The team asks how node order in memory can match them.

By reordering nodes, common walks touch memory in friendlier patterns. The paper presents methods to realize such layouts for general tree types. Tests span several classes of mixed hardware systems. The aim is one data structure that adapts rather than many hand-tuned variants.

Catalog record

CREATOR1 st Daniel Biebert, 2 nd Christian Hakert, 3 rd Jian-Jia Chen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-17434

Browse the full library · About the Tower of Babel