Electrical computers and digital processing systems: processing – Processing control – Context preserving (e.g. – context swapping – checkpointing,...
Reexamination Certificate
1999-11-08
2003-07-22
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Context preserving (e.g., context swapping, checkpointing,...
C712S239000, C712S240000, C712S218000, C712S215000
Reexamination Certificate
active
06598152
ABSTRACT:
INCORPORATION BY REFERENCE
Incorporated by reference herein is the entire specification, including all text disclosure and all drawings, of application having U.S. Ser. No. 09/435,070 filed on Nov. 4, 1999 entitled “Circuits, Systems and Methods for Performing Branch Predictions by Selectively Accessing Bimodal and Fetch-Based Branch History Tables” by the inventor of the present application.
This invention generally deals with a novel process and a novel combination of apparatus in a processor chip for increasing the accuracy of branch prediction in the operation of a processor. More specifically, the present invention deals with the issue of increasing the speed of enablement for certain kinds of branch prediction tables in a processor semiconductor chip after a flush of instruction executions occurs in a processor pipeline.
BACKGROUND
The embodiment in the incorporated specification discloses an instruction prediction mechanism for use in a semiconductor chip which includes multiple types of prediction mechanisms, and controls for selecting among them for picking the prediction mechanism most likely to make the most accurate speculative prediction. A significant increase is thereby obtained in the processor overall speed of execution Particular types of branch prediction mechanisms disclosed therein, in which each selection is made include: a bimodal branch history table (LBHT), a fetch-based branch history table (GBHT), and a selector table (GSEL).
The invention in the related application teaches how a single-ported array can be used for a branch history table in which mispredictions are corrected during a stolen write cycle when the misprediction is detected during actual execution of the conditional branch instruction having the misprediction.
SUMMARY OF THE INVENTION
The subject invention is used to increase the speed of recovery of normal operation of instruction prediction mechanisms using multi-cycle indexing controls from disruptions caused by flushes in an execution pipeline caused during non-branch instructions execution. IFAR (instruction fetch address register) is used to locate an instruction, and a multi-cycle index is used to locate its associated prediction in particular types of instruction prediction mechanisms in which each index is developed over the last C number of fetch cycles.
In the incorporated application, a fetch-based GBHT (global branch history table) is disclosed which uses the IFAR to locate an I-cache instruction and a multi-cycle index developed over the last N fetch cycles to locate each I-cache instruction and its associated prediction required for a program execution. When an adverse event occurs during program execution, flushing of part or all of the program instructions currently selected in a processor's execution pipeline (containing the program instructions to be executed, or being executed) prevents the value of the index during the next eleven fetch cycles after a flush from being reliable, since the index requires the next eleven cycles for its development. Then, predictions cannot be obtained during the next eleven fetch cycles after a flush until the index development is completed, after which the index can be relied on for selecting instructions for execution, except for the case where the flush is caused by a mispredicted conditional branch instruction, for which immediate recovery is obtained in the next fetch cycle after a flush. Then, the recovered multi-cycle prediction mechanism can be providing reliable predictions immediately after a flush with no significant penalty.
Thus, the incorporated application solves the multi-cycle recovery problem for mispredicted conditional branch instructions by saving the value of the multi-cycle index used to select the conditional branch instruction (whether its misprediction indicates a mispredicted target instruction address, or a mispredicted next sequential instruction address, as the next instruction's address). The processor can then recover by using the saved multi-cycle index of the mispredicted branch instruction, since this branch instruction is the last instruction validly selected for execution when the flush is performed on all instructions selected after this branch instruction since they are in a wrong execution path for the program.
However, immediate recovery is not obtained for a multi-cycle index by the solution provided in the incorporated application when a pipeline flush is caused by an event independent of a branch instruction misprediction. Non-branch flushes can occur more frequently than flushes caused by branch mispredictions. That is, there are many causes of non-branch pipeline flushes.
If a branch prediction is being located by a multi-cycle index for an instruction in the I-cache located by the IFAR at the time of occurrence of a non-branch flush, the multi-cycle indices developed immediately thereafter (during the N number of cycles needed to develop a reliable index) are unreliable for use in selecting the next instruction. A relatively large number of conditions exist in a processor which may cause a pipeline flush. Then, an unreliable index may be provided during each of the next N fetch cycles (such as 11 fetch cycles) before the post-flush index values becomes reliable and can be used to make branch predictions for instructions located in the I-cache using the IFAR.
It is therefore the primary object of the subject invention to enable a processor to quickly recover reliable use of a multi-cycle index branch prediction mechanism when a flush occurs in the processor pipeline, whether the flush is caused by an event occurring for a non-branch instruction or for a branch instruction. Recovery of the use of the multi-cycle index prediction mechanism involves quickly restoring a GHV (global history vector) register to a steady state value, which may be disrupted when an execution facility in the processor detects a flush event for a problem instruction. This problem instruction is in a detected dispatch group in the processor execution pipeline. When the problem instruction is executed, if it is a non-branch instruction the processor execution unit signals and invalidates this detected dispatch group and all later dispatch groups in the pipeline. If the problem instruction is a branch instruction, the processor execution unit signals and invalidates all dispatch groups in the pipeline following the dispatch group that contains the branch instruction. Concurrently, the execution unit locates a branch information queue element associated with a branch instruction in the detected dispatch group, or immediately preceding the detected dispatch group if no branch instruction is in the dispatch group. (This branch instruction may or may not be the instruction causing the flush.) A GHV counter value in the queue element indicates the reliability of the associated GHV value in the same queue element. The content of a GHV register is set to a GHV value obtained from the associated branch information queue element. The GHV counter register is set to the GHV counter value in the branch information queue element if the dispatch group containing the problem instruction also contained a branch instruction. The GHV counter register is set to 0 if the dispatch group containing the problem instruction does not contain a branch instruction. If the GHV counter register value is indicated as reliable, the multi-cycle index prediction mechanism may continue to be used without interruption. But if unreliability is indicated for the multi-cycle predictions by the associated GHV counter value in the queue element, the multi-cycle predictions may then not be used until a transient period of a number of fetch cycles have occurred which are required before the GHV counter value reaches a predetermined value N (or N+1) which indicates that GHV has reached its reliable steady-state value.
This invention increases the overall accuracy of branch predictions in the system by increasing the percentage of the time during which the more accurate multi-cycle prediction proce
Ehrlich Marc A.
Ellis Richard L.
Goldman Bernard M.
Gonzalez Floyd A.
International Business Machines - Corporation
LandOfFree
Increasing the overall prediction accuracy for multi-cycle... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Increasing the overall prediction accuracy for multi-cycle..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Increasing the overall prediction accuracy for multi-cycle... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3087153