JP3247998B2 - Ring arbiter and control method therefor - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a ring arbiter capable of shortening the control time and improving the overall processing throughput by performing competitive control independently and in parallel, and its control. About the method.

[0002]

2. Description of the Related Art In a digital system, it may be necessary to select one of a plurality of simultaneously input request signals. A circuit for arbitrating contention in this case is called an arbiter. In a bus sharing system such as a computer,
In order to avoid access conflicts when accessing a shared resource or connecting an input line to an output line in a switch at a junction, etc., control is performed by sequentially circulating a control signal transfer path. The arbiter to be executed is the ring arbiter. That is, the ring arbiter responds to an access request (request) from two or more child systems in a system in which a plurality of child systems are connected to a single shared resource via a shared bus line. It is a means to control. In this case, when the shared resource is used as the output line and the child system is used as the input line, the control is the same as the connection control in the crosspoint type exchange switch. Hereinafter, a ring arbiter will be described using a cross point type switch.

FIG. 5 is a diagram for explaining the operation of a conventional ring arbiter. In FIG. 5, 10 is the main system / output line,
11 is an output line, 12 is a forward control line connected between each fork,
xp (n) (n = 1,... N) is a cross point control circuit having an access right arbitration circuit. A plurality of input lines # 1 to #N are connected to one output line 11. A connection arbitration between the input lines is performed between the output line 11 and the input line in response to a connection request from the input line, and a cross point xp (n) at the highest priority position where the connection request is made is established. It is closed and connected to the output line 11 one-to-one. The control operation is as follows: (a) The presence or absence of a connection request is determined from the highest crossing point of the connection right, and if there is no request, the connection right is transferred to the next crossing point. The transfer direction is fixed to one direction selected at the system construction stage. Here, the transfer is performed in the direction indicated by the forward path control line 12. (B) In the connection right transfer stage, the crossing point for which connection has been requested for the first time acquires the connection right. (C) Transfer the connection right to the next crossing point of the connected crossing point.
In FIG. 5, the output line 11 and the input line # 2 are immediately connected in xp (2) because the current connection right is in xp (2) and there is a request from the input line # 2.

[0004]

In such a case, x
The connection right is transferred to p (3), and the control operation ends.
However, in such a conventional ring arbiter control method, in the state shown in FIG. 5, when a connection request is issued only to the input line # 1, the transfer control of the connection right is performed from xp (2) to xp (2).
(N), crossing points up to xp (1) must be transferred,
The control time for the transfer increases. That is, in the worst case, an arbitrary one input line is selected by making a full cycle of control through a whole system or a control line connecting the cross points. As shown in FIG.
(N), forward path control line 12 connected between (n = 1, N)
Let us consider a case in which control is performed sequentially from the starting point by using. In this case, the crossing points xp (N) and xp (1) are directly connected to the forward path control line 12 using a large driver, and the control information of the forward path control line 12 is propagated from otl (N) to otl (1). Because of the necessity, there is a problem that a large control time is lost. An object of the present invention is to solve such a conventional problem and to provide a ring arbiter capable of reducing the control time without using the cyclic control and a control method thereof.

[0005]

In order to achieve the above object, a method for controlling a ring arbiter according to the present invention uses one of a plurality of request sources for accessing a shared resource.
Select to grant access to selected request sources
N access right arbitration circuits CT (m) (m = 1... N) corresponding to N request sources and access right arbitration circuits CT (1 to N) are arranged in a tandem structure. , The access control lines D and U of the forward path and the return path connected in this arrangement order.
The method of controlling a ring arbiter provided with a request source number M (1 ≦ M <M
+ 1 ≦ N) of the access arbiter CT (M) to including grayed Le - flop (CT (1) ··· CT and (M)) first Group - the flop, the first Group - access during flop The right arbitration circuit is CT
(1)... CT (M) in the order of priority, and M + 1
Of access arbitration circuit including grayed Lumpur - flop (CT (M + 1)
··· CT (N)) the second Group - as a flop, the second Group - flop
Access right arbitration circuit is CT (M + 1)... CT
(N) in the order of priority, and the first group
Each group has its own priority so that two groups have priority.
The state value ST (m) is stored in the access arbitration circuit CT (m).
And the number M of the access right arbitration circuit that obtained the connection right last time
Is N, the all access right arbitration circuit is switched to the first group.
Only, and the access control line D in the outward path is CT (1)
... through each access right arbitration circuit in the order of CT (N)
The access control line U of the return route is CT (N) ...
..Connection via each access right arbitration circuit in the order of CT (1)
And the access control line D on the outward route is in the state ST (m).
Requested access right arbitration within the same group as indicated
One next candidate according to priority and request generation from circuit
The access control line U for the return route is selected according to the state ST (m).
Priority and request generation between the two groups
Therefore, one group is selected and the outgoing and returning trips are selected.
Access right arbitration based on control information by access control lines D and U
Circuit determines access permission / non-permission and generates only one request
Providing connection permission to the source .

[0006]

According to the present invention, (a) each access right arbitration circuit is tandem-connected by independent two-way control lines for transmitting control information for notifying the acquisition or transfer of the access right. And independently and in parallel using the connection control line of That is, the access right arbitration circuits are connected by two-stage access control lines of the forward path and the return path, and the control lines for the forward path and the return path are operated in parallel. As a result, unlike the conventional ring arbiter, the control signal transfer path does not circulate sequentially but is controlled independently and in parallel, so that the control time is greatly reduced.

[0007]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 is an operation principle diagram of a ring arbiter showing a first embodiment of the present invention. Here, for simplicity of description, a case where the present invention is applied to a cross point switch of an exchange having eight input lines and eight cross points is shown. Fork points xp (n), (n = 1 to N, where N =
8) is connected in tandem with upward control lines cu1 and cu2 and downward control lines cd1 and cd2 to cut off control circulation between xp (1) and xp (n). Here, n
= Truncated between 8 and 1. The priority is a direction order in which the connection right is transferred from the crossing point having the connection right before the start of the control to the crossing point where the request exists. In a conventional ring arbiter, as shown in FIG. 5, accommodation fork points are connected in a ring shape as priorities and ordered in one direction. On the other hand, in the present embodiment, the priority order is arbitrary in the initial setting, and thereafter, the priority order of the cross point permitted to be output is set to N (last), and reset in a uniquely ordered direction. The output similarity is given to the highest priority cross point among the cross points input by the output request REQ. In FIG. 1, xp
(3) is a cross point at which output permission was given in the previous control, at which point the priority is reset from the top to the bottom in the figure so as to lower the priority. That is, the cross point xp (4)
Priorities 1 to 8 are determined in the order of xp (8), xp (1) to xp (3). Here, the priority order is determined from the top to the bottom, but the invention is not limited to this. If the direction is always constant, the priority order is set to reverse, that is, set from the bottom to the bottom. No problem.
Here, as a method of displaying the priority, instead of setting 1 to 8, in the tandem connection of xp (1) to xp (8), the upper part from the boundary of the priority of the ring arbiter is grouped.
Group A (low priority group, xp (1) to xp
(3)), the area below the boundary is divided into groups B (groups with higher priority, xp (4) to xp (8)), and state constants st (n), (n = 1 to N ) To '0',
Shown as '1'.

Next, in FIG. 1, the order of connection control is represented by x
A case where a connection request is made to an input line connected to four intersections of p (2), xp (3), xp (6), and xp (7) will be described. In the figure, each control line cd1, cd2, cu1,
In the arrow 2, white ('0' or 'L') indicates non-transmission of any valid signal, and black ('1' or 'H') indicates transmission of any valid signal. [A] xp (2), xp (3), xp (6), xp
(7) There is a connection request. [B] After checking the presence or absence of a connection request and the type of group from xp (1) by cd1 and cd2, xp
The control value is transferred in the direction (8). On the other hand, cu1, c
The presence or absence of a connection request from xp (8) is determined by u2,
After checking the type of the control, the control value is transferred in the direction of xp (1). [C] In each of the groups A and B, cd1 is inverted at the junction having the connection request and the highest priority. To perform detection in the B group, a group boundary (xp
In (4)), cd1 is reset. As a result, one connection candidate is selected for each of the groups A and B. That is, the A group is inverted by xp (2), and the B group is inverted by xp (6). Note that cd2 is a group.
By reversing from white to black at the boundary between groups A and B, the classification of the group is transmitted to each other, resetting cd1 and setting the next rank. [D] Invert cu1 at a cross point belonging to the B group and having a connection request. As a result, the A group is notified that the B group having a higher priority has a connection request. Also, the A group is notified that there is a cross point having the next priority, which is not the highest priority. Also, cu2 is
By reversing from black to white at the boundary between groups A and B, the classification of the groups is transmitted to each other and the next rank is set. [E] The above controls [c] and [d] are performed simultaneously. Also,
Based on the results of [c] and [d], a connection right is given to only one crossing point (that is, xp (6) of B group). [F] Reset the next priority. The crossing point corresponding to the request source to which the access permission was previously given is xp
In the case of (8), there is no next grouping, and all the cross points xp (1) to xp (8) are assigned only to the A group.

