FR2490434A1 - Dispositif de resolution des conflits d'acces et d'allocation d'une liaison de type bus interconnectant un ensemble de processeurs non hierarchises - Google Patents
Dispositif de resolution des conflits d'acces et d'allocation d'une liaison de type bus interconnectant un ensemble de processeurs non hierarchises Download PDFInfo
- Publication number
- FR2490434A1 FR2490434A1 FR8019751A FR8019751A FR2490434A1 FR 2490434 A1 FR2490434 A1 FR 2490434A1 FR 8019751 A FR8019751 A FR 8019751A FR 8019751 A FR8019751 A FR 8019751A FR 2490434 A1 FR2490434 A1 FR 2490434A1
- Authority
- FR
- France
- Prior art keywords
- bus
- station
- stations
- arbitration
- access
- 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.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; 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
- G06F13/36—Handling requests for interconnection or transfer for access to common bus or bus system
- G06F13/368—Handling requests for interconnection or transfer for access to common bus or bus system with decentralised access control
- G06F13/374—Handling requests for interconnection or transfer for access to common bus or bus system with decentralised access control using a self-select method with individual priority code comparator
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Bus Control (AREA)
- Multi Processors (AREA)
- Computer And Data Communications (AREA)
- Debugging And Monitoring (AREA)
- Small-Scale Networks (AREA)
Abstract
DISPOSITIF PERMETTANT DES CONFLITS D'ACCES A UN BUS D'UNE PLURALITE DE STATIONS EMETTRICES - RECEPTRICES DE DONNEES COMPRENANT CHACUNE UN PROCESSEUR ASYNCHRONE ET NON HIERARCHISE, CES STATIONS ETANT RELIEES EN PARALLELE A UN BUS DE TRANSMISSION DE DONNEES AINSI QU'A UN BUS D'ARBITRAGE 5 D'ACCES ET A UN BUS D'OCCUPATION 6, CE DERNIER ETANT MARQUE QUAND LE BUS DE TRANSMISSION DE DONNEES TRANSMET DES DONNEES. IL EST CARACTERISE EN CE QUE CHAQUE STATION COMPREND, OUTRE LE PROCESSEUR, UNE MEMOIRE ET UN SELECTEUR DE SIGNAUX DE TEMPORISATION 300 AYANT DANS CHAQUE STATION DES DUREES DIFFERENTES, DES MOYENS DE MARQUER 305 FIL "MARQUAGE" QUAND LA STATION SE PORTE APPELANTE LE BUS D'ARBITRAGE PENDANT UN TEMPS EGAL A LA DUREE DU SIGNAL DE TEMPORISATION SELECTE, DES MOYENS DE TESTER 305 FIL "ETAT" LE BUS D'ARBITRAGE A LA FIN DU SIGNAL DE TEMPORISATION SELECTE, DES MOYENS DE PRENDRE LE CONTROLE DU BUS DE TRANSMISSION DES DONNEES SI LE TEST INDIQUE LA DISPONIBILITE DU BUS D'ARBITRAGE ET DES MOYENS DE PRISE EFFECTIVE BORNE 111 DU BUS DE TRANSMISSION DES DONNEES QUAND LE BUS D'OCCUPATION DEVIENT DEMARQUE.
Description
- 1 -
DISPOSITIF DE RESOLUTION DES CONFLITS D'ACCES ET D'ALLOCATION D'UNE
LIAISON DE TYPE BUS INTERCONNECTANT UN ENSEMBLE DE PROCESSEURS NON
HIERARCHISES
La présente invention concerne les systèmes multiprocesseurs à
structure répartie, parallèles et asynchrones et dont la liaison d'in-
terconnexion est un bus.
Dans les systèmes de ce type, chaque processeur est raccordé au bus par une interface logicielle et matérielle: ce coupleur assure d'une part la gestion des protocoles d'échange des données entre le processeur expéditeur (ou demandeur) et le processeur destinataire (ou
serveur)et d'autre part, réalise les fonctions de l'invention.
Il y a autant de coupleurs que de processeurs, ils sont tous identiques et on conviendra d'appeler station, l'association d'un
processeur et du coupleur rattaché.
Dans tout système de processeurs parallèles et asynchrones orga-
nisé autour d'une ressource ou de ressources communes, ici le bus, les situations de conflit sont inévitables lorsque deux ou plusieurs stations
tentent d'accéder simultanément au bus afin de transmettre des infor-
mations vers d'autres stations ainsi qu'à la libération du bus, à la prise duquel deux ou plusieurs stations s'étaient portées candidates
tandis qu'il était indisponible parce qu'y transitaient des informations.
Pour éviter les collisions d'accès nuisibles au bon fonctionnement de l'ensemble du système, on fait appel aux dispositifs d'arbitrage qui ont pour rôle de ne sélectionner qu'une station parmi celles qui sont en conflit (parce que simultanément candidates) puis d'allouer le bus à
celle-ci le temps nécessaire pour qu'elle y propage un message d'in-
formations. A l'issue de ce temps, les stations provisoirement rejetées tentent de nouveau l'accès au bus activant les dispositifs d'arbitrage
et ainsi de suite...
On notera également que les systèmes multiprocesseurs organisés autour d'une liaison bus réalisent facilement la technique de l'adressage logique par diffusion. Une station demanderesse d'un service, d'une tâche, d'une fonction... exécutable par une station du système peut ignorer l'implantation géographique et le nom (ou étiquette physique) de cette station ou des stations dans le cas d'une multiplication de la
fonction pour des raisons de partage de travail ou de sûreté de fonction-
nement. Il lui suffit en effet de diffuser le nom logique de la fonction
- 2 - 2490434
(ou du service, ou de la tâche) sur le bus de DONNEES pour que la ou les stations capables de la traiter prennent la demande en compte à l'issue d'un seul message. Les avantages sont importants: 1. il n'y a pas de tables logicielles associant le nom logique de la fonction aux adresses des stations pouvant l'éxécuter à consulter
au préalable.
2. accès immédiat à une station disponible sans avoir recours à une recherche en séquence dans le cas o la première station adressée
physiquement était ou surchagée ou défaillante.
3. reconfiguration rapide, car il n'y a plus la mise à jour des
tables logicielles mentionnées au point 1.
4. possibilité pour chaque station de reconnaître plusieurs
adresses logiques.
La difficulté à résoudre consiste à ne sélectionner qu'une station parmi éventuellement toutes celles qui sont capables d'exécuter la
fonction. Un dispositif d'arbitrage des serveurs réalise cette opération.
L. NISNEVICH & E. STRASBOURGER dans "DECENTRALIZED PRIORITY CONTROL IN DATA COMMUNICATION", Second Annual Symposium on Computer Architecture,
Houston, Texas, 20 - 22 janvier 1975, page 1 à 6, ont proposé un dispo-
sitif d'arbitrage consistant à émettre une information sur un bus commun et à comparer celle-ci à l'état réel de ce bus; en cas de divergence,
la station émettrice se retire d'elle-même.
Dans le dispositif de l'invention, il y a, comme dans le dispositif de NISNEVICH, une station qui prend la maîtrise du bus de DONNEES lors d'un conflit, car on alloue à chaque station une priorité dynamique. Mais le dispositif de l'invention diffère du mécanisme de NISNEVICH par les points suivants:
1. il utilise un principe de codage des arbitres original (tempo-
risation) qui, à performances égales, ne nécessite qu'une liaison fonc-
tionnelle (au lieu de 2), le bus d'ARBITRAGE et le bus d'OCCUPATION peu-
vent en effet être confondus.
2. il est plus économique en matériel que les allocateurs du type NISNEVICH à liaisons parallèles tout en étant plus rapide, car il
permet le parallélisme allocation-transmission dans le cas o l'on dis-
tingue le bus d'ARBITRAGE du bus d'OCCUPATION.
3. enfin, il permet la sélection des serveurs sans liaison spé-
cialisée supplémentaire.
- 3 - Le dispositif de l'invention apporte une solution économique, performante et sûre, aux problèmes liés aux conflits d'accès aux liaisons bus, c'est-à-dire: - qu'il assure la maîtrise du bus de données à un seul demandeur à la fois, quelle que soit l'importance du trafic; - qu'il garantit un service équitable des demandes d'accès par l'absence de hiérarchie, régulant de cette manière l'écoulement des flux de données sans avoir recours aux techniques de type contrôleur centralisé ou au surdimensionnement; - qu'il permet l'allocation dynamique et provisoire d'une priorité d'accès; - qu'il garantit le rendement maximum des échanges inter-stations grâce à la possibilité de recouvrement des phases d'allocation et de transmission; - qu'il permet l'arbitrage et la sélection des candidats serveurs
sans avoir recours à un dispositif particulier.
L'invention va être maintenant décrite en détail en relation avec les dessins annexés dans lesquels: - la Fig. 1 représente sous la forme d'un diagramme de blocs le système de processeurs en parallèle reliés à un bus de DONNEES commun les interconnectant et montre l'existence dans chaque station d'un allocateur conforme à l'invention; - la Fig. 2 représente sous la forme d'un diagramme de blocs un allocateur; - les Figs. 3, 4 et 5 sont des chronogrammes d'arbitrage entre candidats "demandeurs" simultanés,candidats "serveurs" simultanés et candidats "demandeurs" et "serveurs"; - les Figs. 6 et 7 expliquent la différence entre un système de processeurs en parallèle avec phases d'allocation et de transmission en série et phases d'allocation et de transmission en parallèle, le système de l'invention appartenant au second type; - la Fig. 8 représente un circuit d'arbitrage "demandeurs" - la Fig. 9 représente un circuit d'arbitrage "serveurs"; et - les Figs. 10 et 11 sont relatives à la détermination de la différence minimale entre les durées de deux signaux de temporisation d'arbitrage. - 4 -
En se référant à la Fig. 1, plusieurs processeurs 11, 12...
N sont reliés par l'intermédiaire de connexions 1101, 1102,... 110N, de coupleurs 21, 22,... 2N et de connexions 401, 402 -... 40N à un bus de TRANSMISSION DE DONNEES 4. Ces processeurs sont également reliés par l'intermédiaire de connexions (1111 - 1151), (1112 - 1152)... (111N 115N), d'allocateurs 31, 32'... 3 et de connexions 501, 502' N et 601, 6023... 60N respectivement à un bus ARBITRE 5 et à
un bus d'OCCCUPATION 6.
Les allocateurs 31 32 3N sont des automates câblés dont
la structure est représentée sur la Fig. 2. Un allocateur 3 est cons-
titué d'un oscillateur piloté par quartz 301, d'un générateur de tempo-
risations d'arbitrage 300, d'un arbitre "demandeurs" 3000 et d'un arbitre "serveurs" 3500. Le générateur d'arbitrage 300 est activé par un signal "départ" émis soit sur le fil 3010 par l'arbitre "demandeurs" 3000, soit sur le fil 3510 par l'arbitre "serveurs" 3500 et qui lui parvient par la porte OU 307 et le fil-310. Ce signal "départ" provoque la délivrance sur le fil 311 d'un signal "test" après décomptage, dans un décompteur 302 de la temporisation prise au hasard dans le champ de codes binaires 303. Un signal "forçage priorité" peut par le fil 325 positionner le générateur de temporisations 300 sur la temporisation
la plus forte par commande du processeur.
L'allocateur comprend en outre un décodeur 304 qui reçoit des
informations binaires de commande générées par le processeur de la sta-
tion et dont la signification apparait sur le tableau I ci-après
qui n'est autre que le tableau en légende de la Fig. 2.
- 5 - 24PO434
TABLEAU I
Codage de signaux de commande Des circuits d'interface 305 avec le bus ARBITRAGE 5 et 306 avec le bus d'OCCUPATION 6 connectent respectivement aux bus 5 et 6 le circuit d'ARBITRAGE "demandeurs" 3000 et le circuit d'ARBITRAGE "serveurs" 3500.
Un allocateur est donc un organe autonome, indépendant physi-
quement de la liaison 40 au bus de transmission de données, inter-
connecté d'une part à ses homologues par 2 liaisons bus spécialisées 5 et -6 et d'autre part, au processeur de la station à laquelle il appartient
par 5 liaisons point à point 111 - 115.
Le bus ARBITRE 5 et le bus OCCUPATION 6 sont des liaisons physiques multipoints et monofilaires pouvant atteindre une longueur de plusieurs dizaines de mètres; l'un supporte les codes d'arbitrage, l'autre indique la disponibilité ou l'occupation du bus de DONNEES. Ils présentent tous deux 2 niveaux électriques OV,+ 3V correspondant aux niveaux logiques
O et 1.
Le Bus ARBITRAGE 5 Le niveau 1 (marquage) interdit la capture du bus de DONNEES à une station demanderesse ou une station serveur, la première doit attendre
son démarquage (ou libération); la seconde est immédiatement rejetée.
Le marquage à 1 est provoqué: - soit par un candidat demandeur ou serveur dans sa phase d'allocation
A1 A2 A3
O O O O activation de l'arbitre demandeur 1 O O 1 libération de l'arbitre demandeur O 1 O 2 marquage de l'arbitre demandeur 1 1 O 3 activation del'arbitre serveur O O 1 4 Libération de l'arbitre serveur O 1 1 6 Forçage d'une temporisation prioritaire 6 - par l'émission de sa temporisation d'arbitrage; - soit par le demandeur maître et le serveur maître dans leur phase
d'échange d'informations.
Le Bus d'OCCUPATION 6 Il est à 1 durant toute phase d'échange entre un demandeur et
un serveur.
Il est à O lorsque le bus de TRANSMISSION DE DONNEES est au repos. La combinaison des états des bus ARBITRE et OCCUPATION autorise ou non les tentatives d'accès des allocateurs des stations demandeurs
et serveurs.
TABLEAU II
BUS ARBITRE BUS OCCUPATION ARBITRE DEMANDEURS ARBITRE SERVEURS
6} 3000 3500
i. I 0 O autorisé rejeté O 1 attend autorisé I 0 attend rejeté 1 1 attend rejeté Les mécanismes d'arbitrage 3000 et 3500 se déroulent de la mnème manière entre des candidats demandeurs ou des candidats serveurs, mais l'un 3000 est activé lorsque le bus d'OCCUPATION 6 est à O, et
l'autre 3500,1orsqu'il est à 1.
Les chronogamnes des Figs. 3 et 4 explicitent le principe de résoluticn des conflits d'accès entre successivement des candidats demandeurs et serveurs. Les chronogammes de la Fig. 6 représentent une synthèse. En se référant a la Fig. 3 qui représentent des chronogammes d'arbitrage des stations "demandeurs" au temps tO,les stations 11, 12 et 1N activent simultanément leurs allocateurs 31, 32 et 3N en appliquant aux fils 1131 1151, 1132 - 1152 et 113N - 115N le signal 000. Le bus ARBITRE 5 est à O et le bus OCCUPATION 6 est à O. D'après le tableau I, les trois stations sont autorisée à émettre leur signal de temporisation d'arbitrage A1 pour 11, A2 pour 12 et AN pour 1N. On suppose que
A1 AN > A2
En tl, finde la temporisation d'arbitrage A2 de 12. La station
12 teste l'état du bus ARBITRE. Il est occupé. La station 12 est re-
jetée mais maintient sa candidature.
En t2, fin de la temporisation d'arbitrage AN de la station 1N.
Le bus ARBITRE est testé; il est occupé. La station 1N est rejetée mais
maintient sa candidature.
En t3, fin de la temporisation d'arbitrage A1 de la station 11 (c'est la plus longue des temporisations d'arbitrage). Le bus ARBITRE est testé; il est libre. La station 11 prend la maîtrise du
bus de DONNEES.
En t4 = t3 + T, les stations 12 et 1N activent de nouveau leurs allocateurs, un temps T après avoir détecté la libération du bus ARBITRE
en t3.
En t5, la station 12 est rejetée mais maintient sa
sa candidature.
En t6, la station 1N trouve le bus ARBITRE libre et prend la maîtrise du bus de DONNEES mais elle doit attendre la libération du
bus d'OCCUPATION avant d'émettre son message.
En t7, la station 1p tente la capture du bus de DONNEES; elle
est immédiatement rejetée car le bus d'OCCUPATION est à 1.
En t8, libération du bus d'OCCUPATION par la station 11. Les
stations 12 et 1p activent leurs allocateurs (on suppose Ap < A2).
En t9, marquage du bus d'OCCUPATION par la station 1N
En t10, la station 1p est rejetée.
En t11, la station 12 prend la maîtrise du bus de DONNEES mais
n'émettra qu'en t13.
On voit clairement qu'en to il y avait trois stations candidates simultanément et qu'elles ont été autorisées dans l'ordre 11, 1N, 12 de leurs temporisations d'arbitrage A1 > AN > A2. De même en temps t8,
il y avait deux stations candidates simultanées et elles ont été auto-
risées dans l'ordre 12, lp de leurs temporisation d'arbitrage A2 > AP' Une station demandeur, après avoir activé son allocateur, exprimant ainsi son désir d'accéder au bus de TRANSMISSION DE DONNEES, peut présenter les états suivants: - émission immédiate de la temporisation d'arbitrage, les bus
ARBITRE et OCCUPATION étant à 0.
- rejet par un allocateur plus prioritaire se soldant par une attente de libération du bus ARBITRE, laquelle provoque -8-
l'émission de la temporisation d'arbitrage.
- capture du bus de DONNEES avec émission imédiate d'un message ou attente de la liberation du bus de DDNNEES si celui-ci
est occupé.
- marquage du bus ARBITRE lorsqu'elle a trouvé un serveur. Un demandeurpeutcbnc attendre soit comme candidat a la prise, soit comme
maître, procédure qui permnnet de réaliser le parallélisme allocation-
transmission.
En se référant maintenant à la Fig. 4 qui représente des chro-
nogrammes d'arbitrage des stations "demandeurs" et "serveurs", on voit que:
en to0, la-station 11 est candidat demandeur et émet sa tempori-
sation d'arbitrage A1
en t1, la station 11 prend la maîtrise du bus de DONNEES.
en t2, la station 11 marque le bus OCCUPATION et émet un pré-
message contenant l'étiquette logique TRAD voulant dire TRADUCTION.
en t3, les stations lx, 1y, susceptibles de remplir la fonction TRAD présentent simultanément leur candidature en serveur en activant
leurs allocateurs qui émettent les temporisations AX et Ay.
en t4, la station 1z susceptible de remplir également la fonction TRAD présente sa candidature mais trop tard, le bus ARBITRE étant pris
par 1X et ly; la station Z est rejetée.
en t5, la station 1X est rejetée, le bus ARBITRE étant à 1.
en t6, 1Y libère le bus ARBITRE; elle est sélectionnée en serveur; elle émet un accusé de réception et marque le bus ARBITRE
interdisant sa prise par un autre serveur.
en t7, 11 a reçu l'accusé de réception indiquant la disponibilité
de 1y comme serveur, 11 marque également le bus ARBITRE.
en t8, 11 émet son message d'information à destination du ser-
veur 1y.
en t9, iy a reçu le message et libère le bus ARBITRE.
en t10, 1y émet un nouvel accusé de réception vers 11.
en t11, 11 a reçu l'accusé de réception; le message est parvenu
à destination; elle libère les bus ARBITRE et OCCUPATION.
Une station serveur ayant reconnu une adresse fonctionnelle (ici
TRAD) dans le pré-message émis par le demandeur et, activant son allo-
cateur, peut présenter les états suivants - rejet immédiat soit parce que le bus ARBITRE est à 1, soit parce que le bus OCCUPATION est à O émission de la temporisation d'arbitrage au terme de laquelle il y a: rejet si le bus ARBITRE reste à 1 - prise si le bus ARBITRE est à O Le chronogramme d'arbitrage entre candidats-serveurs fait apparaître la nécessité de la procédure d'échange de type "hand-shaking"
entre une station "demandeur" et une station"serveur'. L'enchaî-
nement étant le suivant: - le demandeur émet un pré-message contenant son adresse et une étiquette fonctionnelle - le serveur sélectionné renvoie un accusé de réception - le demandeur émet son message d'information - le serveur achève l'échange par un nouvel accusé de réception Un intervalle de temps T est réservé entre 2 marquages des bus ARBITRE et OCCUPATION. Il est nécessaire pour que le front de démarquage soit décelable pour toutes les stations candidates en
attente du bus.
Un signal trop bref serait en effet trop altéré à l'issue de
sa propagation sur un bus de plusieurs mètres de longueur.
Le parallélisme allocation-transmission
Les chronogrammes des Figs. 3, 4 et 5 mentionnent cette possi-
bilité du dispositif proposé, la comparaison entre la Fig. 6 et la
Fig. 7 en souligne l'intérêt.
En effet, la Fig. 6 de l'art antérieur qui présente l'enchaînement des opérations d'allocation et de transmission met en évidence les pertes de temps provoquées par les phases d'allocation, d'autant plus importantes que le trafic est élevé et que le rapport entre le temps d'allocation et
le temps de transmission est élevé.
S'il est possible de réduire les temps d'allocation à quelques microsecondes, cet "overhead" cumulé représente néanmoins une perte représentant dans certains cas jusqu'à 50 % du taux d'occupation utile du bus. La Fig. 7 représente la simultanéité entre phases d'allocation et phases de transmission, le bus de D0NNEES pouvant travailler ainsi
à son rendement maximum.
Les critères de sélection et l'allocation dynamique de priorité -Un conflit étant toujours résolu au profit de l'allocateur qui possède la temporisation la plus longue, il est indispensable que cette priorité tourne à travers les allocateurs afin que ceux-ci aient en moyenne la même chance d'accéder au bus lorsqu'ils présentent leur
candidature.
Pour cela, le dispositif de l'iînvention consiste à allouer à chaque allocateur un champ de codes binaires dans lequel est tiré au
hasard le code qui fixera la temporisation d'arbitrage.
Les codes seront nécessairement différents d'un allocateur à
l'autre mais ils seront répartis de telle manière que la somme arith-
métique des codes d'un champ soit la même pour chacun de ces champs,
algorithme de répartition qui garantit un service en moyenne équitable.
En régime de surcharge, le hasard peut cependant faire qu'une station candidate attende le bus au-delà d'une.durée qu'elle estime anormale, il se peut également qu'une station souhaite transmettre un message de caractère urgent, dans ces cas, la possibilité de forcer une priorité élevée est indispensable. Celle-ci sera une temporisation plus longue que toutes celles qui appartiennent aux champs de codes
des allocations.
C'est le signal FORCAGE PRIORITE qui active ce code prioritaire.
Si l'application l'exige, il est également possible d'allouer à certaines stations des champs de codes ayant une valeur moyenne plus élevée que
celle des autres stations.
Les temporisations d'arbitrage Nécessairement toutes différentes, leur nombre total NT sera égal au nombre de stations Ns multiplié par leur nombre par station Nc NT = xs x Nc 11- La durée des phases d'allocation est variable, sa valeur maximum
A max étant fonction de NT et de l'écart minimum Z entre deux tempo-
risations. Sa valeur minimum A min doit être supérieure à Z et sa valeur moyenne est A max + A min Calcul de-l'écart Z La Fig. 10 représente trois stations 11, lp, et 1N, 1N étant la station extrême reliée au bus ARBITRE 5. La station 11 émet et les stations lp et 1N sont en attente de pouvoir émettre. La propagation des signaux sur le bus se fait à une vitesse O donnée, égale par exemple à 5 ns par mètre. La distance 11 à 1p est t et le temps de propagation est r=/6 La distance de lp à 1N est L et le temps de propagation est
R = L/O
La Fig. 11, ligne a représente l'instant de libération du bus ARBITRE par la station 11. La Fig. 11, lignes b et c montrentles instants
de test en lp et en 1N en supposant la vitesse de propagation infinie.
Le délai de temporisation de 1p est de (n+1) Z et le délai de tempo-
risation de 1N est nZ. Le délai de temporisation de 1p étant plus grand
que celui de 1N, le conflit d'accès se règle en faveur de lp.
La Fig. 11, lignes d et e tiennent compte de la vitesse de propa-
gation finie et montrent respectivement le tests de 1p à l'instant tp = T + r + (n+1) Z et le test de 1N à l'instant tN = T + r + R + nE Le test de lp parviendra à 1N à l'instant t'p= T + r + R + (n+1)E et le test de 1N parviendra à lp à l'instant t'N = T + r + 2R + nE L'allocateur de 1p comparera tp et t'N et l'allocateur de IN comparera tN et t'p et pour que le conflit soit réglé en faveur de 1p qui a la plus longue temporisation, il faut en 1p tp > t'N Et en 1iN t'p> tN
- 12 -
la seconde équation est toujours vérifiée. Le premier donne r > 2R Si Z est inférieur à 2R, on peut avoir selon le signe de Z, un règlement de conflit en faveur de ip voire un règlement du conflit au détriment des deux stations 1pet 1,qui se retirent toutes deux. Fonctionnement des arbitres Si dans le principe de résolution des conflits, les arbitres demandeurs et serveurs sont identiques, il diffèrent sur quelques points: les conditions d'autorisation liées aux états des bus ARBITRE et OCCUPATION et le fait que l'un mémorise l'état candidat et l'autre non. 1. Arbitre "demandeurs" (Fig. 8) Dès qu'elle est candidate demanderesse, une station émet sur
sa borne 320 un signal ACTIVATION qui est mémorisé dans la bascule 3015.
Plusieurs possibilités se présentent: 1,1. le bus ARBITRE 5 et le bus d'OCCUPATION 6 sont tous deux
libres -
1,11. le détecteur d'ARBITRE LIBRE 3001 génère un signal S1 qui, à travers la porte OU 3002 et la porte ET3903 provoque le marquage du BUS ARBITRE 5 par l'intermédiaire de la bascule 3004. Un
signal S3 également généré par le détecteur d'arbitre libre 3001 dé-
clenche à travers la porte OU 3005,le fil 3010, la porte OU 307 et le
fil 310 la temporisation d'arbitrage par l'intermédiaire du signal DEPART.
Cette temporisation achevée, le décompteur 302 génère un signal TEST mémorisé dans la bascule 3006. Le signal TEST démarque également la bascule 3004 à travers la porte OU 3007 et active un comparateur 3008
dont le rôle est de comparer l'état de 3004 avec l'état du bus ARBITRE 5.
Deux possibilités: 1,111. Il y a une différence signalée par le signal REJET. Ceci
signifie qu'une station plus prioritaire maintient le BUS ARBITRE à 1.
Le signal REJET remet 3006 au repos à travers la porte OU 3009 et génère
à travers la porte OU 3011 un signal PRISE vers le générateur de tem-
porisations 300 dont le rôle est de puiser au hasard une temporisation
d'arbitrage dans le champ de codes binaires 303.
1,112. Il n'y a pas de différence; le comparateur génère le signal OK signifiant que le bus ARBITRE 5 est à O donc que l'allocateur est maître. Le signal OK est appliqué à la porte ET 3016 et donne à sa
- 13 -
sortie du signal MA signifiant que l'allocateur est maître. Le signal MA positionne la bascule 3013.à 1. Cet état est comparé à l'état du bus d'OCCUPATION. Deux possibilités 1,1121. Le bus d'OCCUPATION est libre: le signal ME est généré par la bascule 3013; il signifie la capture du bus de DONNEES par le fil 111. La station peut émettre son message. Le signal ME mémorisé
dans la bascule 3014 marque également l'occupation du bus OCCUPATION.
A l'issue de ses échanges avec un serveur, la station génére un signal LIBERATION qui met au repos les bascules 3004 et 3014 et par suite, les
2 bus ARBITRE 5 et OCCUPATION 6.
Le signal MARQUAGE est généré par le processeur de la station dès
que celle-ci a reçu l'accusé de réception du pré-message (Cf. Fig. 5).
1,1122. Le bus d'OCCUPATION est déjà pris: l'état maître MA est mémorisé en 3013 jusqu'à la libération du bus qui entraîne le processus
1,11121.
1,2. le bus ARBITRE 5 est libre et le bus d'OCCUPATION 6 est Lmargue 1,21. l'activation est mémorisée en 3015, rien ne se passe jusqu'à la libération du bus OCCUPATION qui va générer le signal S1 de marquage du bus ARBITRE 5 par l'intermédiaire du détecteur d'arbitre
libre 3001. Le processus se déroule ensuite comme ci-dessus.
1,3. le bus ARBITRE est occueé Dans ce cas, quelque soit l'état du bus OCCUPATION 6, il y a attente de libération du bus ARBITRE. Celle-ci va activer le dispositif détecteur de libération 3017, si à ce moment-là, le bus d'OCCUPATION est libre. Les deux signaux S2 et S4 sont générés par 3017. S2 a le même
rôle que Si, S4 ayant celui de S3.
2. Arbitre."serveur" (Fig. 9) N'ayant aucune fonction mémoire, son fonctionnement est très simple. Une station s'étant "reconnue" candidat serveur par suite du décodage de l'étiquette fonctionnelle du pré-message qu'elle vient de recevoir, fonction qu'elle est en mesure de traiter, elle active l'arbitre
serveur par le signal ACTIVATION sur la borne 323.
Plusieurs possibilités 2,1. le bus ARBITRE 5 est à 1 et le bus d'OCCUPATION 6 à O ou à 1 Rien ne se passe, le rejet est immédiat. La station abandonne sa qualité de serveur. 2,2. le bus ARBITRE 5 est à O et le bus d'OCCUPATION 6 est à O
Rien ne se passe, rejet immédiat.
2,3. le bus ARBITRE 5 est à O; le bus d'OCCUPATION 6 a 1 Les portes ET 3501 et 3502 sont passantes. La bascule 3503
marque le bus ARBITRE et le-signal DEPART (borne 310) active le géné-
rateur de temporisations d'arbitrage 300. Celui-ci génère le signal TEST (borne 311) après écoulement de la temporisation. Le signal TEST libère la bascule 3503 à travers la porte OU 3504 et active le comparateur 3505. Deux possibilités: 2,31. le bus ARBITRE est à 0. Sa capture est effective; la station devient "serveur", elle peut émettre un accusé de réception. Le comparateur 3505 remarque le bus ARBITRE aussitôt à travers la porte OU 3506. La LIBERATION sera effectuée à l'issue de la réception des données. 2,32. le bus ARBITRE reste à 1: il y a rejet, un serveur
plus prioritaire maintient le bus ARBITRE.
Dans la description qui précède, on a supposé le bus ARBITRE
et le bus OCCUPATION distincts et ayant chacun deux signaux respectivement de marquage et de démarquage; on pourrait, bien entendu, remplacer ces deux bus par un bus unique ayant quatre valeurs représentatives des
marquages et des démarquages combinés d'ARBITRAGE et d'OCCUPATION.
Claims (4)
1 - Dispositif permettant le règlement des conflits d'accès à un bus d'une pluralité de stations émettrices - réceptrices de données
comprenant chacune un processeur asynchrone et non hiérarchisé, les-
dites stations étant reliées en parallèle à un bus de TRANSlIISSIOII DE DONHEES ainsi qu'à un bus d'ARBITRAGE (5) d'accès et à un bus d'OCCUPATION (6), ce dernier étant marqué quand le bus de TRANSMISSION DE DONNEES transmet des données, caractérisé en ce que chaque station comprend, outre le processeur, une mémoire et un sélecteur de signaux de temporisation (300) ayant dans chaque station des durées différentes, des moyens de marquer (305; fil "marquage') quand la station se porte appelante le bus d'ARBITRAGE pendant un temps égal à la durée du signal de temporisation sélecté,des moyens de tester (305; fil "état") le bus d'ARBITRAGE à la fin du signal de temporisation sélecte, des moyens de prendre le contrôle du bus de TRANSMISSION DE DONNEES si le test indique la disponibilité du bus d'ARBITRAGE et des moyens de prise effective (borne 111) du bus de TRANSMISSION DE DONNEES quand le bus d'OCCUPATION
devient démarqué.
2 - Dispositif permettant le règlement des conflits d'accès à un
bus d'une pluralité de stations conforme à'la revendication 1, carac-
térisé en ce que la sélection d'un signal de temporisation par une station appelante est aléatoire et que la moyenne des durées des signaux
de temporisation d'une station est la même pour toutes les stations.
3 - Dispositif de règlement des conflits d'accès à un bus d'une pluralité de stations conforme à la revendication 1, caractérisé en ce que chaque station comprend des moyens Lécodeurs <304), borne (325j de forcer le sélecteur de signaux de temporisation sur le signal de
durée maximale.
4 - Dispositif de règlement des conflits d'accès à un bus d'une pluralité de stations conforme à la revendication 1, caractérisé en ce
que les stations sont munies de moyens de recommencer l'appel en appli-
quant le signal de temporisation sélecté au bus d'ARBITRAGE libre, un
certain délai après la libération dudit bus d'ARBITRAGE.
- 15 -
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR8019751A FR2490434B1 (fr) | 1980-09-12 | 1980-09-12 | Dispositif de resolution des conflits d'acces et d'allocation d'une liaison de type bus interconnectant un ensemble de processeurs non hierarchises |
| JP56143187A JPS5781748A (en) | 1980-09-12 | 1981-09-12 | Data transmission system for solving competitive access between transmitter and receiver for common bus |
| US06/301,837 US4467418A (en) | 1980-09-12 | 1981-09-14 | Data transmission system resolving access conflicts between transmitters-receivers to a common bus |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR8019751A FR2490434B1 (fr) | 1980-09-12 | 1980-09-12 | Dispositif de resolution des conflits d'acces et d'allocation d'une liaison de type bus interconnectant un ensemble de processeurs non hierarchises |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| FR2490434A1 true FR2490434A1 (fr) | 1982-03-19 |
| FR2490434B1 FR2490434B1 (fr) | 1988-03-18 |
Family
ID=9245889
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| FR8019751A Expired FR2490434B1 (fr) | 1980-09-12 | 1980-09-12 | Dispositif de resolution des conflits d'acces et d'allocation d'une liaison de type bus interconnectant un ensemble de processeurs non hierarchises |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US4467418A (fr) |
| JP (1) | JPS5781748A (fr) |
| FR (1) | FR2490434B1 (fr) |
Families Citing this family (27)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5142689A (en) * | 1982-09-27 | 1992-08-25 | Siemens Nixdort Informationssysteme Ag | Process for the preparation of the connection of one of several data processor devices to a centrally synchronized multiple line system |
| US4559595A (en) * | 1982-12-27 | 1985-12-17 | Honeywell Information Systems Inc. | Distributed priority network logic for allowing a low priority unit to reside in a high priority position |
| US4763249A (en) * | 1983-09-22 | 1988-08-09 | Digital Equipment Corporation | Bus device for use in a computer system having a synchronous bus |
| DE3482810D1 (de) * | 1983-09-27 | 1990-08-30 | Trw Inc | Multi-master-uebertragungsbus. |
| US4736319A (en) * | 1985-05-15 | 1988-04-05 | International Business Machines Corp. | Interrupt mechanism for multiprocessing system having a plurality of interrupt lines in both a global bus and cell buses |
| US4757446A (en) * | 1986-04-01 | 1988-07-12 | Wang Laboratories, Inc. | High-speed link for connecting peer systems |
| JPS63118856A (ja) * | 1986-11-06 | 1988-05-23 | Nec Corp | シリアル・バス・インタフエ−ス回路 |
| US5109329A (en) * | 1987-02-06 | 1992-04-28 | At&T Bell Laboratories | Multiprocessing method and arrangement |
| US5142682A (en) * | 1987-03-26 | 1992-08-25 | Bull Hn Information Systems Inc. | Two-level priority arbiter generating a request to the second level before first-level arbitration is completed |
| US5193197A (en) * | 1987-09-24 | 1993-03-09 | Digital Equipment Corporation | Apparatus and method for distributed dynamic priority arbitration for access to a shared resource |
| US5179669A (en) * | 1988-08-22 | 1993-01-12 | At&T Bell Laboratories | Multiprocessor interconnection and access arbitration arrangement |
| JPH02117242A (ja) * | 1988-10-27 | 1990-05-01 | Toshiba Corp | パケット通信装置のバス制御方式 |
| US5081578A (en) * | 1989-11-03 | 1992-01-14 | Ncr Corporation | Arbitration apparatus for a parallel bus |
| US5263163A (en) * | 1990-01-19 | 1993-11-16 | Codex Corporation | Arbitration among multiple users of a shared resource |
| KR920001351A (ko) * | 1990-06-30 | 1992-01-30 | 이헌조 | Id 처리전용 scsi 버스 인터페이스 로직 |
| AU630299B2 (en) * | 1990-07-10 | 1992-10-22 | Fujitsu Limited | A data gathering/scattering system in a parallel computer |
| US5204864A (en) * | 1990-08-16 | 1993-04-20 | Westinghouse Electric Corp. | Multiprocessor bus debugger |
| JP2511588B2 (ja) * | 1990-09-03 | 1996-06-26 | インターナショナル・ビジネス・マシーンズ・コーポレイション | デ―タ処理ネットワ―ク、ロックを獲得させる方法及び直列化装置 |
| GB2251099B (en) * | 1990-12-19 | 1994-08-03 | Motorola Inc | Bus system |
| US5689657A (en) * | 1991-03-30 | 1997-11-18 | Deutsche Itt Industries Gmbh | Apparatus and methods for bus arbitration in a multimaster system |
| US5953510A (en) * | 1991-09-05 | 1999-09-14 | International Business Machines Corporation | Bidirectional data bus reservation priority controls having token logic |
| US5301283A (en) * | 1992-04-16 | 1994-04-05 | Digital Equipment Corporation | Dynamic arbitration for system bus control in multiprocessor data processing system |
| DE69327825T2 (de) * | 1992-08-10 | 2000-10-12 | Lucent Technologies Inc., Murray Hill | Funkübertragungssystem und Funkbasisstation zur Verwendung in einem derartigen System |
| US5754803A (en) * | 1996-06-27 | 1998-05-19 | Interdigital Technology Corporation | Parallel packetized intermodule arbitrated high speed control and data bus |
| US6467006B1 (en) * | 1999-07-09 | 2002-10-15 | Pmc-Sierra, Inc. | Topology-independent priority arbitration for stackable frame switches |
| SE516758C2 (sv) * | 2000-12-22 | 2002-02-26 | Ericsson Telefon Ab L M | Digitalt bussystem |
| CN105404599B (zh) * | 2015-10-29 | 2018-05-29 | 南车株洲电力机车研究所有限公司 | 一种总线访问出错保护方法 |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0007185A1 (fr) * | 1978-06-19 | 1980-01-23 | Am International Incorporated | Dispositif de contrôle et d'enregistrement pour des machines à copier |
Family Cites Families (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3699529A (en) * | 1971-01-07 | 1972-10-17 | Rca Corp | Communication among computers |
| US3886524A (en) * | 1973-10-18 | 1975-05-27 | Texas Instruments Inc | Asynchronous communication bus |
| US4228496A (en) * | 1976-09-07 | 1980-10-14 | Tandem Computers Incorporated | Multiprocessor system |
| US4096571A (en) * | 1976-09-08 | 1978-06-20 | Codex Corporation | System for resolving memory access conflicts among processors and minimizing processor waiting times for access to memory by comparing waiting times and breaking ties by an arbitrary priority ranking |
| US4148011A (en) * | 1977-06-06 | 1979-04-03 | General Automation, Inc. | Asynchronous priority circuit for controlling access to a bus |
| US4363094A (en) * | 1977-12-29 | 1982-12-07 | M/A-COM DDC, Inc. | Communications processor |
| US4229791A (en) * | 1978-10-25 | 1980-10-21 | Digital Equipment Corporation | Distributed arbitration circuitry for data processing system |
| US4237534A (en) * | 1978-11-13 | 1980-12-02 | Motorola, Inc. | Bus arbiter |
| US4281380A (en) * | 1978-12-27 | 1981-07-28 | Harris Corporation | Bus collision avoidance system for distributed network data processing communications system |
| US4281381A (en) * | 1979-05-14 | 1981-07-28 | Bell Telephone Laboratories, Incorporated | Distributed first-come first-served bus allocation apparatus |
| US4313196A (en) * | 1979-12-28 | 1982-01-26 | International Business Machines Corp. | Priority system with low speed request bus |
| US4374413A (en) * | 1980-06-26 | 1983-02-15 | Gte Automatic Electric Labs Inc. | Arbitration controller providing for access of a common resource by a plurality of central processing units |
-
1980
- 1980-09-12 FR FR8019751A patent/FR2490434B1/fr not_active Expired
-
1981
- 1981-09-12 JP JP56143187A patent/JPS5781748A/ja active Pending
- 1981-09-14 US US06/301,837 patent/US4467418A/en not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0007185A1 (fr) * | 1978-06-19 | 1980-01-23 | Am International Incorporated | Dispositif de contrôle et d'enregistrement pour des machines à copier |
Non-Patent Citations (1)
| Title |
|---|
| EXBK/80 * |
Also Published As
| Publication number | Publication date |
|---|---|
| US4467418A (en) | 1984-08-21 |
| FR2490434B1 (fr) | 1988-03-18 |
| JPS5781748A (en) | 1982-05-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| FR2490434A1 (fr) | Dispositif de resolution des conflits d'acces et d'allocation d'une liaison de type bus interconnectant un ensemble de processeurs non hierarchises | |
| EP1701274B1 (fr) | Architecture de noeud de communication dans un système de réseau sur puce globalement asynchrone | |
| FR2519443A1 (fr) | Systeme d'attribution de l'acces a une ressource utilisee en mode partage a la demande | |
| FR2588679A1 (fr) | Dispositif d'arbitrage et procede pour autoriser l'acces a une ressource de traitement de donnees, utilisant un tel dispositif | |
| FR2579342A1 (fr) | Reseau local de transmission de donnees et procede d'affectation automatique d'adresses a des dispositifs de traitement de donnees de ce reseau | |
| FR2758681A1 (fr) | Allocation a une pluralite d'elements d'autorisations d'acces a une ressource partagee | |
| EP0062960B1 (fr) | Procédé de gestion de l'émission-réception de données dans un réseau local de communication et système de transmission de données pour l'application du procédé | |
| FR2517442A1 (fr) | Dispositif d'interruption pour un systeme de multitraitement, procede pour sa commande et systeme pour sa mise en oeuvre | |
| FR2519441A1 (fr) | Systeme de selection de priorite pour l'acces a un bus utilise en mode partage | |
| EP0094717A2 (fr) | Procédé et dispositif d'allocation déterministe explicite du jeton dans un réseau local distribué de transmission avec priorités | |
| EP0005722A1 (fr) | Système de sélection de circuit d'interface prioritaire | |
| EP0917062B1 (fr) | Dispositif d'échange entre unités de traitement d'informations à processeurs interconnectés par un bus commun | |
| CA1209712A (fr) | Procede et installation de transmission de donnees numeriques | |
| FR2725811A1 (fr) | Appareil et procede pour systeme de reservation de memoire tampon | |
| EP3709178A1 (fr) | Procédé de gestion d'accès à un bus informatique partagé, et dispositif électronique correspondant | |
| FR3086426A1 (fr) | Gestionnaire de verrous pour architecture multicoeurs | |
| US7710904B2 (en) | Ring network with variable token activation | |
| US11405766B2 (en) | Connecting computer processing systems and transmitting data | |
| US11357020B2 (en) | Connecting computer processing systems and transmitting data | |
| EP0376249A1 (fr) | Procédé de déblocage d'un système multiprocesseurs multibus | |
| EP1871058B1 (fr) | Système et procédé de gestion de messages transmis dans un réseau d'interconnexions. | |
| US20210250425A1 (en) | Connecting computer processing systems and transmitting data | |
| EP0018617A1 (fr) | Système d'échange de messages codés entre stations | |
| US11271838B2 (en) | Timing synchronization | |
| EP2965214A1 (fr) | Procede de surveillance de communications pour systeme sur puce |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| TP | Transmission of property | ||
| ST | Notification of lapse |