The elastic history buffer - a multi-hybrid branch prediction scheme using static classification /

Modern high-performance architectures are increasingly relying on dynamic branch prediction mechanisms to reduce the impact of branches on system performance. Most dynamic schemes use a table of state counters associated with specific branches, coupled with a buffer recording recent branch outcomes to correlate the behaviour of individual branches with the history of other recently executed branch instructions. The combination generally yields a higher prediction rate than branch-specific counters alone. There is always a question of how much correlation to use and recent studies have reported that some programs benefit from higher levels of correlation than others.In our preliminary studies, we have made the following observation about the nature of branch behaviour: although it is true that most of the branches are correlated with previously executed branches, the actual number of branch outcomes they depend on varies strongly from one branch to another.This thesis presents the Elastic History Buffer, an effective scheme that can exploit the property that each branch instruction may have a different degree of correlation with other branches, while keeping the simple structure of a single global branch history. (Abstract shortened by UMI.