JPS5812612B2 - Asynchronous signal arbiter - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention provides an "earliest request" method when N mutually independent processors in an information processing apparatus asynchronously request the use of any of M mutually equivalent resources. The present invention relates to an asynchronous signal arbitrator that sequentially allows up to M processors to use resources.

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 can follow the "first come, first served" principle, in which the processor that generates the request signal first is allowed to use the resource. Conflicts are controlled.

In addition, if there are multiple resources that are completely equivalent from the processor's perspective, and any one of them can be used, the available resources can be used regardless of the correspondence between individual processors and resources. Permission is granted to the same number of processors as the number of processors.

In other words, in general, when N processors share M (N>M) resources that are completely equivalent to each other, usage permission is granted to the Mth processors from the top to the top in the order of request signal generation. The (M11)th and lower processors are made to wait until a resource becomes available.

One example of such a system is a multiple bus approach in a multiprocessor system.

That is, if each processor requests use of the bus,
Since that processor can be assigned to any free bus, it is always given permission to use the same number of processors as there are buses, and as soon as one bus becomes free, the next processor will use the free bus. be able to.

In addition, there are countless situations in computer systems, communication systems, switching systems, etc. that require control of contention caused by parallel processing as described above.

Conventionally known hardware implementation technology that can control such competition was published in the Journal of the Institute of Electronics and Communication Engineers D. Vol. J61-D, No. 11
, PP888-890, in the paper "A form of multi-resource asynchronous arbiter".

However, the above-mentioned conventional technology has the disadvantage that the operation speed is slow due to the large number of elements required for hardware implementation and the large number of gate stages through which signals must be propagated.

The object of the present invention is to overcome the drawbacks of the above-mentioned prior art while
The object of the present invention is to provide extremely simple hardware for controlling contention according to the "first come, first served" principle when N mutually independent processors request the use of M equal resources.

The asynchronous signal arbitrator of the present invention includes N external input terminals,
A multi-input, one-output logic circuit having a logic function such that the output takes the second value only when all inputs take the first value of the binary signal is arranged in l-to-l correspondence with the external input terminals. As part of multiple inputs to each of the logic circuits, the signals of the corresponding external input terminals and the other (N-1
) M number of N-way selection circuits configured by supplying the output signals of all the logic circuits; As the remaining part, output signals of each of the logic circuits corresponding one-to-one to the same external terminal as the logic circuit included in each of the other (M-1) N-way selection circuits are provided. The feature is that up to M external input signals can be selected on a "first come, first served" basis from N external input signals that are asynchronously activated.

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 invention, in particular N=3, M=2
The configuration for the case is shown below.

In the figure, 511, 512, 513, 521, 522
, 523 is a NANC 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 "L"; otherwise, when at least one input signal has a logic value of "O", the output signal has a logic value of "0". The logical value becomes "l".

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

1 and 2 indicated by broken lines are three-way selection circuits each consisting of three NAND logic circuits.

In the three-way selection circuit 1, the NAND logic circuits 511, 5
12 and 513 are external input lines 101 and 10, respectively.
2 and 103 in one-to-one correspondence.

Similarly, in the three-way selection circuit 2, the NAND logic circuit 5
21, 522, and 523 are external input lines 1, respectively.
01, 102, and 103, and are arranged in a one-to-one correspondence.

External input line 1 is used as an input to the NAND logic circuit 511.
01, the output line 312 of the NAND logic circuit 512, and the NAND logic circuit 512.
An output line 313 of an AND logic circuit 513 and an output line 321 of a NAND logic circuit 521 are supplied.

As an input to the NAND logic circuit 512, external input line 1
02, the output line 311 of the NAND logic circuit 511, and the NAND logic circuit 511.
An output line 313 of an AND logic circuit 513 and an output line 322 of a NAND logic circuit 522 are supplied.

External input line 1 is used as an input to the NAND logic circuit 513.
03, the output line 311 of the NAND logic circuit 511, and the NAND logic circuit 511.
An output line 312 of an AND logic circuit 512 and an output line 323 of a NAND logic circuit 523 are supplied.

As an input to the NAND logic circuit 521, external input line 1
01, the output line 322 of the NAND logic circuit 522, and the NAND logic circuit 522.
An output line 323 of the AND logic circuit 523 and an output line 311 of the NAND logic circuit 511 are supplied.

As an input to the NAND logic circuit 522, external input line 1
02, the output line 321 of the NAND logic circuit 521, and the NAND logic circuit 521.
The output line 323 of the AND logic circuit 523 and the output line 312 of the NANI) logic circuit 512 are supplied.

