Johnny K. F. Lee and Alan Jay Smith

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-83-121
August 1983

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-121.pdf

CPU pipelines need a steady flow of instructions in order to function with maximum effectiveness. Branches which change the expected order of instruction execution require that the pipeline be reloaded, resulting in several lost machine cycles per such branch. By examining the type of branch and the past execution behavior of that branch (taken/not taken) it is possible to predict with high accuracy whether the branch will be taken or not taken, and by remembering the previous branch target (destination), to predict the current branch target. In this paper we use a systematic approach to selecting good prediction strategies. Our studies are based on 26 program address traces grouped into four IBM 370 workloads (scientific, commercial compiler, supervisor) and CDC 6400 and DEC PDP-11 workloads. Our results show the effectiveness of various prediction strategies, the number of past branches that should be remembered, the amount of state required for each and the effect of workload and branch type. Improvements of from 5% to 20% can be expected in CPU performance when a branch target buffer is installed. We also consider issues relating to the implementation of real branch target buffers.

BibTeX citation:

@techreport{Lee:CSD-83-121,
    Author = {Lee, Johnny K. F. and Smith, Alan Jay},
    Title = {Analysis of Branch Prediction Strategies and Branch Target Buffer Design},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1983},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/6335.html},
    Number = {UCB/CSD-83-121},
    Abstract = {CPU pipelines need a steady flow of instructions in order to function with maximum effectiveness. Branches which change the expected order of instruction execution require that the pipeline be reloaded, resulting in several lost machine cycles per such branch. By examining the type of branch and the past execution behavior of that branch (taken/not taken) it is possible to predict with high accuracy whether the branch will be taken or not taken, and by remembering the previous branch target (destination), to predict the current branch target. In this paper we use a systematic approach to selecting good prediction strategies. Our studies are based on 26 program address traces grouped into four IBM 370 workloads (scientific, commercial compiler, supervisor) and CDC 6400 and DEC PDP-11 workloads. Our results show the effectiveness of various prediction strategies, the number of past branches that should be remembered, the amount of state required for each and the effect of workload and branch type. Improvements of from 5% to 20% can be expected in CPU performance when a branch target buffer is installed. We also consider issues relating to the implementation of real branch target buffers.}
}

EndNote citation:

%0 Report
%A Lee, Johnny K. F.
%A Smith, Alan Jay
%T Analysis of Branch Prediction Strategies and Branch Target Buffer Design
%I EECS Department, University of California, Berkeley
%D 1983
%@ UCB/CSD-83-121
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/6335.html
%F Lee:CSD-83-121