Branch prediction apparatus

A branch prediction apparatus, comprising:

• a branch prediction table having prediction bits for each branch instruction to store a result of state transition thereof among eight states including first four states and second four states;
• a prediction generator for outputting, when the prediction bits are in one of the first four states, a “branch taken” as a result of prediction, and for outputting, when the prediction bits are in one of the second four states, “branch not taken” as a result of prediction;
• and
• a prediction bit controller for controlling the prediction bits,
• wherein the prediction generator generates, when a result of a branch instruction is equal to a previous result thereof, a result of prediction equal to the current result of the branch instruction at a next prediction of the branch instruction,
• wherein the prediction generator generates, when a result of a branch instruction is opposite to a previous result thereof and this condition occurs once or consecutively three times, a result of prediction opposite to the current result of the branch instruction at a next prediction of the branch instruction, and
• wherein the prediction generator generates, when a result of a branch instruction is opposite to a previous result thereof and this condition occurs successively two times, a result of prediction equal to the current result of the branch instruction at a next prediction of the branch instruction.

A branch prediction apparatus, comprising:

• a first branch predictor, including:
• a branch prediction table for storing three prediction bits for each branch instruction,
• a branch prediction table for storing one history bit and a 2-bit counter to be updated according to a result of a “branch taken” or a “branch not taken” for each branch instruction,
• a prediction generator for outputting, when the counter has a value of 0 or 2 for a branch instruction, a value of the history bit as a result of prediction, and for outputting, when the counter has a value of 1 or 3 for a branch instruction, a value obtained by reversing the history bit as a result of prediction, and
• a counter controller for comparing a branch instruction result with a value of the history bit before update, for setting 0 to the 2-bit counter value when the branch instruction result matches the value of the history bit before update, and for adding one to the 2-bit counter value when the branch instruction result does not match the value of the history bit before update and the counter value is other than 3;
• a second branch predictor for predicting a branch instruction according to a comprehensive history of all branch instructions;
• a choice prediction table for keeping information to be updated according to “true” or “false” of predictions by the first and second branch predictors;
• and
• a selector for selecting one of the predictions by the first and second branch predictors according to the information of the choice prediction table.

A branch prediction apparatus, comprising:

• a first branch predictor, including:
• a branch prediction table having prediction bits for each branch instruction;
• to store the result of state transition thereof among eight states including first four states and second four states,
• a prediction generator for outputting, when the prediction bits are in one of the first four states, a “branch taken” as a result of prediction and for outputting, when the prediction bits are in one of the second four states, a “branch not taken” as a result of prediction, and
• a prediction bit controller for controlling the prediction bits,
• wherein the prediction generator generates, when a result of a branch instruction is equal to a previous result thereof, a result of prediction equal to the current result of the branch instruction at a next prediction of the branch instruction,
• wherein the prediction generator generates, when a result of a branch instruction is opposite to a previous result thereof and this condition occurs once or consecutively three times, a result of prediction opposite to the current result of the branch instruction at a next prediction of the branch instruction,
• wherein the prediction generator generates, when a result of a branch instruction is opposite to a previous result thereof and this condition occurs successively two times, a result of prediction equal to the current result of the branch instruction at a next prediction of the branch instruction;
• a second branch predictor for predicting a branch instruction according to a comprehensive history of all branch instructions;
• a choice prediction table for keeping information to be updated according to “true” or “false” of predictions by the first and second branch predictors;
• and
• a selector for selecting one of the predictions by the first and second branch predictors according to the information of the choice prediction table.