Exploring the Design Space of SPMD Divergence Management on Data-Parallel Architectures

Abstract—Data-parallel architectures must provide efficient
support for complex control-flow constructs to support sophisticated
applications coded in modern single-program multipledata
languages. As these architectures have wide datapaths that
process a single instruction across parallel threads, a mechanism
is needed to track and sequence threads as they traverse
potentially divergent control paths through the program. The
design space for divergence management ranges from softwareonly
approaches where divergence is explicitly managed by the
compiler, to hardware solutions where divergence is managed
implicitly by the microarchitecture. In this paper, we explore
this space and propose a new predication-based approach for
handling control-flow structures in data-parallel architectures.
Unlike prior predication algorithms, our new compiler analyses
and hardware instructions consider the commonality of
predication conditions across threads to improve efficiency. We
prototype our algorithms in a production compiler and evaluate
the tradeoffs between software and hardware divergence management
on current GPU silicon. We show that our compiler
algorithms make a predication-only architecture competitive
in performance to one with hardware support for tracking
divergence.
Paper