Hardware predication for conditional instruction path branching

Details Hardware predication for conditional instruction path branching Hardware predication for conditional instruction path branching

2000-07-06

2004-06-22

Treat, William M. (Department: 2183)

Electrical computers and digital processing systems: processing

Processing control

Branching

Reexamination Certificate

active

06754812

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of computer systems. More particularly, the present invention relates to the field of processing instructions having conditional program execution flow control.
2. Description of Related Art
Typical processors execute instructions out of order to help improve instruction throughput. Such processors typically process instructions through a pipeline that fetches instructions from memory, decodes each instruction, executes the instruction, and retires the instruction. The operation of each stage of the pipeline typically overlaps those of the other stages in time to help process instructions faster.
By identifying instructions that may be executed regardless of whether one or more prior fetched instructions are executed, typical processors may benefit from executing instructions in parallel, that is overlapping the execution of two or more instructions in time, and/or from executing instructions out of order to avoid stalling on any one instruction, for example, while waiting for the completed execution of an instruction upon which the stalled instruction depends. Instructions executed out of order are retired by the pipeline in order.
The pipeline generally fetches instructions of a program in a sequential order as defined by the program until the program alters its sequential flow with a jump or branch instruction, for example.
An unconditional branch instruction, for example, identifies a non-sequential target instruction that is to follow the unconditional branch instruction. The pipeline identifies the target instruction and then continues fetching instructions of the program starting with the target instruction. Before identifying the target instruction, however, the pipeline may have already fetched and started processing one or more instructions sequentially following the unconditional branch instruction as defined by the program. The alteration in the sequential flow of the program therefore penalizes the execution of the program as the pipeline is to flush such instruction(s) and restart fetching and processing at the target instruction. By identifying the target instruction early in the pipeline, such as in the fetch or decode stage for example, the pipeline helps avoid or minimize this penalty.
A conditional branch instruction identifies a non-sequential target instruction that is to follow the conditional branch instruction if a condition identified by the conditional branch instruction is satisfied. If the condition is not satisfied, the fall through instruction, that is the instruction sequentially following the conditional branch instruction as defined by the program, is to follow the conditional branch instruction. Because resolution of the condition relies on the execution of one or more other instructions, the condition may not be resolved when the conditional branch instruction is fetched. As the pipeline then cannot determine which instruction is to follow the conditional branch instruction, the pipeline typically predicts whether the target instruction or the fall through instruction will follow at the risk of penalizing the execution of the program if the pipeline later determines the wrong instruction was selected. If, for example, the pipeline selects the target instruction and the condition is not satisfied, execution of the program is penalized as the pipeline flushes the target instruction and any fetched instructions following the target instruction when the conditional branch instruction is retired and restarts fetching and processing at the fall through instruction.
The pipeline may try to predict how the condition will be resolved, for example, based on prior executions of the same conditional branch instruction in the program. Typical pipelines, however, cannot accurately predict how every conditional branch instruction will be resolved every time and will therefore incur execution penalties due to branch mispredictions.
Software predicated instructions, such as a conditional move instruction for example, may be used to eliminate or reduce branch instructions and therefore avoid or minimize execution penalties associated with branch mispredictions. Software predication, however, requires compiler help to substitute code in eliminating branch instructions and an instruction set architecture that provides for the software predicated instructions.


REFERENCES:
patent: 5832260 (1998-11-01), Arora et al.
patent: 5909573 (1999-06-01), Sheaffer
patent: 5999736 (1999-12-01), Gupta et al.
patent: 6021487 (2000-02-01), Maliszewski
patent: 6044221 (2000-03-01), Gupta et al.
patent: 6047370 (2000-04-01), Grochowski
patent: 6076153 (2000-06-01), Grochowski et al.
patent: 6170052 (2001-01-01), Morrison
Intel Architecture Optimization Manual, Intel Corporation, Order No. 242816-003, pp. 1-1 to 1-3, 2-1 to 2-16, 3-1 to 3-35, C-1 to C-14, and D-1 to D-2 (1997).
Intel Architecture Optimization Reference Manual, Intel Corporation, Order No. 245127-001, pp. i-xx, 1-1 to 1-16, 2-1 to 2-31, and C-1 to C-19 (1998-1999).
Intel Architecture Software Developer's Manual vol. 1: Basic Architecture, Intel Corporation, Order No. 243190, pp. i-xvi, 1-1 to 1-10, 2-1 to 2-14, and 6-1 to 6-46 (1999).
Intel Architecture Software Developer's Manual vol. 3: System Programming, Intel Corporation, Order No. 243192, pp. i-xxii, 1-1 to 1-9, and 14-1 to 14-35 (1999).
P6 Family of Processors Hardware Developer's Manual, Intel Corporation, Order No. 244004-001, pp. i-vii, 1-1 to 1-2, and 2-1 to 2-7 (Sep. 1998).
Pentium® Processor Developer's Manual, Intel Corporation, Order No. 243502-001, pp. i-x, 1-1 to 104, and 2-1 to 2-14 (Oct. 1997).
U.S. patent application No. 09/611,282, filed Jul. 6, 2000, entitled “Hardware Predication for Conditional Instruction Path Branching”, by Mohammad A. Abdallah, et al.

Affiliated with

Also associated with

Rating

Hardware predication for conditional instruction path branching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hardware predication for conditional instruction path branching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware predication for conditional instruction path branching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3305375