Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1999-12-07
2003-03-11
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06532534
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an information processing apparatus and in particular an apparatus provided with a branch history with a plurality of ways to automatically designate a way in which an entry to be data-processed exists and to speed up the process when a branch history in which both the instruction address of a branch instruction itself executed before and the instruction address of a branch destination are registered has a plurality of ways.
2. Description of the Related Art
An out-of-order process method can be used as one method for improving the efficiency of an information processing apparatus. In an information processing apparatus adopting the out-of-order process method, a subsequent instruction string is sequentially inputted to a plurality of pipelines without waiting for the completion of the execution of one instruction, and the performance is improved by executing processes in parallel.
However, even in the information processing. apparatus adopting the out-of-order process method, if the execution result of a preceding instruction affects the execution of a subsequent instruction, the execution of the subsequent instruction cannot be started unless the execution of the preceding instruction is completed. If the process of the preceding instruction causes delay, the subsequent instruction cannot be executed, the completion of the preceding instruction continues to be waited for, disorder occurs in a pipeline and the performance is degraded.
For a typical example of the instruction above, a branch instruction is listed. In the branch instruction, it is unknown whether a branch is established until the execution is completed, and even when the branch is established, the target address of a branch destination is unknown. Therefore, if a preceding instruction is a branch instruction, a subsequent instruction enters a waiting state and disorder occurs in a pipeline. For this reason, the process of the branch instruction must be sped up using a branch history.
If a branch is established in an branch instruction of which the execution is already completed, the branch history is used to register the instruction address of the branch instruction itself and the instruction address of branch destination, that is, a target address in pairs. Then, if an instruction fetched from a memory device, such as a main memory device, cache memory, and so on, is a branch instruction, the content of the branch history is retrieved. If the address of the instruction is already registered, the process of the branch instruction is started using the registered target address as a predictive branch destination address prior to the judgment on whether a branch is actually established.
Both the instruction address of a branch instruction which is not registered in the branch history and in which a branch is established and the branch destination address must be registered. If the branch instruction address, that is, the target address is modified due to some cause, the predictive branch destination address as the retrieval result of the branch history becomes invalid. In that case, in some cases, the registered target address must be updated and in other cases, an entry in which the instruction address of the branch instruction and the instruction address of the branch destination are registered in pairs must be deleted. Furthermore, if the prediction of a branch establishment failed or if the target address as a branch destination was wrong, information indicating the fact must be stored for each entry.
If a conventional branch history has a plurality of ways, information on the way where an entry in which both the instruction address of a branch instruction itself and a target address should be newly registered exists or on the way where an entry to be updated or deleted exists must be stored in another memory, or the direct retrieval of the branch history must be carried out every time the new registration, update or deletion of an entry is required.
If a separate memory is prepared, the circuit area of the entire information processing apparatus becomes large, and a waiting time for extracting information required to designate a way occurs, which are problems.
If the branch history is directly retrieved, the predictive branch destination address of a branch instruction fetched from a main memory device, and so on, that is, a target address, cannot be searched for while the branch history is retrieved. Therefore, the entire process is temporarily stopped, the performance is greatly degraded and a branch history cannot be effectively utilized, which also is a problem.
SUMMARY OF THE INVENTION
An object of the present invention is to automatically designate a way in which a new entry to be registered in a branch history with a plurality of ways, or an entry to be data-updated or data-deleted exists, without preparing another memory and without directly retrieving the branch history and to effectively utilize a branch history.
In the first aspect of the present invention, an information processing apparatus comprises an instruction fetch unit. The instruction fetch unit attaches way designation information designating a way in which an entry to be data-processed exists to the address of an instruction and provides the way designation information to an instruction execution unit executing the instruction in the information processing apparatus in preparation for the case where an instruction fetched from a memory device, such as a main memory device, cache memory, and so on, is a branch instruction and the data process of the branch history corresponding to the branch instruction is required.
REFERENCES:
patent: 5978906 (1999-11-01), Tran
patent: 1-286031 (1989-11-01), None
patent: 2-71328 (1990-03-01), None
patent: 4-175825 (1992-06-01), None
patent: 6-67880 (1994-03-01), None
“Improving Instruction Cache Branch Prediction with Target Addresses,”IBM Technical Disclosure Bulletin, vol. 3, No. 7, pp. 497-498, Jul. 1993.*
Michaud et al., “Trading Conflict and Capacity Aliasing in Conditional Branch Predictors,” Proceedings of the 24th International Symposium on Computer Architecture, ACM, vol. 25, Iss. May 1, 1997, 2, pp. 292-303, Jun. 1997.
Inoue Aiichiro
Sunayama Ryuichi
Fujitsu Limited
Staas & Halsey , LLP
Treat William M.
LandOfFree
Information processing apparatus provided with branch... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Information processing apparatus provided with branch..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information processing apparatus provided with branch... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3083872