Software branch prediction filtering for a microprocessor

Details Software branch prediction filtering for a microprocessor Software branch prediction filtering for a microprocessor

2001-04-10

2002-04-16

Follansbee, John A. (Department: 2154)

Electrical computers and digital processing systems: processing

Processing control

Branching

Reexamination Certificate

active

06374351

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to microprocessors, and more particularly, to branch prediction for a microprocessor.
BACKGROUND
Reduced Instruction Set Computing (RISC) microprocessors are well known. RISC microprocessors are characterized by a smaller number of instructions, which are relatively simple to decode, and by having all arithmetic/logic operations be performed register-to-register. RISC instructions are generally of only one length (e.g., 32-bit instructions). RISC instruction execution is of the direct hardwired type, as opposed to microcoding. There is a fixed instruction cycle time, and the instructions are defined to be relatively simple so that each instruction generally executes in one relatively short cycle.
A RISC microprocessor typically includes an instruction for a conditional branch operation. I.e., if a certain condition is present, then branch to a given location. It is known that a relatively small number of branch operations cause most of the branch mispredictions. For example, it has been suggested that 80 percent of the branch mispredictions result from 20 percent of the branch instructions for a given processor. Other branch operations are relatively easy to predict. For example, if an array access is preceded by a check for a valid array access, the check for a valid array access is accomplished in a typical RISC microprocessor by executing multiple conditional branches. These branches are generally easy to predict.
SUMMARY
Speed of execution is highly dependent on the sequentiality of the instruction stream executed by the microprocessor. Branches in the instruction stream disrupt the sequentiality of the instruction stream executed by the microprocessor and generate stalls while the prefetched instruction stream is flushed and a new instruction stream begun.
Accordingly, the present invention provides software branch prediction filtering for a microprocessor. For example, the present invention provides a cost-effective and high performance implementation of software branch prediction filtering executed on a microprocessor that performs branch operations. By providing the software branch prediction filtering, many easy-to-predict branches can be eliminated from a hardware-implemented branch prediction table thereby freeing up space in the branch prediction table that would otherwise be occupied by the easy-to-predict branches. In other words, easy-to-predict branches waste entries in a limited-size branch prediction table and, thus, are eliminated from the branch prediction table. This robust approach to software branch prediction filtering provides for improved branch prediction, which is desired in various environments, such as a Java™ computing environment. For example, this method can be used for various instruction sets such as Sun Microsystems, Inc.'s UltraJava™ instruction set.
In one embodiment, a method for software branch prediction filtering for a microprocessor includes determining whether a conditional branch operation is “easy”-to-predict and predicting whether to execute the branch operation based on software branch prediction. However, “hard”-to-predict branches are predicted using a hardware branch prediction (e.g., a limited size hardware branch prediction table).
Other aspects and advantages of the present invention will become apparent from the following detailed description and accompanying drawings.


REFERENCES:
patent: 4370711 (1983-01-01), Smith
patent: 4435756 (1984-03-01), Potash
patent: 5564118 (1996-10-01), Steely, Jr. et al.
patent: 5655122 (1997-08-01), Wu
patent: 5802602 (1998-09-01), Rahman et al.
patent: 5805876 (1998-09-01), Bose et al.
patent: 5848269 (1998-12-01), Hara
patent: 5928358 (1999-07-01), Takayama et al.
patent: 5933628 (1999-08-01), Chang
patent: 6115809 (2000-09-01), Mattson, Jr. et al.

Affiliated with

Also associated with

Rating

Software branch prediction filtering for a microprocessor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Software branch prediction filtering for a microprocessor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Software branch prediction filtering for a microprocessor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2903899