Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
2002-05-09
2004-01-06
El-Hady, Nabil (Department: 2156)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S023000, C712S217000, C712S218000, C712S219000, C712S233000, C712S237000, C712S240000, C712S244000
Reexamination Certificate
active
06675288
ABSTRACT:
BACKGROUND OF THE INVENTION
Instruction pipelining generally involves splitting a data processor into a series of stages called a pipeline. Typically, the pipeline stages process different portions of a stream of instructions concurrently. For example, a fetch stage may fetch instructions from main memory while an execution stage executes one or more previously fetched instructions.
In general, pipelined processors are susceptible to delays caused by instruction dependencies within the instruction stream. For example, consider the following instruction stream having instructions (1), (2) and (3), where (OP
1
), (OP
2
) and (OP
3
) are operations (e.g., add, shift, logical OR) that require various amounts of time (processor cycles) to complete.
R
2
=R
1
(
OP
1
)
R
5
(1)
R
1
=R
3
(
OP
2
)
R
8
(2)
R
7
=R
4
(
OP
3
)
R
6
(3)
An instruction dependency exists between instructions (1) and (2) because instruction (1) reads data from register RI, and instruction (2) subsequently writes new data to register R
1
. In order for instruction (1) to provided a correct result, instruction (2) must write the new data to register R
1
after instruction (1) reads the original data from register R
1
. If instruction (2) writes to register RI before instruction (1) reads from register R
1
, instruction (1) will read the new data written by instruction (2) rather than the original data, and thus may provide an incorrect result. Accordingly, a write-after-read (WAR) dependency (or data hazard) exists between instructions (1) and (2).
Instruction (3) does not access any registers that are accessed by instructions (1) or (2). Accordingly, no instruction dependency exists between instruction (3) and instructions (1) and (2).
In addition to WAR dependencies, there are other types of instruction dependencies that can occur within an instruction stream. In particular, write-after-write (WAW) dependencies involve two instructions that write to the same register in an instruction stream. The two instructions must write to the register in proper order. Otherwise, the wrong data will be left in that register after the two instructions complete. If the wrong data is left in that register, another instruction that reads from that register may provide an incorrect result.
Another type of dependency is a read-after-write (RAW) dependency which involves a first instruction that writes to a register, and a subsequent instruction that reads from the same register. The first instruction must write to the register before the subsequent instruction reads from that register. Otherwise, the subsequent instruction will not read the result of the first instruction, and instead read old data.
Some pipelined processors resolve instruction dependencies by delaying instructions in the pipeline. For the above example, such a processor may issue instruction (1), and delay issuing instruction (2) until instruction (1) reads from register R
1
. The delay prevents instruction (2) from inadvertently overwriting the contents of register R
1
before instruction (1) reads from register R
1
. Accordingly, the data hazard between instructions (1) and (2) is resolved.
Some processors which delay instructions to resolve instruction dependencies have the ability to issue instructions out-of-order. Such out-of-order processors may issue other instructions in place of the delayed instructions so that the processor remains busy. For the above example, an out-of-order processor may delay issuance of instruction (2) while instruction (1) executes. Furthermore, the processor may issue instruction (3) in place of instruction (2) such that stages of the processor do not become idle. Since no dependency exists for instruction (3), it does not matter when instruction (3) executes relative to instructions (1) and (2). Once instruction (1) has read from register R
1
, the processor may issue instruction (2) even though instruction (3) has already issued.
SUMMARY OF THE INVENTION
The conventional approach of resolving instruction dependencies by delaying particular instructions and issuing other instructions in their place is not very effective in certain situations. For example, when the instruction stream has many instruction dependencies and few instructions without dependencies, many instructions must be delayed, and few instructions can be issued in place of the delayed instructions. For such an instruction stream (or portions thereof), the conventional approach may not be able to keep the pipelined processor busy.
The present invention is a technique for mapping instructions to resolve certain types of instruction dependencies such as write-after-read (WAR) dependencies and write-after-write (WAW) dependencies. In some situations, the instructions, once mapped, no longer access the same registers. Accordingly, the particular dependencies are resolved without delaying instructions.
One embodiment of the technique involves obtaining an instruction having at least one logical operand that identifies a logical register. The technique further involves renaming the logical operand with a physical operand that identifies a physical register according to a set of assignments that assign logical registers to physical registers. The instruction is mapped when each logical operand has been renamed. Accordingly, there is no need to delay instructions, and pipeline throughput can be maintained.
Mapped instructions may include logical source and destination operands that identify particular logical registers. Renaming a logical source operand preferably involves finding, in the set of assignments, an existing assignment according to the logical source operand. The found existing assignment may assign the particular logical register to a particular physical register. Renaming may further involve replacing, in the obtained instruction, the logical source operand with a physical source operand that identifies the particular physical register according to the found existing assignment.
The set of assignments may include valid assignments and invalid assignments. Furthermore, finding the existing assignment may involve locating, in the set of assignments, a valid assignment and at least one invalid assignment according to the logical source operand. Finding may further involve selecting, as the existing assignment, the located valid assignment from the located valid and invalid assignments.
Renaming the logical destination operand may involve generating a new assignment according to the set of assignments. The generated new assignment may assign the particular logical register to a particular physical register. Renaming may further involve replacing the logical destination operand with a physical destination operand that identifies the particular physical register according to the generated new assignment.
A previously generated assignment may assign the particular logical register to a physical register that is different than the particular physical register. In this situation, generating the new assignment may involve invalidating the previously generated assignment. Generating may further involve creating and validating the generated new assignment that assigns the particular logical register to the particular physical register.
Another embodiment of the invention is directed to a technique for managing register assignments. The technique involves maintaining, in a register list memory circuit having entries that respectively correspond to physical registers, a list of register assignments that assign logical registers to the physical registers. Additionally, the technique involves maintaining, in a vector memory circuit having bits that respectively correspond to the physical registers, a valid vector that forms, in combination with the list of register assignments, a list of valid register assignments. Furthermore, the technique involves storing, for an instruction that is mapped by the data processor, a copy of the valid vector from the vector memory circuit to a silo memory circuit. Preferably,
Britton Sharon Marie
Fair, III Harry Ray
Farrell James Arthur
Gieseke Bruce
Leibholz Daniel Lawrence
El-Hady Nabil
Hamilton Brook Smith & Reynolds P.C.
Hewlett--Packard Development Company, L.P.
LandOfFree
Apparatus for mapping instructions using a set of valid and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for mapping instructions using a set of valid and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for mapping instructions using a set of valid and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3200675