Poster Type: Research Posters
Author: Tasmia Jannat (Missouri S&T, Department of Computer Science), Gharret Wilcut (Missouri S&T, Department of Computer Science), Sanjukta Bhowmick (University of North Texas), Satish Puri (Missouri S&T, Department of Computer Science)
Abstract: Breadth-first search (BFS) is difficult to accelerate because of irregular memory access, low work per edge, and frequent synchronization. On UPMEM Processing-in-Memory systems, DPUs cannot communicate directly, so existing PIM-BFS designs rely heavily on host-mediated frontier exchange.
We present BFS-FAR, a completed fragmented BFS design that combines locally asynchronous relaxation within each DPU with host-side minimum-level reconciliation. Its key contribution is allowing improved levels to be reused within the same DPU launch, reducing repeated global frontier exchange and host coordination. Experiments using up to 2,540 DPUs cover R-MAT graphs with approximately 262K–4.2M vertices and 4.2M–67.1M directed edges, and controlled-size synthetic graphs ranging from 200K vertices and 10M edges to 13.6M vertices and 730M edges. BFS-FAR achieves 18.0×–86.5× algorithm-only speedup over UPMEM baseline, PrIM-BFS.
The poster will present the BFS-FAR workflow, performance results, timing breakdowns, DPU scaling, and the effects of locality and workload balance.
Best Poster Finalist (BP): no
Poster: PDF
Poster Summary: PDF