  Branch prediction is arguably one of the most important speculative
mechanisms within a high-performance processor architecture. A common approach
to improve branch prediction accuracy is to employ lengthy history records of
previously seen branch directions to capture distant correlations between
branches. The larger the history, the richer the information that the predictor
can exploit for discovering predictive patterns. However, without appropriate
filtering, such an approach may also heavily disorganize the predictor's
internal mechanisms, leading to diminishing returns. This paper studies a
fundamental control-flow property: the sparsity in the correlation between
branches and recent history. First, we show that sparse branch correlations
exist in standard applications and, more importantly, such correlations can be
computed efficiently using sparse modeling methods. Second, we introduce a
sparsity-aware branch prediction mechanism that can compactly encode and store
sparse models to unlock essential performance opportunities. We evaluated our
approach for various design parameters demonstrating MPKI improvements of up to
42% (2.3% on average) with 2KB of additional storage overhead. Our
circuit-level evaluation of the design showed that it can operate within
accepted branch prediction latencies, and under reasonable power and area
limitations.
