US 5,634,103 AGranted

Method and system for minimizing branch misprediction penalties within a processor

AssigneeInternational Business Machines Corporation

InventorsCarl D. Dietz, Robert T. Golla, Christopher H. Olson

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method and system within a processor are disclosed for executing selected instructions among a number of instructions stored within a memory, wherein the processor has a maximum of instructions that can dispatched for execution during each processor cycle. A subset of the instructions are fetched from the memory for execution. A determination is then made whether the set of instructions includes an unresolved branch instruction. In response to a determination that the set of instructions includes an unresolved branch instruction, a prediction is made whether a branch indicated by the branch instruction will be taken or will not be taken. In response to a prediction that the branch will be taken, a nonsequential target instruction indicated by the branch instruction is fetched from memory. A determination is made whether the maximum number of instructions can be dispatched for execution during a processor cycle subsequent to the branch prediction without dispatching instructions within the sequential execution path. In response to a determination that less than the maximum number of target instructions can be dispatched in the processor cycle subsequent to the branch prediction without dispatching instructions within the sequential execution path, an instruction within the sequential execution path is speculatively dispatched for execution. In response to refutation of the branch prediction, the fetch of the nonsequential target instruction is cancelled and the instruction within the sequential execution path is executed, thereby minimizing a performance penalty incurred by the processor due to the mispredicted branch.

Claims18

Dependent claims

A method for executing instructions within a processor, said processor having a memory which stores a plurality of instructions arranged in a sequential order, wherein said processor has a predetermined maximum number of instructions that can be dispatched for execution during each processor cycle, said method comprising:

fetching a subset of said plurality of sequential instructions from said memory for execution by said processor;
determining whether said subset of said plurality of sequential instructions includes an unresolved branch instruction;
in response to a determination that said subset of said plurality of sequential instructions includes an unresolved branch instruction, predicting if a branch indicated by said branch instruction will be taken;
in response to said prediction, fetching at least one nonsequential target instruction indicated by said branch instruction from said memory;
determining whether or not said maximum predetermined number of instructions can be dispatched for execution during a processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction in said sequential order;
in response to a determination that said predetermined maximum number of instructions can be dispatched during said processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction, dispatching said predetermined maximum number of instructions for execution;
in response to a determination that said predetermined maximum number of instructions cannot be dispatched during said processor cycle following said branch prediction without dispatching any sequential instructions which follow said branch instruction, speculatively dispatching a sequential instruction which follows said branch instruction for execution;
in response to refutation of said branch prediction,
cancelling said fetch of said target instruction;
and
executing said sequential instruction which follows said branch instruction, wherein a performance penalty for a mispredicted branch is minimized.

8 more elements

A system for executing instructions within a processor, said processor having a memory which stores a plurality of instructions arranged in a sequential order, wherein said processor has a maximum number of instructions that can be dispatched for execution during each processor cycle, said system comprising:

means for fetching a subset of said plurality of sequential instructions from said memory for execution by said processor;
means for determining whether said subset of said plurality of sequential instructions includes an unresolved branch instruction;
means, responsive to a determination that said subset of said plurality of sequential instructions includes an unresolved branch instruction, for predicting if a branch indicated by said branch instruction will be taken;
means for fetching at least one nonsequential target instruction indicated by said branch instruction from said memory in response to said prediction;
means for determining whether or not said maximum predetermined number of instructions can be dispatched for execution during a processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction in said sequential order;
means, responsive to a determination that said predetermined maximum number of instructions can be dispatched during said processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction, for dispatching said predetermined maximum number of instructions for execution;
means, responsive to a determination that said predetermined maximum number of instructions cannot be dispatched during said processor cycle following said branch prediction without dispatching any sequential instructions which follow said branch instruction, for speculatively dispatching a sequential instruction which follows said branch instruction for execution;
responsive to refutation of said branch prediction,
means for cancelling said fetch of said target instruction;
and
means for executing said sequential instruction which follows said branch instruction, wherein a performance penalty for a mispredicted branch is minimized.

8 more elements

A data processing system, comprising:

a memory which stores a plurality of instructions arranged in a sequential order;
a processor having a predetermined maximum number of instructions that can be dispatched for execution during each processor cycle, said processor including:
means for fetching a subset of said plurality of sequential instructions from said memory for execution by said processor;
means for determining whether said subset of said plurality of sequential instructions includes an unresolved branch instruction;
means, responsive to a determination that said subset of said plurality of sequential instructions includes an unresolved branch instruction, for predicting if a branch indicated by said branch instruction will be taken;
means for fetching at least one nonsequential target instruction indicated by said branch instruction from said memory in response to said prediction;
means for determining whether or not said maximum predetermined number of instructions can be dispatched for execution during a processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction in said sequential order;
means, responsive to a determination that said predetermined maximum number of instructions can be dispatched during said processor cycle following said branch prediction from among sequential instructions preceding said branch instruction and said at least one target instruction without dispatching any sequential instructions which follow said branch instruction, for dispatching said predetermined maximum number of instructions for execution;
means, responsive to a determination that said predetermined maximum number of instructions cannot be dispatched during said processor cycle following said branch prediction without dispatching any sequential instructions which follow said branch instruction, for speculatively dispatching a sequential instruction which follows said branch instruction for execution;
responsive to refutation of said branch prediction,
means for cancelling said fetch of said target instruction;
and
means for executing said sequential instruction which follows said branch instruction, wherein a performance penalty for a mispredicted branch is minimized.

10 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/555,819Filed 9 Nov 1995
Granted: 27 May 1997
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 9/3836
Concurrent instruction execution, e.g. pipeline or look ahead: instruction issuing, e.g. dynamic instruction scheduling or out of order…
G06F 9/384
Dependency mechanisms, e.g. register scoreboarding: register renaming
G06F 9/3842
Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution: speculative instruction execution
G06F 9/3861
Concurrent instruction execution, e.g. pipeline or look ahead: recovery, e.g. branch miss-prediction, exception handling