Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-09-15
2001-10-09
Niebling, John F. (Department: 2812)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06301655
ABSTRACT:
This disclosure relates to the processing of exceptions in asynchronous data processors. Such processors can be used in many different items, including calculators, microcontrollers, microprocessors, digital signal processors, CPU cores for a microcomputer, minicomputer and large-scale computers generally.
BACKGROUND
Asynchronous processors do not use a clock to implement the operating of different operations. One of those operations includes the execution of the instructions of the processor.
The potential advantages of asynchronous and in particular quasi-delay-insensitive implementations of data processors have been described in the prior art. See for instance U.S. Pat. No. 5,752,070 to Martin and Barnes, and other U.S. patent applications by the present inventor.
This application relates more specifically to the case when the processor is pipelined. Pipelining is a standard technique in modern processor architecture and is well described in the literature. For instance, the standard computer architecture text by Hennessy and Paterson describes pipelining in great detail. Pipelining is an implementation technique whereby multiple instructions are simultaneously overlapped in execution. Today, pipelining is the key implementation technique to make CPUs.
A pipeline is like an assembly line: Each step in the pipeline completes a part of the instructions. As in a car assembly line, the work to be done is an instruction is broken down into small pieces, each of which takes a fraction of the time needed to complete the entire instruction. Each of these steps is called a pipeline stage.
In an asynchronous process, a pipeline stage communicates with other stages by exchanging messages. Typically, a stage receives data from a plurality of stages; it then processes the data, and sends the results to a plurality of stages. Each stage proceeds at its own speed. The communication between stages (send and relaying) synchronizes the activities of the different stages.
In a traditional, clocked pipelined processor, the number of instructions in execution in the pipeline is fixed in normal operation. In an asynchronous pipeline, because each stage proceeds at its own speed, the number of instructions in execution is variable. This difference is very important when it comes to dealing with “exceptions”.
An exception, also called “interrupt”, is a hardware and/or software mechanism that makes it possible to interrupt the normal execution of instructions when an exceptional event occurs that requires immediate processing. Such an event is usually an arithmetic error, or a real-time event, or an I/O. Modern exception mechanisms are used for other purposes like training instruction execution, operating system calls, page fault, memory and protection isolation, undefined instructions, protection isolations, hardware malfunction, power failure, etc.
The handling of an exception has a number of steps. (1) the exception is detected, (2) the necessary information relative to the exception is saved into some registers, in particular the program counter value of the instruction that caused the exception, and the nature of the exception, and (3) the program counter is assigned the address of the first instruction of an exception handling routine.
In the case where the processor is pipelined, several instructions may already be in execution when the exception occurs. In that case, all instructions already in execution in the pipeline have to be canceled. The exception mechanism is said to implement precise exceptions when the state of the execution saved for the exception handling routine is the same as the state of the processor before execution of the instruction that caused the exception. As a result, after the exception handler has finished, the execution of the program can be restarted from the point where the exception occurred, without affecting the program behavior.
In a clocked pipeline, all stages are controlled by the same global time reference. When an exception occurs, it is relatively straightforward to take a “snapshot” of the state of the pipeline. In particular, the number of instructions in the pipeline is fixed, and it is therefore straightforward to cancel all instructions in the pipeline.
In an asynchronous pipeline, there is no global clock. The number of instructions in the pipeline is variable. Hence, implementing precise exceptions is more difficult.
SUMMARY OF THE INVENTION
The present disclosure includes a new system and method to effectively handle exceptions in an asynchronous processor.
According to one embodiment of the invention, in an asynchronous pipeline, an instruction interrupted by an exception detected in an execution unit and all the instructions that follow it before the first exception handler instruction do not change the state of the processor (this is known as having precise exceptions). These instructions are prevented from modifying the state of the processor—the general purpose registers, special purpose registers, and data memory—by the use of a special “write-back” process. The write-back process interrupts the normal program-counter execution by requesting that the exception handler be executed. In addition, the write-back saves information about the exception (the cause of the exception, the program counter of the exception instruction, etc.) in special processor registers. Normal execution is resumed when the first instruction of the exception handler is executed.
One aspect for exception handling is the way the program order of the instructions is determined by the write-back process. The write-back process needs information about the order in which the instructions occurred in the program so that it can determine which instructions to cancel, and which instruction caused the first exception. This sequence would normally be lost in an asynchronous processor when the decode distributes the instructions to different execution units. To preserve this order, the decode also maintains a queue of execution unit numbers which correspond to the order in which the execution units were sent instructions. Each execution unit preserves the order of instructions sent to it, and therefore the write-back can reconstruct the program order using this queue.
Once the write-back determines an exception has occurred, it cancels the result of the instruction and subsequent instructions until the first instruction of the exception handler is executed. Each instruction has a special bit associated with it, called the “valid-again” bit. This bit is normally false. When an exception is encountered, the “pcunit” generates a special pseudo-instruction that has the valid-again bit set. The instruction following this pseudo-instruction is the first instruction of the exception handler. When the write-back receives an instruction with the valid-again bit set, it reverts back to normal operation and permits instructions that follow it to modify the state of the processor. The pseudo-instruction is also responsible for updating the special register used to store exception information.
According to another embodiment of the invention, the precise exception mechanism can be used to unpipeline the processor and thus resolve sequencing problems (“data hazards”) on infrequently executed instructions. To support this mechanism, the write-back stalls the pcunit until the valid-again instruction arrives. The special pseudo-instruction is therefore executed without any other instructions running in parallel with it. When a potential sequencing problem is detected, the instruction causing the conflict is made to raise an exception and is saved in a special register. The pseudo-instruction then executes the saved instruction. In this case, the pcunit resumes execution at the next program counter, instead of at the address of the exception handler.
According to another embodiment, the precise exception mechanism can be used to handle speculative execution in an asynchronous architecture. When instructions are executed speculatively, the write-back mechanism can be used to prevent these instruc
Manohar Rajit
Martin Alain J.
Nystrom Mika
California Institute of Technology
Fish & Richardson P.C.
Niebling John F.
Whitmore Stacy
LandOfFree
Exception processing in asynchronous 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 Exception processing in asynchronous processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exception processing in asynchronous processor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2583989