Nothing Special   »   [go: up one dir, main page]

EP0331701A1 - Procede et dispositif de commandes de commutations dans un ensemble d'interconnexions - Google Patents

Procede et dispositif de commandes de commutations dans un ensemble d'interconnexions

Info

Publication number
EP0331701A1
EP0331701A1 EP19880907706 EP88907706A EP0331701A1 EP 0331701 A1 EP0331701 A1 EP 0331701A1 EP 19880907706 EP19880907706 EP 19880907706 EP 88907706 A EP88907706 A EP 88907706A EP 0331701 A1 EP0331701 A1 EP 0331701A1
Authority
EP
European Patent Office
Prior art keywords
arbitration
state
requesting
units
elements
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP19880907706
Other languages
German (de)
English (en)
Inventor
Cyrille Velikanov
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Individual
Original Assignee
Individual
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Individual filed Critical Individual
Publication of EP0331701A1 publication Critical patent/EP0331701A1/fr
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • G06F15/17356—Indirect interconnection networks
    • G06F15/17368—Indirect interconnection networks non hierarchical topologies
    • G06F15/17393—Indirect interconnection networks non hierarchical topologies having multistage networks, e.g. broadcasting scattering, gathering, hot spot contention, combining/decombining
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
    • G06F13/14—Handling requests for interconnection or transfer

