Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
1997-12-16
2002-10-08
Ellis, Richard L. (Department: 2653)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S225000
Reexamination Certificate
active
06463522
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to processors and, more particularly, to processors having a memory order buffer.
2. Background Art
Current superscaler processors, such as microprocessors, perform techniques such as branch prediction and out-of-order execution to enhance performance. Processors having out-of-order execution pipelines execute certain instructions in a different order than the order in which the instructions were fetched and decoded. Instructions may be executed out of order with respect to instructions for which there are not dependencies. Out-of-order execution increases processor performance by preventing execution units from being idle merely because of program instruction order. Instruction results are reordered after execution.
The task of handling data dependencies is simplified by restricting instruction decode to being in-order. The processors may then identify how data flows from one instruction to subsequent instructions through registers. To ensure program correctness, registers are renamed and instructions wait in reservation stations until their input operands are generated, at which time they are issued to the appropriate functional units for execution. The register renamer, reservation stations, and related mechanisms link instructions having dependencies together so that a dependent instruction is not executed before the instruction on which it depends. Accordingly, such processors are limited by in-order fetch and decode.
When the instruction from the instruction cache misses or a branch is mis-predicted, the processors have either to wait until the instruction block is fetched from the higher level cache or memory, or until the mis-predicted branch is resolved, and the execution of the false path is reset. The result of such behavior is that independent instructions before and after instruction cache misses and mis-predicted branches cannot be executed in parallel, although it may be correct to do so.
A memory order buffer has been used to order loads and stores. There is a need for improved mechanisms in a processor that allow the processor to recover from speculation errors.
SUMMARY OF THE INVENTION
In one embodiment of the invention, a processor includes a memory order buffer (MOB) including load buffers and store buffers, wherein the MOB orders load and store instructions so as to maintain data coherency between load and store instructions in different threads, wherein at least one of the threads is dependent on at least another one of the threads. In another embodiment of the invention, a processor includes an execution pipeline to concurrently execute at least portions of threads, wherein at least one of the threads is dependent on at least another one of the threads, the execution pipeline including a memory order buffer that orders load and store instructions. The processor also includes detection circuitry to detect speculation errors associated with load instructions in a load buffer.
REFERENCES:
patent: 5142634 (1992-08-01), Fite et al.
patent: 5153848 (1992-10-01), Elkind et al.
patent: 5309561 (1994-05-01), Overhouse et al.
patent: 5313634 (1994-05-01), Eickemeyer
patent: 5420990 (1995-05-01), McKeen et al.
patent: 5420991 (1995-05-01), Konigsfeld et al.
patent: 5421021 (1995-05-01), Saini
patent: 5524250 (1996-06-01), Chesson et al.
patent: 5524262 (1996-06-01), Colwell et al.
patent: 5546593 (1996-08-01), Kimura et al.
patent: 5586278 (1996-12-01), Papworth et al.
patent: 5588126 (1996-12-01), Abramson et al.
patent: 5606670 (1997-02-01), Abramson et al.
patent: 5613083 (1997-03-01), Glew et al.
patent: 5664137 (1997-09-01), Abramson et al.
patent: 5671444 (1997-09-01), Akkary et al.
patent: 5680565 (1997-10-01), Glew et al.
patent: 5724536 (1998-03-01), Abramson et al.
patent: 5724565 (1998-03-01), Dubey et al.
patent: 5742782 (1998-04-01), Ito et al.
patent: 5748937 (1998-05-01), Abramson et al.
patent: 5754818 (1998-05-01), Mohamed
patent: 5802272 (1998-09-01), Sites et al.
patent: 5812811 (1998-09-01), Dubey et al.
patent: 5826109 (1998-10-01), Abramson et al.
patent: 5832260 (1998-11-01), Arora et al.
patent: 5881280 (1999-03-01), Gupta et al.
patent: 5887166 (1999-03-01), Mallick et al.
patent: 5913925 (1999-06-01), Kahle et al.
patent: 5933627 (1999-08-01), Parady
patent: 5961639 (1999-10-01), Mallick et al.
patent: 5999727 (1999-12-01), Panwar et al.
M. Franklin, “The Multiscalar Architecture,” Ph.D. Dissertation, Univ. of Wisconsin, 1993, pp. i, ii, v-ix, 109-134.
J. Smith et al., “The Microarchitecture of Superscaler Processors,” Proceedings of IEEE, vol. 83, No. 12, Dec. 1995, pp. 1609-1624.
D. Tullsen et al., “Simultaneous Multithreading: Maximizing On-Chip Parallelism,” The 22nd International Symposium on Computer Architecture, Jun. 1995, pp. 392-403.
G. Sohi et al., “Multiscaler Processors.” The 22nd Annual International Symposium on Computer Architecture, Jun. 1995, pp. 414-425.
E. Rotenberg et al., “Trace Processors,” The 30th International Symposium on Microarchitecture, Dec. 1997, pp. 138-148.
M. Franklin et al., “ARB: A Hardware Mechanism for Dynamic Reordering of Memory References. IEEE Transactions on Computers”, vol. 45, No. 5, May 1996, pp. 552-571.
J. Tsai et al., “The Superthreaded Architecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation,” Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, Oct. 1996, pp. 35-46.
P. Song, “Multithreading Comes of Age,” Microprocessor Report, Jul. 14, 1997, pp. 13-18.
Patent application Ser. No. 08/746,547, field Nov. 13, 1996, pending, “Processor Having Replay Architecture,” Inventor David Sager.
Q. Jacobson et al. “Path-Based Next Trace Prediction,” Proceedings of the 30th International Symposium on Microarchitecture, Dec. 1997, pp. 14-23.
Q. Jacobson et al. “Control Flow Speculation in Multiscalar Processors,” Proceedings of the 3rd International Symposium on High-Performance Computer Architecture, Feb. 1997, pp. 218-229.
R. Nair, “Dynamic path-based branch correlation,” Proceedings of the 28th International Symposium on Microarchitecture, Dec. 1995, pp. 15-23.
S. Palacharla et al., “Complexity-Effective Superscalar Processors,” The 24th Annual International Symposium on Computer Architecture, pp. 206-218, Jun. 1997.
M. Lipasti et al., “Value Locality and Load Value Prediction,” Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, Oct. 1996, ASPLOS-VII, pp. 138-147.
Written Opinion cited in a PCT Application corresponding to 08/992,375.
Aldous Alan K.
Ellis Richard L.
Intel Corporation
Patel Gautam R.
LandOfFree
Memory system for ordering load and store instructions in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory system for ordering load and store instructions in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory system for ordering load and store instructions in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3000120