Electrical computers and digital processing systems: processing – Architecture based instruction processing
Reexamination Certificate
1997-12-31
2001-02-20
Elmore, Rita (Department: 2759)
Electrical computers and digital processing systems: processing
Architecture based instruction processing
C712S229000, C712S244000, C712S245000
Reexamination Certificate
active
06192464
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to processors and computers, and more particularly, to a method and apparatus that partially decodes instructions into micro-ops before renaming destination registers.
2. Description of the Related Art
Modem processors and computers have increased their operating speeds and efficiency through a variety of methods and structures. Many processors and similar hardware structures increase instruction throughput by executing instructions either in parallel or out-of-order of the original instruction sequence. The instruction throughput of an out-of-order processor may be improved by using auxiliary hardware structures and special methods that make the execution order more flexible. The hardware structures and special methods include fetchers that employ branch prediction, parallel decoders, large reorder buffers, dependency determination, and renaming of destination registers. These hardware structures and methods for treating the incoming instruction sequence may affect the processor's throughput by synergistic interactions.
FIG. 1
illustrates a portion
10
of an out-of-order processor. A fetcher
12
retrieves a sequence of instructions from memory or caches
14
. The fetcher
12
sends the retrieved instructions to one or more decoders
16
. The decoders
16
translate the complex instructions, e.g., macro instructions, into simpler hardware executable micro-operations (micro-ops). The decoders
16
send a sequence of micro-ops to a renamer
18
. The renamer
18
reassigns additional physical registers to replace destination registers of the micro-ops, i.e. the registers for storing results. The renamer
18
may also record data on the dependencies between the micro-ops and on the reassignment of additional physical registers in a dependency table
20
. The renamer
18
assigns the renamed micro-ops entries in a reorder buffer
22
and sends the micro-ops to a scheduler
24
. The scheduler
24
assigns instructions for execution in an order that may not follow the original order of the instruction sequence. The scheduler
24
does not assign dependent instructions for execution before the instructions on which they depend. The scheduler
24
consults and updates the dependency and register assignment information in the dependency table
20
. A retirement unit
28
removes executed instructions from the reorder buffer
28
in the original instruction order and sends the results to registers and/or caches
30
.
FIG. 2A
illustrates the effect of renaming on the out-of-order execution of write-after-write instructions, i.e. two instructions having the same destination register. At block
40
, three instructions
42
,
44
,
46
are shown in the original order of an instruction sequence. The instructions
42
,
44
,
46
have been decoded, i.e. they are micro-ops.
The source and destination addresses can include both memory locations and registers. While macro instructions may have a variable number of addresses, decoded instructions, i.e. micro-ops, have a limited and fixed number of destination and source addresses for a given micro-architecture. In most computers, micro-ops do not have more than two source addresses, e.g., A and B for the first instruction
42
, and one destination address, e.g., the register R
1
for the first and second instructions
42
,
44
. Some computers may employ micro-ops with more source or destination addresses, but the micro-ops of each architecture still have a limited number of addresses.
Due to the small register sets in many computers, the same register may appear in two or more instructions. For example, the register R
1
is the destination address of the first and second instructions
42
,
44
of block
40
and is one source address of the third instruction
46
. The appearance of the same register in separate instructions can create real and artificial dependencies that prohibit the out-of-order execution of the instructions involved and of instructions dependent thereon.
In the processor
10
, it is ordinarily advantageous to be able to execute instructions in any order that keeps the execution unit or units
26
continually busy. For example, executing the second instruction
44
before the first instruction
42
may enable the processor
10
to avoid a period in which one of the execution units
26
is inactive. Instruction dependencies can make the results artificially dependent on the execution order and can interfere with the use of out-of-order execution as a means of improving the efficiency of the processor
10
.
Block
50
illustrates the result of executing the second instruction
44
out-of-order, i.e. before the first instruction
42
. Since the first and second instructions
42
,
44
do not depend on each other, they may be executed in any order. Nevertheless, a problem occurs when the execution order of these write-after-write instructions
42
,
44
is inverted, because the third instruction
46
depends on the second instruction
44
in block
40
, and the third instruction
46
depends on the first instruction
42
in the inverted order of block
50
. Executing write-after-write instructions out-of-order may change the results from subsequent dependent instructions.
Block
52
illustrates how renaming eliminates dependencies when write-after-write instructions are executed out-of-order. The renamer
18
assigns a new additional physical register R′
1
for the destination register of the second instruction
44
in block
40
, i.e. the register R
1
is renamed to R′
1
, in the instruction
45
of block
52
. The renamer
18
also replaces R
1
with R′
1
, in instructions dependent on the second instruction
44
, i.e. the source register R
1
of the third instruction
46
of block
40
is renamed to R′
1
, giving the third instruction
47
of block
52
. Renaming uses additional physical registers of the processor
10
, such as R′
1
, to “rename”, i.e. replace, registers appearing as source or destination addresses in instructions. After renaming, the destination register of the first instruction
42
of block
52
is not an address of the third instruction
47
of block
52
. Therefore, the execution of the first instruction
42
and the renamed second instruction
45
may be performed in any order without changing the results coming from dependent instructions, such as the third instruction
47
of block
52
.
As illustrated in
FIG. 2B
, renaming may also be employed to enable the out-of-order execution of write-after-read instructions, i.e. two instructions wherein the same register is a source address for the earlier instruction and a destination address for the later instruction. At block
60
, an instruction
62
having a destination register R
1
is independent of an earlier instruction
64
having the same register R
1
as a source address. Block
66
illustrates the result of executing the first and second instructions
64
,
62
of block
60
out-of-order. Now, the destination register R
1
of the earlier executed instruction
62
becomes a source address for the later executed instruction
64
. The out-of-order execution of the write-after-read instructions
64
,
62
generates a new dependency for the instruction
64
. Generally, the new dependency for the instruction
64
means that different results are obtained when the two instructions
62
,
64
are executed in the original instruction order of block
60
and in the inverted order of block
66
.
At block
68
, the original destination register R
1
of the second instruction
62
of the write-after-read sequence of block
60
has been renamed with an additional physical register R′
1
. The renamer
18
also renames the source address R
1
to R′
1
in all subsequent instructions that depend on the original second instruction
62
of block
60
. The renamer performs a look-up in the dependency table
20
for correspondences between the original destination register and the additional physical registers so that source registers
Blakely , Sokoloff, Taylor & Zafman LLP
Elmore Rita
Intel Corporation
LandOfFree
Method and apparatus for decoding one or more instructions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for decoding one or more instructions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for decoding one or more instructions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2612615