Brevet FR2988877A1 — publié le 20131004

UTILISATION OPTIMISEE D'UNE MATRICE DE PROCESSEURS AYANT DES RESSOURCES DEFECTUEUSES PAR REDONDANCE A L'INTERIEUR DE GRAPPES DE PROCESSEURS Domaine technique de l'invention L'invention est relative aux circuits intégrant une matrice de processeurs ou éléments de traitement semblables, et plus particulièrement à une méthodologie permettant d'utiliser un tel circuit même s'il est partiellement défaillant. État de la technique La figure 1 représente schématiquement un circuit intégrant une matrice de 4x4 éléments CL, du type décrit dans la demande de brevet US2011093854. Les éléments CL sont tous semblables et interconnectés par un réseau sur puce. Comme cela est représenté pour la deuxième rangée et la deuxième colonne, le réseau sur puce peut être de topologie en « tore replié ». Des interfaces d'entrée/sortie, non représentées, sont également insérées dans le réseau sur puce. Chaque élément CL est en fait une « grappe » de processeurs. La figure 2 représente un exemple de structure d'une telle grappe. La grappe comprend 16 processeurs PE semblables connectés à un bus commun B. Le bus B est également relié à une mémoire RAM partagée par les processeurs, à un circuit de gestion de la grappe MGR, et à un routeur RTR. Le routeur RTR assure les communications entre la grappe et le réseau sur puce par quatre voies, N, E, S et W, correspondant aux quatre directions possibles dans la matrice. Le routeur RTR assure également une fonction de noeud du réseau pour relayer des données en transit non destinées à la grappe. Un circuit du type de la figure 1 contient ainsi 256 processeurs. On ne parle plus dans ce cas d'un système « multiprocesseur », terminologie utilisée pour désigner un système avec au plus une dizaine de processeurs, mais d'un système « manycore », terme anglais signifiant « nombreux coeurs (de processeur) ». Le circuit intégré est de grande taille et présente ainsi une probabilité de défaillance élevée au cours de sa fabrication. En début de phase d'industrialisation, sur des plaquettes de 300 mm et avec un noeud technologique de 32 nm, on constate des rendements aussi bas que 30 %, en supposant qu'un circuit est rejeté lorsqu'un seul de ses éléments est défectueux. De nombreuses applications susceptibles d'être exécutées sur un circuit « manycore » n'ont pas besoin de l'ensemble de la puissance de calcul du circuit, c'est-à-dire qu'elles pourraient s'exécuter de manière satisfaisante même si un ou plusieurs processeurs, ou autres ressources du circuit, sont défaillants. Il est donc intéressant, du point de vue du rendement de fabrication, d'accepter au test des circuits ayant un nombre d'éléments défaillants dans une marge de redondance spécifiée. On souhaite alors que les éventuelles défaillances restent transparentes à l'utilisation, c'est-à-dire qu' elles n'affectent pas le développement des applications et leur exécution sur le circuit. Dans un système multiprocesseur conçu pour répartir des tâches de manière dynamique, 10 on peut assez facilement prévoir qu'un processeur défaillant soit identifié et désactivé (en temps réel ou au cours du test en production), et que les tâches se répartissent sur les processeurs restants. Le brevet US8074110 décrit un tel système. Il comprend un pool de processeurs qui sont alloués de manière dynamique en fonction de la puissance de calcul requise par 15 l'application en cours d'exécution. Il est également conçu pour identifier des processeurs défectueux et de les exclure du pool. Toutefois, une allocation dynamique de tâches interdépendantes est un problème NPcomplet - le nombre de combinaisons à évaluer pour une optimisation croît exponentiellement avec le nombre de ressources partagées. L'efficacité d'un système tel 20 que celui du brevet US8074110 susmentionné diminue rapidement avec le nombre de processeurs. Pour éviter ce problème de complexité de l'allocation dynamique des tâches, sans toutefois prévoir de redondance, la demande de brevet US2011093854 susmentionnée (figures 1 et 2) prévoit une combinaison d'allocations statique et dynamique. 25 L'application est subdivisée en tâches qui sont réparties en groupes de tâches ayant un fort taux d'interdépendance. Les groupes sont répartis de manière fixe sur des grappes respectives du circuit - les grappes sont ainsi allouées de manière statique aux groupes de tâches. Ces opérations, dites de placement-routage, sont réalisées par la chaine de compilation à partir d'un code source décrivant les différentes tâches et leurs 30 dépendances (c'est-à-dire les conditions nécessaires à leur exécution, par exemple la disponibilité de données produites par une ou plusieurs autres tâches). Le « placement » consiste au groupement des tâches en fonction des ressources disponibles dans les grappes et à l'affectation des groupes aux grappes, et le « routage » consiste à établir les chemins de communication entre grappes dans le réseau sur puce. Le routage est également statique, calculé à l'avance pour optimiser la bande passante du réseau sur puce en fonction des débits requis entre les grappes. Par contre, à l'intérieur d'une grappe, les processeurs sont alloués de manière dynamique aux tâches. Le nombre de processeurs d'une grappe reste dans une limite 5 raisonnable pour mettre en oeuvre une allocation dynamique. L'allocation des processeurs est mise en oeuvre par le circuit de gestion MGR de la grappe (figure 2). Ce circuit de gestion est notamment prévu pour gérer une file de « tâches prêtes », dans laquelle les processeurs oisifs viennent chercher des tâches à exécuter. Ainsi, des occurrences successives d'une même tâche peuvent être exécutées par des processeurs 10 différents. Résumé de l'invention On souhaiterait prévoir de la redondance dans un circuit « manycore » à allocation de ressources partiellement statique. On tend à satisfaire ce besoin en prévoyant un procédé d'allocation et d'exécution de 15 tâches dans un circuit multiprocesseurs organisé en une matrice de plusieurs grappes semblables de plusieurs processeurs. A la compilation d'une application à exécuter sur le circuit, on subdivise l'application en plusieurs tâches ; on groupe les tâches en plusieurs groupes en fonction des ressources disponibles dans les grappes ; et on produit des informations d'affectation statique des groupes à des grappes respectives. Les 20 informations d'affectation statique sont appliquées au démarrage du circuit. A la compilation, on suppose qu'une grappe singulière est défaillante, et on produit plusieurs combinaisons d'affectations statiques, chacune pour une position différente de la grappe singulière dans la matrice. Au démarrage du circuit, une grappe défaillante est détectée et on applique une combinaison d'affectation statique pour laquelle la position de la 25 grappe singulière coïncide avec la position de la grappe défaillante. Selon un mode de mise en oeuvre, à la compilation, la défaillance de la grappe singulière est supposée totale, d'où il résulte qu'aucun groupe de tâches ne lui est affecté. Selon un mode de mise en oeuvre, à la compilation, la défaillance de la grappe 30 singulière est supposée partielle et due à la défaillance d'une ressource isolée pouvant être allouée dynamiquement, d'où il résulte que le groupe de tâches qui lui est affecté tient compte de l'absence de la ressource isolée. Selon un mode de mise en oeuvre, le procédé comprend les étapes consistant à inclure des informations de routage statique entre grappes dans les informations d'affectation statique ; et produire un premier jeu de combinaisons de routages statiques n'utilisant pas un routeur de la grappe singulière. Selon un mode de mise en oeuvre, le procédé comprend les étapes consistant à produire un second jeu de combinaisons de routages statiques utilisant le routeur de la grappe singulière ; et au démarrage du circuit, appliquer une combinaison de routage statique du second jeu si le routeur de la grappe défaillante est opérationnel. On prévoit également un circuit multiprocesseurs comprenant une matrice de plusieurs grappes semblables de plusieurs processeurs, chaque grappe étant configurée pour allouer ses ressources de manière dynamique aux tâches d'un groupe affecté de manière statique à la grappe ; et une mémoire servant à la programmation du circuit, stockant des informations de placement-routage définissant l'allocation statique des grappes aux groupes de tâches. La mémoire stocke plusieurs combinaisons de placement-routage correspondant aux positions possibles d'une grappe singulière, et on prévoit des moyens pour identifier une grappe défaillante et appliquer une combinaison de placement-routage pour laquelle la position de la grappe singulière coïncide avec la position de la grappe défaillante. Selon un mode de réalisation, les informations de placement de la grappe singulière ne 20 définissent aucune tâche. Selon un mode de réalisation, les informations de placement de la grappe singulière définissent un groupe de tâches conçu pour utiliser moins de ressources que celles disponibles dans la grappe. Selon une variante, on prévoit un procédé d'allocation et d'exécution de tâches dans un 25 circuit multiprocesseurs organisé en une matrice de plusieurs grappes semblables de plusieurs processeurs. A la compilation d'une application à exécuter sur le circuit, on subdivise l'application en plusieurs tâches ; on groupe les tâches en plusieurs groupes en fonction des ressources disponibles dans les grappes, chaque groupe de tâches étant formé de manière qu'il utilise moins de ressources que celles normalement 30 disponibles dans une grappe ; et on produit des informations d'affectation statique des groupes à des grappes respectives. A l'exécution dans chaque grappe, les ressources de la grappe sont allouées de façon dynamique aux tâches. On détecte une ressource défaillante dans une grappe et on la désactive, d'où il résulte que les tâches se répartissent de manière dynamique les ressources restantes de la grappe. Selon un mode de mise en oeuvre, un processeur formant une ressource est désactivé an arrêtant son signal d'horloge. Selon un mode de mise en oeuvre, un processeur formant une ressource est désactivé en gardant à un état actif son signal de réinitialisation. Selon un mode de mise en oeuvre, une page mémoire formant une ressource est désactivée en mappant son espace d'adressage vers une page disponible. Description sommaire des dessins Des modes de réalisation seront exposés dans la description suivante, faite à titre non limitatif en relation avec les figures jointes parmi lesquelles : - les figures 1 et 2, précédemment décrites, représentent une architecture classique de circuit « manycore » à allocation de ressources partiellement statique ; - la figure 3 illustre un procédé de placement-routage de tâches dans un circuit « manycore » à allocation partiellement statique, autorisant la défaillance d'une grappe ; et - la figure 4 représente schématiquement un circuit « manycore » à allocation partiellement statique, dans lequel chaque grappe peut avoir un processeur défaillant. Description d'un mode de réalisation préféré de l'invention Dans un système « manycore » à allocation partiellement statique, du type de la demande de brevet US2011093854 (figures 1 et 2), il est a priori difficile de prévoir de la redondance. Si l'on prévoit des grappes CL redondantes, on se heurte au problème du remplacement d'une grappe défaillante par une grappe de secours alors que les grappes ont été allouées de manière statique à la compilation. Il n'est pas envisageable de déplacer de manière automatique et transparente le groupe de tâches affecté à une grappe défaillante vers une nouvelle grappe disponible. Un tel déplacement briserait notamment le routage statique établi dans la phase de placement-routage. La figure 3 sert à illustrer un procédé permettant une « réparation » transparente d'une grappe défaillante dans un système ayant une grappe redondante. A titre d'exemple, dans la partie droite de la figure 3, on a représenté un circuit « manycore » de 4x4 grappes dont la grappe située en deuxième rangée et deuxième colonne est défaillante. La grappe redondante n'est pas identifiable. Par contre, l'outil de développement de l'application est contraint pour n'exploiter que 15 grappes sur les 16 et à produire une combinaison de placement-routage optimale pour chaque possibilité d'exclusion d'une grappe de la matrice. Les 16 combinaisons possibles sont illustrées dans la partie gauche de la figure 3. Les informations de placement-routage font normalement partie des paramètres stockés dans une mémoire non-volatile externe NVMEM servant à programmer le circuit « manycore » à son démarrage. Dans le cas présent, on stocke les 16 combinaisons de placement-routage dans cette mémoire non-volatile. La grappe défaillante est identifiée, par exemple, à l'aide d'un fusible programmé lors de la phase de test en production, par un programme de test lancé à la mise sous tension, ou par un circuit d'autotest embarqué BIST. Le programme de démarrage, exécuté par un processeur du sous-système d'entrée/sortie IOSYS du circuit, identifie ainsi la grappe défaillante et sélectionne la combinaison de placement-routage qui l'évite, la combinaison illustrée en deuxième rangée et deuxième colonne dans l'exemple de la figure 3. S'il n'y a pas de grappe défaillante, l'une quelconque des combinaisons peut être sélectionnée - on prendra celle qui est accessible le plus rapidement. Bien entendu, l'élaboration de 16 combinaisons de placement-routage prendra plus de temps que l'élaboration d'une seule. Mais ce temps est du temps « hors ligne » pris sur la compilation de l'application. Le temps d'exécution de l'application n'est pas affecté. Le temps de démarrage du circuit à sa mise sous tension n'est pas affecté de manière significative - on ajoute une lecture d'un registre d'indentification de grappe défaillante et la consultation d'un tableau pour extraire l'adresse de la combinaison de placement-routage à utiliser. Le registre peut être configuré pour contenir directement l'adresse de la combinaison à utiliser. La méthodologie qui vient d'être décrite est généralisable à un circuit ayant deux grappes redondantes ou plus. Si la taille de la matrice est de N grappes et que l'on prévoit p grappes redondantes, le nombre de combinaisons de placement-routage à établir est égal au nombre de combinaisons de p grappes dans la matrice, à savoir : CPN = N!/p!(N-p)! Pour 2 grappes redondantes dans une matrice de 16, on a 16x15/2 = 120 combinaisons. Le nombre de combinaisons augmente rapidement avec le taux de redondance. Cela impacte principalement le temps de compilation, qui est hors ligne, mais le temps 5 d'exécution de l'application reste optimal. Une grappe peut être totalement défaillante, par exemple à cause de la défaillance de son circuit de gestion MGR ou du bus système B. Dans ce cas, on utilise la méthodologie qui vient d'être décrite. Il subsiste le fait qu'une grappe défaillante peut avoir un routeur RTR opérationnel. 10 Dans ce cas les combinaisons de placement-routage pourraient en tenir compte et utiliser des chemins qui passent par le routeur de la grappe défaillante - cela pourrait améliorer la bande passante réseau. Par contre, si le routeur est défaillant, les combinaisons de placement-routage utiliseront des chemins alternatifs ne passant pas par ce routeur. 15 Si on veut envisager les deux hypothèses (routeur défaillant ou non), on établira deux jeux de combinaisons de placement-routage, l'un empruntant le routeur de la grappe défaillante, l'autre l'évitant. Si le routeur de la grappe défaillante s'avère opérationnel, on sélectionnera plutôt la combinaison utilisant le routeur, car elle offrira une meilleure bande passante. 20 Une grappe peut être seulement partiellement défaillante, à cause notamment de la défaillance d'un processeur ou de la mémoire. Malgré une telle défaillance, la grappe peut continuer à fonctionner. Comme l'allocation des ressources est dynamique dans la grappe, il suffit pour cela d'identifier et désactiver la ressource défaillante pour que le système cesse de l'utiliser, par exemple à l'aide d'un fusible programmé lors de la 25 phase de test en production, ou en temps réel par un circuit BIST. Si la mémoire est défaillante, il suffit en général de dérouter l'accès à une zone mémoire dans laquelle la panne est détectée vers une autre zone disponible de la mémoire. Si on utilise un circuit de gestion de mémoire virtuelle, celui-ci peut être paramétré pour mapper l'espace d'adressage d'une page défaillante vers une autre page disponible. S'il 30 s'avère qu'aucune zone mémoire n'est disponible pour cette opération, la page défaillante pourrait être mappée vers une zone d'une mémoire externe généralement connectée au circuit. Une telle mesure éviterait des erreurs mais ralentirait notablement l'accès aux données de la page défaillante et obligerait à prévoir un routage des communications à destination de cette mémoire. Si un processeur est défaillant, on pourra le désactiver par : - le maintien à l'état actif de son signal de réinitialisation, - le maintien à un état fixe de son signal horloge, - la coupure de son alimentation, ou - la coupure de son accès au bus mémoire. Le processeur ainsi désactivé ne pourra pas chercher des tâches dans la file de « tâches prêtes », et ces tâches seront réparties naturellement sur les processeurs restants. La présence de processeurs ou de zones mémoire défaillants réduit les ressources disponibles dans la grappe. Un groupe de tâches qui aurait été défini à la compilation pour tenir compte de tous les processeurs d'une grappe pourrait toujours être exécuté dans une telle grappe défaillante, mais le temps d'exécution risquerait de dépasser la valeur spécifiée dans le cahier des charges de l'application. En ce qui concerne les ressources mémoire, le remplacement par une zone mémoire externe serait encore bien plus problématique. Pour ne pas être confronté à ce problème, on peut marquer la grappe comme défaillante et utiliser le procédé décrit en relation avec la figure 3, qui produira une combinaison de placement-routage évitant la grappe. On peut néanmoins vouloir exploiter les ressources réduites disponibles dans la grappe. On est alors de nouveau confronté au problème de l'allocation statique des grappes, où les grappes sont censées être semblables et avoir les mêmes ressources. La figure 4 sert à illustrer une technique que l'on peut utiliser pour éviter ce problème. Bien que chaque grappe comporte 16 processeurs, on contraint l'outil de développement pour ne tenir compte que de 15 processeurs par grappe, par exemple, pour la formation des groupes de tâches à affecter aux grappes. Ainsi, comme cela est illustré par des processeurs marqués en noir à la figure 4, un processeur quelconque dans chaque grappe peut être défaillant, sans que le circuit ne soit considéré comme défaillant. La même méthodologie peut être appliquée aux mémoires des grappes : on contraint l'outil de développement à tenir compte d'un nombre réduit de pages mémoire dans chaque grappe, de sorte que les pages inutilisées soient disponibles pour remplacer dynamiquement des pages qui s'avèrent défaillantes. De façon générale, on considère que les ressources de chaque grappe ont un même taux de redondance r, égal au rapport du nombre de ressources isolables que l'on permet d'être défaillantes sur le nombre total de ressources. Les outils de compilation sont conçus pour définir les groupes de tâches en considérant que chaque grappe dispose d'un taux de ressources disponibles de 1 - r. Le circuit est rejeté au test en production si l'une quelconque des grappes a un taux de ressources défaillantes supérieur à r. En termes de taux d'exploitation des processeurs, dans l'exemple considéré, le circuit est prévu pour fonctionner à 1 - r = 15/16 de sa capacité, ce qui est en fait équivalent à la solution de la figure 3. Si la matrice comprend N grappes de Q processeurs, la première solution offre un taux d'exploitation du circuit de (N-1)/N, tandis que la deuxième offre un taux de (Q-1)/Q. Ainsi, on préfèrera utiliser la solution qui offre le meilleur taux. Il est probable que pour augmenter la puissance de calcul d'un circuit, on augmentera plutôt le nombre de grappes que le nombre de processeurs par grappe, d'où il résulte que la solution de la figure 3 offrira un meilleur taux d'exploitation. Le choix de la solution dépend également de la nature des défaillances les plus fréquentes. La solution de la figure 4 ne tolère pas la défaillance totale d'une grappe, mais tolère une défaillance d'un processeur ou d'une zone mémoire par grappe. Elle est donc plus robuste à de multiples défaillances distribuées. Les processeurs et les mémoires représentent tout de même la majorité de la surface du circuit, et présentent donc une probabilité de panne majoritaire par rapport aux autres éléments du circuit. S'il s'avère que la défaillance la plus fréquente est celle d'un processeur isolé ou d'une zone mémoire isolée, il est possible de ne cibler que ce type de défaillance et d'exploiter la puissance de calcul du circuit au maximum en combinant les solutions des figures 3 et 4. Pour cela on contraint l'outil de développement pour tenir compte de ressources réduites (processeurs et/ou mémoire) dans une grappe singulière et de la totalité des ressources dans les autres grappes. L'outil de placement-routage est prévu pour produire les combinaisons de placement-routage pour les différentes positions possibles de la grappe singulière. Cette grappe joue le même rôle, dans le principe, que la grappe défaillante de la figure 3. Les combinaisons de placement-routage (seize dans l'exemple) sont stockées dans la mémoire servant au démarrage du circuit. A la mise sous tension, le programme de 5 démarrage identifie la grappe contenant l'éventuelle ressource défaillante, et applique la combinaison de placement-routage correspondante. On obtient alors un taux d'exploitation des processeurs de 255/256, ou de (NQ-1)/NQ. Cette solution permet par ailleurs d'augmenter encore la redondance au sein de la même grappe sans impacter le taux d'exploitation de manière significative. En tolérant p 10 ressources défectueuses dans la même grappe, le taux devient (NQ-p)/NQ. REVENDICATIONS1. Procédé d'allocation et d'exécution de tâches dans un circuit multiprocesseurs organisé en une matrice de plusieurs grappes semblables (CL) de plusieurs processeurs (PE), comprenant les étapes suivantes : - à la compilation d'une application à exécuter sur le circuit : - subdiviser l'application en plusieurs tâches ; - grouper les tâches en plusieurs groupes en fonction des ressources disponibles dans les grappes ; - affecter les groupes de façon statique à des grappes respectives ; - à l'exécution dans chaque grappe, allouer les ressources de la grappe de façon dynamique aux tâches ; caractérisé en ce qu'il comprend les étapes suivantes : - à la compilation, former chaque groupe de tâches de manière qu'il utilise moins de ressources que celles normalement disponibles dans une grappe ; et l'exécution, détecter une ressource défaillante dans une grappe et la désactiver, d'où il résulte que les tâches se répartissent de manière dynamique les ressources restantes de la grappe. 2. Procédé selon la revendication 1, dans lequel un processeur formant une ressource est désactivé an arrêtant son signal d'horloge. 3. Procédé selon la revendication 1, dans lequel un processeur formant une ressource est désactivé en gardant à un état actif son signal de réinitialisation. 4. Procédé selon la revendication 1, dans lequel une page mémoire formant une ressource est désactivée en mappant son espace d'adressage vers une page disponible.