Definitions

  • the invention relates to electronic switching control techniques which make it possible to connect different units which are interconnectable in a set of interconnections. It involves the intervention of an arbitration law to decide which connections to establish based on demand and availability.
  • the requests are expressed by sending elements when they are in a requesting state and that the availabilities are those of receiving elements, depending on whether they are free or already occupied in a connection, and that each of the units of the interconnection unit may present one or more requests and, simultaneously or not, one or more availabilities.
  • the units considered are from electronic processors which constitute computer data processing units, whether these processors are used in particular to perform calculations by programs, to ensure access to a memory module, to define data inputs or outputs, to access an external network, or in any other way.
  • the units are electronic processors
  • the physical phenomenon exploited in the transfer of information and in the constitution of the signals used for the implementation of the arbitration law is of an electrical or electromagnetic nature
  • the invention applies equally well to interconnection assemblies exploiting magnetic, or optical, or fluidic, or any other phenomena.
  • the invention is not limited as regards the field of application, for example multiprocessor computers or telephone exchanges, nor as regards the nature of the interconnectable units, the above processors being able to be replaced by channels transmission or even software units (programs, tasks, etc.), or with regard to the nature of the connections to be established, which can be in particular uni- or bi-directional, single-line or multi-line.
  • software units programs, tasks, etc.
  • connections to be established which can be in particular uni- or bi-directional, single-line or multi-line.
  • current electronic techniques offer several architectures for connecting between . them processing units or memory units.
  • Another solution consists in organizing all of the processors 5 into a matrix of nodes, in which each processor can communicate with its direct neighbors.
  • each processor is connected to four processors which are adjacent to it.
  • This method is satisfactory in particular 0 applications, such as that of graphics processors, where the operations to be performed and the data to be processed are in accordance with the topology of such a matrix.
  • the establishment of a connection between two non-adjacent processors is done by passing through intermediate nodes, each with a downtime, the progression in the network being controlled at each node by a routing decision. It is therefore understood that the communication paths can include a large number of intermediate nodes and that for a large number of units or processors, the time taken to route messages often becomes prohibitive.
  • the present invention therefore aims to achieve an interconnection system in which each processor, and more generally each unit of a set, can be connected to any other directly, by making the junction * between transmitter and receiver element without go through intermediate nodes, performing all the junctions simultaneously, avoiding the drawbacks of network interconnection assemblies of previous designs as well as the recourse to a management of assignments by computer program.
  • the invention proposes to assign to any requesting transmitting element any free receiving element from among those capable of fulfilling the requested role, by selecting it by an arbitration sequence which can be implemented in circuits separate from those which make the connections in the set of interconnectable units, which makes it possible to simultaneously establish all the connections thus decided by the arbitration sequence between the requesting elements and the respective free receiving elements affected, and which is developed without interference with the links established between the units and the operations they carry out.
  • the subject of the invention is a method for controlling switching in a set of interconnections between a plurality of units each having at least one function among those of the transmitting element and of the receiving element, characterized in that the '' we order at least some of said elements into a series of successive elements where all the receiving elements are interchangeable in a role to be completed with respect to each emitting element, we explore said series of said elements, determining for each emitting element s '' it is in a requesting state or in a non-requesting state and for each receiving element if it is in a free state or in an occupied state, and a free receiving element is assigned a requesting transmitting element which is selected according to a law of predetermined arbitration as a function of the respective states of the intermediate elements between them in said series, and in that the co nnexion between the corresponding unit elements in said set as well as their change from requesting state to non-requesting state and free state to occupied state.
  • an arbitration sequence therefore essentially comprises an exploration step and a selection step, on the series previously constituted. It will be observed, however, that the different operations that these stages imply can be carried out both simultaneously and sequentially, depending on which of the available technologies appears preferable in each particular practical realization.
  • the proposed technique can be applied to all or part of a complex set of interconnections, comprising many units.
  • similar subgroups can each include a receiver for several transmitters.
  • the arbitration law selects, to assign it to a free receiving element, that of the requesting transmitters which is the first in said series such that, in the successive elements which l 'separate, the number of free receivers is equal to the number of requesting transmitters.
  • this number can be zero, which can mean, in particular, that for a unit having both functions simultaneously, if its emitting element is in the requesting state and if its receiving element is in the free state, we connect them directly. This can also mean that when a free receiving element is immediately followed by a requesting transmitter, the latter is then assigned to it.
  • units capable of playing either the role of receiving element and the role of transmitting element and possibly both roles simultaneously may be advantageous to use units capable of playing either the role of receiving element and the role of transmitting element and possibly both roles simultaneously to give them alternately the capacity or not to play one or the other roles at the choice of a stage of the process prior to the implementation of the arbitration law.
  • the invention also relates to a switching control device comprising means specific to the implementation of the above method.
  • an interconnection system comprising a set of units each having at least one function among those of receiving element and emitting element, in which said units are organized in a matrix comprising in each node a relay of control of a connection between a transmitting element and a receiving element and in which said units are also organized into an arbitration matrix where each of said elements is associated with a plurality of switching nodes allowing the transfer of 'an arbitration signal to a neighboring node.
  • the arbitration matrix comprises a first line of referral control nodes allowing the sampling of an arbitrage signal from a receiving element if it is in the free state or its transfer to a transmitting element if it is in the requesting state and the control of routing nodes associated with said receiving or transmitting element to selectively determine in each the formation of a section of arbitration path allowing the transfer of such an arbitration signal to a neighboring node selected according to the state of said element.
  • FIG. 1 shows a set of microprocessor units comprising N transmitters E and M receivers R, interconnected through an N x M matrix;
  • FIG. 2 is a diagram illustrating, on an example, the method of arbitration of the connections to be made in this system;
  • FIG. 6 schematically illustrates the constitution of a referral control node in a particular embodiment of the arbitration matrix
  • FIG. 8 shows schematically the control means of the switching of the connection matrix from the arbitration matrix.
  • microprocessors constitute the units of the set of interconnections. They are organized according to a matrix of interconnections between transmitter channels and receiver channels which physically represent the functions of transmitter element and of receiver element respectively.
  • Each of the microprocessors considered is assumed to include either a transmitter channel, a receiver channel, or both a transmitter channel and a receiver channel.
  • the receiver elements selected in a series suitable for implementing the arbitration law are trivialized, that is to say t5 that they are each individually capable of handling the signals of each of the transmitting elements, the latter being, on the other hand, specific in their functions and the roles which they assign to the elements to which they are connected.
  • Figure 1 shows an orthogonal matrix of interconnections between N emitters Eo- " ⁇ En-1 and
  • the connection between Ei and Rj is made by establishing a physical link between the channel leaving the Ei (transmitter channel) and the channel entering Ri (receiver channel), at a single point which is their point of intersection. In each of these points, which
  • the sending channels are represented by vertical lines and the receiving channels by horizontal lines. Upward direction for horizontal lines 35 and right-to-left direction for horizontal lines are related to the direction of transmission of the signals conveyed during the connections.
  • a set of n transmitters are requesting (D 0 to Dn-1), while a set of m receivers are free at the time considered (L 0 to Lm- 1).
  • the transmitters which are not requesting, can also be in communication already established with certain receivers, or else they can be (momentarily) "passive" vis-à-vis the inter ⁇ communications system.
  • FIG. 2 The arbitration process applied according to the invention is illustrated geometrically in FIG. 2.
  • the different units are explored in series periodically. For this, their order in the series being arbitrary, they are shown distributed on a closed line, more precisely at points represented on a circle, each point carrying a transmitter, or a receiver, or a transmitter and a receiver.
  • each transmitter is designated by a tile, which is ticked if it is requestor, and each receiver by a circle, which is checked if it is free.
  • the order of the transmitters on the circle, as well as the order of the receivers, corresponds to their order in FIG. 1.
  • the distribution of the receivers among the transmitters is completely arbitrary. This distribution makes some of the transmitters more priority (that is to say more frequently served), than the others.
  • each free receiver Li is assigned a closest requesting transmitter Dj (in the direction of travel of the circle) such as the number L (i, j) of points S (Ljç) representing free receivers which are crossed by the arc drawn between S (L j .) and S (Dj) in the chosen direction of travel, is equal to the number D (i, j) of points S (Dfc) representing requesting issuers.
  • Dj the closest requesting transmitter
  • Dj the number of points S (Ljç) representing free receivers which are crossed by the arc drawn between S (L j .) and S (Dj) in the chosen direction of travel
  • arbitration operations are not necessarily defined as a series of elementary actions taking place successively in a pre-established order over time. Although we often have to represent or perform them in this way, we can also obtain a similar result (the associations D - L established) whatever the order of execution of these elementary actions.
  • the connections decided by arbitration can be different (not the number of associations D - L, my their constitution). In fact, the result remains within the scope of the invention, but in one. arrangement which is completely symmetrical to the previous one.
  • FIG. 3 results from a development in plan of the circular arrangement of FIG. 2, considered during a determined arbitration sequence.
  • the circle of Figure 2 here becomes a straight line which constitutes the baseline, the arcs of the circle become segments of this straight line, and the strings become broken lines which represent paths of arbitration over the baseline.
  • the different elements are numbered on the baseline, in the order they have in the defined range for the application of the arbitration law, and here regardless of whether they are transmitters or receivers, except that a single number is assigned to the sending and requesting elements belonging to the same unit which fulfills the two functions.
  • the lines loop back and forth between two ends of the table.
  • the baseline after the point S- ⁇ g f continues towards So.
  • This “dynamic” classification characterizes the points Sk according to the current state of the transmitting and receiving channels which they represent.
  • the “static” classification will show the following types:
  • FIG. 4 makes it better to see that the switching nodes of the different lines (or rows) are also grouped in columns, each column comprising a series of nodes which are all associated with the same element.
  • This command has the effect of determining in each node, the formation of a section of path in the orientation thus selected, section which will be alone accessible to any arbitration signal circulating in an arbitration path passing through this node, which , path consists of one node to another following individual successive sections.
  • Examples include:
  • the unit comprises both a transmitter channel and a receiver channel, the switching nodes being of type XRE ... XRE '.
  • an emitter type point (-, E) taking into account the requesting state or not by the first node S and, in all the nodes of the column, selection of a horizontal path section if the emitter n is not a requester, of a descending section if it is a requester.
  • the state of the receiver is expressed by a signal "1" that takes the value 1 for free, or the value 0 for non-free (do occupied), and that of the transmitter by signal "d" qu takes the value 1, if it is requesting, the value 0 if it is not requesting.
  • Two bistable circuits 61 and 62 of type D respectively receive these status signals as well as a synchronization signal jh. In combination with two ET 63 and 64 doors, they control:
  • FIG. 7 illustrates only the making of a node associated with a unit having the double function of transmitting element and receiving element.
  • a node does not have the mission of creating the control signals e_ and - but only that of using them to select or block an ascending or descending path section, which neither does it have the mission of allowing binary signal transfers with an "in” input or an “out” output and that instead of connecting input and output, it must make operational or block a section of path horizontal.
  • the three possible sections i are each represented at 74 for the descending section, 76 for the ascending section, and 78 for the horizontal section, with at the heart of the node a group of four gates controlled by the signals e_ and r, among which:
  • an AND gate 71 blocks the descending section when the signal e does not have the value 1,
  • an AND gate 73 blocks the ascending section if the control signal r does not have the value 1,
  • each logical gate of the nodes of the arbitration matrix is replaced by a set of gates which are controlled by the same signals e and r of the command lines. referral.
  • the arbitration paths thus formed allow the circulation of information contained in an arbitration signal between the "in” input from a receiving element and the "out” output reaching a transmitting element.
  • This signal makes it possible to transmit a specific address to the corresponding free receiver by the arbitration path which transmits it to the transmitting element which has been assigned to it by the application of the arbitration law.
  • the same signal is also used to control the change of state of elements since the transmitting element becomes "served” and the receiving element becomes "occupied” during all the time that the transfer of information between the two will last. units assigned to each other.
  • this arbitration signal also controls the establishment of a functional link between these two elements by controlling the corresponding switching relay of the switching matrix of FIG. 1.
  • FIG. 8 illustrates the functional links between receiving elements and requesting elements by the corresponding four switching relays.
  • a register 3 ⁇ which contains the specific address of the element in binary form and which delivers it as an arbitration signal to the entry in the arbitration matrix.
  • the function of the register is governed by a synchronization signal s_.
  • the address contains in a first bit validation information for the allocation of the two elements.
  • the state signal IL of this reception element is transmitted through the interconnection matrix on line 35, along the corresponding row of nodes (relays). In this same row, the information to be transmitted from the transmitting element to the receiving element once the connection has been established between them, passes over a line 37.
  • this same information is admitted along the column of nodes or relays, by a line 36.
  • the status signal d_ of this element is produced, at the output of a bistable 81 of RS type.
  • a bistable 81 of RS type By the time the law of arbitration decided on the allocation, it is in state 1 characteristic of a requesting element as soon as the associated source makes a request for emission and is maintained in this state until the element is served .
  • bistables 81 operate asynchronously independently of the operation of the arbitration matrix.
  • the arbitration signal received at the "out" output of the arbitration path reaching element 33 transmits 0 - the address of the receiving element to a shift register 82.
  • the arrival of the validation bit causes , at the level of the bistable 81, the passage of the signal d to the value 0, translating the change of state from "requesting" to "served,” therefore not requesting. It is also transmitted by a lig 5 38 which controls the start of the transmission of information by line 36.
  • the information source transmits a signal which is received by 39 in the shift register 82 , to cancel the effect of the validation bit and again command 0 to set the requesting state in the signal d ⁇ .
  • the element 33 is also provided with an address decoder 84 which has as many outputs as there are relays at the nodes of the column in the arbitration matrix. Each output being connected to one of the relays 5 This decoder 84 processes the address information of the register
  • the relay illustrated by a tri-state buffer 85, thus links lines 36 and 37 for the transmission of information.
  • the same output of the address decoder 84 controls a NOR gate 86 which has as many inputs as there are transmitting elements 5 in the row of the relay 31.
  • the output of the gate is the line 35 on which consequently the operation of the address sign at the entrance of the door, passes the signal to the non-free state as long as the receiver 32 is occupied with a link with a transmitter by a relay from his row.
  • a step in the process prior to the exploration and selection steps determines which of the group units can fulfill this function of receiving element, and each time this unit has been used in an assignment and a connection to a transmitting element, it is ordered the passage of this function of receiving element from the corresponding unit to the following. Any other permutation algorithm is equal possible.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Computer Hardware Design (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Multimedia (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Small-Scale Networks (AREA)
  • Multi Processors (AREA)

Abstract

L'invention concerne un système d'intercon­ nexion comportant un ensemble d'unités Eo, ... EN-1, Ro, ... RM-1 présentant chacune au moins une fonction parmi celles d'élément récepteur Ro, ... RM-1 et élément émetteur Eo, ... EN-1, dans lequel lesdites unités sont organisées en une matrice d'interconnexion comportant en chaque noeud un relais de commande d'une connexion entre un élément émetteur et un élément récepteur, et dans lequel lesdites unités sont organisées par ailleurs en une matrice d'arbitrage où chacun desdits éléments est associé à une pluralité de noeuds d'aiguillage permettant le transfert d'un signal d'arbitrage à un noeud voisin.
Abstract
The invention relates to an interconnection system comprising an assembly of units Eo, ... EN-­ 1, Ro, ... RM-1 presenting each at least one function amongst those of receiver element Ro, ... RM-1 and emitter element Eo, ... EM-1 wherein said units are organized in an interconnection matrix comprising at each node a relay for the control of a connec­ tion between an emitter element and a receiver ele­ ment, and wherein said units are further organized in an arbitration matrix where each of said ele­ ments is associated with a plurality of switching nodes making possible the transfer of an arbitra­ tion signal to a neighbouring node.

Description

PROCEDE ET DISPOSITIF DE COMMANDES DE COMMUTATIONS DANS UN ENSEMBLE D'INTERCONNEXIONS
L'invention concerne les techniques électroniques de commande des commutations qui permettent de connecter entre elles différentes unités qui sont interconnectables dans un ensemble d'interconnexions. Elle implique l'intervention d'une loi d'arbitrage pour décider des connexions à établir en fonction des demandes et des disponibilités.
On considérera dans ce qui suit que les demandes sont exprimées par des éléments émetteurs quand ils sont dans un état demandeur et que les disponibilités sont celles d'éléments récepteurs, suivant qu'ils sont libres ou déjà occupés dans une connexion, et que chacune des unités de l'ensemble d'interconnexion peut présenter une ou plusieurs demandes et, simultanément ou non, une ou plusieurs disponibilités.
Par ailleurs, on s'intéressera plus particu¬ lièrement au cas où les unités considérées sont dès processeurs électroniques qui constituent des unités de traitement de données informatiques, que ces processeurs soient utilisés notamment pour effectuer des calculs par programmes, pour assurer l'accès à un module mémoire, pour définir des entrées ou sorties de données, pour accéder à un réseau extérieur, ou de toute autre manière. Mais il s'agit là seulement d'un exemple parmi les multiples applications que peut recevoir l'invention. Ainsi notamment, alors que si les unités sont des processeurs électroniques, le phénomène physique exploité dans le transfert des informations et dans la constitution des signaux utilisés pour la mise en oeuvre de la loi d'arbi¬ trage est de nature électrique ou électromagnétique, l'invention s'applique tout aussi bien à des ensembles d'interconnexion exploitant des phénomènes magnétiques, ou optiques, ou fluidiques, ou de tout autre ordre. De même, l'invention n'est pas limitée en ce qui concerne le domaine d'application, par exemple les ordinateurs multiprocesseurs ou les centraux téléphoniques, ni en ce qui concerne la nature des unités interconnectables, les processeurs ci- dessus pouvant être remplacés par des canaux de transmission ou même des unités logicielles (programmes, tâches, etc.), ni en ce qui concerne la nature des connexions à établir, qui peuvent être notamment uni- ou bi-directionnelles, monolignes ou multilignes. σ Si l'on se réfère spécialement aux systèmes multi¬ processeurs, les techniques électroniques actuelles proposent plusieurs architectures pour connecter entre .elles des unités de traitement ou unités de mémoire.
Une première solution consiste à connecter toutes 5 les unités à un seul et unique chemin de données : le bus. Si dans un tel système plusieurs unités ont chacune droit à demander d'accéder au bus, ceci crée des conflits d'accès au- bus. Il faut organiser pour elles un ordre de priorité. Et cependant, le problème majeur reste toujours présent : 0 il faut qu'à chaque instant, un seul élément émetteur puisse avoir accès au bus. De ce fait, cette solution n'est envisageable que dans le cas où le nombre de processeurs n'est pas très élevé, généralement autour de 8.
Une autre solution consiste à organiser l'ensemble 5 des processeurs en une matrice de noeuds, en lesquels chaque processeur peut communiquer avec ses voisins directs. Dans une matrice carrée par exemple, chaque processeur est connecté à quatre processeurs qui lui sont adjacents. Cette méthode est satisfaisante dans des 0 applications particulières, comme celle des processeurs graphiques, où les opérations à effectuer et les données à traiter sont en accord avec la topologie d'une telle matrice. Mais dans le cas général, l'établissement d'une connexion entre deux processeurs non adjacents se fait en 5 passant par des noeuds intermédiaires, avec en chacun un temps d'arrêt, la progression dans le réseau étant commandée à chaque noeud par une décision de routage. On comprend dès lors que les chemins de communication peuvent comporter un nombre important de noeuds intermédiaires et que pour un grand nombre d'unités ou processeurs, le temps d'acheminement des messages devient souvent prohibitif.
On connaît aussi des systèmes où ce sont les interconnexions qui sont organisées en matrice, avec en chaque noeud du réseau un relais de commutation qui permet de.relier ou non, sans intermédiaire, un élément émetteur déterminé avec un élément récepteur déterminé. Dans tous les systèmes de ce type proposés à ce jour, qui concernent surtout la téléphonie, les différents émetteurs et les différents récepteurs remplissent des rôles respectifs déterminés, et périodiquement ils sont d'abord soumis en série à une exploration par un programme qui décide de leurs affectations chacun à chacun, puis dans une autre étape les commutations de relais ainsi décidées sont commandées en série. Non seulement ces systèmes sont particulièrement longs dans leur fonctionnement séquentiel, qui doit être répété à chaque série de commutations, aussi bien pour décider des connexions à établir que pour commander les commutations de relais correspondants. De plus ils ne donnent pas toute satisfaction si l'on a besoin d'une grande sécurité dans l'acheminement des informations, évitant tout blocage au cas où le récepteur appelé ne serait pas libre.
La présente invention vise donc à réaliser un système d'interconnexion dans lequel chaque processeur, et plus généralement chaque unité .d'un ensemble, peut être connecté à tout autre de manière directe, en réalisant la jonction*entre élément émetteur et élément récepteur sans passer par des noeuds intermédiaires, en réalisant toutes les jonctions simultanément, en évitant les inconvénients des ensembles à réseau d'interconnexions des conceptions antérieures ainsi que le recours à une gestion des affectations par programme d'ordinateur. Pour ce faire, l'invention propose d'affecter à tout élément émetteur demandeur un élément récepteur libre quelconque parmi ceux qui sont aptes à remplir le rôle demandé, en le sélectionnant par une séquence d'arbitrage qui peut être mise en oeuvre dans des circuits-distincts de ceux qui réalisent les connexions dans l'ensemble d'unités interconnectables, qui permet d'établir simultanément toutes les connexions ainsi décidées par la séquence d'arbitrage entre les éléments demandeurs et les éléments récepteurs libres respectifs affectés, et qui s'élabore sans interférence avec les liaisons établies entre les unités et les opérations qu'elles réalisent.
Ainsi l'invention a pour objet un procédé de commande de commutations dans un ensemble d'interconnexions entre une pluralité d'unités chacune à au moins une fonc¬ tion parmi celles d'élément émetteur et d'élément récepteur, caractérisé en ce que l'on ordonne au moins certains desdits éléments en une série d'éléments successifs où tous les éléments récepteurs sont interchangeables dans un rδle à remplir à l'égard de chaque élément émetteur, on explore ladite série desdits éléments, en déterminant pour chaque élément émetteur s'il est dans un état demandeur ou dans un état non demandeur et pour chaque élément récepteur s'il est dans un état libre ou dans un état occupé, et à un élément récepteur libre on affecte un élément émetteur demandeur qui est sélectionné selon une loi d'arbitrage prédéterminée en fonction des états respectifs des éléments intermédiaires entre eux dans ladite série, et en ce que l'on commande alors la connexion entre les éléments d'unités correspondants dans ledit ensemble ainsi que leur changement d'état demandeur à état non demandeur et d'état libre à état occupé.
Ce que l'on a appelé ci-avant une séquence d'arbi¬ trage comprend donc essentiellement une étape d'exploration et une étape de sélection, sur la série préalablement cons¬ tituée. On observera cependant que les différentes opérations que ces étapes impliquent peuvent être réalisées aussi bien de manière simultanée que de manière séquentielle, suivant celle des technologies disponibles qui apparaît préférable dans chaque réalisation pratique particulière.
Par ailleurs, la technique proposée peut être appliquée à tout ou partie d'un ensemble d'interconnexions complexe, comprenant de nombreuses unités. Dans certains cas, il peut être utile d'appliquer simultanément la séquence d'arbitrage à différentes séries d'éléments dans lesquels chaque série est constituée en regroupant, avec au moins un élément émetteur, une pluralité d'éléments récepteurs équivalents entre eux dans leur rôle récepteur, par le fait, par exemple, que chacun d'eux est en mesure d'accomplir une même tâche demandée, qu'ils ont les mêmes fonctionnalités et qu'ils accèdent à un même ensemble de données. A l'inverse, des sous-groupes analogues peuvent comporter chacun un récepteur pour plusieurs émetteurs.
Dans un mode de mise en oeuvre préféré de l'invention, la loi d'arbitrage sélectionne, pour l'affecter à un élément récepteur libre, celui des émetteurs demandeurs qui est le premier dans ladite série tel que, dans les éléments successifs qui l'en séparent, le nombre de récepteurs libres soit égal au nombre d'émetteurs demandeurs. On peut admettre que ce nombre puisse être nul, ce qui peut signifier, en particulier, que pour une unité présentant simultanément les deux fonctions, si son élément émetteur est à l'état demandeur et si son élément récepteur est à l'état libre, on les connecte entre eux directement. Ce qui peut signifier aussi que quand un élément récepteur libre est immédiatement suivi d'un émetteur demandeur, celui-ci lui est alors affecté.
Dans d'autres formes de mise en oeuvre du procédé, on peut aussi, de manière symétrique à ce qui précède, s'intéresser d'abord à un élément émetteur demandeur et lui affecter celui des éléments récepteurs libres qui est le premier dans la série à respecter la même condition de la loi d'arbitrage.
Par ailleurs, on peut avoir avantage à utiliser des unités capables de jouer indifféremment le rôle d'élément récepteur et le rôle d'élément émetteur et éventuellement les deux rôles simultanément pour leur conférer alternativement la capacité ou non de jouer l'un ou l'autre des rôles au choix d'une étape du procédé préalable à la mise en oeuvre de la loi d'arbitrage.
L'invention a également pour objet un dispositif de commande de commutations comportant des moyens propres la mise en oeuvre du procédé ci-dessus.
Elle a encore pour objet un système d'intercon¬ nexion comportant un ensemble d'unités présentant chacune au moins une fonction parmi celles d'élément récepteur et élément émetteur, dans lequel lesdites unités sont organisées en une matrice comportant en chaque noeud un relais de commande d'une connexion entre un élément émetteur et un élément récepteur et dans lequel lesdites unités sont organisées par ailleurs en une matrice d'arbi¬ trage où chacun desdits éléments est associé à une plura¬ lité de noeuds d'aiguillage permettant le transfert d'un signal d'arbitrage à un noeud voisin.
Selon des caractéristiques secondaires de l'inven tion, la matrice d'arbitrage comporte une première ligne d noeuds de commande d'aiguillage permettant le prélèvement d'un signal d'arbritrage depuis un élément récepteur s'il est à l'état libre ou son transfert à un élément émetteur s'il est à l'état demandeur et la commande de noeuds d'ai- guillage associés audit élément récepteur ou émetteur pour déterminer sélectivement dans chacun la formation d'un tronçon de chemin d'arbitrage permettant le transfert d'un tel signal d'arbitrage vers un noeud voisin sélectionné d'après l'état dudit élément.
On décrira maintenant plus en détails une forme d réalisation particulière de l'invention qui fera mieux comprendre les caractéristiques essentielles et les avantages, étant entendu toutefois que cette forme de réalisation est choisie à titre d'exemple et qu'elle n'est nullement limitative. Sa description est illustrée par les dessins annexés, dans lesquels :
- la figure 1 représente un ensemble d'unités à microprocesseurs comprenant N émetteurs E et M récepteurs R, interconnectés à travers une matrice N x M ; - la figure 2 est un schéma illustrant, sur un exemple, le procédé d'arbitrage des connexions à réaliser dans ce système ;
- la figure 3 donne une autre représentation de c schéma, légèrement modifiée, où le schéma circulaire de la figure 2 est ouvert en plan ;
- la figure représente schématiquement un dispositif d'arbitrage selon la présente invention ;
- la figure 5 fait apparaître l'ensemble des chemins d'arbitrage établis dans la matrice d'arbitrage de la figure 4 ;
- la figure 6 illustre schématiquement la constitution d'un noeud de commande d'aiguillage dans une forme particulière de réalisation de la matrice d'arbitrage ;
- la figure 7 montre de même la constitution de l'un des noeuds d'aiguillage associé au noeud de la figure 6 î
- la figure 8 représente schématiquement les moyens de commande des commutations de la matrice de connexions à partir de la matrice d'arbitrage.
Dans l'exemple de réalisation décrit, on se réfèr à une application de l'invention à la commande des commutations permettant de relier entre eux des micro¬ processeurs pour permettre le transfert de données de l'un à l'autre et le déroulement de programmes ou logiciels de traitement de telles données ou la commande de l'accomplis¬ sement de tâches extérieures. Ces microprocesseurs constituent les unités de l'ensemble d'interconnexions. Ils 5 sont organisés selon une matrice d'interconnexions entre des canaux émetteurs et des canaux récepteurs qui représentent matériellement les fonctions d'élément émetteur et d'élément récepteur respectivement. Chacun des microprocesseurs considérés est supposé comporter, soit un 10 canal émetteur, soit un canal récepteur, soit à la fois un canal émetteur et un canal récepteur.
Conformément à l'invention, les éléments récepteurs retenus dans une série convenant à la mise en oeuvre de la loi d'arbitrage sont banalisés, c'est-à-dire t5 qu'ils sont aptes chacun individuellement à gérer les signaux de chacun des éléments émetteurs, ces derniers étant, par contre, spécifiques dans leurs fonctions et les rôles qu'ils assignent aux éléments auxquels ils sont connectés. A chacun des éléments émetteurs demandeurs, on
2Q peut donc affecter l'un quelconque des éléments récepteurs libres, et c'est là qu'intervient la loi d'arbitrage appliquée selon l'invention.
Ainsi, la figure 1 montre une matrice orthogonale d'interconnexions entre N émetteurs Eo-«^En-1 et
25 M récepteurs, Ro..»Rm-1. La connexion entre Ei et Rj se fait par l'établissement d'une liaison physique entre le canal sortant du Ei (canal émetteur) et le canal rentrant dans Ri (canal récepteur), dans un seul point qui est leur point d'intersection. En chacun de ces points, qui
30 constituent les noeuds de la matrice, se trouve un relais de commutation tel que 21.
Les canaux émetteurs sont représentés par des lignes verticales et les canaux récepteurs par des lignes horizontales. Le sens montant pour les lignes horizontales 35 et le sens de droite à gauche pour les lignes horizontales sont liés au sens de transmission des signaux véhiculés lors des connexions. On a représenté aussi symboliquement qu'à un instant considéré, un ensemble de n émetteurs se portent demandeurs (D0 à Dn-1), alors qu'un ensemble de m récepteurs sont libres à l'instant considéré (L0 à Lm-1).
Dans l'ensemble de la figure 1, N = 16, M = 11, = 7 et m r 6. Tous les récepteurs qui ne sont pas libres, sont occupés. Ceci peut signifier qu'ils sont connectés à certains émetteurs, ou bien qu'ils ne sont pas disponible pour toute autre raison. Les émetteurs qui ne sont pas demandeurs, peuvent être, eux-aussi, en communication déj établie avec certains récepteurs, ou bien ils peuvent êtr (momentanément) "passifs" vis-à-vis du système d'inter¬ communications.
Dans l'exemple de la figure 1, on a fait apparaître une configuration instantanée qui implique, po les émetteurs demandeurs : D0 = Eo, D1 = E2, D2=E5, D3= E
D4 = E8, D5 = E10, D6= E13 et pour les récepteurs libres
Lo = R2, L1 = R3, L2 = R , 3 = Rγ, L4 = R8, L5 = R9.
Le procédé d'arbitrage appliqué selon l'inventio est illustré de façon géométrique, sur la figure 2. Dans procédé, les différentes unités sont explorées en série périodiquement. Pour cela, leur ordre dans la série étant quelconque, elles sont figurées réparties sur une ligne fermée, plus précisément en des points représentés sur u cercle, chaque point portant un émetteur, ou un récepteur, ou un émetteur et un récepteur. On choisit aussi une direction de parcours de ce cercle, illustrée ici par une flèche dans le sens inverse des aiguilles d'une montre. Dans l'exemple de la figure 2, on voit 20 points distincts sur le cercle, avec parmi eux : 7 points comportant un émetteur et en même temps un' récepteur, 9 points comportant un émetteur, et enfin, 4 points comportant un récepteur. Symboliquement, chaque émetteur est désigné par un carreau, qui est coché s'il est demandeur, et chaque récepteur par un cercle, qui est coch s'il est libre. L'ordre des émetteurs sur le cercle, aussi bien que l'ordre des récepteurs, correspond à leur ordre sur la figure 1. Par contre, la distribution des récepteur parmi les émetteurs est tout à fait arbitraire. Cette distribution rend certains des émetteurs plus prioritaires (c'est-à-dire plus fréquemment servis), que les autres.
Dans le cas représenté par les figures 1 et 2, le nombre maximal des associations "émetteur demandeur - récepteur libre" possibles (associations D-L) est égal à 6 (car m < n et m = 6). Ces associations peuvent être établies de plusieurs façons différentes ; et, parmi ces façons différentes, le procédé de l'invention, dans le mod de mise en oeuvre particulier considéré, se prête particulièrement bien à une réalisation par un dispositif électronique "décentralisé", c'est-à-dire tel que la décision globale d'arbitrage résulte immédiatement d'une multitude de décisions locales, prises individuellement en chaque point. Conformément à la loi d'arbitrage appliquée dans la mise en oeuvre du procédé, on attribue à chaque récepteur libre Li un émetteur demandeur Dj le plus proche (dans le sens de parcours du cercle) tel que le nombre L (i,j) de points S (Ljç) représentant des récepteurs libre qui sont traversés par l'arc de cercle tracé entre S (Lj.) et S (Dj) dans le sens choisi de parcours, est égal au nombre D (i,j) de points S(Dfc) représentant des émetteurs demandeurs. Géométriquement t cela signifie que les cordes de tous ces arcs ne s'intercroisent nulle part (voir figur 2). Deux cas à remarquer dans l'exemple : l'arc entre S(L2 et S(D2) dégénère en un seul point, car ce point est en même temps émetteur demandeur et récepteur libre. D'autre part, on voit en D+ un point S(D5 Qui reste isolé, car le nombre d'émetteurs demandeurs est égal à 7 et le nombre de récepteurs libres est égal à 6 seulement. Dans le cas général, il restera n-m émetteurs demandeurs "non-servis" si n > m, et m - n récepteurs libres "non-affectés" si m > n.
On remarquera, par ailleurs, que les opérations d'arbitrage ne sont nécessairement définies comme une sui d'actions élémentaires se déroulant successivement dans u ordre préétabli dans le temps. Bien que l'on soit amené à les représenter ou réaliser souvent de cette manière, on peut aussi obtenir un résultat similaire (les association D - L établies) quel que soit l'ordre d'exécution de ces actions élémentaires. Par contre, si on change le sens de parcours du cercle (ou si on trace des arcs commençant au S (Di) et aboutissant aux S (Lj), ce qui revient au même) les connexions décidées par l'arbitrage peuvent être différentes (non pas le nombre des associations D - L, ma leur constitution). De fait, le résultat reste dans le cadre de l'invention, mais dans une. disposition qui est complètement symétrique de la précédente.
En se référant maintenant aux figures 3 et 4, on décrira comment la mise en oeuvre de la loi d'arbitrage peut être concrétisée dans un dispositif d'arbitrage constitué sous forme d'une matrice de noeuds d'aiguillage comportant une première ligne, où se définit la commande chacune des séries de noeuds d'aiguillage associées chacu à chacun des différents éléments émetteurs ou récepteurs la série d'éléments explorée dans une séquence d'arbitrage
La figure 3 résulte d'un développement en plan d la disposition circulaire de la figure 2, considérée lors d'une séquence d'arbitrage déterminée. Le cercle de la figure 2 devient ici une ligne droite qui constitue la ligne de base , les arcs du cercle deviennent des segments de cette ligne droite, et les cordes deviennent des lignes brisées qui représentent des chemins d'arbitrage surmonta la ligne de base. Les différents éléments sont numérotés sur la ligne de base, dans l'ordre qu'ils ont dans la séri définie pour l'application de la loi d'arbitrage, et ici indépendamment du fait qu'ils soient émetteurs ou récepteurs, sauf qu'un numéro unique est attribué aux éléments émetteur et demandeur appartenant à une même unit qui remplit les deux fonctions. Les lignes se rébouclent entre deux extrémités du tableau. Ainsi, la ligne de base, après le point S-\ g f continue vers So. De même, le chemin d'arbitrage, issu du point S13 = S (L3 aboutit au point S3 = S (D1), et le chemin issu du S15 = S (L4) aboutit au So = S (Do)» dans la même organisation que sur la figure On voit sur la représentation graphique de la figure 3 que les chemins d'arbitrage y sont formés de tronçons représentés par des segments successifs de lign droites, qui peuvent prendre trois orientations différent r montante, descendante ou étal (ou horizontale). L'orientation de chaque chemin parmi ces trois possibilité au-dessus de chaque point ne dépend que de la nature (de l fonction) et de l'état de l'élément présent en ce point ou des éléments présents en ce point. On peut qualifier comme suit les types de points ainsi rencontrés :
- Type (L,-) : récepteur libre sans émetteur demandeur dans la même unité.
- Type (-, D) î émetteur demandeur, sans récepteu libre.
- Type (L,D) : récepteur libre et en même temps émetteur demandeur. - Type (-,-) : ni récepteur libre, ni émetteur demandeur.
Cette classification "dynamique" caractérise les points Sk selon l'état courant des canaux émetteurs et récepteurs qu'ils représentent. La classification "statique" fera apparaître les types suivants :
- Type (R, -) : récepteur et pas émetteur (SR su la figure 4).
- Type (-,E): émetteur et pas récepteur (SE sur figure 4). - Type (R, E) : récepteur et émetteur (SRE sur l figure 4). En suivant les chemins d'arbitrage de gauche à droite, on voit que l'apparition d'un point Sk de tvPe (L ) fait remonter le tronçon de chaque chemin qui surmonte point vers le niveau suivant (par exemple, S15 sur la figure 3)» tandis que l'apparition d'un point S^ de type ,D), par exemple S8 - fait redescendre chaque chemin vers niveau suivant inférieur. Le passage au-dessus d'un point de type (L, D) ou (-,-) ne modifie pas le niveau : chaque chemin reste horizontal, ou étale. On remarque, en outre, que le tronçon initial et le tronçon terminal de chaque chemin sont plus abrupts que les tronçons intermédiaires, ceci au niveau où les noeuds d'aiguillage d'une première ligne de noeuds assurent la liaison fonctionnelle avec le éléments, émetteurs ou récepteurs, qui lui sont immédiate ment adjacents sur la ligne de base.
La figure 4 fait mieux apparaître que les noeuds d'aiguillage des différentes lignes (ou rangées) sont regroupés par ailleurs en colonnes, chaque colonne comportant une série de noeuds qui sont tous associés à u même élément. On a illustré par une ligne en trait interrompu partant de cet élément, le fait que tous les noeuds d'aiguillage d'une même colonne sont commandés à partir d'un noeud occupant la première ligne, suivant la nature de la fonction et suivant l'état de l'élément correspondant à la colonne. Cette commande a pour effet de déterminer dans chaque noeud, la formation d'un tronçon de chemin dans l'orientation ainsi sélectionnée, tronçon qui sera seul accessible à tout signal d'arbitrage circulant dans un chemin d'arbitrage passant en ce noeud, lequel , chemin est constitué d'un noeud à un autre par la suite de tronçons successifs individuels.
On a fait figurer à titre d'exemples :
- une ligne de commande de noeuds d'aiguillage de type XR à partir d'un noeud de commande d'aiguillage de type SR en un point où se trouve un élément récepteur,
- une ligne de commande de noeuds d'aiguillage de type XE...XE' à partir d'un noeud de commande d'aiguilla de type SE situé en un point où se trouve un élément émetteur,
- deux lignes de commande associées dans un cas où, en un point SRE, l'unité comporte à la fois un canal émetteur et un canal récepteur, les noeuds d'aiguillage étant de type XRE... XRE'.
Les actions nécessaires en ces différents noeud de la matrice d'arbitrage sont prises en charge concrè- tement par des circuits électroniques qui ont été représentés sur les figures 6 et 7 pour le cas le plus complet des types SRE et XRE, les autres pouvant aisémen être conçus de manière similaire avec les simplification appropriées. Les exigences sont, comme on i'a fait apparaîtr en trait renforcé sur une ligne intermédiaire de noeuds- la figure :
- en un point de type récepteur (R,-), prise en compte de l'état libre ou occupé par le noeud de command d'aiguillage SR et, dans tous les noeuds XR de la colonn sélection d'un tronçon horizontal si le récepteur est occupé, d'un tronçon ascendant si le récepteur est libre
- en un point de type émetteur (-,E) prise en compte de l'état demandeur ou non par le premier noeud S et, dans tous les noeuds de la colonne, sélection d'un tronçon de chemin horizontal si l'émetteur n'est pas demandeur, d'un tronçon descendant s'il est demandeur.
Ces différentes possibilités sont combinées ensembles dans les noeuds SRE et XRE associés à tout poi de type double (R,E), récepteur et émetteur. Toutefois, divers noeuds de la dernière ligne de la colonne ne permettent aucun tronçon ascendant.
Dans la forme de réalisation particulière des noeuds de la matrice d'arbitrage, telle qu'elle est illustrée par les figures 6 et 7, la formation d'un chem d'arbitrage se traduit par le passage d'un signal d'arbitrage binaire qui circule dans les tronçons sélectionnés par les commandes d'aiguillage.
Au niveau de la première ligne de noeuds (figure 6) un tel signal est prélevé à chaque élément récepteur et transmis par un tronçon ascendant 69 si le récepteur est libre (porte 66). Il peut retourner à un élément émetteur par un tronçon descendant 60 si l'émetteur est demandeur (porte 65). Sur la figure 6, il est repéré par l'entrée "in" au prélèvement d'un récepteur, et par la sortie "out à l'admission dans un émetteur, le récepteur et l'émetteu étant ici combinés en un seul noeud. Sur cette même figur l'état du récepteur se traduit par un signal "1" que prend la valeur 1 pour libre, ou la valeur 0 pour non-libre (do occupé), et celui de l'émetteur par signal "d" qu prend l valeur 1, s'il est demandeur, la valeur 0 s'il est non- demandeur.
Deux circuits bistables 61 et 62 de type D reçoivent respectivement ces signaux d'état ainsi qu'un signal de synchronisation jh. En combinaison avec deux portes ET 63 et 64, ils commandent :
1) Si les signaux d et 1 ont tous les deux la valeur 0, un premier état des deux circuits bistables d'où s'ensuit :
- l'ouverture des deux portes 63 et 64 et l'apparition d'une valeur 0 dans deux signaux de commande et r émis respectivement par chacune d'elles ;
- par l'ouverture de la porte 63, également l'ouverture de la porte ET 65 qui coupe ainsi l'accès du tronçon descendant 60 à la sortie "out" pour le transfert d'informations ;
- par l'ouverture de la porte 64, également l'ouverture d'une porte ET 66 qui coupe ainsi l'accès du tronçon ascendant 69 à l'entrée "in" ;
- l'ouverture d'une porte ET 67 pour interdire un transfert direct qui serait possible entre l'entrée "in" et la sortie "out". 2) Si les signaux d'état d_ et jL_ ont tous deux la. valeur 1 , un second état des deux circuits, bistables oppos au premier, avec en conséquence :
- la même ouverture des portes 63 et 64, d'o la valeur 0 pour les signaux de commande e_ et _r et la fermeture des tronçons 60 et 69 ;
- mais, la fermeture de la porte 67 qui suffit à fermer une porte OU 68 du circuit du signal vers la sortie "out", assurant ainsi le transfert direct des informations du signal binaire entre l'entrée "in" et la sortie "out".
3) Quand les signaux d'état sont d à la valeur 0 et 1 à la valeur 1, témoignant de l'état libre-du récepteur, l'émetteur restant non demandeur, le premier état pour le bistable 61 associé à l'émetteur et le second état pour le bistable 62 associé au récepteur, et par suite s
- la fermeture de la porte 64, la porte 63 restant ouverte j -«la production d'une valeur 1 sur le signal de commande de récepteur j? tandis que le signal de command d'émetteur e_ conserve la valeur 0 ;
- la fermeture de la porte 66, et donc du tronçon ascendant 69 qui devient ainsi capable de transmettre les informations binaires depuis l'entrée "in"
4) Quand les signaux d'état admis sont d à la valeur 1 et 1 à la valeur 0, un état symétrique du précédent pour les circuits bistables et les portes 63 et 64, d'où : - la production d'une valeur 1 sur le signal de commande d'émetteur .e tandis que le signal de commande de récepteur r conserve la valeur 0,
- la fermeture de la porte 65 sur le tronçon descendant 60 et, de ce fait, la porte 67 restant ouverte, la transmission de tout signal d'informations binaires de ce tronçon vers la sortie "out" par la porte OU 68.
Un schéma analogue à celui de la figure 6 est utilisé pour les autres noeuds de commande d'aiguillage d la première ligne de la matrice, avec toutefois toutes le simplifications utiles du fait que les constituants associés à la fonction émetteur ne servent pas quand l'unité correspondante a uniquement la fonction récepteur et vice-versa.
La même remarque vaut pour les noeuds d'aiguilla des autres lignes, et la figure 7 illustre seulement la réalisation d'un noeud associé a une unité ayant la fonction double d'élément émetteur et élément récepteur. Mais il est tenu compte, en outre, de ce qu'un tel noeud n'a pas la mission de créer les signaux de commande e_ et - mais seulement celle de les utiliser pour sélectionner ou bloquer un tronçon de chemin ascendant ou descendant, qu'il n'a pas non plus la mission de permettre des transferts de signal binaire avec une entrée "in" ou une sortie "out" et qu'au lieu de relier entrée et sortie, il doit rendre opératif ou bloquer un tronçon de chemin horizontal.
Conformément à la figure 7, les trois tronçons i possibles sont représentés chacun en 74 pour le tronçon descendant, 76 pour le tronçon ascendant, et 78 pour le tronçon horizontal, avec au coeur du noeud un groupe de quatre portes commandées par les signaux e_ et r , parmi lesquelles :
- une porte ET 71 bloque le tronçon descendant quand le signal e n'a pas la valeur 1,
- une porte ET 72 à une entrée sur le tronçon horizontal et deux entrées inversées sur les signaux e et r_, rend opératif le tronçon horizontal du noeud si les signaux de commande e_ et présentent tous deux la valeur (états non demandeur et non libre ou états demandeur et libre),
- une porte ET 73 bloque le tronçon ascendant si le signal de commande r n'a pas la valeur 1,
- et une porte OU 70, à trois entrées reliées aux trois sorties des portes précédentes, rend opératif le tronçon non bloqué en tant que tronçon constitutif du chemin d'arbitrage passant en ce noeud.
Dans le cas où les chemins sont multilignes pour permettre le transfert d'informations en parallèle, chaque porte logique des noeuds de la matrice d'arbitrage est remplacée par un ensemble de portes qui sont commandées pa les mêmes signaux e et r des lignes de commande d'aiguil¬ lage.
A ce stade de la description on aura compris comment fonctionne la matrice d'arbitrage et la mise en oeuvre de la loi d'arbitrage dans les deux étapes du procédé que sont :
- l'étape d'exploration des éléments d'une série d'unités préalablement définie qui se traduit par la production des valeurs 0 ou 1 dans les signaux d'état d et 1 ;
- l'étape de sélection des affectations d'éléments récepteurs à éléments demandeurs par la constitution de chemins d'arbitrage formés à travers la matrice par des tronçons qui sont sélectionnés à chaque noeud d'aiguillage sous la commande des signaux e et r produits sur une première ligne des noeuds en fonction de l'état de l'élément associé.
De plus, les chemins d'arbitrage ainsi constitués permettent la circulation d'informations contenues dans un signal d'arbitrage entre l'entrée "in" provenant d'un élément récepteur et la sortie "out" parvenant à un élémen émetteur. Ce signal permet de transmettre une adresse spécifique au récepteur libre correspondant par le chemin d'arbitrage qui la transmet à l'élément émetteur qui lui a été affecté par l'application de la loi d'arbitrage. Le même signal sert aussi à commander le changement d'état de éléments puisque l'élément émetteur devient "servi" et l'élément récepteur devient "occupé" pendant tout le temps que durera le transfert des informations entre les deux unités affectées l'une à l'autre.
Il convient maintenant de décrire brièvement comment ce signal d'arbitrage commande également l'établi sement d'une liaison fonctionnelle entre ces deux élément par la commande du relais de commutation correspondant de la matrice de commutation de la figure 1. A cette fin on référera à la figure 8 qui illustre les liaisons fonction nelles entre des éléments récepteurs et des éléments demandeurs par les quatre relais de commutation correspon dant.
On considère plus particulièrement un relais 31, placé dans la matrice d'interconnexion, sur la rangée d'u élément récepteur 32 qui s'est déclaré libre et auquel la matrice d'arbitrage a affecté l'élément émetteur 33 de la colonne de ce relais.
Dans le mode de réalisation particulier, pour l'élément récepteur, on a représenté sur cette figure, un registre 3^ qui contient l'adresse spécifique de l'élémen sous forme binaire et qui la délivre en tant que signal d'arbitrage vers l'entrée "in" de la matrice d'arbitrage. La fonction du registre est régie par un signal de synchronisation s_. L'adresse contient dans un premier bit une information de validation de l'affectation des deux éléments. Par ailleurs, le signal d'état IL de cet élément réception est transmis à travers la matrice d'intercon¬ nexion sur la ligne 35, le long de la rangée de noeuds (relais) correspondante. Sur cette même rangée les informations à transmettre de l'élément émetteur à l'élément récepteur une fois la liaison établie entre eux, passe sur une ligne 37.
Au niveau de l'élément émetteur associé, ces même informations sont admises le long de la colonne de noeuds ou relais, par une ligne 36.
Le signal d'état d_ de cet élément est produit, à la sortie d'un bistable 81 de type RS. Au moment où la loi d'arbitrage a décidé de l'affectation, il est à l'état 1 caractéristique d'un élément demandeur dès que la source associée effectue une demande d'émission et est maintenue dans cet état jusqu'à ce que l'élément soit servi.
^ Ces bistables 81 fonctionnent de manière asynchrone indépendamment du fonctionnement de la matrice d'arbitrage.
Le signal d'arbitrage reçu à la sortie "out" du chemin d'arbitrage parvenant à l'élément 33, transmet 0 - l'adresse de l'élément récepteur à un registre à décalage 82. L'arrivée du bit de validation provoque, au niveau du bistable 81, le passage du signal d à la valeur 0, traduisant le changement d'état de "demandeur" à "servi," donc non demandeur. Il est également transmis par une lig 5 38 qui commande la démarrage de la transmission d'informations par la ligne 36. A la fin de cette transmission, la source d'informations émet un signal qui est reçu par 39 dans le registre à décalage 82, pour annuler l'effet du bit de validation et commander à nouve 0 la mise à l'état demandeur dans le signal d^.
L'élément 33 est muni par ailleurs d'un décodeur d'adresse 84 qui comporte autant de sorties qu'il y a de relais aux noeuds de la colonne dans la matrice d'arbitrage. Chaque sortie étant reliée à l'un des relais 5 Ce décodeur 84 traite l'information d'adresse du registre
82 sous la commande du bit de validation, et en fonction cette adresse, il commande la fermeture du relais 31 présent sur la rangée contenant l'émetteur 32 qui présent cette adresse. 0
Le relais, illustré par un buffeur tri-état 85, met ainsi en liaison les lignes 36 et 37 pour la transmission d'information. Simultanément, la même sortie du décodeur d'adresse 84 commande une porte NON-OU 86 qui comporte autant d'entrées qu'il y a d'éléments émetteurs 5 dans la rangée du relais 31. La sortie de la porte est la ligne 35 sur laquelle par conséquent, l'opération du sign d'adresse à l'entrée de la porte, fait passer la signal à l'état non-libre tant que le récepteur 32 est occupé d une liaison avec un émetteur par un relais de sa rangée. Dans le cours de la description précédente, on s'est intéressé notamment au cas ou une même unité de l'ensemble d'interconnexion peut remplir et la fonction d'élément émetteur et la fonction d'élément récepteur. Ce permettra maintenant de mentionner une possibilité d'application de l'invention à des ensembles particuliè¬ rement complexes. On n'entrera toutefois pas dans le déta de la réalisation pratique pour ce qui en est à la portée de l'homme de l'art.
Dans un tel exemple selon l'invention, on peut assurer un ordre de priorité tournant dans les affectatio entre éléments afin d'éviter qu'un élément émetteur demandeur particulier reste trop longtemps non servi. On prévoit donc pour cela de constituer l'ensemble d'inter¬ connexions entièrement par des unités à fonctions émetteu et récepteur, et donc la matrice d'arbitrage entièrement par des noeuds des types SRE et XRE des figures 6 et 7. L différentes unités sont réparties dans le dispositif d'arbitrage en divers groupes contenant chacun un même nombre d'éléments, et chacun des éléments dans chacun des groupes peut être commandé pour être alternativement capable ou non de remplir la fonction d'élément récepteur Par ailleurs, on prévoit qu'à chaque instant, une seule unité remplit la fonction d'élément récepteur dans chacun des groupes. Une étape du procédé préalable aux étapes d'exploration et de sélection détermine celle des unités groupe qui pourra remplir cette fonction d'élément récepteur, et chaque fois que cette unité a été utilisée dans une affectation et une connexion à un élément émetteur, on commande le passage de cette fonction d'élément récepteur de l'unité correspondante à la suivante. Tout autre algorithme de permutation est égale- ment possible.
Naturellement, l'invention n'est en rien limitée par les particularités qui ont été spécifiées dans ce qui précède ou par les détails du mode de réalisation particulier choisi pour illustrer l'invention. Toutes sortes de variantes peuvent être apportées à la réalisatio particulière qui a été décrite à titre d'exemple et à ses éléments constitutifs sans sortir pour autant du cadre de l'invention. Cette dernière englobe ainsi tous les moyens constituant des équivalents techniques des moyens décrits ainsi que leurs combinaisons.

