Accelerating Out-of-Core Graph Random Walk Processing via Locality-Aware Algorithm-Hardware Co-Design

Authors:
Open Access
Publisher website
Google Scholar
Abstract
Modern out-of-core random walk systems partition large disk-resident graphs into blocks and use walkers to efficiently scale graph processing. However, our study reveals a critical inefficiency: while most walker updates are processed efficiently, a small fraction of remaining walkers incur disproportionately high block I/Os, accounting for over 75% of total block I/O time. This performance bottleneck stems from static in-memory block layouts, which lead to excessive loading of irrelevant data during late-stage walker updates. To address this, we introduce LocWalker, a storage system that combines algorithmic and hardware innovations to optimize I/O efficiency for out-of-core random walks. At the algorithmic level, LocWalker specifically optimizes the last remaining few walkers processing through a skeleton-based walker updating scheme and a bounded breadth-first search (BBFS)-based block shrinking mechanism, both leveraging temporal and spatial locality to reduce the number and size of block I/Os per iteration during the iterative random walk process. Architecturally, LocWalker integrates a hardware-accelerated block provision engine on a computational SSD to minimize additional computational overhead introduced by our innovative features. High-level APIs enable easy integration with existing systems. Evaluated against SOWalker, GraphWalker, and NosWalker with a Samsung SmartSSD, LocWalker achieved substantial I/O time reductions (1.82× to 11.06×) and overall performance improvements (1.44× to 5.43×).
Funding Information
  • National Key Research and Development Program of China (2023YFB4503400)
  • National Natural Science Foundation of China (62402456 and 62402457)
  • Zhejiang Provincial Natural Science Foundation of China (LQ24F020027)

This publication has 43 references indexed in Scilit: