JPH0690232A - Access arbitration system - Google Patents

Abstract

(57) [Abstract] [Purpose] In the access arbitration method between the access request source and the shared resource, the control line and the signal line are omitted as hardware. [Structure] The combinations to be accessed are divided into small groups, and the contention arbitration calculation is performed in parallel in each group. [Effect] The competition arbitration time does not increase even if the access request generation source and the scale of the shared resource increase.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention is used in an information processing apparatus, a communication exchange, particularly an ATM exchange, and other systems having a plurality of resources commonly connected by a bus.
Here, the resource means a memory device, an output device, a display device, an input device, a printing device, a functional unit, and other equipment accompanied by hardware for operating the system.

The present invention relates to arbitration of a plurality of access requests generated from within a system with respect to a plurality of shared resources arranged in one system.

[0003]

2. Description of the Related Art Arbitration of access requests according to the prior art will be described with reference to a model shown in FIG. 4, which is based on a ring arbiter control method. In this model, there are eight access request sources R (1) to R (8) and eight resources S (1) to S (8) that accept the access requests.
These are respectively connected to the input terminal group and the output terminal group of the matrix switch means. The matrix switch means may be provided with hardware of a matrix structure as shown in the drawing, or may be virtual one composed of a logic circuit having the illustrated matrix function capable of transmitting an access request. The number of access request sources and the number of resources are not necessarily equal.

The access request sources R (1) to R (8) generate access requests one after another. Since access requests are generated according to the circumstances of the source, a plurality of access requests may compete for one resource at the same time. The contention is arbitrated by the control circuit which controls the matrix switch means, and the access request is transmitted from one access request generation source to one resource of the request destination. At this time, the ring arbiters RA (1) to RA (8) sweep the access requests as shown by the arrows in FIG. 6, respectively, and when they reach the corresponding access request, they pass through the intersection C (n, m). Only one access request is transmitted to the resource side, and the resource accepts the access request.

When one access request is accepted,
Information indicating that the request has been accepted is transmitted to the request source that has transmitted the access request. By accepting one access request, another access request sent to the ring arbiter is made to wait, and the other access request is detected at the next timing or at the next timing. After the access request is accepted, processing such as transfer of necessary data via this matrix switch means or via another bus signal line is executed.

[0006]

In such contention arbitration of access requests, it is preferable when the number of access request sources and the number of resources are small, but the number of contention arbitration increases as the number increases. N is N + ΔN, M is M +
By increasing to ΔM, the scale of the matrix switch is N × M, but becomes (N + ΔN) × (M + ΔM) = NM + ΔNM + NΔM + ΔNΔM. The increase in the scale of the matrix switch directly increases the competition arbitration calculation by the ring arbiter. That is, in FIG. 4, the request generation source R (1) and the resource S (8)
In order to establish a connection with, the ring arbiter must go through eight intersections and conduct competitive arbitration. Furthermore, as the size of the matrix switch increases, the number of intersections that the ring arbiter must go through also increases. Moreover, it is necessary to send and receive the connection availability information for the access request each time. In other words, the calculation time becomes long and it becomes necessary to use an expensive element capable of executing high-speed calculation.

An object of the present invention is to improve the above and to reduce the number of contention arbitrations to be executed by apparently reducing the number of access request sources or the number of resources by changing the logic of contention arbitration. And An object of the present invention is to provide a method capable of shortening the contention arbitration time for access request arbitration and executing contention arbitration with a low-speed element.

[0008]

According to the present invention, N request generation sources (N is an integer of 2 or more) for generating access requests,
M resources (M is an integer of 2 or more) shared by the access request generation sources, the N request generation sources are connected to input terminals, and the M resources are connected to output terminals. Matrix switch means having a capacitance of × M,
The present invention is implemented in an apparatus including a control circuit for controlling connection / disconnection of the matrix switch means.

The access request sources are resources in a broad sense, and may be one of the M resources depending on the device configuration. The matrix switch means may be a matrix switch in which switches made up of hardware are arranged at intersections of a matrix, and a virtual circuit for substantially realizing a circuit for connecting or disconnecting an access request at the intersections by a program control circuit. Matrix switch may be used.

