Multiple Redundant Clock Circuit

1. Field of the Invention

The invention relates to a data processing device which consists of a plurality of parallel-operating data processing modules and which includes a multiple redundant clock device which consists of clock circuits. Each clock circuit is assigned to a respective data processing module. The clock device also includes an interconnection network for communicating output clock signals between the respective clock circuits. Each clock circuit includes an input majority decision device for determining a majority signal from the output clock signals received. Each clock circuit also includes a clock function generator which includes a readjustment circuit for readjusting the clock function generator according to the majority signal by way of a control function in order to reduce a deviation between the clock function signal and the majority signal. Each clock circuit also includes an output element for forming the output clock signal of the relevant clock circuit from said clock function signal.

2. Prior Art

A data processing device of this kind is known from U.S. Pat. No. 4,402,045. The known device is a so-called (n,k) system, notably a (4, 2) system in which quadruplication of the processor capacity and doubling of the storage capacity (i.e. doubling of the storage capacity per data word) are used in order to ensure that the device remains operational even when one of the data processing modules breaks down. It has been proposed to provide such a data processing device with a multiple redundant clock device (column 11, lines 25-30 of the cited Patent Specification) so that a given failure in the clock device is also permissible.

In this respect reference is made to the article by D. Davies et al: Synchronizing and Matching in Redundant Systems, IEEE Tr. Comp. Vol. C27, No. 6, June 1978, pages 531-539. The clock device shown in FIG. 9 of the cited article includes three clock circuits which receive the output clock signals of all three clock circuits. On mathematical grounds it has been found that such a triplication offers insufficient protection, so that errors can still occur, even when two clock modules operate correctly

It is an object of the invention to provide a data processing device of the kind set forth in the Field of the Invention in which the synchronization between the clock at the level of the clock pulse cycle is maintained, both in the case of malfunctioning of at the most one or at the most two clock circuits, and in the case of an arbitrary signal configuration of such malfunctioning. It is a further object of the invention that the input majority decision device and the readjustment circuit have a simple logic structure. It is further object to enable a short signal delay time and hence a high clock frequency, oscillations being self-damping at the level of the single clock cycle, and the difference between the synchronized clock circuits always remaining small in as much as they are restricted by the accuracy of the electronic components. The above arbitrary signal configuration may concern the shape of the signal itself. It may also concern the shape of the relevant output clock signal received by the other clock circuits. This shape need not be the same for all other clock circuits.

The object in accordance with the invention is achieved in that there are provided four data processing modules, each of which includes a respective clock circuit, each input majority decision device receiving exclusively the output clock signals of the other clock circuits in order to determine a two thirds majority therefrom, the control function by the majority signal implementing a deviation reduction factor which is substantially smaller than 1 for each signal transition in the binary majority signal. Notably Exclusive-OR functions whose comparatively long signal delay times form a known drawback can thus be dispensed with. For example, when the aim is to achieve a clock frequency of 8 MHz, this means a half period of approximately 60 ns. The delay time of many commercially available components is approximately 10 ns. The spread of this delay time is also in the same order of magnitude. Due to these two effects, the error margin will be reduced by such a value when a very simple input majority decision device is used. If use were made of a more complex deviation determining device comprising a series connection of a plurality of such components, the resistance against errors of such a clock device would usually become illusionary.

The invention also relates to a multiple redundant clock device for use in such a data processing device as well as to a clock circuit for use in such a data processing device or such a clock device.

Further advantageous aspects are described in the dependent claims.

The majority decision device usually supplies a bivalent majority signal. The clock function generator supplies the clock function signal which is recurrent with the clock period. The clock function is readjusted by the readjustment circuit which receives the majority signal. In many embodiments the readjustment circuit is functionally combined with further parts of the clock function generator, so that it does not form a separate part thereof. The output element forms the output clock signal from the clock function signal for supply to the majority decision devices. In some embodiments the output element is notional. In other embodiments the output element can introduce a phase shift, for example, by inversion.

The invention will be described hereinafter with reference to a number of figures and tables.

FIG. 1 shows a data processing device in accordance with the invention;

FIG. 2 shows a multiple redundant clock device for use in the device shown in FIG. 1;

