JPS6217774B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention selects a request signal that arrives fastest when N mutually independent processors in an information processing device share the same resource and asynchronously request its use. The present invention relates to a competition processing circuit that has a function and can self-inspect for internal failures.

In a resource sharing system in which multiple processors that operate independently share resources such as memory, arithmetic units, and data buses, two or more processors simultaneously generate signals requesting the use of the same resource, causing contention. Sometimes. Therefore, in order to improve system efficiency and reliability, it is important to easily realize hardware that can appropriately allocate resource usage rights to each processor without causing problems in such cases. It is.

By the way, if you do not set a specific priority among each processor and treat them completely equally, you should follow the principle of first come, first serve, in which the processor that generates the request signal first is allowed to use the resource. Contention is thus controlled. One example of such a system is a shared memory scheme in a multiprocessor system.

In addition, there are countless situations in computer systems, exchange systems, etc. that require control of contention caused by parallel processing.

The technology that has been known to realize hardware that can control such conflicts was developed in 1977.
In April, IEICE Transactions D, Vol.57-D, No.
4, Published in the paper ``A method for configuring an asynchronous arbiter'' published in PP242-244.

However, in the above-mentioned conventional technology, if a failure occurs inside the competition control circuit itself,
The intended control function may not be achieved, and in some cases, a fatal error may occur in selecting two or more request signals at the same time.

SUMMARY OF THE INVENTION In order to overcome the drawbacks of the prior art described above, an object of the present invention is to perform a function of selecting request signals from N mutually independent processors on a "first come, first served" basis, and to prevent failures occurring inside the circuit from occurring by itself. The purpose is to provide a simple circuit that can be tested.

According to the present invention, all inputs are binary signals.
2N (2N-1) input 1 output logic circuits each having a logic function whose output takes a second value only when the value of
It consists of 2N external input terminals and 2N external output terminals, and the 2N logic circuits have 2N external input terminals and 2N external output terminals.
The outputs of the 2N logic circuits are respectively supplied to the input lines of all the logic circuits belonging to groups other than the group to which the logic circuit belongs, and the corresponding external inputs. By connecting each of the 2N external input terminals to one input line to the corresponding logic circuit, the signal which arrived earliest among the N sets of competing input signals is connected to the input terminal. A contention processing circuit is obtained which has the function of selecting the internal faults and the function of self-checking for internal failures.

Next, one embodiment of the present invention will be described in detail with reference to the drawings.

The figure shows that in one embodiment of the present invention, in particular N=2
The configuration for the case is shown below.

In the figure, 11, 12, 13, 14 are NAND
It is a logic circuit. The logic function of the NAND logic circuit is as follows. In other words, the output signal has a logic value of "0" only when all input signals have a logic value of "1"; otherwise, when at least one input signal has a logic value of "0", the output signal has a logic value of "0". It becomes “1”.

101, 102, 103, and 104 are external input lines connected to external input terminals (not shown), respectively.

The NAND logic circuits 11 and 12 form one set, and correspond to the set of external inputs 101 and 102. NAND logic circuits 13 and 14 constitute another set, which corresponds to the set of external inputs 103 and 104.

21, 22, 23, and 24 are ordinary NAND logic circuits (or inverters), but they do not constitute the present invention, but are used to more effectively implement the present invention, as will be explained later. be.

The output line 201 of the NAND logic circuit 11 is the NAND
It is connected to input lines to the logic circuits 13 and 14, and is also connected to an external output terminal (not shown) via an output line 301 of the inverter 21.

The output line 202 of the NAND logic circuit 12 is the NAND
It is connected to the input lines to the logic circuits 13 and 14, and is also connected to an external output terminal (not shown) via the output line 302 of the inverter 22.

The output line 203 of the NAND logic circuit 13 is the NAND
It is connected to input lines to the logic circuits 11 and 12, and is also connected to an external output terminal (not shown) via an output line 303 of the inverter 23.

An output line 204 of the NAND logic circuit 14 is connected to input lines to the NAND logic circuits 11 and 12, and is also connected to an external input terminal (not shown) via an output line 304 of the inverter 24.

The example shown in the figure is an embodiment in the case of N=2, but in the case of general N, the above connection relationship follows the following rules. That is, 2N
NAND logic circuits are divided into groups of two, and each
The output of the NAND logic circuit becomes an input to all the NAND logic circuits belonging to groups other than the one to which it belongs, and also becomes an output signal to the corresponding external output terminal.

