Presentation
GPU-Accelerated BFS for Dynamic Networks
DescriptionThe breadth-first-search (BFS) algorithm serves as a fundamental building block for graph traversal with a wide range of applications, spanning from the electronic design automation (EDA) field to social network analysis. Many contemporary real-world networks are dynamic and evolve rapidly over time. In such cases, recomputing the BFS from scratch after each graph modification becomes impractical. While parallel solutions, particularly for GPUs, have been introduced to handle the size complexity of static networks, none have addressed the issue of work-efficiency in dynamic networks. In this paper, we propose a GPU-based BFS implementation capable of processing batches of network updates concurrently. Our solution leverages batch information to minimize the total workload required to update the BFS result. Additionally, we introduce a technique for relabeling nodes, enhancing locality during dynamic BFS traversal. We present experimental results on a diverse set of large networks with varying characteristics and batch sizes.
Event Type
Work-in-Progress Poster
TimeTuesday, June 256:00pm - 7:00pm PDT
LocationLevel 2 Lobby
AI
Autonomous Systems
Cloud
Design
EDA
Embedded Systems
IP
Security