Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2005-04-05
2005-04-05
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06877089
ABSTRACT:
Apparatus and methods implemented in a processor semiconductor logic chip for providing novel “hint instructions” that uniquely preserve and reuse branch predictions replaced in a branch history table (BHT). A branch prediction is lost in the BHT after its associated instruction is replaced in an instruction cache. The unique “hint instructions” are generated and stored in a unique instruction cache which associates each hint instruction with a line of instructions. The hint instructions contains the latest branch history for all branch instructions executed in an associated line of instructions, and they are stored in the instruction cache during instruction cache hits in the associated line. During an instruction cache miss in an instruction line, the associated hint instruction is stored in a second level cache with a copy of the associated instruction line being replaced in the instruction cache. In the second level cache, the copy of the line is located through the instruction cache directory entry associated with the line being replaced in the instruction cache. Later, the hint instruction can be retrieved into the instruction cache when its associated instruction line is fetched from the second level cache, and then its associated hint instruction is also retrieved and used to restore the latest branch predictions for that instruction line. In the prior art this branch prediction would have been lost. It is estimated that this invention improves program performance for each replaced branch prediction by about 80%, due to increasing the probability of BHT bits correctly predicting the branch paths in the program from about 50% to over 90%. Each incorrect BHT branch prediction may result in the loss of many execution cycles, resulting in additional instruction re-execution overhead when incorrect branch paths are belatedly discovered.
REFERENCES:
patent: 5669001 (1997-09-01), Moreno
patent: 5699536 (1997-12-01), Hopkins et al.
patent: 5887159 (1999-03-01), Burrows
patent: 6108775 (2000-08-01), Shiell et al.
patent: 6427192 (2002-07-01), Roberts
patent: 798632 (1997-10-01), None
Handy, “The Cache Memory Book, 2ndEdition,” 1998, pp. 18-19.*
E. Rotenberg, S. Bennett and J. Smith, Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching, Apr. 11, 1996, pp. 1-48.
T. M. Conte, K. N. Menezes, P. M. Mills and B. A. Patel, “Optimization of Instruction Fetch Mechanisms for High Issue Rates,” in Proceedings of the 22nd Annual International Symposium on Computer Architecture, (Santa Margherita, Italy), Jun. 1995, pp. 333-344.
Tse-Yu Yeh, D. Marr and Y. Patt, “Increasing the Instruction Fetch Rate Via Multiple Branch Prediction and a branch Address Cache,” Procedings of the 7th ACM International Conference on Supercomputing, Jul. 1993, pp. 67-76.
J. E. Smith, A Study of Branch Prediction Strategies, in 8th Annual International Symposium of Computer Architecture, ACM, 1981, pp. 202-215.
Tse-Yu Yeh and Y. Patt, “A Comparison of Dynamic Branch Predictors That Use Two Levels of Branch History”, in 20th Annual International Symposium of Computer Architecture, ACM, 1993, pp. 257-266.
T. Ball and J R. Larus, “Branch Prediction for Free”, in 1993 SIGPLAN Conference on Programming Languages Design and Implementation, ACM, Jun. 1993, pp. 1-28.
Augspurger Lynn L.
Chan Eddie
Goldman Bernard M.
Huisman David J
International Business Machines - Corporation
LandOfFree
Branch prediction apparatus and process for restoring... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Branch prediction apparatus and process for restoring..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branch prediction apparatus and process for restoring... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3434911