Electrical computers and digital processing systems: processing – Processing control – Processing sequence control
Reexamination Certificate
1999-11-29
2003-04-15
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Processing sequence control
C712S226000, C712S219000, C712S227000, C714S017000
Reexamination Certificate
active
06550005
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an apparatus and method for processing data in response to a sequence of program instructions at least one of which may be subject to cancellation.
2. Description of the Prior Art
In some pipelined CPUs an instruction can be cancelled before the point at which it would usually have finished. One condition which causes this behaviour is a memory access fault otherwise known as an abort. An abort is signaled when some intervention by the operating system is required. e.g. in a demand paged virtual memory system an abort is signaled when an attempt is made to access data which does not currently reside in the main memory of the system. Only after the operating system has moved the data into memory can the access be completed.
Typically an abort will simply cause the instruction which aborted to be cancelled and the instruction stream to be changed to execute a software abort handler. Once the abort handler has fixed the cause of the abort the instruction stream is switched back to the aborted instruction which will be re-executed.
As the aborted instruction has been partially executed before the abort is signaled and it was cancelled, it is vital that any state which the instruction has updated before the abort occurred does not prevent correct re-execution of the instruction.
For example, many instruction sets include instructions which load a register from an address calculated by summing the contents of a register holding a base address and a register holding a offset address. Often there is an option to write back to the register holding the base address the sum of its original contents plus the contents of the offset address. In this case the instruction will write to both the loaded register and the base register. In the event that a load aborts, the correct data is not available to be written into the loaded register. However, incorrect data can safely be written as it will be replaced by the correct value when the instruction is re-executed.
The same is not, however, true for the write to the base register. The base address register is read by the instruction as well as written by it, so when the instruction is re-executed it must contain the original value or the load will occur from the wrong address. Although the signal that an access has aborted is often a late arriving signal, in most systems it does arrive in time for the base register write to be averted.
Another example is concerned with instruction sets that include a load-multiple instruction which will load a set of registers from consecutive memory locations starting from an address specified in a base register. Often these instructions take many cycle to execute as they load data into successive registers in the specified set.
In some systems it is possible for an abort to occur on any of the accesses caused by the instruction. Normally this does not cause any additional difficulty as all the registers can be safely reloaded upon re-execution of the instruction. However at least two potentially difficult cases do exist:
a) the base writeback case analogous to the previous example;
b) the base register is also a member of the set of registers which is to be loaded—in this case the load to the base register may occur several cycles before an abort happens on a latter member of the set of registers to be loaded.
Case (a) is typically dealt with by delaying the base register writeback until it is know that no further aborts can occur for the instruction. If an abort does occur then the writeback is cancelled.
It is harder to deal with case (b) in the same manner as this would require that the order of the loads was shuffled to make the base register load occur last of all. One more practical way to deal with case (b) is to provide dedicated hardware to preserve a copy of the original base register upon starting the instruction up to a point where an abort can no longer occur. This copy is used to restore the original value if an abort does occur.
A problem with this approach is that the dedicated hardware tends to disadvantageously increase the circuit size and complexity.
It should be noted that the situations detailed above are merely examples and that similar problems may occur with other instructions as well as loads and for other cancellations as well as aborts.
SUMMARY OF THE INVENTION
Viewed from one aspect the present invention provides an apparatus for processing data in response to a sequence of program instructions, said apparatus comprising: a primary pipelined processing unit for performing data processing, said primary pipelined processing unit being responsive to a cancellation condition to cancel processing of a partially completed cancellable program instruction; a fix-up pipelined processing unit; and a pseudo instruction generator responsive to at least one cancellable program instruction that can be subject to cancellation to generate a cancellation fix-up instruction that is issued to said fix-up pipelined processing unit, said cancellation fix-up instruction being operable upon occurrence of a cancellation condition to control said fix-up pipelined processing unit to produce a state in which said partially completed program cancellable instruction may be re-executed at a later time.
The apparatus of the present invention recognises the above problem and addresses the problem by providing an apparatus to handle cancellation of program instructions and to restore the apparatus to a state in which the program instruction can be re-executed without, for example, storing the original value of the base address in separate specially provided and controlled hardware. It does this by using a pseudo-instruction to deal with cancellation, the pseudo-instruction being fed down a pipeline of a fix-up processing unit in the same way as any other instruction. This means that much of the interlock and forwarding logic of the pipelined processor can be re-used to handle cancellation thereby reducing the need for dedicated special purpose logic. Thus, if an abort occurs the normal instruction will be cancelled, while the fix up pseudo instruction will only complete in such a case.
The advantages of the present invention become greater as machines are adapted to launch more instructions at once and do more out of order execution. In such machines a cancellation fix-up pseudo-instruction allows almost the same hardware which deals with execution order and forwarding for standard instructions to deal with keeping the cancellation fix-up in the right place in the order. This would otherwise become an increasingly difficult task for dedicated special purpose hardware.
Advantageously, said pseudo instruction generator is operable to generate a fix-up instruction only when said cancellable program instruction comprises an instruction to overwrite the contents of a base register containing a base address for a data processing operation specified by said cancellable instruction.
Many instructions that are cancelled when partially completed can simply be re-executed without any problems. With other instructions which involve the changing of a value in the base register which is used as an address in the instruction re-execution of a partially completed instruction may give the wrong result as the base address register which is used by the instruction may have been changed. By differentiating between these two sets of instructions and only producing a fix-up instruction in the cases where re-execution may be a problem, this embodiment of the present invention provides an efficient way of dealing with these different situations.
In preferred embodiments, said pseudo instruction generator is operable in response to a cancellable program instruction that overwrites the contents of a base register containing a base address for a data processing operation specified by said cancellable instruction to generate a cancellation fix-up instruction that reads an initial value from said base register prior to it being overwritten.
By issuing a pseudo in
Arm Limited
Nixon & Vanderhye P.C.
Pan Daniel H.
LandOfFree
Mechanism for recovery from termination of a program... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mechanism for recovery from termination of a program..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for recovery from termination of a program... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3038058