Electrical computers and digital processing systems: processing – Instruction fetching – Prefetching
Reexamination Certificate
1998-09-14
2004-05-25
Donaghue, Larry D. (Department: 2154)
Electrical computers and digital processing systems: processing
Instruction fetching
Prefetching
C712S023000, C712S218000, C712S219000, C712S233000
Reexamination Certificate
active
06742108
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of computer systems; more particularly, the present invention relates to executing load instructions before it is known that they can be legally executed (i.e., speculatively).
BACKGROUND OF THE INVENTION
Some computers have the capability to execute instructions out of order. In other words, the central processing unit (CPU) and the computer system is capable of executing one instruction before a previous instruction in the instruction execution stream. To execute computer programs more quickly in a computer system, it is often helpful to move instructions earlier in the execution stream than the programmer had initially planned. In particular, it is useful to move instructions to a location prior to branch instructions, the execution of which determine whether the moved instructions would have been executed. Such instructions are called speculative instructions because they are executed prior to knowing that the instructions are going to be executed (since the branch instruction has not been executed yet). However, memory operations typically must be executed in order to maintain memory consistency, especially when their execution would create incorrect results.
Exceptions may arise as a result of program execution. Although it is desirable to execute instructions speculatively, it is important not to take exceptions on such instructions where an instruction potentially may not actually be executed. As discussed above, whether these speculative instructions will actually be executed is based on whether a branch (or other conditional statement) is actually taken or not. Thus, when instructions are speculative, one cannot take an exception because the path that caused the exception might not have ever occurred.
One prior art solution to execute programs more quickly is to move only those instructions that are proven not to cause exceptions. This does work well for most integer instructions as they, in general, do not cause exceptions. Loads and divides can cause exceptions. A load instruction allows a central processing unit that processes data in a computer system to receive the data from memory. A load instruction typically specifies an address to a location in memory at which the desired data is stored. The load instruction also usually specifies the amount of data that is desired. Using the address and the amount of data specified, the memory may be accessed and the desired data obtained. It is very difficult to prove ahead of time that a load will not cause exception.
One solution to allow a program to execute more quickly is to move a load instruction earlier in the execution stream and replace them with loads which do not take exceptions. These are called dismissible loads. This is an effective solution. However, the program may no longer raise an exception which would have been raised had the change in program order not been made.
Another solution may be to use an additional bit in each register result indicating whether an instruction would have caused an exception. This allows for general speculation and still maintains the knowledge that an exception occurred. If using a register that has the bit set to indicate an exception occurred, the register is merely passed along with its results. A disadvantage of this approach is that it requires an additional register state which must be saved and restored.
The present invention allows load instructions to be moved earlier in the instruction stream for speculative execution while still allowing exceptions to occur when they should.
SUMMARY OF THE INVENTION
A method and apparatus for speculatively executing a load is described. The present invention includes a method and apparatus for executing a dismissible load instruction as part of, and earlier in, a series of executable instructions than the load. The present invention also includes a method and apparatus for executing another instruction, as part of the series of executable instructions, to determine whether to take an exception for the dismissible load instruction.
REFERENCES:
patent: 5704053 (1997-12-01), Santhanam
patent: 5732242 (1998-03-01), Mowry
patent: 5751983 (1998-05-01), Abramson et al.
patent: 5802337 (1998-09-01), Fielden
Klaiber et al. ; An Architecture for Software-Controlled Data Prefetching; pp. 43-53; ACM 5/91.*
Callahan et al. ; Software Prefetching; pp. 40-52; ACM 4/91.*
Mowry; Tolerating Latency Through Software-Controlled Data Prefetching; pp. 1-202; Stanford Univ. 3/94.*
Rogers et al., “Software Support for Speculative Loads”; 10/92.
Blakely , Sokoloff, Taylor & Zafman LLP
Donaghue Larry D.
Intel Corporation
LandOfFree
Method and apparatus for executing load instructions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for executing load instructions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for executing load instructions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3248233