FIG. 3 diagrammatically shows a four-fold redundant clock device;

FIG. 4 illustrates a multiple clock device which cannot cope with a given error situation;

FIG. 5 illustrates this error situation and its consequences;

FIG. 6 shows the variation of various quantities as a function of time;

FIG. 7 shows a clock circuit which includes a filter circuit;

FIG. 8 shows a clock circuit which includes a crystal;

FIG. 9 shows an alternative embodiment of FIG. 8;

FIG. 10 shows a further alternative embodiment of FIG. 8;

FIG. 11 shows an alternative embodiment which includes a phase-locked loop;

FIG. 12 is Table 1 of formulae;

FIG. 13 is Table 2 of formulae;

FIG. 14 is Table 3 of formulae;

FIG. 15 is Table 4 of formulae.

FIG. 1 shows a simple block diagram of a multiprocessor computer in accordance with the invention which includes a multiple redundant clock device. The computer includes four computer modules. Each computer module includes a processor module, its own clock circuit, and a data word reconstruction module. There are four processor modules: 200-206. Each clock circuit 220-226 applies clock signal to the associated processor. Each clock circuit also applies clock signals to all other clock circuits, and hence indirectly to the other processor modules. Each processor module applies its output data to all four data word reconstruction modules 210-216 which together constitute a data word reconstruction device. In each data word reconstruction module given data errors can be detected and/or corrected: the correct data is then applied to the associated processor module in which data processing can take place.

A computer subdivided into a number of modules is described in the cited U.S. Patent No. 4,402,045. Therein a code word consisting of code symbols is formed on the basis of a data word consisting of data symbols. After encoding, each computer module treats only a part of the code word, for example one code symbol. This operation concerns, for example memory storage, followed by reading and regenerating the code symbol. In order to reconstruct the entire data word for an arithmetic operation, all code symbols are applied to all computer modules. It has been found that the operation can be correctly performed even when, for example one computer module malfunctions completely.

In accordance with the set-up shown in FIG. 1, the various operations in the various computer modules are synchronized by the clock device which consists of the clock circuits 220-226. The operation of the data word reconstruction modules can also be synchronized in this manner, but is not shown. When one of the computer modules, for example the module including the blocks 202, 212, 222, breaks down (data or clock), the other three modules can continue to operate as usual. According to the cited reference, for a four-fold processing capacity in the arithmetic and logic unit (ALU) and the like, the system need only have a two-fold storage capacity in the memory in comparison with a single, non-redundant processor (in the terminology used, the processor thus also includes the foreground memory; the background memory and further peripheral apparatus will not be considered herein).

Similarly, another multiple redundant data processing device (for example, a communication system or a word processing system) may also include such a multiple redundant clock device. The improved clock device will be described hereinafter. At the level of the data processing device an improvement is achieved in that the output clock signal is applied to only three other clock circuits.

FIG. 2 shows an embodiment of a multiple redundant clock device in accordance with the invention for use in the data processing device shown in FIG. 1. There are provided four clock circuits 20, 22, 24, 26 one of which is shown in detail at the gate level. The clock circuit 20 itself is described in the article by Davies et al, FIG. 9. This clock circuit includes three AND-gates 28, 30, 32 and one OR-gate 34. These gates together constitute the majority decision device 54. The other elements constitute the clock function generator 56. These elements are an 8-MHz crystal 36, resistors 38, 40, 42 (1000 ohms), a capacitor 46 (10 pF), an amplifier 50 (of the ECL type 10104 like the AND-gates) which has a non-inverting output and an inverting output which is denoted by a circle, and a voltage comparator 48 of the type LM311 which is connected in the manner shown. The feedback via the parts, 40, 42, 48, and 50 serves to adjust the duty cycle (the period during which the output clock signal is high, divided by the oscillation period) to substantially 50%. The readjustment of the oscillator circuit is realized by directly coupling the output signal of the majority decision circuit to the crystal connection. Other feasible clock circuits will be described hereinafter.

