Determinism in a multiprocessor computer system and monitor and processor therefor Number:7,155,704 from the United States Patent and Trademark Office (PTO) owispatent

Title: Determinism in a multiprocessor computer system and monitor and processor therefor

Abstract: A multiprocessor computer system which provides fault tolerance includes a number of processing sets. At least one of the processing sets is operable asynchronously of a second processing set. A monitor is connected to receive I/O operations output from the processing sets for identifying faulty operation of those units. The monitor is also operable to synchronise operation of the processing sets by signalling the processing sets on receipt of outputs from those units indicative of a plurality of them being at an equivalent stage of processing. The monitor provides for buffering of I/O operations output from the processing sets and for selective forwarding of those I/O operations to an external I/O bus. The processing set may be formed from a single processor or from multiple processors.

Patent Number: 7,155,704 Issued on 12/26/2006 to Williams

---

Inventors:	Williams; Emrys J. (Sunnyvale, CA)
Assignee:	Sun Microsystems, Inc. (Santa Clara, CA)
Appl. No.:	09/953,804
Filed:	September 17, 2001

---

Related U.S. Patent Documents

---

	Application Number	Filing Date	Patent Number	Issue Date
	09106883	Dec., 2001	6327668

---

Current U.S. Class:	717/127 ; 709/209; 714/11; 714/4; 717/129
Current International Class:	G06F 9/44 (20060101); G06F 11/00 (20060101)
Field of Search:	717/127-135,114 714/1,4,11,12,9,49 718/106,105 370/352,254 709/201,212,209 711/153 710/263 707/10 700/79

---

References Cited [Referenced By]

---

U.S. Patent Documents

	3623011		November 1971		Baynard et al.
	3763474		October 1973		Freeman et al.
	4196470		April 1980		Berg
	4564900		January 1986		Smitt
	4634110		January 1987		Julich et al.
	5161156		November 1992		Baum et al.
	5295260		March 1994		Pribnow
	5303143		April 1994		Sommer et al.
	5339404		August 1994		Vandling, III
	5513354		April 1996		Dwork et al.
	5533188		July 1996		Palumbo
	5640514		June 1997		Barthel et al.
	5675807		October 1997		Iswandhi et al.
	5737514		April 1998		Stiffler
	5745672		April 1998		Stiffler
	5751955		May 1998		Sonnier et al.
	5884018		March 1999		Jardine et al.
	5890003		March 1999		Cutts et al.
	5892895		April 1999		Basavaiah et al.
	5938775		August 1999		Damani et al.
	5991518		November 1999		Jardine et al.
	6011791		January 2000		Okada et al.
	6049798		April 2000		Bishop et al.
	6105053		August 2000		Kimmel et al.
	6151689		November 2000		Garcia et al.
	6154877		November 2000		Ramkumar et al.
	6189112		February 2001		Slegel et al.
	6243361		June 2001		McMillen et al.
	6263452		July 2001		Jewett et al.
	6496940		December 2002		Horst et al.
	6634019		October 2003		Rice et al.
	6694412		February 2004		Frank et al.
	2001/0049817		December 2001		Kashiwagi
	2002/0010735		January 2002		McMillen et al.

Foreign Patent Documents

	0104490		Sep., 1983		EP
	0286856		Mar., 1988		EP
	0447576		Mar., 1990		EP
	61023246		Jan., 1986		JP
	01128156		May., 1989		JP
	01183744		Jul., 1989		JP
	01300364		Dec., 1989		JP
	93/09494		May., 1993		WO
	95/15529		Jun., 1995		WO
	97/50024		Dec., 1997		WO

Other References

Hofmann et al., Distributed performance monitoring: methods, tools, and applications, IEEE, vol. 5, Issue 6, Jun. 1994 pp. 585-598. cited by exam- iner . Robinson et al., A temporal model for transparent monitoring of shared-memory multiprocessors, IEEE, Nov. 1-5, 1993 pp. 388-394. cited by examiner . Burkhart et al., Performance-measurement tools in a multiprocessor environment, IEEE, vol. 38, Issue 5, May 1989 pp. 725-737. cited by exami- ner . Michaels et al., A microprocessor-based instrument for nystagmus analysis, IEEE, vol. 65, Issue 5, May 1977 pp. 730-735. cited by examiner.

Primary Examiner: Zhen; Wei
Assistant Examiner: Rampuria; Satish S.
Attorney, Agent or Firm: Meyertons Hood Kivlin Kowert & Goetzel, P.C. Rankin; Rory D. Kivlin; B. Noe

---

Parent Case Text

---

This application is a continuation of U.S. patent application Ser. No. 09/106,883 (now U.S. Pat. No. 6,327,668, issued Dec. 4, 2001) filed on Jun. 30, 1998, of which this application is a continuation filed under 37 CFR 1.53(b).

---

Claims

---

What is claimed is:

