US6014742A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Trace branch prediction unit
Assignee: Intel Corp
•
Filing: 1997-12-31
•
Granted: 2000-01-11
•
Expires: 2017-12-31
Abstract
Abstract A trace branch prediction unit includes a trace branch target buffer connected to a trace cache. The trace cache stores traces of micro-ops, with the micro-ops being stored non-sequentially. The trace branch target buffer generally reads a buffer entry corresponding to a particular trace line one clock cycle before the trace line is read to a processor. Using the entry, the trace branch target buffer predicts whether the trace cache should follow the existing trace or leave the trace. If the trace branch target buffer predicts that the trace cache should leave a trace, the trace branch target buffer provides a target address for a new trace. The trace branch target buffer also predicts when a trace is ending and provides a target address for the next trace.
Inventors
- 👤 Robert Franklin Krick
- 👤 Chan Woo Lee
- 👤 Reynold Viriato D'Sa
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 00:26
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F9/3808; G06F9/3836; G06F9/3842; G06F9/3848
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
92 words
A branch target buffer for a trace cache, comprising: a target buffer array, the target buffer array storing a plurality of TBTB entries; and a target buffer data path, the target buffer data path receiving one of the TBTB entries, the one of the TBTB entries corresponding to at least one micro-op contained in the trace cache and containing information about a branch in the at least one micro-op, the buffer data path using the TBTB entry to predict one of a Trace Leave and a Not Trace Leave for the branch.
Claim 2
Dependent Claim
92 words
A branch target buffer for a trace cache, comprising: a target buffer array, the target buffer array storing a plurality of TBTB entries; and a target buffer data path, the target buffer data path receiving one of the TBTB entries, the one of the TBTB entries corresponding to at least one micro-op contained in the trace cache and containing information about a branch in the at least one micro-op, the buffer data path using the TBTB entry to predict one of a Trace Leave and a Not Trace Leave for the branch.
Claim 3
Dependent Claim
55 words
The branch target buffer according to claim 1, further comprising a head target buffer, the head target buffer receiving a head TBTB entry corresponding to a first line of a trace and predicting one of the Trace Leave and the Not Trace Leave for the first line of a trace using the head TBTB entry.
Claim 4
Dependent Claim
48 words
The branch target buffer according to claim 2, wherein the head target buffer both receives the head TBTB entry and predicts one of the Trace Leave and the Not Trace Leave in an amount of time less than an amount of time required to access the trace cache.
Claim 5
Dependent Claim
47 words
The branch target buffer according to claim 2, wherein when one of the target buffer data path and the head target buffer predicts the Trace Leave, one of the target buffer data path and the head target buffer sends a target address to the target buffer array.
Claim 6
Dependent Claim
136 words
A trace cache unit, comprising: a trace cache array adapted to store instruction traces, each of the instruction traces organized into at least one trace line, each of the trace lines including at least one micro-op; and a trace branch target buffer, the trace branch target buffer including: a buffer array, the buffer array storing a plurality of TBTB entries, the TBTB entries being indexed according to the micro-ops of the trace lines; and a buffer data path, the buffer data path receiving a first TBTB entry, the first TBTB entry corresponding to a first micro-op of a selected trace line and containing information about a branch of the first micro-op, the buffer data path using the first TBTB entry to predict one of a Trace Leave and a Not Trace Leave for the first micro-op.
Claim 7
Dependent Claim
136 words
A trace cache unit, comprising: a trace cache array adapted to store instruction traces, each of the instruction traces organized into at least one trace line, each of the trace lines including at least one micro-op; and a trace branch target buffer, the trace branch target buffer including: a buffer array, the buffer array storing a plurality of TBTB entries, the TBTB entries being indexed according to the micro-ops of the trace lines; and a buffer data path, the buffer data path receiving a first TBTB entry, the first TBTB entry corresponding to a first micro-op of a selected trace line and containing information about a branch of the first micro-op, the buffer data path using the first TBTB entry to predict one of a Trace Leave and a Not Trace Leave for the first micro-op.
Claim 8
Dependent Claim
118 words
The trace cache unit according to claim 5, the buffer data path receiving a plurality of TBTB entries corresponding to a plurality of branching micro-ops of the selected trace line and containing information about branches of the branching micro-ops, the plurality of TBTB entries including the first TBTB entry and the plurality of micro-ops including the first micro-op, the buffer data path using the plurality of TBTB entries to predict one of the Trace Leave and the Not Trace Leave for each of the branching micro-ops; wherein when the buffer data path predicts the Trace leave for at least two of the branching micro-ops, the buffer data path orders the branching micro-ops to determine a first Trace Leave.
Claim 9
Dependent Claim
65 words
The trace cache unit according to claim 5, wherein the trace branch target buffer further includes a head trace branch target buffer, the head trace branch target buffer receiving a head TBTB entry corresponding to a first line of a trace and predicting one of a Trace Leave and a Not Trace Leave for the first line of a trace using the head TBTB entry.
Claim 10
Dependent Claim
49 words
The trace cache unit according to claim 7, wherein the head trace branch target buffer, in an amount of time less than an amount of time required to access the trace cache, receives the head TBTB entry and predicts one of the Trace Leave and the Not Trace Leave.
Claim 11
Dependent Claim
49 words
The trace cache unit according to claim 7, wherein when one of the buffer data path and the head trace branch target buffer predicts a Trace Leave, one of the buffer data path and the head trace branch target buffer sends a target address to the trace cache array.
Claim 12
Independent Claim
102 words
A method for branch prediction in a trace cache, the trace cache storing traces of micro-ops, the traces organized into trace lines, each of the trace lines containing at least one micro-op, the trace cache connected to a trace branch target buffer containing a buffer array, the buffer array storing a plurality of TBTB entries corresponding to the micro-ops, comprising the steps of: looking up a first TBTB entry corresponding to a first branching micro-op of a selected trace line; and predicting one of a Trace Leave and a Not Trace Leave for the first branching micro-op using the first TBTB entry.
Claim 13
Independent Claim
102 words
A method for branch prediction in a trace cache, the trace cache storing traces of micro-ops, the traces organized into trace lines, each of the trace lines containing at least one micro-op, the trace cache connected to a trace branch target buffer containing a buffer array, the buffer array storing a plurality of TBTB entries corresponding to the micro-ops, comprising the steps of: looking up a first TBTB entry corresponding to a first branching micro-op of a selected trace line; and predicting one of a Trace Leave and a Not Trace Leave for the first branching micro-op using the first TBTB entry.
Claim 14
Dependent Claim
48 words
The method according to claim 10, further comprising, when the Trace Leave is predicted, the steps of: sending a mask to the trace cache to invalidate any micro-ops of the selected trace line located after the first branching micro-op; and sending a target address to the trace cache.
Claim 15
Dependent Claim
116 words
The method according to claim 10, further comprising the steps of: looking up a second TBTB entry corresponding to a second branching micro-op of the selected trace line; and predicting one of the Trace Leave and the Not Trace Leave for the second branching micro-op using the second TBTB entry, wherein the above two steps are performed while the steps of looking up and predicting on the first branching micro-op are performed; and ordering the first and second branching micro-ops when the Trace Leave is predicted for the first and second branching micro-ops to determine a first Trace Leave predicted micro-op, the first Trace Leave predicted micro-op being one of the first and second branching micro-ops.
Claim 16
Dependent Claim
44 words
The method according to claim 12, further comprising the steps of: sending a mask to the trace cache to invalidate any micro-ops of the selected trace line located after the first Trace Leave predicted micro-op; and sending a target address to the trace cache.
Claim 17
Dependent Claim
154 words
The method according to claim 10, the TBTB entries including build predictions, each of the build predictions being one of a taken prediction and a not taken prediction, wherein the step of predicting one of a Trace Leave and a Not Trace Leave includes the substeps of: making a computed prediction on the first branching micro-op, the computed prediction being one of the taken prediction and the not taken prediction; comparing the computed prediction with the build prediction of the first branching micro-op; and predicting a Trace Leave when the computed prediction does not match the build prediction and a Not Trace Leave when the computed prediction matches the build prediction; and wherein the step of sending a target address to the trace cache includes sending a taken target address when the computed prediction is the taken prediction and sending a not taken target address when the computed prediction is a not taken prediction.
Claim 18
Dependent Claim
59 words
The method according to claim 10, the selected trace line including a trace head, further comprising, when the Trace Leave is predicted for the first branching micro-op, the steps of: clearing a next consecutive trace line from a pipeline to the processor; and ignoring any predictions made based on any TBTB entries corresponding to the next consecutive trace line.
Claim 19
Independent Claim
134 words
A method for branch prediction in a trace cache, the trace cache connected to a trace branch target buffer, the trace cache storing traces, the traces organized into trace lines of micro-ops, comprising the steps of: (a) reading a leading trace line from the trace cache to a processor; (b) reading a first following trace line from the trace cache to the processor, the leading trace line and the first following trace line being stored sequentially in the trace cache; and the following steps, which are performed while steps (a) and (b) are performed: (c) reading any TBTB entries corresponding to the first following trace line to the trace branch target buffer; and (d) predicting one of a Trace Leave and a Not Trace Leave for any branch of the first following trace line.
Claim 20
Independent Claim
134 words
A method for branch prediction in a trace cache, the trace cache connected to a trace branch target buffer, the trace cache storing traces, the traces organized into trace lines of micro-ops, comprising the steps of: (a) reading a leading trace line from the trace cache to a processor; (b) reading a first following trace line from the trace cache to the processor, the leading trace line and the first following trace line being stored sequentially in the trace cache; and the following steps, which are performed while steps (a) and (b) are performed: (c) reading any TBTB entries corresponding to the first following trace line to the trace branch target buffer; and (d) predicting one of a Trace Leave and a Not Trace Leave for any branch of the first following trace line.
Claim 21
Dependent Claim
110 words
The method according to claim 16, further comprising, when the Not Trace Leave is predicted for the first following trace line, the steps of: (e) reading a second following trace line from the trace cache to the processor; and the following steps, which are performed while steps (b) and (e) are performed: (f) reading any TBTB entries corresponding to the second following trace line to the trace branch target buffer, the first following trace line and the second following trace line being stored sequentially in the trace cache; and (g) predicting one of the Trace Leave and the Not Trace Leave for any branch of the second following trace line.
Claim 22
Dependent Claim
73 words
The method according to claim 16, further comprising, when the Trace Leave is predicted for a branching micro-op of the first following trace line, the following steps: (e) sending a mask from the trace branch target buffer to the processor to invalidate any micro-ops of the first following trace line that are stored after the branching micro-op; and (f) sending a target address from the trace branch target buffer to the trace cache.
Claim 23
Dependent Claim
124 words
The method according to claim 18, wherein step (d) includes the substeps of: (1) making a computed prediction on the branch, the computed prediction being one of a taken prediction and a not taken prediction; (2) comparing the computed prediction with a historical prediction of the branch, the historical prediction being one of the taken prediction and the not taken prediction; and (3) predicting a Trace Leave when the computed prediction does not match the historical prediction and a Not Trace Leave when the computed prediction matches the historical prediction; and wherein step (f) includes sending a taken target address when the computed prediction is the taken prediction and sending a not taken target address when the computed prediction is the not taken prediction.
Claim 24
Dependent Claim
67 words
The method according to claim 16, the leading trace line including a trace head, further comprising the following steps, which are performed while steps (a) and (b) are performed: (e) reading any TBTB entries corresponding to the leading trace line to the trace branch target buffer; and (f) predicting one of the Trace Leave and the Not Trace Leave for any branch of the leading trace line.
Claim 25
Dependent Claim
76 words
The method according to claim 20, further comprising, when the Trace Leave is predicted for any branch of the leading trace line, the steps of: (g) sending a mask from the trace branch target buffer to the processor to invalidate all micro-ops of the first following trace line; and (h) sending a mask from the trace branch target buffer to the processor to invalidate any micro-ops following a last branching micro-op of the leading trace line.
Claim 26
Dependent Claim
45 words
The method according to claim 16, further comprising the steps of: (e) recognizing whether the first following trace line is a last line of a trace; and (f) predicting a Trace End when the first following trace line is the last line of a trace.
Claim 27
Dependent Claim
43 words
The method according to claim 22, further comprising the steps of: (g) predicting a target address for a new trace when the first following trace line is the last line of a trace; and (i) sending the target address to the trace cache.
Claim 28
Independent Claim
118 words
A method for branch prediction in a trace cache, the trace cache connected to a trace branch target buffer, the trace cache storing traces, the traces organized into trace lines containing micro-ops, the trace branch target buffer including a head trace branch target buffer, comprising the steps of: (a) reading a leading trace line from the trace cache to a processor; (b) the following steps, which are performed while step (a) is performed: (1) reading any head TBTB entries corresponding to the leading trace line to the head trace branch target buffer; and (2) predicting one of a Trace Leave and a Not Trace Leave for any branch of the leading trace line using the head TBTB entry.
Claim 29
Independent Claim
118 words
A method for branch prediction in a trace cache, the trace cache connected to a trace branch target buffer, the trace cache storing traces, the traces organized into trace lines containing micro-ops, the trace branch target buffer including a head trace branch target buffer, comprising the steps of: (a) reading a leading trace line from the trace cache to a processor; (b) the following steps, which are performed while step (a) is performed: (1) reading any head TBTB entries corresponding to the leading trace line to the head trace branch target buffer; and (2) predicting one of a Trace Leave and a Not Trace Leave for any branch of the leading trace line using the head TBTB entry.
Claim 30
Dependent Claim
85 words
The method according to claim 24, further comprising the steps of: (c) reading any TBTB entries corresponding to a first following trace line to the trace branch target buffer while step (a) is performed; and when the Not Trace Leave is predicted for each branch of the leading trace line, the following steps: (d) reading the first following trace line to the processor; and (e) predicting one of the Trace Leave and the Not Trace Leave for any branch of the first following trace line.
Claim 31
Dependent Claim
83 words
The method according to claim 24, further comprising the steps of: (c) reading any TBTB entries corresponding to a first following trace line to the trace branch target buffer while step (a) is performed; and when the Trace Leave is predicted for any branch of the leading trace line, the following steps: (d) ignoring any predictions based on TBTB entries corresponding to the first following trace line; and (e) sending a target address from the trace branch target buffer to the trace cache.
References Cited (Backward Citations)
US5381533A
Cited
US5742804A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-10 | 2003-07-12 | 2004-01-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-10 | 2007-07-12 | 2008-01-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-10 | 2011-07-12 | 2012-01-11 | $7700.00 | Window Closed / Lapsed |