The cited article describes a clock device which consists of three clock circuits, the output clock signals thereof being applied to the inputs of all three majority decision circuits. It has been found by the present inventor that an incorrectly operating system is thus obtained in given circumstances, even when malfunctioning is limited to one clock circuit only. A first step in accordance with the invention consists in increasing the number of clock circuits to four. As will be described hereinafter, the clock device can then continue to operate correctly, even in the presence of an arbitrarily malfunctioning clock circuit. In accordance with FIG. 2, the output clock signal of the clock circuit 20 is applied only to the other three clock circuits 22, 24, 26, and is not fed back to the majority decision device of the own clock circuit. The same is applicable to the output clock signals of the other clock circuits. This is because feedback of an output clock signal to an input of the own clock circuit would necessitate a different method of treatment for the "own" output clock signal; such a method would require slow circuits, for example circuits utilizing Exclusive-OR gates.

FIG. 3 diagrammatically shows a four-fold redundant clock device. Each clock device includes a majority decision device (voter V1 . . . V4 which output respective majority signals d1 . . . d4. Each clock circuit also includes a clock function generator F1 . . . F4 which outputs an output clock signal c1 . . . c4. Each clock function generator is also shown to include a readjustment circuit B1 . . . B4 and a clock K1 . . . K4.

In this respect the FIGS. 4, 5 illustrate a triple clock device and an error situation which cannot be dealt with by this device, respectively. FIG. 4 shows three clock circuits which all receive the output clock signals a1 . . . a3. The majority decision devices V1 . . . V3 operate in the manner described with reference to FIG. 2 and output the signals b1 . . . b3. The elements T1, T2, T3 are delay lines having a delay of one half local clock period. The construction of an oscillator circuit by means of such elements, for example formed as a series connection of an odd number of inverters, is known per se. Finally, a respective inverter 401 is connected to the output of each delay line. FIG. 5 shows a feasible error situation when the second clock circuit malfunctions: this clock circuit supplies the upper clock circuit with a signal which is the same as a1(t) and the lower clock circuit with a signal which is the same as a3(t). The first three curves in FIG. 5 represent the three signals a1 . . . a3 as seen by the upper clock circuit. The fourth curve represents the signal b1(t) formed by the majority decision device V1. The next three curves represent the three signals a1 . . . a3 as seen by the lower clock circuit. The last curve represents the signal b3(t) formed by the majority decision device V3. It appears that the phase differences between the output clock signals b1(t) and b3(t) thus increases continually. When the same error pattern occurs in the circuit disclosed in the cited article, essentially a similar incorrect behaviour will be observed. Furthermore, various other error situations exist which can lead to such a desynchronizing system.

Therefore, the requirements to be imposed on an error-tolerant multiple clock device are as follows:

(a) when the phase difference between any pair of correctly operating clock circuits does not exceed a first limit value, this phase difference may not exceed this limit value either at a later instant (this will be demonstrated by the formula 4.2 of table 4 to be discussed hereinafter);

(b) when the phase difference between any pair of correctly operating clock modules exceeds a second limit value, this difference should increase in time (self-synchronizing). The decrease need not always be monotonic (this will be demonstrated by the formula 4.3). The two limit values may be the same or not; in any case they are smaller than one half clock period.

Hereinafter the "clock period" of a binary signal will be defined as an integer number which is incremented by one in reaction to each signal transition. The clock period of the signal ci(t) is ni and the clock period of the signal di(t) is m(i). The shift of the signal ci(t) on the clock period ni=k is referred to as xi(k). The shift of the signal di(t) on the clock period m(i)=k is referred to as yi(k). FIG. 6 shows an example of these quantities in a time diagram, the time being measured, for example in ns (10.sup.9 s). Between two successive signals the shift of the relevant signal remains unchanged.

Also defined is the difference in time shift between two clock signals:

For the description given hereinafter it is assumed that the majority decision device instantaneously determines the majority function, which determination is followed by a delay, after which the binary majority signal becomes available. A delay also occurs at the input of the clock function generator: these delays are represented together by Ti. The signal di appears at the output of this delaymechanism.

It is assumed that D is the closed interval between two real limits for which the function Fi is defined. For Fi it holds good that for each value of x in the interval D the function Fi is continuous and differentiable, its derivative being positive and smaller than 1. This derivative is the deviation reduction factor, that is to say the factor whereby a deviation between two signals is reduced. When this factor is high, for example close to 1, the deviation will be quickly reduced. When this factor is low, the reduction of the deviation will take longer. It has been found that the deviation reduction factor is preferably substantially less than 1, for example less than 0.8. This is because the susceptibility to disturbances is thus reduced, because the disturbance becomes only partly (or delayed by one or more periods) manifest in the output signal. In that case an incidental disturbance need not cause a loss of stability. The unfavourable properties of the circuit shown in FIG. 4 are inter alia caused by the fact that the deviation reduction factor has the value 1: any deviation will be immediately passed on in its entirety. Usually an even smaller value will be advantageous, for example a value smaller than or equal to 0.5 or even a value between 0.01 and 0.1. It holds good in general that as the deviation reduction factor is lower the stability of each individual clock circuit will be higher. However, the speed of reaction to a variation, for example a switch-on phenomenon will be slower. In some cases the initiation of synchronization will be strongly impeded when the reduction factor is low. However, positive results have also been obtained for such low values. Because of its high stability, a deviation reduction factor of, for example 0.001 may occur for a crystal. The derivative of Fi is referred to as Fi'. It is assumed that:

xi(k+l)=xi(k)+Fi(yi(k)-xi(k)).

In that case there will be a quantity zi,j(k) between yi(k)-xi(k) and yi(k)-xj(k) for which the formule 1 of table 4 holds good (notation 4.1). Expressed in words this formule means that the difference between the two signals at the instant (k+1) is equal to the difference between these two signals at the instant (k), increased and decreased, respectively, by an amount which depends on the signals at the instant k. Actually, the deviation is corrected for by the reduction factor (first expression), after which the known indermediate-value theorem is applied. A delay line can in principle be used as a function generator for Fi. However, because the respective deviation reduction factor F'i+1, it will not be suitable. Good results, however, can be obtained by means of a phase-locked loop (PLL), a band filter (notch filter) and a crystal.

Subsequently: when the phase shifts (skew) between the clock modules are small, it holds good for a multiple redundant clock device comprising n clock circuits of which at least G circuits operate correctly, that there exists a finite number A.sub.max and an integer number k>0, so that for the sub-set of correctly operating clock modules in the formule 4.2 holds good (see the above paragraph a). This means that a sufficiently accurate synchronization will no longer be lost, provided at least that no new malfunction occurs among the mutually synchronized clock circuits. Moreover, the condition of formule 4.3 is applicable.

The proof of the second condition (the above paragraph b) for a system including four correct modules is given in table (1) where, without prejudice to its generality: x1(k).ltoreq.x2 k).ltoreq.x3(k).ltoreq.x4(k). The formules 1.1 . . . 1.4 follow therefrom. The formules 1.5 . . . 1.10 follow from the definition of ri,j(k+1). If it is stipulated that .vertline.ri,j(k+1).vertline..ltoreq.r4,l(k)), the necessary and adequate condition of formula 1.11 is applicable, together with the definitions and conditions stated for 1.12.

