Abstract
The All-Pairs Shortest Paths (APSP) problem is a fundamental computational challenge in network analysis, often bottlenecked by the "memory wall" in traditional architectures. We present PIM-FW, a hardware-software co-design that accelerates the Floyd-Warshall (FW) algorithm by integrating computation directly into High-Bandwidth Memory (HBM3). By utilizing bit-serial processing elements within DRAM banks and a novel interleaved data mapping, PIM-FW achieves an 18.7× speedup and a 3,200× energy reduction compared to an NVIDIA A100 GPU, while occupying less than 1% of the die area.
Introduction
The All-Pairs Shortest Paths (APSP) problem is essential for logistics, routing, and social network analysis. The standard Floyd-Warshall (FW) algorithm has $O(N^3)$ complexity, which on modern CPUs and GPUs leads to significant data movement overhead. For every "min-plus" operation, the processor must fetch three values and write one back, causing the memory bus to become a bottleneck. This "memory wall" leaves powerful GPU cores idling and consumes the majority of system energy. PIM-FW addresses this by moving the computation to where the data resides.
Methods: Hybrid PIM-PNM Architecture
PIM-FW employs a hybrid approach combining Processing-In-Memory (PIM) and Processing-Near-Memory (PNM) to balance local throughput with global communication.
Hardware Design
The architecture features two types of processing units:
- Bank Processing Elements (BPEs): 16 compact, bit-serial units are embedded in every DRAM bank to handle local $O(N^3)$ updates.
- Channel Processing Elements (CPEs): Located at the channel level, these units manage data aggregation and global communication across banks.
The use of bit-serial logic instead of parallel 32-bit adders ensures extreme area efficiency. This allows the PIM logic to be integrated into HBM3 with minimal manufacturing overhead.
Software and Data Mapping
A compiler-driven interleaved mapping policy distributes the distance matrix tiles across HBM3’s 32 bank-groups. This static policy ensures high parallelism across all memory channels and prevents hotspots, maximizing the utilization of the distributed BPEs.
Evaluation
The system was evaluated using real-world graph traces from the SNAP dataset and OpenStreetMap, including:
- ca-GrQc: Collaboration network ($N = 5,242$).
- p2p-Gnutella08: Peer-to-peer network ($N = 6,301$).
- OpenStreetMap: Road network ($N = 8,192$).
Key Results
PIM-FW demonstrates significant improvements over high-end GPU baselines.
- Performance: It achieves an 18.7× speedup over an optimized blocked FW implementation on an NVIDIA A100. Even against projected H100 performance, it maintains a 4.2× advantage.
- Energy and Area Efficiency: The architecture reduces DRAM energy consumption by 3,200× compared to the A100. Furthermore, the area overhead is remarkably low, with the PIM/PNM logic occupying less than 1% of the total die area.
Discussion and Conclusion
The primary insight of PIM-FW is the "Energy-Movement Paradox": the cost of moving data often dwarfs the cost of computation. By adopting a pragmatic division of labor between PIM (local math) and PNM (global coordination), PIM-FW overcomes the memory wall. While currently optimized for dense graphs and fixed tile sizes, future iterations could extend these principles to sparse-graph algorithms and more flexible hardware allocations. PIM-FW proves that architectural innovation in memory is a viable path forward for data-intensive graph problems.
Summary updated