Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
2000-08-29
2004-10-26
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S217000, C712S218000, C712S219000, C712S213000, C712S236000, C712S237000, C712S240000
Reexamination Certificate
active
06810474
ABSTRACT:
TECHNICAL FIELD
The present invention relates to an information processor that performs predetermined operations according to the programmed instruction words, and specifically relates to the technology for shortening processing time of the information processor in the case where a dependency on the reference data exist between the instruction words.
BACKGROUND ART
In the information processor as typified by the microprocessor, any desired operation for the processing of information is executed by carrying out an operation specified by a programmed instruction words. It is the principle that reading of the instruction words and the execution of the operations should be done in the sequence of the instruction words, and hence a following instruction that is to refer to data generated by a preceding instruction in the program must wait for termination of the execution of the preceding instruction. This is a limitation that a following instruction cannot overtake a preceding instruction due to the so-called data dependency even if how much the following instruction is fast.
In terms of shortening of the processing time of the information processor, it is impossible to achieve the shortening of the processing time that surpasses the above-mentioned limitation unless the execution result of the preceding instruction is predicted by some kind or another predicting means and the execution of the following instruction gets started based on the prediction. A method where the instruction is executed based on the prediction is called speculative execution or speculation execution, which is not limited to this case. For methods of the speculative execution of the instruction having the data dependency described in this paragraph, the following technologies are known.
A technology disclosed in “IBM Journal of R&D, Vol.37, No.4, pp. 547-564, July (1993)” and “IEICE Transaction on Information and Systems, Vol.E79-D, No.11, pp. 1523-1532, November (1996)” (hereinafter referred to as “literature 1”) is for predicting an address on memory where data to be loaded is stored, namely, the load address, with respect to the load instruction for reading the data from memory outside an information processor into a register inside the information processor. The load address is reference information indispensable to perform the execution for the load instruction. Generally, there is a relation that the preceding instruction generates the actual load address or information necessary to calculate the load address and then the load instruction refers to it. Moreover, the execution time of the load instruction is long in general, and hence preferably the execution of the load instruction gets started as early as possible. In the technology disclosed in the literature 1, a cache-like mechanism is provided that can retrieve a load address used by the load instruction in the past using the address where the load instruction is stored as a key when the load instruction is read into the information processor and the load address is predicted without waiting for the execution termination of the preceding instruction by which the load address is actually fixed. The loading operation from the memory is initiated based on this load address. On the other hand, the load address calculation not based on the prediction concerned is concurrently executed. Load address calculation results through these two ways are collated. When the coincidence is obtained, whole processing time is shortened by the amount of preceded loading from the memory based on the prediction. When the coincidence is not obtained, whole processing time becomes the original execution time of the load instruction. By the way, the instruction for referring to the data that is loaded by the load instruction is not executed speculatively, but the execution is made to wait until correctness of the load address prediction is judged.
In the literature 1, the content of the prediction is limited to the load address and there is no disclosure regarding a point that an instruction for referring to the result of the loading etc. is executed speculatively. Regarding this point, technologies extended in such a way that the operation result is predicted for a general instruction and a following instruction that refers to the predicted operation result thereof is executed speculatively are disclosed in the following literatures: Technical Digest, 24th International Symposium on Computer Architecture (ISCA), pp. 194-205 (1997); Technical Digest, 29th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-29), pp. 226-237 (hereinafter referred to as “literature 2”); Japanese Patent Prepublication No. 60-129839 (hereinafter referred to as “literature 3”); Japanese Patent Prepublication No. 62-84340 (hereinafter referred to as “literature 4”); and Japanese Patent Prepublication No. 01-187634 (hereinafter referred to as “literature 5”). In each of the technologies disclosed in the literatures 2 to 5, memory for storing the past execution result of the instruction is provided in an information processor, and when the instruction is read into the information processor or is intended to be executed, the past execution result is outputted as a prediction for the execution of this time. If the following instruction has the data dependency, the speculative execution of the following instruction is initiated at the time of outputting of this prediction result. Thus, the instructions having the data dependency are executed speculatively in order as a system of a chain of instructions. In those technologies, the original execution result of the instruction and the prediction result are all collated, and when the coincidence is not obtained, an instruction having the data dependency just after the occurrence of inconsistence and instructions thereafter are executed again. In other word, all the results that were executed speculatively based on the prediction are discarded and the instruction execution is performed again.
As described above, in the information processor disclosed in the above-mentioned literatures 1 to 5 where the execution result is predicted and the following instruction having the data dependency is executed speculatively, an arithmetic and logical unit is used in performing speculative execution, and when the prediction goes wrong, the same arithmetic and logical unit is used again. Therefore, the frequency of use of the arithmetic and logical unit increases, and the information processor entails a risk of deterioration in terms of the processing time due to conflicting on the arithmetic and logical unit. This problem has not been examined in the above-mentioned literatures 1 to 5, but has been found through examination by the inventors of the present invention.
Moreover, in the technologies disclosed in the above-mentioned literatures 1 to 5, storage means for storing the past operation results is essential. Specifically, it is postulated that the storage means whose capacity is as large as that of the so-called instruction cache is indispensable because the storage means must store the operation results for the instructions. In the general information processor, in odor to shorten the processing time, it is effective to install the instruction cache and the data cache additionally. Therefore, even though the storage means to be used for the prediction of the instruction execution is provided in a limited-space device, the storage means that is used for predicting the instruction execution cannot chose but be a small scale one, because securing the capacity of the instruction cache and the data cache take first priority in general.
DISCLOSURE OF THE INVENTION
Then, a first object of the present invention is to circumvent the conflicting on the arithmetic and logical unit not using an original arithmetic and logical unit when a following instruction having the data dependency is executed speculatively.
Moreover, a second object of the present invention is to provide a technology whereby high prediction accuracy is secured even when small-scale sto
Mattingly Stanger & Malur, P.C.
Pan Daniel H.
LandOfFree
Information processor 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 processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information processor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3295903