Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-07-17
2001-07-10
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S237000, C712S234000, C711S210000
Reexamination Certificate
active
06260138
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to apparatus and methods for dispatching instructions in a processor, and to such a processor. In particular, the present invention relates to the handling and issue of branch instructions.
In a pipelined processor, there is a penalty for executing control-flow (branch) instructions. In particular, for conditional branches where the value of a condition is not known at the time of instruction issue, either the issue must be stalled until the information becomes available, or the instruction must be issued speculatively based on an assumed value.
Many different approaches to the handling of conditional branch instructions are known in the prior art.
A general description of pipeline processing architectures and the handling of branch instructions is to be found, for example, in “Advanced Computer Architectures—A Design Space Approach”, by Messrs D Sima, T Fountain and P Kacsuk, published by Addison Wesley Longman Limited in 1997 (ISBN 0-201-42291-3). Various aspects of parallel processing architectures are described. These include parallel processing architectures including multiple execution units and parallel decoding of instructions in, for example, superscalar processors, as well as aspects of dependency checking, etc., associated therewith. Chapter 8 of that book on pages 295-368 is directed to the processing of control transfer instructions. The handling of unresolved conditional branches is discussed. Three basic approaches are identified, namely blocking branch processing, speculative branch processing, and multiway branch processing.
Blocking branch processing is a trivial approach to cope with unresolved conditional branches whereby, on detection of a conditional branch, the conditional branch is simply stalled until the specified condition can be resolved. Although this approach is simple to implement, it is inefficient because of the stalling of processing until the resolution of the condition on which a branch is based.
With speculative branch processing, on detection of an unresolved conditional branch, a guess is made as to the outcome of the condition and execution continues speculatively along the guessed path. If it is subsequently determined that the correct guess was made, the speculative execution can be confirmed and then continued. However, if an incorrect guess was made, all of the speculatively executed instructions have to be discarded and execution restart along the correct path. This approach offers higher performance than blocking branch processing. However, there is still a penalty to be paid when an incorrect guess is made due to the need to restart processing along the correct path. Various approaches are used to make the “guess” as to which path to execute speculatively following an unresolved conditional branch.
The simplest approach is to employ a fixed prediction, whereby the same guess is always made, either taking the branch path, or not taking the branch path. This unsophisticated approach makes use of the time during resolution of the condition on which the branch is to be based by speculatively executing instructions, but makes no attempt to assess the relative merits of the individual paths. A more sophisticated approach is to make a true prediction, either in a static manner on the basis of the object code to be executed, or dynamically on the basis of an execution history. Although the use of true prediction improves the chance of selecting the correct path for speculative execution, it does not overcome the problem of having to execute the alternative path from the branch point when an incorrect guess is made.
Multiway branch processing overcomes the performance disadvantages described with respect to speculative branch processing at the cost of duplicating the instruction issue and execution hardware. In other words, multiple sets of instruction issue, dispatch and execution units, and typically multiple instruction buffers, are provided in order to enable multiple instruction sequences following a branch to be executed in parallel during resolution of the condition for the branch. On resolution of the condition, the processing of the path not required is simply halted and the processing of the path determined by resolution of the condition is then proceeded with. Although the multiway branch processing does overcome the performance disadvantages of the speculative branch processing described above, it requires an extensive investment in hardware. Also, where multiple branch instructions occur in close proximity within a code sequence, mere duplication of the necessary hardware may be insufficient in order to provide a significant performance enhancement and accordingly more than two sets of instruction issue, dispatch and execution units may be required.
Accordingly, an object of the present invention is to mitigate the disadvantages of speculative branch processing without requiring the additional investment in hardware required by multiway branch processing.
SUMMARY OF THE INVENTION
Particular and preferred aspects of the invention are set out in the accompanying independent and dependent claims. Combinations of features from the dependent claims may be combined with features of the independent claims as appropriate and not merely as explicitly set out in the claims.
In accordance with one aspect of the invention, there is provided data processing apparatus including a plurality of execution units, at least one instruction buffer and an instruction processing mechanism. The instruction processing mechanism is configured to be operable to allocate respective priorities to instruction paths (instruction streams) following a conditional branch. The instruction processing mechanism is further operable to prioritize the dispatch of instructions for multiple paths to available execution units for speculative execution according to the allocated priorities.
Thus, for example, instructions in the instruction buffer relating to a predicted path, or instruction stream, following a conditional branch can be dispatched to available execution units in preference to instructions relating to any other paths, or instruction streams, instructions relating to other paths being dispatched to any execution units remaining available. Further instructions from the predicted path, or from all or any combination of paths, may be loaded into the instruction buffer.
By the use of the available execution units for executing instructions from a non-predicted path, progress can be made along a non-predicted path without a performance penalty compared to conventional speculative execution, yet without the hardware requirements of conventional multiway branch processing. Where a non-predicted path is subsequently shown to be the correct path, at least some progress can have been made along that path.
In order to identify the instructions for the respective paths, and accordingly, the respective priorities, priority tags can be associated with the instructions. The instruction buffer can be operable to receive undecoded, partially decoded or fully decoded instructions with any associated priority tag(s).
For dispatching an instruction, a dispatch unit can be responsive to any priority tags associated with instructions within a window in the instruction buffer to prioritize the issue of instructions from that window such that an instruction associated with a higher priority tag is issued in preference to an instruction associated with a lower priority tag. The window can be smaller than or the same size as the instruction buffer.
Alternatively, or in addition, where multiple execution buffers are each associated with one or more execution units and instructions are held in the execution buffers with any associated priority tags, an execution dispatch unit associated with each execution buffer can be responsive to any priority tags associated with instructions within a window in the associated execution buffer to prioritize the issue of instructions from that window such that an instruction associated with a hig
O'Melveny & Myers LLP
Pan Daniel H.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for branch instruction processing in a... 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 branch instruction processing in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for branch instruction processing in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2460073