As an input to the NAND logic circuit 523, external input line 1
03, the output line 321 of the NAND logic circuit 521, and the NAND logic circuit 521.
An output line 322 of an AND logic circuit 522 and an output line 313 of a NAND logic circuit 513 are supplied.

The connection relationships described above comply with the following rules.

That is, the inputs to each NAND logic circuit included in the three-way selection circuit 1 are the external input line corresponding to that NAND logic circuit and the remaining two NAND logic circuits included in the three-way selection circuit 1. output line, and one NAND included in the three-way selection circuit 2 and corresponding to the same external input line.
The output line of the logic circuit is supplied.

Furthermore, the inputs to each NAND logic circuit included in the three-way selection circuit 2 are also supplied according to exactly the same rules.

Therefore, for example, the inputs to the NAND logic circuit 511 include the corresponding external input line 101, the output lines of the remaining two NAND logic circuits 512 and 513 included in the three-way selection circuit 1, and the output lines of the three-way selection circuit 1. A NAND logic circuit 52 included in the selection circuit 2 and corresponding to the external input line 101
This means that one output line is supplied.

As mentioned above, the figure shows the case where N=3 and M=2, that is,
This shows the configuration of an embodiment of the present invention in which three processors issue usage requests for two resources. It is composed of N lines and M N-way selection circuits corresponding to the three-way selection circuits 1 and 2, and each N-way selection circuit is composed of N NAND logic circuits.

In addition, each of the NAND logic circuits included in each N-way selection circuit has its input as the corresponding external input line and the remaining (N-1) NAND logic circuits included in the same N-way selection circuit. output lines of NAND logic circuits and other (M-1) NAND logic circuits.
The same external input line, one for each of the selection circuits, and the output line of the corresponding NAND logic circuit are supplied.

Therefore, the number of inputs to each NAND logic circuit is given by.

In the example shown in the figure, the 4-input NAND logic circuit 6
An embodiment of the present invention is configured by three external input terminals (not shown).

The reference numerals 11, 12, 13, 21, 22, 23 are conventional NAND logic elements, but they do not constitute the invention, and as explained later, they can be used to more effectively implement the invention. It is something.

Next, the effects of the present invention will be explained by explaining the operation of the device shown in the figures.

When three processors corresponding to external input lines 101, 102, and 103 request the use of resources, the logic value of the corresponding input line changes from "0" to "l11."

The two resources correspond to three-way selection circuits 1 and 2, respectively.

Normally, when there is no request, the loop input lines 101 and 102
, 103 has a logical value of "0".

At this time, the seven force lines 311, 3 of the six NAND logic circuits
The logical values of 12, 313, 321, 322, and 323 are all "'1".

Therefore, the output lines 211, 212, 213, 2 to the outside
The logical values of 21, 222, and 223 are all "0".

This means that there are no requests for use of any resources by any of the processors.

Now, assume that the three processors issue usage requests independently from each other, and the external input lines 101, 102, and 103 change from "0" to "II" in this order.

NA because the external input line 101 becomes “l 11” the earliest.
The condition that the output signals of ND logic circuits 511 and 521 are inverted is satisfied.

If the NAND logic circuit 511 inverts the output signal faster, the output line 311 becomes “0゛゜”, so the NAND
The output signal of the ND logic circuit 521 can no longer be inverted and remains "tl&".

Furthermore, as a result, the outputs of the NAND logic circuits 512 and 513 also remain at "1".

That is, the three output lines 311, 31 of the three-way selection circuit 1
Out of 2,313, only the output line 311 corresponding to the external input line 101 that changed from “0” to “1” the earliest changes to “111”.
→'゛0'' change occurs and other output lines 312 and 313
remains at “1°”.

This means that for the external input line 101, the three-way selection circuit 1
This means that the use of the corresponding resource is permitted.

On the other hand, in the three-way selection circuit 2, the output line 321 of the NAND logic circuit 521 is fixed to "l&I" because of the output line 311, but the output lines of the remaining NAND logic circuits 522 and 523 are arbitrary. is left behind.

In this situation, the external input line 10, which has the second highest request generation order,
Due to the “0”→“111” change of 2, the output line 322 of the NAND logic circuit 522 causes a “1”→“0” change.

As a result, the output line 323 of the NAND logic circuit 523 is “
It is fixed at 1".

