BRANCH HISTORY GUIDED INSTRUCTION/DATA PREFETCHING

A mechanism is described that prefetches instructions and data into the cache using a branch instruction as a prefetch trigger. The prefetch is initiated if the predicted execution path after the branch instruction matches the previously seen execution path. This match of the execution paths is determined using a branch history queue that records the branch outcomes (taken/not taken) of the branches in the program. For each branch in this queue, a branch history mask records the outcomes of the next N branches and serves as an encoding of the execution path following the branch instruction. The branch instruction along with the mask is associated with a prefetch address (instruction or data address) and is used for triggering prefetches in the future when the branch is executed again. A mechanism is also described to improve the timeliness of a prefetch by suitably adjusting the value of N after observing the usefulness of the prefetched instructions or data.