Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2011-01-11
2011-01-11
Coleman, Eric (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S233000
Reexamination Certificate
active
07870371
ABSTRACT:
A frequency-based prediction of indirect jumps executing in a computing environment is provided. Illustratively, a computing environment comprises a prediction engine that processes data representative of indirect jumps performed by the exemplary computing environment according to a selected frequency-based prediction paradigm. Operatively, the exemplary prediction engine can keep track of targets, in a table, taken for each indirect jump and program context (e.g., branch history and/or path information) of an exemplary computing program. Further, the prediction engine can also store a frequency counter associated with each target in the exemplary table. Illustratively, the frequency counter can record the number of times a target was taken in the recent past executions of an observed one or more indirect jump. The prediction engine can supply the target address of an indirect jump based on the values of the frequency counters of each stored target address.
REFERENCES:
patent: 5163140 (1992-11-01), Stiles et al.
patent: 5740416 (1998-04-01), McMahan
patent: 5752069 (1998-05-01), Roberts et al.
patent: 5812839 (1998-09-01), Hoyt et al.
patent: 5822559 (1998-10-01), Narayan et al.
patent: 5832260 (1998-11-01), Arora et al.
patent: 5848268 (1998-12-01), Matsuo
patent: 5878255 (1999-03-01), Tran et al.
patent: 6092187 (2000-07-01), Killian
patent: 6170054 (2001-01-01), Poplingher
patent: 6233678 (2001-05-01), Bala
patent: 6327704 (2001-12-01), Mattson et al.
patent: 6560693 (2003-05-01), Puzak et al.
patent: 7111096 (2006-09-01), Banning et al.
patent: 2003/0065912 (2003-04-01), Hum et al.
patent: 2003/0182543 (2003-09-01), Keller et al.
patent: 2005/0262332 (2005-11-01), Rappoport et al.
patent: 2006/0190924 (2006-08-01), Bruening et al.
Hao, E., etal., Increasing the Instruction Fetch Rate via Block Structured Instruction Set Architectures, Intl. Journal of Parallel Programming, Plenum Publishing Corp., vol. 26, No. 4, pp. 449-478.
Chang, Po-Yung etal., Target Prediction for Indirect Jumps, 1997, ACM, pp. 274-283.
McFarling, Scott, Combining Branch Predictors,Jun. 1993, Digital Western research Laboratory, 22 pages.
Brad Calder, et al. Fast & Accurate Instruction Fetch and Branch Prediction. 1994 Intl. Symp. on Computer Architecture, Chicago, Il. Apr. 1994. http://www.cs.ucsd.edu/˜calder/papers/ISCA-94.pdf. Last accessed Oct. 1, 2007, 10 pages.
Marat Boshernitsan, et al. ROE: Runtime Optimization Environment, Dec. 12, 1998. http://66.102.1.104/scholar?hl=en&lr=&q=cache:EVXe1d1OoVYJ:www.cs.berkeley.edu/˜efros/projects/cs252.ps.gz. Last accessed Oct. 1, 2007, 27 pages.
Karel Driesen. Efficient Polymorphia Calls http://www.cs.mcgill.ca/˜karel/efficient.polymorphic.calls.pdf. Last accessed Oct. 1, 2007, 231 pages.
Brad Calder, et al. Reducing Indirect Function Call Overhead in C++ Programs. ACM Principles and Practice of Programming Languages, Portland, Oregon 1994. http://www/cs/ucsd.edu/˜calder/papers/POPL-94.pdf. Last accessed Oct. 1, 2007, 11 pages.
Joao Jose Alberto
Mutlu Onur
Coleman Eric
Microsoft Corporation
Turocy & Watson LLP
LandOfFree
Target-frequency based indirect jump prediction for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Target-frequency based indirect jump prediction for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Target-frequency based indirect jump prediction for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2698218