The above first condition holds good for A.sub.max .gtoreq.A.sub.min, because if 0<ri,j(k).ltoreq.A.sub.max, i>j, and 0<F'(x)<1, there will be found .vertline.ri,j(k+1).vertline..ltoreq.A.sub.max.

In the case of one malfunctioning clock module (for example, No. 4) only the formulae for yi(k) will be different. Assume that table 2, formula 2.1 is applicable; in that case the formulae 2.2 . . . 2.4 hold good. Therein, hi(k) represents the effect of the signal of the malfunctioning (fourth) module on the process in the i.sup.th i=1, 2, 3) module. The prefactor 0.5 represents the effect of the majority decision. Subject to the condition of the formula 2.8 which does not imply a further restriction, the original second condition will hold good for formula 2.9. The original first condition will hold good for A.sub.max .gtoreq.A.sub.min.

FIG. 7 shows a clock circuit which includes a filter circuit. The function F can now be written as the formula 3.1, in which T is the period of the input signal and Ai is much larger than Bi. Subject to the condition 3,2, 3.1 can be approximated by 3.3. This results in 3.4. The factor E is determined mainly by the accuracy of the components. If (3.5) is applicable, 3.6 will follow therefrom. For example, if max.sub.i (e.sub.i)=0.01 and T=125 ns, the following will hold good: 0<E<1.4 ns. Electronic components having a short delay time and a comparatively small spread in the value of the delay are known for example from the catalogue FAST TTL LOGIC SERIES, published by Signetics Corporation, book IC 15 N, February 1984. The majority decision device can be formed by the component 74F64 (page 35.7 ff. of said book). This component has a delay time spread between 2.5 and 7 ns, so at the most 4.5 ns. A usually necessary inverting buffer will generally also imply a spread of 2 ns. The maladjustment of the frequency with respect to the optimum frequency of the relevant crystal can usually also imply a spread of 2 ns, thus in total a spread of 8.5 ns. Together with an additional spread caused by the comparison of the frequencies, this means a total of approximately 10 ns, which is an acceptable value for the relevant application. The output OR-gate of the majority decision device is wired internally in the FAST circuit. As indicated, two resistors from a voltage divider between the supply voltage (+) and ground. The output includes a buffer 100 which supplies a square-wave signal.

