Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
1999-10-14
2003-12-02
Ingberg, Todd (Department: 2124)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C712S205000, C711S147000
Reexamination Certificate
active
06658554
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention generally relates to architectures of electronic computers providing speculative execution.
In an electronic computer, a processing unit communicates with electronic memory holding data and program instructions. Typically, the processing unit executes the program instructions to load data from the memory, perform an operation on that data, and store the result of that operation back to the memory. During the operations, the data and result are temporarily held in registers internal to the processor. Registers are limited in number and cannot be practically used for long term storage of data.
The time required to load data from the memory and to store the data to the memory slows the speed of execution of the program. For this reason, it is known to construct cache memories which allow high bandwidth communication of limited amounts of data between the cache and processor. The cache is refreshed from the main memory as needed according to techniques well known in the art.
It is also known in the art to increase the speed of program execution by using multiple processing units to simultaneously execute instructions or to execute instructions in an order differing from normal program order. Computers using this technique are termed instruction level parallel (“ILP”) processors as may be distinguished from systems in which independent programs may be assigned different processors, for example.
In an ILP processor, the processor fetches multiple instructions in an instruction “window” and an allocation circuit allocates those instructions to separate processing units. The separate processing units may read data from memory and perform arithmetic or logical operations on that data. A retirement circuit then collects the results generated by the independent processing units and “retires” the instructions executed by those processing units by writing final results to memory. The retirement circuitry resolves mis-speculation, that is, situations where instructions were executed out-of-order but were in fact dependent on an earlier instruction in the execution order and therefore may have produced an erroneous result.
There are two types of dependency between instructions that may cause mis-speculation. “Control dependency” is the dependency exhibited by instructions after conditional branch or jump instructions on how the branch or jump is resolved. Instructions immediately after a branch may correctly execute only if the branch is not taken. “Data dependency” is the dependency of later instructions that use data on earlier instructions that create the data. These later data-using instructions may correctly execute only if the earlier instructions creating the data do not change the data or have completed the change of data. A dependency is “unambiguous” if it necessarily produces an error when the dependent instruction is executed before the instruction on which it is dependent.
Control and data dependencies limit the ability of an ILP processor to execute normally sequential instructions simultaneously or out-of-order. If the dependency is unambiguous, the results of an out-of-order execution of a dependent instruction must be discarded (“squashed”) and executed at later time (for data dependence) or other instructions executed instead (for control dependence). Squashing instructions is time wasting and to some extent defeats the advantages to be gained from parallel processing. In order to avoid the problems associated with squashing, the ILP processor can guess or “speculate” how any dependency will be resolved or whether it is relevant. This speculation need not be perfect, as it will ultimately be assessed by the retirement circuit, but it should be as accurate as possible. U.S. Pat. No. 5,781,752 issued Jul. 14, 1998 and entitled: Table Based Data Speculation Circuit for Parallel Processing Computer, assigned to the same assignee as the present invention and hereby incorporated by reference, discusses a method of determining likely data dependencies between given instructions in a program so that mis-speculation may be avoided.
BRIEF SUMMARY OF THE INVENTION
The present inventors have recognized that the mechanism of detecting data dependency disclosed in the above referenced pending application may be used to implicitly link data-consuming instructions that rely for their data on a common preceding instruction. In this way, time consuming memory transfers may be postponed or eliminated. Knowledge of data dependencies is used to pass data directly between instructions via special registers without waiting for the completion of memory LOADs. The same structure allows the identification of memory STORE operations which provide the data to the data consuming LOADs so that data may be passed directly from these STORE instructions.
Because the method of identifying data dependence is probabilistic, actual memory LOADs must be performed to confirm the predicted flow of data directly between instructions. However, in an ILP processor, data may be speculatively transferred between instructions to be squashed later if the speculation proves wrong according to standard ILP techniques.
Specifically, the invention provides a memory bypass circuit for use in an electronic processor executing data-producing instructions producing data to be stored into a memory and data-consuming instructions loading data from the memory. The memory bypass circuit includes a dependency table linking in “read-read” dependencies first data-consuming instructions to second data-consuming instruction according to a probability that both data consuming instructions read the same memory location. A storage register stores the data received by a first data consuming instruction identified to a read-read dependency of the dependency table. A table reviewing circuit, responsive to a second data-consuming instruction, reviews the dependency table and when the second data-consuming instruction is part of a read-read dependency with the first data consuming instruction, reads the data for that read-read dependency from the storage register.
Thus, it is one object of the invention to explicitly link data between two data-consuming instructions so as to provide a direct path of inter-instruction communication that bypasses standard memory and even cache memory. By establishing a direct inter-instruction communication pathway, the speed of communication is improved.
The dependency table may hold a prediction value associated with each read-read dependency and the table reviewing circuit may respond to the given data-consuming instruction, that is part of a dependency, by reading the data for that read-read dependency from the storage register only if the prediction value is above a predetermined threshold value. A dependency detection circuit detecting a data dependence between data consuming instructions generates the prediction value.
Thus, it is another object of the invention to provide for linkage of data-consuming instructions through the use of a probabilistic technique that examines after-the-fact detections of data dependence to predict future data dependencies. In this way no explicit linkage of the instructions need be done by the programmer and instructions whose dependence varies dynamically may be accommodated.
The dependency table may further link, in “read-write” dependencies, particular data-producing instructions to particular data-consuming instructions according to a probability that the data-producing instruction produces data used by the data-consuming instruction. In this case, the storage register further stores the data produced by the data-producing instruction identified to the read-write dependency of the dependency table and the table reviewing circuitry is responsive to a given data-consuming instruction to review the dependency table and when the given data-consuming instruction is part of a read-write dependency, reading the data for that dependency from the storage register.
Thus it is a further object of the invention to permit the same mechanism u
Moshovos Andreas I.
Sohi Gurindar S.
Ingberg Todd
Quarles & Brady LLP
Wood William H.
LandOfFree
Electronic processor providing direct data transfer between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Electronic processor providing direct data transfer between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Electronic processor providing direct data transfer between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3130607