FIG. 2 is a block diagram showing a control circuit at each crossing point in FIG. In FIG. 2, ST is a circuit that holds a state constant st (n) and outputs it to another block (stout). Comp1 is a comparison circuit for controlling the control lines cd1, cd2 from above in FIG. 1, and Comp2 is a control circuit for controlling lines cu1, c from below in FIG.
This is a comparison circuit that controls u2. Also, Comp3 is
The output enable ACK and the next st (n) value (stin) are output from the independent outputs Q1 and Q2 of Comp1 and Comp2. The input values to the junction xp (n) of each control line are cd1i (n), cd2i (n), cu1i (n),
cu2i (n), and output values are cd1o, respectively.
(N), cd2o (n), cu1o (n), cu2o
(N). That is, cd1i (n) = cd1o
(N-1), cd2i (n) = cd2o (n-1), c
u1i (n) = cu1o (n + 1), cu2i (n) =
cu2o (n + 1). The logic of each control line is as follows. [B] cd1 control (cd1i (0) = '0') cd1o (n) = REQ + cd1i (n), and cd1o (n) = '0' at the group boundary [b] cd2 control cd2o (n) = st (N) [c] cu1 control (cu1i (0) = '0') cu1o (n) = (stou * REQ) + cu1i
(N) [d] cu2 control cu2o (n) = st (n) The next access right is permitted (ack) and the next group is divided (stin value) based on the information of these control lines. .

FIG. 6 is a diagram showing the truth values of [1] and [2] of Comp1 in FIG. 2, and FIG. 7 is a diagram showing the truth values of [3] and [4] of Comp2. is there. FIG. 8 is a diagram showing the output permission ACK by Comp3 in FIG. 2 and the truth value of the next st (n) value stin. In FIG. 6, as is clear from the above equations [a] and [b], cd1o (n) indicates whether REQ is H,
It is H when cd1i (n) is H, and becomes 0 at the group boundary. Cd2o (n) transmits the state constant of st (n). Q1 is R if stout is L
It becomes H when EQ is H and cd1i (n) is L, and sto
If ut is H and REQ is H, cd1i (n) or cd2i
It becomes H when any of (n) is L. Note that the symbol "-" in FIGS. 6, 7 and 8 can be any of "L" and "H", and is an error value that cannot be output in the present invention. It is not considered in the calculation of each value such as Q2, ACK, and stin. FIG. 10 (a), (b)
FIGS. 11A and 11B are diagrams showing the logic of Comp1 and Q1 in FIG. 2, and FIGS.
FIG. 13 is a diagram showing the logic of p2 and Q2,
(B) shows ACK of Comp3 and stin in FIG.
It is a figure showing the logic of. In the present embodiment, the number of (child systems / input lines) is set to 8, but it can be realized even when the number of (child systems / input lines) is increased to 9 or more.
Further, although the cross point control is asynchronous, it is of course possible to use synchronous control.

FIG. 3 is an operation principle diagram of a ring arbiter showing a second embodiment of the present invention. Also in this case, a case is shown in which the present invention is applied to a junction switch of an exchange having eight input lines and eight junctions. The cross points forming the ring arbiter are xp (n),
(N = 1 to N, here N = 8) is connected to the upward control line cu.
And tandem connection with the downward control lines cd1 and cd2,
Cut off the control cycle between zp (1) and xp (n).
The priority is arbitrary in the initial setting, and the priority of the cross point permitted to be output thereafter is set to N (that is, the lowest).
Reset to a uniquely ordered direction. The output permission is given to the junction having the highest priority among the junctions input by the connection request REQ. In the example of FIG. 3, xp (3) is the crossing point at which the output permission was obtained in the previous control, so that the next time it becomes the lowest rank. In resetting the priority, the cross points xp (4) to x
p (8), priority 1 in the order of xp (1) to xp (3)
~ 8 is determined. Here, the priority order is determined from top to bottom, but if the direction is always fixed, the direction of the priority order may be reversed. Also, as in the case of FIG. 1, instead of the priorities 1 to 8, xp (1) to xp (8)
In the tandem connection of the above, from the boundary of the priority of the ring arbiter, a group A (that is, a group with a low priority) is placed above and a group B (that is, a group with a high priority) is placed below. By dividing, the state constants st (n), (n = 1 to
N) are represented as '0' and '1', respectively. As shown in FIG. 3, xp (2), xp (3), xp (6), xp (6)
The order of connection control when a connection request is made to the input line connected to the four-forked point in (7) will be described. In FIG. 3 as well, white ('0' or 'L') indicates the non-transmission of an arbitrary valid signal and black ('1' or 'H') indicates the transmission of an arbitrary valid signal. , Respectively. [A] xp (2), xp (3), xp (6), XP
(7) There is a connection request. [B] After checking the presence or absence of a connection request and the type of group from xp (1) by cd1 and cd2, xp
The control value is transferred in the direction (8). By cu, xp
After checking the presence or absence of a connection request and the group type from (8), the control value is transferred in the direction of xp (1). [C] Invert the cd1 at the junction having the highest priority and having a connection request in the A group. In addition, B glue
Cd2 is inverted at the junction where the connection request is present and the priority is the highest. As a result, one connection candidate is selected in each of the groups A and B. Here, xp (2) of the A group and xp (2) of the B group
(6) is selected. [D] Belonging to the B group, c
Invert u. As a result, the fact that there is a connection request to the B group having a higher priority is transmitted to the A group. [E] The above controls [c] and [d] are performed simultaneously.
From the results of [c] and [d], the only cross point (x of the B group)
p (6)) is given a connection right. [F] Reset the next priority.

