Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel notion of convergence for control-flow graphs, focusing on the synchronization of threads within a thread block. By formalizing convergent nodes and edges, the authors provide a framework that allows compilers to identify when barriers can be safely placed, thus eliminating unnecessary code transformations for warp-synchronous hardware. The proposed linear-time iterative work-list algorithm effectively propagates convergence information, enhancing precision through additional refinements based on region and path information.
Identifying convergent regions in control-flow graphs can drastically reduce the overhead of thread synchronization in parallel computing.
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.