US 6,560,693 B1 · Branch history guided instruction/data prefetching

Abstract

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.

Claims34

Dependent claims

In a system including a high speed buffer logically coupled between memory and at least one processor unit, a method for prefetching information into the high speed buffer for use in processing an instruction stream by the at least one processor unit, the method comprising the steps of:

dynamically generating first path data during run time, wherein the first path data represents a first path that encompasses a prefetch trigger event and an instruction that uses information prefetched by a prefetch operation associated with the prefetch trigger event;
dynamically generating second path data during run time, wherein the second path data represents a predicted second path of execution;
determining whether the first path data is consistent with the second path data;
and
prefetching instructions and data when the first path data is consistent with the second path data.

2 more elements

In a data processing system including a high speed buffer logically coupled between memory and at least one processor unit, an apparatus for prefetching information into the high speed buffer for use in processing an instruction stream by the at least one processor unit, the apparatus comprising:

prefetch logic for dynamically generating first path data during run time, wherein the first path data represents a first path that encompasses a prefetch trigger event and an instruction that uses information prefetched by a prefetch operation associated with the prefetch trigger event;
branch path prediction logic for dynamically generating second path data during run time, wherein the second path data represents a predicted second path of execution;
and
compare logic determining whether the first path data is consistent with the second path data;
and
prefetch execution logic for prefetching instructions and data when first path data is consistent with the second path data.

3 more elements

Dependencies are inferred from the claim text.

Branch history guided instruction/data prefetching

Life of this patent

Branch history guided instruction/data prefetching

Life of this patent

Abstract

Claims34