FIG. 4 is a block diagram showing the structure of each fork in FIG. 3, and FIGS. 13 and 14 (a), (b)
Is a diagram showing the logic of Comp4 in FIG. 4, and s
It is a figure which shows the logic of tin and ACK. In FIG.
ST2 is a circuit that holds a state constant st (n) and outputs it to another block (stout). Also, Com
p4 is a circuit for controlling the control lines cd1 and cd2 from above and the control line cu from below in FIG. Comp4
Is the output permission ACK and the value of the next st (n) (sti
n) is output. The input values to the junction xp (n) of each control line are cd1i (n), cd2i (n), cui, respectively.
(N), and output values are cd1o (n) and cd2, respectively.
o (n) and cuo (n). In this case, cd1i
(N) = cd1o (n-1), cd2i (n) = cd2
o (n-1) and cui (n) = cuo (n + 1). The logic of each control line is as follows. [A] cd1 control (cd1i (0) = '0') cd1o (n) = REQ + cd1i (n) [b] cd2 control (cd2i (0) = '0') cd2o (n) = (REQ · st (n) )) + Cd2i
(N) [c] cu control (cui (N) = '0') cuo (n) = REQ + cui (n + 1) Based on the information of these control lines, the permission (ack) of the next access right and the next group Perform a split (stin).
FIG. 9 shows an output permission ACK by Comp4 in FIG.
FIG. 7 is a diagram illustrating a truth value of a value stin of the next st (n). In FIG. 9, cd1o (n) indicates whether REQ is H or cd1i (n) is H, as is clear from the above equation [a].
Is H if both are L and L if both are L. Also, cd
2o (n) is REQ, as is apparent from the above equation [b].
If the AND of st and (n) is H or cd2i (n) is H, it becomes H, and if both are L, it becomes L. Also, cuo
(N) indicates that REQ is H, as is apparent from the above equation [c].
Or, if cui (n + 1) is H, it becomes H, and if both are L, it becomes L. In the present embodiment, the number of (child systems / input lines) is set to 8, but it can be realized even when the number of (child systems / input lines) is increased. Further, the cross point control is asynchronous, but synchronous control is also possible.

[0013]

As described above, according to the present invention,
Each access right arbitration circuit is connected by a two-step access control line of the outward return path, and the control line of the outward return path is operated in parallel, so that the control time can be reduced as compared with the conventional cyclic control. It is.

[0014]

[Brief description of the drawings]

FIG. 1 is an operation principle diagram of a ring arbiter showing a first embodiment of the present invention.

FIG. 2 is a block diagram showing a configuration of each fork point in FIG.

FIG. 3 is an operation principle diagram of a ring arbiter showing a second embodiment of the present invention.

FIG. 4 is a block diagram showing a configuration of each fork point in FIG. 3;

FIG. 5 is a diagram illustrating the operation principle of a conventional ring arbiter.

FIG. 6 is a diagram illustrating truth values of a comparison circuit Comp1 in FIG. 2;

FIG. 7 is a diagram showing a truth value of the comparison circuit Comp2 in FIG. 2;

FIG. 8 is a diagram illustrating truth values of a comparison circuit Comp3 in FIG. 2;

FIG. 9 is a diagram showing truth values of a comparison circuit Comp4 in FIG. 4;

FIG. 10 shows comparison circuits Comp1 and Q1 in FIG.
It is a figure showing the logic of.

FIG. 11 is a diagram showing comparison circuits Comp2 and Q2 in FIG.
It is a figure showing the logic of.

FIG. 12 is a diagram illustrating logics of ACK and stin of a comparison circuit Comp3 in FIG. 2;

