US5644744A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Superscaler instruction pipeline having boundary identification logic for variable length instructions
Assignee: International Business Machines Corp
•
Filing: 1995-05-12
•
Granted: 1997-07-01
•
Expires: 2015-05-12
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-04 07:28
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
167 words
A method of fetching multiple instructions in a pipelined microprocessor for out-of-order instruction execution in microprocessor architectures that permit store to the instruction stream, said method comprising the steps of: storing most recent addresses of cache lines which have been accessed for instruction fetching for execution in a content addressable memory, said instructions being of variable length; logically identifying instruction boundaries for each of said plurality of instructions held in cache; holding a next instruction in an anticipation buffer, said next instruction being located and identified by said identifying step using said content addressable memory; aligning and appending said next instruction to said instructions held in cache, based on said step of logically identifying instruction boundaries, without first sequentially decoding said instructions; detecting an occurrence of a store to memory request to one of said instruction addresses in the content addressable memory; delaying the store to memory request until previous instructions are executed; and then refetching instructions that follow the store to memory request in program order.
Claim 2
Independent Claim
167 words
A method of fetching multiple instructions in a pipelined microprocessor for out-of-order instruction execution in microprocessor architectures that permit store to the instruction stream, said method comprising the steps of: storing most recent addresses of cache lines which have been accessed for instruction fetching for execution in a content addressable memory, said instructions being of variable length; logically identifying instruction boundaries for each of said plurality of instructions held in cache; holding a next instruction in an anticipation buffer, said next instruction being located and identified by said identifying step using said content addressable memory; aligning and appending said next instruction to said instructions held in cache, based on said step of logically identifying instruction boundaries, without first sequentially decoding said instructions; detecting an occurrence of a store to memory request to one of said instruction addresses in the content addressable memory; delaying the store to memory request until previous instructions are executed; and then refetching instructions that follow the store to memory request in program order.
Claim 3
Dependent Claim
47 words
The method as in claim 1, wherein said logically identifying step includes steps of identifying a characteristic of an accessed instruction of said instructions held in cache and storing information of said characteristic of said accessed instruction held in cache in a plurality of instruction boundary fields.
Claim 4
Dependent Claim
52 words
The method as in claim 1, further comprising a step, following said delaying step, of purging said instructions that follow the store to memory request that are being executed when said detecting step detects said occurrence of a store to memory request to addresses indicated by said instruction addresses in the memory.
Claim 5
Dependent Claim
38 words
The method as in claim 1, wherein said detecting step further comprises a step of comparing every active store to memory request with every instruction address in said memory during a machine cycle that had a store request.
Claim 6
Dependent Claim
22 words
A method as in claim 1, further comprising a step of executing at least two of said instructions held in cache simultaneously.
Claim 7
Dependent Claim
38 words
A method as in claim 1, wherein said logically identifying step further comprises: modifying said cache to include an instruction boundary field; and determining a characteristic of said instruction and writing said characteristic in said instruction boundary field.
Claim 8
Independent Claim
219 words
A method of fetching multiple instructions in a pipelined microprocessor for out-of-order instruction execution in microprocessor architectures that permit store to the instruction stream, said method comprising the steps of: storing most recent addresses of cache lines which have been accessed for instruction fetching for execution in a content addressable memory, said instructions being of variable length; logically identifying instruction boundaries for each of said plurality of instructions held in cache; holding a next instruction in an anticipation buffer, said next instruction being located and identified by said identifying step using said content addressable memory; detecting an occurrence of a store to memory request to one of said instruction addresses in the content addressable memory; delaying the store to memory request until previous instructions are executed; and then refetching instructions that follow the store to memory request in program order, wherein said logically identifying step includes steps of identifying a characteristic of each of said instructions held in cache and storing information of said characteristic of each of said instructions held in cache in a plurality of instruction boundary fields, wherein said step of identifying a characteristic includes a step of identifying one of the following characteristics of each of said instructions held in cache: 00=NOT A BOUNDARY 01=INSTRUCTION PREFIX BYTE 10=COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) 11=SIMPLE INSTRUCTION BOUNDARY.
Claim 9
Independent Claim
219 words
A method of fetching multiple instructions in a pipelined microprocessor for out-of-order instruction execution in microprocessor architectures that permit store to the instruction stream, said method comprising the steps of: storing most recent addresses of cache lines which have been accessed for instruction fetching for execution in a content addressable memory, said instructions being of variable length; logically identifying instruction boundaries for each of said plurality of instructions held in cache; holding a next instruction in an anticipation buffer, said next instruction being located and identified by said identifying step using said content addressable memory; detecting an occurrence of a store to memory request to one of said instruction addresses in the content addressable memory; delaying the store to memory request until previous instructions are executed; and then refetching instructions that follow the store to memory request in program order, wherein said logically identifying step includes steps of identifying a characteristic of each of said instructions held in cache and storing information of said characteristic of each of said instructions held in cache in a plurality of instruction boundary fields, wherein said step of identifying a characteristic includes a step of identifying one of the following characteristics of each of said instructions held in cache: 00=NOT A BOUNDARY 01=INSTRUCTION PREFIX BYTE 10=COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) 11=SIMPLE INSTRUCTION BOUNDARY.
Claim 10
Dependent Claim
42 words
The method as in claim 7, further comprising the steps of: performing an instruction having said 11=SIMPLE INSTRUCTION BOUNDARY characteristic in one machine cycle, and performing an instruction having said 10=COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) characteristic in at least two machine cycles.
Claim 11
Independent Claim
155 words
A method of fetching multiple instructions in a pipelined microprocessor for out-of-order instruction execution in microprocessor architectures that permit store to the instruction stream, said method comprising the steps of: storing most recent addresses of cache lines which have been accessed for instruction fetching for execution in a memory; logically identifying instruction boundaries for each of said plurality of instructions held in cache; holding a next instruction in an anticipation buffer, said next instruction being located and identified by said identifying step using said memory; aligning and appending said next instruction to said instructions held in cache, based on said step of logically identifying instruction boundaries, without first sequentially decoding said instructions; detecting an occurrence of a store to memory request to one of said instruction addresses in the memory; delaying the store to memory request until previous instructions are executed; and then refetching instructions that follow the store to memory request in program order.
Claim 12
Independent Claim
155 words
A method of fetching multiple instructions in a pipelined microprocessor for out-of-order instruction execution in microprocessor architectures that permit store to the instruction stream, said method comprising the steps of: storing most recent addresses of cache lines which have been accessed for instruction fetching for execution in a memory; logically identifying instruction boundaries for each of said plurality of instructions held in cache; holding a next instruction in an anticipation buffer, said next instruction being located and identified by said identifying step using said memory; aligning and appending said next instruction to said instructions held in cache, based on said step of logically identifying instruction boundaries, without first sequentially decoding said instructions; detecting an occurrence of a store to memory request to one of said instruction addresses in the memory; delaying the store to memory request until previous instructions are executed; and then refetching instructions that follow the store to memory request in program order.
Claim 13
Dependent Claim
24 words
The method as in claim 9, wherein said storing step comprises a step of storing said most recent addresses in a content addressable memory.
Claim 14
Dependent Claim
13 words
The method as in claim 9, wherein said instructions are of variable length.
Claim 15
Dependent Claim
47 words
The method as in claim 9, wherein said logically identifying step includes steps of identifying a characteristic of an accessed instruction of said instructions held in cache and storing information of said characteristic of said accessed instruction held in cache in a plurality of instruction boundary fields.
Claim 16
Dependent Claim
36 words
A method as in claim 9, wherein said logically identifying step further comprises: modifying said cache to include a boundary field; and determining a characteristic of said instruction and writing said characteristic in said boundary field.
Claim 17
Dependent Claim
52 words
The method as in claim 9, further comprising a step, following said delaying step, of purging said instructions that follow the store to memory request that are being executed when said detecting step detects said occurrence of a store to memory request to addresses indicated by said instruction addresses in the memory.
Claim 18
Dependent Claim
38 words
The method as in claim 9, wherein said detecting step further comprises a step of comparing every active store to memory request with every instruction address in said memory during a machine cycle that had a store request.
Claim 19
Dependent Claim
22 words
A method as in claim 9, further comprising a step of executing at least two of said instructions held in cache simultaneously.
Claim 20
Independent Claim
144 words
A method of fetching multiple instructions in a pipelined microprocessor for out-of-order instruction execution in microprocessor architectures that permit store to the instruction stream, said method comprising the steps of: storing most recent addresses of cache lines which have been accessed for instruction fetching for execution in a memory, detecting an occurrence of a store to memory request to one of said instruction addresses in the memory; delaying the store to memory request until previous instructions are executed; refetching instructions that follow the store to memory request in program order; and logically identifying instruction boundaries for each of said plurality of instructions held in cache, wherein said step of identifying a characteristic include a step of identifying one of the following characteristics of each of said instructions held in cache: 00=NOT A BOUNDARY 01=INSTRUCTION PREFIX BYTE 10=COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) 11=SIMPLE INSTRUCTION BOUNDARY.
Claim 21
Independent Claim
144 words
A method of fetching multiple instructions in a pipelined microprocessor for out-of-order instruction execution in microprocessor architectures that permit store to the instruction stream, said method comprising the steps of: storing most recent addresses of cache lines which have been accessed for instruction fetching for execution in a memory, detecting an occurrence of a store to memory request to one of said instruction addresses in the memory; delaying the store to memory request until previous instructions are executed; refetching instructions that follow the store to memory request in program order; and logically identifying instruction boundaries for each of said plurality of instructions held in cache, wherein said step of identifying a characteristic include a step of identifying one of the following characteristics of each of said instructions held in cache: 00=NOT A BOUNDARY 01=INSTRUCTION PREFIX BYTE 10=COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) 11=SIMPLE INSTRUCTION BOUNDARY.
Claim 22
Dependent Claim
42 words
The method as in claim 17, further comprising the steps of: performing an instruction having said 11=SIMPLE INSTRUCTION BOUNDARY characteristic in one machine cycle, and performing an instruction having said 10=COMPLEX INSTRUCTION BOUNDARY (NO PREFIX) characteristic in at least two machine cycles.
References Cited (Backward Citations)
US4669043A
Cited
US5051885A
Cited
US4985825A
Cited
US5113515A
Cited
US5144692A
Cited
US5226130A
Cited
US5500942A
Cited
US5471591A
Cited
US5210842A
Cited
US5363495A
Cited
US5285527A
Cited
US5450605A
Cited
US5434987A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-06-30 | 2000-12-30 | 2001-07-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-06-30 | 2004-12-30 | 2005-07-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-06-30 | 2008-12-30 | 2009-07-01 | $7700.00 | Window Closed / Lapsed |