Claims

REVENDICATIONS
1. Procédé de commande de commutations dans un ensemble d'interconnexions entre une pluralité d'unités chacune à au moins une fonction parmi celles d'élément émetteur et d'élément récepteur, caractérisé en ce que l'o ordonne au moins certains desdits éléments en une série d'éléments successifs, où tous les éléments récepteurs son interchangeables dans un rôle à remplir à l'égard de chaq élément émetteur, on explore ladite série desdits éléments en déterminant pour chaque élément émetteur s'il est dans un état demandeur ou dans un état non demandeur et pour chaque élément récepteur s'il est dans un état libre ou dans un état occupé, et à un élément récepteur libre on affecte un élément émetteur demandeur qui est sélectionné selon une loi d'arbitrage prédéterminée en fonction des états respectifs des éléments intermédiaires entre eux dan ladite série, et en ce que l'on commande alors la connexio entre les éléments d'unités correspondants dans ledit ensemble ainsi que leur changement d'état demandeur à état non demandeur et d'état libre à état occupé.
2. Procédé de commande de commutations selon la revendication 1, caractérisé en ce que ladite loi d'arbitrage sélectionne, pour l'affecter à un élément récepteur libre, celui des émetteurs demandeurs qui est le premier dans ladite série à être tel que dans les éléments successifs qui l'en séparent, le nombre de récepteurs libres soit égal au nombre d'émetteurs demandeurs.
3. Procédé selon la revendication 1 ou 2, caracté risé en ce que les étapes d'exploration et de sélection sont réalisées en permanence par l'établissement de chemin d'arbitrage pour la transmission d'un signal d'arbitrage produit par un élément récepteur libre et reçu par un élément émetteur demandeur.
4. Procédé selon la revendication 1, 2 ou 3, caractérisé en ce que l'on fait comporter à ladite série plusieurs groupes d'unités comportant chacun plusieurs unités pouvant être rendues alternativement capables ou no de remplir la fonction d'éléments récepteur, en ce que l'o confère cette capacité à l'une seule desdites unités dans chaque groupe, (en la faisant passer à la suivante après) et en ce qu'après sélection pour une connexion, on fait passer cette capacité à la suivante, ou selon un autre algorithme analogue.
5. Dispositif de commande de commutations pour la mise en oeuvre du procédé selon la revendication 1, carac térisé en ce qu'il comporte des moyens d'exploration pour produire pour chaque élément émetteur un signal d'état (d) traduisant s'il est ou non à l'état demandeur et pour chaque élément récepteur un signal d'état (1) traduisant s'il est ou non à l'état libre, des moyens pour prélever à chaque élément récepteur à l'état libre (32) un signal d'arbitrage contenant une adresse de cet élément, des moyens pour recevoir un tel signal d'arbitrage à chaque élément émetteur à l'état demandeur (33) e pour décoder l'adresse qu'il contient, des moyens pour transmettre les signaux d'arbitrage suivant des chemins d'arbitrage établi à travers des noeuds d'aiguillage (XRE) par application de la loi d'arbitrage.
6. Système d'interconnexion comportant un ensembl d'unités présentant chacune au moins une fonction parmi celles d'élément récepteur et élément émetteur, dans lequ lesdites unités sont organisées en une matrice d'intercon¬ nexion comportant en chaque noeud un relais de commande d'une connexion entre un élément émetteur et un élément récepteur,- et dans lequel lesdites unités sont organisées par ailleurs en une matrice d'arbitrage où chacun desdits éléments est associé à une pluralité de noeuds d'aiguilla permettant le transfert d'un signal d'arbitrage à un noeu voisin.
7. Système selon la revendication 6, caractérisé en ce que la matrice d'arbitrage comporte une première ligne de noeuds de commande d'aiguillage permettant le prélèvement d'un signal d'arbitrage depuis un élément récepteur s'il est à l'état libre, ou son transfert à un élément émetteur s'il est à l'état demandeur et la comman de noeuds d'aiguillage associés audit élément récepteur o émetteur pour déterminer sélectivement dans chacun la formation d'un tronçon de chemin d'arbitrage permettant l transfert d'un tel signal d'arbitrage vers un noeud voisi sélectionné d'après l'état dudit élément.
8. Dispositif selon la revendication 7, caracté¬ risé en ce que chaque noeud d'aiguillage comporte des moyens pour bloquer ou rendre opératif comme tronçon dudi chemin d'arbitrage l'un seul des trois tronçons de liaiso avec des noeuds voisins qui peut être un tronçon horizont et soit un tronçon ascendant pour un élément récepteur, soit un tronçon descendant pour un élément émetteur.
EP19880907706 1987-09-07 1988-09-06 Procede et dispositif de commandes de commutations dans un ensemble d'interconnexions Withdrawn EP0331701A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR8712364A FR2620285B1 (fr) 1987-09-07 1987-09-07 Procede et dispositif de commandes de commutations dans un ensemble d'interconnexions
FR8712364 1987-09-07