1. A monitor for a multiprocessor system including a plurality of processing sets, wherein at least a one processing set is operable asynchronously of another processing set, the monitor being connectable to receive I/O operations output from the processing sets, the monitor being operable to synchronize operation of the processing sets by signaling the processing sets on receipt of progress indications indicative of a plurality of the processing sets being at an equivalent stage of processing, the monitor further being responsive to an interrupt from an I/O device to pass the interrupt to the processing sets with an acknowledgement signal for an equivalent progress indication, whereby the interrupt is passed to the processing sets at an equivalent stage of processing.

2. The monitor of claim 1, wherein the monitor is further operable, when an equivalent progress indication has been received from all processing sets, to return an acknowledgement signal to the processing sets.

3. The monitor of claim 1, wherein the monitor is operable to determine faulty operation of processing sets being monitored thereby on detecting non-equivalent operation thereof.

4. The monitor of claim 1, wherein the monitor is operable to receive I/O operations from a third processing set, the monitor comprising a voter operable to determine a fault on a processing set by majority voting.

5. The monitor of claim 4, wherein the monitor is further operable, where the system only comprises two remaining processing sets, to determine a fault on a processing set by initiating processing set diagnostics on the processing sets.

6. The monitor of claim 1, wherein the monitor is operable, when the system comprises two processing sets, to determine a fault on a processing set by initiating processing set diagnostics on the processing sets.

7. A monitor for a multiprocessor system including a plurality of processing sets, wherein at least a one processing set is operable asynchronously of another processing set, the monitor being connectable to receive I/O operations output from the processing sets, being operable to synchronize operation of the processing sets by signaling the processing sets on receipt of progress indications indicative of a plurality of the processing sets being at an equivalent stage of processing, and further being operable to buffer the I/O operations, to compare an I/O operation output from a processing set to I/O operations buffered for another processing set for determining equivalent functioning of the processing sets, and to issue a state modifying I/O operation only on determining equivalent operating of the processing sets.

8. A multiprocessor computer system comprising: a plurality of processing sets, wherein at least one processing set is operable asynchronously of another processing set; a monitor connected to receive I/O operations output from the plurality of processing sets for identifying faulty operation of the processing sets, the monitor being operable to synchronize operation of the processing sets by signaling the processing sets on receipt of progress indications indicative of a plurality of the processing sets being at equivalent stage of processing and being further operable, when an equivalent progress indication has been received from each of at least a plurality of processing sets, returns an acknowledgement signal to the processing sets from which a progress indication has been received.

9. The system of claim 8, wherein the progress indication is an I/O cycle.

10. The system of claim 9, wherein the progress indication is a special read I/O cycle.

11. The system of claim 8, wherein the monitor, when an equivalent progress indication has been received from all processing sets, returns an acknowledgement signal to the processing sets.

12. The system of claim 8, wherein a processing set is stalled at a progress increment when an acknowledgement signal for a previous progress increment has not been received, the processor being stalled until the acknowledgement signal for the previous progress increment has been received.

13. The system of claim 8, wherein the monitor is responsive to an interrupt from an I/O device to pass the interrupt to the processing sets with an acknowledgement signal for an equivalent progress indication whereby the interrupt is passed to the processing sets at an equivalent stage of processing.

14. The system of claim 8, wherein the monitor is operable to determine faulty operation of the processing sets monitored by the monitor on detecting non-equivalent operation thereof.

15. The system of claim 14, additionally comprising at least a third processing set, wherein the monitor is also connected to receive at least output traffic from the third processing set, the monitor being operable to determine a fault on a processing set by majority voting.

16. The system of claim 14, wherein the monitor is operable where the system comprises two processing sets to determine a fault on a processing set by initiating processing set diagnostics on the processing sets.

17. The system of claim 15, wherein the monitor is further operable where the system only comprises two remaining processing sets to determine a fault on a processing set by initiating processing set diagnostics on the processing sets.

18. A multiprocessor computer system comprising: a plurality of processing sets, wherein at least one processing set is operable asynchronously of another processing set; a monitor connected to receive I/O operations output from the plurality of processing sets for identifying faulty operation of the processing sets, the monitor being operable to synchronize operation of the processing sets by signaling the processing sets on receipt of progress indications indicative of a plurality of the processing sets being at equivalent stage of processing and being further operable to buffer the I/O operations, to compare an I/O operation output from a processing set to I/O operations buffered for another processing set for determining equivalent functioning of the processing sets, and to issue a state modifying I/O operation only on determining equivalent operating of the processing sets.

19. The system of claim 18, wherein each processing set is a symmetric multiprocessor comprising a plurality of processors.

---

Description

---

BACKGROUND OF THE INVENTION

This invention relates to providing determinism in a multiprocessor computer system, to a monitor and processor for such a system and to a method of operating such systems. A particular application of the invention is to fault tolerant processing systems.

Many processing systems operate to a strict timing regime, changing their internal state on a known clock. Such a synchronous design of a processing system results in a large finite state machine. The internal state and outputs of this machine are entirely predictable, if inputs are presented in a known relationship to the clock. This determinism enables the construction of a fault tolerant multi-computer system by providing checking hardware, which compares the operation of one processor or set of processors against that of another identical processor or set of processors. The checking hardware can be arranged to check for faults in the operation of one or more of the processing sets by comparing the outputs of those processing sets on each clock.