The same analysis is applicable when use is made of a crystal (FIG. 8). The only problem is due to higher harmonics of the oscillation frequency. These harmonics can remain negligibly small when the load capacitance C.sub.b and the load resistance R.sub.b of the series circuit are suitably chosen. For T=125 ns (8 MHz), it can be calculated that R=2.5 . . . 5 kohms, C.sub.b =10 . . . 20pF. In a practical realization, soldered connections and connection points already imply 10 pF. The factor ei is approximately equal to the sum of the tolerances of the load resistance and the load capacitance. This is because the resonant frequency of the crystal is accurate to from 10.sup.-5 to 10.sup.-6 and in the same order of magnitude as that of the components in the equivalent diagram. When the components exhibit a spread of 5% (ei=0.05), the most unfavourable phase shift will be approximately 10 ns. The circuit also includes a variable resistor 102, a damping resistor 104 and an inverter 106 (type 74 F 04) in order to compensate for the inversion effect of the majority decision device.

FIG. 9 shows an alternative embodiment for fixing the duty cycle at 50%. To this end, in addition to the presence of the capacitor 108 and the voltage divider 110/112, the output clock signal ci(t) is fed back, via the halving element 114, to the junction of the capacitor 108 and the resistor 110. The halving element 114 halves the voltage received under the influence of the supply voltage on a "positive" pole. Another embodiment consists in that the inverting buffer element (74 LS 04) and the halving element 114 are replaced by a buffer which includes a non-inverting output and an inverting output which is fed by the junction of the resistors 110 and 112. Both output signals are applied to a differential amplifier whose output is connected to the junction of the capacitor and the resistor 110.

FIG. 10 shows a further alternative embodiment of the clock circuit shown in FIG. 8; this alternative somewhat resembles an implementation involving a phase-locked loop. In addition to the crystal 120, the output buffer 122 and the majority decision device 124 there are provided:

a feedback for the clock output signal to the negative input of a difference determining device 126;

an integrating network consisting of a resistor 128 and a capacitor 130;

a capacitor 132 whose capacitance can be adjusted by the integration result, thus enabling readjustment of the oscillation frequency.

FIG. 11 shows an alternative embodiment involving a phase-locked loop. The circuit includes a majority decision device 142, a multiplier circuit 142, a low-pass filter 144 LOPAS, a voltage-controlled oscillator 146, and an output buffer stage 148. A variation of the phase of the signal di(t) is conducted through the low-pass filter LOPAS: fast variations, therefore, have no effect and are distributed in time. The function F is implemented by the loop: 0<F'<<1. The phase-locked loop does not operate at its own resonant frequency, because the frequency of the signal di(t) also depends on the phase-locked loops of the other clock circuits. The accuracy of the phase-locked loop and its internal phase shift must be taken into account in the same way as for the alternative embodiments including the bandfilter or the crystal.

It is to be noted that the various clock circuits in a multiple redundant clock system can be based on several of the principles of the FIG. 7 . . . 11. Furthermore, various modifications of the circuits of the FIGS. 7 . . . 11 are feasible.