Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
1999-07-08
2002-09-03
Kim, Kenneth S. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S217000, C712S219000
Reexamination Certificate
active
06446194
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to microprocessors, and more particularly to the efficient utilization of rename buffers in a superscalar processor.
2. Description of Related Art
Microprocessors have been made faster and more powerful through the use of the reduced instruction set computer (RISC) processor. Further advances in the field of RISC processors have led to the development of superscalar processors. Such processors allow speculative execution, out-of-order instruction execution, and dispatching of instructions beyond dependent instructions. To support such speculative and out-of-order operations in superscalar processors, rename buffers have been utilized. A rename buffer allows a dispatch unit to rename memory buffers so that a location to which execution units temporarily cannot write results can be assigned rename value locations for an operand/result. The rename buffers are limited in number, causing decreased performance when all of the rename buffers are busy but not all of the execution units in the processor are busy. To help improve performance during times when all of the rename buffers are busy, a method for using a virtual rename buffer has been disclosed. A virtual rename buffer, as its name implies, is not actually a physical buffer. Rather, it is simply an address that is assigned to an instruction so that the instruction can be dispatched to the appropriate execution unit. Thus, the instruction can be operated upon but cannot be finished until an actual or physical rename buffer becomes available. This saves time by allowing part of the execution of the instruction to be accomplished while waiting on a physical buffer to open up.
Patel, et. al, (U.S. Pat. No. 5,758,117) provides a method and system for reducing dispatch stalls and for efficiently utilizing rename buffers in a superscalar processor. The method includes tracking allocation and deallocation of real rename buffers for instructions dispatched by a dispatch unit, and providing at least one virtual rename buffer for allocation of an instruction when the real rename buffers have been allocated. The method further includes tagging the instruction allocated to the at least one virtual rename buffer with a rename buffer busy signal, wherein the rename buffer busy signal indicates to an execution unit of the processor that the instruction cannot be completed.
The system disclosed by Patel, et. al, includes a plurality of rename buffers, a dispatch unit coupled to the plurality of rename buffers, and an allocation/deallocation table coupled to the dispatch unit and the plurality of rename buffers. Further, the table includes a plurality of real rename buffer slots and at least one virtual rename buffer slot. Additionally, a rename busy signal is provided via the table for an instruction allocated to the at least one virtual rename buffer slot.
Greater efficiency results from effectively controlling the use of virtual rename buffers in conjunction with real rename buffers. The virtual rename buffers allow dispatches to execution units to continue even after all of the real rename buffers have been allocated. Thus, processor performance is improved by reducing the number of stalls in a dispatch unit due to a lack of real rename buffers.
Detecting the wrapping of a multiple slotted resource is often required in microprocessor designs, particularly in buffer renaming. Virtual renaming will likely become more important in microprocessor designs as the number of rename buffers increases due to the increase of superscalar processors and the increase of execution pipe latencies to obtain higher frequencies in processors.
As an example of a virtual rename scheme that has previously been disclosed, consider FIG.
1
. An instruction
100
can be dispatched to superscalar units based on a 32 buffer virtual rename space
110
while implementing only 16 physical rename buffers
120
. The dispatched instruction's sources
130
are mapped to the rename buffer
140
allocated for the instruction producing the previous result, assuming that the instruction
100
is dependent upon a previous instruction. The target
150
is allocated a unique rename buffer
160
from the 32 virtual rename space. These results are saved in an instruction queue
170
and the instruction
100
can be issued. However, the instruction
100
cannot be issued to the execution unit from the queue
170
until one of the physical buffers
120
associated with the unique rename buffer
160
is free.
One method of mapping this scheme is to divide the 32 virtual rename space
110
into an upper portion
180
and lower portion
190
and to overlay the 16 physical rename buffers
120
over the upper portion
180
and the lower portion
190
of the 32 virtual rename space. Thus, physical buffer ‘0’
120
a
is mapped onto virtual buffers ‘0’
190
a
and ‘16’
180
a
; physical buffer ‘1’
120
b
is mapped to virtual buffers ‘1’
190
b
and ‘17’
180
b
, and so on. Using this map, the instruction allocated to virtual buffer ‘16’
180
a
cannot issue until the instruction allocated to virtual buffer ‘0’
190
a
is completed, thereby freeing physical buffer ‘0’
120
a
. Determining whether or not the physical buffer associated with the allocated virtual buffer is free requires wrap detection. For a superscalar processor in which instruction queues may issue to multiple units in a speculative or out-of-order fashion, the determination of whether or not to issue instructions to the execution unit becomes a critical path in the machine, even more so as cycle times become more aggressive. One solution is to add a cycle to the issue determination to alleviate the critical path.
The logic used to implement this solution is shown in FIG.
2
. The encoded address of each of the 32 virtual rename buffers
110
includes one high order bit in addition to the encoded address of the corresponding physical buffer. Similarly, each of the 16 physical buffers
120
have a “virtual bit” associated with it to indicate whether the buffer is associated with the upper portion
180
or the lower portion
190
of the virtual rename space
110
. For example, before any of the buffers are allocated, each of these 16 virtual bits would contain a logic ‘0’ to indicate that the physical buffer is currently mapped to the lower portion
190
of the virtual rename space
110
. That is, the virtual bit associated with physical buffer ‘0’
120
a
would indicate that the buffer is currently associated with virtual buffer ‘0’
190
a
; the virtual bit associated with physical buffer ‘1’
120
b
would indicate that the buffer is currently associated with virtual buffer ‘1’
190
b
, and so on. Once the contents of a physical buffer are written into the architected buffer file, the virtual bit associated with that physical buffer is toggled to indicate that the physical buffer now maps to the opposite half of the virtual rename space. Thus, when physical buffer ‘0’ with a virtual bit value of ‘0’
120
a
writes its contents to the architected buffer file, the virtual bit is toggled from ‘0’ to ‘1’ to indicate that physical buffer ‘0’
120
a
is now mapped to virtual rename buffer
16
180
a.
Referring now to
FIG. 2
, the four lower order bits of the target buffer pointer
200
are input to a 4-to-16 decoder
210
. The 16 orthogonal signals
215
are connected to the select inputs of the 16-to-1 multiplexer
220
. The 16 virtual bits
225
associated with the 16 physical rename buffers
120
are connected to the input of the multiplexer
220
such that the multiplexer uses the 16 orthogonal signals
215
to select the virtual bit corresponding to the physical buffer mapping to the target buffer pointer
200
. The virtual bit
235
that is selected by the multiplexer
220
is compared with the higher order bit
240
of the target buffer pointer
200
using an exclusive or gate
245
. If the virtual bit
235
and the higher order bit
240
match, then the exclusive or gate
245
will output a ‘0’ indicating that the instruction may issue to the
Eisen Susan Elizabeth
Phillips James Edward
Kim Kenneth S.
McBurney Mark E.
Nichols Michael R.
Yee Duke W.
LandOfFree
Virtual register renamed instruction issue for execution... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Virtual register renamed instruction issue for execution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Virtual register renamed instruction issue for execution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2885147