Address-Branch Correlation: A Novel Locality For Long-Latency Hard-To-Predict Branches

Hard-to-predict branches depending on long-latency cache-misses have been recognized as a major performance obstacle for modern microprocessors. With the widening speed gap between memory and microprocessors, such long-latency branch mispredictions also waste substantial power/energy in executing instructions on wrong paths, especially for large instruction window processors. This paper presents a novel program locality that can be exploited to handle long-latency hard-to-predict branches. The locality is a result of an interesting program execution behavior: for some applications, major data structures or key components of the data structures tend to remain stable for a long time. If a hard-to-predict branch depends on such stable data, the address of the data rather than the data value is sufficient to determine the branch outcome. This way, a misprediction can be resolved much more promptly when the data access results in a long-latency cache miss. We call such locality address-branch correlation and we show that certain memory-intensive benchmarks, especially those with heavy pointer chasing, exhibit this locality. We then propose a low-cost auxiliary branch predictor to exploit address-branch correlation. Our experimental results show that the proposed scheme reduces the execution time by 6.3% (up to 27%) and energy consumption by 5.2% (up to 24%) for a set of memory-intensive benchmarks with a 9kB prediction table when used with a state-of-art 16kB TAGE predictor. ©2008 IEEE