This paper investigates the theoretical step complexity tradeoffs between Breadth-First Search (BFS) and connectivity-based Random Spanning Tree (RST) algorithms on emerging memory architectures. It introduces a unified hierarchical memory model and proposes a hybrid algorithm that adapts between BFS and RST approaches based on memory characteristics.
Key findings
BFS and RST exhibit different access patterns favoring certain memory hierarchy configurations.
Connectivity-based RST algorithms achieve better step complexity on memory hierarchies with high bandwidth asymmetry.
A hybrid algorithm, HemHybrid, adaptively switches between BFS and RST for improved performance.
Limitations & open questions
The paper focuses on theoretical analysis and requires empirical validation on real hardware.