Publications (1)

Publication Number Publication Date
EP0331701A1 true EP0331701A1 (fr) 1989-09-13

Family

ID=9354665

Family Applications (1)

Application Number Title Priority Date Filing Date
EP19880907706 Withdrawn EP0331701A1 (fr) 1987-09-07 1988-09-06 Procede et dispositif de commandes de commutations dans un ensemble d'interconnexions

Country Status (5)

Country Link
EP (1) EP0331701A1 (fr)
JP (1) JPH02502590A (fr)
AU (1) AU2301788A (fr)
FR (1) FR2620285B1 (fr)
WO (1) WO1989002630A1 (fr)

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4349702A (en) * 1978-05-12 1982-09-14 Bell Telephone Laboratories, Incorporated Nodal switching network with binary order links
FR2470996B1 (fr) * 1979-11-30 1986-01-31 Quinquis Jean Paul Perfectionnements aux systemes electroniques multiprocesseurs destines au traitement de donnees numeriques et logiques
AT383221B (de) * 1980-09-08 1987-06-10 Quatember Bernhard Dipl Ing Dr Rekonfigurierbares verbindungsnetzwerk
DE3151081C2 (de) * 1981-12-23 1983-12-15 Felten & Guilleaume Fernmeldeanlagen GmbH, 8500 Nürnberg Verfahren und Anordnung zur Verbindungsherstellung in einer Fernmeldeanlage
DE3215080A1 (de) * 1982-04-22 1983-10-27 Siemens AG, 1000 Berlin und 8000 München Anordnung zur kopplung von digitalen verarbeitungseinheiten
JPS61214694A (ja) * 1985-03-18 1986-09-24 インタ−ナショナル　ビジネス　マシ−ンズ　コ−ポレ−ション データ伝送のスイッチング装置

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO8902630A1 *

