PIM-FW: Hardware-Software Co-Design of All-pairs Shortest Paths in DRAM

Tsung-Han Lu, Zheyu Li, Minxuan Zhou, Tajana RosingarXiv 2025 · DOI · arXiv

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:

  1. Bank Processing Elements (BPEs): 16 compact, bit-serial units are embedded in every DRAM bank to handle local $O(N^3)$ updates.
  2. Channel Processing Elements (CPEs): Located at the channel level, these units manage data aggregation and global communication across banks.
PIM-FW bank-level architecture featuring bit-serial Bank Processing Elements (BPEs).

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.
Energy consumption comparison and area overhead breakdown of the PIM-FW architecture.

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

BibTeX
@misc{lu2025pim,
  author = {Tsung-Han Lu and Zheyu Li and Minxuan Zhou and Tajana Rosing},
  title = {{PIM-FW: Hardware-Software Co-Design of All-pairs Shortest Paths in DRAM}},
  year = {2025},
  eprint = {2512.18158},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.18158},
}
Figure