The FAB predictor: using Fourier analysis to predict the outcome of conditional branches

This paper proposes to transform the branch outcome history from the time domain to the frequency domain. With our proposed Fourier Analysis Branch (FAB) predictor, we can represent long periodic branch history patterns - as long as 2¹³ bits - with a realistic number of bits (52 bits). We evaluate the potential gains of the FAB predictor by considering a hybrid branch predictor in which each branch is predicted using a static scheme, the 2-bit dynamic scheme, the PAp and GAp schemes, and our FAB predictor. By including our FAB predictor in the hybrid predictor, it is possible to cut the misprediction rate of integer applications in the SPEC95 suite by between 5 and 50% with an average of 20%. Besides evaluating its performance, this paper shows some key properties of our FAB predictor and presents some possible implementation approaches.