As inputs to each NAND logic circuit, the outputs of all NAND logic circuits belonging to other groups, that is, (2N-2) outputs, are supplied according to the above rules, and the outputs corresponding to the NAND logic circuit in question are supplied as inputs. One input line is connected to the external input terminal. Therefore, the total number of input lines to each NAND logic circuit is (2N-1).

Therefore, in the embodiment shown in the figure:
Since N=2, the circuit of the present invention is constituted by four external input terminals, four external output terminals, and four NAND logic circuits corresponding to each.
As inputs to the NAND circuits 11, 12, 13, and 14, the corresponding external input lines 10
1, 102, 103, and 104 are supplied.

Next, the operation when there is no failure inside the circuit shown in the figure, that is, when the circuit is normal will be explained.

A pair of external input lines 101 and 102 correspond to a request signal of one processor 1, and another pair of external input lines 103 and 104 correspond to a request signal of another processor 2 independent of processor 1.

Normally, when there is no request from the processor, the external input line pairs 101, 102 and 103, 10
The signal values of 4 are (0, 0), respectively.
When a request is generated from the processor 1, the pair of external input lines 101 and 102 take on signal values (1, 1). Similarly, when a request is generated from the processor 2, the pair of external input lines 103 and 104 take the signal value (1, 1). Unless there is a failure in the circuit shown in the figure and the external input terminal not shown, the signal value of each external input line pair will never take (1, 0) or (0, 1).

Now, if there is no request from any processor,
The values of external input lines 101, 102, 103, and 104 are "0". At this time, the values of the output lines 201, 202, 203, and 204 of the four NAND logic circuits are all "1". Therefore, the external output line 301,
The values of 302, 303, and 304 are all "0". This output state means that there is no request from any processor.

Next, when the processor 1 issues a request, the values of the external input line pair 101 and 102 become (1, 1), so the values of the output lines 201 and 202 of the NAND logic circuits 11 and 12 both become "0". As a result, the values of external output lines 301 and 302 both become "1".
This output state means that processor 1's request has been granted, and processor 1 can therefore occupy and use the resource. When processor 2 issues a request in this state, external input line pair 10
The value of 3,104 becomes (1,1), but since the output value "0" of NAND logic circuits 11 and 12 is supplied as input to NAND logic circuits 13 and 14, cannot be inverted, and the values of external output lines 303 and 304 also remain at "0". In other words, external output lines 301, 30
If the value of 2,303,304 is (1,1,0,0), it means that the request from processor 1 has already been granted, and in this state, the request from processor 2 will not be granted. Conversely, if Processor 2's request occurs earlier and is granted, Processor 1's request will not be granted for the same reason as above. The external output at this time is (0, 0, 1, 1).

By the way, if processor 1 and processor 2 issue requests almost simultaneously, external input line 1
The values of 01, 102, 103, and 104 all become "1" almost at the same time.

As a result, four NAND logic circuits 11, 12,
13 and 14 try to change from 1 to 0 all at once because the condition for inversion is satisfied. For example, if NAND logic circuit 11 completes the change from 1 to 0 fastest, NAND logic circuits 13 and 14 Since "0" is supplied to the input, it can no longer be inverted, and the values of output lines 203 and 204 remain "1".

On the other hand, since the NAND logic circuit 12 changes from 1 to 0, the external output lines 301, 302, 30
The value of 3,304 becomes (1, 1, 0, 0), and the request from processor 1 is accepted. vice versa
If the 1→0 change in the NAND logic circuit 13 or 14 occurs instantaneously, the NAND logic circuits 11 and 12
can no longer perform a 1→0 change, and the external output line 3
The values of 01, 302, 303, 304 are (0, 0,
1, 1), and the request from processor 2 is accepted.

As can be seen from the above explanation, when the circuit shown in the figure is normal, it handles conflicts between the request signals of processor 1 and processor 2, selects the one that generates the request earlier, and gives the exclusive right to use the resource. It has the function of giving.

Next, the operation when a failure occurs in a part of the circuit shown in the figure will be explained.

For example, consider a case where the NAND logic circuit 11 fails and the value of its output line 201 is fixed at "1".

In this case, the value of the external output line 301 is fixed to "0". Therefore, when there is a request from the processor 1, both the external input lines 101 and 102 become "1", and as a result of the NAND logic circuit 12 being inverted, the value of the external output line 302 becomes "1"; The values of all external output lines other than this are "0".
That is, external output lines 301, 302, 303,
The value of 304 remains (0, 1, 0, 0) and no change occurs thereafter. Since this value never occurs when the circuit is normal, observing this output value immediately indicates that a failure has occurred within the circuit.

