JPH0253983B2 - - Google Patents

Description

Claim 1: comprising two input ports and one output port, each of the input ports having N input data lines, and the one output port having N output data lines; only one of said two input ports at a time in response to an active logic signal on any one of said N input data lines at said input port when an input port of and means for transmitting bits of multi-bit characters from the selected input port to the output port in parallel and synchronously with each other, each of the multi-bit characters an arbiter represented by active logic signals on M data lines of N input ports, where M is at least 2, and where N is greater than M and greater than 3; . 2. The arbiter of claim 1, wherein said means for sending includes an N-bit wide queue for receiving characters from said selected input port and communicating said received characters to said output port. 3. Each of the input ports further includes one input control line, and the sending means generates a control signal on the one input control line of the selected input port to control the input control line of the selected input port. 2. The arbiter of claim 1, including means for indicating when characters on the input data lines are acceptable and may change. 4. The output port further includes one output control line, and the sending means responds to a signal on the one output control line to
2. The arbiter of claim 1 including means for generating characters on the output data lines. 5 detecting a predetermined character on the N input data lines of the selected input port, and responsively detecting one of the two characters on the N data lines of the output port; 2. The arbiter of claim 1, further comprising means for generating a signal to indicate which input port has been selected. 6, further comprising means for detecting a predetermined character on the N input data lines of the selected input port and responsively deselecting it from the selected input port. The arbiter described in Section 1. 7. Each of the multi-bit characters is a series of externally generated A _S ...A _S M...MC _EM A _A ...A _A
a multi-bit character in the form of C _EA , generating one of two selectable characters on said output port immediately after said C _EM character is sent to said output port; 2. The arbiter of claim 1, further comprising means for identifying the input port from which the arbiter was sent. BACKGROUND OF THE INVENTION This invention relates to arbiters and selectors and their circuitry. Generally, an arbiter is a logic circuit having two input ports and one output port, and in its operation a message is sent from either input port to an output port. For example, one prior art arbiter is also the inventor of the present application.
No. 4,251,879, issued February 17, 1981 to Becky J. Clark. Also, generally speaking, a selector has one input port and two input ports.
In operation, a message is sent from one input port to a selected one of the two output ports. For example, one prior art selector
December 2, 1980 to Becky J. Clark, same as above.
No. 4,237,447, issued in 1999. The limitations that the arbiter and selector described above have are:
The point is that they only work on bit-serial messages. That is, messages are sent one bit at a time from its input port to its output port. Therefore,
The maximum baud rate at which these arbiters and selectors operate is relatively low. In order to increase this baud rate, it is also conceivable to connect a number of the above-mentioned arbiters and selectors in parallel. However, the problem with such parallel connections is that the bits do not follow parallel paths in synchronization with each other. The reason is that when a request arrives at both input ports at the same time, the arbiter randomly selects one or the other of the input ports. Therefore, multiple bits sent from a source through the parallel connection of arbiters and selectors described above will reach their destination in an unexpected and highly scrambled manner. It is therefore a primary object of this invention to provide an improved arbiter. Another object of the invention is to provide an arbiter that passes multiple bits in parallel from its input port to its output port. SUMMARY OF THE INVENTION The above objects and other objects are achieved by an arbiter comprising two input ports, one output port, means for selecting, and means for sending.
Each of the input ports has N input data lines and the output port has N output data lines. The means for selecting selects one of the two input ports at a time in response to an active logic signal on any one of the N input data lines at the input port when neither input port is already selected. Select only one. The sending means sends the bits of the multi-bit character from the selected input port to the output port in parallel and synchronously with each other. Each of the multi-bit characters is represented by an active logic signal on M out of N data lines of the selected input port;
M is at least 2 and N is greater than M and greater than 3.

[Brief explanation of the drawing]