Other processing systems do not behave in such a simple manner. Examples of this type are processing systems where the clock is not known, where multiple unrelated clocks are used, or where processor operation uses no clocks at all. These processing systems cannot be modelled as synchronous finite state machines. It may not be possible to present inputs to these processing systems in any known relationship to the computer's internal state. The detailed operation of these machines is non-deterministic. This prevents ordinary construction of checking hardware to compare operation between identical systems.

An aim of the present invention is to enable the provision of a deterministic multiprocessor system where at least one processor, or set of processors, operates asynchronously of another processor or set of processors.

SUMMARY OF THE INVENTION

Particular and preferred aspects of the invention are set out in the accompanying independent and dependent claims. Combinations of features from the dependent claims may be combined with features of the independent claims as appropriate and not merely as explicitly set out in the claims.

In accordance with one aspect of the invention, there is provided a monitor for a multiprocessor system. The monitor includes a plurality of processing sets, where at least one processing set is operable asynchronously of another processing set. The monitor is connectable to receive I/O operations output from the processing sets. The monitor is operable to synchronise operation of the processing sets by signalling the processing sets on receipt of progress indications indicative of a plurality of the processing sets being at an equivalent stage of processing.

In an embodiment of the invention, therefore, in addition to providing for the monitoring of I/O operations, a monitor is provided for responding to outputs for the processing sets indicative of the processing sets being at an equivalent stage of processing to synchronise the operation of the processing sets. In this manner, a plurality of asynchronous processors can be kept in step in a deterministic manner, at least at selected points during processing. This facilitates the cross checking of I/O operations for fault tolerant operation and also facilitates the timely delivery of interrupts.

The monitor can be operable, when an equivalent progress indication has been received from each of at least a plurality of processing sets, to return an acknowledgement signal to the processing sets from which a progress indication has been received. In certain cases, the acknowledgement signal may only be returned to the processing sets when a progress indication has been received from all processing sets.

The monitor is preferably operable to pass an interrupt from an I/O device to the processing sets with an acknowledgement signal for an equivalent progress indication. In this manner, the interrupts can be passed to the processing sets in a deterministic manner at an equivalent stage of processing.

The monitor can determine faulty operation of the processing sets on detecting non-equivalent operation thereof.

The monitor may be operable with only two processing sets, or with three or more processing sets. Where the monitor is used with three or more processing sets, a faulty processing set can be determined by majority voting. Where the monitor is used with only two processing sets, or where further processing sets have failed leaving only two processing sets, a faulty processing set may be determined by initiating processing set diagnostics on the processing sets.

In a preferred embodiment of the invention, the monitor is connectable to receive I/O operations output from the processing sets, and is operable to buffer the I/O operations, to compare an I/O operation output from a processing set to I/O operations buffered for another processing set for determining equivalent functioning of the processing sets, and to issue a state modifying I/O operation only on determining equivalent operating (or equivalent operation or functioning) of the processing sets.

In accordance with another aspect of the invention, there is provided a multiprocessor computer system. The system includes a plurality of processing sets, wherein at least one processing set is operable asynchronously of another processing set. The system also includes a monitor as described above.

In a preferred embodiment of the invention, the synchronising and fault monitoring operations are performed by a common I/O monitor unit.

Each of the processing sets can be configured, for example by the provision of appropriate control code and/or appropriate hardware, to record its progress in processing instructions and to issue a progress indication to the monitor as an I/O operation each time a predetermined progress increment has been recorded. Issuing the progress indication as an I/O operation, facilitates the use of a monitor unit for both synchronisation and fault monitoring purposes. However, the progress indication could instead be output as, for example, a signal on a dedicated or shared signal line.

Each processing set can include an instruction counter, with a progress indication for each progress increment of n counts. In a preferred embodiment the counter is implemented as a decrementer with a progress indication being issued when the decrementer underflows.

In order that the period between progress indications is relatively constant, it is advantageous to associate each instruction with a count value, whereby the counter is modified by the count value for an instruction on retiring of the instruction. The count value can be dependent on one or more of an instruction type, an operand and an address.

The recording of the progress of instruction processing can be suspended in a processing set for execution of certain instructions, such as an instruction executed by a software emulation in a processing set.

In order to allow for differences in processing speed in respective processing sets, while still maintaining processing sets substantially in step, a processing set is stalled on recording a progress increment when an acknowledgement signal for a previous progress increment has not been received by the processing set. The stalled processing set is kept stalled until the acknowledgement signal for the previous progress increment has been received by the processing set.

The monitor can be connected to receive and buffer I/O operations output from the processing sets, to compare an I/O operation output from one processing set to I/O operations buffered for another processing set for determining equivalent functioning of the processing sets, and to issue a state modifying I/O operation only on determining equivalent operating of the processing sets. A non-repeatable state modifying operation could be a read instruction with side effects or a write instruction. An embodiment of the invention can thereby respond to I/O instructions in an efficient manner, directly forwarding I/O operations which are not state modifying (i.e., where these may be withdrawn if required without corruption if a fault were subsequently determined), and buffering I/O operations prior to being forwarded until equivalent operation has been determined if the I/O operations are state modifying. For example, a read instruction having no side effects could be issued directly from the monitor on first receipt thereof from a processing set.

