On Thread Convergence
arXiv:2607.11636
The paper defines a notion of convergence for nodes and edges in a control‑flow graph to determine when a barrier will reliably synchronize all threads in a GPU thread block, and presents a linear‑time analysis algorithm with refinements for better precision.
Abstract
We introduce a notion of convergence for the nodes and edges of a control-flow graph that captures whether a barrier placed at that location is guaranteed to synchronize all threads of a thread block in every execution. Convergence analysis lets a compiler determine when a barrier lies in a uniformly executed region and therefore avoid the code transformations otherwise required to implement thread-block barriers correctly on warp-synchronous hardware. We formalize convergent nodes, convergent edges, and well-synchronized programs; give two inference rules (a branch rule and a merge rule); and present a linear-time iterative work-list algorithm that propagates convergence information bidirectionally through the flow graph. We then describe refinements that improve precision using single-entry single-exit region information, path information, and thread-variance information.