Patent US5909573A successfully refreshed from Google Patents.
US5909573A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of branch prediction using loop counters
Assignee: Intel Corp
•
Filing: 1996-03-28
•
Granted: 1999-06-01
•
Expires: 2016-03-28
Abstract
Abstract To increase the efficiency of a pipelined microprocessor, branch prediction is often implemented. Many branch instructions are used to implement program loops with a fixed number of iterations. To accurately predict the branching behavior of branch instructions used to implement program loops a counter based branch prediction system is suggested. The counter based branch prediction system is based on acquiring a final loop count at run time. The final loop count specifies the number of iterations the loop will perform such that the final loop count is used to predict the branching behavior of the branch instruction used to implement the program loops. Three methods for acquiring a final loop count are proposed. Using the suggested counter-based branch prediction method improves the branch prediction rate of the loop related branch instructions and the overall average prediction rate. As a result, this enables the design of higher performing computer pipelines.
Inventors
- 👤 Gad S. Sheaffer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 09:07
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F9/32; G06F9/322; G06F9/325; G06F9/3836; G06F9/3842; G06F9/3844
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
146 words
A method improving the prediction of branch instructions with program loops in a pipelined computer microprocessor, said microprocessor containing a branch prediction mechanism that predicts which instructions should be fetched after a branch instruction, and said mechanism utilizing a branch target buffer, wherein sad method comprising the steps of: determining a final loop count for a loop based branch instruction, said final loop count comprising a number of loop iterations; storing said final loop count in a branch target buffer; clearing a loop count in said branch target buffer; modifying said loop count when said loop based branch instruction is encountered; comparing said loop count to said final loop count; predicting said loop based branch instruction taken when said loop count does not equal said final loop count; and predicting said loop based branch instruction not taken when said loop count equals said final loop count.
Claim 2
Independent Claim
146 words
A method improving the prediction of branch instructions with program loops in a pipelined computer microprocessor, said microprocessor containing a branch prediction mechanism that predicts which instructions should be fetched after a branch instruction, and said mechanism utilizing a branch target buffer, wherein sad method comprising the steps of: determining a final loop count for a loop based branch instruction, said final loop count comprising a number of loop iterations; storing said final loop count in a branch target buffer; clearing a loop count in said branch target buffer; modifying said loop count when said loop based branch instruction is encountered; comparing said loop count to said final loop count; predicting said loop based branch instruction taken when said loop count does not equal said final loop count; and predicting said loop based branch instruction not taken when said loop count equals said final loop count.
Claim 3
Dependent Claim
25 words
The method as claimed in claim 1 wherein said step of determining a final loop count comprises dynamic run-time determination of said final loop count.
Claim 4
Dependent Claim
28 words
The method as claimed in claim 1 wherein said step of determining a final loop count comprises run-time determination of a memory location containing a final loop count.
Claim 5
Dependent Claim
53 words
The method as claimed in claim 1 wherein said step of determining a final loop count comprises using a hint bit that identifies a branch instruction as implementing a program loop, wherein said hint bit informs the branch target buffer that said branch instruction is best predicted by a counter based prediction scheme.
Claim 6
Dependent Claim
30 words
The method as claimed in claim 1 wherein said step of determining a final loop count comprises identifying a branch instruction as implementing a program loop with a hint instruction.
Claim 7
Dependent Claim
81 words
A branch target buffer for predicting branch instructions, said branch target buffer comprising: a tag address field, said tag address field identifying location of a branch instruction in memory; a target address field, said target address field specifying address that program will branch to if said branch instruction is predicted taken; a final loop count field, said final loop count field containing a number of loop iterations; and a counter field, said counter field storing a current number of loop iterations.
Claim 8
Dependent Claim
81 words
A branch target buffer for predicting branch instructions, said branch target buffer comprising: a tag address field, said tag address field identifying location of a branch instruction in memory; a target address field, said target address field specifying address that program will branch to if said branch instruction is predicted taken; a final loop count field, said final loop count field containing a number of loop iterations; and a counter field, said counter field storing a current number of loop iterations.
Claim 9
Dependent Claim
43 words
The branch target buffer as claimed in claim 6 further comprising: a branch history field, said branch history field storing a history of branch results; and a branch type field, said branch type field specifying if said branch instruction implements a program loop.
References Cited (Backward Citations)
US3551895A
Cited
US4370711A
Cited
US4764861A
Cited
US4882701A
Cited
JPS62114034A
Cited
US5297281A
Cited
US5367703A
Cited
US5584001A
Cited
US5758142A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-31 | 2002-11-30 | 2003-06-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-31 | 2006-11-30 | 2007-06-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-31 | 2010-11-30 | 2011-06-01 | $7700.00 | Window Closed / Lapsed |