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
| CREATOR | 1 st Daniel Biebert, 2 nd Christian Hakert, 3 rd Jian-Jia Chen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-17434