In a triple-modular-redundancy system (TMR), or higher order redundancy system, equivalent operating of the processing sets can be determined by majority voting on I/O operations. As an alternative, equivalent operating of the processing sets could be determined when all processing sets have output the same I/O operation. The policy for determining equivalent operating of the processing sets could be varied according to the number of processing sets being monitored.

To facilitate the determination of equivalent operations to be compared, the monitor can be operable:

to determine a buffer for each I/O operation dependent upon first invariant information (e.g., an I/O operation type and/or a processor number within a processing set) in the I/O operation;

to determine an order of I/O operations within the identified buffer dependent on second invariant information (e.g., an address phase ordering or an order number) in the I/O operations; and

to determine equivalent operation of the processing sets on the basis of equivalent third invariant information (e.g., write value data, an I/O command and an address) in the I/O operations at equivalent positions in equivalent buffers for the processing sets.

Each processing set may be a symmetric multiprocessor comprising a plurality of processors.

Where each processing set includes at least one resource for each processing set shared by the processors of the processing set the monitor can be configured to ensure equivalent ordering of mutexes (mutual exclusion primitives) for the processing sets for controlling access by the processors of the respective processing sets to the respective resources, thus maintaining equivalent operation of the processing sets.

The mutex ordering mechanism can form part of a monitor connected to receive I/O operations output from the processing sets for synchronising the operation of the processing sets by signalling the processing sets on receipt of output I/O operations indicative of a plurality of them being at equivalent stage of processing.

The monitor can comprise both a voter for determining equivalent ordering of I/O operations and common mutex storage accessed by voted I/O operations. It can also include a mutex manager. The mutex manager can include a mutex start register and a mutex stop register for each processing set. The mutex manager can include multiple sets of mutex start registers and a hash mechanism for accessing a mutex list for an I/O cycle.

In accordance with a further aspect of the invention, there is provided a processor for a multiprocessor computer system, the processor comprising a progress indication generator, the progress indication generator generating a progress indication representative of a determined increment of instruction processing greater than one instruction.

The invention also provides a method of indicating the progress of a processor in executing instructions in a multiprocessor computer system, where the processor is operable asynchronously of at least one other processor. The method may comprise the steps of: modifying a count value for each instruction executed; and outputting a progress indication for a determined number of counts.

In accordance with another aspect of the invention, there is provided a method of operating a multiprocessor computer system comprising a plurality of processing sets, wherein at least one processing set is operable asynchronously of another processing set and a monitor connected to receive I/O operations output from the plurality of processing. The method comprises:

detecting progress indications output by the processing sets; and

synchronising operation of the processing sets by signalling the processing sets on receipt of progress indications indicative of a plurality of the processing sets being at equivalent stage of processing.

BRIEF DESCRIPTION OF THE DRAWINGS

Exemplary embodiments of the present invention will be described hereinafter, by way of example only, with reference to the accompanying drawings in which like reference signs relate to like elements and in which:

FIG. 1 is a schematic block representation of a multiprocessor computer system;

FIG. 2 is a schematic representation of one processing set for the system of FIG. 1;

FIG. 3 is a schematic block diagram of a monitor unit of the system of FIG. 1;

FIG. 4 illustrates the stalling of a processor to allow another to catch up;

FIG. 5 is a schematic block diagram of an aspect of a processor of FIG. 1;

FIG. 6 illustrates special I/O cycles for progress indication;

FIG. 7 illustrates the keeping of processors in step;

FIG. 8 is a flow diagram illustrating operation of the system of FIG. 1;

FIG. 9 is a schematic block diagram illustrating an aspect of the monitor unit of FIG. 1;

FIG. 10 is a schematic block diagram illustrating a further aspect of the monitor unit of FIG. 1;

FIG. 11 is a schematic block diagram illustrating an aspect of the system of FIG. 1;

FIG. 12 is a schematic block diagram illustrating a further aspect the system of FIG. 1; and

FIGS. 13A and 13B are a schematic block diagram illustrating mutex hardware and a representation of an associated address map, respectively;

FIG. 14 is a schematic block diagram illustrating another aspect of the system of FIG. 1; and

FIG. 15 is a schematic block diagram illustrating a further aspect of the system of FIG. 1.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

FIG. 1 is a schematic overview of a multiprocessor computer system 10 comprising a plurality of processing sets 12, 14, 16 and an input/output (I/O) monitor unit 18. The multiprocessor computer system 10 can comprise only two processing sets 12, 14, or may comprise further processing sets such as the third processing set 16 shown in dashed lines, or even further processing sets. Each of the processing sets could be formed by a single, individual, processor, or may comprise a group of processors (for example a symmetric multiprocessor (SMP) system) and would normally be provided with local memory. Such a processing set is also known in the art as a CPUset. The processing sets are arranged to operate under the same or equivalent programs. The I/O monitor unit 18 links individual processing set I/O buses 22, 24, 26, etc. from the processing sets 12, 14, 16 to a common I/O device bus 20 to which I/O devices are connected. The monitor unit 18 thus forms a bridge between the processing set I/O buses 22, 24 26, etc. and the I/O device bus 20. Although one monitor unit and one I/O device bus 20 is shown, a plurality of monitor units such as the monitor unit 18, each with a respective I/O device bus 20, may be provided.

