Exploiting untagged branch prediction cache by relocating branch

Details Exploiting untagged branch prediction cache by relocating branch Exploiting untagged branch prediction cache by relocating branch

1996-05-14

1998-02-24

Kim, Kenneth S.

395580, 395587, 395708, 395709, G06F 945

Patent

active

057218935

ABSTRACT:
An untagged branch prediction cache is exploited by relocating branches during a final pass in the compilation process, after all other optimizations have been applied, where a pass is made over the instructions in each subprogram, and all branches that use the branch prediction cache (BPC) are placed into buckets, where each bucket corresponds to a position in the BPC. Recorded with each branch is its expected direction (taken, not taken), based either on profiling data or on static heuristics. Each bucket is then inspected. For buckets containing branches whose predicted directions conflict, an attempt is made to move some of those branches to another bucket. If other branches' positions are affected, the bucket inspection process is restarted, after recalculation of the bucket positions of all BPC branches. Branches that have matching predicted directions, but that currently fall into separate buckets, may be moved into the same bucket, so that the histories of branches can reinforce one another. Heuristics may be used to dictate which branches are considered, what code transformations are used to relocate branches, and whether both conflict avoidance and match enhancement are performed.

REFERENCES:
patent: 5450588 (1995-09-01), Hoxey
patent: 5511198 (1996-04-01), Hotta
patent: 5530964 (1996-06-01), Alpert et al.
patent: 5568623 (1996-10-01), Ogawa
patent: 5596732 (1997-01-01), Hosoi
patent: 5655122 (1997-08-01), Wu
Patterson, David A. et al., "Computer Architecture A Quantitative Approach", Second Edition, Chapter 4, Advances Pipefining and Instruction-Level Parallelism, Section 4.3, Reducing Branch Penalties with Dynamic Hardware Prediction, pp. 262-278.
Pan, Shien-Tai et al., "Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation," ASPLOS V -- Oct. 1992.
Lee et al., "Branch Prediction Strategies and Branch Target Buffer Design," Computer, Jan. 1984, pp. 6-22.
Smith, James E., "A Study of Branch Prediction Strategies," 1981 IEEE, pp. 135-148.

Affiliated with

Also associated with

Rating

Exploiting untagged branch prediction cache by relocating branch does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Exploiting untagged branch prediction cache by relocating branch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exploiting untagged branch prediction cache by relocating branch will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1881416