Brevet FR2670920A1 — publié le 19920626

La présente invention concerne un appareil et un procédé destinés à résoudre de grands systèmes denses d'équations linéaires dans un ordinateur à traitement parallèle De façon plus particulière, cette invention concerne un procédé de traitement parallèle efficace dans son ensemble qui résout des systèmes denses d'équations linéaires (celles qui contiennent environ 25.000 variables) dans lequel le système utilise efficacement les ressources de calcul et d'entrée/ sortie de l'ordinateur à traitement parallèle et minimise le temps mort de ces ressources. Pour certaines applications, par exemple la détermination de la section transversale radar d'un avion, ou la simulation d'écoulement dans un plan de sustentation, on utilise de très grands systèmes d'équations linéaires Ces équations linéaires comprennent parfois un nombre de variables de l'ordre de 25 000 ou davantage Il faut donc résoudre de très grande matrices comprenant environ 25 000 x 25 000 éléments ou davantage pour résoudre ces équations linéaires Ceci est typiquement difficile à réaliser avec des ordinateurs algébriques linéaires de l'art antérieur en raison de leurs limites inhérentes, comme la puissance de traitement ou la vitesse du dispositif d'entrée/sortie De plus, des limites générales, par exemple la largeur de bande et le coût des ressources constituées par des ordinateurs géants, ont empêché les solutions de ces problèmes Les architectures parallèles de calcul ont été utilisées pour résoudre certains types de problèmes, y compris des systèmes d'équations linéaires, puisque de nombreux petits processeurs peuvent effectuer certaines opérations de facon plus efficace qu'un grand processeur à haute vitesse, comme celui qui se trouve dans un ordinateur géant typique Les limites pratiques de la partition du problème à résoudre dans les machines à traitement parallèle, cependant, ont réduit l'utilité de cette architecture. Dans une machine à traitement parallèle, il faut diviser un problème, (par exemple les opérations nécessaires pour résoudre une grande matrice représentant un système d'équations linéaires) en une série de problèmes discrets afin que le système engendre une solution Segmenter un tel problème n'est pas une tâche facile et doit être conçu avec soin afin de maximiser le traitement par chacun des noeuds parallèles et de minimiser les opérations d'entrée/sortie qui doivent être effectuées Ceci est réalisé afin que le système ne passe pas la majeure partie du temps à effectuer des opérations d'entrée/sortie, en devenant ainsi "lié par les entrées/sorties" alors que les ressources de calcul du système restent sensiblement inactives Par conséquent, un but de la conception de systèmes et de problèmes consiste à maximiser l'ampleur du temps pendant lequel le système traite Un autre but des architectures de traitement parallèle, dans la mise en oeuvre de solution de très grandes matrices, consiste équilibrer la capacité entrée/sortie afin que le système ne soit pas totalement "lié par les calculs" (par exemple traitement seul, sans opérations d'entrée/sortie) tandis que les unités entrée/sortie restent inactives. Un autre problème des ordinateurs à traitement parallèle est que de grands blocs d'une matrice (peut être la matrice entière) doivent être chargés dans la mémoire principale de chaque noeud de traitement parallèle afin de calculer la solution Etant donné que de très grandes matrices exigent des quantités importantes de mémoires principales d'ordinateurs, certains systèmes effectuent des solutions de matrices, "hors noyau" En d'autres termes, des éléments situés à l'intérieur de la matrice qui ne sont pas nécessaires à un instant particulier peuvent être sortis et écrits sur un disque sortie et/ou entrés sur une bande pour être ultérieurement récupérés et traités dans la mémoire principale de chaque noeud dans le système de traitement parallèle Un tel agencement permet un système facile de maintien de réserves (puisqu'elles sont constamment envoyées vers la bande, un disque ou d'autres milieux similaires), et constitue en même temps un point de vérification naturel auquel le calcul peut reprendre si l'alimentation du système d'ordinateur est défaillante, s'il apparaît un défaut de fonctionnement du système ou s'il se produit un autre évènement quelconque qui arrête le traitement. Etant donné le long temps nécessaire pour résoudre de très grandes matrices (qui peut atteindre un mois complet en temps réel pour certains systèmes très importants, par exemple ceux qui contiennent 100 000 x 000 éléments), l'éventualité d'une défaillance de l'alimentation du système ou d'un autre type de défaut de fonctionnement peut se révéler fatale pour résoudre la matrice Un tel système peut être appelé un "dispositif de résolution hors noyau". Un but de la présente invention consiste à réaliser un procédé qui soit spécialement adapté à résoudre sur des ordinateurs à traitement parallèle les problèmes à très grandes matrices. Un autre but de la présente invention consiste à réaliser un procédé de division d'un système à grandes équations linéaires en vue d'une solution efficace par un ordinateur à traitement parallèle. Selon un premier aspect, l'invention propose, pour atteindre ces buts, un procédé destiné à résoudre, dans un ordinateur à traitement parallèle, un système d'équations linéaires dont les coefficients résident dans une première matrice et dans les côtés droits des équations linéaires résidant dans un premier vecteur, la première matrice étant divisée en une pluralité de ND sections de disques en ligne, une pluralité de ND sections de disques en colonne et ND sections de disques en diagonale, et le premier vecteur comprenant ND sections de disques, caractérisé en ce qu'il comprend des étapes suivantes: a répéter les étapes suivantes pour toutes les valeurs de j comprises entre 1 et ND, i factoriser chacune des sections de la pluralité de sections de lignes j; ii factoriser chacune des sections de la pluralité de sections de colonnes j; iii lorsque les étapes i et ii ont achevées, factoriser la section diagonale j en utilisant la pluralité de sections de lignes j et de sections de colonnes j; iv inverser la section diagonale j; b éliminer en sens direct pour toutes les sections du premier vecteur en utilisant la première matrice; et c substituer en sens inverse pour toutes les sections du premier vecteur en utilisant la première matrice. L'inversion utilise, selon un mode de réalisation préféré, une technique de Gauss Jordan. L'ordinateur à traitement parallèle peut comprendre une pluralité de noeuds de calcul, chaque noeud de calcul factorisant une pluralité d'éléments dans chaque section de la pluralité de sections de ligne j, de la pluralité de sections de colonnes j et de la section diagonale j. De préférence, la pluralité de sections de lignes j, de sections de colonne j et de sections diagonales j sont mémorisées dans un milieu de mémorisation non volatile, qui peut comprendre un disque magnétique et/ou un disque optique. Selon un deuxième aspect, l'invention propose, pour atteindre ces buts, un procédé destiné à résoudre, dans un ordinateur à traitement parallèle, un système d'équations linéaires dont les coefficients résident dans une première matrice et des côtés droits des équations linéaires résidant dans un premier vecteur, la première matrice étant divisée en ND lignes, ND colonnes et ND sections diagonales de disques, et le premier vecteur comprenant ND section de disque, caractérisé en ce qu'il comprend les étapes consistant à: a répéter les étapes suivantes pour toutes les valeurs de j qui sont comprises entre 1 et ND, i factoriser la ligne j; ii factoriser la colonne j; iii lorsque les étapes i et ii ont été achevées, factoriser la section diagonale j en utilisant la ligne j et la colonne j; iv inverser la section diagonale j; b éliminer en sens direct pour toutes les sections du premier vecteur utilisant la première matrice; et c substituer en sens inverse pour toutes les sections du premier vecteur utilisant la première matrice. Selon cet aspect de l'invention, également, l'inversion utilise, selon un mode de réalisation préféré, une technique de Gauss Jordan. L'ordinateur à traitement parallèle peut comprendre une pluralité de noeuds de calcul, chaque noeud de calcul factorisant une partie de la ligne j, une partie de la colonne j et une partie de la section diagonale j. De préférence, la ligne j, la colonne j et la section diagonale j sont mémorisées dans un milieu de mémorisation non volatile, qui peut comprendre un disque magnétique et/ou un disque optique. On va maintenant décrire la présente invention à l'aide d'un mode de réalisation préféré, donné à titre d'exemple et non à titre limitatif, en liaison avec les dessins annexés dans lesquels les mêmes références désignent des éléments similaires et dans lesquels: la Figure 1 représente l'architecture de traitement parallèle du mode de réalisation préféré. la Figure 2 représente l'architecture interne d'un noeud de calcul du mode de réalisation préféré. la Figure 3 représente une matrice qui doit être résolue en étant divisée en sections de noeuds et de disques. les Figures 4 a, 4 b et 4 c représentent un procédé de factorisation pour une matrice utilisée dans la présente invention. les Figures 5 a et 5 b représentent les phases d'élimination en sens direct et de substitution en sens inverse pour le procédé de résolution du mode de réalisation préféré. la Figure 6 représente une partie d'une matrice et l'ordre dans lequel des sections particulières de disques sont factorisées dans le mode de réalisation préféré. les Figures 7 a à 7 d représentent un procédé utilisé pour inverser un bloc dans une matrice. la Figure 8 indique quelles sections de noeuds de la matrice sont nécessaires à un noeud de calcul à un instant donné et l'ordre dans lequel ces sections de noeuds sont envoyées à d'autres noeuds dans l'ordinateur à traitement parallèle. la Figure 9 représente le procédé utilisé pour une opération de multiplication matrice-matrice de section de noeud qui est effectuée par chaque noeud de calcul dans le mode de réalisation préféré. On va décrire un procédé de résolution d'un très grand système dense d'équations linéaires dans un ordinateur à traitement parallèle Dans la description qui suit, dans un but d'explication, des longueurs spécifiques de mémoires, des dispositifs entrée/sortie, des architectures et des dimensions de matrices sont indiqués afin de permettre une compréhension complète de la présente invention Il sera cependant clair pour l'homme de l'art que la présente invention peut être mise en oeuvre sans ces détails spécifiques Dans d'autres cas, des circuits et dispositifs bien connus seront représentés sous forme de schéma fonctionnel afin de ne pas obscurcir inutilement la présente invention. A la Figure 1, l'appareil sur lequel le procédé est mis en oeuvre dans le mode de réalisation préféré est représenté dans son ensemble par 100 Le système est une machine de traitement parallèle appelée l'ordinateur Intel i PSC(R>/860 fabriqué par la Supercomputer Systems Division, de Beaverton, Oregon, de Intel'R) Corporation (Intel et i PSC sont des marques déposées de la Intel Corporation de Santa Clara, Californie) Le système 100 est également connu de façon générique comme le "hypercube" Il faut noter que le système 100 comprend de façon générale une série de noeuds comme 110 et 150 représentés à la Figure 1 dans le système 100 qui sont reliés entre eux par des séries de canaux comme 130, 140 et 160 à l'intérieur du système 100 Un noeud peut être noeud d'entrée/sortie (E/S), comme 150 ou un noeud de calcul comme 110 représenté à la Figure 1 Le système 100, tel qu'il est représenté à la Figure 1, constitue un système de calcul réparti dans lequel des dispositifs entrée/sortie sont disponibles pour tous les autres noeuds du système 100 au moyen de leur noeuds respectifs E/S comme 150 et leurs noeuds de calcul comme 110. Le noeud E/S 150 est couplé au noeud de calcul par une ligne 170 Il est également couplé à une série de dispositifs E/S comme des unités de disques 181 et 182, l'unité à bande magnétique 183 ou le carrousel 184 de disques optiques Ces dispositifs sont couplés au noeud E/S 150 par le bus 180 représenté à la Figure 1 Dans le mode de réalisation préféré chacun des dispositifs E/S 181 à 184 est un dispositif d'interface de systèmes de petits ordinateurs (SCSI) permettant des vitesses de transfert pouvant atteindre un mégabyte par seconde au noeud E/S 150 Dans le mode de réalisation préféré, les disques 181 et 182 sont des unités de disques durs à SCSI étanches de classe Winchester dont la capacité maximale de mémorisation est actuellement d'environ 760 mégabytes L'unité à bande magnétique 183, dans le mode de réalisation préféré est une unité à bande magnétique numérique à balayage en hélice de 8 mm utilisée typiquement dans des applications de bandes vidéo La capacité approximative est égale à 3 unités de disque comme 181 et 182 L'unité à bande 183 permet de reporter des unités entières de disques comme 181 et 182 sur l'unité à bande en vue d'un traitement ultérieur, ou peut être utilisée pour effectuer des opérations de réserves. Depuis peu, un noeud E/S 150 peut être couplé à une unité 184 de carrousel à unités de disques optiques. 184 peut être un carrousel à unité de disque optique ("un juke-box de disques compacts de ROM, ou CD ROM") ou peut être, dans une variante de mode de réalisation, une très grande unité de disque optique unique L'unité de disque optique 184 comprend un mécanisme qui permet un accès à l'un quelconque des nombreux disques optiques susceptibles d'être réécrits contenus a l'intérieur de l'unité 184 Ceci donne au système 100 un accès à de nombreux gigabytes de données puisque la capacité de ces disques optiques est d'environ un demi gigabyte Dans des systèmes comprenant plus de 25 000 variables, il faut utiliser de grandes quantités de mémorisation en milieux fixes, comme des carrousels à disques optiques Dans le mode de réalisation préféré, le noeud E/S 150 est un microprocesseur 80386 fabriqué par Intel Corporation de Santa Clara, Californie. Le noeud E/S 150 est relié a son noeud de calcul correspondant, comme 110 dans le système 100 représenté à la Figure 1, par un réseau à haute vitesse appelé le réseau Direct-Connect TM fabriqué par Intel Corporation de Santa Clara, Californie Chaque canal Direct- Connect TM, comme 170 représenté à la Figure 1, est une connexion spécialisée de haute capacité permettant des transferts bidirectionnels à une vitesse pouvant atteindre 5,6 mégabytes par seconde Ce canal permet un accès à tous les noeuds du système 100 par chacun des autres noeuds Tous les noeuds E/S comme 150 et tous les dispositifs E/S comme 181 à 184 sont traités sur le système 100 en tant qu'une entité logique en utilisant le système appelé Concurrent File System (CFS) qui est également un produit de Intel Corporation de Santa Clara, Californie En d'autres termes, même si un accès à différents noeuds et dispositifs E/S est obtenu par de noeuds de calcul du système 100 autres que le noeud , ces dispositifs apparaissent sous la forme d'une entité logique pour le noeud demandant l'accès Le CFS du mode de réalisation préféré exploite un accès parallèle à tous les dispositifs E/S et à tous les processeurs en vue d'un acheminement efficace, automatique des demandes E/S et des données dans tout le réseau Lorsque des grands fichiers sont créés par un noeud de calcul unique, le CFS répartit automatiquement les fichiers parmi les dispositifs E/S disponibles En cas d'accès à de nombreux petits fichiers, la charge est typiquement répartie parmi des dispositifs E/S disponible, des canaux E/S disponibles et les canaux de communication internes à l'intérieur du système 100. Le système Direct-Connect T' représenté dans son ensemble à la Figure 1 comprend des noeuds entrée/ sortie comme 150, et des noeuds de calcul 110, reliés dans une topologie appelée "l'hypercube" Chaque noeud de calcul comme 110 est relié à des canaux individuels comme 130, 140 et 160 dans lesquels chaque noeud possède N voisins La valeur maximale de N, dans le mode de réalisation préféré, est de 7 Par conséquent, dans la topologie d'hypercube du mode de réalisation préféré, un maximum de 128 noeuds de calcul ( 2 N o N égal 7) peuvent résider dans le système Chaque noeud de calcul peut être relié au plus à un noeud E/S comme Bien que la Figure 1 ne représente que 8 noeuds de calcul dans un but d'illustration, 64 noeuds de calcul résident dans le système 100 dans le mode de réalisation préféré Dans des variantes de mode de réalisation, cette valeur peut être une autre puissance de deux Dans le mode de réalisation préféré, le système 100 ne comprend que huit noeuds E/S, la plupart des noeuds de calcul n'étant pas couplés à un noeud E/S correspondant De plus, un noeud de calcul 111 du système 100 ne possède pas de noeud E/S correspondant. La raison en est que le noeud de calcul 111 est couplé à une unité en façade appelée le System Resource Manager (SRM) 151 comme représenté à la Figure 1 La topologie du système 100 permet aux noeuds résidant à un emplacement quelconque de l'hypercube de communiquer avec d'autres noeuds résidant dans l'hypercube en partageant ainsi des ressources comme des unités de disques, des unités de bandes, et d'autres ressources de calcul comme si elles étaient directement reliées au noeud Le système 100 permet des transferts il bidirectionnels à des vitesses pouvant atteindre 5, 6 mégabytes par seconde à l'intérieur de l'hypercube. Même si une ressource demandée est couplée à un autre noeud de calcul, la réponse provenant de la demande E/S donnée par un noeud est la même que si la ressource était reliée directement au noeud Une description détaillée de la technologie de communication Direct- Connect TM utilisée dans le système 100 du mode de réalisation préféré peut être trouvée dans le demande de brevet US No de série 07/298 551 dont l'inventeur est Stephen F Nugent. Comme représenté à la Figure 2 chaque noeud de calcul comprend une unité centrale de traitement 201 qui est un RISC (calculateur à jeu réduit d'instructions) i 86 OTM fabriqué par Intel Corporation de Santa Clara, Californie Chaque noeud de calcul comme 110 comprend un bus 205 qui est couplé à l'unité centrale de traitement i 860 M 4,En outre, le bus 205 établit une communication entre l'unité centrale de traitement 201 et 8 mégabytes de mémoires à accès aléatoire 202 pour mémoriser et traiter des variables assignées au noeud 110 En outre, le bus 205 est couplé à l'interface 203 de réseaux qui permet une communication avec d'autres noeuds du système 100. L'interface 203 de réseaux est couplée à un dispositif d'acheminement 204 de réseaux qui achemine le message transmis par un noeud de calcul comme 110 vers un noeud récepteur approprié dans le système 100 Comme représenté à la Figure 2, le dispositif d'acheminement 204 de réseaux effectue le couplage du noeud 110 avec les canaux extérieurs de communication, comme 130, 140 et 160 représentés aux Figures 1 et 2 Le dispositif d'acheminement 204 de réseaux garantit que les messages envoyés par le noeud 110 sont transmis au noeud récepteur approprié par des lignes comme 130, 140 et représentées à la Figure 1. Puisque le calcul d'une solution pour des matrices dépassant 25 000 x 25 000 éléments en dimension dépasse largement la capacité de mémoire principale de tous les systèmes de calcul connus, il faut mémoriser pendant le traitement des parties de la matrice sur un disque magnétique, un disque optique ou une mémoire à bande Ce qui permet à la matrice représentant le système d'équations linéaires d'être essentiellement d'une dimension quelconque puisque seules des parties de la matrice résideront dans la mémoire de l'ordinateur principal à un instant quelconque donné Le reste de la matrice résidera dans différents dispositifs E/S comme des unités de disques ou de bandes Ce système d'équations linéaires sera de la forme: AX = B o A est une matrice carrée de dimensions N x N. B est une matrice N x K des côtés droits de l'équation, et X est la matrice des inconnus Afin de maximiser la capacité des unités centrales de traitement, de minimiser la charge des canaux E/S et de communication entre processeurs dans le système 100, et de permettre des points de vérification périodiques pour permettre une reprise dans le cas d'une défaillance du système ou d'une interruption par l'opérateur, la plupart des éléments des matrices traitées sont mémorisés "hors noyau" sur une mémorisation à disque. Dans le mode de réalisation préféré, on n'utilise qu'une mémorisation à disque magnétique pour augmenter la mémoire principale du système 100 pour une matrice dont la dimension peut atteindre 25000 x 25000 On utilise un disque optique ou une mémorisation sur bande pour des problèmes plus importants Un bloc de disque (ou section de disque) est une partie de la matrice qui est mémorisée "hors noyau" sur des unités comme 181 et 182 représentées à la Figure 1, et dont la dimension est déterminée de la façon suivante Comme représenté à la Figure 3, une matrice arbitraire 300 peut être de dimension N x N Une telle matrice peut être divisée en plus petits blocs carrés comme 310, représenté à la Figure 3, chaque bloc étant mémorisé sur un disque. Chaque bloc, appelé une section de disque, est d'une dimension de L x L éléments Chaque section de disque comme 310 comprend en outre des sections carrées comme 320, 321, 322 et 323 qui sont de dimensions M x M et sont appelées des blocs de noeud ou sections de noeud. Des sections de noeud sont des parties particulières de sections de disque qui sont résolues par un noeud de calcul particulier comme 110 représenté à la Figure 1. Chaque dimension de section de disque (L) est déterminée par le nombre de noeuds de calcul du système par la capacité de mémoire et de mémorisation fixe de chacun de ces noeuds Dans le système 100, chaque section de disque comme 310 comprend 64 M x M sections de noeud parce qu'il existe 64 noeuds de calcul dans le mode de réalisation préféré A la Figure 3, cependant, seules seize sections de noeud sont représentées dans des buts d'illustration Dans le mode de réalisation préféré, en prenant en compte un double effet de tampon et les trois variables nécessaires pour chaque bloc de noeud, chaque dimension de section de noeud est limitée à 0,9 mégabytes de mémoire de chaque noeud de calcul. Ceci se traduit en un bloc de noeud dont les dimensions sont 224 éléments x 224 éléments Dans le mode de réalisation préféré, par conséquent, M est 224 et L est 1824 Chaque section de disque comme 310 représentée à la Figure 3 contient par conséquent 1792 x 1792 éléments Bien que L égale 1792 dans le mode de réalisation préféré, cette valeur particulière variera en fonction de la capacité de chaque noeud, du nombre de processeurs et de la dimension particulière du problème dans des variantes de modes de réalisation. Dans le mode de réalisation préféré, le nombre de sections de disque dans une ligne de la matrice est égal à ND, et les dimensions de la matrice dans les sections de disques sont ND x ND Le nombre total de sections de disque dans les lignes ou les colonnes de la matrice est donc égal a ND(ND 1)/2 Ces limites particulières ne doivent pas être considérées comme limitant le cadre de la présente invention. Dès lors qu'a été effectuée la partition du problème en sections de disques et de noeuds, chaque section de disque peut être factorisée Le procédé de factorisation de la présente invention est représenté comme processus 400 aux Figures 4 a à 4 c Le procédé de factorisation 400 commence à l'étape 401, initialise l'indice i à l'étape 402, et incrémente l'indice i à l'étape 403 Le processus 400 détermine ensuite à l'étape 404 si l'indice i est encore inférieur ou égal à ND, le nombre total de sections de disque d'une ligne Si i est supérieur à ND, le processus 400 se termine à l'étape 405 Lorsque i est supérieur à ND, le processus 400 aura déterminé les valeurs de toutes les inconnues de chaque section de disque de la matrice. Le processus continuera à l'étape 406 si i n'a pas encore dépassé ND dans le processus 400 Les étapes 406 à 413 factorisent une ligne entiere de sections de disque A l'étape 406, une deuxième variable d'indice j est initialisée à zéro et incrémentée à l'étape 407 Il est déterminé à l'étape 408 si la variable d'indice j est encore inférieure à la variable l'indice i et, si elle ne l'est pas, le processus 400 passe à la partie du processus de calcul de la i-ième colonne des sections de disque comme représenté à la Figure 4 b Si, en revanche, l'indice j est encore inférieur à l'indice i selon la détermination à l'étape 408, le processus 400 passe à l'étape 409 dans laquelle un indice k est initialisé à zéro L'indice k est incrémenté à l'étape 410 et le processus 400 passe en 411 pour déterminer si l'indice k est encore inférieur à l'indice j Si l'indice k est encore inférieur à l'indice j le processus 400 passe à l'étape 412 dans lequel la section de disque résidant dans la matrice A à la i- ième ligne et la j-ieme colonne (Auj) est rendue égale à Aui Aik * Aki Puis, l'étape 412 revient a l'étape 410 dans laquelle l'indice k est incrémenté et les étapes 410 à 412 sont répétées tant que k est inférieur à j Si k est supérieur ou égal à j, le processus 400 passe à l'étape 413 dans laquelle Aij est rendu égal à Aiu * Ajj (Ai An est une section diagonale de disque de la matrice). Le processus de factorisation 400 continue à la Figure 4 b et calcule la i-ième colonne des sections de disque de la matrice Le processus 400 continue a l'étape 414 dans laquelle la variable d'indice j est initialisée à zéro et incrémentée à l'étape 415 A l'étape 416, il est déterminé si la variable d'indice j est inférieure à la variable de l'indice i Si elle ne l'est pas, le processus 400 continue à calculer la i- ième section diagonale de disque de la matrice dans le processus 400 représenté à la Figure 4 c Cependant, si j est encore inférieur a i, le processus 400 passe à l'étape 417 qui initialise l'indice k à zéro et passe à l'étape 418 pour incrémenter k L'étape 419 détermine si k est encore inférieur à j et, s'il ne l'est pas, le processus 400 passe à l'étape 420 qui calcule Aji égal à Aui A Jk * Aki 420 revient alors à l'étape 418 et les étapes 418 à 420 seront répétées tant que k est inférieur à j Dès lors que k est supérieur ou égal à j, l'étape 419 passe à l'étape 415 qui incrémentera la variable d'indice j L'étape 416, lorsque j est supérieur ou égal à i, passera au reste du processus 400 représenté à la Figure 4 c pour calculer la i-ième section diagonale de disque. Le reste du processus 400 représenté à la Figure 4 c factorise la i-ième section diagonale de disque dans la matrice Le processus 400 continue al'etape 421 pour initialiser l'indice j à zéro et incrémenter j à l'étape 422 Il est déterminé à l'étape 423 si l'indice j est encore inférieur à i Siil l'est, l'étape 423 passe à l'étape 425 L'étape 425 calcule la section diagonale de disque Aii comme égale à lancienne diagonale moins les j-ièmes sections de ligne et de colonne Le processus 400 passe à l'étape 422 qui incrémentera à nouveau la valeur j et passera à l'étape 423 425 sera exécuté pour toutes les valeurs de j o j est inférieur à i, en engendrant la valeur diagonale de bloc décomposée de façon appropriée. Dès que j égale i, selon la détermination de l'étape 423, le processus 400 passe à l'étape 424 et calcule l'inverse du bloc diagonal de disque Aii Ce calcul est effectue en utilisant une technique d'inversion de Gauss-Jordan qui est représentée et décrite en référence aux Figures 7 a à 7 d Bien qu'une inversion explicite ne soit pas nécessaire pour calculer la solution de la matrice, une inversion à l'étape 424 diminue sensiblement le temps d'exécution total nécessaire pour obtenir la solution de la matrice dans une architecture à traitement parallèle La raison en est que l'inversion du bloc sera nécessaire pour la phase de solution du procédé représenté au processus 500 aux Figures 5 a et 5 b qui est décrite plus loin. Bien que l'inversion du bloc diagonal représenté à l'étape 424 nécessite à court terme une quantité importante de temps de calcul, elle réduit le temps global d'utilisation du bloc diagonal à un facteur de dix environ L'inversion de Gauss-Jordan représentée aux Figures 7 a à 7 d est une variante du calcul de l'inverse d'une matrice comme une section de disque. Dans le mode de réalisation préféré, elle est supérieure à un procédé utilisant une factorisation LU (qui est la manière habituelle de calculer un inverse pour une machine de traitement linéaire) puisqu'elle nécessite moins de communication et possède des longueurs moyennes de vecteur plus longues. La Figure 6 représente l'ordre dans lequel des sections de disque sont factorisées pour la solution de la matrice Comme représenté à la Figure 6, la matrice 600 comprend une pluralité de sections de disque comme 601 à 617 représentées à la Figure 6. Comme représenté a la Figure 6, des sections de disque de chaque ligne sont calculées avant de calculer les sections de disque pour chaque colonne Lorsque la ligne et la colonne correspondante ont été calculées, la section diagonale de disque de la matrice est calculée Comme représenté à la Figure 6, on calcule en premier lieu le bloc diagonal de la première ligne et de la première colonne 601 Puisqu'il n'y a pas d'autres éléments de ligne ou de colonne pour la première itération lorsque i=l, seul le bloc diagonal 601 est factorisé Puis, pour i= 2, la section de disque 602 à ligne unique est calculée et ensuite la section de disque 605 à colonne unique est factorisée Lorsque les sections de ligne et de colonne ont été factorisées, la section diagonale de disque 606 est calculée Ce processus continue de cette manière, en calculant par exemple dans l'itération suivante, la section de disque 603, et 607 pour la i-ième ligne lorsque i= 3 et ensuite les blocs de colonne correspondants 610 et 611 sont factorisés Lorsque 610 et 611 ont été factorisés, la section diagonale 612 est factorisée Le processus 480 continue de cette manière en calculant en premier lieu les éléments de ligne puis les éléments de colonne pour chaque valeur de i jusqu'à ce que i égale le nombre total de sections de disque de la matrice Dans cet exemple, o seules seize sections de disque ont été représentées, le processus se termine lorsque la section 617 a été factorisée Ce processus suit généralement la diagonale, en quittant chacun des disques dans lesquels la mémoire est écrite dans un état cohérent, en vue d'un traitement ultérieur par d'autres noeuds exigeant les éléments situés à l'intérieur du noeud de bloc particulier, et elle minimise aussi l'opération entrée/sortie effectuée sur les disques dans le système 100. Le procédé de solution correspondant pour la matrice qui a été factorisée par le processus 400 est représenté comme processus 500 aux Figures 5 a et 5 b La phase d'élimination en sens direct du processus de solution 500 est décrite en référence à la Figure 5 a. 500 commence en 501 et initialise l'indice i en 502. L'indice i est incrémenté en 503 et il est déterminé a l'étape 504 si i est encore inférieur ou égal à ND, le nombre total de sections de disques de la matrice Si i est encore inférieur ou égal à ND, ce qui indique que la matrice n'a pas été entièrement traitée, 504 passe à l'étape 505 Les étapes 503 à 507 seront effectuées tant que l'indice i est inférieur ou égal à ND L'étape 505 initialise l'indice j à zéro et j est incrémenté à l'étape 506 Si j est encore inférieur ou égal a l'indice i, la i-ième section de disque de la matrice B est calculée Bi=Bi-Ai i B Ce calcul est effectué jusqu'à ce que l'indice j soit égal à l'indice i. L'étape 508 est répétée pour chaque valeur de j tant que j est inférieur à i Lorsque j devient supérieur ou égal à i, le processus 500 revient à l'étape 503 dans laquelle i est incrémenté Puis, 508 est exécuté pour la valeur suivante de Bi jusqu'à ce que toutes les valeurs de Bi aient eté déterminées dans la phase d'élimination en sens direct 500 a représentée à la Figure 5 a Lorsque toutes les valeurs de Bl ont été déterminées (o l'indice i dépasse ND, selon la détection de l'étape 504 >, le processus 500 passe à la phase de substitution en sens inverse du procédé 500 de résolution représenté à la Figure 5 b La phase de substitution en sens inverse du processus 500 commence à l'étape 509, représentée à la Figure 5 b, dans laquelle l'indice i est rendu égal à ND+l A l'étape 510, i est immédiatement décrémenté de un Puis, à l'étape 511, il y est déterminé si i est devenu inférieur à un (par exemple 0) Lorsque i est devenu inférieur a un, la phase de substitution en sens inverse du procédé de solution 500 est achevée à l'étape 512 Cependant, si l'indice i n'est pas encore devenu inférieur à un, l'étape 513 place un deuxième indice variable j égal lui aussi à ND+l A nouveau, comme avec i ci-dessus, j est immédiatement décrémenté de un à l'étape 514, et il est déterminé à l'étape 515 si j est supérieur à i Ceci détermine si la phase de substitution en sens inverse est achevée (comme indiqué par une valeur de l'indice j supérieure à celle de l'indice i) Si la phase de substitution en sens inverse est achevée, on exécute l'étape 516 dans laquelle la i-ième section de disque de la matrice B est rendue égale au bloc de disque existant Bi multiplié par la section diagonale de disque Aii Comme la diagonale Aii a déjà été inversée précédemment, le résultat placé en Bi à l'étape 516 devrait contenir cette partie de la solution pour la matrice Si, cependant, toutes les colonnes de la i-ième ligne de la matrice A n'ont pas été calculées dans la section actuelle de disque Bi, l'étape 515 passe à l'étape 517 dans laquelle la section de disque Bi est rendue égale à la section de disque actuelle Bi moins la j-ième colonne de la i-ième ligne de A multipliée par BJ. L'étape 517 revient à l'étape 514 o j est à nouveau décrémenté, et l'étape 517 est exécutée de façon répétitive jusqu'à ce que j ne soit plus supérieur à i selon la détermination à l'étape 515 Les étapes 510 à 517 sont effectuées de façon répétitive jusqu'à ce que, selon la détection de l'étape 511, l'indice i soit devenu inférieur à un A cet instant, toutes les inconnues de la matrice B ont été déterminées Ainsi, la solution du système d'équations linéaires représenté par les matrices A et B a été maintenant déterminée. L'inversion, effectuée sur la section diagonale de disque dans la matrice, et représentée a la Figure 4 c comme étape 424, est maintenant décrite en référence aux Figures 7 a à d Elle est appelée inversion de Gauss-Jordan Bien que le mode de réalisation préféré utilise une inversion de Gauss-Jordan comme représenté aux Figures 7 a à 7 d, d'autres procédés d'inversion peuvent être utilises dans des variantes de modes de réalisation Le processus d'inversion 700 est représenté comme débutant à la Figure 7 a à l'étape 701 et l'indice variable i est initialisé à O à l'étape 702 L'étape 703 incrémente i et il est déterminé à l'étape 704 si i est inférieur ou égal à L (le nombre d'éléments de la section de disque en cours d'inversion) S'il ne l'est pas, le processus 700 se termine à l'étape 705 et tous les éléments de ce bloc diagonal de la matrice sont maintenant inversés A l'étape 706, la valeur de l'indice j est initialisée à i, et une valeur maximale (MAX) est initialisée à O à l'étape 707 Puis, à l'étape 709, il est déterminé si j est inférieur ou égal à N et, si tel n'est pas le cas, le processus 700 passe à l'étape 713 représentée à la Figure 7 b Si, en revanche, j est encore inférieur ou égal à N, le processus 700 passe à l'étape 710 L'étape 710 détermine si la valeur absolue (en utilisant une fonction de valeur absolue appelée ABS) de Aij est supérieure à la valeur MAX qui a été déterminée jusqu'ici Si elle ne l'est pas, le processus 700 exécute de façon répétitive les étapes 708 à 710 jusqu'à ce que, ou bien j soit égal à N à l'étape 709, ou bien la valeur absolue de la valeur d'éléments AI, t ABS(Aîj" soit supérieure a MAX Si elle l'est, l'étape 710 mène à l'étape 711 qui rend MAX égale à la valeur absolue de Ai i et à l'étape 712 qui mémorise la valeur de l'indice j dans m Ceci permet de garder mémoire de l'élément qui présente la plus grande amplitude de la i-ième ligne Lorsque tous les éléments de la i-ième ligne ont été traités, selon la détermination de l'étape 709, le processus 700 passe à l'étape 713 de la Figure 7 b. A l'étape 713 représentée à la Figure 7 b, il est déterminé si MAX est supérieur à O S'il ne l'est pas, la matrice est singulière et tout le traitement s'arrête à l'étape 714 Un inverse ne peut pas être calculé pour cette matrice particulière Si MAX est supérieur à 0, cependant, le traitement continue et l'étape 715 initialise la valeur de l'indice j à 0. L'indice j est incrémenté a l'étape 716 et il est détermine à l'étape 717 si j a atteint N Si j n'a pas encore atteint L, selon la détermination de l'étape 717, les étapes 718, 719 et 720 sont exécutées jusqu'à ce que j ne soit plus inférieur ou égal à L Les étapes 718 à 720 rendent une variable temporaire (TEMP) égale à Ai s A l'étape 719, Ai u est rendu égal à Amj, le pivot calculé précédemment (élément qui contenait MAX) dans la ligne Am-j est ensuite rendu égal à TEMP à l'étape 720, en permutant les valeurs contenues dans les deux positions Aij et Am Si, en revanche, j dépasse L (j n'est plus inférieur ou égal à N), le processus 700 passe à l'étape 721 qui rend l'élément diagonal Aii égal à son inverse Puis, le processus 700 passe à l'étape 722 en initialisant j à 0, et ensuite à l'étape 723 qui incrémente j A nouveau, à l'étape 724, il est déterminé si j est inférieur ou égal à L S'il ne l'est pas, le processus 700 passe a l'étape 727 représentée a la Figure 7 c S'il l'est, le processus 700 passe aux étapes 725 et 726 L'étape 725 détermine si les indices variables j et i sont égaux et, s'ils le sont, le processus 700 revient à l'étape 723 Si j nlest pas égal à i, le processus passe à l'étape 726 dans laquelle la valeur actuelle A Jt est rendue égale a la valeur actuelle Aj i multipliée par la valeur de l'élément diagonal Aii Puis, le processus 700 revient à l'étape 723 Lorsque j n'est plus inférieur ou égal à L, selon la détermination de l'étape 724, le processus 700 passe à létape 727 représentée à la Figure 7 c. Comme représenté à la Figure 7 c, l'étape 727 initialise à nouveau j à O et incrémente j à l'étape 728 A l'étape 729, j est à nouveau vérifié pour déterminer s'il est encore inférieur ou égal à N S'il l'est, il est déterminé si j est égal à i et, s'il l'est, l'étape 730 revient à l'étape 728 pour l'incrémentation de l'indice variable j S'il n'est pas égal à i, l'étape 730 passe à l'étape 731 qui initialise k et passe à l'étape 723 qui incrémente k. Il est déterminé à l'étape 733 si k est inférieur ou égal à L S'il l'est, le processus 700 revient à nouveau à l'étape 728 Si k est encore inférieur ou égal à L, le processus passe à l'étape 734 dans laquelle l'indice variable k est vérifié pour déterminer s'il est ou non égal à i S'il n'est pas égal à i, le processus passe à l'étape 735 dans laquelle la valeur de colonne Akj est rendue égale à la valeur actuelle de Ak J moins le produit de Aki par Ai;. Puis, l'étape 735 revient à l'étape 732 qui, à nouveau, incrémente k à l'étape 732 et détermine si toute la ligne a été traitée en vérifiant l'indice variable k a l'étape 733 Lorsque la valeur de l'indice j est déterminée comme n'étant plus inférieure ou égale à L, a l'étape 729, le processus 700 passe à l'étape 736 représentée à la Figure 7 d. Comme représenté à la Figure 7 d, l'étape 736 initialise j à O et j est incrémenté à l'étape 737. L'étape 737 passe à l'étape 738 dans laquelle j est vérifié pour déterminer s'il est encore inférieur ou égal à L, ce qui indique que toute la ligne a fini son traitement S'il l'est, le processus 700 revient à l'étape 703 à la Figure 7 a et tout le processus 700 est à nouveau exécuté jusqu'à ce que i soit supérieur à L. S'il est encore inférieur ou égal à L, il est déterminé à l'étape 739 si j est égal i S'il l'est, l'étape 739 revient à l'étape 737 et les étapes 737 a 739 sont exécutées a nouveau Si, en revanche, les indices j et i ne sont pas égaux, selon la détermination de l'étape 739, on passe a l'étape 740 dans laquelle la valeur actuelle de ligne Aij est rendue égale à la valeur négative de la diagonale Art multipliée par la valeur actuelle de l'élément de ligne Air Puis, l'étape 740 revient à l'étape 737 et les étapes 737 à 739 sont à nouveau exécutées Ainsi, lorsque le processus 7 u O revient aux étapes 703 et 704 (i a dépassé la valeur de L ce qui indique que tout le bloc de diagonal de disque est maintenant inversé), le processus 700 se termine à l'étape 705 représentée à la Figure 7 a Tout le bloc diagonal de disque de la matrice A est maintenant inversé. Tous les noeuds de calcul du système 100 aident à l'exécution des procédés 400 et 500 représentés aux Figures 4 a à 4 c et 5 a et 5 b Il existe trois opérations de base qui doivent être exécutées sur les sections de disques de la matrice: 1 A A B * C 2 A= A *C 3 A= inverse de A Par conséquent, des blocs particuliers de noeuds provenant de l'intérieur de la matrice doivent être disponibles pour chaque noeud pour effectuer les calculs ci-dessus La répartition des blocs de noeud de la matrice à des noeuds est décrite en référence a la Figure 8. Comme représenté a la Figure 8, les blocs de noeuds de la section de disque de la matrice A nécessaires pour la factorisation complète sont représentés graphiquement pour calculer A = A B * C. La Figure 8 représente un cas d'exemple d'un système qui accède à des sections de la matrice dans laquelle le système de traitement parallèle comporte seize noeuds Pour calculer une valeur particulière (par exemple A = A BC ou A = BC), le noeud doit pouvoir accéder à une section de noeud des valeurs A qui est calculé sur toute la ligne des blocs de noeuds B, et une colonne de blocs de C provenant de la section de disque En choisissant avec soin les sections a partir desquelles il y a lieu de commencer, chaque noeud peut calculer A = A B * C pour une paire de sections de noeuds tout en passant simultanément une section de noeud B au noeud de calcul responsable de traiter la section de noeud suivante vers la droite de la section actuelle de noeud et une section de noeud C à la section de calcul suivante "en descendant" (responsable de traiter la section de noeud suivante en descendant dans la section de disque). Par exemple, comme représenté à la Figure 8, pour calculer la valeur du bloc de noeud A 23 801, le noeud de calcul engendrant A 23 801 demande accès à la rangée 811 provenant de la section de disque B 810, et à la colonne de valeur de section de noeud 821 de la section de disque C 820 Comme représenté graphiquement à la Figure 8, lorsqu'une section particulière de noeud B a été calculée, par exemple B 21 812, cette section est passée au noeud de calcul engendrant la section de noeud B 22 813 B 24 814 passe son bloc à B 2 l 812, le noeud traitant la section immédiatement à droite lorsque B 24 814 a été calcule Ceci continue de façon circulaire dans toute la ligne 801 représentée a la Figure 8. De plus, lorsque chaque bloc de noeud de colonne C, comme à la colonne 821, est calculé, ces blocs sont envoyés au noeud de calcul responsable de traiter la section de noeud C suivante en descendant la colonne. Par exemple, lorsque la section de noeud C 33 822 est calculée, cette section est envoyée au noeud de calcul traitant la section suivante en descendant C 4 a 823. Comme pour les blocs de noeud de section B, la colonne s'enroule sur elle-même et, lorsque le noeud de calcul qui traite le dernier bloc de noeud de la colonne, par exemple C 23 824, est calculé, ce bloc est passé au noeud qui traite la section de la première colonne, par exemple celui qui calcule Ca 3 822 La séquence de traitement des sections de noeuds dans chaque section de disque, comme 800, 810 et 820, est complète lorsque chaque processeur comprend une ligne entière de sections de noeuds B et une colonne entière de sections de noeuds C. Pour engendrer les produits matriciels nécessaires pour les processus 400 et 500, chaque noeud, en utilisant la répartition et le passage de valeurs présentés à la Figure 8, doit calculer un produit de deux matrices Ce processus est représenté comme processus 900 à la Figure 9 Le processus 900 est un exemple d'un programme de multiplication standard matrice-matrice BLA 53 ZGEMM Le processus 900 engendre un produit matrice-matrice dans lequel deux matrices B et C sont de dimensions M x M, le résultat est placé en A, les coefficients a et Z sont envoyés et le processus 900 utilise la variable temporaire D, et le vecteur temporaire TEMP de dimension M Le processus 900 de multiplication matrice-matrice commence à l'étape 901 et initialise l'indice i égal à O à l'étape 902 A l'étape 903, i est incrémenté de 1, et 904 détermine si i est encore inférieur à M, le nombre d'éléments des matrices en cours de multiplication Le processus 900 se termine à l'étape 905 si l'indice i n'est plus inférieur ou égal à M, le nombre total d'éléments de la matrice Le processus 900 continue à l'étape 906 qui initialise l'indice j à 0, et passe à l'étape 907 qui incrémente j L'étape 908 détermine si j est encore inférieur ou égal à M et, s'il l'est, on passe à l'étape 909 dans laquelle une variable temporaire TEM Pj est rendue égale à Z*Aij On revient ensuite de l'étape 909 à l'étape 907 et les étapes 907 à 909 sont exécutées de façon répétitive Si, en revanche, j n'est plus inférieur ou égal à M, l'étape 908 passe a l'étape 910 o k est initialisé à O et passe à l'étape 911 qui incrémente k de 1. Le processus 900 se poursuit à l'étape 912 dans laquelle il est déterminé si k est encore inférieur ou égal à N Si k est encore inférieur ou égal à M, le processus 900 passe à l'étape 913 qui rend D égale au produit de a par Cki A l'étape 914, l'indice j est à nouveau initialisé à O et j est incrémenté à l'étape 915 Si j est encore inférieur ou égal a M, selon la détermination de l'étape 916, l'étape 917 rend TEM Pl égal à la valeur actuelle de TEM Pj plus le produit de D par Bjk Puis, l'étape 917 revient à l'étape 915 et les étapes 915 à 917 sont exécutées de façon répétitive jusqu'à ce que j dépasse N, selon la détermination de l'étape 916 Si j dépasse M, selon la détermination de l'étape 916, le processus 900 passe à l'étape 911 et les étapes 911 à 917 sont à nouveau exécutées tant que k et j sont inférieurs ou égaux à M. Lorsque k est supérieur à M, selon la détermination de l'étape 912, le processus 900 passe à l'étape 918 qui initialise aussi j égal à 0 Puis, j est incrémenté a l'étape 919, puis le processus 900 passe à l'étape 920 Llétape 920 détermine si j est encore inférieur ou égal à M et, s'il l'est, le processus 900 passe à 1 étape 921 qui rend l'élément Ai i égal à TEM Pj Puis, l'étape 921 passe a l'étape 919, et les étapes 919 à 921 sont exécutées de façon répétitive jusqu'à ce que j ne soit plus inférieur ou égal à M, selon la détermination de l'étape 920. Lorsque j n'est plus inférieur ou égal à M, selon la détermination de l'étape 920, le processus 920 revient à l'étape 903 qui incrémente à nouveau i et le reste des matrices B et C est traité A la fin du processus 900, par conséquent, le noeud a complètement calculé un produit matrice-matrice pour une paire donnée de matrices B et C. Bien que le procédé décrit en référence aux Figures 4 a à c et 5 a-b ait été décrit en référence à un système 100 qui n'utilise que des unités de disques a milieux magnétiques, comme 181 et 182 à la Figure 1, un système semblable de répartition de données parmi les noeuds de calcul du système peut être utilisé pour des systèmes d'équations linéaires encore plus grand, avec des dispositifs fixes de mémorisation de plus grande capacité Au lieu de n'utiliser que des milieux magnétiques comme dans le mode de réalisation préféré, des unités de disques optiques comme 184 peuvent, dans une variante de mode de réalisation être utilisés en augmentant le nombre de sections de disques Ceci est réalisé en répartissant la mémorisation du nombre volumineux de blocs sur des disques optiques individuels en utilisant un dispositif de carrousel de disques comme 184 De plus, une unité 183 à bande, représenté à la Figure 1, peut être utilisée pour enregistrer sur bande des grandes sections de disques pour des matrices plus importantes dans une autre variante de mode de réalisation. Bien que le mode de réalisation préféré ait été décrit en se référant a l'utilisation d'un nombre de noeuds de calcul égal à une puissance paire de deux (par exemple, 16 ou 64) le procédé représenté aux Figures 4 a à 4 c et 5 a et 5 b peut être implanté sur un système utilisant un nombre de noeuds de calcul égal a une puissance impaire de deux (par exemple, 2, 8, 32 ou 128) Dans le procédé de factorisation, le calcul de sections de disques de la i-ième rangée de la factorisation et le calcul de sections de disques de la i-ième colonne sont indépendants Ainsi, sur un système employant 128 noeuds de calcul, par exemple 64 noeuds pourraient être assignés au calcul des lignes de la factorisation et 64 noeuds pourraient être assignés au calcul des colonnes Seul le calcul des blocs diagonaux exige une certaine synchronisation entre les deux jeux de noeuds de calcul Par conséquent, pour résoudre ce problème, le bloc diagonale devrait être considéré comme une partie de la colonne Puisque les opérations de lignes exigent l'étape additionnelle de multiplier par une section diagonale de disque, la quantité de travail effectué par les processeurs de lignes et les processeurs de colonnes est égale, jusqu'à l'étape de l'inversion de la section diagonale de disque En partageant les colonnes des sections diagonales de disque parmi tous les processeurs une inversion de Gauss-Jordan peut être mise en oeuvre sur l'ensemble des processeurs et tous les processeurs peuvent être maintenus actifs en permanence Dans la phase de solution, comme représenté aux Figures 5 a et 5 b, chaque colonne de la matrice de solution est indépendante de sorte que tous les processeurs peuvent être maintenus actifs en amenant un jeu de 64 noeuds à calculer un jeu de solution et l'autre jeu de 64 noeuds à calculer un jeu différent de solution. En utilisant des combinaisons de mémorisation d'unité de disques ou d'autres formes de milieux, en liaison avec une architecture de traitement parallèle comme représenté à la Figure 1, de très grands systèmes d'équations lineaires denses peuvent être résolus On parvient à accroître la performance de tels systèmes en choisissant avec soin des procédés particuliers pour résoudre de tels systèmes d'équations linéaires Comme décrit plus haut, bien qu'une inversion explicite de blocs diagonaux d'une matrice d'un tel système d'équations linéaires exige, pendant de courts laps de temps, une quantité importante de charge générale d'UCT, ce schéma est économique ultérieurement parce que le temps nécessaire pour utiliser le bloc diagonal peut être réduit par un facteur pouvant atteindre 10. la raison en est que l'utilisation des sections diagonales de disques est beaucoup plus efficace après l'inversion En utilisant ce schéma particulier dans le système 100, on réduit fortement le temps réel nécessaire pour calculer un système dense d'équations linéaires comme celui qui est nécessaire pour des problèmes de sections transversales radar et dissimulation d'écoulement d'air dans un plan de sustentation. Ainsi, un procédé de solution de système très dense d'équations linéaires sur un ordinateur à traitement parallèle a été décrit Bien que la présente invention ait été décrite particulièrement en se référant aux Figures 1 à 9, l'homme de l'art comprendra que la présente invention d'une utilité dépassant largement celle qui est décrite dans les Figures On envisage que de nombreuses variantes et modifications peuvent être effectuées par l'homme de l'art sans s'écarter de l'esprit et du cadre de la présente invention telle qu'elle est décrite plus haut. REVENDICATIONS 1 Procédé destiné à résoudre, dans un ordinateur a traitement parallèle, un système d'équations linéaires dont les coefficients résident dans une première matrice et dont les côtés droits des équations linéaires résident dans un premier vecteur, la première matrice étant divisée en une pluralité de ND sections de disques en ligne, une pluralité de ND sections de disques en colonne et ND sections de disques en diagonale, et le premier vecteur comprenant ND sections de disques, caractérisé en ce qu'il comprend des étapes suivantes: a répéter les étapes suivantes pour toutes les valeurs de j comprises entre 1 et ND, i factoriser chacune des sections de la pluralité de sections de lignes j; ii factoriser chacune des sections de la pluralité de sections de colonnes j; iii lorsque les étapes i et ii ont achevées, factoriser la section diagonale j en utilisant la pluralité de sections de lignes j et de sections de colonnes j; iv inverser la section diagonale j; b éliminer en sens direct pour toutes les sections du premier vecteur en utilisant la première matrice; et c substituer en sens inverse pour toutes les sections du premier vecteur en utilisant la première matrice. 2 Procédé selon la revendication 1 caractérisé en ce que l'ordinateur à traitement parallèle comprend une pluralité de noeuds de calcul, chaque noeud de calcul factorisant une pluralité d'éléments dans chaque section de la pluralité de sections de ligne j, de la pluralité de sections de colonnes j et de la section diagonale j. 3 Procédé selon la revendication 2 caractérisé en ce que la pluralité de sections de lignes j, de sections de colonne j et de sections diagonale j sont mémorisées dans un milieu de mémorisation non volatile. 4 Procédé selon la revendication 3 caractérisé en ce que le milieu de mémorisation non volatile comprend un disque magnétique. Procédé selon la revendication 3 caractérisé en ce que le milieu de mémorisation non volatile comprend un disque optique. 6 Procédé destiné à résoudre, dans un ordinateur à traitement parallèle, un système d'équations linéaires dont les coefficients résident dans une première matrice et des côtés droits des équations linéaires résidant dans un premier vecteur, la première matrice étant divisée en ND lignes, ND colonnes et ND sections diagonales de disques, et le premier vecteur comprenant ND section de disque, caractérisé en ce qu'il comprend les étapes consistant à: a répéter les étapes suivantes pour toutes les valeurs de j qui sont comprises entre 1 et ND, i factoriser la ligne j; ii factoriser la colonne j; iii lorsque les étapes i et ii ont été achevées, factoriser la section diagonale j en utilisant la ligne j et la colonne j; iv inverser la section diagonale j; b éliminer en sens direct pour toutes les sections du premier vecteur utilisant la première matrice; et c substituer en sens inverse pour toutes les sections du premier vecteur utilisant la première matrice. 7 Procédé selon la revendication 6 caracterisé en ce que l'ordinateur à traitement parallèle comprend une pluralité de noeuds de calcul, chaque noeud de calcul factorisant une partie de la ligne j, une partie de la colonne j et une partie de la section diagonale j. 8 Procédé selon la revendication 6 dans lequel la ligne j, la colonne j et la section diagonale j sont mémorisées dans un milieu de mémorisation non volatile. 9 Procédé selon la revendication 8, caractérisé en ce que le milieu de mémorisation non volatile comprend un disque magnétique. 10 Procédé selon la revendication 8 caractérisé en ce que le milieu de mémorisation non volatile comprend un disque optique.