The I/O monitor unit (monitor) 18 is arranged to detect a difference in operation between the individual processor units 12, 14, 16 to determine faulty operation of one or more of those processing sets 12, 14, 16.

If more than two processing sets are provided, the monitor unit can detect a difference in operation between the processing sets and can employ majority voting to identify a faulty processing set, which can be ignored. If just two processing sets are used, or if following elimination of one or more faulty processing sets only two valid processing sets remain operable, a difference between the operation of the processing sets can signal faulty operation of one of the processing sets, although identification of which one of the processing sets is faulty can be a more complex task than simply employing majority voting.

The structure shown in FIG. 1 could be that for a synchronously operating multiprocessor system. In this case, because the individual processing sets 12, 14, 16 are operating synchronously, they should provide the same I/O outputs at the same time, and therefore it is an easy matter for the monitor unit 18 to compare those outputs to determine whether the processors are still in synchronism.

The structure shown in FIG. 1 also applies to a system where the processing sets 12, 14, 16 are not, or are not all, synchronously operating. In this case, the difficulty arises in determining what I/O outputs need to be compared and when these need to be compared by the monitor unit 18 in order to determine equivalent operating (i.e. equivalent operation or functioning) of the processing sets 12, 14, 16.

In simple terms, in the case of an asynchronous system, the monitor unit 18 observes the I/O outputs from the processing sets 12, 14, 16 and also presents I/O inputs to the processing sets 12, 14, 16. The monitor unit 18 acts to synchronize the operation of the processing sets 12, 14, 16 as described in more detail below. If one processing set (e.g. 12) presents an I/O output and another processing set (e.g. 14) does not, the monitor unit 18 waits to see if the output of the other processing set 14 eventually arrives. It can be arranged to wait up to a time limit, the worst case difference in the operating time between the compared processing sets. If no output has arrived, or a different output has arrived, the monitor unit 18 can be arranged to flag the event as a mis-compare. This approach can be used to build a fault tolerant computer by having all I/O operations from the processing sets 12, 14, 16 pass through the monitor unit 18. The monitor unit 18 can delay passing on an I/O operation until it is sure that at least a certain number or proportion of the processing sets, typically a majority of the processing sets, concur. If the monitor unit knows that the I/O operation will not change the state of the I/O system--a read without side effects, for example--it can pass the I/O operation as soon as the first I/O operation output from the fastest compared processing set arrives, to enhance operating speed. Even if, in a fault tolerant processing environment, the system eventually decides that the cycle was a mistake, it will have done no harm, and the optimization could speed things up.

FIG. 2 is a schematic overview of one possible configuration of a processing set, such as the processing set 12 of FIG. 1. The processing set 14 can have the same configuration. In FIG. 2, one or more processors (here four processors) 30 are connected by one or more internal buses 32 to a processing set bus controller 34. The processing set bus controller 34 is connected via a processing set I/O bus 22 to a monitor unit (not shown in FIG. 2). Although only one processing set I/O bus 22 is shown in FIG. 2, in other examples there may be multiple monitor units, in which case there would be one processing set I/O bus 22 per monitor unit from the processing set bus controller 34. In the processing set 12 shown in FIG. 2, individual processors operate using common memory 36, and receive inputs and provide outputs on the common processing set I/O bus(es) 22 via the processing set bus controller 34. It will be appreciated that FIG. 2 is a schematic representation of one example only of a possible configuration for a processing set and that other configurations are possible in other examples depending upon the processing and other requirements of the processing set concerned. For example, a processing set may include only a single processor, with or without memory and with an I/O bus controller.

FIG. 3 is a schematic overview of an example of a monitor unit 18. As shown in FIG. 3, the monitor unit 18 includes a voter/controller 50. Respective I/O bus interfaces 52 are provided for each of the I/O buses 22, 24, 26 to the processing sets 12, 14, 16 depending on the number of processing sets provided in the system. Respective buffers 54 are provided for buffering I/O operations received from the buses 22, 24, 26. Buffer stages 55 each comprise a bus interface 52 and a corresponding buffer 54. Return lines 56 provide for signals to be passed between the voter 50 and the respective bus interfaces 52. The voter/controller is responsive to the I/O operations received from the buses 22, 24, 26 in order to control the passing of I/O operations via the common I/O device bus interface 58 to the common I/O device bus 20. The voter/controller is also operable selectively to control a degree of synchronization of the asynchronously operating processing sets 12, 14, 16.