Also Published As

Publication number Publication date
WO1989002630A1 (fr) 1989-03-23
AU2301788A (en) 1989-04-17
JPH02502590A (ja) 1990-08-16
FR2620285A1 (fr) 1989-03-10
FR2620285B1 (fr) 1990-01-19

Similar Documents

Publication Publication Date Title
EP1701274B1 (fr) Architecture de noeud de communication dans un système de réseau sur puce globalement asynchrone
EP0597028B1 (fr) Architecture de systeme en tableau de processeurs a structure parallele
FR3072797A1 (fr) Synchronisation dans un agencement de traitement a paves multiples et a puces multiples
FR2509944A1 (fr) Systeme de diagnostic et methode de localisation des defauts dans un reseau de commutation a commande repartie
EP0005722A1 (fr) Système de sélection de circuit d&#39;interface prioritaire
EP0039635B1 (fr) Procédé d&#39;arbitration centralisée, et arbitreur centralisé
EP0340841A1 (fr) Elément de circuit-point de croisement entre deux lignes omnibus
EP0782815B1 (fr) Dispositif de gestion de relations entre des objets
EP0331701A1 (fr) Procede et dispositif de commandes de commutations dans un ensemble d&#39;interconnexions
FR3007916A1 (fr) Systeme de transmission d&#39;informations commute utilisable notamment dans des applications avioniques
CA1092225A (fr) Central telephonique et les circuits de commande associes
FR2948206A1 (fr) Dispositif et procede pour l&#39;execution distribuee de traitements de donnees numeriques
FR2766937A1 (fr) Protocole et systeme de liaison par bus entre elements d&#39;un microcontroleur
EP0113272B1 (fr) Réseau maille modulaire de communications
EP1052573B1 (fr) Procédé et dispositif pour commander l&#39;ordre de départ d&#39;informations ou d&#39;objets stockés temporairement
FR2627878A1 (fr) Dispositif de traitement numerique de signaux
EP0505541B1 (fr) Circuit de gestion de sorties pour automate programmable
EP1772808A1 (fr) Dispositif et procédé de lecture d&#39;informations dans un ensemble de composants électroniques reliés à un bus de communication, appliqué à la lecture d&#39;une matrice de pixels
FR2617302A1 (fr) Circuit pour memoriser des etats de disponibilite de ressources logiques, telles que cellules de memoire, et etablir des adresses de ressources libres
FR2538140A1 (fr) Dispositif de couplage de bus pour systeme de traitement de donnees a bus multiples
EP1493083B1 (fr) Système reconfigurable de contrôle basé sur la mise en oeuvre matérielle de graphes de pétri
EP4434205A1 (fr) Configuration dynamique de la planification de transmission des flux dans les réseaux déterministes
FR2668626A1 (fr) Procede de configuration d&#39;un systeme informatique maille.
FR2642252A1 (fr) Unite d&#39;interconnexion entre circuits, notamment du type crossbar procede de mise en oeuvre d&#39;une unite d&#39;interconnexion entre circuits, et utilisations d&#39;une unite d&#39;interconnexion entre circuits
EP0403364A2 (fr) Dispositif de transfert bidirectionnel de données entre une station centrale et des stations locales

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 19890425

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE CH DE FR GB IT LI LU NL SE

17Q First examination report despatched

Effective date: 19910812

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 19911224