Various features and advantages of the invention may be better understood by reference to the following detailed description and accompanying drawings. FIG. 1 shows a system of arbiters constructed in accordance with the present invention. FIG. 2 is a block diagram of one of the arbiters of FIG. 3-6 are detailed logic diagrams of one preferred embodiment of the arbiter of FIG. 2.

[Detailed description of the invention]

A preferred embodiment of the invention will now be described in detail with reference to FIGS. 1-6. First, FIG. 1 shows an example of how three arbiters 10A, 10B, and 10C constructed according to the present invention can be interconnected as a system. Of course, any other number of arbiters and selectors may be interconnected in an input port-output port format to form other systems. Arbiters 10A, 10B, and 10C are identical to each other; the letters A, B, and C are added only to identify their location within the system. Each arbiter includes two input ports and one output port. In Figure 1, reference numerals 11 and 12 indicate respective input ports;
Reference number 13 indicates the output port. In the system of FIG. 1, the output ports of arbiters 10A and 10B are connected to each input port of arbiter 10C. In operation, messages are sent from any input port of arbiters 10A and 10B to the output port of arbiter 10C. When each message is introduced with the arbiter system, A _S …A _S M…MC _EM A _A …A _A C _EA
and each message, after being sent to the output port 13 of the arbiter 10C, has the format A _S ... A _S M ... MC _EM A _A ... A _A C _EA . In the message formats described above, each symbol A _S , M, C _EM , C _EA and _AA represents one character. Also, this character is represented by M out of N codes. That is,
Each of the input ports 11 and 12 and the output port 13 of the arbiter includes N data lines, and the characters on the data lines are represented by the signals on the M lines of the N that are active. It will be done. Also, in the message format mentioned above,
The symbol M represents a character in the body of the message, and the symbols A _S , C _EM , C _EA and A _A represent control characters. The control character A _S is used in conjunction with a selector circuitry (not shown), which, if required, is connected to the output port 13 of the arbiter 10C. Control character C _EM
is used by the arbiter circuitry itself to indicate the end of the message body. one control character
A _A is generated by each arbiter to indicate which of its input ports the message will pass through. The A _A characters are two particular characters C ₀ and C ₁ of the set of possible characters for M. A _S character is also
Characters C ₀ and C ₁ . control character
C _EA is sent by the arbiter to indicate the end of the A _A character string. Turning now to FIG. 2, a block diagram of one arbiter is shown. In this block diagram, signals D _{01 .} . . D _0N represent the data signals on each input data line of input port 11, and signals D ₁₁ .
D _1N represents the data signal on each input data line of input port 12, and signals D _{1 .} . . D _N represent the data signal on each output data line of output port 13. Each input port also includes one input control line and the output port also includes one output control line. Signal A ₀ is generated by the arbiter on the input control line to input port 11, and the signal
A ₁ is generated by the arbiter on the input control line to input port 12, and signal A is received by the arbiter on the output control line to output port 13. Generally, these signals are utilized to regulate the transfer of characters from the output port's data line to the input port's data line. Detailed circuit diagrams of a preferred embodiment of the arbiter of FIG. 2 are shown in FIGS. 3, 4A, 4B, and 4C.
The operation of these logic circuits will now be described. In general, Figures 3 and 6 show the portion of the arbiter that selects one input port, and Figures 4A-4C and 5 route a character from the selected input port to the output port. The arbiter part is shown. Now, consider the logic circuit shown in FIG.
This logic circuit includes multiple NAND gates 20-1
...20-N, 21, 22, 23-1...23-N,
and 24-31 and two transistors 32A and 32B, which are interconnected as shown. NAND gates 20-1 to 20-N have input port 11
Each input data signal D ₀₁ to D 0N is received from the input data signal D 01 to D _0N .
Similarly, NAND gates 23-1 to 23-N
receives each input data signal D ₁₁ through D _1N from input port 12 . In the initial state, the input data signal D ₀₁ to
D _0N and D ₁₁ through D _1N are all inactive, which means low in this example. Similarly, in the initial state, signals R ₀ and R ₁ are both low, and signals S ₀ ′,
CLEAR ₀ ′, S ₁ ′, CLEAR ₁ ′, and RESET′ are all high. This initial state results from the signal RESET' being low for a period of time and changing to high. In this initial state, no input port is selected. When the circuit of FIG. 3 is in the initial state described above, an input port is selected in response to an input data signal for that input port to become active. That is, if any one of the input data signals D ₀₁ to D _0N goes high, input port 11 is selected, while if any one of the input lines D ₁₁ to D _1N goes high, input port 12 is selected. is selected. For example, assume that input data signal D ₀₁ goes high. In response, signal _R0 goes high. The output of gate 21 then goes low and its output latches signal _R0 high.
A high signal R ₀ causes the output of NAND gate 26 to go low. As a result, the transistor 32A
turns off, so its output goes high. Signal S ₀ then goes low, which causes the outputs of all gates 20-1 through 20-N to go high. Also, signal S ₀ from NAND gate 29 goes high, thereby indicating that input port 11 has been selected. Once an input port is selected, it remains selected until all messages have passed through it. Therefore, the input port 11 is
Remains selected until a C _EA character is received by its input port. When the C _EA character is received, the circuit of FIG. 6 operates to return the circuit of FIG. 3 to the initial state described above. This recursion to the initial state will be discussed at the end of this detailed description. Consider now the logic circuits of FIGS. 4A to 4C. FIG. 4A shows one bit of an N bit wide queue. This queue receives the character on the input data line from the selected input port and sends the character to the output data line of the output port. NAND gate 40-4
7 forms the input buffer to the queue, while NAND gates 50-54 form the output buffer to the queue. This queue is N bits wide. To construct this queue, the circuit of Figure 4A is repeated N times with some variation. This change allows any selectable control character A _A to be inserted into the message as described above. That is, character A _A can be any two codes of all possible sets by placing M out of N input data lines active. Some of these codes indicate that input port 11 is selected, while other codes indicate that input port 1 is selected.
2 is selected. If the kth bit of both these codes is 1, the queue for this kth bit is formed exactly as shown in Figure 4A. However, if the kth bit for both these codes is 0, then the queue for this kth bit is NAND gate 44.
and 45 are deleted. Also, if the kth bit of the code indicating that input port 11 is selected is 1, and on the other hand the kth bit of the code indicating that input port 12 is selected.
If the th bit is 0, the signal S ₀ is sent to the inputs of NAND gates 44 and 45. And if the kth bit of the code indicating that input port 11 is selected is 0, while input port 1
If the kth bit of the code is 1, indicating that 2 is selected, the signal S ₁ is sent to the inputs of NAND gates 44 and 45. Also, gate 54 only appears once, and its output is
Provided for all NAND gates 50 and 52. Feedback from the queue output buffer to the queue input buffer is provided by the circuit of FIG. 4B. This circuit uses multiple NAND
It includes gates 60-1 to 60-N, 61, 62, and 63-1 to 63-X. Here, X
is the number of combinations of N things taken M at a time. Therefore, NAND gates 63-1 to 6
3-X each detects one of the characters that may be present in the output queue. Therefore, if the output of any one of gates 63-1 through 63-X is low, the output buffer is full as indicated by signal _AK being true. Each of gates 60-1 through 60-N is also connected to receive a respective bit in the output buffer of the queue. One preferred means of generating control signals A ₀ and A ₁ to indicate when the characters on the N input data lines of a selected input port may be accepted and changed is shown in FIG. 4C. There is. This circuit includes NAND gates 70-1 to 70-X, 71-1 to 70-N, and 72
76 inclusive. As before, in this expression,
X represents the number of combinations of N items that take M items at a time. All these NAND gates are interconnected as shown. Each of NAND gates 70-1 through 70-X detects one character that may be present in the input buffer of the queue. Therefore, gate 70
A low at the output of any of -1 to 70-X indicates that the character is present in the input buffer. Also, gates 70-1 to 70-
Each of N is 1 in the buffer of the input queue.
connected to receive each bit. Note that four of gates 70-1 through 70-X detect each control character. These gates are 70-A, 70-
They are labeled B, 70-C, and 70-D. Gate 70-A detects the end of message control character _CEM , gate 70-B detects the end of address control character _CEA , and gates 70-C and 70-D detect the end of control character C0 _.
and detect C ₁ . They indicate which of the input ports is selected. All of these control characters are shown in Figures 3 and 6.
The operation of these circuits will now be briefly described. However, first of all,
To further understand how the circuit in Figure C operates, consider the following sequence. In the initial state, all input signals to the queue of FIG. 4A are inactive. That is, the signals D _0K , S ₀ , D _1K , S ₁ , and
SEND are all low and signal A _K ' is high. Then, in response to any input data line going high on one input port, either signal _S0 or _S1 goes high, as described in connection with FIG. Indicates the selected port. For example, suppose signal S ₀ goes high. Then, if the kth input data signal D _0K goes high, the output of NAND gate 40 goes low and the output of NAND gate 47 goes high. NAND gate 47 generates signal D _JK , _which is fed back through NAND gates 46 and 41, thereby latching the input buffer. Signal D _JK is also the 4th C
The signal is sent to NAND gates 70-1 to 70-X in the circuit shown. Then, if a total of M bits are present in the input buffer of the queue, the output of one of these gates 70-1 through 70-X goes low. This low causes the output of NAND gate 72 to go high;
1 through 71-N, thereby causing the output of NAND gate 72 to be latched high. Also, high signal S ₀ and
The simultaneous occurrence of a high from the output of NAND gate 72 causes the output of NAND gate 73 to go low;
Also, the output of gate 74 goes high. Therefore, input control signal A ₀ goes high to indicate that the character on the input data line has been received and may now change. Next, consider the sequence of how characters are transferred from the input buffer to the output buffer. Initially, it is assumed that output buffer control signal A is high. In this state,
The output of NAND gate 54 is low, which blocks the contents of the buffer from being transferred to the output buffer. However, if signal A goes low, the output of NAND gate 54 goes high. The simultaneous occurrence of two highs at the input of NAND gate 50 then causes that gate to go low, which causes the output of NAND gate 53 to go high. This high is
Feedback is provided through NAND gates 51 and 52, thereby latching the output buffer. Then all output buffer data signals D _K are
NAND gates 63-1 to 63- in Figure 4B
Sent to X. If M of these signals are high, the NAND gates 63-1 to 63-
One output of X goes low. This low forces the output of NAND gate 61 high. The high is then latched through the feedback provided by NAND gates 60-1 through 60-N. The high output of NAND gate 61 is
2's output low, and this low causes the next
The outputs of NAND gates 46 and 40 are driven high. If D _0K changes to low in response to A ₀ changing to high, the output of NAND gate 41 changes to high, thereby causing NAND gate 47
goes low. All input buffer data bits D _JK are NAND gates 70-1 to 70
- Sent to N. And if all signals D _JK are low, the outputs of all NAND gates 70-1 to 70-N go high, thereby
Forces the output of NAND gate 72 low. This in turn forces the input control signal A ₀ low,
This low indicates that the input buffer has been cleared and a new character can be present on the input data line. The low output of NAND gate 72 also returns the feedback provided by NAND gates 70-1 through 70-N to its initial state, thereby returning the circuit of FIG. 4C to its initial state. Now consider how characters are removed from the queue's output buffer. Initially, output control signal A goes high.
This in turn forces the output of NAND gate 54 low, which in turn forces the output of NAND gate 50 and 52
, thereby causing them to change high. When D _JK goes low as a result of clearing the input buffer,
NAND gates 50 and 51 turn high.
When NAND gates 50, 51, and 52 are all high, output signal _DK goes low.
NAND gates 60-1 to 60-N and 6
3-1 through 63-X detect lows on all bits of the queue's output buffer. And when this low is detected, NAND gate 6
The output of 1 goes low. This is next
The feedback provided by NAND gates 60-1 through 60-N is returned to its initial state and the circuit of FIG. 4B is returned to its initial state.
Also, the output of the NAND gate 62 shifts to high,
This allows new characters to be received by the input buffer of the queue. Characters continue to be sent from the queue's input buffer to the queue's output buffer in the manner described above until the control character _CEM is received by the input buffer. When the control character _CEM is received, it is sent to the output buffer and one control character A _A is generated at the input _buffer of the queue by the circuit of FIG. Since this character A _A is generated internally, no input control signal A ₀ is sent to it. Then the internally generated control character A _A
is passed from the input buffer to the output buffer, the input control signal A ₀ is forced low so that other control characters A _A generated by any preceding arbiter in the system wait. Allows you to move through the queue. In detail, the above sequence occurs as follows. First, signal D _0K goes high, thereby causing the signal from the input buffer of the queue to
D _JK is moved to high. All signal D _JK 4th
It is sent to NAND gates 70-1 to 70-X in Figure C. And there NAND gate 70-A
detects the control character C _EM . Note that the output of NAND gate 70-A does not go directly to the input of NAND gate 72, but rather to the input of NAND gate 80 in the circuit of FIG. The overall circuit in Figure 5 is a NAND gate 80
91, which are interconnected as shown. The output of NAND gate 81 is the output of NAND gate 7
Forced high in response to detection of control signal _CEM by 0-A. This high then forces the output of NAND gate 83 low. The output of NAND gate 83 is the output of NAND gates 81 and 82.
Feedback is provided to that input through Therefore, the low output of NAND gate 83 is latched. Also, the low output of the NAND gate 83 is a signal to the NAND gate 72 in FIG. 4C.
Sent as EM _B ′. This forces the output of NAND gate 72 high, which in turn causes input control signal _A0 to go high. In response to signal _A0 going high, all input data bits _D0K go low. Then, when signal A _K ' goes low indicating that the contents of the input buffer have been transferred to the output buffer, all signals D _JK in the input buffer of the queue go low. Normally when this occurs, NAND gate 72 in FIG. 4C will go low, thus causing input control signal _A0 to go low. However, in this case,
The signal EM _B ' from NAND gate 83 is latched low, and this signal is also connected to NAND gate 7.
2, so the input control signal A ₀ remains high. However, when the signal D _JK from the input buffer of the queue goes low, the NAND gate 70
-A's output goes high. This output is sent to NAND gate 85 of the circuit of FIG. 5, so that the output of NAND gate 85 goes low.
This then leads to the SEND from NAND gate 86.
Forces the signal high and forces the output of NAND gate 89 high. Queue input buffer NAND gate 44
is connected to receive the SEND signal and the A _K ' signal. Therefore, when signal A _K ' goes high, indicating that the output buffer is empty, the output of NAND gate 44 goes low. This causes the input buffer signal D _JK to be set high. Recall that there are four variations to the input buffer of the queue. These variations then allow any two codes C ₀ and C ₁ to be generated as control characters A _A at the input buffer in response to the SEND signal, as explained above. These two codes indicate which input port is selected. NAND gates 70-C and 70 in Figure 4C
-D is the code C ₀ and
Detect the presence of _C1 . The outputs of these NAND gates are then sent to NAND gates 87 and 88 in the circuit of FIG. Therefore, if any of these control characters are present in the input buffer, the outputs of NAND gates 87 and 88 will go high, which in turn forces the output of NAND gate 90 low. The low output of NAND gate 90 is latched by NAND gates 88 and 89. This low also forces a high from the output of NAND gate 91. This high from NAND gate 91 then forces the output from NAND gate 83 high. This high from the output of NAND gate 83 is then output from NAND gate 86.
Force SEND signal low. After the control character generated in the input buffer is transferred to the output buffer, signal A _K ' goes low. This clears the input buffer and all signals D _JK go low. The outputs of NAND gates 70-C and 70-D of FIG. 4C then go high. Also,
All outputs of NAND gates 71-1 through 71-N go high. The signals C ₀ ′ and C ₁ ′ are
It goes high at the input of NAND gate 87 in the circuit of FIG. This in turn forces the output of NAND gate 90 high. signal CLEAR
A high on D' causes NAND gate 72 to go low and input control signal _A0 to go low, thereby indicating that another character can now be received on the input data line. CLEAR
A high on D' causes NAND gate 91 to go low, thereby returning the circuit of FIG. 5 to its initial state. The control character _CEA is then finally received in the input queue. This control character is
Indicates that transmission from the selected input port is complete. Therefore, the control character C _EA
In addition to sending the arbiter to the output port, the arbiter must be deselected from the input port. This is done as follows. First, the control character _CEA is shown in Fig. 4C.
It is detected in the input queue by NAND gate 70-B, the output of which is sent to NAND gate 100 in the circuit of FIG. This overall circuit consists of 100 NAND gates
116, which are interconnected as shown. A low on the input of NAND gate 100 forces the output of this gate high, which in turn
Forces the output of NAND gate 102 low.
This row is latched by the feedback provided by gate 100. This low is also sent back to the NAND gate 72 of the circuit of Figure 4C, which in turn forces input control signal _A0 high. This allows the control character _CEA on the input data line to be removed. After the character _CEA has been transferred from the input buffer to the output buffer, the signal _AK ' goes low. This, combined with the removal of the character C _EA from the input data line, forces the signal D _JK from the queue's input buffer low.
Therefore, the fourth step to detect the control character C _EA is
The output of NAND gate 70-B in Figure C goes high. This high is received by NAND gate 104 of the circuit of FIG. 6, thereby causing its output to go low. Then by this row
The output of NAND gate 108 goes high and this high is latched by the feedback provided by NAND gates 105, 106, and 107. Due to the high output of NAND gate 108,
The output of NAND gate 109 is driven low.
This low is sent to the circuit of FIG. 3 as the signal CLEAR ₀ '. So the signal CLEAR ₀ ′ is
NAND gates 20-1 to 20-N and
Forces the output of NAND gate 21 to go high and thus signal R ₀ goes low.
This low then forces the output of NAND gate 26 high, and this high causes the other input ports to
It can be selected through the NAND gate 27. However, selection of this other input port is temporarily blocked by the low signal CLEAR ₀ ' on NAND gate 30. The signal CLEAR ₀ ' is also the NAND signal in the circuit of Figure 6.
sent to gate 116. This signal, which is low, then forces the output of NAND gate 116 high. This causes the output of NAND gate 101 to go low, which causes NAND gate 1
The output of 02 becomes high. NAND gate 102
causes NAND gate 103 to go low and sends signal EA _B ' to NAND gate 72 in FIG. 4C. NAND gate 72 therefore goes high, which in turn forces input control signal _A0 low and causes signal AQ low to be sent to the circuit of FIG. Therefore, the previously selected input port is returned to its initial state. Also, the NAND gate 2 in the circuit shown in Figure 3
In response to the high output of 6, transistor 32 turns on. Therefore, NAND gate 2
The output of 9 goes low. NAND gate 29
The output of is sent to NAND gates 104 and 105 in FIG. Therefore, these
The output of the NAND gate goes high, which in turn forces the CLEAR ₀ ' signal from NAND gate 109 high. NAND gate 116 goes low and NAND gate 101 goes high. This returns the circuit of FIG. 6 to its initial state, which also removes the blocking signal from NAND gate 30 of FIG. 3, allowing the corresponding input port to be selected. A preferred embodiment of this invention has been described in detail. However, many changes and modifications may be made without departing from the character and spirit of the invention. It is therefore to be understood that the invention is not limited to the embodiments described above, but is to be defined by the scope of the appended claims.