Conditional branch control method

Details Conditional branch control method Conditional branch control method

1998-06-29

2001-01-30

Pan, Daniel H. (Department: 2783)

Electrical computers and digital processing systems: processing

Processing control

Branching

C712S215000, C712S238000, C714S718000

Reexamination Certificate

active

06182211

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a program control method of controlling a conditional branch in an information processing apparatus which processes an instruction by pipeline processing.
2. Description of the Background Art
In an information processing apparatus which processes an instruction by pipeline processing, while instructions are fed to a pipeline and executed one after another, as the instructions are executed overlapping each other, execution of the instructions is realized at a high speed. However, when a conditional branch instruction requires a branch, since an instruction beyond the branch is fetched at a point when the condition is decided, that is, since a branch address is set to a program counter after a branch judgement is made, a wasteful space, namely, a branch hazard is created in the pipeline.
Such a branch hazard is more likely to occur when a condition is met than when the condition is not met. Branch hazards increase one cycle where there is one instruction fetch stage. Branch hazards increase two cycles where there are two instruction fetch stages. Further, branch hazards increase N cycles where there are N instruction fetch stages (N is an optional positive integer.).
One conventional means for solving the problems is a branch method which uses a so-called delay branch, which requires execution of an instruction located at an address which follows a branch instruction in a delay slot to thereby reduce branch hazards in a pipeline. One example of such a conventional branch method is described in Japanese Patent Application Laid-Open Gazette No. 4-127237, for instance.
According to the conventional method as described above, since an instruction in a delay slot is executed during a cycle of a branch hazard, execution cycles of a branch instruction reduce on appearance. However, in a branch method which utilizes a delay branch described above, since there is a restriction on instructions which can be located in a delay slot, or since it is difficult to appropriately assign instructions to a delay slot if branch hazard have a large number of cycles, or for other reasons, it is not possible to effectively reduce branch hazards in all cases.
SUMMARY OF THE INVENTION
The present invention aims at providing a program control method which effectively reduces branch hazards during control of conditional branching in an information processing apparatus which processes an instruction by pipelines processing, without restricting a structure of a pipeline, the contents of an instruction, etc.
A program control method according to the present invention is characterized in that on a premise that a conditional branch instruction includes an address to which a branch is to be made, pipeline information of a subsequent instruction which is subsequent to the conditional branch instruction is saved before a condition of the conditional branch instruction becomes defined, that is, before a branch judgement is made so that an instruction beyond the branch is fed to a pipeline in advance, and the beyond-the-branch instruction is executed as it directly is when the condition is met, but the saved pipeline information of the subsequent instruction is returned to the pipeline and the subsequent instruction which is subsequent to the conditional branch instruction is executed when the condition is not met. As the pipeline information of the subsequent instruction described above, the address of the subsequent instruction and the instruction code of the subsequent instruction may be used.
In this structure, since the beyond-the-branch instruction is fed to the pipeline in advance before the condition of the conditional branch instruction becomes defined, by the time the condition is met, at lest the first stage of the pipeline processing of the beyond-the-branch instruction is already complete. After the condition is met, the pipeline processing of the beyond-the-branch instruction is continued starting at the second stage or one of the following stages. Hence, it is possible to reduce branch hazards which are associated with execution of the beyond-the-branch instruction more than where the beyond-the-branch instruction is fed to the pipeline after the condition of the conditional branch instruction becomes defined.
Meanwhile, since pipeline information of a subsequent instruction which is subsequent to the conditional branch instruction is saved before the condition of the conditional branch instruction becomes defined, when the condition is not met, as the saved pipeline information of the subsequent instruction which is subsequent to the conditional branch instruction is returned to the pipeline, the subsequent instruction which is subsequent to the conditional branch instruction is executed without increasing branch hazards.
Hence, as a whole, it is possible to reduce branch hazards which are created when the condition is met without increasing branch hazards which are created when the condition is not met, execute a program efficiently, and shorten a processing time.
Further, since the foregoing requires simply to save the pipeline information of the subsequent instruction which is subsequent to the conditional branch instruction and feed the beyond-the-branch instruction to the pipeline in advance before the condition of the conditional branch instruction becomes defined, it is possible to effectively reduce branch hazards without restricting the structure of the pipeline, the contents of instructions, etc.


REFERENCES:
patent: 5440704 (1995-08-01), Itomitsu et al.
patent: 5928358 (1999-07-01), Takayama
patent: 5940857 (1995-08-01), Nakanishi et al.
patent: 6009515 (1999-12-01), Steele, Jr.
patent: 6019501 (2000-02-01), Okazaki
patent: 812599 (1982-07-01), None
patent: 812599 (1989-07-01), None
patent: 2130634 (1990-05-01), None
patent: 4127237 (1990-09-01), None
patent: 4127237 (1992-04-01), None
patent: 520067 (1993-01-01), None
patent: 5173785 (1993-07-01), None
Patterson, et al., “Computer Architecture: A Quantitative Approach”, pp. 262-267 and English translation of pp. 265 121—p. 266 118 thereof.
Office Action from the Japanese Patent Office dated Mar. 2, 1999 and English translation.
European Search Report dated Feb. 15, 1999.
Antonio Gonzalez, “A Survey of Branch Techniques in Pipelined Processors”, Microprocessors and Microprogramming, vol. 36, No. 5, Oct. 1, 1993, pp. 243-257, XP00039707.
Ando, et al., “Speculative Execution and Reducing Branch Penalty on a Superscalar Processor”, IEICE Transactions on Electronics, vol. e76c, No. 7, Jul. 1993, pp. 1080-1092, XP000394448.
Intrater, et al., “Decoded Instruction Cache for Variable Instruction-Length Computers”, Proceedings of the Conference of Electrical and Electronics Engineers in Israel, Tel Aviv, Mar. 7-9, 1989, No. Conf. 16, Mar. 7, 1989, pp. 1-4, XP000077585, Institute of Electrical and Electronics Engineers.
Sohie, et al., “A Digital Signal Processor with IEEE Floating-Point Arithmetic”, vol. 8, No. 6 + index, Dec. 1, 1988, pp. 49-67, XP000105805.
Office Action from the Japanese Patent Office dated Nov. 17, 1998 and English translation.
Final Rejection from the Japanese Patent Office dated Jun. 8, 1999 and English translation for Patent Application No. 186570.

Affiliated with

Also associated with

Rating

Conditional branch control method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Conditional branch control method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conditional branch control method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2556807