Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2002-02-22
2004-06-29
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S241000
Reexamination Certificate
active
06757814
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems and more particularly to computer system processors that support predication and perform predicate prediction.
BACKGROUND OF THE INVENTION
A processor manipulates and controls the flow of data in a computer system. Increasing the speed of the processor will tend to increase the computational power of the computer. Processor designers employ many different techniques to increase processor speed to create more powerful computers for consumers. One technique for increasing processor speed is called predication.
Predication is the conditional execution of instructions depending on the value of a variable called a predicate. For example, consider the two instructions:
COMPARE a, b=P
IF (P) THEN c=a+b
The first instruction, COMPARE a, b=P, determines a value for the predicate P. For example, if a is equal to b, then the value of predicate P is “True”, and if a is not equal to b, then the value of predicate P is “False.” “True” and “False” are typically represented in a computer system as single bit values “1” and “0”, respectively (or “0” and “1”, respectively, in a negative logic implementation).
The second instruction, IF (P) THEN c=a+b, includes two parts. The first part, IF (P) THEN, predicates (or conditions) the second part, c=a+b, on the value of predicate P. If P is true (e.g. a “1”), then the value of c is set equal to the value of a+b. If P is false (e.g. a “0”), then the second part of the instruction is skipped and the processor executes the next sequential instruction in the program code.
Unfortunately, the compare instruction, COMPARE a, b=P, can take a lengthy amount of time to process. Because of this, the execution of subsequent instructions in the program code sequence may be delayed until the compare instruction is resolved.
SUMMARY OF THE INVENTION
A new method and apparatus for performing predicate prediction is described. In one method, both a predicted predicate value for a predicate and a confidence value for the predicted predicate value are determined.
Other features and advantages of the present invention will be apparent from the accompanying drawings and the detailed description that follows.
REFERENCES:
patent: 4578750 (1986-03-01), Amdahl et al.
patent: 4967351 (1990-10-01), Zmyslowski et al.
patent: 4999800 (1991-03-01), Birger
patent: 5857104 (1999-01-01), Natarjan et al.
patent: 5903750 (1999-05-01), Yeh et al.
patent: 6009512 (1999-12-01), Christie
patent: 6021487 (2000-02-01), Maliszewski
patent: 6115808 (2000-09-01), Arora
patent: 0 855 645 (1998-07-01), None
patent: WO 97/48042 (1997-12-01), None
patent: WO 98/08160 (1998-02-01), None
patent: WO 99/14667 (1999-03-01), None
August et al., “Architectural Support for Compiler-Synthesized Dynamic Branch Prediction Strategies: Rationale and Initial Results”,Third International Symposium on High-Performance Computer Architecture, IEEE, pp. 84-93, Feb. 1-5, 1997.*
Manne et al., “Pipeline Gating: Speculation Control for Energy Reduction”,Proceedings of the 25th Annual International Symposium on Computer Architecture, IEEE, pp. 132-141, Jun. 27-Jul. 1, 1998.*
Pnevmatikatos et al., “Guarded Execution and Branch Prediction in Dynamic ILP Processors”,Proceedings of the 21st Annual International Symposium on Computer Architecture, IEEE, pp. 120-129, Apr. 18-21, 1994.*
Mahlke et al., “Characterizing the Impact of Predicated Execution on Branch Prediction,” Proceedings of the 27th Annual International Symposium Microarchitecture, Micro-27, IEEE, pp. 217-227, Nov. 30-Dec. 2, 1994.*
Dulong, et al.,An Overview of the Intel ® 1A-64 Compiler,Technology Journal Q4, 1999, pp. 1-15.
Intel ® Itanium™ Architecture Software Developer's Manual, Part II: Optimization Guide for the Intel ® Itanium™ Architecture,Predication, Control Flow, and Instruction Stream,vol. 1: Application Architecture, Revision 2.0, Dec. 2001, pp. 1:129, 1:155-1:163.
Intel® Itanium™ Processor, Product Highlights, Copyright © 2001, Intel Corporation.
Tom R. Halfhill,Beyond Pentium II,BYTE.com, Dec. 1997, pp. 1-10.
Jim Turley,64-Bit CPUs: What You Need To Know,Extreme Tech, Feb. 8, 2002, pp. 1-26.
Nicholas P. Carter, ECE 412-Advanced Computer Architecture, Lecture 4:Predication,Sep. 13, 2000, pp. 1-27.
S.A. Mahika, “Effective Compiler Support for Predicated Execution Using the Hyperbolic”, 1992 IEEE, pp. 45-54.
K.C. Tal et al., “Evaluation of a predicate -based software testing strategy”, IBM Systems Journal, vol. 33, No. 3, pp. 445-457.
Jacobsen et al., “Assigning Confidence to Conditional Branch Predictions,”Proceedings of the29th Annual IEEE/ACM International Symposium on Microarchitecture, pp.142-152, Dec. 2-4, 1996.
Grunwald et al., “Confidence Estimation for Speculation Control”Proceedings of the25th Annual International Symposium on Computer Architecture, pp. 122-131, Jun. 27-Jul. 2, 1998.
Grochowski Edward T.
Kling Ralph M.
Mulder Hans J.
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Treat William M.
LandOfFree
Method and apparatus for performing predicate prediction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing predicate prediction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing predicate prediction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3352123