Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or... – Scoreboarding – reservation station – or aliasing
Reexamination Certificate
1999-11-29
2003-04-22
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
Scoreboarding, reservation station, or aliasing
C712S237000, C711S211000, C711S213000, C711S144000, C711S204000
Reexamination Certificate
active
06553483
ABSTRACT:
BACKGROUND OF THE INVENTION
For modern processors there is a difference between logical registers and physical registers that actually store the data. Logical registers are labels defined by the instruction set architecture. These labels do not address specific hardware within a processor. Indeed, a logical register label may refer to a first register for a first instruction in a program and may refer to an entirely different register for another instruction. Physical registers are storage units within a processor core. Logical registers are mapped to physical registers. The mapping changes over time. Typically, the identity and use of physical registers cannot be determined by a processor's instruction set architecture.
For example, the instruction “MOV EAX, 0” (Store the value
0
in register EAX) does not refer to a physical register location in a processor. Instead, it refers to a “logical register,” a fictional register that may be mapped to various physical registers within a processor as the processor advances through executable program instructions. This property of modern processors is a well-known byproduct of out-of-order processing.
The inventors of the present invention noted that the values stored in physical registers often exhibit a high degree of redundancy. For example, consider an example where three variables are initialized to zero in a processor core. In traditional processors, the three variables each would occupy different physical registers. This is inefficient because, so long as the values are the same, the contents of the three variables could be stored in a single physical register. The other two registers could be used for other purposes. U.S. patent application Ser. No. 08/348,403, entitled “Unified Renaming Scheme,” filed Jul. 7, 1999, discloses a register renaming scheme that maps multiple logical registers to a single physical register.
A virtual naming scheme (sometimes referred to as “late binding”) has recently been proposed for physical registers. See, Gonzalez, et al., “Virtual Physical Registers,” Proc. 4th Int'l Symp. High Perf. Computer Architecture (February 1998). Under the virtual renaming scheme, physical registers are allocated for data generated during instruction execution after the data is generated. In traditional processors, physical locations had been allocated to instructions much earlier, when the instructions were loaded in the processor core. Because the virtual renaming techniques shorten the amount of time that a physical register is allocated to a particular instruction, Gonzalez's techniques permit a fixed number of physical registers to support a greater number of instructions than could have been supported when registers were allocated upon receipt of an instruction.
Accordingly, there is a need in the art for a virtual register renaming scheme that permits multiple logical registers that have the same value to map to a single physical register wherein that value is stored.
SUMMARY
Embodiments of the present invention provide a register allocation unit that, when results of a newly executed instruction are generated, determines whether the results match the value of previously stored data. When there is a match, the results are assigned to the memory location where the matching data is stored.
REFERENCES:
patent: 5535346 (1996-07-01), Thomas, Jr.
patent: 5546593 (1996-08-01), Kimura et al.
patent: 5692168 (1997-11-01), McMahan
patent: 5828860 (1998-10-01), Miyaoku et al.
patent: 6298435 (2001-10-01), Chan et al.
Gonzalez et al, “Virtual-Physical Registers”, 1998 Fourth International Symposium on High-Performance Computer Architecture, Las Vegas, Nevada, Feb. 1-4, 1998, IEEE Computer Society, Los Alamitos, California.
Gonzalez et al, “Virtual Registers”, Fourth International Conference on High-Performance Computing, Dec. 18-21, 1997, Bangalore, India, IEEE Computer Society, Los Alamitos, California.
Anderson et al, “The IBM System/360 Model 91:Machine Philosophy and Instruction-Handling”,IBM Journal of Research and Development, vol. 11, No. 1, Jan. 1967, pp. 8-24.
Butler et al, “An Area-Efficient Register Alias Table for Implementing HPS”, Proceedings of the 1990 Int'l. Conference on Parallel Processing, vol. 1 Architecture, Aug. 13-17, 1990, Pennsulvania State University Press, University Park, PA, pp. I-611 to I-612.
Butler et al, “A Comparative Performance Evaluation of Various State Maintenance Mechanisms”, Proceedings of the 26th Annual Int'l. Symposium on Microarchitecture, Dec. 1-3, 1993, Austin, TX, pp. 70-79.
Chrysos et al, “Memory Dependence Prediction Using Store Sets”, Proceedings of the 25th Annual Int'l. Symposium on Computer Architecture, Jun. 27-Jul. 1, 1998, Barcelona, Spain, pp. 142-153.
Farkas et al, “Register File Design Considerations in Dynamically Scheduled Processors”,WRL Research Report 95/10, Nov. , 1995, Palo Alto, CA.
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.
Gallagher et al, “Dynamic Memory Disambiguation using the Memory Conflict Buffer”, Proceedings of the 6th Int'l. Conference on Architectural Support for Programming Languages and Operating Sytems, Oct. 4-7, 1994, San Jose, CA, pp. 183-193.
Keller, Robert, “Look-Ahead Processors”,Computing Surveys, vol. 7, No. 4, Dec. 1975, New York, NY, pp. 177-195.
Hwu et al, “Checkpoint Repair for High-Performance Out-of-Order Machines”, vol. C-36, No. 12, Dec. 1987, New York, NY, pages 177-195.
Pentium® Prop Family Developer's Manual, vol. 2: Programmer's Referance Manual, Jan. 1996, Chapters 1 and 2.
Johnson, Mike,Superscalar Microprocessor Design, 1991, Chapters 10 and 11, Englewood Cliffs, NJ.
Lipasti et al, “Exceeding the Dataflow Limit Via Value Prediction”, Proceedings of the 29th Annual IEEE/ACM Int'l. Symposium on Microarchitecture, Dec. 2-4, 1996, pp. 226-237.
Martin et al, “Exploiting Dead Value Information”, Proceedings of the 30th Annual IEEE/ACM Int'l. Symposium on Microarchitecture, Dec. 1-3,
Moshovos et al, “Dynamic Speculation and Synchronization of Data Dependence”, Proceedings of the 24th Annual Int'l. Symposium on Computer Architecture, Jun. 2-4, 1997, Denver, CO, pp. 181-193.
Moshovos et al, “Streamlining Inter-Operation Memory Communication Via Data Dependence Prediction”, Proceedings of the 30 Annual IEEE/ACM Int'l. Symposium on Microarchitecture, Dec. 1-3, 1997, Research Triangle park, NC, pp. 235-245.
Moudgill et la, “Register Renaming and Dynamic Speculation: An Alternative Approach”, Proceedings of the 26th Annual Int'l. Symposium on Microarchitecture, Dec. 1-3, 1993, Austin, TX, pp. 202-213.
Patt et al, “HPS, A New Microarchitecture: Rationale and Introduction”, Proceedings of the 18th Annual Workshop on Microprogramming, Pacific Grove, CA, vol. 16, No. 4, Dec. 3-6, 1985, pp. 103-108.
Smith et al, “Implementation of Precise Interrupts in Piplined Processors”, Proceedings of the 12th Annual Int'l. Symposium on Computer Architecture, Jun. 17-19, 1985, Boston, MA, pp. 36-44.
Smith et al, “The Microarchitecure of Superscalar Processors”,Proceedings of the IEEE, Dec. 1995, pp. 1609-1624.
Sodami et al., “Dynamic Instruction Reuse”, Conference Proceedings of the 24th Annual Int'l. Symposium on Computer Architecture, Jun. 2-4, 1997, Denver, CO, pp. 194-205.
Tjaden et al, “Detection and Parallel Execution of Independent Instructions”,IEEE Transactions on Computers, vol. C-19, No. 10, Oct. 1970, pp. 889-895.
Tyson et al, “Improving the Accuracy and Performance of Memory Communication Through Renaming”, Proceedings of the 30th Annual IEEE/ACM Int'l. Symposium on Microarchitecture, Dec. 1-3, 1997, Research Triangle Park, NC, pp. 218-227.
Weiss et al, “Instruction Issue Logic in Pipelined Supercomputers”, vol. C-33 No. 11, Nov. 1984, pp. 1013-1022.
Jourdan et al, “A Novel Renaming Scheme to Exploit Value Temporal Locality through Physical Register Reuse and Unification”, Proceedings 31st Annual ACM/IEEE Int'l Symposium on Micr
No affiliations
LandOfFree
Enhanced virtual renaming scheme and deadlock prevention... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced virtual renaming scheme and deadlock prevention..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced virtual renaming scheme and deadlock prevention... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3079543