| next > | ©2001 Harald Bögeholz |
Dynamic means that the prediction for the outcome of a specific branch can change over time, depending on execution history.
Idea: For each branch, remember the previous outcome (taken/not taken). Predict that at the next time it will be the same as last time.
Implementation: use the lower a bits of the branch instruction's address as the index into a table of 2a bits. When a branch is fetched, take its address modulo 2a and look at the corresponding table entry. If 1, predict taken. If 0, predict not taken. Later, when the actual outcome of the branch is determined, update the table bit to reflect it.
Problem: different branches might appear at the same address (mod 2a). But hey, so what? Branch prediction is a heuristic anyway and has no influence on correct results of the program, only on execution time. So we can (and have to) affort to make errors from time to time ...