Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-01-19
2001-12-18
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S237000
Reexamination Certificate
active
06332191
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of processors and, more particularly, to speculatively fetching instructions following a branch instruction in a microprocessor.
2. Description of the Related Art
Superscalar processors attempt to achieve high performance by issuing and executing multiple instructions per clock cycle and by employing the highest possible clock frequency consistent with the design. Over time, the number of instructions concurrently issuable and/or executable by superscalar processors has been increasing in order to increase the performance of superscalar processors.
Unfortunately, many of the concurrently issuable and/or executable instructions are branch instructions where the address of the instruction subsequent to the branch instruction may not be known prior to execution of the branch instruction. Consequently, branch instructions may incorporate significant delays into a superscalar microprocessor.
One mechanism to counter the delays caused by branch instructions is a branch prediction unit. A branch prediction unit is typically configured to provide a branch prediction address in response to receiving the address of a branch instruction. In order to generate a branch prediction address, however, a branch instruction typically must be fetched and decoded. After a branch instruction is fetched and decoded, a branch prediction unit must then spend one or more clock cycles generating a branch prediction address. Although a branch prediction unit reduces the delay associated with branch instructions, significant delays still occur between fetching a branch instruction and generating a corresponding branch prediction address. It would be desirable to minimize the time between fetching a branch instruction and generating a branch prediction address.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a line predictor configured to speculatively fetch instructions following a branch instruction. The line predictor stores a plurality of lines that each contain instruction line information. Each line stored by the line predictor includes a fetch address, information regarding one or more instructions, and one or more next fetch addresses. In response to receiving a fetch address, the line predictor is configured to provide instruction line information corresponding to the one or more instructions located at the fetch address to an alignment unit. The line predictor is also configured to provide a next fetch address associated with the fetch address to an instruction cache for speculative fetching and to a branch prediction unit for a branch prediction. The next fetch address is further fed back into the line predictor to generate the instruction line information associated with it and a subsequent next fetch address.
Generally speaking, a next fetch address may be a next sequential fetch address or a branch target address. A next sequential fetch address is the sequential address following the last instruction associated with the instruction line information of the fetch address unless an instruction within the line is a branch instruction. If an instruction within the instruction line information of the fetch address is a branch instruction, the next fetch address may be the target address of the branch instruction.
The branch prediction unit is configured to generate a branch prediction in response to receiving a next fetch address if a branch instruction is detected in the instruction line information of the next fetch address. The branch prediction is then compared to a subsequent next fetch address. If the branch prediction differs from a subsequent next fetch address, operations that were initiated using the next fetch address are canceled, the subsequent next fetch address is updated in the line predictor, and the updated subsequent next fetch address is refetched. In one particular embodiment, the line predictor contains multiple banks that each contain a plurality of lines for storing instruction line information. In this embodiment, the line predictor can be dual ported to update and refetch the subsequent next fetch address in the same clock cycle.
Broadly speaking, a microprocessor comprising a line predictor, an instruction cache, and a branch prediction unit is contemplated. The line predictor is configured to store instruction line information regarding two or more instructions terminated by a branch instruction. The line predictor is further configured to store a first fetch address corresponding to the two or more instructions and a second fetch address corresponding to the branch instruction. The instruction cache is coupled to the line predictor and configured to store a plurality of instructions. The branch prediction unit is coupled to the line predictor and is configured to store a plurality of branch predictions. The line predictor is also configured to provide the first fetch address to the instruction cache and the branch prediction unit during a first clock cycle.
A method for speculatively fetching one or more instructions following a branch instruction is also contemplated. A first fetch address is generated in a line predictor corresponding to a line of instruction line information regarding two or more instructions terminated by a branch instruction during a first clock cycle. A second fetch address is also generated in a line predictor corresponding to a predicted address of the branch instruction during a second clock cycle. The first fetch address is provided to a branch prediction unit during the first clock cycle where a branch prediction is generated for the branch instruction based on the first fetch address.
A microprocessor is also contemplated comprising a line predictor, an instruction cache, and a branch prediction unit. The line predictor includes a first and a second line of instruction line information. Each line of instruction line information includes a fetch address field configured to store a fetch address, a plurality of instruction/ROP fields, and a next fetch address field configured to store a next fetch address. The instruction cache is coupled to the line predictor and is configured to store a plurality of instructions. The branch prediction unit is coupled to the line predictor and is configured to store a plurality of branch predictions. A last of the plurality of instruction fields in the second line corresponds to a branch instruction and the second next fetch address corresponds to an instruction subsequent to the branch instruction. Also, the line predictor is configured to provide the first next fetch address to the instruction cache and the branch prediction unit during a first clock cycle.
A computer system comprising a microprocessor and an input/output device coupled to the microprocessor is also contemplated. The microprocessor comprises a line predictor, an instruction cache, and a branch prediction unit. The line predictor is configured to store instruction line information regarding two or more instructions terminated by a branch instruction. The line predictor is further configured to store a first fetch address corresponding to the two or more instructions and a second fetch address corresponding to the branch instruction. The instruction cache is coupled to the line predictor and configured to store a plurality of instructions. The branch prediction unit is coupled to the line predictor and is configured to store a plurality of branch predictions. The line predictor is configured to provide the first fetch address to the instruction cache and the branch prediction unit during a first clock cycle. The input/output device is configured to communicate between the computer system and another computer system coupled to the input/output device.
REFERENCES:
patent: 5142634 (1992-08-01), Fite et al.
patent: 5283873 (1994-02-01), Steely, Jr. et al.
patent: 5434985 (1995-07-01), Emma et al.
patent: 5608886 (1997-03-01), Blomgren et al.
patent: 5742805 (1998-04-01), Kulkarni et al.
patent: 5758143 (1998-05-01), Le
Advanced Micro Devices , Inc.
Conley Rose & Tayon PC
Ellis Richard L.
Merkel Lawrence J.
LandOfFree
System for canceling speculatively fetched instructions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for canceling speculatively fetched instructions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for canceling speculatively fetched instructions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2572018