Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Reducing an impact of a stall or pipeline bubble
Reexamination Certificate
2001-05-04
2002-05-07
Donaghue, Larry D. (Department: 2154)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Reducing an impact of a stall or pipeline bubble
C712S023000, C712S218000, C709S241000
Reexamination Certificate
active
06385715
ABSTRACT:
FIELD
The invention generally relates to processors, and in particular to multi-threading techniques for a processor utilizing a replay queue.
BACKGROUND
The primary function of most computer processors is to execute a stream of computer instructions that are retrieved from a storage device. Many processors are designed to fetch an instruction and execute that instruction before fetching the next instruction. Therefore, with these processors, there is an assurance that any register or memory value that is modified or retrieved by a given instruction will be available to instructions following it. For example, consider the following set of instructions:
1) Load memory-
1
→register-X;
2) Add
1
register-X register-Y→register-Z;
3) Add
2
register-Y register-Z→register-W.
The first instruction loads the content of memory-
1
into register-X. The second instruction adds the content of register-X to the content of register-Y and stores the result in register-Z. The third instruction adds the content of register-Y to the content of register-Z and stores the result in register-W. In this set of instructions, instructions
2
and
3
are considered “dependent” instructions that are dependent on instruction
1
. In other words, if register-X is not loaded with valid data in instruction
1
before instructions
2
and
3
are executed, instructions
2
and
3
will generate improper results. With the traditional “fetch and execute” processors, the second instruction will not be executed until the first instruction has properly executed. For example, the second instruction may not be dispatched to the processor until a cache hit/miss signal is received as a result of the first instruction. Further, the third instruction will not be dispatched until an indication that the second instruction has properly executed has been received. Therefore, it can be seen that this short program cannot be executed in less time than T=L
1
+L
2
+L
3
, where L
1,
L
2
and L
3
represent the latency of the three instructions. Hence, to ultimately execute the program faster, it will be necessary to reduce the latencies of the instructions.
Therefore, there is a need for a computer processor that can schedule and execute instructions with improved speed to reduce latencies.
SUMMARY
According to an embodiment of the present invention, a processor is provided that includes an execution unit to execute instructions and a replay system coupled to the execution unit to replay instructions which have not executed properly. The replay system includes a checker to determine whether each instruction has executed properly and a plurality of replay queues. Each replay queue is coupled to the checker to temporarily store one or more instructions for replay.
REFERENCES:
patent: 5185871 (1993-02-01), Frey et al.
patent: 5197132 (1993-03-01), Steely, Jr. et al.
patent: 5341482 (1994-08-01), Cutler et al.
patent: 5519841 (1996-05-01), Sager et al.
patent: 5828868 (1998-10-01), Sager et al.
patent: 5835745 (1998-11-01), Sager et al.
patent: 5966544 (1999-10-01), Sager
patent: 6088790 (2000-07-01), Grochowski
patent: 6094717 (2000-07-01), Merchant et al.
patent: 6163838 (2000-12-01), Merchant et al.
Wallace et al., Threaded Multiple Path Execution, Jun. 1998, pp. 1-12.
Roos et al., Execution Replay of Parallel Programs, 1993, pp. 1-6.
Marcuello et al., Data Speculative Multithreaded Architecture, 1998, pp. 321-324.
Gulati et al., Performance Study of a Multithreaded Superscalar Microprocessor, 1996, pp. 291-301.
Akkary et al., A Dynamic Multithreading Processor, 1998, pp. 226-236.
Tsai et al., Performance Study of a Concurrent Multithreaded Processor, 1998, pp. 24-35.
Boggs Darrell D.
Merchant Amit A.
Sager David J.
Antonelli Terry Stout & Kraus LLP
Donaghue Larry D.
LandOfFree
Multi-threading for a processor utilizing a replay queue does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-threading for a processor utilizing a replay queue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-threading for a processor utilizing a replay queue will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2862020