Further, if the NAND logic circuit 11 fails and the value of its output line 201 is fixed at "0", the value of the external output line 301 is fixed at "1". Therefore, when there is no request from the processor 1, the values of the external input lines 101 and 102 are "0", so the NAND logic circuit 12 is not inverted, and the values of the external output lines 301, 302, 303, and 304 are ( 1,0,0,0). This value also never occurs when the circuit is normal, so by observing this value it is possible to know that an internal failure has occurred.

Similarly, NAND logic circuits 12, 13, 1
4 or their input/output lines, or inverter 2
1, 22, 23, 24 or any one of their input/output lines is fixed at "0" or "1".
The value of 03,304 is (1,0,0,0),(0,
1,0,0), (0,0,1,0), (0,0,0,
Either 1) is observed. Since these values never occur under normal conditions, it can be determined that a failure has occurred. In other words, the values of the output input line pairs 301, 302 and 303, 304 are (0, 0) or (1, 1) during normal operation, and (1, 0) or (0, 1) occurs during failure. , thereby allowing self-inspection. However, even under normal conditions, due to element delay during (0,0) → (1,1) change or (1,1) → (0,0) change, (1,0) or (0 ，
1) can occur, so if the output is observed continuously for a sufficiently long time compared to the delay time of the element, and the value (1, 0) or (0, 1) is maintained during that time, a failure occurs. It is determined that It should be noted that, as a matter of course, the external output line 301,
The values of 302, 303, 304 are (1, 1, 1,
1) will never happen. Because 4
This is because the NAND logic circuits 11, 12, 13, and 14 mutually supply their outputs to the inputs of other sets to perform a mutual inhibition function. This causes a fatal malfunction for the contention processing circuit, ie, it will never grant approval to more than one request at the same time.

By the way, if the circuit shown in the figure is normal, requests from processors 1 and 2 occur simultaneously, and external input lines 101, 102, 103, and 104 change from 0 to 1 almost simultaneously, the NAND logic circuit 11,
12, 13, and 14 try to cause a 1→0 change all at once. At this time, for example, if the NAND logic circuit 11 first changes from 1 to 0 as described above, the NAND
The logic circuit 13 can no longer achieve a 1 → 0 change, but instantaneously changes from 1 → 0 → 1 in a “whisker-like” manner.
pulses may be generated. This whisker-like pulse can be easily absorbed by inserting a capacitive delay element such as a capacitor. Inverters 21, 22, 23, and 24 shown in the figure are provided for this purpose, and are elements having capacitive delay characteristics like ordinary NAND elements.
The NAND logic circuits 11, 12, 13, and 14 themselves usually have capacitive delays, so the whisker-like pulses may not occur in some cases. In this case, inverters 21, 22, 23, and 24 shown in the figure are not required.

The operation of the embodiment of the present invention has been described above for the case where N=2, but the same applies generally to the case of competition processing for N processors.

Also, although we have used the case of using a NAND logic circuit as an example, it is exactly the same even if a NOR logic circuit is used.Furthermore, it is also possible to use a circuit that combines OR and NOT, or a circuit that combines AND and NOT. Embodiments of the invention can be constructed in exactly the same way.

In summary, the basics of the present invention are that 2N
Divide the NAND (or NOR) logic circuits into groups of two, supply the output of each NAND logic circuit to all NAND logic elements other than the group to which it belongs,
Another object of the present invention is to realize a simple circuit that can process conflicting request signals from N processors and self-test internal failures at the same time by using two-wire input/output signals.

[Brief explanation of the drawing]

The figure is a block diagram showing the configuration of an embodiment of the competition processing circuit of the present invention. In the figure, 11,1
2, 13, 14 are NAND logic circuits, 21, 22,
23 and 24 indicate inverters, respectively.

Claims (1)

[Claims] 1 2N with a logic function in which the output takes the second value only when all inputs take the first value of the binary signal
(2N-1) input 1-output logic circuits, 2N external input terminals and 2N external output terminals each having a one-to-one correspondence with the logic circuits; The circuits are divided into groups of two, and the outputs of the 2N logic circuits are respectively supplied to and correspond to the input lines of all the logic circuits belonging to groups other than the group to which the logic circuit belongs. connected to the external input terminal,
By connecting each of the 2N external input terminals to one input line to the corresponding logic circuit, the 2N external input terminals have the function of selecting the earliest arriving signal among the N sets of competing input signals. A contention processing circuit characterized in that it has a function of self-inspecting for failures.