Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-02-18
2003-09-16
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06622241
ABSTRACT:
TECHNICAL FIELD
The technical field is computer architectures that use branch prediction as a means to improve processing performance.
BACKGROUND
Modern microprocessors frequently use long pipelines to process instructions. A side effect of these long pipelines is an increase in the penalty for branches, which must redirect the instruction sequence. Usually, this branching behavior requires flushing at least a portion of the pipeline, thereby degrading pipeline performance. Branch prediction structures are commonly implemented in hardware to mitigate this penalty.
A branch prediction structure may predict branch targets and may store the branch target information in a branch prediction table. However, some branch target information that is stored in the branch target structure may be incorrect. These errors may occur because in some cases, only a portion of a target address is stored in the branch prediction table. In these cases, the remainder of the target address is inferred, typically using bits from the current branch instruction address. If this assumption is incorrect, entries in the branch prediction structure can be wasted and/or cause inefficient branch prediction. This incorrect information cannot be used for subsequent branch predictions and so is useless. The presence of this useless information is referred to as branch pollution.
SUMMARY
A comparator compares aliasing bits of a predicted branch target to corresponding bits of a current branch instruction address. The address comparison of the aliasing bits is made to determine if a branch target address is outside of a branch target range for a branch prediction structure. If the aliasing bits match, then assumptions about the branch target address being in a same memory block as the current branch instruction are correct, and the branch prediction is usable. If the aliasing bits do not match, then the branch prediction will be incorrect.
The results of the comparison are stored in a branch resolution table. The branch resolution table stores branches that are in the pipeline but that have not yet retired. When a branch instruction retires, a corresponding branch entry is accessed and a comparison result bit is examined. If the comparison result bit indicates that the branch target did not alias, the branch entry is allowed to update into the branch prediction structure so that future occurrences of the branch can be predicted. Otherwise, the branch entry will not be inserted. Avoiding insertion of the branch entry when the entry would have provided an incorrect branch target saves entry space in the branch prediction structure that can be used for more useful predictions, and potentially prevents additional incorrect predictions that may result from using an incorrect branch target.
In an alternative embodiment, the same comparison result bit flows down the pipeline with the rest of the instruction until retirement of the instruction. At retirement, if the comparison result bit indicates that the aliasing bits match, then the entry is allowed to be inserted into the branch prediction structure.
REFERENCES:
patent: 5721855 (1998-02-01), Hinton et al.
patent: 5812839 (1998-09-01), Hoyts et al.
patent: 5826074 (1998-10-01), Blomgren
patent: 5859999 (1999-01-01), Morris et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 5867698 (1999-02-01), Cumming et al.
Wolfe, A., “Patents shed light on Merced's Innards”, Electronic Engineering Times, Feb. 15, 1999.
Brockmann Russell C.
Fernando Susith R.
Kelly Brian M.
Ellis Richard L.
Hewlett--Packard Development Company, L.P.
LandOfFree
Method and apparatus for reducing branch prediction table... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reducing branch prediction table..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing branch prediction table... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3018386