Triangular Matrix Device for the Assignment of Priorities

The invention relates to a device for assigning priorities having a plurality of request channels addressed by request signals.

In parallel operation of a plurality of processors or other dependently operating computer units, assurance must be provided that only one processor will always have control over common arrangements or devices, for example, over data buses, control lines, memories and the like and that all others are in a state of waiting. In this regard, a device for assigning priorities serves to seek out, from several simultaneous requests, the one request which has the highest priority at the time in question.

Two types of priorities are differentiated between in the allotment of priorities. In one scheme of priorities with fixed priorities, the order of priorities does not change. An example thereof is a priority chain built as series-connected flipflops. In a rotating priority, on the other hand, all requests are considered to be of like importance, the priorities being dynamically variable. Processors with frequent request demands, for example, can thereby be assigned lower priorities temporarily, so that processors with infrequent request demands receive the desired access through a high priority assignment and are not blocked.

It is accordingly an object of the invention to provide a device assigning priorities of the foregoing general type which ensures a setting of the priority of every request individually and an assignment of like or equal priorities by groups.

With the foregoing and other objects in view, there is provided, in accordance with the invention, a device for assigning priorities having a plurality of request channels addressed by request signals, including a plurality of output channels arranged with the request channels in matrix form, each of the request channels being directly connected to one of the output channels and being connected to the respective remainder of the plurality of output channels via a respective switching element controlled by a request signal blocking the appertaining output channels.

In accordance with another feature of the invention, the request channels, the output channels and the switching elements form a triangular matrix.

In accordance with a further feature of the invention, the switching element is formed of two cross-coupled FETs respectively addressed via a request and output channel, respectively.

In accordance with an additional feature of the invention, each of the switching elements has rotation control means for temporarily suppressing the switching function thereof.

In accordance with an added feature of the invention, each of the switching elements is formed of two cross-coupled FETs respectively addressed via a request and output channel, respectively, and the rotation control means have other FETs addressed in opposite phases and located at base points of the cross-coupled FETs forming the switching elements.

In accordance with yet a further feature of the invention, the other FETs of the rotation control means are addressed via a flipflop.

In accordance with a concomitant feature of the invention, there is provided, a control for holding the respective states, the control being preconnected to the rotation control means.

The invention offers the advantage that high flexibility of the priority assignment is achieved with a limited amount of circuitry. Fixed and rotating priorities can be realized as well as combinations of the two types of priorities which are adaptable in a relatively simple manner to the respective requirements. In this regard, the rotation method is fair with respect to infrequent requests. Due to the matrix structure according to the invention and to the use of identical cells, the arrangement or device of the invention is highly suited for integrated circuits, because the duplication of cells minimizes the technical expense for producing the layout.

A further embodiment of the invention, in which the desired scheme of priorities is adjustable via a data processing program, has the advantage that the priority of the individual request channels can be set independently of one another, and the modularity is thus increased.

Other features which are considered as characteristic for the invention are set forth in the appended claims.

Although the invention is illustrated and described herein as embodied in device for the assignment of priorities, it is nevertheless not intended to be limited to the details shown, since various modifications and structural changes may be made therein without departing from the spirit of the invention and within the scope and range of equivalents of the claims.

The construction and method of operation of the invention, however, together with additional objects and advantages thereof will be best understood from the following description of specific embodiments when read in connection with the accompanying drawing, in which:

FIG. 1 is a schematic block diagram of a first part of a priority network;

FIG. 2 is a schematic block diagram of a second part of the priority network;

FIG. 3 is a schematic diagram of the course of a priority rotation;

FIG. 4 is a schematic block diagram of a third part of the priority network;

FIG. 5 is a circuit diagram showing details of one of the matrix elements of the priority network; and

FIGS. 6 and 7 are each schematic block diagrams of different embodiments of the invention.

In accordance with the invention the arrangement for the priority assignment is shown wired as the network in the figures. In order to make the presentation clearer, the network is shown in three parts A, B and C wired together in themselves according to FIGS. 1, 2 and 4, respectively. The respective subsidiary circuits shown schematically in the nodes are correspondingly realized in a matrix element D.sub.ij as shown in FIG. 5. A complete presentation of a network can be found, for example, in FIGS. 6 and 7, respectively.

As FIG. 1 shows with respect to part A, the priority network has several request channels E.sub.i (i=1 to n ) and a like number of output channels A.sub.j (j=1 to n). Each request channel E.sub.i is permanently connected to an output channel A.sub.i (in the example embodiment of FIGS. 1 and 2, along a principal diagonal 2) and are connected at the remaining crossings to the remaining output channels A.sub.j via respective switching elements V.sub.ij. On the input side, the matrix is preceded by a decoupling device 1.

In this matrix arrangement, a priority which has the highest actual priority is picked out from among simultaneous priority requests on the request channels E.sub.i. Because each channel can occupy any position within the priority sequence, all channels are treated the same from the point of view of circuit construction.

Every request channel E.sub.i therefore must be checked for presence of a possible request signal on every other request channel. if a request is present on one of the channels E.sub.i, the switching element V.sub.ij suppresses a request on the other channels (j=i), if the channel E.sub.i has a higher actual priority than the channel E.sub.j. In this manner, only the request with the highest priority remains i.e. only one output channel A.sub.j is active.

