Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-01-09
2001-07-03
Follansbee, John A. (Department: 2154)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06256729
ABSTRACT:
TRADEMARK NOTICE
Sun, Spring, Solaris, Sunsoft, and SunOS are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks are used under license and are trademarks or registered trademarks of SPARC International, Inc. in the United States of America and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.
BACKGROUND OF THE INVENTION
The present invention relates to out-of-order instruction execution. In particular, the present invention relates to branch instructions that are executed out-of-order and to resolving mispredicted branches.
A commonly used technique for increasing pipelined microprocessor performance has been to execute instructions in an order other than a sequential order, i.e. out-of-order. Typically, pipelined processors supporting out-of order instruction execution include instruction scheduling units that decide which instructions to execute and in which order such instructions are executed.
When branch instructions are included, instruction fetch units typically include branch prediction units. Branch instructions typically include two addresses, a target address (TA) and a fall-through address (FA). A processor is instructed to jump to the TA for the next instruction to be executed when a branch is taken, and the processor is instructed to jump to the FA, which is typically the next sequential address in the program order, for the next instruction to be executed when the branch is not taken. Typically, branch prediction units predict whether branches are taken or not taken and/or predict a TA for the branches.
Problems arise with out-of-order execution schemes when branch instructions are included. For example, typically only upon completion of execution and pending retirement of a branch instruction is the processor able to determine a direction, whether a branch was taken or not taken. Only after the actual directions are determined or actual TAs are determined can the processor determine whether the branch predictions were correct. If the branch prediction was incorrect, i.e. a branch was taken that should not have been taken, the predicted TA is not the same as the actual TA, etc, then the pipeline will typically be stopped, the instructions issued after the branch instruction flushed from the pipeline, and the processor restarted according to the actual branch result. Because a typical processor must wait until the branch instruction is actually executed and awaiting retirement, before the instruction at the new TA can be fetched, many processing cycles are wasted.
Other drawbacks with typical pipelined processors that support branch predictions are that large amounts of data must be stored in order to allow for the processor to restart properly. Typically, all instructions including branch instructions being processed in the pipeline are stored in a “central instruction window” in a single memory. However, branch instructions require the storage of different data than conventional instructions and thus require the central instruction window to be increased in word size (bits) to store the branch instruction specific data. Further, with the additional storage of branch instructions, execution units require additional parsing logic to decode the additional fields and data. Thus, storage of branch instruction related data requires a great increase in memory size and logic.
The above problem is greatly magnified as the depth of the central instruction window increases, i.e. the number of instructions in an instruction pipeline increases. Another drawback is that typical pipeline processors have great difficulty resolving more than one branch instruction per clock cycle.
What is needed are improved methods and apparatus for resolving multiple branches that are executed out-of-order and resolving mis-predicted branches.
SUMMARY OF THE INVENTION
The present invention discloses methods and apparatus for enhanced resolution of mispredicted branches by providing and utilizing a branch repair table.
According to a preferred embodiment of the present invention, a branch repair table including a plurality of entries for a processor is disclosed. An entry of the first plurality of entries in the branch repair table includes a first portion for storing a branch identifier, a second portion for storing a fall-through address associated with a branch instruction, and a third portion for storing a target address associated with the branch instruction.
According to another embodiment a microprocessor for executing instructions out of order includes a branch repair table for storing data related to branch instructions, the branch repair table including a first plurality of entries, at least one entry of the first plurality of entries having a first portion for storing a target address of a branch instruction and a second portion for storing a fall-through address for the branch instruction. The microprocessor also includes a pipelined execution unit having an associated central instruction window, the central instruction window including a second plurality of entries for storing instructions including the branch instructions and a reference to at least the one entry in the first plurality of entries, the second plurality of entries less than the first plurality of entries.
According to yet another embodiment of the present invention, a method for repairing a pipeline in response to a branch instruction includes the steps of providing a branch repair table having a plurality of entries, predicting a target address for the branch instruction, allocating an entry in the branch repair table for the branch instruction, and storing the predicted target address, fall-through address, and repair information in the entry in the branch repair table. The steps of processing the branch instruction to determine an actual target address, comparing the predicted target address to the actual target address, and repairing the pipeline in response to the repair information in the entry in the branch repair table in response to the predicted target address and the actual target address being different, are also included.
Further understanding of the nature and advantages of the invention may be realized by reference to the remaining portions of the specification and drawings.
REFERENCES:
patent: 5805876 (1998-09-01), Bose et al.
patent: 5944817 (1999-08-01), Hoyt et al.
Mike Johnson,Superscalar Microprocessor Design,Prentice Hall, 1991, p. 133, 1991.
Cherabuddi Rajasekhar
Panwar Ramesh K.
Patel Sanjay
Talcott Adam R.
Follansbee John A.
Sun Microsystems Inc.
Townsend and Townsend / and Crew LLP
LandOfFree
Method and apparatus for resolving multiple branches 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 apparatus for resolving multiple branches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for resolving multiple branches will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2497316