Brevet FR2482746A1 — publié le 19811120

ARRIERE-PLAN DE L'INVENTION. La présente invention concerne un système de macb1ne à calculer à multiprocesseur pour l'exécution d'un algorithme divisible, en particulier d'un algorithme récursif, sur des données d'entrée, comportant une classification remplie au moins en grande partie selon n colonnes (n 2) et p rangées (p % 2) de modules machine. Un tel algorithme est réalisé dans une procédure récursive. Une procédure P {.xi, yj}, qui opère sur des grandeurs d'entrée (xo... xi) en vue de produire des grandeurs de sortie (yo... yj) est qualifiée de récursive lorsque, dans le corps de la procédure, cette même procédure est à nouveau appelée, par exemple sous la forme de P tx (i-m), yk} ou (i - m) O. L'exécution de cette procédure ainsi appelée peut souvent former une tc]le partielle de structure plus simple qui forme alors une partie du résultat de l'algorithme initial. L'appel de la procédure peut s'effectuer deux fois ou plus de deux fois dans une même procédure de sorte que- la tâche qu'elle doit effectuer est divisée en un certain nombre de tâches partielles. Cette division peut se produire plusieurs fois consécutivement jusqu'à ce que finalement une ou plusieurs tâches partielles élémentaires soient formées et exécutées, et que leur résultat puisse être utilisé dans un stade précédent de la série de divisions et ainsi de suite pour revenir à la présentation de l'algorithme initial. Il s'avère que de nombreux algorithmes peuvent être divisés avantageusement en tâches partielles. La division suivante est donnée à titre d'exemple: n (n)ni,J't1 (n(n- (k) (n-k), k!: (n-l) + k _ l) Il est clair que la division peut être effectuée à condition que k > 1 (auquel il est toujours implicite que n k) . D'autres algorithmes de nature récursive sonôt par exemple: les multiplications matricielles et les mécanismes de triage. La division en tâches partielles peut souvent s'effectuer selon une division par deux produisant chaque fois une ramification. L'exécution est accélérée lorsqu'un processeur réservé est présent pour chaque tâche partielle élémentaire. Il est alors défavorable que le nombre de processeurs nécessaire soit très grand parce que ce nombre doit être adapté à la forme la plus dévelloppée de l'algorithme (dans l'exemple qui précède, il est donc déterminé notamment par la plus grande valeur admissible de n). Parallèlernent à ceci surgit une difficulté qui est due au fait que, pour un réseau se ramifiant de manibre exponentielle, les trajets de liaison entre les processeurs peuvent devenir excessive- ment longs et que la classification peut présenter un manque d'hbmogénéité important par exemple sur un support plat: le nombre de processeurs augmente en effet de manière exponentielle dans les couches succes- sves du motif de ramification. RESUME DE L'INVENTION. L'invention a pour but de fournir, dans l'optique du problème décrit plus haut, une classification pour un système d- machine à calculer à multiprocesseur qui présente les avantages suivants: une tâche d'un algorithme à exécuter dans un processeur peut y être divisée en deux ou plus de deux tâches partielles (pour le même algorithme) qui peuvent être envoyées chacune à un autre processeur respectif en rue de la poursuite du calcul tandis que le résultat final ainsi finalement formé peut être ramené au processeur initial, le nombre total de tâches partielles ainsi formées ne devant pas satisfaire à une limitation qui est provoquée par le nombre limité de processeurs ou de modules machine dans la classification: à priori, un arbre binaire infini peut être représenté sur la classification, tandis que des moyens sont aussi présents pour s'opposer à une accumulation de tâches dans un seul module machine. L'invention réalise ces buts par le fait qu'elle est caractérisée en ce que chaque module comporte: a) une première connexion de source (COML) pour la réception d'un premier signal d'activation avec un signal paramétrique annexé pour un algorithme et l'émission d'un signal de résultat de cet algorithme; b) une deuxième connexion de source (COMU) pour la réception d'un deuxième signal d'activation avec un signal paramétrique annexé pour un algorithme. et l'émission d'un signal de résultat de cet algorithme; c) un élément mémoire pour le stockage de signaux de programme d'au moins une procédure pouvant être activée sélectivement par un signal d'activation pour diviser la tâche d'un algorithme divisible associé en deux tâches partielles et de combiner les résultats des tâches partielles, à la réception de ceux-ci, sous la forme du résultat de la dite tâche, ou pour exécuter une tâche partielle élémentaire du-dit algorithme; - d) un élément processeur pour recevoir les dits signaux de programme et les signaux paramétriques et, en alternance, soit formercles dites tâches partielles soit combiner les résultats reçus, et exécuter la dite tâche partielle élémentaire et produire un signal de résultat; e) une première connexion de but (COMR) pour l'émissions d'un troisième signal d'activation avec un signal paramétrique annexé d'une première tâche-partielle ainsi formée du dit algorithme et pour la réception. d'un signal de résultat de cette première tâche partielle; f) une deuxième connexion de but (COMD) pour l'émission d'un quatrième signal d'activation avec un signal para- métrique annexé d'une deuxième tâche partielle du dit _ 4 _ algorithme formée en même temps que la dite première tâche partielle et pour la réception d'un signal de résultat de cette deuxième tâche partielle; étant entendu qu'au moins un module machine comporte, à titre de module d'accès de l'ensemble de la classi- fication, une autre connexion de source pour la réception d'un signal d'activation externe avec un signal para- métrique annexé pour un algorithme et la fourniture d'un signal de résultat de cet algorithme; les modules machine étant connectés par leur première connexion de but à ia première connexion de source dul module machine voisin le plus proche sur la même rangée, et tous les derniers modules machine des rangées sont chaque fois connectés au premier module machine d'une rangée correspondante et inversement, les mnodules machine étant connectés par]leur deuxième connexion de but à la deuxième connexion de source du module machine le plus proche de la même colonne et tous les derniers modules machine des colonnes sont connectés chaque fois au premier module machine d'une colonne correspondante et inversement. Un tel arbre binaire est connu dans la théorie des graphes (graph theory) qui est une théorie consacrée. Les fonctions de la division de la tâche d'un algorithme en tâches partielles et de]a combinaison des résultats des tâches partielles en un résultat de l'algorithme sont exécutées chaque fois dans un module machine: l'exécution de ce processus signifie la mise en oeuvre à cet endroit d'un noeud de l'arbre (binaire ou d'ordre plus élevé). Par la constitution décrite de la classification des modules machine et le couplage en boucle des connexions de but et des connexions de source, on peut projeter un arbre de dimension quel- conque sur la classification. Chaque module machine peut alors recueillir un certain nombre de noeuds. Ce nombre n'est limité que par le fait qu'un module machine - 5 - 2482746 _ 5 _ d présente une certaine capacité de mémoire finie. Les noeuds mis en oeuvre dans un module machine peuvent être "actifs" ou "non actifs". Dans un module machine simple, au maximum un noeud sera toujours actif. La classification peut comprendre nxp modules machine mniais aussi un nombre moins élevé. Ce dernier cas peut se présenter par exemple lorsqu'un module machine n'est plus en état de fonctionner; dans ce cas, la communica- tion est établie directement avec le module suivant à condition que les connexionis en question soient présentes. Un module machine déterminé peut aussi ne pas être mis en oeuvre, par exemple par manque de place sur un support à câblage imprimé. Il est aussi possible de loger un certain nombre de modules machine ou même tous les modules machine de la classification dans un seul circuit intégré. Dans une classification o n = p = 4 un ou deux modules par exemple peuvent alors être absents ou défectueux. Cependant, lorsque ]la classification devient moins coinplète la répartition O0 des tâches devient aussi moins favorable. Par le terme "classification", on entend dans ce qui précède une classification fonctionnelle. L'agencement géométrique peut être choisi différemment. Il est avantageux que les derniers modules machine des rangées (1.... p) soient connectés chaque fois par leur première connexion de but à la Première connexion de source des premiers modules machine des rangées (j+ l, j+2... p, 1,... j), et que les derniers modules machine des colonnes (1, 2,... n) soient connectés par leur deuxième connexion de but chaque fois à la deuxième connexion de source des premiers modules machine des colonnes (k+l, k+2,... n, 1,... k). Ceci donne une construction plus systématique de la classi- fication par le couplage en retour organisé de manière cyclique. f -6 - Il est avantageux que la classification comprenne (nxp) modules machine, que k=o et que les nombres (p+j) et n ne possèdent pas de facteur commun. Il s'avère que la représentation du graphe sur la classi- fication de modules machine devient aloi.s très systé- matique. Dans de nombreux algorithmes, certaines tâches partielles se répètent avec les mmines valeurs para- n-1. ,1 2, ,-,_D 2 inètriques. Ainsi (n) = d.(: = ( 'tk- /- k '+2'k-lJ'k2' Selon cette réalisation de la classification, le terme "médian" de la partie de droite ne doit être calculé que dans un seul module machine. D'une manière corres- pondante, la tâche partielle ne doit être exécutée qu'une fois pour chaque paire de valeurs (k) Cepen- dant, une constructiop systématique de la classifi- cation est aussi tras utile pour l'exécution d'autres algorithmes. Il est avantageux que p = n. Ceci donne une construction compacte de la classification. Il est avantageux que chaque module machine comprenne des moyens permettant d'exécuter séparément un processus central et chaque fois un processus de canal pour chacunrdes dites connexions de celui-ci et de faire communiquer en outre le processus central exclusivement avec les processus de canaux du module en question, les processus de canaux assurant complète- ment la communication entre les divers modules machine et la division de la tâche, la combinaison des résultats des tâches partielles ou l'exécution d'une tâche partielle élémentaire étant entièrement assurée par le processus central. Une telle construction permet de séparer facilement le traitement (division, recom- binaison, exécution d'une tâche partielle élémentaire) des processus de communication entre différents modules machine. Un module machine peut par exemple maintenant aussi recevoir un message pour un noeud qui, à un _ 7 _ 4 certain moment, n'est précisément pas actif, sans que le noeud en cours d'exécution à cet endroit par le processus central soit perturbé. L'exécution dans un seul processeur de différents processus est en ellemême bien connue. Il est avantageux que des moyens soent présents dans chaque module machine pour adjoindre à un message qui y est formé par un processus central, une indication présentant une première valeur qui indique que le message sert exclusivement de message de quantité pour le noeud actif dans un module machine récepteur et une deuxième valeur qui indique que le message sert exclusivement de message d'activation pour un noeud identifié dans un module machine récep- teur au moyen d'une indication contenue dans le corps du message. Ceci donne une organisation simple de messages de quantité; par le terme "quantité", on entend une doiinée qui est nécessaire pour la poursuite de l'exécution dlun programme d'un noeud. Ainsi, un message de quantité peut être transmis directement vers la mémoire du module machine (le noeud en question est en effet actif) et aucun tamponnage du message n'est nécessaire. D'autre part,- un noeud non actif peut aussi facilement être activé de cette façon. L'activation proprement dite d'un noeud est effectuée par le processus central du module machine récepteur. Il est avantageux que, sous la commande de la dite première valeur, un chemin de communication soit ouvert entre deux parties des mémoires des modules machine associés attribuées à ce moment à deux noeuds qui communiquent. Ceci donrme une communication rapide dans laquelle il n'y a pas de risque de congestion-en raison de deux ou de plus de deux trajets de message en conflit. Ceci constitue pour ainsi dire une géné- ralisation du mécanisme d'empilage" (stack). -8- Il est avantageux que de tels processus de canaux couplés soient chacun pourvus: g) de premiers moyens de signaux (P(x)) pour, au moyen d'une première position, pour chaque connexion précitée vers un autre module machine, signaler une émission ou une réception souhaitée d'un message suivant cette connexion par le dit premier module machine, une deuxième -position servant, i l'exclusion d'autres positions après l'achèvement de la dite émission ou de la dite réception, de position de repos; h) des deuxièmes moyens de signaux (Q(x)) présentant une premiere position pour, dans le cas d'une émission souhaitée par un autre module machine suivant cette connexion, après que la première position des dits premiers moyens de signaux y ait été formée, être amenés eux-mêmes dans cette première position et une deuxième position qui, après détection de la première position mentionnée en dernier lieu, opère alors comme position active et pour, dans le cas d'une réception souhaitée par un autre module machine suivant cette connexion après que la dite position active mentionnée en dernier lieu ait été formée, par l'autre module, être amenés eux-mêmes ainsi dans la première position, la deuxième position servant de position de repos au terme de la dite réception. Ceci donne une procédure de-communication sûre. COURTE DESCRIPTION DES FIGURES.- Une forme d'exécution préférée de l'invention sera décrite ci-après et plus spécialement, dans l'ordre: la structure du réseau, la coopération fonctionnelle entre les modules machine, la structure d'un module standard et du module d'accès et l'organisation d'un module au point de vue programme. Cette description est donnée avec référence aux dessins annexés dans lesquels: -- 9 _- la Fig. 1 illustre un réseau de 3x4 modules machine; les Fig. 2a, 2b, 2c illustrent trois autres réseaux de modulE machine; la Fig. 3 illustre un motif de division des taches d'un algorithme en tâches partielles; la Fig. 4 illustre l'ordre de succession des fonctions d'un modul machine; la Fig. 5 illustre, pour les Fig. 1 et 3, un état d'activation possible des moaules; la Fig. 6 illustre, pour les Fig. 2 et 3, un état d'activation possible des modules; la Fig. 7 est un schéma synoptique de la réalisa- tion d'un module machine; la Fig. 8 illustre un développement de la Fig. 7 en vue de la rdalisation d'un module d'accès; la Fig. 9 est un tableau de marche pour un module machine émetteur lors d'une opération de comnun5 cation; la Fig. 10 est un tableau de marche pour un module machine récepteur, et les Fig. lia à 11f indiquent plusieurs opérations partielles d'un module machine dans un-langage de programmation sulpérieur. LA STRUCTURE DU RESEAU DE MODULES MACHINE. La Fig. 1 illustre un réseau de 3x4 modules machine. Il est avantageux que les chiffres 3 et 4 soient des nombres premiers entre eux. Un module machine quelconque, dans ce cas-ci de module "00" fonctionne comme module d'accès et possède à cet effet une connexion de source 100 pour la réception d'un signal d'activation extérieur avec un signal paramétrique annexé pour un algorithme. Dans le réseau représenté aux dessins, le module 00 comporte deux connexions de but qui sont connectées respectivement chaque fois f -10 - à une connexion de source des modules "01" et "10". Le module "01" comporte deux connexions de but qui sont chacune respectivement connectées à une connexion de source des deux modules "02" et "11". Le module "22" comporte deux connexions de but qui sont connectées chaque fois à une connexion de source des modules "23" et "02" respectifs et ainsi de suite. Dans le module "O", la tâche de l'algorithme en question peut être divisée d'une manière décrite plus en détail plus loin en deux tâches partielles afférant au même algorithme, à moins que la tâche initiale ait un caractère élémentaire et soit ainsi indivisible. Ce caractère élémentaire est déterminé par la valeur du signal paramétrique (ou des signaux paramétriques) en s15 vigueur à cet endroit. Lorsque la tâche est cependant divisible, un signal. d'activation pour la tâche partielle avec un signal par-ramétrique annexé du module "00" sont chaque fois amnenés respectivement aux modules "10" et "01" pour y être traités de la même manière que -20 l'algorithme initial dans le module "00". Le module peut donc activer les modules 20 et 11, le module 01, les modules 11 et 02, et ainsi de suite. Lorsqu'une tâche partielle élémentaire est activée, elle est exécutde et son signal de résultat est renvoyé vers le module machine o la tâche partieile a été formée pour être combiné avec le résultat d'autres tâches partielles éventuelles. Finalement, le résultat de la tâche de l'algorithme initial apparaît dans le module machine "00" pour pouvoir êire fourni au monde exté- rieur. Ce monde extérieur peut être réalisé par exemple par une machine à calculer dont le dispositif représenté sur la Fig. 1 forme une extension spéciale. La Fig. 2 illustre un réseau de 4x4 modules machine. Le couplage en retour ou par réaction des modules machine d'une rangée s'effectue de la même 2L /46 - ll - manière que sur la Fig. 1. Les colonnes sont cependant couplées en boucle avec un décalage de sorte que le module 32 est connecté par exemple au module 01. Il s'agit là d'un couplage en boucle avantageux lorsque les nombres de rangées et de colonnes de la classi- fication sont égaux ou lorsque ces nombres ont un facteur commun, comme décrit avec référence à la Fig. 6. Si les colonnes sont numérotées par ordre croissant de la droite vers la gauche, la deuxième connexion de but du dernier module machine des colonnes 1, 2,... n est chaque fois connectée à la dernière connexion de source du premier module machine succes- sivemennt des colonnes k+1... n, 1... k. Dans ce cas-ci, la valeur de n est alors égale à 4 et celle de k à 1. Un tel décalage peut:ussi être réalisé entre les raingées et aussi pour des rangées et des colonnes simultanément. Les structures des Fig. 1 et 2 correspondent d'une manière topologique à un tore: sur une telle surface finie, des lignes infinies peuvent être pro- jetées dans deux directions sans qu'un pôle se forme quelque part (comme dans le cas d'une boule). Un tel pôle o se rejoignent donc de nombreuses connexions, provoquerait facilement de la congestion. Les réseaux représentés sur les Fig. 1 et 2 peuvent comporter d'autres nombres de rangées et de colonnes; plusieurs modules d'accès peuvent aussi être présents. En outre certains modules machine peuvent être absents. Lorsque, sur la Fig. 1 par exemple le module machine 12 est absent, les modules machine 11/13 ou 02/22 peuvent être directement connectés l'un à l'autre. Si le module 23 est absent, les deux connexions de but des modules 22 et 13 doivent être couplées en boucle. Dans certains cas, le couplage en boucle des modules péri- - 12 - phériques peut s'effectuer d'une manière moins systématique, par exemple d'une façon telle que sur la Fig. 1, les paires de modules 00/03, 10/23 et /13 soient interconnectées. L'interconnexion systé- matique assure cependant fréquemment une répartition plus uniforme de la charge des tâches (partielles) sur le réseau de modules. La Fig. 2b illustre un réseau de 28 modules machine. Chaque module a trois connexions dans le réseau qui sont toutes utilisables dans deux direc- tions: elles peuvent servir aussi bien de connexion de source que de connexion de but. Lorsqu'un module machine reçoit une tâche, celle-ci est, si nécessaire, divisée en tâches partielles; les tâches partielles sont transmises par les deux connexions autres que celle par laquelle la tâche initiale avait été reçue. Les chiffres indiquent les niveaux du modèle de division. La tâche initiale est indiquée par "1", les niveaux successifs par 2, 3... etc. Il est clair qu'à chaque niveau suivant plusieurs modules machine sont mis en-oeuvre (jusqu'à ce qu'au niveau "9" ils soient - tous mis en oeuvre).. La Fig. 2c illustre un autre réseau de 28 modules machine. Chaque module présente trois connexions. Les connexions aux rangées fonctionnent dans une seule direction. Les connexions aux colonnes fonctionnent dans deux directions. Lorsqu'un module machine reçoit une tâche, celle-ci est divisée, si nécessaire; les tâches partielles sont alors expédiées par les deux connexions de but disponibles. Les chiffres indiquent à nouveau les niveaux dans le modèle de division. L'augmentation du nombre de modules machine qui mis en oeuvre à chaque niveau suivant est dans ce cas plus lente que dans le cas de la Fig. 2b. LA COOPERATION FONCTIONNELLE ENTRE LES MODULES MACHINE. _ 13 _ La Fig. 3 illustre un modèle de division pour un algorithme et en particulier l'algorithme déjà mentionné à titre d'exemple pour le calcul de (n). On suppose qu'il y a deux sortes d'algorithmes partiels élémentaires à savoir ceux servant à déter- miner (j) et (j). Il est bien entendu aussi possible de traiter (l) encore davantage en algorithmes partiels divisés. Les algorithmes partiels pour (5), (4) et (3) se retrouvent deux fois dans cet arbre, de sorte que O10 les résultats doivent aussi être utilisés deux fois pour un traitement dans un algorithme partiel de plus haut rang. Sur la Fig. 1, il est par exemple possible que le module 00 effectue la division (7), le module 10 la division (6), le module 20 la division 1 (5) et le module 00 à nouveau la division (4) de sorte qu'à ce moment, dans le module 00, deux noeuds de l'arbre binaire sont réalisds. Dans de nombreux cas, î 4 pendant la division (3), le noeud précédent se trouvera dans un état d'attente. Sous ce rapport, la Fig. 4 illustre un exemple d'une succession des fonctions à exécuter dans un module machine pour un algorithme déterminé. A gauche dans ce diagramme de temps (pour A), le module machine n'est pas actif. A un certain moment, un signal d'activation est reçu et, à. la suite de ce signal, le noeud en question est appelé à la vie (A). Ceci signifie que dans le module machine, une certaine quantité d'espace de mémoire est réservée par exemple pour des variables d'état du noeud des bits de signaux pour la commande de la communication, des résultats intermédiaires. Pendant, les parties indiquées par A, dans le module machine en question, un autre noeud, pour autant qu'il soit présent, peut chaque fois devenir actif en lieu et place de celui pour lequel la procédure est ici illustrée. Le A signi- fie donc simplement que lenoeud en question peut être t activé. Ensuite, en R sont reçus un ou plusieurs signaux paramétriques et si nécessaire un signal d'identification pour l'algorithme, lorsque plusieurs algorithmes différents sont préprogrammés dans le module machine en question. I1 n'est en soi pas nécessaire que cette réception soit réalisée comme une opération indivisible mais elle peut aussi être réalisée en plusieurs parties, auquel cas, dans un intervalle de temps intermédiaire, un autre noeud o peut y devenir actif. Dans le système représenté sur la Fig. 3, un noeud qui doit ainsi être réalisé, peut être appelé A la vie pour ainsi dire "doublement" chaque fois par deux noeuds du rang supérieur suivant. Dans ce cas, la première opération de réception est donc double. Les noeuds respectifs ne doivent pas fonctionner de manière synchrone et la r6cepttion des signaux paramétriques associés peut s'effectuer dans une partie quelconque de la procédure ultérieure. -Apres la première réception, un intervalle de repos peut à nouveau se présenter. Une partie de l'algorithme est alors exécutée, notanmment la partie o la tâche de l'algorithme est divisée en deux tâches partieles (P). Un signal d'activation avec un signal paramétrique annexé est ensuite transmis (S, S) chaque fois à deux noeuds du rang inférieur suivant. Suit alors un plus long intervalle dans lequel des noeuds de rangs inférieurs exécutent les taches partielles, éventuellement à l'aide d'autres divisions (A). Arrivent ensuite les résultats des tâches partielles dans le noeud en question, (R, R), éventuellement séparés par un intervalle A plus long que celui indiqué ici parce que les noeuds activés ensuite ne fonctionnent à nouveau plus de manière synchrone ou parce que les modules machine activés ensuite doivent exécuter des quantités d'opérations différentes. Dans l'inter- - 15 - -alle P suivant, les résultats des tâches partielles sont combinés pour produire le résultat de l'algorithme appelé initialement. Ce résultat est émis (S) vers le noeud qui a produit la tâche partielle (initiale) (il peut également s'agir à n-uveau de deux noeuds). Finalement, le noeud en question est supprimé (A) ce qui libère l'espace de mémoire réservé. Lorsque -la tâche d'un algorithme est divisée en plus de deux tâches partielles, l'ordre de succession des inter- valles P, R, S devient plus-compliqué. Pour trois parties, par exemple: RPSSSRRRPS oh R est l'opération de réception, S l'opé- ration d'émission et P l'opération de traitement. La Fig. 5 illustre pour la Fig. 1, un état ]5 d'activation possible des modules en supposant que l'exécution de la division d'une tâche nécessite chaque fois le même temps. Chaque module du système est représenté plusieurs fois (uniquement par son numéro). Les tâches de l'algorithme sont chaque fois divisées et Jes tâches partielles sont transmises aux modules qui sont adjacents au module diviseur à droite et en dessous de celui-ci. Certains modules reçoivent deux fois la même tâche qui n'est alors exécutée qu'une seule fois. De cette façon, les modules exécutent leur tâche (partielle) en respectant une synchronisa- tion réciproque. Les modules machine actifs à u:: certain moment forment ainsi une diagonale. Un exemple d'une telle diagonale est indiqué et va du module 10 à gauche en bas au module 02 à droite en haut. Onze des douze modules machine sont alors actifs simulta- nément pour exécuter les opérations appartenant à un des noeuds. Par le fait que ce nombre est relative- ment grand, le traitement peut s'effectuer relativement rapidement même pour un réseau très compliqué. Lorsque la division en tâches partielles n'est pas symétrique, - 16 le traitement prend bien entendu plus de temps parce qu'un plus grand nombre de noeuds doit être réalisé. Comme le montre la Fig. 3, le nombre total de noeuds (y compris ceux danslesquels aucune division en algorithmes partiels ne doit plus être effectuée) est égal à 14. Dans un cas asymétrique, dans lequel chaque tâche partielle doit être exécutée séparément (donc sans utilisation multiple), le nombre de tâches partielles à exécuter serait égal à: 21 (1 + 2 + 4 + 6 + 6 + 2). Au cas o une division par trois ou davantage est nécessaire, le nombre de noeuds augmente aussi en général: dans ce cas, la possibilité de combinaisons pour différents noeuds selon la - Fig. 3 peut se présenter ou non. La Fig. 6 représente un état semblable à celui de la Fig. 5, mais toutefois en rapport avec la classification de la Fig. 2. Dans cette classification également, les deux tâches partielles sont chaque fois attribuées aux modules machine qui, aux dessins, se trouvent à côté à droite ou en dessous du module dans lequel la division est effectuée. Il en cst ainsi par exemple du modal]e 33 vers les modules 02 et 30. Un motif complet des 16 modules machine est chaque fois représenté dans un bloc délimi. Dans ce cas également, exactement comme sur la Fig. 5, une diagonale de modules actifs en!mSme temps est indiquée et va du module "22" à gauche et en bas jusqu'au module "02" à droit et en haut. Cette diagonale comprend 11 modules tous différents entre eux de sorte que, dans ce cas également, lm grand nombre de modules machine peut être actif en mime temps: la vitesse de traitement est ainsi relativerment grande. L'agence- ment systématique des Fig. 1 et 2 donne donc parfois des avantages mais un autre agencement du motif d'interconnexion des modules machine aux bords peut - 1742746 aussi être avantageux. LA STRUCTURE D'UN MODULE MACHINE. La Fig. 7 illustre une forme d'exécution d'un module machine qui peut être utilisé sur la Fig. 1 pour tous les modules à l'exception du module d'accès "00". Le module comporte deux circuits intégrés, à savoir un microordinateur 300 du type INTEL 8748 ou INTEL/SIGNETICS 8048, et une mémoire vive avec un élément entrée/sortie 302 du type INTEL 8155 (INTEL lO Corp., Santa Clara, Californie, Etats-Unis d'Amérique, décrit dans l'ouvrage INTEL MCS-48 family of single- chip microcornputers-User's manual). La différence entre les deux micro-ordinateurs réside dans ce cas exclusi- vement dans le fait que le premier peut être électriquement et le deuxième ne peut pas l'être. Pour la structure et les détails de l'tensemble des instructions, on peut se référer -aussi à l'ouvrage "8048 Microcomputer User's Manual" édité par le fabricant, Signetics Corporation, 811 East Arques Av. Sunnyvale, Califorilie 94086, Etats-Unis d'Amérique en collaboration avec la Société N.V. Philips' Gloei- lampenfabrieken, Eindhoven, Pays-Bas (1978). L'élément 300 est alimenté en +5 volts sur les broches de connexion 40/26 et est connecté à la masse par les broches 20 (CSS) et 7(EA). La fréquence d'horloge interne est réglée g:r une valeur correcte par une petite bobine 304 de 47 micro,. et par deux condensateurs de 22 pF sur les bornes 2/3. Les tolé- rances de fabrication permettent à cette fréquence d'horloge de s'étendre quelque peu mais, pour le choix décrit, elle est en tout cas comprise entre les limites admissibles pour le composant en question.' De ce fait, des modules fonctionnent cependant d'une manière asynchrone les uns par rapport aux autres ce qui, comme mentionné plus haut, ne constitue pas - 18 - un inconvénient. Dans un autre agencement, tous les modules pourraient aussi fonctionner d'une manière synchrone les uns par rapport aux autres au moyen d'une horloge centrale. Un signal extérieur "0" appliqué sur la broche 4 permet de ramener les micro- ordinateurs de tous les modules machine ensemble à un état initial. Les broches 1, 5, 6, 9, 23, 24, 25 et 39 ne sont pas utilisées par le fait (non repré- senté) qu'elles portent une tension de signal fixe de "0" ou de "+l5 volts". Le micro-ordinateur est pourvu de quatre connex- ions qui lui permettent de communiquer avec d'autres modules machine à savoir COML (à gauche, broches 35, 27, 31), COMD (en bas, broches 36, 28, 32), COMR (à droite, broches 37, 29, 33) et COMU (en haut, broches 38, 30, 34). Parmi ces broches, les broches 35 à 38 incluse sont réservées au transport de dorne5es et les deux autres de chaque groupe de trois assurent i'organisation de la denture de synchronisation (handshake). Le micro-ordinateur est pourvu sur les dites broches appartenant respectivement aux "portes" 1 et 2 d'une possibilité favorable'de transport de données quasi bidirectionnel. Pour plus de concision, on peut se référer pour les détails techniques à la documentation du fabricant. Les broches 12 à 19 sont connectées au bus de données intérieur et convien- nent pour permettre la lecture ou l'enregistrement sous la commande synchronisante d'un signal sur les broches de commande de lecture-enregistrement 8/10. D'autres signaux de commande peuvent apparaître sur les broches 21, 22 pour l'élément 302. Finalement, un signal "Adress latch enable" peut apparaItre sur la broche 11 pour activer une action d'enregistrement d'adresse. Ceci est nécessaire pour pouvoir amener à l'élément 302 successivement des données d'adresse . -i -19 - et d'information. A titre d'éléments fonctionnels importants sous ce rapport, le micro-ordinateur 300 comporte une unité de traitement centrale de 8 bits, une mémoire de programme (EPROM) de lk bytes et une mémoire vive de 64 bytes. L'élément 8155 est une mémoire vive comportant en outre notamment une fonction d'entrée/sortie et présente une capacité de 256 bytes qui peuvent donc 3 être adressés par 8 bits d'adresse. Au moyen des broches 12 à 19 incluse, cet e mémoire est connectée au micro-ordinateur 300. Le signal de lecture-enregistre- ment annoncé peut gtre reçu sur lesbornes 9/10 et le signal de commande pour remplir les extracteurs d'adresse au moyen d'une adresse peut être reçu sur la borne 11. 1.5 De plus, un signal de sélection peut être reçu sur la broche 7 et permet de choisir parmi les modes de mnroire et d'entrée/sortie et un signal de retour à l'état initial peut être reçu sur la borne 4 pour activer un état initial. La broche 40 peut encore recevoir 5 volts et la-broche 20 le potentiel de masse. Les broches 37 à 39 sont réservées à la réception:d'un signal de sélection à trois bits permettant de choisir le cas échéant entre plusieurs algorithmes. Dans l'algorithme donné à titre d'exemple, on a observé que la capacité de mémoire restante était si faible qu'on a renoncé à réaliser 1lu-ieurs algorithmes différents. Pour l'extension de la capacité de mémoire, on peut se référer à la documentation du fabricant. La sélection parmi plusieurs algorithmes différents peut aussi être exécutée par voie de programme: dans ce cas, chaque message émis doit par exemple contenir une indication de l'algorithme auquel il est destiné. Dans ce cas, plusieurs algo- rithmes peuvent aussi être exécutés en même temps: en principe le premier ne doit pas être achevé avant que le second soit mis en route par amenée à un module d'accès. La broche 8 est connectée à la masse en vue d'une activation continue. Les broches 1, 2, 3, 5, 6, et 21 à 36 incluse ne sont ici pas utilisées. Le module décrit peut recevoir un signal d'activation avec un signal paramétrique annexé sur l'une des connexions COML, COMU ou sur les deux à la suite de quoi une procédure à exécuter est appelée dans la lO mémoire de programme (interne dans l'élément 300). Le module machine peut alors à nouveau envoyer un signal d'activation avec un signal paramétrique annexé sur une des connexions COMPR, CO}D ou sur les deux. Les résultats sont dirigés en sens opposé(s). LA STRUCTURE DU MODULE D'ACCES. La Fig. 8 illustre une forme d'exécution d'un module d'accès. En soi, plusieurs modules d'accès peuvent être présents. Il est possible aussi que tous les modules du réseau puissent recevoir de l'informa- tion ensemble, par exemple de l'information de programme et contiennent donc aussi certaines facilités d'accès. La Fig. 8 comprend, comme la Fig. 7, un nlicro-ordi- nateur du type 8748 ou 8048 (élément 300). Pour une grande partie des connexions, on peut se référer à la figure précédente; dans ce cas-ci, seules les modifications par rapport à cette figure sont indiquées. La capacité de la mémoire de programme du composant 300 n'est ici pas suffisante pour les fonctions d'entrée/ sortie et par conséquent, un composant 400 du type INTEL 2758 est adjoint. Il s'agit d'une némoire PROM d'une capacité de 1024 bytes rue 8 bits. Les dix bits d'adresse A. à A9 inclus peuvent être reçus sur les broches 8... 1, 22, 23. Les connexions pour les bits de données 0 à 07 inclus sont formées par les broches 9, 10, 11, 13,... 17. Les broches 21 et 24 sont counec- 21 - tées à une alimentation de 5 volts, les broches 19, 12 au potentiel terrestre. Un signal de validation peut être reçu sur les broches interconnectées 18 (CE) et 20 0E). En tant que mémoire morte, l'élément 400 ne donne que des bytes d'information au micro-ordinateur 300 et est connecté avu bus de données de la même manière que l'élément 302. Pour le stockage temporaire des huit bits d'adresse les moins significatifs, une porte d'entrée/sortie 402 du type 8212 est présente et contient des bascules. Contrai- remnent à l'élément 8155, le composant 2758 n'est pas conçu pour stocker intérieurement la totalité de l'adresse. Les broches d'entrée DI1 à DI8 sont connec- tées à la liaison de données. Les broches 2(MD), 14 (CLR) et 24 (VCC) sont connectées à un potentiel de +5 volts, les broches l(DS-1) et 12 (GND) sont connectées à la masse. Un signal de validation (Address Latch Enable, ALE) peut être reçu du micro- ordinateur sur la broche 13 (DS2). Pour le reste, la -connexion de source du module d'acces est réalisée par l'intermédiaire de l'élément 402 du type INTEL 8251 et peut ainsi être connectée au monde extérieur. Cet élément 8251 est une unité d'adaptation program- mable pour la communication. Il sert dans cet exemple notamment à permettre l'échange d'information série avec une unité dite télétype qui, pour plus de conei- sion, n'est pas représentée. Les broches 27, 289 1, 2, 5,... 8 servent au transport des données propre- ment dites. La broche 26 est connectée à une source d'alimentation de 5 volts, les broches 4 (GND), 17 (CTS) et 22 (DSR) sont connectées au potentiel de masse. La borne 10 reçoit le signal WR, la borne 13 le signal RD du micro-ordinateur 300; de plus, la borne 20 reçoit le signal d'horloge CLK qui est dérivé de la broche 1 (TO) du micro-ordinateur, la broche Il -22 - reçoit un signal de validation (Cs) qui est dérivé de la broche 38 (P 27) du micro-ordinateur, la broche 12 reçoit un signal de sélection "commande/informa- tion de données" (C/D) qui est dérivé de la broche 35 du micro-ordinateur et la broche 21 reçoit un signal de retour à l'état initial (RESET} qui est dérivé de la broche 36 (P 25) du micro-ordinateur. Aux b{oches 9 (TXC) 'et 25 (RXC) est connecté un oscillateur externe 404 du type SE555 qui détermine la fréquence de bit. Cet oscillateur est connecté de la manière représentée au moyen des résistances 406 (8, 25 kohms), 408 (39 kohms) et 410 (10 kolhms) et des condensateurs 412 (2,2 microF), 414 (8,2 nF) et 416 (o10 nF). De l'élément 402, la broche 19 (TxD) sert de sortie de donnée série et la-broche 3 (RxD) d'entrée de donnée série. Les inverseurs 418, 420 font partie d'un composant du type MC 1489A o Vcc = + 5 voltZ et GND = O volt. Le circuits-portes NON-ET 422, 426 font partie d'un composant du type SN 7438. Les autres éléments ont les valeurs suivantes: 428: 10 nF; 430: 1000 ohms; 432: 470 pF; 434: 1000 ohms; 436: 220 ohms, - W; 438: 10 microF (tantale). Les connexions 440 sont les entrées-de l'unité télétype, les connex- ions 442 les sorties vers le télétype. Pour les connexions 440, le schéma équivalent du télétype est un interrupteur marche-arrêt. Une autre solution consiste à supprimer l'inverseur 418 et à connecter la connexion inférieure de "440" à -5 volts (au lieu du potentiel de masse). Pour laconnexion 442, le schéma équivalent du télétype est une bobine. Une autre solution consiste a supprimer le composant 422 et à connecter les entrées respectives du composant 426 à la borne 19 de l'élément 402 et, par l'intermédiaire de la résistance 434, à +5 volts. Les modifications suivantes apparaissent dans ! 7Y46 - 23 le module d'accès, par rapport au circuit de la Fig 7 Darxs r élimert 300, la broche 35. ecla broche 7 de 1' élément 302 et la broche 12 de l'élément 402; la broche 36 avec la broche 21 de l'élément 402 et la broche 4 de l'élé- ment 302; la broche 37 avec la broche 8 de l'élément ,; la broche 38 avec la broche 11 de l'élément 402; les b.roches 21, 22 respectivement avec les broches 22, 23 de l'élé1ment 400; les broches 23, 24: ne sont pas utilisées. Dans l'élément 302, les broches suivantes sont utilisées d'une manière autre: la broche 25 est utilisée comme broche de donnée pour la connexion COMIL et de la même manière les broches 26, 27, 28 $ respectivement pour les connexions COMD, CO0R, COMU. Dans la forme d'exécution, le module d'accès ]5 comprend les fonctions d'un module machine "ordinaire" - plus la fonction d'adaptation au monde extérieur. Cette adaptation' peut aussi être réalisée dans un dispositif séparé. T.a seule chlose'qui différentie le. module d'accès des autres est-une connexion supplémen- taire à côté de COML, COMU, COMP, COMD. Un de ces é61éments, par exemple COML, peut même fonctionner à double effet grâce à un branchement qui y est incor- poré. UNE ORGANISATION PAR PROGRA.MiE D'UN MODULE. L'organisation globale. d'un module machine sera décrite ci-après avec référence aux.Fig. 7, 8. Lorsque, contrairement à la solution simple de'la Fig. 7, plusieurs algorithmes non connus au préalable doivent pouvoir être exécutés, chaque module machine doit comprendre un "programme de charge" résidentiel. Ce programme est activé, soit par un signal de retour à l'état initial global (borne 4 de l'élément 300 de la Fig. 7), soit par le fait qu'un message entrant est pourvu d'une indication d'activation pour le - 24 - programme de charge. La technique du chargement d'un programme est en elle-même bien connue. Elle se déroule ici selon une variante de la Fig. 4, à savoir selon un ordre: RS(S). Le programme est donc reçu (R) et émis (S) et si nécessaire encore envoyé vers un deuxième module machine. Chaque module machine ne doit cependant recevoir le programme qu'une seule fois. Le programme de charge résidentiel régit alors l'organisation selon laquelle le programme de travail est stocké. Lors de l'exécution de l'algorithine, plusieurs noeuds sont réalisés comme décrit. Pour plus de simpli- cité, À - _ oOud t.t une identification unique qui, dans l'exemple représenté sur la Fig. 3, est formée par exet ple des deux sigcauix paramdtriques associés: le noeud qui doit, par exemple, calculer (5) porte alors l'iTdication "0521". '-1 est aisé d'en déduire les autres noeuds communiqlulant avec ces noeuds: les tâches partielles sont exécutées par les noeuds "10420" et "0520", les résultats sont amenés aux noeuds "0522" et "0622" (bien entendu uniquement si et pour autant que ces deux noeuds soient réalisés *dans l'algorithme). Dans un module machine, l'espace de mémrnoire disponible est attribué de la manière suivante à un noeud. En premier lieu, une partie est nécessaire pour le 5rogramme de charge (RAM ou ROM). De plus, une partie est nécessaire pour le fonctionnement du module machine lui-même, ce qui lui permet de commuter d'un noeud à un autre et de synchroniser les processus de commluni- cation (RAM ou ROM). Ensuite, une certaine quantité est nécessaire pour les instructions du programlme applicateur. Lorsque ce programme peut être chargé, il se rapporte donc à une mémoire (RAM): cette mémoire contient entre autres une indication de la quantité 2 if?2746 - 25 - d'espace de mémoire (RAM) qui est nécessaire pour chaque noeud: ceci se rapporte donc à de l'espace pour des résultats intermédiaires, pour le nom du noeud, pour un mot d'enregistrement de titre d'instruc- tion, pour une indication de saut indiquant le noeud vers lequel il faut sauter, etc. De plus, la mémoire du module machine contient encore une table d'adresses qui indique les adresses auxquelles les différents noeuds sont stockés. Au départ, tous les éléments de ce tableau sont vides. Une telle organisation à table segmentaire est bien connue en soi. La structure à programme d'un module machine contient plusieurs processus séquentiels travaillant en coopération. Un article standard concernant ces processus intitulé "Cooperating Sequential Processes" de E.W. Dijkstra publié dans "Programming Languages", F. Genuys ed., Academic Press, New York 1968, décrit toutes sortes de niveaux d'interaction pour éviter un blocage interne de la progression. Par module, cinq processus sont prévus dans la forme d'exécution: a) le processus central qui assure les activités des différents noeuds, un noeud tout au plus étant toujours actif; b) pour chacune des quatre connexions (COML, COMU, CO}R, COMD) un processus de canal qui commande la communica- tion proprement dite entre 1,s noeuds des divers modules machine. Par connexion, un transport d'infor- mation semi-duplex est possible. De plus, il est clair que dans la forme d'exécution, deux noeuds diffé- rents ne communiquent jamais directement l'un avec l'autre dans le même module machine. Chaque processus de canal communique avec le processus central associé au moyen de grandeurs séma- phore binaires (bits de signaux) et au moyen d'opéra- tions p et v connues en soi sur ces grandeurs (voir entre autres l'article de Dijkstra mentionné plus haut). On commencera ci-après par décrire l'inter- action entre le processus central d'un module machine et ses quatre processus de canaux (dans le module d'accès éventuellement donc cinq processus de canaux) qui a lieu au moyen d'opérations élémentaires "SEND" et "SELECT" définies ci-après. Sous ce rapport, la Fig. 9 illustre pai t'u. 4-eu c' ' 'u,i ' snsuc'-w,l'opération qui se produit dans deux modules machine communicants pour accompagner le transfert d'un message, notamment en ce qui concerne le module émet- teur. La Fig. lla illustre les mêmes opérations expri- mées en un langage de programmation supérieur. Chaque module machine peut comporter un plus grand nombre de noeuds dont tout au plus un est toujours activé. Une partie de la mémioire locale doit être. réservée pour chaque noeud. Le cas ou le nombre de noeuds à réaliser localement est supdrieur à celui qui correspond à la mémoire localement disponible ne sera pas consi- déré ici. Pour chaque noeud réalisé localement, plusieurs paires de variables Booléennes sont disponibles (qui sont situées en des endroits prédéteninés dans la mémoire locale attribuée aux noeuds). Le nombre de ces paires est égal à la somme du nombre de tâches û5 partielles que l'on peut obtenir par division de la ta de d'un algorithme à utiliser conformément au pro- gramme de division employé pour un traitement non local (dans l'exemple de la Fig. 3, ce nombre est donc égal à deux), augmenté du nombre de directions dans lesquelles le résultat de l'algorithme exécuté finalement dans le module machine en-question peut finalement être expédié (dans l'exemple de la Fig. 3, ce nombre est aussi égal à deux). En principe, le dit nombre de 2 + 2 = 4 peut aussi bien être plus grand (plus de deux tâches partielles sont formées) que plus petit (le résultat formé n'est - 27 - émis ou expédié que dans une direction). Le module machine émetteur détermine lui-même dans quelle direc- tion l'information est expédiée. La paire de variables Booléennes intéressantes est celle de P et Q. Le bloc 226 indique maintenant le démarrage d'une opération d'émission. Dans le bloc 230, dans le module machine "N" émetteur, la variable Booléenne P appartenant au canal x en question est mise à la valez "1". Dans le bloc 232, la -ariable Booléenne Q appartenant au canal en question est directement amenée dans l'état "1" dans le module N' fonctionnant comme récepteur. L'indi- cation sur la ligne 3 de la Fig. 11a stipule que "action" et "fonctionnement" se trouvent ici dans deux modules machine différents. Au niveau de la communica- tion, ceci signifie un fonctionnement non synchronisé au cours duquel, à ce monelnt, l'opération indiquée doit r6ussir sans condition. Dans le bloc 234, on détecte si, dans le ulodule m.clline mretteur, la varia- ble Booléenne Q-apparteuant au canal en question se trouve dans l'état "1". S'il n'en *est pas ainsi, le processus dans le bloc 236 est amené dans un état. d'attente, tandis qu'après, dans le module machine en question, un autre mode, du moins s'il est présent, est activé. Lorsque plusieurs noeuds non actifs sont présents, la sélection peut par exemple s'effectuer selon une interrogation cyclique: cette activation est symbolisée par le fait que le bloc 234 comporte une deuxième entrée partant du bloc d'activation 238. A partir du bloc 238 également, un trajet direct est o30 donc à nouveau possible vers le bloc 236. Lorsque le module en question ne contient qu'un seul processus, la couronne 234-236-238 est parcourue sans interruption. Lorsque dans ce qui précède, la variable Q mentionnée en dernier lieu avait bien la valeur "1", l'opération de communication est réalisée dans le bloc 242. Lorsque _ 28- le message est expédié, dans le bloc 244, la variable Booléenne Q est mise à 11"0"11 dans le module machine émetteur et ensuite, dans le bloc 246, la variable Booléenne P est mise à 1"0"1 dans le module machine émetteur. Finalement, dans le bloc 248, le noeud en question a terminé le transport: il peut entreprendre d'autres activités, par exemple entamer une nouvelle procédure de communication, traiter les résultats présents ou être désactivé. La Fig. 10 illustre d'une manière correspondante, au niveau d'instruction, le tableau de marche du module récepteur et la Fig. 11b illustre les mêmes opérations, mais exprimées en un langage de programma- tion supérieur. Le bloc 250 indique que la procédure -5 de communication est entamée. Le module récepteur peut iné-vitablément conllnaître le canal sur lequel une information doit être reçue: par exemple dans le premier exemple décrit, lorsque le résultat d'une des deux tâches partielles est reçu, mais que l'autre ne l'est pas encore, et que le résultat est toujours reçu par le mnême chemin que celui par lequel les signaux de la tAche partielle à exécuter avaient été expé- diés. En principe, cette dernibre particularité n'est. pas nécessaire: il est par exemple possible qu'un module machine essaie d'expédier-le résultat "aussi rapidement que possible", pour- autant que ce soit par une des deux liaisons CO0NM, C0OMU. Il peut en être de même lors de l'attribution des tâches partielles. Ce problème est important notamment lorsque le processus de division n'est pas symétrique, de telle sorte que le nombre de tâches partielles par niveau de division aug.:,.-e plus que d'une manière linéaire. Dans de tels cas et aussi lorsque, par exemple, il faut recevoir encore au moins deux résultats, on ne sait pas sur quelle cpnnexion le résultat sera reçu. Dans le bloc 252, la - 29 - variable Booléenne P de tous les canaux par lesquels un message peut être reçu, est amenée dans l'état "1" dans le module machine récepteur (N'). Dans le bloc 256, on détecte si, dans le module récepteur, la variable Booléenne Q de l'un quelconque des canaux envisagés dans le bloc 252 se trouve dans l'état "1"; voir le bloc 232. S'il n'en est pas ainsi, le processus en question est amené dans un état d'attente dans le bloc 258, tandis qu'à la suite de cela, dans le module !0 en question, un autre noeud est activé. Cette activa- tion d'un noeud (de récepteur) est symbolisée par le bloc 260. Il convient de noter que dans un même module, tant des noeuds de récepteur que des noeuds d'émetteur peuvent être activés. Lorsque, dans ce qui precede, plus d'un "1" est détecté, on en choisit un de la mani&re connue. Lorsqu'un seul "1" est détecté ou est sélectionné, cela signifie que l'on connaît un noeud d'émetteur qui souhaite une communication (voir Fig. 9, bloc 232). Ensuite, dans le bloc 262, la variable Q du canal correspondant détecté ou sélec- tionné dans le noeud de récepteur est rendue égale à "0". Ensuite, dans le bloc 264 du module machine émet- teur, la variable Q du canal en question es rendue égale à "l". Il s'agit à nouveau d'une opération dans laquelle "l'action" et le "fonctionnement" se trouvent dans deux modules machines différents. Dans le bloc 266, le message est reçu dans le noeud de récepteur - par l'intermédiaire de la liaison ainsi sélectionnée puis il est absorbé, par exemple stocké dans un emplacement de mémoire de la partie de la mémoire attribuée au noeud actif à ce moment là. A la fin du message, toutes les variables Booléennes P du module machine récepteur qui ont été mises à "1" dans le bloc 252, sont ramenées à "0" dans le bloc 268. Dans le bloc 270, la procédure de communication est terminée. ....DTD: - 30 - 2482746 _ 3o _ Ensuite, diverses procédures peuvent à nouveau être entreprises (traitement de résultats, autre communi- cation, activation d'un autre noeud), comme décrit plus haut pour le module émetteur. On décrira sous ce rapport ce qui, sur la Fig. 4, est désigné comme une opération "S" ou comme une opération "R". Un message comporte les deux zones suivantes: a. une grandeur binaire dont une première valeur indique que le contenu du message contient une opération sur une variable "Q", comme décrit à propos des Fig. 9, 10. La deuxième valeur de cette grandeur binaire indique que le contenu du message ne contient pas une telle opération; b. une grandeur de plusieurs bits qui, dans le cas o le messagecontient-une opération sur une variable Q, indique les deux noms des noeuds émetteur et récep- teur. Au cas ou le message en question ne contient aucune opération sur une variable Booléenne Q, cela signifié que cette grandeur à plusieurs bits contient une information destinée aux noeuds actifs à ce moment dans le module machine récepteur. Cette information peut notamment être une grandeur paramétrique. La commulation vers un autre noeud sur les Fig. 9, 10 se produit lorsque, pendant l'instruction "d'attente", la ou les variables Booléennes Q inté- ressantes du noeud actif & ce moment est ou sont dans l'état "0", c'està-dire "pas vrai". Parmi les autres noeuds dans le module machine en question, le premier noeud suivant est trôitg _', pcour ce traite- ment, au moins deux variables Booléennes P, Q asso- ciées l'une à l'autre ont toutes deux la valeur 1. Lors de la désactivation d'un noeud, les contenus de ces registres sont à nouveau enregistrés sur des emplacements de mémoire réservés de la partie de la mémoire du module machine en question qui est attribué au noeud correspondant. Cette technique est dans - 31 - l'ensemble classique. Dans l'organisation décrite, ]la recherche se poursuit donc sans discontinuer jusqu'à ce qu'un nouveau noeud à activer soit trouvé. On décrira encore ci-après l'interaction entre les processus de canaux d'un module machine et le processus central. La Fig. 11c illustre un processus de canal. Les quatre canaux physiques (U, D, R,- L) sont symbolisés par leur index 'x". La communication avec un module machine voisin est chaque fois réglée dans une denture de synchronisation (handshake) au moyen de deux variables Booléennes a, b et d'un tampon BUF. Le procédé de synchronisation est une variante de celui qui a été décrit précédemment dans' l'ancienne demande de brevet Zançais pub]-ee oscis n 5n. 4w.: ci. -:. - - incorporée ici à. titre de référence. Le tampon BUF est utilisé dans deux directions en relation avec l'organisation à liaisons semi-tduplex entre les divers modules machine; le tampon a une capacité de stockage suffisante Dour les deux premières zones décrites d'unI message. De plus, chaque processus de canal CP (x) utilise deux grandeurs sémaphore Booléennes il(x) et i2(x) pour l'amenée de l'information et une grandeur sémaphore BooIéenne 01(x) pour l'évacuation de l'information qui est à nouveau stockée de la manière habituelle sur des positions de registre correspondantes. On admet que le processus de canal CP (x) débute par une opé- ration d'émission. Le canal opposé d'une paire (U/D; R/L) devrait alors débuter par une opération de réception. La Fig. 11c indique le programme dans un langage de programmation supérieur. Lorsque a b, le processus de canal en question peut émettre, et lors que a = b: il peut recevoir. Un commentaire est indiqué par des accolades: la ligne 5 indique qu'un message est parvenu dans BUF(x) et que ce message contient une opération 2482746- _ J _ sur une variable Q: zone fl. La ligne 6 indique que la deuxième zone (f2) du tampon contient encore l'identité du noeud adressé. Grâce à l'identité, deux adresses y, z de l'espace de mémoire disponible sont maintenant implicitement attribuées (ligne 7). Lorsque l'adresse z a une valeur spécifique prédéterminée qui est indiquée par un astérisque, ceci signifie qu'il s'agit d'un "nlouveau" noeud pour lequel de l'espace de îiimoire est réservé à l'adresse de mémoire "y". y est alors une valeur d'adresse relative: c'est- à-dire celle de l'élément suivant de la table de segments qui est libre: l'espace alloué ou attribué est suffisant pour le noeud; l'espace qui est néces- saire est do-?rné par le prograrmlie principal décrit plus haut. Lorsque par contre (ceci est i.ndiqué par un petit rectangle) il ne s'agit pas d'un nouveau noeud, rien ne se produit (skip). Ensuite, lorsqu'il s'agit d'ln nouveau noeud, sur la ligne 11 une grandeur M est rendue égale à 1, q est une grandeur d'adresse de dSp1acemcnt dans le noeud, la quantité d'espace de mYimoJre oqui est nécessaire pour chaque noeud est indiquée par. La ligne 12 forme le pendant de la ligne 5: le mi.essage concerne donc alors une valeur paramétriqlue. Dans ce cas, le processus de canal attend jusqu'à ce que le noeud à ce moment actif puisse accepter cette valeur paramétrique reçue. La ligne 13 indique que ceci est réalisé avec les opérations p- et v- en elles-mêmes classiques: Ceci sera encore expliqué pluis en détail avec référence à la Fig. 11d. La ligne 14 indique que le tampon peut être vide, ce qui est indiqué par l'indication "NIL". Dans ce cas, rien ne se produit. Sur la ligne 16, la variable a est inversée puis on attend jusqu'à ce que les variables $5 a et b soient égales (le pendant de la ligne 03). Slit -4 2746 - 33 - alors la sommation pour une opération d'émission qui débute par une opération p- sur les variables Booléennes "t01(x)". Sur la ligne 18, on procède alors à un essai Termettant de vérifier si la variable "full" est vraie, ce qui permet d'indiquer que le noeud atif à ce moment a effectivement placé une information à émettre dans le tampon. Lorsque cette grandeur est "vraie", il y a retour à l'état initial. Ensuite, la variable "a" est inversée et le processus attend jusqu'à ce que les lO variables a et b soient inégales. Lorsqu'il en est ainsi (opération v-) le processus en question peut se poursuivre. La ligne 20 indique que lorsque la variable "full" n'est pas vraie, la mémoire est remplie d'un message postiche NIL: ceci est donc le cas lorsque le processus central n'a aucun message à émettre. La ligne 21 est ensuite égale à la ligne 19. Finalement, les lignes 22, 23 indiquent la fin des événements. La communication entre le processus de canal CP(x) et le processus central de ce même module machine s'effectue par l'une des trois procédures qui sont illustrées sur les Fig. 11 d, e, f. La Fig. 11d indique la procédure pour la réception d'un message. Ce message est caractérisé par une longueur 1 (nombre de bytes), par une adresse de démarrage A dans la mémoire, adresse qui est reproduite dans le processus central, et par un nom de canal x. La ligne 2 définit une variable courante. Au moyen des opérations p- et v-, sur la ligne 3, le contenu du tampon est repris dans la mémoire. Après mise à jour de la grandeur de comptage d'adresse, la boucle est parcourue. Finalement, la procédure est terminée sur les lignes 5, 6. D'une manière correspondante, la Fig. 11e donne la procédure pour l'émission d'un message, ce message étant destiné au noeud actif dans le module machine -34 - récepteur et ne contenant par conséquent qu'une certaine quantité de signaux paramétriques. Sur la ligne 5, une variable Booléenne est rendue "vraie", ce qui indique que le module machine en question, donc aussi le noeud correspondant, a un message à émettre. Cette variable Booléenne "full" est utilisée sur la Fig. 11c. Sur la ligne 4, à cet effet, le tampon de 9omimunication associé est tout d'abord rempli du signal paramétrique et de l'adresse de démarrage. La boucle est aussi parcourue plusieurs fois jusqu'à ce que l'adresse courante 11 soit égale à la grandeur de longueur 1. On utilise chaque fois une opération -v sur la grandeur 01(x). Sous ce rapport, les Figs.11d et 11e concordent largement. -3 D'une manièrie correspondante, la Fig. 11f indique la procédure pour le remplissage du tampon au moyen d'un signal qui est destiné à un noeud si possible actif mais cependant à activer plus tard. En premier lieu, par:'unple selon les règles de calcul indiquées plus haut, sur-la ligne 2, l'identification du noeud pour lequel le message est destiné est calculée à partir de l'identification du noeud initial. Ensuite, le tampon est rempli à l'aide d'une opération p effec- tuée sur la variable Booléenne 01(x), le contenu de la première zone du message impliquant donc l'indica- tion d'activation. La variable Booléenne "full. est ensuite mise à 1 et la procédure est terminée au moyen d'une opération sur 01(x). Il convient de noter encore que, grâce à l'opération en boucle de la Fig. 11d, l'émission d'un paramètre s'effectue directement de la mémoire du module émetteur vers la mémoire. du module machine récepteur. Il n'y a donc aucun risque de congestion par des trajets de message en conflit les uns avec les autres. Par le signal de retour à l'état initial (voir plus haut), toutes les grandeur 01 sont encore amenées dans l'état "1" et toutes les grandeurs il, i2 sont amenées dans l'état "0". - 35 - REVFNDlCATIONS 1o Système de machine à calculer à multiprocesseur pour l'exécution d'un algorithme divisible sur des données d'entrée, comportant une classification fonc- tionnelle de modules machine remplie au moins en grande partie selon n colonnes (n> 2) et p re (p> 2)., caractérisé en ce que chaque module machine contient un nombre uniforme de m liaisons de classification o 4 m > 3, parmi lesquelles chaque fois un premier ensemble partiel d'au moins deux liaisons de classifi- cation convient commne connexion de source pour la réception d'un signal d'activation et d'un signal paramétrique annexé pour un algorithme et pour l'émission d'un signal de résultat de cet algorithme, 3_5 chaque module machine contient un élément de mémoire (302) pour le stoolcage- de signaux de programme d'au moins une procodure pouvant être activée sélectivement par un signal d'actlvition afin de diviser la tâche d'un algoritlme-divisible associé en deux tâches par- tielles et de combiner les résultats des tâches par- tielles à la réception de ceux-ci en résultat de la dite tâche ou d'exécuter une tâcSe partie.lle élémen- taire du dit algorithme, chaque module machine contient, en outre, un élément processeur (300) pour recevoir les dits signaux de programme et les signaux paramértriques et en alternance soit former les dites tâches partielles, soit combiner les résultats reçus ou exécuter la dite tâche partielle élémentaire et produire un signal de résultat, et, parmi les dites k liaisons de classification, un deuxième ensemble partiel d'au moins deux liaisons de classification convient comme connexions de but pour l'émission d'un autre signal d'activation et d'un signal paramétrique annexé pour une tâche partielle ainsi formée du dit algorithme et pour la réception d'un signal de résultat de la dite tAche partielle, étant entendu que, pour chaque module machine, chacune des m liaisons de classification précitées est un élé]ment d'au moins un des dits premier et deuxième ensembles partiels, qu'au moins un module machine contient, en tant que module d'accès de la classification globale, une autre connexion de source pour la réception d'un signal d'activation externe et d'un signal paramétrique a]nnexé pour un algorithme et pour la fourniture d'un signal de résultat de cet algorithme, qu'un module machine des dites liaisons comporte une première connexion de but conneci le à la première connexion de source du module machine voisin le plus proche sur la même -' que tous les derniers modules machine des rangées sont chaque- fois connectés au premier module machine d'une rangée corr'espondante, que les modules i.;achine comportent une deuxi.me connexion.de but qui est connectéae à une deuxiome connexion de but d'un module machine voi Sn danis la memne colonne et que le dernier module machine d'au moins à peu près la moitié du nombre de colonnes présente une deuxième connexion de but qui est connectée à la deuxième connexion de source du premier module machine d'une colonne correspondante. 2. Système de machine à calculer à multiprocesseur suivant la revendication 1 caractérisé en ce que n = 4, chacun des dits_ ensembles partiels contient deux éléments, la deuxième connexion de but de chaque module machine est connectée à la deuxième connexion de source du module machine voisin de la même colonne et la deuxième connexion de but du dernier module machine de toutes les colonnes est connectée à la deuxième connexion de source du premier module machine d'une colonne correspondante. 3. Système de machine à calculer à multiprocesseur 37 - 487U46 _ 37_ suivant la revendication 2, caractérisé en ce que les derniers modules machine des rangées (1... p) sont connectés chaque fois par leur première connexion de but à la première connexion de source des premiers modules machine des rangées (j+l, j+2,... pl 1... j) et les derniers modules machine des colonnes (1, 2,... n) sont connectés par la deuxième connexion de but ch]aque fois à la deuxième connexion de source des premiers modules machine des colonnes (k+l, k+2,... !O n, 1... k). 4. Système de mac]hine à calculer à multiprocesseur suivant la revendication 3, caractérisé en ce que la classification comprend (nxp) modules machine, k = o et les nombres (p+j) et n ne possèdent pas de facteur i C oni!lln. 5. Systbme de machine à calculer à multiprocesseur su-ivant la rev-,ndication 2, 3 ou 4, caractérisé en ce que p -= n. 6. Systme de machine à calculer à multiprocesseur -O suivant l'une quelconque des revendications 2 à 5 incluse, caractérisé en ce que chaque module machine comprend des 1moyens permettant d'exécuter séparément un procossus central et chaque fois un processus de canal pour chacune des dites connexions de celui-ci et de faire communiquer en outre le processus central exclusivement avec les processus de canaux du module en question, les processus de canaux assurant complète- ment la communication entre les divers modules machine, et la division de la tâche, la combinaison des résul- tats des tâches partielles ou l'exécution d'une tâche partielle élémentaire étant entièrement assurée par le processus central. 7. Système de machine à calculer à multiprocesseur - suivant l'une quelconque des revendications 2 à 6 incluse, caractérisé en ce que des moyens sont présents dans -33 - chaque module machine pour adjoindre à un message qui y est formé par un processus central une indication présentant une première valeur qui indique que le message sert exclusivement de message de quantité pour le noeud actif dans un module machine récepteur et une deuxième valeur qui indique que le message sert exclusivement de message d'activation pour un noeud identifié dans un module machine récepteur au moyen d'une indication contenue dans le corps du O10 message.. 8. Système à multiprocesseur suivant la revendica- tioi 7, caractérisé en ce que, sous la commande de la dite première valeur, un chemin dd cormmuuioii;ion est ouvert entre deux parties des mdmoires des modules machine associés attribuées à ce moment à deux noeuds qui communiquent. 9-. Système de muichine à calculer à lmultiprocesseur suivant l'une quelconque des revendications 2 à 8 incl-; dans lequel chaque fois deux modules machine connectés 'l'un à l'autre sont couplés par l'intermédiaire d'une paire de processus de canaux colnnectés réciproquement en une denture de synchronisation, caractérisé en ce que de tels processus de canaux couplés sont pourvus chacun de: g) des premiers moyens de signaux (P(x)) pour, au moyen d'une p.ernière position (1), pour chaque connexion pré- citée vers un autre module machine, signaler une émission ou une réception souhaitée d'un message suivant cette connexion par le'dit premier module machine, une deuxième position (O) servant à l'exclu- sion d'autres positions après l'achèvement de la dite émission ou de la dite réception, de position de repos; h) des deuxièmes moyens de signaux (Q(x)) présentant une première position pour, dans le cas d'une émission souhaitée par un autre module machine suivant cette - 39.! cornexion, après que la première position des dits premiers moyens de signaux y ait été formée, être amenés eux-mêmes dans la première position et une deuxièrne position (0) qui après détection (256),9 de la première position mentionnée en dernier lieu, opère alors comme position "active" (262) et po:r, dans le cas d'une réception souhaitée par un autre module riachine sniyant cette connexion, après que la dite position "active" mnentioinnée en dernier lieu ait i0 été formée, Tzar l'autre module, être amenés eux-mêmes ainsi dans Ja première position (264), la deuxième position servant de position de repos (244) m terme de la dite réception.