Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-08-09
2001-05-15
Eng, David Y. (Department: 2155)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06233679
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a method and system for branch prediction in a computer system. The method and the system are particularly well suited for use in processors executing programs running for a long time such as the ones used in telecommunication systems.
BACKGROUND OF THE INVENTION AND PRIOR
Branch prediction mechanisms can be loosely divided into static branch prediction and dynamic branch prediction mechanisms.
Static branch prediction is implemented by including a prediction within the branch instruction, i.e. a bit that gives an indication to the processor executing the conditional branch instruction whether a conditional branch is likely to be taken or not. This bit is set by the compiler based on either heuristics, i.e. a conditional branch out of loops is most often not taken, or based on feedback from program execution. The feedback from execution is collected by means of having a program inserting instructions around each conditional branch which records whether the branch is taken or not. The program is then executed and statistics are collected. Thereupon, the program is compiled once again and the collected branch statistics is used to set branch prediction.
Dynamic branch prediction collects branch statistics in separate data structures in the processor, for example in branch history tables, BHTs, or in separate bits in the processor instruction cache or memory. Usually one or two bits in an instruction cache line are used.
The disadvantage with these methods are:
Setting static branch prediction based on heuristics does not give optimal performance.
Setting static branch prediction based on feedback gives a number of extra steps in the program generation and works well only as long as the branch statistics collected are similar to real execution in systems using varying and different data sets.
Dynamic branch prediction adds cost for additional data structures within the CPU. Due to physical limitations, as well as costs, these structures can not include data for all conditional branch instructions in the program and several data branches have to share entries within a BHT. The performance of dynamic branch prediction then depends on the statistical behaviour of the program. For example, if the lower bits of the address of the conditional branch instruction are used to select an entry in the BHT, the performance can depend on whether or not the program has been loaded on addresses that make more than one often executed branch.
In telecommunication applications, programs are loaded into the system and will be used continuously for a long time, i.e. usually at least for weeks, until the system is reloaded with a new revision of the program. The execution can in most cases be expected to have the same statistics during that time.
Furthermore, U.S. Pat. No. 5,367,703 describes a branch prediction mechanism in a superscalar processor system. The mechanism uses branch history tables which include a separate branch history for each fetch position within a multi-instruction access. A prediction field consisting of two bits is used for determining whether a particular branch is to be taken or not. The value of the two bits is incremented or decremented in response to a branch being taken or not.
U.S. Pat. No. 5,423,011 discloses an apparatus consisting of an associated memory in which branch prediction bits are stored, cache lines and comparison means for matching stored prediction bits with their corresponding cache lines.
In the patent application GB 2 283 595 a branch prediction circuitry which can operate in one of the two user selectable modes is described.
SUMMARY
It is an object of the present invention to provide a method and a system which overcomes the problems as outlined above, and which can provide a branch prediction mechanisms which can take advantage of the fact that a program is run for a long time.
This object is obtained with a semi-static branch prediction mechanism comprising three parts:
1) a branch prediction bit in the instruction, or an extra bit in the instruction memory,
2) a hardware counter that can collect branch statistics for a specific conditional branch instruction in the program memory, and
3) a background program.
The branch prediction mechanism then operates as follows: The background program, e.g. a program having a low priority, a periodic recurrent program, etc., reads the instruction memory to locate conditional branch instructions.
When finding a conditional branch instruction the background program starts the hardware counter to record branch statistics for that branch and goes to sleep for a while.
After waking up, the background program uses the collected statistics to set the prediction in the conditional branch instruction in the program memory.
A system operating in such a manner has several advantages, such as:
It is transparent for software, and even if the instruction in the program memory is used for storing branch prediction information, there is no impact on any software development tools and the way of storing information can be changed between CPU implementations.
The hardware design is simple.
The hardware cost is low, since no separate data structures are needed for branch prediction.
The method makes it possible to predict multiple conditional branch instructions in parallel, which for example can be needed in superscalar processors for getting good branch prediction accuracy.
The program performance depends on the execution statistics for the predicted branch only, not on interaction with other conditional branch instructions in other programs.
However, there are some conditions that must be met for the semi-static branch prediction mechanism to work well, i.e. to provide a good branch prediction.
i) The sample program must be executed for a relatively long time and have approximately the same behaviour during that time since it takes some time for the background program to scan the program for all conditional branch instructions, and collect reliable statistics.
ii) It must be possible to include the branch prediction bit.
iii) It must be possible to include a hardware counter or counters for collecting execution statistics.
The APZ processors used in the AXE telephone switch manufactured by Ericsson fulfil all these requirements. The hardware and software are custom designed and most conditional branch instructions have several unused bits, which can be used for storing branch prediction.
Furthermore, the background program and the counters can be used for updating a branch history table (BHT). Instead of updating the prediction bit in a conditional branch instruction after each time new statistics are collected, the background program is used for updating the prediction field corresponding to the instruction in the BHT.
Such an implementation can, for example, be advantageous when it is not possible to include the branch prediction bit.
REFERENCES:
patent: 4334268 (1982-06-01), Boney et al.
patent: 5051944 (1991-09-01), Fetterrolf et al.
patent: 5367703 (1994-11-01), Levitan
patent: 5394529 (1995-02-01), Brown, III et al.
patent: 5423011 (1995-06-01), Blaner et al.
patent: 5440704 (1995-08-01), Itomitsu et al.
patent: 5742804 (1998-04-01), Yeh et al.
patent: 5835745 (1998-11-01), Sagar et al.
patent: 5857104 (1999-01-01), Natarjan et al.
patent: 5887159 (1999-03-01), Burrows
patent: 5890008 (1999-03-01), Panwar et al.
patent: 5933628 (1999-08-01), Chang
SIGPLAN Notice, vol. 29, No. 11, 1994, Cliff Young et al., “Improving the Accuracy of Static Branch Prediction Using Branch Correlation”.
SIGPLAN Notice, vol. 27, No. 9, 1992 Shien-Tai Pan et al., “Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation”.
Computer Architecture News, vol. 24, No. 2, 1996, (Philadelphia, Pennyslvania, USA), Nicolas Gloy et al., “An Analysis of Dynamic Branch Prediction Schemes on System Workloads”.
Eng David Y.
Nixon & Vanderhye P.C.
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Method and system for branch 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 system for branch prediction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for branch prediction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2474204