US5640526A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Superscaler instruction pipeline having boundary indentification logic for variable length instructions
Assignee: International Business Machines Corp
•
Filing: 1994-12-21
•
Granted: 1997-06-17
•
Expires: 2014-12-21
Abstract
Abstract A mechanism which manages variable length instructions in cache is comprised of three cooperating elements designed to optimize self modifying code and anticipate next instructions for branch operand management. A content addressable memory (CAM) stores addresses of lines which have been accessed for instruction fetching. In a system having modifiable instruction stream (i.e., store to instruction stream), when the CAM matches, the system must retire certain instructions, flush instructions and then fetch the modified instruction stream. Boundary identification logic examines a field in each cache byte to determine the nature of the byte. This field is initially cleared at the time the cache line is loaded and filled with the line is fetched. An anticipation buffer designed to minimize the circuitry necessary for fetches across cache lines is loaded with sequentially anticipated prefetched instructions from the cache. These anticipated instructions can then be concatenated by a fetch aligner.
Inventors
- 👤 Stephen William Mahin
- 👤 Stephen Michael Conor
- 👤 Stephen J. Ciavaglia
- 👤 Lyman Henry Moulton, III
- 👤 Stephen Emery Rich
- 👤 Paul David Kartschoke
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 18:12
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3814; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0877; G06F12/0886; G06F9/30145; G06F9/30149; G06F9/30152; G06F9/3812; G06F9/3816; G06F2212/00; G06F2212/45; G06F2212/452
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
152 words
A cache control unit for an instruction cache, said instruction cache comprising part of an instruction pipe, the cache control unit comprising: a content addressable memory for storing most recent addresses of cache lines which have been accessed for instruction fetching for execution said instructions being of variable length; boundary identification logic connected to said instruction cache for identifying instruction boundaries for each of said plurality of instructions held in said instruction cache; an anticipation buffer for holding a next instruction, said anticipation buffer minimizing circuitry for fetches across cache lines; and an instruction fetch unit, connected to said instruction cache for fetching instructions to be executed, said instruction fetch unit including alignment logic connected to said anticipation buffer and responsive to said boundaries of instructions read from said instruction cache for aligning and appending said next instruction to said instructions held in said instruction cache, without first sequentially decoding said instructions.
Claim 2
Dependent Claim
152 words
A cache control unit for an instruction cache, said instruction cache comprising part of an instruction pipe, the cache control unit comprising: a content addressable memory for storing most recent addresses of cache lines which have been accessed for instruction fetching for execution said instructions being of variable length; boundary identification logic connected to said instruction cache for identifying instruction boundaries for each of said plurality of instructions held in said instruction cache; an anticipation buffer for holding a next instruction, said anticipation buffer minimizing circuitry for fetches across cache lines; and an instruction fetch unit, connected to said instruction cache for fetching instructions to be executed, said instruction fetch unit including alignment logic connected to said anticipation buffer and responsive to said boundaries of instructions read from said instruction cache for aligning and appending said next instruction to said instructions held in said instruction cache, without first sequentially decoding said instructions.
Claim 3
Dependent Claim
68 words
The cache control unit recited in claim 1 further comprising: first logic means connected to said content addressable memory for detecting an occurrence of a store to memory request to one of said instruction addresses; and second logic means responsive to the first logic for delaying the store to memory request until previous instructions are executed and then refetching instructions that follow the store instruction in program order.
Claim 4
Dependent Claim
19 words
A cache control unit as in claim 1 wherein address entries in said content addressable memory are first-in, first-out.
Claim 5
Dependent Claim
29 words
A cache control unit as in claim 3 wherein the number of entries in said content addressable memory is greater than a number of operations in the instruction pipe.
Claim 6
Dependent Claim
34 words
A cache control unit as in claim 4 wherein the content addressable memory includes comparing means for comparing an address of each instruction to be executed against all addresses in the content addressable memory.
Claim 7
Dependent Claim
54 words
A cache control unit as in claim 5 wherein in said comparing means generates a hit output when a match is found between an address of an instruction to be executed and an address in the content addressable memory and further comprising means to register an exception condition when a hit output is generated.
Claim 8
Dependent Claim
38 words
A cache control unit as in claim 1 wherein said boundary identification logic includes means for evaluating boundary fields in each cache byte in said instruction cache and identifying boundaries of variable length instructions in said instruction cache.
Claim 9
Dependent Claim
73 words
The cache control unit recited in claim 7 wherein each line in cache includes a byte with an associated boundary field which provides an indication of the nature of the byte, the boundary field marking the beginning of a variable length instruction and information about the instruction to reduce decode time, said boundary identification logic decoding said boundary field at a time when an instruction stored in an addressed cache line is fetched.
Claim 10
Dependent Claim
33 words
A cache control unit as in claim 1 wherein said next instruction in said anticipation buffer is in a sequence of anticipated prefetched instructions from said instruction cache or a branch target instruction.
Claim 11
Dependent Claim
243 words
A cache control unit for an instruction cache, said instruction cache comprising part of an instruction pipe, the cache control unit comprising: a content addressable memory for storing most recent addresses of cache lines which have been accessed for instruction fetching for execution, said instructions being of variable length; boundary identification logic connected to said instruction cache for identifying instruction boundaries for each of said plurality of instructions held in said instruction cache; an anticipation buffer for holding a next instruction, said anticipation buffer minimizing circuitry for fetches across cache lines; first logic means connected to said content addressable memory for detecting an occurrence of a store to memory request to one of said instruction addresses; and second logic means responsive to the first logic for delaying the store to memory request until previous instructions are executed and then refetching instructions that follow the store instruction in program order, wherein each line in cache includes a byte with an associated boundary field which provides an indication of the nature of the byte, the boundary field marking the beginning of a variable length instruction and information about the instruction to reduce decode time, said boundary identification logic decoding said boundary field at a time when an instruction stored in an address cache line is fetched, wherein the boundary field is a 2-bit field encoded as follows: 00 =NOT A BOUNDARY 01 =INSTRUCTION PREFIX BYTE 10 =COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) 11 =SIMPLE INSTRUCTION BOUNDARY.
Claim 12
Dependent Claim
243 words
A cache control unit for an instruction cache, said instruction cache comprising part of an instruction pipe, the cache control unit comprising: a content addressable memory for storing most recent addresses of cache lines which have been accessed for instruction fetching for execution, said instructions being of variable length; boundary identification logic connected to said instruction cache for identifying instruction boundaries for each of said plurality of instructions held in said instruction cache; an anticipation buffer for holding a next instruction, said anticipation buffer minimizing circuitry for fetches across cache lines; first logic means connected to said content addressable memory for detecting an occurrence of a store to memory request to one of said instruction addresses; and second logic means responsive to the first logic for delaying the store to memory request until previous instructions are executed and then refetching instructions that follow the store instruction in program order, wherein each line in cache includes a byte with an associated boundary field which provides an indication of the nature of the byte, the boundary field marking the beginning of a variable length instruction and information about the instruction to reduce decode time, said boundary identification logic decoding said boundary field at a time when an instruction stored in an address cache line is fetched, wherein the boundary field is a 2-bit field encoded as follows: 00 =NOT A BOUNDARY 01 =INSTRUCTION PREFIX BYTE 10 =COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) 11 =SIMPLE INSTRUCTION BOUNDARY.
Claim 13
Dependent Claim
180 words
A content addressable memory connected to means for detecting a store-to-the instruction-stream event in the execution of self modifying code, said content addressable memory storing most recent addresses of cache lines which have been accessed from an instruction cache for execution, said instruction cache comprising part of an instruction pipe, said content addressable memory storing address entries on a first-in, first-out basis, the number of entries in said content addressable memory being greater than a number of operations in the instruction pipe, said means for detecting including: boundary identification logic connected to said instruction cache for identifying instruction boundaries for each of said plurality of instructions held in said instruction cache; an anticipation buffer for holding a next instruction; and an instruction fetch unit, connected to said instruction cache for fetching instructions to be executed, said instruction fetch unit including alignment logic connected to said anticipation buffer and responsive to said boundaries of instructions read from said instruction cache for aligning and appending said next instruction to said instructions held in said instruction cache, without first sequentially decoding said instructions.
Claim 14
Dependent Claim
180 words
A content addressable memory connected to means for detecting a store-to-the instruction-stream event in the execution of self modifying code, said content addressable memory storing most recent addresses of cache lines which have been accessed from an instruction cache for execution, said instruction cache comprising part of an instruction pipe, said content addressable memory storing address entries on a first-in, first-out basis, the number of entries in said content addressable memory being greater than a number of operations in the instruction pipe, said means for detecting including: boundary identification logic connected to said instruction cache for identifying instruction boundaries for each of said plurality of instructions held in said instruction cache; an anticipation buffer for holding a next instruction; and an instruction fetch unit, connected to said instruction cache for fetching instructions to be executed, said instruction fetch unit including alignment logic connected to said anticipation buffer and responsive to said boundaries of instructions read from said instruction cache for aligning and appending said next instruction to said instructions held in said instruction cache, without first sequentially decoding said instructions.
Claim 15
Dependent Claim
30 words
A content addressable memory as in claim 11 further comprising comparing means for comparing an address of each instruction to be executed against all addresses in the content addressable memory.
Claim 16
Dependent Claim
53 words
A content addressable memory as in 12 wherein in said comparing means generates a hit output when a match is found between an address of an instruction to be executed and an address in the content addressable memory and further comprising means to register an exception condition when a hit output is generated.
Claim 17
Dependent Claim
53 words
A content addressable memory as in 12 wherein in said comparing means generates a hit output when a match is found between an address of an instruction to be executed and an address in the content addressable memory and further comprising means to register an exception condition when a hit output is generated.
Claim 18
Dependent Claim
126 words
A boundary identification logic connected to said content addressable memory for identifying instruction boundaries for each of said plurality of variable length instructions held in an instruction cache, said boundary identification logic including: means for evaluating boundary fields in each cache byte in said instruction cache and identifying boundaries of variable length instructions in said instruction cache; an anticipation buffer for holding a next instruction; and an instruction fetch unit, connected to said instruction cache for fetching instructions to be executed, said instruction fetch unit including alignment logic connected to said anticipation buffer and responsive to said boundaries of instructions read from said instruction cache for aligning and appending said next instruction to said instructions held in said instruction cache, without first sequentially decoding said instructions.
Claim 19
Dependent Claim
126 words
A boundary identification logic connected to said content addressable memory for identifying instruction boundaries for each of said plurality of variable length instructions held in an instruction cache, said boundary identification logic including: means for evaluating boundary fields in each cache byte in said instruction cache and identifying boundaries of variable length instructions in said instruction cache; an anticipation buffer for holding a next instruction; and an instruction fetch unit, connected to said instruction cache for fetching instructions to be executed, said instruction fetch unit including alignment logic connected to said anticipation buffer and responsive to said boundaries of instructions read from said instruction cache for aligning and appending said next instruction to said instructions held in said instruction cache, without first sequentially decoding said instructions.
Claim 20
Dependent Claim
73 words
A boundary identification logic recited in claim 14 wherein each line in cache includes a byte with an associated boundary field which provides an indication of the nature of the byte, the boundary field marking the beginning of a variable length instruction and information about the instruction to reduce decode time, said boundary identification logic decoding said boundary field at a time when an instruction stored in an addressed cache line is fetched.
Claim 21
Dependent Claim
147 words
A boundary identification logic connected to said content addressable memory for identifying instruction boundaries for each of said plurality of variable length instructions field in an instruction cache, said boundary identification logic including means for evaluating boundary fields in each cache byte in said instruction cache and identifying boundaries of variable length instructions in said instruction cache, wherein each line in cache includes a byte with an associated boundary field which provides an indication of the nature of the byte, the boundary field marking the beginning of a variable length instruction and information about the instruction to reduce decode time, said boundary identification logic decoding said boundary field at a time when an instruction stored in an addressed cache line is fetched, wherein the boundary field is a 2-bit field encoded as follows: 00=NOT A BOUNDARY 01=INSTRUCTION PREFIX BYTE 10=COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) 11=SIMPLE INSTRUCTION BOUNDARY.
Claim 22
Dependent Claim
147 words
A boundary identification logic connected to said content addressable memory for identifying instruction boundaries for each of said plurality of variable length instructions field in an instruction cache, said boundary identification logic including means for evaluating boundary fields in each cache byte in said instruction cache and identifying boundaries of variable length instructions in said instruction cache, wherein each line in cache includes a byte with an associated boundary field which provides an indication of the nature of the byte, the boundary field marking the beginning of a variable length instruction and information about the instruction to reduce decode time, said boundary identification logic decoding said boundary field at a time when an instruction stored in an addressed cache line is fetched, wherein the boundary field is a 2-bit field encoded as follows: 00=NOT A BOUNDARY 01=INSTRUCTION PREFIX BYTE 10=COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) 11=SIMPLE INSTRUCTION BOUNDARY.
References Cited (Backward Citations)
US4669043A
Cited
US5051885A
Cited
US5113515A
Cited
US5226130A
Cited
US5500942A
Cited
US5210842A
Cited
US5363495A
Cited
US5285527A
Cited
US5450605A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-06-16 | 2000-12-16 | 2001-06-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-06-16 | 2004-12-16 | 2005-06-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-06-16 | 2008-12-16 | 2009-06-17 | $7700.00 | Window Closed / Lapsed |