Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2001-05-17
2004-08-31
Chan, Eddie (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S239000
Reexamination Certificate
active
06785804
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of processors and, more particularly, to the cancelling of speculative instructions in response to a branch misprediction.
2. Description of the Related Art
Branch instructions present numerous challenges to processor designers. The existence of branch instructions in code, and the mechanisms that the processor includes to handle the branch instructions with high performance, are frequently large factors in determining the overall performance that a user may actually experience when using a system including the processor.
One mechanism frequently used to address the challenges presented by branch instructions is speculative operation. Generally, branch instructions may be predicted (e.g. taken or not taken, for conditional branches, and/or branch target address predictions, for indirect branches and returns) and speculative operation may be performed based on the prediction. Instructions may be speculatively fetched and processed up to and/or including execution prior to resolution of the predicted branch instruction. If the prediction is correct, performance of the processor may be increased due to the speculative processing of the next instructions to be executed after the branch (either those at the branch target address or the sequential instructions). However, if the prediction is incorrect, the speculative instructions must be cancelled. Cancelling the speculative instructions, particularly in wide issue processors, may be complex.
A further difficulty introduced in some instruction set architectures (e.g. the MIPS instruction set architecture) involves the branch delay slot. The instruction in the branch delay slot is typically executed irrespective of whether the branch instruction is taken or not taken. However, for some branch instructions, the instruction in the branch delay slot is architecturally defined to be conditional based on whether the corresponding branch is taken or not taken. If the branch is taken, the instruction in the branch delay slot is executed. If the branch is not taken, the instruction in the branch delay slot is not executed. Thus, the branch delay slot instruction is treated differently for different branches, further complicating the cancelling of speculative instructions. Any type of instruction may be in the branch delay slot, and thus locating the instruction and cancelling or not cancelling the instruction based on which branch instruction that instruction follows is complicated.
SUMMARY OF THE INVENTION
A processor implements a mechanism for handling instruction cancellation for mispredicted branch instructions. Particularly, a first tag (referred to herein in certain exemplary embodiments as a branch sequence number) is assigned to a branch instruction. Dependent on the type of branch instruction, a second tag is assigned to an instruction in the branch delay slot of the branch instruction. The second tag may equal the first tag if the branch delay slot is unconditional for that branch, and may equal a different tag if the branch delay slot is conditional for the branch. If the branch is mispredicted, the first tag is broadcast to pipeline stages that may have speculative instructions, and the first tag is compared to tags in the pipeline stages. If the tag in a pipeline stage matches the first tag, the instruction is not cancelled. If the tag mismatches, the instruction is cancelled. Thus, an instruction in the unconditional delay slot is not cancelled (since the second tag equals the first tag for the unconditional delay slot) and an instruction in the conditional delay slot is cancelled (since the second tag equals a different tag). The cancellation mechanism thus may not require special handling of the branch delay slot during cancellation . . . the assignment of the tag may ensure the proper cancellation or non-cancellation of the branch delay slot instruction.
Broadly speaking, a processor is contemplated comprising a control circuit and a pipeline. The control circuit is configured to assign a first tag to a branch instruction and a second tag to a second instruction in a branch delay slot of the branch instruction. The second tag is equal to either the first tag or a different tag dependent on a type of the branch instruction. Coupled to receive the second instruction and the second tag, and further coupled to receive the first tag if the branch instruction is mispredicted, the pipeline is configured to selectively cancel the second instruction responsive to values of the first tag and the second tag.
Additionally, a method is contemplated. A first tag is assigned to a branch instruction. A second tag is assigned to a second instruction in a branch delay slot of the branch instruction. The second tag is equal to either the first tag or a different tag dependent on a type of the branch instruction. If the branch instruction is mispredicted, the second instruction is selectively cancelled responsive to values of the first tag and the second tag.
REFERENCES:
patent: 4755966 (1988-07-01), Lee et al.
patent: 5487156 (1996-01-01), Popescu et al.
patent: 5574871 (1996-11-01), Hoyt et al.
patent: 5604912 (1997-02-01), Iadonato et al.
patent: 5822575 (1998-10-01), Tran
patent: 5887161 (1999-03-01), Cheong et al.
patent: 6032244 (2000-02-01), Moudgill
patent: 6260138 (2001-07-01), Harris
patent: 6289442 (2001-09-01), Asato
Heinrich, “MIPS R4000 Microporcessor User's Manual, 2nd Edition,” 1994, p. 41.*
Klauser et al., “Selective Eager Execution on the PolyPath Architecture,” 1998, pp. 1-10.*
Halfhill, “Beyond Pentium II,” Dec. 1997, pp. 1-8, downloaded from http://www.byte.com.*
Tom R. Halfhill, “SiByte Reveals 64-Bit Core For NPUs; Independent MIPS64 Design Combines Low Power, High Performance,” Microdesign Resources, Jun. 2000, Microprocessor Report, 4 pages.
SiByte, “Target Applications,” http://sibyte.com/mercurian/applications.htm, Jan. 15, 2001, 2 pages.
SiByte, “SiByte Technology,” http://sibyte.com/mercurian/technology.htm, Jan. 15, 2001, 3 pages.
SiByte, “The Mercurian Processor,” http://sibyte.com/mercurian, Jan. 15, 2001, 2 pages.
SiByte, “Fact Sheet,” SB-1 CPU, Oct. 2000, rev. 0.1, 1 page.
SiByte, “Fact Sheet,” SB-1250, Oct. 2000, rev. 0.2, 10 pages.
Stepanian, SiByte, SiByte SB-1 MIPS64 CPU Core, Embedded Processor Forum 2000, Jun. 13, 2000, 15 pages.
Jim Keller, “The Mercurian Processor: A High Performance, Power-Efficient CMP for Networking,” Oct. 10, 2000, 22 pages.
Gerry Kane and Joe Heinrich, “MIPS RISC Architecture,” MIPS Technologies, Inc., 1992, pp. 1-12 to 1-14, 3-19 to 3-21, A-7, A-15 to A-38, A-50 to A-53, and C-6 to C-7.
SiByte, Letter from Anu Sundaresan, May 18, 2000, 1 page.
Broadcom Corporation
Chan Eddie
Huisman David J.
Merkel Lawrence J.
LandOfFree
Use of tags to cancel a conditional branch delay slot... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Use of tags to cancel a conditional branch delay slot..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Use of tags to cancel a conditional branch delay slot... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3321467