The features of the present invention are as follows. A control circuit for controlling connection / disconnection of the intersections of the matrix switch means, an arbitration means for performing arbitration when an access request is generated from a plurality of the access request generation sources for one of the resources, and the arbitration means. And a disconnection means for controlling disconnection of the intersection points of the matrix switch means, the arbitration means of the control circuit being a plurality of intersection points of the matrix switch means smaller than the number (N × M), A means for dividing at least a part of the output terminals into a group including a plurality of intersections, a means for performing one of the divided groups and performing the arbitration in the focused group, and a group for the attention. And means for circulating all of the divided groups over time.

In the means for dividing into the groups, the logic of the division can be changed according to the occurrence frequency of the access request, and the logic of the division can be changed according to the priority level of the access request. You can also

[0012]

In the system of the present invention, the range in which the contention arbitration is performed is divided into small groups, and the contention arbitration is executed by parallel processing for each group. The number of transfers for contention arbitration is reduced.

Therefore, when the scale of the matrix switch is increased, the control time required for contention arbitration is the same as that of the conventional example at worst, and the control time is improved.

Further, it is possible to set priorities in accordance with the access frequency, change the grouping, and give priority to each group by a priority control signal from the outside.

[0015]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The configuration of the first embodiment of the present invention will be described with reference to FIG. FIG. 1 is a block diagram of a first embodiment device of the present invention.

According to the present invention, eight request generation sources R (1) to R (8) that generate access requests and eight request generation sources R (1) to R (8) shared by the access requests are generated. Resource S (1) ~
S (8) and eight request generation sources R (1) to R (8) are connected to the input terminals ₁₁ to ₁₈ to provide eight resources S (1) to S (8).
Are connected to the output terminals 2 _{1 to} 2 ₈ and have a capacity of 8 × 8, and request sources R (1) to R (8) for access to one of the resources S (1) to S (8). ), An arbitration unit 5 that is an arbitration unit that executes arbitration when access requests are generated, and a matrix switch that is a connection / disconnection unit that controls connection / disconnection of the matrix switch 3 according to the result of the arbitration. This is an access arbitration system including a control circuit 4 including a disconnecting unit 6.

Here, a feature of the present invention is that the arbitration means of the control circuit 4 has a plurality of intersections of the matrix switch 3 smaller than the number (8 × 8), and at least a part of the output terminals 2 _{1 to} 2 ₈ is divided into groups G (1,1) to G (4,4) including a plurality of intersections, and one of the divided groups G (1,1) to G (4,4). And a means for executing the arbitration in the focused groups G (1,1) to G (4,4) and the focused groups G (1,1) to G (4,4).
4) is included in all the divided groups G (1,1) to G (4,4). In the first embodiment of the present invention, it is configured to circulate in synchronization with the transmission timing of the time slot.