FIG. 2 shows, with respect to the part B, a simplified circuit of the priority network in which a triangle matrix is formed by a fold along the main diagonal 2. To realize a rotating priority sequence, each switching element V.sub.ij is preceded by a control element, advantageously a flipflop F.sub.if, for storing the priority of a request channel E.sub.i with respect to a further request channel E.sub.j. The actual priority sequence is determined by preoccupation of the flipflops F.sub.ij. If the flipflops are held in a given state, a priority scheme with fixed priorities is produced. In dynamic switching, the priorities rotate.

A combination of held and dynamically switched flipflops F.sub.ij permits the production of flexible priority schemes with fixed priorities and the development of groups, within which the priorities rotate.

FIG. 3 shows schematically two examples of a rotating priority within groups of four request channels, respectively, E.sub.i (i=1 to 4), which are purported to be of equal importance mutually. To each group there is firmly assigned a common region in the otherwise variable priority sequence.

In the example at the top of FIG. 3, the request of channel E.sub.i is processed. During the processing, this channel E.sub.i is put in line in a priority sequence behind the other channels within the group region. It therefore receives the lowest priority, while the other channels E.sub.2, E.sub.3 and E.sub.4 are, respectively, advanced one place forward.

In the second example, the channel E.sub.3 which is in second place is being processed. It is therefore, likewise, placed in line farther to the rear within the priority sequence. In the advance, however, only the channels E.sub.1 and E.sub.4 are taken into account, which had been weighted or evaluated in the original sequence as being of lower value than the channel E.sub.3. The channel E.sub.2 which had been weighted or evaluated originally ahead of the channel E.sub.3 with the highest priority, retains the high priority thereof.

This kind of rotation rewards channels with infrequent requirements in that they travel or migrate forwardly in the priority sequence.

The dynamic switching of the flipflops F.sub.ij is accomplished according to FIG. 2 in such a manner that the setting and resetting inputs S, R are addressed via rotational channels T.sub.j. All of the setting inputs S of the flipflops F.sub.ij of a column are connected, in this regard, to a rotational input assigned to this column. Furthermore, all of the resetting inputs R of all of the flipflops F.sub.ij, if desirable or necessary, lie at a rotational channel characterized by the column numbering i.

The rotational channels T.sub.j are activated if the request from the output channel j is processed. If flipflops F.sub.ij are to be held in a given state, this must be accomplished in such a way that the setting and resetting inputs S and R do not become operative.

FIG. 4 shows, with respect to the part C, in which manner fixed priorities can be set within a priority scheme. For this purpose, the flipflops F.sub.ij are addressed by respective control signals FS, FR, via which they can be held either in the set or in the reset state. If neither of the control signals FS, FR is activated, the appertaining flipflop is switchable dynamically via its setting and resetting inputs S and R. The control signals FS, FR can be taken off at a memory device, such as a ROM, for example, a PLA (programmable logical array) or by any other combinatory logic. It is addressed via address lines PS.

FIG. 5 shows a realized embodiment of a matrix element D in MOS-technology, composed of the functional parts illustrated in FIGS. 1, 2 and 4. The switching elements V.sub.ij are formed of two cross-coupled FETs 50 which are addressed, respectively, by decoupled request signals X and by the signals Y present at the output channels A.sub.j. The rotational control is formed of further FETs 51 in the control paths of the FETs 50 and of an R-S flipflop 52, via the outputs Q, Q of which the FETs 51 are addressed. For realizing the function performed by the part C, FETs 53 are arranged at the bases of the flipflops 52 and are addressed via the signals FS and FR, respectively. A flipflop state is held by separating the base point.

The exemplary embodiment shown in FIG. 6 is a triangle matrix with four request channels E.sub.1 to E.sub.4 and four output channels A1 to A4. They are equipped with matrix elements D.sub.ij (i=2 to 4, j=1 to i-1). Each of the input channels E.sub.i are decoupled via an inverter and a source circuit connected thereto. The signals FS, FR for holding the flipflop states are stored in a ROM 3 addressed via lines PS.

A further advantageous exemplary embodiment of the invention is shown in FIG. 7. In this regard, each request channel E.sub.i is associated with a priority channel P.sub.i for transmitting a priority number PN.sub.i which is provided via a program of a computing system. This priority number PN.sub.i determines the weight or evaluation of the request of the appertaining channel E.sub.i. Like priority numbers of several channels E.sub.i lead to the aforedescribed group formation. The priority numbers PN.sub.i and PN.sub.j are mutually compared pairwise in comparators C.sub.ij, which precede the respective matrix elements D.sub.ij.

Each comparator C.sub.ij compares a priority word PN.sub.i present at the first input A thereof, with a priority word PN.sub.j present at the second input B thereof. In the given exemplary embodiment, the priority word PN.sub.i is fed to the second inputs B of those comparators C.sub.ji which are arranged in the matrix column i. The priority word PN.sub.i is further fed to those first inputs A of the comparators C.sub.ij.

A smaller priority number means a higher priority. Assuming that a request channel E.sub.i has a higher priority than a request channel E.sub.j a priority number PN.sub.i <PN.sub.j. In a comparator C.sub.ij, the priority number PN.sub.i is therefore fed to the input A, and the priority number PN.sub.j is fed to the input B. A logical zero can thereby be taken off at an output A<B of the comparator C.sub.ij and, as the control signal FS, hold the appertaining flipflop F.sub.ij in the set state. If the priority number PN.sub.i is larger than the priority number PN.sub.j, a logical zero is taken off at the second output A<B and, as a control signal FR, holds the flipflop in the reset condition. If the priority number PN.sub.i =PN.sub.j, the flipflop can be switched via its setting and resetting inputs S.sub.j and R. Both channels then belong to the same group.