US5699536A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computer processing system employing dynamic instruction formatting
Assignee: International Business Machines Corp
•
Filing: 1995-04-13
•
Granted: 1997-12-16
•
Expires: 2015-04-13
Abstract
Abstract A computer processing apparatus includes a buffer called a decoded instruction buffer (DIB), which is used to store groups of commands representing instructions that can be executed in parallel. Each pattern in a DIB group may be an encoding of a long instruction termed a long decoded instruction (LDI). The DIB works in conjunction with a conventional computer processing apparatus consisting of a memory system, an instruction queue, and an instruction dispatch unit feeding into a set of execution units. When an instruction is not available in the DIB, this and subsequent instructions are fetched from the memory system into the instruction queue and executed in a conventional way. Simultaneous with the execution of instructions by the conventional apparatus, a group formatter creates a set of LDIs, each of which is an alternate encoding of a set of the original instructions which can be executed in parallel. In constructing the LDIs, the group formatter analyzes the dependency between instructions and instruction latency. Each set of LDIs constructed by the group formatter is saved in the DIB so that the next execution of the same set of instructions can be executed directly from the DIB on the full complement of functional units and will not require the effort of dependency and latency analysis.
Inventors
- 👤 Martin Edward Hopkins
- 👤 Ravindra K. Nair
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 18:33
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/22; G06F9/30; G06F9/38; G06F9/3802; G06F9/3808; G06F9/32; G06F9/322; G06F9/323; G06F9/3836; G06F9/3838; G06F9/384; G06F9/3853; G06F9/3854; G06F9/3856; G06F9/3858; G06F9/3885
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
225 words
A computer processing apparatus comprising: a first processing engine comprising: a first memory for storing instructions to be executed by at least one first execution unit, an instruction fetch unit for fetching instructions from said first memory into an instruction queue according to a fetch control signal, a dispatch unit for dispatching instructions stored in said instruction queue for execution by said at least one first execution unit, and means for updating said fetch control signal according to execution of instructions performed by said at least one first execution unit; alternate encoding execution means comprising a plurality of second execution units; a group formatter for generating an alternate encoding of sequences of instructions dispatched for execution by said dispatch unit concurrent with execution of said sequences of instructions by said first processing engine, wherein said alternate encoding comprises a set of long decoded instructions, wherein each long decoded instruction (LDI) comprises a set of op-fields each corresponding to one of said plurality of second execution units, and wherein each op-field is executable by the corresponding second execution unit; a second memory for storing said alternate encoding generated by said group formatter; and wherein, upon detecting that said fetch control signal corresponds to said alternate encoding stored in said second memory, said plurality of second execution units execute said alternate encoding stored in said second memory.
Claim 2
Dependent Claim
225 words
A computer processing apparatus comprising: a first processing engine comprising: a first memory for storing instructions to be executed by at least one first execution unit, an instruction fetch unit for fetching instructions from said first memory into an instruction queue according to a fetch control signal, a dispatch unit for dispatching instructions stored in said instruction queue for execution by said at least one first execution unit, and means for updating said fetch control signal according to execution of instructions performed by said at least one first execution unit; alternate encoding execution means comprising a plurality of second execution units; a group formatter for generating an alternate encoding of sequences of instructions dispatched for execution by said dispatch unit concurrent with execution of said sequences of instructions by said first processing engine, wherein said alternate encoding comprises a set of long decoded instructions, wherein each long decoded instruction (LDI) comprises a set of op-fields each corresponding to one of said plurality of second execution units, and wherein each op-field is executable by the corresponding second execution unit; a second memory for storing said alternate encoding generated by said group formatter; and wherein, upon detecting that said fetch control signal corresponds to said alternate encoding stored in said second memory, said plurality of second execution units execute said alternate encoding stored in said second memory.
Claim 3
Dependent Claim
32 words
The computer processing apparatus of claim 1, wherein said group formatter generates said alternate encoding subsequent to execution of said sequences of instructions by said execution unit of said first processing engine.
Claim 4
Dependent Claim
21 words
The computer processing apparatus of claim 1, wherein said alternate encoding generated by said group formatter is suitable for parallel execution.
Claim 5
Dependent Claim
34 words
The computer processing apparatus of claim 1, wherein at least one of said second execution units of said alternate encoding execution means is different from said first execution unit of said first processing engine.
Claim 6
Dependent Claim
32 words
The computer processing apparatus of claim 1, wherein one of said plurality of second execution units of said alternate encoding execution means comprises said first execution unit of said first processing engine.
Claim 7
Dependent Claim
30 words
The computer processing apparatus of claim 1 wherein each op-field may be executed by the corresponding second execution unit of said alternate encoding execution means in a single machine cycle.
Claim 8
Dependent Claim
129 words
The computer processing apparatus of claim 1, wherein said alternate encoding execution means comprises a plurality of register resources that said op-fields may use and/or define, and wherein said group formatter comprises: a op-field encoder that generates said op-fields according to said sequences of instructions dispatched for execution by said dispatch unit; a time stamp table for storing time stamp identifiers associated with each of said register resources, wherein said time stamp identifiers identify on which LDI of said set of long decoded instructions the associated register resource will be available; and an allocator that builds said set of long decoded instructions according to dependency between instructions within said sequences of instructions, time stamp identifiers stored in said time stamp table, and said op-fields generated by said op-field encoder.
Claim 9
Dependent Claim
27 words
The computer processing apparatus of claim 7, wherein said allocator builds said set of long decoded instructions according to latency of instructions within said sequences of instructions.
Claim 10
Dependent Claim
33 words
The computer processing apparatus of claim 7, wherein said allocator closes said set of long decoded instructions upon detecting that one instruction within said sequences of instructions corresponds to a predefined stopping instruction.
Claim 11
Dependent Claim
39 words
The computer processing apparatus of claim 7, wherein, upon detecting that one instruction of said sequences of instructions defines a resource previously defined by an op-field of a current group, said allocator renames said resource to a free resource.
Claim 12
Dependent Claim
47 words
The computer processing apparatus of claim 7, wherein said time stamp table includes time stamp identifiers associated with load and store operations, respectively, and wherein said allocator utilizes said time stamp identifiers associated with load and store operations to maintain order of said load and store operations.
Claim 13
Dependent Claim
112 words
The computer processing apparatus of claim 1, wherein said second memory comprises: an array of entries each including a set of long decoded instructions; means for determining if one entry of said array of entries corresponds to said fetch control signal; means for reading out a set of long decoded instructions of said one entry upon determining that said one entry corresponds to said fetch control signal; and wherein said alternate encoding execution means comprises: a buffer for storing said set of long decoded instructions read out from said second memory, and said plurality of second execution units execute said op-fields of said set of long decoded instructions stored in said buffer.
Claim 14
Dependent Claim
29 words
The computer processing apparatus of claim 12, wherein said alternate encoding execution means further comprises means for updating said fetch control signal according to execution results of said op-fields.
Claim 15
Dependent Claim
34 words
The computer processing apparatus of claim 12, wherein said plurality of second execution units put away execution results of said op-fields of each LDI to appropriate register resources after finishing execution of each LDI.
Claim 16
Dependent Claim
38 words
The computer processing apparatus of claim 12, wherein said plurality of second execution units put away execution results of said op-fields of said set of long decoded instructions after finishing execution of said set of long decoded instructions.
Claim 17
Dependent Claim
70 words
The computer processing apparatus of claim 12, further comprising an exception controller that, upon experiencing an exception, updates said fetch control signal to correspond to a first instruction encoded within said set of long decoded instructions stored in said buffer, updates register resources associated with said first processing engine to their original state prior to said first instruction, and enables said first processing engine to begin processing said first instruction.
Claim 18
Dependent Claim
44 words
The computer processing apparatus of claim 12, wherein one or more of said long decoded instructions stored in said second memory are compressed; and wherein said alternate encoding execution means includes means for expanding each long decoded instruction which is compressed prior to execution.
Claim 19
Dependent Claim
66 words
The computer processing apparatus of claim 12, further comprising means for loading said set of long decode instructions currently stored in said buffer into said group formatter for subsequent processing upon detecting that one of said op-fields of said set of long decoded instructions stored in said buffer is resolved as a branch instruction out of said set of long decoded instructions stored in said buffer.
Claim 20
Dependent Claim
68 words
The computer processing apparatus of claim 1, wherein at least one sequence S of said sequences of instructions comprises a branch instruction B, an instruction PB preceding said branch instruction B, and an instruction FB following said branch instruction B, and wherein said set of long decoded instructions corresponding to said sequence S includes op-fields corresponding to said branch instruction B, said instruction PB and said instruction FB.
Claim 21
Dependent Claim
32 words
The computer processing apparatus of claim 19, wherein position of one of said instruction PB and said instruction FB in said sequence of instructions is not adjacent to said branch instruction B.
Claim 22
Dependent Claim
22 words
The computer processing apparatus of claim 19, wherein said instruction FB is determined based upon execution results of said branch instruction B.
Claim 23
Dependent Claim
38 words
The computer processing apparatus of claim 19, wherein said sequence S comprises multiple branch instructions, and wherein said set of long decoded instructions corresponding to said sequence S includes op-fields corresponding to each of said multiple branch instructions.
Claim 24
Dependent Claim
22 words
The computer processing apparatus of claim 22, wherein said sequence S is determined based upon execution results of said multiple branch instructions.
Claim 25
Dependent Claim
194 words
In a computer processing system wherein instuctions are stored in a first memory, a method of executing said instructions comprising the steps of: fetching instructions from said first memory into an instruction queue according to a fetch control signal; dispatching instructions stored in said instruction queue for execution by at least one first execution unit; updating said fetch control signal according to execution of instructions performed by said at least one first execution unit; generating an alternate encoding of sequences of instruction dispatched for execution concurrent with execution of said sequences of instructions by said at least one first execution unit, wherein said alternate encoding comprises a set of long decoded instructions, wherein each long decoded instruction (LDI) comprises a set of op-fields each corresponding to one of a plurality of second execution units, and wherein each op-field is executable by the corresponding second execution unit; storing said alternate encoding generated by said group formatter in a second memory; and controlling said plurality of second execution units to execute said alternate encoding stored in said second memory upon detecting that said fetch control signal corresponds to said alternate encoding stored in said second memory.
Claim 26
Dependent Claim
194 words
In a computer processing system wherein instuctions are stored in a first memory, a method of executing said instructions comprising the steps of: fetching instructions from said first memory into an instruction queue according to a fetch control signal; dispatching instructions stored in said instruction queue for execution by at least one first execution unit; updating said fetch control signal according to execution of instructions performed by said at least one first execution unit; generating an alternate encoding of sequences of instruction dispatched for execution concurrent with execution of said sequences of instructions by said at least one first execution unit, wherein said alternate encoding comprises a set of long decoded instructions, wherein each long decoded instruction (LDI) comprises a set of op-fields each corresponding to one of a plurality of second execution units, and wherein each op-field is executable by the corresponding second execution unit; storing said alternate encoding generated by said group formatter in a second memory; and controlling said plurality of second execution units to execute said alternate encoding stored in said second memory upon detecting that said fetch control signal corresponds to said alternate encoding stored in said second memory.
Claim 27
Dependent Claim
23 words
The method of claim 24, wherein said alternate encodings are generated subsequent to execution of said sequences of instructions by said execution unit.
Claim 28
Dependent Claim
21 words
The method of claim 24, wherein said alternate encoding is suitable for parallel execution by said plurality of second execution units.
Claim 29
Dependent Claim
28 words
The method of claim 24, wherein each op-field may be executed by the corresponding second execution unit of said alternate encoding execution means in a single machine cycle.
Claim 30
Dependent Claim
120 words
The method of claim 24, wherein said computer processing system includes: a plurality of register resources that said op-fields may use and/or define, an op-field encoder that generates said op-fields according to said sequences of instructions dispatched for execution, and a time stamp table for storing time stamp identifiers associated with each of said register resources, wherein said time stamp identifiers identify on which LDI of said set of long decoded instructions the associated register resource will be available; the method further comprising the step of: building said set of long decoded instructions according to dependency between instructions within said sequences of instructions, time stamp identifiers stored in said time stamp table, and said op-fields generated by said op-field encoder.
Claim 31
Dependent Claim
24 words
The method of claim 28, wherein said set of long decoded instructions are built according to latency of instructions within said sequences of instructions.
Claim 32
Dependent Claim
33 words
The method of claim 28, further comprising the step of: closing said set of long decoded instructions upon detecting that one instruction within said sequences of instructions corresponds to a predefined stopping instruction.
Claim 33
Dependent Claim
45 words
The method of claim 28, further comprising the step of: upon detecting that one instruction of said sequences of instructions defines a resource previously defined by an op-field of one LDI within said set of long decoded instructions, renaming said resource to a free resource.
Claim 34
Dependent Claim
46 words
The method of claim 28, wherein said time stamp table includes time stamp identifiers associated with load and store operations, respectively, further comprising the step of: maintaining order of said load and store operations according to said time stamp identifiers associated with load and store operations.
Claim 35
Dependent Claim
94 words
The method of claim 24, wherein said second memory comprises an array of entries each including a set of long decoded instructions, further comprising the steps of: determining if one entry of said array of entries corresponds to said fetch control signal; reading out a set of long decoded instructions of said one entry upon determining that said one entry corresponds to said fetch control signal; storing said set of long decoded instructions read out from said second memory; and executing said op-fields of said set of long decoded instructions stored in said buffer.
Claim 36
Dependent Claim
22 words
The method of claim 33, further comprising the step of: updating said fetch control signal according to execution results of said op-fields.
Claim 37
Dependent Claim
30 words
The method of claim 33, further comprising the step of: putting away execution results of said op-fields of each LDI to appropriate register resources after finishing execution of each LDI.
Claim 38
Dependent Claim
34 words
The method of claim 33, further comprising the step of: putting away execution results of said op-fields of said set of long decoded instructions after finishing execution of said set of long decoded instructions.
Claim 39
Dependent Claim
73 words
The method of claim 33, further comprising the steps of: upon experiencing an exception, updating said fetch control signal to correspond to a first instruction encoded within said set of long decoded instructions stored in said buffer, updating register resources associated with said at least one execution unit to their original state prior to said first instruction, and enabling processing of said first instruction for execution by said at least one execution unit.
Claim 40
Dependent Claim
53 words
The method of claim 33, further comprising the steps of: prior to storing said one or more of said long decoded instructions in said second memory, compressing said one or more long decoded instructions; and prior to executing said one or more long decoded instructions, expanding each long decoded instruction which is compressed.
Claim 41
Dependent Claim
58 words
The method of claim 33, further comprising the step of: upon detecting that one of said op-fields of said set of long decoded instructions stored in said buffer is resolved as a branch instruction out of said set of long decoded instructions stored in said buffer, updating said set of long decoded instructions currently stored in said buffer.
Claim 42
Dependent Claim
52 words
The method of claim 33, wherein said updating of said set of long decoded instructions stored in said buffer includes the step of adding at least one long decoded instruction to said set of long decoded instructions according to said sequences of instructions and dependency between instructions within said sequences of instructions.
Claim 43
Dependent Claim
37 words
The method of claim 40, wherein said at least one long decoded instuction is added to said set of long decoded instructions stored in said buffer according to latency of said instuction within said sequences of instuctions.
Claim 44
Dependent Claim
64 words
The method of claim 24, wherein at least one sequence S of said sequences of instructions comprises a branch instruction B, an instruction PB preceding said branch instruction, and an instruction FB following said branch instruction, and wherein said set of long decoded instructions corresponding to said sequence S includes op-fields corresponding to said branch instruction B, said instruction PB and said instruction FB.
Claim 45
Dependent Claim
30 words
The method of claim 42, wherein position of one of said instruction PB and said instruction FB in said sequence of instructions is not adjacent to said branch instruction B.
Claim 46
Dependent Claim
20 words
The method of claim 42, wherein said instruction FB is determined based upon execution results of said branch instruction B.
Claim 47
Dependent Claim
36 words
The method of claim 42, wherein said sequence S comprises multiple branch instructions, and wherein said set of long decoded instructions corresponding to said sequence S includes op-fields corresponding to each of said multiple branch instructions.
Claim 48
Dependent Claim
20 words
The method of claim 45, wherein said sequence S is determined based upon execution results of said multiple branch instructions.
References Cited (Backward Citations)
EP0021399A1
Cited
EP0096575A2
Cited
US4484272A
Cited
EP0101596A2
Cited
US4679141A
Cited
US5016163A
Cited
US5021945A
Cited
US4903196A
Cited
EP0255186A2
Cited
US4811214A
Cited
US5127104A
Cited
US4992938A
Cited
US5297281A
Cited
US5197137A
Cited
US5502826A
Cited
US5450556A
Cited
US5299321A
Cited
US5442790A
Cited
EP0523337A2
Cited
US5347639A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-15 | 2001-06-16 | 2001-12-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-15 | 2005-06-16 | 2005-12-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-15 | 2009-06-16 | 2009-12-16 | $7700.00 | Window Closed / Lapsed |