UC San Diego

All-pairs shortest paths is a fundamental algorithm used for routing, logistics, and network analysis, but the cubic time complexity and heavy data movement of the canonical Floyd-Warshall algorithm severely limits its scalability on conventional CPUs or GPUs. In this paper, we propose PIM-FW, a novel co-designed hardware architecture and dataflow leveraging processing in and near memory to accelerate the blocked FW algorithm on an HBM3 stack. To enable fine-grained parallelism, we propose a massively parallel array of specialized bit-serial bank and channel PEs designed to accelerate core min-plus operations. Our dataflow complements this hardware, employing an interleaved mapping policy for superior load balancing and a hybrid memory computing model for efficient computation and reduction. This in-bank computing approach allows all distance updates to be performed and stored locally, a key contribution which eliminates the data-movement bottleneck inherent in GPU-based approaches. We implement a full hardware-software co-design using a cycle-accurate simulator for an 8-channel, 4-Hi HBM3 stack on real road-network traces. Experimental results show that, for an 8, 192 × 8, 192 graph, PIM-FW achieves an 18.7 × speedup and consumes 3200 × lower memory-stack/accelerator-side energy under our modeled PIM stack assumptions compared to a state-of-the-art GPU-only Floyd-Warshall.