Therefore, the three output lines 321, 322 of the three-way selection circuit 2
, 323, only the output line 322 corresponding to the external input line 102 that changed from "0" to ",N second earliest is ",4".
1→゜“0゛change, and the other output lines 321 and 32
3 remains "l".

This means that the external input line 102 is permitted to use the resources corresponding to the three-way selection circuit 2.

As a result, since the two resources are already occupied, the external input line 103 of the third rank remains on standby while changing from "0" to "1".

After that, if the processor corresponding to the external input line 101 finishes its work, the output line 311 of the NAND logic circuit 511 changes 101 from "1&1→Z40h&".
is inverted and becomes "l&I."

As a result, the output line 313 of the NAND logic circuit 513 becomes “L”.
"→"O" change occurs, and the processor corresponding to the external input line 101 is given permission to use the resource corresponding to the three-way selection circuit 1.

At this time, the output line 312 of the NAND logic circuit 512 remains fixed at M, since the output line 322 from the three-way selection circuit 2 is "0".

In this way, permission to use the two resources corresponding to the three-way circuits 1 and 2 and the same number of processors is granted according to how quickly the requests are generated.

By the way, “0” of the first external input line 101 → “l”
Although the explanation has been made assuming that the output of the NAND logic circuit 511 is inverted in accordance with the change, the NAND logic direction circuit 511
Which of 521 and 521 is reversed first depends on its physical (
delay) characteristics.

If the output of the NAND logic circuit 511 is “t&1→
If it changes to “0”, as explained above, the NAND
The output of the logic circuit 521 remains fixed at "1", and in the opposite case, the output of the NAND logic circuit 511 remains fixed at "1".

At this time, as is clear from the logic function of the NAND logic circuit, it is impossible for both the outputs of the NAND logic circuits 511 and 521 to become "0".

However, due to signal propagation delays in elements and wiring,
For example, the NAND logic circuit 511 goes from “1” to “0” first.
``When a change occurs, a ``whisker-like'' pulse that changes from ``111 to 71 011 to 1'' may be generated instantaneously on the output line 321 of the NAND logic circuit 521.

This "whisker-like" pulse can be easily absorbed by inserting a capacitive delay element such as a capacitor into the output line.

The elements 11, 12, 13, 21, 22, 23 in the figure are provided for this purpose, and are ordinary NAND elements,
It is any logic element having capacitive delay characteristics such as an AND element.

NA-ND logic circuits 511, 512, 513, 521,
522 and 523 themselves usually have capacitive delays,
For this reason, the "whisker-like" pulse is often not generated.

In that case, elements 11, 12, 13, 21, 22 in the figure
, 23 are not necessary.

The operation of the embodiment of the present invention has been described above using the case of N=3 and M=2 as an example, but the operation is generally the same in the case of N processors and M resources.

As is clear from the figure, the delay time from input to output is equal to the delay of one stage of NAND logic circuit, and the operation speed is extremely high.

In addition, the number of required elements is generally NAND logic circuit.
M number, which is significantly reduced compared to the conventional technology.

Although the explanation has been given using a NAND logic circuit as an example, it is the same even if a NOR logic circuit is used.Furthermore, a circuit that combines AND and NOT,
Alternatively, the embodiments of the present invention can be configured in exactly the same manner using a circuit that combines OR and NOT.

In summary, the basics of the present invention are to provide M N-way selection circuits each consisting of N NAND or NOR logic circuits, and to input the output of each N-way selection circuit directly into the other N-way selection circuit. The object of the present invention is to realize a fast and simple hardware capable of handling competing requests for M resources from N processors on a "first come, first served" basis.

[Brief explanation of the drawing]

The figure is a block diagram showing the configuration of an embodiment of the present invention. In the figure, 1 and 2 are three-way selection circuits, 511, 51
2,513,521,522,523 are NAND logic circuits, 11,12,13,21,22,23 are NA
ND logic circuits are shown respectively.

Claims (1)

[Claims] 1 N external input terminals and a multi-input one-output logic circuit having a logic function such that the output takes the second value only when all inputs take the first value of the binary signal. N terminals are arranged in one-to-one correspondence, and as part of multiple inputs to each of the logic circuits, the signals of the corresponding external input terminals and all other (N-1) logic circuits are provided. M number of N-way selection circuits configured by supplying an output signal of of (M
-1) Asynchronously activated by supplying the output signal of each of the logic circuits in one-to-one correspondence to the same external terminal as the logic circuit included in each of all of the N-way selection circuits. An asynchronous signal arbiter characterized in that it is possible to select up to M signals on a "first come, first served" basis from N external human input signals.