This `degree of synchronization` is based on selectively stalling the processor(s) 30 of the processing sets 12, 14, etc. without the need for a synchronous clock. This is achieved by arranging for each processor to provide a progress indication so that the monitor can tell how far processing has proceeded. In the distant past, processors were arranged to output a pulse on the completion of each instruction. However, this is no longer appropriate. Nowadays, instructions are completed faster than can be signaled externally. Also, the out-of-order nature of execution makes it difficult to decide exactly when an instruction has completed. Is it when the instruction itself is finished, or when the instruction and all earlier instructions are finished? These complications need a more sophisticated progress indication.

The progress indication is used by the monitor to slow down a processor so that it does not become too far out of step with another. For this, processors also need to provide some way to allow the monitor to stall them.

FIG. 4 is a timing diagram illustrating the stalling of one processor to allow another to catch up. In FIG. 4, time increases from left to right. A first, faster, processor P1 issues a progress indication at 40 and is permitted to continue to processing unless it receives a stall indication from an external monitor. In response to the return of a stall indication from the monitor to the first processor P1, this processor then stalls (as represented by a block symbol) until the progress indication is supplied at 42 by the second, slower, processor P2. The first processor is then permitted to proceed at 44 on receipt of a release from the monitor.

Progress indications should be generated such that the time intervals between them are approximately constant, such that they do not come so fast that as to make electrical signaling impractical, and such that progress indication is deterministically related to the instructions executed. For stall requests, it is desirable that the external electronics does not have to be exceptionally fast either to request or to refrain from requesting a stall. When the external electronics does not request a stall, the processor should not be slowed in any way. However, when the stall is requested, the processor should halt in a precise state, with all instructions up to the stalled instruction retired, and no instructions beyond it issued.

One example of a mechanism for providing a suitable progress indication is to assert an output every N instructions, where N is some fixed (or even programmable) number of instructions. This can be achieved by providing an instruction counter which outputs a progress indication every N instructions. This works well when all the instructions take approximately the same time to execute. If the instructions vary in execution time, or some instructions may be extended by external communications (like an I/O read operation), this simple mechanism may provide time intervals between progress indications that are too variable for convenience.

A more sophisticated mechanism for providing a progress indication enables the instruction count to vary according to the real state. This could take into account the variation in instruction timing to provide more-or-less constant intervals between progress indications.

Where reference is made to the `real state` this is to be understood to encompass the programmer visible state, subject to certain constraints. Thus it includes the content of a fixed set of registers, including the program counter and main memory, but excludes transitory elements such as caches and intermediate pipeline values. The `real state` includes all data required for context switching between processes plus, for example, operating system status data.

FIG. 5 illustrates an example of a mechanism for achieving this. In FIG. 5, an instruction-to-count converter 61 translates each instruction as it is executed by the execution unit 60 into an approximate time equivalent. This represents a best estimate of how long the instruction is going to take to execute. To do this, the converter 61 takes into account one or more parameters of the instruction, such as the instruction type, the operands being handled, and the results produced, including addresses used, and may also take account of previous instructions. One or more look-up tables 62, which may be programmable, can provide conversion factors between the parameters and timing information for input to the converter 61.

To provide determinism, the converter 61 does not take into account data not included in the real state of the processor, such as the congestion in pipelines or whether a variable is in a cache or not. The approximate time equivalent, a number, is fed to the decrementer 64, where it forms a decrement value to be subtracted from the current value stored in the decrementer 64. When the decrementer 64 underflows through zero, it produces a carry output 65 which is received by a progress controller 66. The progress controller 66 can then output a signal externally as the progress indicator 67. Before the next decrement operation, the decrementer is reinitialized to an initial value from a register 63, which may be programmable.

The instruction-to-count converter 61 may include stored state information. One application of this is accounting for software emulation of particular instructions. When the converter 61 detects (e.g., from the instruction type information) that an instruction is to be emulated instead of executed, it sets an internal flag to show that it should no longer count instructions, equivalent to producing decrement values of zero. When the converter 61 sees the return-from-emulation instruction at the end of the emulation routine, it produces the decrement value for the emulated instruction, which it could compute internally or which could be provided by special code in the emulation routine. In this way, a processor which emulates some instructions could be made equivalent to one which executes them all in hardware, for comparison purposes.

The carry output 65 can be used by the progress controller 66 to provide a progress indication 67 output from the processor as a pulse or a step on a signal wire. Alternatively, the carry output can lead to the progress controller 66 issuing a special progress indication I/O cycle to be scheduled on the processor I/O bus. For example, the processor can issue a special read cycle on the I/O bus at each progress indication. This is illustrated schematically in FIG. 6.

Before moving to FIG. 6, it is to be noted that a block 68 is shown in FIG. 5. This represents a sent/acknowledgment indicator 68 (see FIG. 5), the purpose and operation of which will be described later.

