Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Scoreboarding – reservation station – or aliasing
Reexamination Certificate
1998-11-20
2001-10-30
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Scoreboarding, reservation station, or aliasing
C712S219000
Reexamination Certificate
active
06311267
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to data processing systems and more specifically applies to recovery mechanisms for such systems, particularly where the system includes a processor that is superscalar or has a pipelined execution unit.
BACKGROUND OF THE INVENTION
Currently, register renaming techniques employ a mechanism where the target register of an instruction is assigned a temporary rename buffer during the instruction dispatch cycle of that instruction. This instruction will hang on to the temporary buffer from the dispatch time until it is completed by the machine; which locks up rename resources for a long time (i.e. if the instruction is a load that misses L1 or L2 caches). A load miss in a cache is a typical event, for example, which looks up rename resources for a long time. Thus, a need exists for improved renaming.
SUMMARY OF THE INVENTION
The foregoing need is addressed by the present invention, as follows.
A target register of an instruction is assigned a rename register in response to the instruction being issued. That is, the target register is renamed at issue time, not at dispatch time.
A new deadlock issue arises due to the present invention because of a potential race among instructions. That is, instructions are dispatched in program order, and in the prior art each instruction needing a rename register is assigned a rename register at dispatch; therefore, according to the prior art it is not possible for a deadlock to occur wherein younger instructions consume all available rename registers, and an older instruction is unable to be dispatched for lack of a rename register. However, according to the present invention, instructions are dispatched in program order, but are not assigned a rename register until issue time. Furthermore, issuance depends on availability of source operands, and completion is in program order. Therefore, one aspect of the present invention involves a recognition that without adequate rename register and allocation/deallocation resources it would be possible for a deadlock to occur. That is, if younger instructions were issued before older instructions to the extent of consuming all rename registers, this would prevent issuance of an older instruction for lack of a rename register. If an instruction cannot be issued, it cannot complete. Therefore, completion in program order would be impossible if an oldest instruction could not be issued for lack of a rename register. To avoid this potential deadlock, rename register allocation/deallocation logic, according to the present invention, includes logic for allocating and deallocating two sets of rename registers, one set from a regular rename buffer and another set from an overflow rename buffer. According to this allocation/deallocation logic, an oldest instruction currently being processed in the processor is identified as an instruction which is next to be completed. If this oldest instruction is still in the instruction queue and the regular rename buffer is full, then a rename register is assigned from the rename overflow buffer to this instruction, so the instruction can execute.
Advantages of the present invention include allowing the rename buffer to remain free until it is ready to be consumed by the execution engines, and avoiding a rename buffer being held for a long time by an instruction that is not ready to be executed. Consequently, more rename registers are freed for younger instructions to be dispatched and executed. But deadlock is avoided, because rename registers are not permitted to be assigned to younger instructions to an extent that younger instructions consume all available rename registers.
REFERENCES:
patent: 4992938 (1991-02-01), Cocke et al.
patent: 5497499 (1996-03-01), Garg et al.
patent: 5625837 (1997-04-01), Popescu et al.
patent: 5630149 (1997-05-01), Bluhm
patent: 5673427 (1997-09-01), Brown et al.
patent: 5699538 (1997-12-01), Le et al.
patent: 5708841 (1998-01-01), Popescu et al.
patent: 5758117 (1998-05-01), Patel et al.
patent: 5872950 (1999-02-01), Levitan et al.
patent: 5872985 (1999-02-01), Kimura
patent: 5944812 (1999-08-01), Walker
Le Hung Qui
Nguyen Dung Quoc
Anthony V. S. England
Chan Eddie
International Business Machines - Corporation
Patel Gautam R.
Salys Casimer K.
LandOfFree
Just-in-time register renaming technique does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Just-in-time register renaming technique, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Just-in-time register renaming technique will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2591024