Adaptive Predicated Execution

Dr. Kim is from University of Texas, Austin
Branch mispredictions are a major source of wasted energy consumption and a
major obstacle to building a high-performance processor. Predicated
execution, a compiler-oriented solution to the problem, eliminates branch
instructions by converting control dependencies to data dependencies at the
cost of fetching both sides of the branch direction. Hence, if a branch is
easy-to-predict at run-time, predicting the branch direction (a
hardware-only solution) is more efficient. On the other hand, if a branch is
hard-to-predict at run-time, predicating the branch code (a compiler-only
solution) provides better performance. Since predication is not adaptive to
run-time program behavior, it sometimes reduces performance and increases
energy consumption significantly.

In this talk, I will describe my proposed solutions to the "branch problem"
that combine the two mechanisms (branch prediction and predication)
effectively. The first solution is wish branches, which allow the compiler
to generate code that can be executed either as normal branch code or as
predicated code. With wish branches, the hardware chooses between normal
branch code and predicated code based on the run-time branch behavior and
the estimated run-time effectiveness of either solution. The second, more
powerful solution is the diverge-merge processor (DMP), which dynamically
predicates instructions at run-time, using dynamic information about
frequently-executed program paths and control-flow hints provided by the
compiler. DMP not only provides run-time adaptivity to predication but also
enables a much larger set of control-flow graphs to be predicated without
requiring significant support in the instruction set architecture.
Experimental evaluations show that DMP eliminates a large set of branch
mispredictions with significantly less overhead than previously proposed
branch handling paradigms and thereby both improves performance and reduces
the overall energy consumption of high-performance processors.

Hyesoon Kim is a Ph.D. candidate in Electrical and Computer Engineering
at UT-Austin. Her research interests include high-performance
energy-efficient microarchitectures and
programmer-compiler-microarchitecture interaction. She received a BA in
mechanical engineering from Korea Advanced Institute of Science and
Technology (KAIST), an MS in mechanical engineering from Seoul National
University, and an MS in computer engineering from UT-Austin. She worked at
Intel for four summers and previously she was a researcher at Hyundai Motor
Company Research Labs.