US 6,477,640 B1Granted

Apparatus and method for predicting multiple branches and performing out-of-order branch resolution

AssigneeMotorola, Inc.

InventorsJeffrey Pidge Rupley, II, Marvin A. Denman, Bradley G. Burgess, David C. Holloway

Life of this patent

Estimating the term…

Loading patent…

Abstract

A branch prediction unit apparatus and method uses an instruction buffer (20), a completion unit (24), and a branch prediction unit (BPU) (28). The instruction buffer (20) and/or the completion unit (24) contain a plurality of instruction entries that contain valid bits and stream identifier (SID) bits. The branch prediction unit contains a plurality of branch prediction buffers (28a-28c). The SID bits are used to associate the pending and executing instructions in the units (20 and 24) into instruction streams related to predicted branches located in the buffers (28a-28c). The SID bits as well as age bits associated with the buffers (28a-28c) are used to perform efficient branch prediction, branch resolution/retirement, and branch misprediction recovery.

Claims8

Dependent claims

A data processing system comprising:

an instruction buffer;
a completion unit coupled to the instruction buffer;
a branch prediction unit coupled to the completion unit and the instruction buffer, the branch prediction unit having a plurality of branch prediction buffers for predicting a plurality of branch instructions;
the instruction buffer comprising:
a plurality of instruction entries, each instruction entry containing a valid bit;
a plurality of stream identifier bits;
an instruction;
each bit position in the plurality of stream identifier bits associated with a unique one of the plurality of branch prediction buffers;
and
bit values of the plurality of stream identifier bits defining dependence among instructions contained in the plurality of instruction entries;
wherein a first instruction in a first instruction entry is dependent upon a second instruction in a second instruction entry when a first bit position of the plurality of stream identifier bits of the first and second instruction entries contains a first bit value.

8 more elements

A method for performing branch prediction and resolution, the method comprising:

fetching a plurality of computer instructions, each of the plurality of computer instructions being associated with a plurality of stream identifier bits having bit positions, the plurality of computer instructions being program ordered;
determining at least one computer instruction that is an unresolved branch instruction within the plurality of computer instructions;
assigning the unresolved branch instruction to a selected branch prediction buffer selected from a plurality of branch prediction buffers, each branch prediction buffer being associated with a unique one bit position within the plurality of stream identifier bits;
setting, to a first bit value bit, a first bit position of the plurality of stream identifier bits associated with all instructions in the plurality of computer instructions having a program order greater than a program order of the unresolved branch instruction;
resolving one branch instruction within one of the plurality of branch prediction buffers as being correctly predicted;
and
clearing, in response to the step of resolving, the first bit value from the first bit position of the plurality of stream identifier bits associated with the one branch instruction.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 09/659,401Filed 11 Sep 2000 · continuation
Priority: 3 Apr 1998
Granted: 5 Nov 2002
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 9/3851
Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution: from multiple instruction streams, e.g. multistreaming
G06F 9/3844
Speculative instruction execution: using dynamic branch prediction, e.g. using branch history tables
G06F 9/3861
Concurrent instruction execution, e.g. pipeline or look ahead: recovery, e.g. branch miss-prediction, exception handling
G06F
Computing and data processing