Workshop: IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms
Authors: Tasmia Jannat and Gharret Wilcut (Missouri University of Science and Technology, Department of Computer Science); Sanjukta Bhowmick (University of North Texas); and Satish Puri (Missouri University of Science and Technology, Department of Computer Science)
Abstract: Breadth-first search (BFS) is difficult to accelerate because of irregular memory accesses, limited computation per edge, and frequent synchronization. Processing-in-Memory (PIM) offers high memory-level parallelism, but level-synchronous BFS is ill-suited to UPMEM because DRAM Processing Units (DPUs) cannot communicate directly and must coordinate through the host. To address this, we present BFS-FAR, an execution model that replaces strict level-by-level synchronization with fragment-local progress and update-aware reconciliation. BFS-FAR partitions graphs into per-DPU CSR fragments, performs in-place local relaxation, and reconciles replicated levels through a parallel host-side minimum reduction. Experiments on R-MAT and synthetic graphs using up to 2,540 DPUs show 18.0-86.5 algorithm-only speedups over PrIM-BFS, although CPU_64T remains faster because host-mediated coordination still limits complete BFS performance. These results highlight execution model and communication granularity as key design considerations for irregular PIM workloads.
Back to IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing
Back to Full Workshop Archive Listing