Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-05-02
2004-04-20
Tsai, Henry W. H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S237000
Reexamination Certificate
active
06725365
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method of executing instructions including branch instructions, and to a computer system for such execution.
BACKGROUND TO THE INVENTION
In a superscalar pipelined computer system, the execution of branches can pose a problem. This is particularly the case for predicated branches in a guarded instruction execution system. In a pipelined computer system, branch instructions may be fetched and decoded several machine cycles earlier than the state at which the guard indicator of the branch is resolved (true or false) to determine whether or not the branch is taken. Until the guard indicator of the branch is resolved, the computer system does not know whether the instruction subsequent to the branch instruction which should next be executed is the instruction in the original program sequence which contained the branch instruction, or the instruction at the target address indicated by the branch. In the former case, the branch is not taken and in the latter case the branch is taken. If the branch is taken, it is necessary to start fetching instructions from the target address and to supply these through the pipelined computer system. If the branch is not taken, it is necessary to continue supplying and executing instructions from the original instruction sequence following the branch instruction.
It is desirable to reduce the penalties involved if a branch is not taken by already having available instructions to be executed for that case.
SUMMARY OF THE INVENTION
According to one aspect of the invention there is provided a computer system for executing instructions predicated on guard indicators included in the instructions, the instructions including normal instructions which are executed if the guard indicator is true and branch instructions which are executed if the guard indicator is false, the computer system comprising: instruction supply circuitry; at least one execution unit for receiving instructions from the supply circuitry; branch detection circuitry for detecting a branch instruction, for holding the guard indicator of the branch instruction and for setting a branch shadow mode; means operable in the branch shadow mode for comparing the guard indicator of the branch instruction with the guard indicator included in subsequent instructions and for continuing to supply instructions if the guard indicators match and for preventing supply of instructions if the guard indicators do not match; and means for disabling the branch shadow mode when the branch instruction has been determined such that the branch is taken or not by resolving the status of the guard indicator.
According to another aspect of the invention there is provided a method of executing instructions in a computer system predicated on guard indicators included in the instructions, the instructions including normal instructions which are executed if the guard indicator is true and branch instructions which are executed if the guard indicator is false, the method comprising: supplying instructions to at least one execution unit; detecting a branch instruction and, responsive to such detection, holding the guard indicator of the branch instruction and setting a branch shadow mode; in the branch shadow mode, comparing the guard indicator of the branch instructions with the guard indicator included in subsequent instructions and continuing to supply instructions if the guard indicators match, and preventing the supply of instructions if the guard indicators do not match; and disabling the branch shadow mode when the branch instruction has been determined such that the branch is taken or not by resolving the status of the guard indicator.
The computer system described herein allows instructions to continue to be fetched provided that they are predicated on the same guard indicator as the falsely guarded branch instruction. Therefore, when the guard value for the guard indicator is resolved as false, and the branch is taken, the subsequent instructions are automatically annulled because they are predicated on the guard indicator being true. That is, they would be executed only if the guard indicator is true. Thus no extra action is required in order to avoid these instructions being executed when the branch is taken.
However, if the branch is not taken, the instructions which are predicated on the guard being true will automatically be required next to be executed and will be ready in the pipeline. Therefore there is a significant improvement in latency if the branch is not taken with the system described herein.
The detection of the guard indicator can be carried out in a decoder of the computer system, and therefore the matter can be resolved at an early stage in the pipeline.
REFERENCES:
patent: 5381532 (1995-01-01), Suzuki
patent: 5740415 (1998-04-01), Hara
patent: 5748936 (1998-05-01), Karp et al.
patent: 5799180 (1998-08-01), Shiell et al.
patent: 5933628 (1999-08-01), Chang
patent: 0 180 725 (1986-05-01), None
patent: 0 488 819 (1992-06-01), None
European Search Report from application No. 99410061, filed May 3, 1999.
Adams, R., et al,A Parallel Pipelined Processor With Conditional Instruction Execution,Computer Architecture News, vol. 19, No. 1, Mar. 1, 1991 pp. 135-142, XP000201932 ISSN: 0163-5964.
U.S. patent application Ser. No. 09/562,542, Wojcieszak et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/562,717, Wojcieszak et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/562,718, Wojcieszak et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/563,475, Coffler et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/562,715, Wojcieszak et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/563,610, Wojcieszak et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/563,703, Uguen et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/563,154, Coffler et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/563,704, Coffler et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/563,468, Coffler et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/563,315, Grossier, filed May 2, 2000.
U.S. patent application Ser. No. 09/561,629, Grossier, filed May 2, 2000.
U.S. patent application Ser. No. 09/563,473, Bernard, filed May 2, 2000.
U.S. patent application Ser. No. 09/563,186, Alofs, filed May 2, 2000.
U.S. patent application Ser. No. 09/563,477, Cousin, filed May 2, 2000.
U.S. patent application Ser. No. 09/563,702, Coffler et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/563,634, Coffler et al., filed May 2, 2000.
U.S. patent application Ser. No. 09/563,153, Debbagh et al., filed May 2, 2000.
Bouvier Stephane
Cofler Andrew
Jorgenson Lisa K.
Morris James H.
STMicroelectronics S.A.
Tsai Henry W. H.
Wolf Greenfield & Sacks P.C.
LandOfFree
Branching in a computer system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Branching in a computer system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Branching in a computer system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3204132