Next, the operation of the first embodiment of the present invention will be described with reference to FIG. FIG. 2 is a flow chart showing the operation of the first embodiment of the present invention. The intersections of the matrix switch 3 are divided into groups G (1,1) to G (4,4), and the group G
When (1,1) to G (4,4) are represented by a set of intersections C (1,1) to C (8,1), C (1,1), C (1,2), and C (2 , 1), C (2,2) ⇔ G (1,1) C (1,3), C (1,4), C (2,3), C (2,4) ⇔ G (1,2 ) C (1,5), C (1,6), C (2,5), C (2,6) ⇔ G (1,3) C (1,7), C (1,8), C (2,7), C (2,8) ⇔ G (1,4) C (3,1), C (3,2), C (4,1), C (4,2) ⇔ G (2 , 1) C (3,3), C (3,4), C (4,3), C (4,4) ⇔ G (2,2) C (3,5), C (3,6) , C (4,5), C (4,6) ⇔ G (2,3) C (3,7), C (3,8), C (4,7), C (4,8) ⇔ G (2,4) C (5,1), C (5,2), C (6,1), C (6,2) ⇔ G (3,1) C (5,3), C (5, 4), C (6,3), C (6,4) ⇔ G (3,2) C (5,5), C (5,6), C (6,5), C (6,6) ⇔ G (3,3) C (5,7), C (5,8), C (6,7), C (6,8) ⇔ G (3,4) C (7,1), C ( 7,2), C (8,1), C (8,2) ⇔ G (4,1) C (7,3), C (7,4), C (8,3), C (8, 4) ⇔ G (4,2) C (7,5), C (7,6), C (8,5), C (8,6) ⇔ G (4,3) C (7,7), C (7,8), C (8,7), C (8,8) ⇔ G (4,4) (S 1). Of these, groups G (1,1) to G (4,4) that can arbitrate for one access opportunity are G (i1, j1).
, G (i2, j2), G (i3, j3), G (i4, j4) [i1 ≠ i2
≠ i3 ≠ i4 and j1 ≠ j2 ≠ j3 ≠ j4] are satisfied. Four groups G (1,1) to G (4,4). These are called arbitration right groups G (i1, j1) to G (i4, j4) in order to distinguish them from the other groups G (1,1) to G (4,4). The arbitration right groups G (i1, j1) to G (i4, j4) in FIG. 1 are groups G (1,1) to G (4,4) surrounded by solid lines, and R (1) and R (2 ), ⇔ S (3), S (4) [Mediation right group G
(1,2)] R (3), R (4), ⇔ S (5), S (6) [Mediation right group G
(2,3)] R (5), R (6), ⇔ S (7), S (8) [Mediation right group G
(3,4)] R (7), R (8), ⇔ S (1), S (2) [Mediation right group G
(4,1)] (S2). This shows the scope of competing mediation on one occasion. For example, in the one arbitration right group G (3,4), the resources S (1) to S (8) that may be accessed by the request sources R (5) and R (6) are the resources S (1) to S (8). 7) or S (8). Mediation right group G (i1, j1) within one combined group ~
Each group G (1,1) to G constituting G (i4, j4)
Mixing mediation is performed in parallel for (4, 4) (S3).
Here, as compared with the conventional example, the contention arbitration for the resource S (8) needs to be performed among all the request generation sources R (1) to R (8), and therefore, due to the large-scale control data transfer. Although it was necessary to select access candidates, in the case of the first embodiment of the present invention, only contention arbitration between the request generation sources R (5) and R (6) is required. That is, the arbitration range is 4 as compared with the conventional example.
The mediation right groups G (i1, j1) to G (i4, j
Since (4) processes the contention arbitration in parallel, the contention arbitration can be speeded up.

By fixing the groups G (1,1) to G (4,4) and circulating the combination of the arbitration right groups G (i1, j1) to G (i4, j4), any request source is generated. R (1) ~ R (8)
Can access any resource S (1) to S (8).

The arbitration right groups G (i1, j1) to G (i4,
When the competitive arbitration in j4) ends (S4), R (1), R (2), ⇔ S (1), as the next arbitration right groups G (i1, j1) to G (i4, j4), S (2) [Mediation Group G
(1,1)] R (3), R (4), ⇔ S (3), S (4) [Mediation right group G
(2,2)] R (5), R (6), ⇔ S (5), S (6) [Mediation right group G
(3,3)] R (7), R (8), ⇔ S (7), S (8) [Mediation right group G
(4,4)], the arbitration right groups G (i1, j1) to G (i4, j4) are arbitrated by competition (S5), and the next arbitration right group G (i1, j1) ~ Go to G (i4, j4). All the combinations are visited (S6), and the competitive arbitration ends.

Next, a second embodiment of the present invention will be described with reference to FIG. FIG. 3 is a block diagram of the second embodiment of the present invention. The feature of the second embodiment of the present invention is that the group G (i, j) [however,
i = 1,2,3,4, j = 1,2,3,4] is provided, and the monitoring data CT (i) of CT (i) or the external control signal is provided. An arbitration right group selection unit GCT for changing the group G (1,1) to G (4,4) division and controlling the priority by PR is provided.
Upon receiving the monitoring data CL (i), the arbitration right group selection unit GCT determines the groups G (1,1) to G from the occurrence frequency.
Prioritize (4,4). Alternatively, change the grouping. For example, when the arbitration right group selection unit GCT detects that the requests sources R (1) to R (4) and the resources S (1) to S (4) are frequently accessed, the group G ( 1,1), G (1,2), G (2,1), G (2,2) are prioritized, and the group G (1,1) shown by the dashed line in FIG.
, G (1,2), G (2,1), and G (2,2) are formed into a group LG, and request sources R (1) to R (4) and resources S are formed.
It corresponds to frequent access between (1) to S (4). If a large grouping such as the group LG is used, contention arbitration can be performed frequently in the grouping, and the number of data transfers for contention control is reduced, so that the group G (1,1) ...
The round trip time of G (4,4) can be shortened. In addition, the arbitration right group selection unit G determines the priority from the outside by the external control signal PR.
Can be entered in CT.

Now, a procedure for setting the priority order to the groups G (1,1) to G (4,4) will be described. The arbitration right groups G (i1, j1) to G (i4, j4) in FIG. 3 are portions surrounded by solid lines, and are R (1), R (2), ⇔ S (3), S (4). [Mediation Group G
(1,2)] R (3), R (4), ⇔ S (5), S (6) [Mediation right group G
(2,3)] R (5), R (6), ⇔ S (7), S (8) [Mediation right group G
(3,4)] R (7), R (8), ⇔ S (1), S (2) [Mediation right group G
(4,1)]. This shows the scope of performing competitive arbitration on one occasion. For example, one arbitration group G (3,4)
Are resources S (1) to S (8) that may be accessed by the request sources R (5) and R (6) are resources S (7).
Alternatively, it indicates S (8). The arbitration right groups G (i1, j1) to G (i4, j4) sequentially circulate as described in the first embodiment of the present invention to perform competitive arbitration.

In the second embodiment of the present invention, the monitoring unit CT (i) receives the monitoring data CL (i) from the request generation sources R (1) to R (8) and transfers it to the arbitration right group selection unit GCT. . In the arbitration right group selection unit GCT, these monitoring data CL
(i) is deciphered, and the arbitration right groups G (i1, j1) to G (i4, j4), which have the highest priority, are set based on the access frequency. In addition, the arbitration right group G (i1, j1) is generated by the external control signal PR.
~ G (i4, j4) can be arbitrarily prioritized.

Here, if the priority of the access request to the resources S (3) and S (4) of the request generation sources R (1) and R (2) is higher than the others, the arbitration right group Selector GC
T is R (1), R (2), ⇔ S (3), S (4) [Mediation right group G
(1,2)] ... (priority) is suspended. As a result, the next mediation right group G (i1,
The combination of j1) to G (i4, j4) is originally R (1), R (2), ⇔ S (1), S (2) [arbitration right group G
(1,1)] R (3), R (4), ⇔ S (3), S (4) [Mediation right group G
(2,2)] R (5), R (6), ⇔ S (5), S (6) [Mediation right group G
(3,3)] R (7), R (8), ⇔ S (7), S (8) [Mediation right group G
(4,4)] becomes R (1), R (2), ⇔ S (3), S (4) [arbitration right group G (1,2)] ... (priority) R (3), R (4), ⇔ S (1), S (2) [Mediation right group G (2,1)] R (5), R (6), ⇔ S (5), S (6) [Mediation right group G (3,3)] R (7), R (8), ⇔ S (7), S (8) [arbitration right group G (4,4)]. This is the first priority arbitration group G (1,2)
This is an example in which the arbitration right group G (2,3), which should originally be transferred to the group G (2,2), is caused to jump to the group G (2,1) due to the suspension of the. In this way, the positions of the highest priority arbitration right groups G (i1, j1) to G (i4, j4) are determined first, and other arbitration right groups G ( i1, j1) to G (i4, j4) are determined.

As a further example, the demand source R (3),
When the priority of the access request to the resources S (1) and S (2) of R (4) is higher than the other priorities, the arbitration right group selection unit GCT determines R (3) and R (4). , ⇔ S (1), S (2) [Mediation right group G
(2,1)] ... (priority) is secured, originally, R (1), R (2), ⇔ S (1), S (2) [arbitration right group G
(1,1)] R (3), R (4), ⇔ S (3), S (4) [Mediation right group G
(2,2)] R (5), R (6), ⇔ S (5), S (6) [Mediation right group G
(3,3)] R (7), R (8), ⇔ S (7), S (8) [Mediation right group G
(4,4)] where R (1), R (2), ⇔ S (7), S (8) [Mediation right group G (1,4)] R (3), R (4) , ⇔ S (1), S (2) [Mediation right group G (2,1)]… (Priority) R (5), R (6), ⇔ S (5), S (6) [Mediation right group G (3,3)] R (7), R (8), ⇔ S (3), S (4) [Mediation right group G (4,2)] From group G (2,3) Arbitration rights groups G (i1, j1) to G (i4, j4) are jumped to group G (2,1). Other mediation groups G (1,4), G (3,3), G (4,2)
Are determined sequentially after the arbitration group G (2,1) is determined.

If the highest priority of access to the resources S (7) and S (8) of the request generation sources R (5) and R (6) is input by the external control signal PR, the arbitration right group selection Part G
CT is R (5), R (6), ⇔ S (7), S (8) [Mediation right group G
(3,4)] ... (priority) is suspended. As a result, the next mediation right group G (i1,
j1) to G (i4, j4) are originally R (1), R (2), ⇔ S (1), S (2) [arbitration right group G
(1,1)] R (3), R (4), ⇔ S (3), S (4) [Mediation right group G
(2,2)] R (5), R (6), ⇔ S (5), S (6) [Mediation right group G
(3,3)] R (7), R (8), ⇔ S (7), S (8) [Mediation right group G
(4,4)] becomes R (1), R (2), ⇔ S (1), S (2) [Mediation right group G
(1,1)] R (3), R (4), ⇔ S (3), S (4) [Mediation right group G
(2,2)] R (5), R (6), ⇔ S (7), S (8) [Mediation right group G
(3,4)] R (7), R (8), ⇔ S (5), S (6) [Mediation right group G
(4,3)].

In the first and second embodiments of the present invention, eight request generation sources R (1) to R (8), eight resource S (1) to S (8), and request generation source R (1 ) -R (8) is divided into 4, the number of request generation sources R (1) to R (8) is 2, and the number of resources S (1) is 2.
~ S (8) is divided into 4 resources S (1) to S (8)
Although the number is set to 2, the number is not limited, and the number can be set to any number and group scale.

The priority can also be set between a plurality of request generation sources R (1) to R (8) and a plurality of resources S (1) to S (8).

[0029]

As described above, according to the present invention, it is possible to change the logic of contention arbitration and apparently reduce the number of access request generation sources or the number of resources to reduce the number of contention arbitrations to be executed. According to the present invention, the contention arbitration time for access request arbitration can be shortened, and contention arbitration can be executed by a low-speed element.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a first embodiment of the present invention.

FIG. 2 is a flowchart showing the operation of the first embodiment of the present invention.

FIG. 3 is a configuration diagram of a second embodiment of the present invention.

FIG. 4 is a configuration diagram of a conventional example.

[Explanation of symbols]

1 ₁ to ₁₈ input terminal 2 ₁ to 2 ₈ output terminal 3 matrix switch 4 control circuit 5 arbitration unit 6 matrix switch disconnection unit LG group R (1) to R (8) request source S (1) to S ( 8) Resource Xp intersection

─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. ⁵ Identification code Internal reference number FI Technical display location H04L 12/44 12/48 H04Q 3/52 A 9076-5K 8732-5K H04L 11/20 Z

Claims (3)

[Claims] 1. N request generating sources (N is an integer of 2 or more) for generating access requests, M resources (M is an integer of 2 or more) shared by the access request generating sources, and Matrix switch means having a capacity of N × M in which N request sources are connected to input terminals and the M resources are connected to output terminals; and a plurality of the access request sources for one of the resources. Access arbitration method including arbitration means for performing arbitration when an access request is issued from the device, and a control circuit including a connection / disconnection means for controlling connection / disconnection of the matrix switch means according to the result of the arbitration. In the arbitration means of the control circuit, the number of intersections of the matrix switch means (N × M)
A means for dividing the output terminal into a group including a plurality of intersections at least in part, and a means for focusing on one of the divided groups and executing the arbitration in the focused group. And a means for circulating the group of interest for all of the divided groups over time, the access arbitration method. 2. The access arbitration method according to claim 1, wherein the means for dividing into groups includes means for changing the logic of the division according to the frequency of occurrence of access requests. 3. The access arbitration system according to claim 1, wherein the means for dividing into groups includes means for changing the logic of the division according to the priority level of the access request.