Branch prediction

Modern computer processors can start processing an instruction before they're done with the previous one. But what happens when the chip encounters a conditional branch statement (i.e. "if x=0 goto line 20")? This will create a gap in the instruction pipeline, slowing down program execution. One way to fill this gap is to simply guess what instruction will occur next, and start processing it immediately. If the chip guesses wrong, it must retrace and fix the mistake.

Branch prediction schemes

A comparison of several different methods for predicting program flow.

View the:

Paper

This project won 10th place in the 1994 Westinghouse Science Talent Search (now run by Intel):

Franz Edward Boas. (1994) "Properties of branch prediction schemes."

Project advisor: Prof. Michael D. Smith, Division of Engineering and Applied Science, Harvard

Abstract
Pipelined processors operate quickly because they can start processing an instruction before the previous one has been completed. In order to do this, the computer must be able to predict what the next instruction will be before the previous instruction has been processed. Most pipelined processors use the two-bit scheme for program flow prediction. This project introduces the Markov and run-length schemes, and shows that they are more accurate than the two-bit scheme for some programs.

Return to the main page