US6018786A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Trace based instruction caching
Assignee: Intel Corp
•
Filing: 1997-10-23
•
Granted: 2000-01-25
•
Expires: 2017-10-23
Abstract
Abstract A cache memory is constituted with a data array and control logic. The data array includes a number of data lines, and the control logic operates to store a number of trace segments of instructions in the data lines, including trace segments that span multiple data lines. In one embodiment, each trace segment includes one or more trace segment members having one or more instructions, with each trace segment member occupying one data line, and the data lines of a multi-line trace segment being sequentially associated (logically). Retrieval of the trace segment members of a multi-line trace segment is accomplished by first locating the data line storing the first trace segment member of the trace segment, and then successively locating the remaining data lines storing the remaining trace segment members based on the data lines' logical sequential associations.
Inventors
- 👤 Robert F. Krick
- 👤 Glenn J. Hinton
- 👤 Michael D. Upton
- 👤 David J. Sager
- 👤 Chan W. Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 10:53
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3808; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0875; G06F9/3836; G06F9/3854; G06F9/3858
Claims Analysis
Total Claims: 54
Claim 1
Independent Claim
62 words
An apparatus comprising: a) a data array having a plurality of data lines; and b) control logic coupled to the data array to store a plurality of trace segments of instructions into the data lines, including trace segments that span multiple data lines, and to locate each of the multiple data lines spanning trace segments by address matching a single location address.
Claim 2
Independent Claim
62 words
An apparatus comprising: a) a data array having a plurality of data lines; and b) control logic coupled to the data array to store a plurality of trace segments of instructions into the data lines, including trace segments that span multiple data lines, and to locate each of the multiple data lines spanning trace segments by address matching a single location address.
Claim 3
Dependent Claim
58 words
The apparatus as set forth in claim 1, wherein the control logic operates to constitute each trace segment with trace segment members having one or more instructions, and store each trace segment member in a data line; and the control logic further operates to sequentially associate the data lines of a multi-line trace segment in a logical manner.
Claim 4
Dependent Claim
84 words
The apparatus as set forth in claim 1, wherein the control logic operates to retrieve trace segment members of a multi-line trace segment by first locating the data line storing a first trace segment member of the multi-line trace segment and retrieving the first trace segment member, and then successively locating the remaining data lines storing remaining trace segment members based on logical sequential associations of the data lines, and retrieving the remaining trace segment members as the data lines they occupy are located.
Claim 5
Dependent Claim
44 words
The apparatus as set forth in claim 3, wherein the control logic operates to maintain addresses associated with the data lines storing the first trace segment members of the trace segments to facilitate said locating the first trace segment members of the trace segments.
Claim 6
Dependent Claim
67 words
The apparatus as set forth in claim 4, wherein the apparatus further includes at least partial content address matching circuitry, and the control logic being also coupled to the at least partial content address matching circuitry operates to at least partial content address match the maintained associated addresses with an access address to locate the data line storing a first trace segment member of a trace segment.
Claim 7
Dependent Claim
71 words
The apparatus as set forth in claim 5, wherein the control logic operates to partial content address match the maintained associated addresses with the access address to locate the data line storing a first trace segment member of a trace segment; and the control logic further operates to validate the first trace segment member stored in a partially matching data line is indeed the correct first trace segment member being sought.
Claim 8
Dependent Claim
46 words
The apparatus as set forth in claim 1, wherein the control logic operates to maintain at least partial control information for each data line of a multi-line trace segment to sequentially associate the data line with its successor data lines in a logical manner, where applicable.
Claim 9
Dependent Claim
56 words
The apparatus as set forth in claim 7, wherein the data lines are organized into N ways of S sets; and the control logic operates to maintain a next way index for each data line of the multi-line trace segment, except the last data line, to index a way location of an immediate successor data line.
Claim 10
Dependent Claim
50 words
The apparatus as set forth in claim 7, wherein the data lines are organized into N ways of S sets; and the control logic operates to store successive trace segment members of a multi-line trace segment into successive data lines, maintaining a predetermined set relationship between the successive data lines.
Claim 11
Dependent Claim
56 words
The apparatus as set forth in claim 7, wherein the data lines are organized into N ways of S sets; and the control logic operates to maintain a next set index for each data line of the multi-line trace segment, except the last data line, to index a set location of an immediate successor data line.
Claim 12
Dependent Claim
46 words
The apparatus as set forth in claim 1, wherein the control logic operates to maintain at least partial control information for each data line of a multi-line trace segment to sequentially associate the data line with its predecessor data lines in a logical manner, where applicable.
Claim 13
Dependent Claim
56 words
The apparatus as set forth in claim 11, wherein the data lines are organized into N ways of S sets; and the control logic operates to maintain a previous way index for each data line of the multi-line trace segment, except the first data line, to index a way location of an immediate predecessor data line.
Claim 14
Dependent Claim
37 words
The apparatus as set forth in claim 1, wherein the control logic further operates to maintain one or more control information associated with all or selected ones of the data lines to optimize performance of said apparatus.
Claim 15
Dependent Claim
36 words
The apparatus as set forth in claim 13, wherein the control logic further operates to maintain a next instruction pointer for a data line having the last trace segment member of a trace segment stored therein.
Claim 16
Dependent Claim
31 words
The apparatus as set forth in claim 13, wherein the control logic further operates to maintain a next instruction pointer for each data line having a trace segment member stored therein.
Claim 17
Dependent Claim
38 words
The apparatus as set forth in claim 13, wherein the control logic further operates to maintain a first trace segment member indicator for each data line having the first trace segment member of a trace segment stored therein.
Claim 18
Dependent Claim
38 words
The apparatus as set forth in claim 13, wherein the control logic further operates to maintain a last trace segment member indicator for each data line having the last trace segment member of a trace segment stored therein.
Claim 19
Dependent Claim
30 words
The apparatus as set forth in claim 13, wherein the control logic further operates to maintain a micro-op pointer for each data line having a trace segment member stored therein.
Claim 20
Dependent Claim
26 words
The apparatus as set forth in claim 13, wherein the control logic further operates to maintain a branch target address for a data line, where applicable.
Claim 21
Dependent Claim
49 words
The apparatus as set forth in claim 1, wherein the control logic operates to terminate storing of instructions of a trace segment in one data line, and continues storing of instructions of the trace segment in another data line, in accordance with a plurality of data line terminating conditions.
Claim 22
Dependent Claim
40 words
The apparatus as set forth in claim 20, wherein the data line terminating conditions include a condition of encountering a complex macro-instruction that decodes into at least M micro-ops, where M is equal to or greater than a predetermined maximum.
Claim 23
Dependent Claim
38 words
The apparatus as set forth in claim 20, wherein the data line terminating conditions include a condition of encountering a conditional branch micro-op, after a predetermined maximum limit for conditional branch micro-ops per trace segment has been reached.
Claim 24
Dependent Claim
47 words
The apparatus as set forth in claim 1, wherein the control logic operates to terminate storing of instructions as members of a current trace segment, and continues storing of instructions as members of a new trace segment, in accordance with a plurality of trace segment terminating conditions.
Claim 25
Dependent Claim
23 words
The apparatus as set forth in claim 23, wherein the trace segment terminating conditions include a condition of encountering an indirect branch macro-instruction.
Claim 26
Dependent Claim
34 words
The apparatus as set forth in claim 23, wherein the data line terminating conditions include a condition of encountering an instruction, after a predetermined maximum limit for instructions per trace segment has been reached.
Claim 27
Dependent Claim
35 words
The apparatus as set forth in claim 1, wherein the apparatus further comprises a plurality of buffers for building up trace segment members along a predicted execution direction before storing them into the data lines.
Claim 28
Dependent Claim
41 words
The apparatus as set forth in claim 1, wherein the apparatus further comprises an immediate extractor coupled to the data array for extracting a branch instruction pointer associated with a data line whose contents are being output by the data array.
Claim 29
Dependent Claim
59 words
The apparatus as set forth in claim 1, wherein the apparatus further comprises (c) a tag array having a plurality of corresponding tag entries of the data lines, and coupled to the control logic; and the control logic operates to store control information into the tag entries to facilitate storing and retrieving trace segment members of the trace segments.
Claim 30
Independent Claim
130 words
A method for caching instructions comprising: a) storing first one or more instructions in a first data line as a first trace segment member of a trace segment; b) storing address information in association with the first data line containing the first trace segment member, to facilitate location of the first data line and retrieval of the first trace segment member; c) storing second one or more instructions in a second data line as a second trace segment member of the trace segment; and d) storing at least partial control information other than address information in association with said first data line about the second data line to facilitate location of the second data line and retrieval of the second trace segment member upon locating the first trace segment member.
Claim 31
Independent Claim
130 words
A method for caching instructions comprising: a) storing first one or more instructions in a first data line as a first trace segment member of a trace segment; b) storing address information in association with the first data line containing the first trace segment member, to facilitate location of the first data line and retrieval of the first trace segment member; c) storing second one or more instructions in a second data line as a second trace segment member of the trace segment; and d) storing at least partial control information other than address information in association with said first data line about the second data line to facilitate location of the second data line and retrieval of the second trace segment member upon locating the first trace segment member.
Claim 32
Dependent Claim
82 words
The method as set forth in claim 29, wherein the method further comprises: d) storing third one or more instructions in a third data line as a third trace segment member of the trace segment; and e) storing at least partial control information other than address information in association with the second data line about the third data line to facilitate location of the third data line and retrieval of the third trace segment member upon retrieving the second trace segment member.
Claim 33
Dependent Claim
27 words
The method as set forth in claim 30, wherein each of (a), (b) and (d) is terminated in accordance with a plurality of data line terminating conditions.
Claim 34
Dependent Claim
35 words
The method as set forth in claim 30, wherein each of (a), (b) and (d) includes building the first/second/third data line in a buffer for building up trace segment members along a predicted execution direction.
Claim 35
Independent Claim
130 words
A method for caching instructions comprising: a) locating a first data line storing a first trace segment member of a trace segment by address matching an access address against location addresses maintained in association with first trace segment members of trace segments; b) retrieving the first trace segment member and first at least partial control information other than address information about a second data line storing a second trace segment member of the trace segment, the at least partial control information being maintained in association with the first data line; and c) locating the second data line without address matching, and retrieving the second trace segment member relying at least in part on the retrieved first at least partial control information other than address information about the second data line.
Claim 36
Independent Claim
130 words
A method for caching instructions comprising: a) locating a first data line storing a first trace segment member of a trace segment by address matching an access address against location addresses maintained in association with first trace segment members of trace segments; b) retrieving the first trace segment member and first at least partial control information other than address information about a second data line storing a second trace segment member of the trace segment, the at least partial control information being maintained in association with the first data line; and c) locating the second data line without address matching, and retrieving the second trace segment member relying at least in part on the retrieved first at least partial control information other than address information about the second data line.
Claim 37
Dependent Claim
87 words
The method as set forth in claim 33, wherein (c) further includes retrieving second at least partial control information about a third data line storing a third trace segment member of the trace segment, the second at least partial control information being maintained in association with the second data line; and the method further comprises (d) locating the third data line, and retrieving the third trace segment member relying at least in part on the retrieved second at least partial control information about the third data line.
Claim 38
Dependent Claim
28 words
The method as set forth in claim 34, wherein one or more of (b), (c) and (d) further include retrieving micro-ops of a macro-instruction from a microcode sequencer.
Claim 39
Dependent Claim
68 words
The method as set forth in claim 33, wherein (c) includes accessing a way of a set of data lines of a data array, where the way of the set is indexed by a way index of the retrieved first at least partial control information about the second data line, and the set is governed by a predetermined set relationship between the first and the second data lines.
Claim 40
Dependent Claim
56 words
The method as set forth in claim 33, wherein step (c) includes accessing a way of a set of data lines of a data array, where the way and the set are indexed by a way index and a set index of the retrieved first at least partial control information about the second data line respectively.
Claim 41
Dependent Claim
49 words
The method as set forth in claim 33, wherein said address matching of (a) is performed with corresponding address bit subsets of the access address and the location addresses maintained, and (a) further includes validating whether a matching data line indeed contains the first trace segment member being sought.
Claim 42
Dependent Claim
83 words
A cache-memory apparatus comprising: a) a first state machine to operate the cache-memory apparatus in an execution mode, wherein trace segment members of trace segments of instructions stored in a plurality of data lines are looked up and output; and b) a second state machine that is separate and distinct from the first state machine to operate the cache-memory apparatus in a trace segment build mode wherein trace segment members of trace segments of instructions are built and stored into the data lines.
Claim 43
Dependent Claim
83 words
A cache-memory apparatus comprising: a) a first state machine to operate the cache-memory apparatus in an execution mode, wherein trace segment members of trace segments of instructions stored in a plurality of data lines are looked up and output; and b) a second state machine that is separate and distinct from the first state machine to operate the cache-memory apparatus in a trace segment build mode wherein trace segment members of trace segments of instructions are built and stored into the data lines.
Claim 44
Dependent Claim
68 words
The cache-memory apparatus as set forth in claim 39, wherein when operating the cache-memory apparatus in the execution mode, the first state machine operates the cache-memory apparatus in one of a plurality of states including a trace segment head lookup state, a trace segment body lookup state, and a trace segment tail lookup state, for looking up trace segment heads, trace segment bodies, and trace segment tails respectively.
Claim 45
Dependent Claim
32 words
The cache-memory apparatus as set forth in claim 40, wherein the plurality of states further include a microcode sequencer lookup state for retrieving micro-ops of a macro instruction from a microcode sequencer.
Claim 46
Dependent Claim
69 words
The cache-memory apparatus as set forth in claim 39, wherein when operating the cache memory apparatus in the trace segment build mode, the second state machine operates the cache-memory apparatus in one of a plurality of states including a fill buffer transfer state for transferring a trace segment member from a fill buffer into a data array, the first trace segment member being built along a predicted execution direction.
Claim 47
Dependent Claim
72 words
A processor comprising: a) an execution unit; b) a cache memory coupled to the execution unit, the cache memory including a data array having a plurality of data lines, and control logic to store a plurality of trace segments of instructions into the data lines, including trace segments that span multiple data lines, and to locate each of the multiple data lines spanning trace segments by address matching a single location address.
Claim 48
Dependent Claim
72 words
A processor comprising: a) an execution unit; b) a cache memory coupled to the execution unit, the cache memory including a data array having a plurality of data lines, and control logic to store a plurality of trace segments of instructions into the data lines, including trace segments that span multiple data lines, and to locate each of the multiple data lines spanning trace segments by address matching a single location address.
Claim 49
Dependent Claim
73 words
A computer system comprising: a) a processor including a cache memory having a data array with a plurality of data lines, and control logic to store a plurality of trace segments of instructions into the data lines, including trace segments that span multiple data lines, and to locate each of the multiple data lines spanning trace segments by address matching a single location address; and b) an input/output component coupled to the processor.
Claim 50
Dependent Claim
73 words
A computer system comprising: a) a processor including a cache memory having a data array with a plurality of data lines, and control logic to store a plurality of trace segments of instructions into the data lines, including trace segments that span multiple data lines, and to locate each of the multiple data lines spanning trace segments by address matching a single location address; and b) an input/output component coupled to the processor.
Claim 51
Dependent Claim
98 words
A processor comprising: a) an execution unit; and b) a cache memory coupled to the execution unit, the cache memory having a first state machine to operate the cache memory in an execution mode, wherein trace segment members of trace segments of instructions stored in a plurality of data lines are looked up and output, and a second state machine that is separate and distinct from the first state machine to operate the cache memory in a trace segment build mode wherein trace segment members of trace segments of instructions are built and stored into the data lines.
Claim 52
Dependent Claim
98 words
A processor comprising: a) an execution unit; and b) a cache memory coupled to the execution unit, the cache memory having a first state machine to operate the cache memory in an execution mode, wherein trace segment members of trace segments of instructions stored in a plurality of data lines are looked up and output, and a second state machine that is separate and distinct from the first state machine to operate the cache memory in a trace segment build mode wherein trace segment members of trace segments of instructions are built and stored into the data lines.
Claim 53
Dependent Claim
98 words
A computer system comprising: a) a processor including a cache memory having a first state machine to operate the cache memory in an execution mode, wherein trace segment members of trace segments of instructions stored in a plurality of data lines are looked up and output, and a second state machine that is separate and distinct from the first state machine to operate the cache memory in a trace segment build mode wherein trace segment members of trace segments of instructions are built and stored into the data lines; and b) an input/output component coupled to the processor.
Claim 54
Dependent Claim
98 words
A computer system comprising: a) a processor including a cache memory having a first state machine to operate the cache memory in an execution mode, wherein trace segment members of trace segments of instructions stored in a plurality of data lines are looked up and output, and a second state machine that is separate and distinct from the first state machine to operate the cache memory in a trace segment build mode wherein trace segment members of trace segments of instructions are built and stored into the data lines; and b) an input/output component coupled to the processor.
References Cited (Backward Citations)
US5381533A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-24 | 2003-07-26 | 2004-01-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-24 | 2007-07-26 | 2008-01-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-24 | 2011-07-26 | 2012-01-25 | $7700.00 | Window Closed / Lapsed |