Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2007-12-31
2010-10-19
Chan, Eddie P (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
07818551
ABSTRACT:
Systems and methods are provided to detect instances where dynamic predication of indirect jumps (DIP) is considered to be ineffective utilizing data collected on the recent effectiveness of dynamic predication on recently executed indirect jump instructions. Illustratively, a computing environment comprises a DIP monitoring engine cooperating with a DIP monitoring table that aggregates and processes data representative of the effectiveness of DIP on recently executed jump instructions. Illustratively, the exemplary DIP monitoring engine collects and processes historical data on DIP instances, where, illustratively, a monitored instance can be categorized according to one or more selected classifications. A comparison can be performed for currently monitored indirect jump instructions using the collected historical data (and classifications) to determine whether DIP should be invoked by the computing environment or whether to invoke other indirect jump prediction paradigms.
REFERENCES:
patent: 5923863 (1999-07-01), Adler et al.
patent: 5956758 (1999-09-01), Henzinger et al.
patent: 6237077 (2001-05-01), Sharangpani et al.
patent: 6367004 (2002-04-01), Grochowski et al.
patent: 6754812 (2004-06-01), Abdallah et al.
patent: 6988183 (2006-01-01), Wong
patent: 7051193 (2006-05-01), Wang et al.
patent: 7085919 (2006-08-01), Grochowski et al.
patent: 7178011 (2007-02-01), Seal et al.
patent: 7210025 (2007-04-01), Uht et al.
patent: 2007/0288730 (2007-12-01), Luick
patent: 2010/0095102 (2010-04-01), Toyoshima et al.
Kim et al. (Diverge-Merge Processor (DMP): Dynamic Predicated Execution of Complex Control-flow Graphs Based on Frequently Executed Paths); MICRO'06; 2006; 12 pages.
Klauser et al. (Klauser) (Selective Eager Execution on the PolyPath Architecture); Proceedings of the 25th annual international symposium on Computer architecture (ISCA '98); pp. 250-259; Year of Publication: 1998.
Pagiamtzis et al. (Pagiamtzis) (Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey); IEEE Journal of Solid-State Circuits, vol. 41, No. 3, Mar. 2006, pp. 712-727.
Joao et al. (Joao) (Dynamic Predication of Indirect Jumps); IEEE Computer Architecture Letters, May 2007, 4 pages.
Heil et al. (Selective Dual Path Execution) Technical Report, University of Wisconsin, Madison, Nov. 1996., 29 pages.
Jacobsen et al. (Assigning Confidence to Conditional Branch Predictions); Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture; pp. 142-152; Year of Publication: 1996.
Grunwald et al. (Confidence Estimation for Speculation Control) ; Proceedings of the 25th annual international symposium on Computer architecture (ISCA '98); pp. 122-131.
Klauser et al. (Dynamic Hammock Predication for Non-predicated Instruction Set Architectures); Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques; 8 pages.
Kim (Adaptive Predication via Compiler-Microarchitecture Cooperation); Dissertation at UT: Austin, Aug. 2007, 192 pages.
Joao et al. (Improving the Performance of Object-Oriented Languages with Dynamic Predication of Indirect Jumps); ASPLOS 2008, Mar. 1-5, 2008, pp. 80-90.
Tyson et al. (Limited Dual Path Execution); CSE-TR 346-97, University of Michigan, 1997; 14 pages.
Ahuja et al. (Multipath Execution: Opportunities and Limits); In Proceedings of the 1998 International Conference on Supercomputing, Jul. 1998; 8 pages.
Tang et al. (RIMP: Runtime Implicit Predication); APPt 2005, LNCS 3756, pp. 71-80, 2005.
Klauser et al. (Selective Branch Inversion: Confidence Estimation for Branch Predictors) ; International Journal of Parallel Programming, vol. 29, No. 1, 2001, 30 pages.
Belgaumkar (General Dynamic Predication for SuperScalar Processors) ; Thesis at the Michigan Technological University, 2003; 64 pages.
Farooq et al. (Value Based BTB Indexing for Indirect Jump Prediction); The 16th International Symposium on High-Performance Computer Architecture. Jan. 2010; 11 pages.
Hyesoon Kim, et al. Wish Branches: Combining Conditional Branching and Predication for Adaptive Predicated Execution http://131.107.65.76/˜onur/pub/kim—micro05.pdf. Last accessed Oct. 1, 2007, 12 pages.
Po-Yung Chang, et al. Target Prediction for Indirect Jumps. ISCA '97, Denver, CO, USA. ACM 0-89791-901-7/97/0006 http://ieeexplore.ieee.org/iel3/4807/13287/00604707.pdf?tp=&isnumber=13287&arnumber=604707. Last accessed Oct. 3, 2007, 10 pages.
Hyesoon Kim, et al. Profile-assisted Compiler Support for Dynamic Predication in Diverge-Merge Processors https://research.microsoft.com/˜onur/pub/kim—cgo07.pdf. Last accessed Oct. 3, 2007, 12 pages.
Joao Jose A
Mutlu Onur
Chan Eddie P
Microsoft Corporation
Turocy & Watson LLP
Vicary Keith
LandOfFree
Feedback mechanism for dynamic predication of indirect jumps does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Feedback mechanism for dynamic predication of indirect jumps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Feedback mechanism for dynamic predication of indirect jumps will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4173178