FIG. 6 is a timing diagram in which time increases from left to right. FIG. 6 represents an internal progress indication 1001, which results in the processor issuing special progress indication I/O request 1002. At some later time, the monitor 18 responds with 1003. Later, the processor generates another internal progress indication 1004, which will trigger another cycle externally. Using this system, it is possible to stall the processor automatically. If the processor is designed so that it cannot issue progress indication 1004 before it has received response 1003, the monitor 18 can have the effect of stalling a processor by merely delaying delivery of 1003. Provided 1003 arrives adequately before 1004, the processor will execute at full speed. Delaying 1003 can postpone 1004 indefinitely. Accordingly, with the arrangement represented in FIG. 6, the progress of two processors of different speed can be kept in step.

FIG. 7 is also a timing diagram in which time increases from left to right. As shown, following an internal progress indication 3001, a faster processor 3000 issues special progress indicator I/O cycle request 3002. This is before a slower processor 2000 issues its equivalent request 2002, following an internal progress indication 2001. The monitor 18 refrains from issuing responses 2003 and 3003 until it has observed both requests 2002 and 3002. This inhibits processor 3000 from progressing to the state where it can issue internal progress indication 3004, so keeping the processors in step.

Along with the responses 2003 and 3003, the monitor can send interrupt information. This could be as simple as a one-bit interrupt request or could be a whole packet of interrupt data. The processor can use this to determine whether it is going to take an interrupt or continue normal processing. If the processor is designed to take interrupts only at the precise instruction associated with an internal progress indication, then any requested interrupt will be taken by processor 2000 at progress indication 2004, and by processor 3000 at 3004. For lockstep processors, this would be at the precise same instruction on processors 2000 and 3000. The monitor acts to keep the progress indications in step, and can be sure that both processors take the interrupt on the same progress indication without ambiguity. The processors themselves ensure deterministic delivery of progress indication, affected only by their real state.

Interrupts delivered in this way can be delayed by about two progress indications before the processor begins to execute the interrupt routine. It is desirable to arrange that this delay does not produce an unacceptable performance.

When processor 2000 is nearing progress indicator 2004, it may well want to begin issuing instructions beyond that precise instruction implied by 2004. Instructions execute out-of-order for speed. In order to provide a precise interrupt model at this precise instruction, this may not be allowed. This would slow the processor. In order to avoid this, the processor could be designed to ignore this restriction when response 2003 has already been received and the processor already knows that no interrupt will be taken at 2004. So, if 2003 occurs early enough before 2004, the processor will continue at top speed. This provides a mechanism for delivering interrupts precisely at deterministic instructions independent of the operating speed of the processor and without slowing the processor unnecessarily, which is precisely what is needed in an asynchronous lockstep system.

Instead of performing a special progress indication I/O cycle on the I/O bus, different signaling means can be used for fundamentally the same protocol. Wires separate from the I/O bus can carry the processor special cycle request to the monitor and carry the response back. This allows the progress indication interval to be short without consuming I/O bus bandwidth. If wanted, the processor can perform a special I/O cycle after delivery of an interrupt request to fetch a packet of interrupt data.

In fault tolerant systems, the monitor is arranged to deal with the possible problem of a missing progress indication. An upper bound is set for the time between progress indications. The upper bound chosen in any particular implementation can be based on processor speed variations and could be defined as a multiple of the normal speed of the processors. The upper bound is typically defined as a function of the normal time between progress indications. Accordingly, if the progress indications are 1 us apart, the upper bound might be 2 us. If the progress indications are 100 ms apart, the upper bound might be 200 ms. This would mean that a monitor would have to wait at least 200 ms instead of 2 us before beginning recovery action if no progress indication arrived. This illustrates that it is desirable to have short and well-defined intervals between progress indications.

FIG. 8 is a flow diagram illustrating the operation and inter-relationship of the various elements shown in FIG. 5 in order to enable selective synchronization of the individual processing set as described with reference to FIGS. 6 and 7.

Accordingly, when an instruction is dispatched, the decrementer 64 can be updated at step 74, following determination of an instruction count value by the converter 61 at step 72. Although a decrementer 64 is shown in FIG. 5, in another implementation a positive changing counter, for example a modulo-n counter, could be used instead.

If, in step 76, the decrementer 64 has not underflowed, then control passes back to step 72 for the next instruction. However, if the decrementer has underflowed, a test is made in step 78 to determine whether an acknowledgment for a previous progress indication has been received. If an acknowledgment for a previous progress indication has been received, a progress indication is sent to the monitor unit at step 86, and a sent/acknowledgment indicator 68 (see FIG. 5) is set in the progress controller 66 to indicate that a progress indication has been sent, but no acknowledgment has been received. Control then passes back to step 71 to initialise the decrementer 64.

If, in step 78, it is determined that the set/acknowledgment indicator 68 is still set, indicating that a progress indication has been sent, but no acknowledgment thereto has been received, the processor is stalled in step 80. The processor remains stalled until it is determined in step 82 that the sent/acknowledgment indicator 68 has been re-set, indicative of receipt of the acknowledgment for the progress indication previously sent. At this time, the processor is released in step 84. Control then passes to step 86 where the next progress indication is sent and the sent/acknowledgment indicator 68 is once more set. Control then passes back to step 72 for the next instruction.

Accordingly, it can be seen that, according to FIG. 8, the processor is stalled if an acknowledgment for a previous progress indication has not been received at the time the processor determines that a further progress indication should be sent to the monitor unit 18.