FIG. 13 is a diagram illustrating the logic of a comparison circuit Comp4 in FIG. 4;

FIG. 14 is a diagram showing logic of stin and ACK in FIG. 4;

[Explanation of symbols]

 cd1, cd2 Downward control line cu1, cu2, cu Upward control line xp (n) Crossing point REQ Connection request ST State constant holding circuit Comp1, 2, 3, 4 Comparison circuit stin Next value (high or low priority) ACK output permission ST2 State constant holding circuit

──────────────────────────────────────────────────続 き Continuation of front page (72) Inventor Yukihiro Doi 1-6, Uchisaiwaicho, Chiyoda-ku, Tokyo Nippon Telegraph and Telephone Corporation (56) References JP-A-56-72752 (JP, A) JP-A Sho 62-251952 (JP, A) 1992 IEICE Spring Conference B-451 IEICE Technical Report SS E91-157 (58) Fields studied (Int. Cl. ⁷ , DB name) H04L 12/56 H04L 12/28 G06F 13/37

Claims (2)

(57) [Claims] Claims: 1. A plurality of elements for accessing a shared resource.
Select one of the request sources and select the request source
, N access right arbitration circuits CT (m) corresponding to N request sources (m = 1...)
N) and the access right arbitration circuits CT (1 to N) are arranged in a tandem structure and provided with access control lines D and U for outbound and inbound routes connected in the order of arrangement. The number M of the request source that previously obtained the connection right in the array
(1 ≦ M <M + 1 ≦ N) access right arbitration circuit CT
(M) and including grayed Lumpur - flop (CT (1) ··· CT ( M))
Is a first group, and access rights in the first group are
The arbitration circuit sets the priority in the order of CT (1)... CT (M).
A, (M + 1) th access arbitration circuit including grayed Le - flop (CT (M + 1) ··· CT (N)) the second Group - the flop, the second Group - access arbiter in flops Is CT (M +
1)... Priority is given in the order of CT (N),
So that the second group has priority over the group
Each group is placed in each access arbitration circuit CT (m).
The status ST (m) is stored, and the access
If the number M of the arbitration circuit is N,
The stop circuit is only the first group, and the access
The line D is connected to each of the accessors in the order of CT (1) ... CT (N).
Access via the arbitration circuit for access control
The line U represents each actuating line in the order of CT (N)... CT (1).
Access via the access right arbitration circuit
Line D is the same group indicated by state ST (m).
Priority and request from the requested access right arbitration circuit
The next candidate is selected according to the occurrence, and
Access control line U is a two-glue signal indicated by the state ST (m).
-One group according to priority and request generation between groups
-Select the access control line for the forward and return trips
In the access right arbitration circuit based on the control information by D and U,
A ring arbiter control method characterized in that access permission / non-permission is determined and connection permission is given to only one request source . 2. A shared resource - Select one from among a plurality of request sources accessing the scan, lingua give permission to the request source selected - in Vita, into N request sources of Corresponding N access right arbitration circuits
CT (m) (m = 1... N) and the access right arbitration
Roads CT (1-N) are arranged in a tandem structure,
Access control lines D and U for outbound and return
Only the number of the request source to obtain a previous connection right in sequence M
(1 ≦ M <M + 1 ≦ N) access right arbitration circuit CT
(M) and including grayed Lumpur - flop (CT (1) ··· CT ( M))
The first Group - the flop, the first Group - permission in flops
The arbitration circuit sets the priority in the order of CT (1)... CT (M).
A, (M + 1) th access arbitration circuit including grayed Le - and up - the flop (CT (M + 1) ··· CT (N)) the second Group
And, second Group - have access arbitration circuit in-flops CT (M +
1)... Priority is given in the order of CT (N),
So that the second group has priority over the group
Each group is placed in each access arbitration circuit CT (m).
The status ST (m) is stored, and the access
If the number M of the arbitration circuit is N,
The stop circuit is only the first group, and the access
The line D is connected to each of the accessors in the order of CT (1) ... CT (N).
Access via the arbitration circuit for access control
The line U represents each actuating line in the order of CT (N)... CT (1).
Access via the access right arbitration circuit
The control line D is the same group indicated by the state ST (m).
Priority and request from the requested access right arbitration circuit in the
The next candidate is selected according to the request, and the
Access control line U is connected to the 2 st point indicated by the state ST (m).
One group according to priority and request generation between groups
Select the loop and access control lines for the forward and return routes
In the access right arbitration circuit based on the control information by D and U,
Access permission / non-permission, and means for giving connection permission to only one request source.
Vita.