Electrical computers and digital processing systems: processing – Processing architecture – Superscalar
Reexamination Certificate
1999-09-17
2001-08-07
Donaghue, Larry D. (Department: 2154)
Electrical computers and digital processing systems: processing
Processing architecture
Superscalar
C712S217000, C712S215000
Reexamination Certificate
active
06272617
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to superscalar reduced instruction set computers (RISC), more particularly, the present invention relates to a register renaming circuit for superscalar RISC computers.
2. Related Art
A more detailed description of some of the basic concepts discussed in this application is found in a number of references, including Mike Johnson,
Superscalar Microprocessor Design
(Prentice-Hall, Inc., Englewood Cliffs, N.J., 1991) (hereafter Johnson); John L. Hennessy et al.,
Computer Architecture—A Quantitative Approach
(Morgan Kaufmann Publishers, Inc., San Mateo, Calif., 1990). Johnson's text, particularly Chapters 2, 6 and 7 provide an excellent discussion of the register renaming issues addressed by the present invention.
A major consideration in a superscalar RISC processor is to how to execute multiple instructions in parallel and out-of-order, without incurring data errors due to dependencies inherent in such execution. Data dependency checking, register renaming and instruction scheduling are integral aspects of the solution. A detailed discussion of storage conflicts, register renaming and dependency mechanisms is found in commonly owned, co-pending U.S. Pat. No. 5,497,499, (hereafter referred to as the '499 patent).
The '499 patent discloses a register renaming circuit (RRC) having a fixed instruction window. In the fixed instruction window, dependency checking and resource assignment is done on the same set of instructions until all the instructions in the set are completed. This means that there is a fixed relationship between each instruction's position in the instruction stream and the instruction number used for resource assignment.
For example, in an instruction stream with an instruction window of 4 instructions every fourth instruction mapps to instruction A (i.e., the first instruction in the window). This technique makes re-mapping of instruction very simple. In this case a 4-to-1 multiplexer is all that is necessary for each resource to forward a single instruction to that resource. However, the fixed format requires that the instruction window be advanced by a fixed amount, which results in somewhat inefficient processing.
When an instruction retires (an instruction can retire after it has been executed without exception and when all previous instructions have been executed and their results are stored in the register file), its result is moved into a main register file (i.e., the programmable visible register file) and if any instructions were dependent on that instruction, their renamed sources are not needed anymore. In the architecture disclosed in the '499 patent, all instructions' sources are renamed every cycle. This renaming technique requires many comparators for performing the dependency checks. More specifically, the source register addresses of each instruction must be compared to the destination register addresses of all preceding instructions in the instruction window every cycle.
What is desired is a more efficient register renaming technique requiring less comparators and permitting the processor to execute instructions in parallel and out of order.
SUMMARY OF THE INVENTION
The present invention is directed to a system and method for performing register renaming of source registers on a per-cycle basis only for new instructions added to the instruction window in that cycle. The present invention thus reduces the total number of dependency check comparators necessary for performing register renaming.
A preferred embodiment of the present invention comprises storing the instructions in a variable advance instruction window, and assigning a tag to each instruction in the instruction window. The tag of each retired instruction is assigned to the next new instruction to be added to the instruction window. The results of instructions executed by the processor are stored in a temp buffer according to their corresponding tags to avoid output dependencies and anti-dependencies. The temp buffer therefore permits the processor to execute instructions out of order and in parallel.
Data dependency checks are performed only for each new instruction added to the instruction window. Operands of the instructions having input dependencies are often located in the temporary buffer, and the source register addresses of those instructions having dependencies are renamed according to the tags of the operands located in the temp buffer. The renamed source register addresses are then stored in a rename result register file.
REFERENCES:
patent: 4626989 (1986-12-01), Torii
patent: 4675806 (1987-06-01), Uchida
patent: 4722049 (1988-01-01), Lahti
patent: 4807115 (1989-02-01), Torng
patent: 4901233 (1990-02-01), Liptay
patent: 4903196 (1990-02-01), Pomerene et al.
patent: 4942525 (1990-07-01), Shintani et al.
patent: 5067069 (1991-11-01), Fite et al.
patent: 5072364 (1991-12-01), Jardine et al.
patent: 5109495 (1992-04-01), Fite et al.
patent: 5142633 (1992-08-01), Murray et al.
patent: 5167026 (1992-11-01), Murray et al.
patent: 5214763 (1993-05-01), Blaner et al.
patent: 5222244 (1993-06-01), Carbine et al.
patent: 5226126 (1993-07-01), McFarland et al.
patent: 5251306 (1993-10-01), Tran
patent: 5255384 (1993-10-01), Sachs et al.
patent: 5261071 (1993-11-01), Lyon
patent: 5278963 (1994-01-01), Hattersley et al.
patent: 5317720 (1994-05-01), Stamm et al.
patent: 5345569 (1994-09-01), Tran
patent: 5355457 (1994-10-01), Shebanow et al.
patent: 5371684 (1994-12-01), Iadonato et al.
patent: 5398330 (1995-03-01), Johnson
patent: 5442757 (1995-08-01), McFarland et al.
patent: 5448705 (1995-09-01), Ngyen et al.
patent: 5487156 (1996-01-01), Popescu et al.
patent: 5497499 (1996-03-01), Garg et al.
patent: 5524225 (1996-06-01), Kranich
patent: 5560032 (1996-09-01), Nguyen et al.
patent: 5561776 (1996-10-01), Popescu et al.
patent: 5574927 (1996-11-01), Scantlin
patent: 5590295 (1996-12-01), Deosoran et al.
patent: 5592636 (1997-01-01), Popescu et al.
patent: 5606676 (1997-02-01), Grochowski et al.
patent: 5619668 (1997-04-01), Zaidi
patent: 5625837 (1997-04-01), Popescu et al.
patent: 5627983 (1997-05-01), Popescu et al.
patent: 5708541 (1998-01-01), Popescu et al.
patent: 5737624 (1998-04-01), Garg et al.
patent: 5768575 (1998-06-01), McFarland et al.
patent: 5797025 (1998-08-01), Popescu et al.
patent: 5809276 (1998-09-01), Deosaran et al.
patent: 5832205 (1998-11-01), Kelly et al.
patent: 5832293 (1998-11-01), Popescu et al.
patent: 0 378 195 A3 (1990-08-01), None
patent: 0 515 166 (1992-11-01), None
patent: 0 533 337 A1 (1993-03-01), None
patent: WO 88/09035 (1988-11-01), None
patent: WO 91/20031 (1991-12-01), None
Keller, R.M., “Look-Ahead Processors,”Computing Surveys,vol. 7, No. 4, Dec. 1975, pp. 177-195.
Lam, M.S., “Instruction Scheduling For Superscalar Architectures,”Annu. Rev. Comput. Sci.,vol. 4, 1990, pp. 173-201.
Lightner et al. “The Metaflow Architecture,” p. 11, 12, 63, 64, 67, and 68, Jun. 1991,IEEE Micro Magazine.
Lightner, B.D. et al., “The Metaflow Lightning Chipset,” pp. 13-14 and 16, 1991IEEE Publication.
Melvin, S. and Patt, S., “Exploiting Fine-Grained Parallelism Through a Combination of Hardware and Software Techniques”,Proceedings From ISCA-18,pp. 287-296, May, 1990.
Murakami, K. et al., “SIMP (Single Instruction stream/Multiple instruction Pipelining): A Novel High-Speed Single-Processor Architecture,”ACM,1989, pp. 78-85.
Patt, Y.N. et al., “Critical Issues Regarding HPS, A High Performance Microarchitecture,”Proceedings of the 18th Annual Workshop on Microprogramming,Dec. 1985, pp. 109-116.
Patt, Y.N. et al., “HPS, A New Microarchitecture: Rationale and Introduction,”Proceedings of the 18th Annual Workshop on Microprogramming,Dec. 1985, pp. 103-108.
Patt, Y.N. et al., “Run-Time Generation of HPS Microinstructions From a VAX Instruction Stream,”Proceedings of MICRO 19 Workshop,New York, New York, Oct. 1986, pp. 1-7.
Peleg et al., “Future Trends in Microprocessors: Out-of-Order Execution, Spec. Branching and Their CISC Performance Potential”, Mar
Deosaran Trevor A.
Garg Sanjiv
Iadonato Kevin R.
Donaghue Larry D.
Seiko Epson Corporation
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
System and method for register renaming does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for register renaming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for register renaming will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2527909