As mentioned above, the I/O progress indications can be sent to the monitor unit 18 as specific I/O operations. Alternatively, they could be supplied over a special hardwired connection (not shown).

FIG. 9 is a schematic diagram of aspects of the monitor unit responsive to the specific progress indication I/O operations from the individual processing sets to establish concurrent operation of those processing sets, and to return acknowledgement to the individual processing set when concurrent operation has been determined, as described with reference to FIG. 7. Elements already described before as indicated by like reference signs will not be described again here.

As shown in FIG. 9, a progress register 94 is provided for each corresponding processor of the processing sets connected to the monitor unit 18. Thus, for example, if there are three processors P0, P1 and P2 in each of two processing sets PSA and PSB, then there will be three progress registers R0, R1 and R2 for the processors P0, P1 and P2, respectively. To provide synchronization, each processor in the processing sets is operable to issue a special I/O read operation to the respective progress registers. Thus, in the example above, the P0 processor in each of processing sets PSA and PSB issues special I/O read operations to progress register R0, the P1 processor in each of processing sets PSA and PSB issues special I/O read operations to progress register R1 and the P2 processor in each of processing sets PSA and PSB issues special I/O read operations to progress register R2. I/O synchronization within the monitor is arranged to delay the return of a response to the read processors (i.e. by returning the read data from progress register 94 concerned) as an acknowledgement to the processors until an equivalent read has been performed by each of equivalent processors of the processing sets. This response is what is then used to control the stalling of the processors as has been described with reference to FIG. 6 to 8 above.

It will be seen that the combination of the logic in the processing sets 12, 14, etc. described with reference to FIG. 5 for reading the progress registers 94 of FIG. 9 in the monitor unit 18 enables the processing of the individual processing sets to be made deterministic and synchronized in accordance with specific points during the processing. As indicated, this avoids the need for a timer, which would not be deterministic in the individual processing set, by the provision of a specific I/O operation or other progress indication signals at predetermined points in the processing determined by counting the individual instructions executed in the processing sets. As indicated, it is preferred that the count is made dependent on the nature of the individual instructions.

While the processing sets 12, 14, etc. may not be strictly deterministic, they should respect some constraints on their operation. It should be possible to perceive an order in the instructions the processors execute. Normally, this is the order in which the instructions are written in the program, modified by branch operations. Processors may internally reorder the instructions, and may execute some instructions in parallel, but the eventual effect should be the same as if the instructions were executed in the order the programmer expects. If this is not the case, the program result may not be as the programmer expects. (In this regard, interrupts and DMA will be discussed below). In addition, the order of I/O operations presented as outputs to the monitor unit 18 are determined absolutely by the program, independent of the detailed timing of execution. This is typically the case, as it is difficult to manage I/O devices without this capability. It should be noted, however, that processors routinely reorder writes behind reads for speed. It is possible to provide for this and still carry out effective I/O operations. This can be managed with separate read and write comparison channels in the monitor unit, providing the processor is guaranteed not to reorder writes among themselves or reads among themselves, and will deliver at least the first read and the first write to the monitor unit at once.

FIG. 10 is a schematic representation showing aspects of the monitor unit 18 for controlling the passing of I/O operations to the common external bus or buses 20 and also for determining faulty operation of the individual processor units.

The I/O bus interfaces 52 connected to the respective I/O buses 22, 24 of the processing sets 12, 14 are operable to identify write and read operations and respectively to buffer the write and read operations in respective buffers 114/115. These buffers 114/115 represent one example of a configuration of the buffers 54 of FIG. 3. It should be noted that this is one exemplary arrangement and that other arrangements may not separate writes and reads as indicated in FIG. 10, or may separate I/O operation according to different criteria. An I/O writes voter 116 is operable to compare individual write operations within the respective buffers 114 for the individual I/O processing sets 12, 14, etc. to determine receipt of equivalent I/O write operations. The monitor unit is operable to buffer the write operations for up to a predetermined time as determined by a timer 120 and is operable to identify a fault in respect of one of the processors when corresponding I/O operations are not received from each of the processors. Similarly, a reads voter 118 is provided for comparing buffered read operations and operates in a similar manner.

In a triple modular redundant (TMR) arrangement with three processing sets, the determination of which of the processing sets is faulty can be accomplished by majority voting in the writes and reads voters 116 and 118, respectively. Alternatively, in an arrangement where there are only two processing sets (i.e. a dual modular redundant arrangement (DMR)), the determination of which of the processing sets is faulty can be more complex, but can still be determined by diagnostic techniques.

The writes and reads voters 116 and 118 can be arranged to pass write and read operations via the common I/O bus interface 58 to the common I/O bus or buses 20 in accordance with appropriate strategies. For example, as indicated above, if an I/O operation will not change the state of the I/O system (a read without side effects, for example) the monitor unit can be arranged to pass the I/O operation as soon as the first I/O operation output from a processing set arrives. In other circumstances, where an I/O operation will change the state of the I/O system (a write operation or a read operation with side effects, for