Locality Aware Process Remapping for Distributed-Memory Graph Workloads
Md Nahid Newaz, Sayan Ghosh, Nathan R. Tallent, Guangzhi Qu · 2025
Distributed-memory graph applications are dominated by communication and synchronization overheads. For such applications, the communication pattern comprises of variable-sized data exchanges between process neighbors in a process graph topology. Unlike process grid for rectangular problems, it is much more difficult to optimize communication for the graph topology. Custom process assignment can improve the communication performance irrespective of the data partitioning strategy. Existing automated solutions are scarce and only caters to a cartesian process topology and not the graph topology which is induced by graph-based workloads. In this paper, we propose automated network-agnostic locality-aware process assignment heuristics for distributedmemory graph workloads, based on the structure of input graphs. For four communication intensive distributed-memory graph workloads - Breadth First Search (BFS), Louvain Clustering, Triangle Counting and Single Source Shortest Path (SSSP), we demonstrate up to$30-40 \%$improvements in the overall MPI communication times through proposed process remapping methodologies via packet-level simulations using Structural Simulation Toolkit (SST) and validate the strategies empirically on HPE Slingshot network of the NERSC Perlmutter supercomputer.