Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
1999-06-26
2003-10-28
Baderman, Scott (Department: 2184)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C712S244000
Reexamination Certificate
active
06640315
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to enhancing instruction level parallelism in a multi-issue processor environment, and relates more particularly to a technique for the efficient recovery of exceptions generated during speculative execution.
BACKGROUND OF THE INVENTION
The performance of modern microprocessors has been increasing at a rapid and dramatic pace. Although microprocessor clock speeds keep increasing at a relatively moderate pace, microprocessor processing power has been increasing dramatically due to microprocessors having parallel architecture features. In 1990, conventional microprocessors executed one instruction per cycle. By 1995, conventional microprocessors had the ability to execute up to four instructions per cycle. It is anticipated that within about the next year, microprocessors will be widely available that are capable of executing up to at least eight instructions per cycle. A microprocessor that is capable of executing multiple instructions per cycle is also referred to as a multi-issue processor.
Despite the dramatic increase in the potential processing power of multi-issue processors, deficiencies in compiler technology and supporting architecture design typically limit the actual processing power realized to only a small fraction of the massive potential of the multi-issue processor. Unless a compiler and the supporting hardware expose substantial portions of the instructions in parallel to the microprocessor hardware, the processing power potential of the microprocessor is largely wasted. Thus, much attention has been focused upon techniques to increase the amount of instruction level parallelism (ILP) visible to the multi-issue microprocessor so as to realize the great processing power advantages of multi-issue microprocessors.
Three techniques have been studied individually to increase ILP: (1) control speculation, (2) data speculation, and (3) predication. Control speculation and data speculation fall into a more general category of speculative execution, where the execution of instructions are performed before their proper execution conditions have been determined.
Control speculation breaks control dependencies which occur between branches and other operations. In other words, instead of conventionally executing instructions sequentially, the schedule of instructions is modified such that certain instructions are moved up in the schedule and executed in parallel with other instructions and at a time when it is not necessarily known with certainty that the control flow of the code will require actual execution of those instructions. Such instructions are executed speculatively, i.e., executed based upon an assumption that the control flow will dictate that they should actually be executed.
An operation is control dependent on a branch if the branch determines whether control flow will actually reach the operation during the execution of the program. A control dependence is broken by guessing a branch will go in a particular direction, thereby making operations along the predicted direction to execute independently of the branch. Breaking control dependencies through control speculation reduces control dependence height and results in a more compact instruction execution schedule.
FIG. 6
illustrates a very simple example depicting control speculation. On the left is illustrated the instruction schedule for a sample instruction segment that dies not use control speculation. On the right is illustrated the same set of instructions, but scheduled using control speculation with a two-issue processor, sequence of execution of each of the processors being indicated by the two separate columns. When control speculation, is used the instructions associated with the LABEL
1
may be moved up in the schedule and executed control speculatively (indicated with <CS>) simultaneously with other instructions, as illustrated. As can be seen in the speculative version, two different LD instructions and two different ADD instructions are executed simultaneously. At the location where the LD r
1
, ADDR
2
instruction was located (at LABEL
1
) in the non-speculative version, there is substituted a CHK instruction in the speculative version that checks register R
1
to determine if an exception occurred as a result of the control speculative execution. If no exception was detected from register R
1
, then the speculation was successful and, as seen, the length of the code schedule has been reduced. However, if an exception was detected from register R
1
, such as if the memory being accessed by the load caused a segmentation violation, page fault, TLB (Translation Lookaside Buffer) miss, or cache memory miss, then the load of the control speculation redoes additional handling, and recovery should be initiated by re-executing the speculatively executed set of instructions.
Data speculation breaks data flow dependencies between memory operations. Two memory operations are flow dependent on one another if the first operation writes a value to an address and the second operation potentially reads from the same address. Thus, the original order of the memory operations must be maintained to ensure proper value flow. For a dependence to exist, the operation need only potentially read from the same address. If two memory operations are not provably independent, they are dependent by definition. A memory dependence where the dependence control is not certain is referred to as an ambiguous memory dependence. A memory dependence is broken by guessing that the two memory operations will access different locations, thereby making the operations independent of one another. With data speculation, memory operations may be aggressively reordered to effectively reduce memory dependence height which further results in a more compact instruction schedule.
Another technique that has been explored to increase ILP is predication. Predicated execution is a mechanism that supports conditional execution of individual operations based on Boolean guards, which are implemented as predicate register values. With predication, the representation of programmatic control flow can be inherently changed thereby physically restructing the control flow into a more efficient form execution on a wide-issue processor.
Speculative execution, however, introduces additional complexities and requires different and more sophisticated handling of particular conditions. One of the greatest challenges in dealing with speculatively executed instructions is how to handle exception or error conditions to ensure proper program control. When a non-speculatively executed instruction generates an exception condition, the exception is reported and handled immediately. However, when a speculatively executed instructions encounters an exception condition, it may be necessary to defer the exception to ensure that it does not interfere with proper operation of the program. Furthermore, exception recovery may require a long and time-consuming process, so it is frequently preferable to defer an exception encountered in a speculatively executed instruction until it is determined with certainty that the program flow actually requires execution of the instruction.
U.S. Pat. No. 5,692,169 to Kathail et al. for a Method and System for Deferring Exceptions Generated During Speculative Execution is directed to a technique where exceptions generated during execution of speculative instructions are deferred. The reference indicates that deferred exceptions may be detected and reported using a check operation either incorporated into a non-speculative operation or inserted as a separate check operation. The reference, however, does not provide a particular technique for recovery, but merely states that “when an exception is detected, the CPU branches to an exception handling routine.”
Smith et al. in Efficient Superscalar Performance Through Boosting, Proceedings of the Fifth International Conference on Architecture Support for Programming Languages and Operating Systems, October, 1992, pp. 248-259,
August David I.
Connors Daniel A.
Hwu Wen-mei W.
Sias John W.
Baderman Scott
Board of Trustees of the University of Illinois
Gardner & Carton & Douglas LLP
LandOfFree
Method and apparatus for enhancing instruction level... 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 enhancing instruction level..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for enhancing instruction level... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3139088