Close

Presentation

An Adaptive Asynchronous Approach for the Single-Source Shortest Paths Problem
DescriptionLarge-scale graphs with billions and trillions of vertices and edges require efficient parallel algorithms for common graph problems, one of which is single-source shortest paths (SSSP). Bulk-synchronous parallel algorithms such as Delta-stepping experience large synchronization costs at the scale of many nodes, so asynchronous approaches are needed for scalability. However, asynchronous approaches are susceptible to wasteful, speculative execution. We introduce ACIC, a highly asynchronous approach modulated by continuous concurrent introspection and adaptation. Using message-driven concurrent reductions and broadcasts, task-based scheduling, and an adaptive aggregation library, we explore techniques such as evolving windows and generation and prioritized flow of optimal updates, or edge relaxations, aimed at reducing speculative loss without constraining parallelism. Our results, while preliminary, demonstrate the promise of these ideas, with the potential to impact a wider class of graph algorithms.
Event Type
Workshop
TimeSunday, 17 November 20242:40pm - 2:50pm EST
LocationB310
Tags
Graph Algorithms
Heterogeneous Computing
Programming Frameworks and System Software
Registration Categories
W