Branch Target Buffer Preloading (16-Sep-2009)

Branch Target Buffer Preloading

In a microprocessor, an instruction fetcher delivers some number of instructions per clock cycle from the instruction cache. These instructions are known as a fetch group. Given the clock period of modern microprocessors, it often takes several cycles to access the instruction cache. However, this access is pipelined such that the cache latency in clock cycles equals the number of outstanding possible requests. Figure 1 depicts best case instruction flow of fetch groups enumerated A-E through a hypothetical processor with fetcher/cache pipe states IF1-IF3. An address "A" is generated in IF1, the cache is accessed in IF2, and the contents are available for processing in IF3.

IF1 | A | B | C | D | E | | |
IF2 | | A | B | C | D | E | |
IF3 | | | A | B | C | D | E |
Figure 1. Best case instruction flow

For the sake of argument, assume that there is an unconditional branch in fetch group "B" to fetch group "E". Figure 2 depicts fetcher behavior without a BTB or in the case of a BTB miss. Note the bubble after "B" in IF3: the pipe stages which would normally process fetch group "C" must discard "C" as it is not needed. In effect, there is a one cycle bubble in the pipe as the branch redirect in "B" is not visible until IF3.

IF1 | A | B | C | E | | |
IF2 | | A | B | C | E | |
IF3 | | | A | B | | E |
Figure 2. Instruction flow without a BTB

Figure 3 shows what transpires when a BTB hit for fetch group "B" is encountered that indicates there is a redirection to somewhere in "E".

IF1 | A | B | E | | |
IF2 | | A | B | E | |
IF3 | | | A | B | E |
Figure 3. Instruction flow with a BTB

Unfortunately, in order to do this, the branch taken in "B" must already have been encountered previously in IF3. Inserting a hint instruction "x" earlier in one of the fetch groups of the stream that indicates that fetch group "B...