Brevet FR3091774A1 — publié le 20200717

Description Titre de l'invention : Procédé de déploiement d'une tâche dans un supercalculateur, procédé de mise en oeuvre d'une tâche dans un su- percalculateur, programme d'ordinateur correspondant et supercal- culateur [0001] La présente invention concerne un procédé de déploiement d'une tâche dans un su- percalculateur, un procédé de mise en oeuvre d'une tâche dans un supercalculateur, un programme d'ordinateur correspondant et un supercalculateur. [0002] L'invention s'applique plus particulièrement à un procédé de déploiement cl' une tâche clans une grappe d'ordinateurs formant un supercalculateur comportant : [0003] - des ordinateurs présentant chacun au moins une interface réseau formant un noeud ; et [0004] - un réseau d'interconnexion des noeuds, comportant : [0005] -- des commutateurs présentant chacun des interfaces réseaux, et [0006] -- des liens connectant chacun soit un noeud et une interface réseau d'un com- mutateur, soit deux interfaces réseaux de deux commutateurs respectifs ; [0007] le procédé comportant : [0008] - l'allocation de noeuds à la tâche. [0009] L'article de J. Domke et T. Hoeller intitué intitulé « Scheduling-Aware Routine for Supercomputers » et publié dans SC '16: Proceedings of the International Conference for Hie Performance Computing, Networking, Storage and Analysis, Salt Lake City, UT, 2016, pp. 142-153, doi: 10.1109/SC.2016.12 décrit un procédé utilisant une base de données avec la liste des tâches en cours d'exécution sur le supercalculateur, le routage recalculant les routes en fonction de leur utilisation afin de réduire la congestion sur le réseau. [0010] L'article de Matthieu Perotin et Tom Cornebize intitulé « Isolating Jobs for Security on High-Performance Fabrics » publié dans High-Performance Interconnection Networks in the Exascale and Big-Data Era (HiPINEB) 2017, IEEE 3rd International Workshop on, pp. 49-56, 2017, décrit un procédé dans lequel les tâches sont isolées les unes des autres (dans le sens où elles ne peuvent pas communiquer entre elles) en supprimant des lignes dans les tables de routage, de manière à ce qu'il n'existe pas de route entre deux noeuds alloués respectivement à deux tâches différentes. [0011] Cependant, aucun des deux documents ci-dessus ne s'intéresse au problème du contrôle de l'environnement d'exécution des tâches. [0012] 11 peut ainsi être souhaité de prévoir un procédé de déploiement d'une tâche dans une grappe d'ordinateurs formant un supercalculateur, qui permette de s'affranchir d'au 2 moins une partie des problèmes et contraintes précités. [0013] L'invention a donc pour objet un procédé de déploiement d'une tâche dans une grappe d'ordinateurs formant un supercalculateur comportant : [0014] - des ordinateurs présentant chacun au moins une interface réseau formant un noeud ; et [0015] - un réseau d'interconnexion des noeuds, comportant : [0016] -- des commutateurs présentant chacun des interfaces réseaux, et [0017] -- des liens connectant chacun soit un noeud et une interface réseau d'un com- mutateur, soit deux interfaces réseaux de deux commutateurs respectifs ; [0018] le procédé comportant : [0019] - de noeuds à la tâche ; [0020] le procédé étant caractérisé en cc qu'il comporte en outre : [0021] - la détermination, dans le réseau, d'un sous-réseau, d'interconnexion des noeuds alloués, satisfaisant un ou plusieurs critères de détermination prédéfinis comportant un premier critère selon lequel le sous-réseau utilise uniquement des liens qui ne sont alloués à aucune autre tâche déjà déployée ou bien qui sont alloués à moins de N autres tâches déjà déployées, N étant un nombre prédéfini valant un ou plus ; [0022] - l'allocation du sous-réseau, et en particulier des liens appartenant à ce sous-réseau, à la tâche ; et [0023] - l'implémentation de routes de communication inter-noeuds dans le sous-réseau alloué. [0024] Ainsi, grâce à l'invention, le nombre de tâches partageant chaque lien est limité, de sorte que chaque lien a peu de chance d'être congestionné. Ainsi, chaque tâche a l'impression d'être seule (ou presque) à utiliser le réseau d'interconnexion. Ainsi, en particulier, lorsqu'une tâche est exécutée plusieurs fois, l'environnement d'exécution varie peu, puisqu'il est peu affecté par les autres tâches en cours d'exécution. [0025] De façon optionnelle, le nombre prédéfini N vaut un. [0026] De façon optionnelle également, le ou les critères de détermination du sous-réseau comportent en outre un deuxième critère selon lequel le sous-réseau déterminé est celui, parmi au moins deux sous-réseaux satisfaisant les critères autres que le deuxième critère, utilisant le plus de commutateurs déjà alloués chacun à au moins une tâche déjà déployée. [0027] Ainsi, moins de commutateurs sont utilisés, ce qui permet d'éteindre, ou bien de placer dans un état de veille, un grand nombre de commutateurs inutilisés. Malgré la surconsommation et le léger temps de latence dus à l'allumage ou bien au réveil d'un commutateur, il a été trouvé, qu'en moyenne, le procédé de l'invention pouvait permettre une économie d'énergie sans retarder sensiblement le déploiement des tâches. 3 [0028] Dc façon optionnelle également, la détermination du sous-réseau comporte la déter- mination des au moins deux sous-réseaux satisfaisant le ou les critères autres que le deuxième critère, puis la sélection parmi ces au moins deux sous-réseaux de celui utilisant le plus de commutateurs déjà alloués chacun à au moins une tâche déjà déployée. [0029] Il est également proposé un procédé de mise en oeuvre d'une tâche, comportant : [0030] - le déploiement de la tâche dans un supercalculateur, conformément à un procédé de déploiement selon l'invention ; [0031] - l'exécution de la tâche ; et [0032] - à la fin de l'exécution de la tâche : [0033] -- la détection d'au moins un lien qui n'est alloué à aucune tâche, et [0034] -- le placement de chaque lien détecté dans un état inactif, dans lequel le lien requiert une consommation énergétique inférieure à une consommation énergétique requise par un lien associé à au moins une tâche. [0035] Ainsi, il est possible de diminuer la consommation d'énergie du supercalculateur, sans avoir besoin de réaliser des mesures de débit dans les liens pour désactiver ceux dont le débit est nul. [0036] Dc façon optionnelle, le procédé comporte, pour placer un lien dans l'état inactif, l'extinction des deux interfaces réseau que cc lien connecte de sorte qu'aucun courant ou lumière ne parcourt cc lien. [0037] De façon optionnelle également, le procédé comporte, pour placer un lien dans l'état inactif, la diminution d'une fréquence de fonctionnement d'au moins une des deux interfaces réseau que ce lien connecte. [0038] 11 est également proposé un programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur, caractérisé en ce qu'il comprend des instructions pour l'exécution des étapes d'un procédé selon l'invention, lorsque ledit programme est exécuté sur un ou plusieurs ordinateurs. [0039] 11 est également proposé une grappe d'ordinateurs formant un supercalculateur comportant : [0040] - des ordinateurs présentant chacun au moins une interface réseau formant un noeud ; [0041] - un réseau d'interconnexion des noeuds, comportant : [0042] -- des commutateurs présentant chacun des interfaces réseaux, et [0043] -- des liens connectant chacun soit un noeud et une interface réseau d'un com- mutateur, soit deux interfaces réseaux de deux commutateurs respectifs ; [0044] le supercalculateur comportant en outre des moyens logiciels et/ou matériels de dé- ploiement d'une tâche, conçus pour mettre en oeuvre l'étape suivante : [0045] - l'allocation de noeuds à la tâche ; [0046] le supercalculateur étant caractérisé en ce qu'il comporte en outre des moyens logiciels et/ou matériels de déploiement d'une tâche, conçus pour mettre en oeuvre les étapes suivantes : [0047] - la détermination, dans le réseau, d'un sous-réseau, d'interconnexion des noeuds alloués, satisfaisant un ou plusieurs critères de détermination prédéfinis comportant un premier critère selon lequel le sous-réseau utilise uniquement des liens qui ne sont alloués à aucune autre tâche déjà déployée ou bien qui sont alloués à moins de N autres tâches déjà déployées, N étant un nombre prédéfini valant un ou plus ; [0048] - l'allocation du sous-réseau, et en particulier des liens appartenant à ce sous-réseau, à la tâche ; et [0049] - l'implémentation de routes de communication inter-noeuds dans le sous-réseau alloué. [0050] L'invention sera mieux comprise à l'aide de la description qui va suivre, donnée uniquement à titre d'exemple et faite en se référant aux dessins annexés dans lesquels : [0051] [fig.1] la figure 1 représente schématiquement la structure générale d'une grappe d'ordinateurs formant un supercalculatcur, selon un mode de réalisation de l'invention, [0052] [fig.2] la figure 2 représente schématiquement un commutateur du supercalculateur de la figure 1, ainsi que l'environnement de cc commutateur, [0053] [fig.3] la figure 3 illustre les étapes successives d'un procédé de mise en oeuvre d'une tâche dans le supercalculateur de la figure 1, selon un mode de réalisation de l'invention, [0054] [fig.4] la figure 4 illustre un sous-réseau d'interconnexion de noeuds du supercal- culateur de la figure 1 alloués à une première tâche, [0055] [fig.5] la figure 5 illustre un sous-réseau potentiel d'interconnexion de noeuds du su- percalculateur de la figure 1 alloués à une deuxième tâche, [0056] [fig.6] la figure 6 illustre un sous-réseau potentiel d'interconnexion de noeuds du su- percalculateur de la figure 1 alloués à une deuxième tâche, [0057] [fig.7] la figure 7 illustre un sous-réseau potentiel d'interconnexion de noeuds du su- percalculateur de la figure 1 alloués à une deuxième tâche, [0058] [fig.8] la figure 8 illustre un sous-réseau potentiel d'interconnexion de noeuds du su- percalculateur de la figure 1 alloués à une deuxième tâche, [0059] [fig.9] la figure 9 illustre les deux sous-réseaux d'interconnexion de noeuds du super- calculateur de la figure 1 alloués respectivement aux première et deuxième tâches, [0060] [fig.10] la figure 10 illustre un sous-réseau potentiel d'interconnexion de noeuds du supercalculateur de la figure 1 alloués à une troisième tâche, [0061] [fig.11] la figure 12 illustre un sous-réseau potentiel d'interconnexion de noeuds du supercalculateur de la figure 1 alloués à une troisième tâche, [0062] [fig.12] la figure 12 illustre un sous-réseau potentiel d'interconnexion de noeuds du supercalculateur de la figure 1 alloués à une troisième tâche, [0063] [fig.13] la figure 13 illustre les trois sous-réseaux d'interconnexion de noeuds du su- percalculateur de la figure 1 alloués respectivement aux première, deuxième et troisième tâches, et [0064] [fig.14] la figure 14 illustre des liens libérés suite à l'arrêt de l'exécution de la deuxième tâche, dans le supercalculateur de la figure 1. [0065] En référence à la figure 1, une grappe d'ordinateurs 100 (« computer cluster » en anglais) formant un supercalculateur, mettant en oeuvre l'invention va à présent être décrite. [0066] La grappe d'ordinateurs 100 regroupe des ordinateurs 102, 104 indépendants appa- raissant de l'extérieur comme un calculateur unique à très forte puissance de calcul, dit calculateur à haute performance de traitement ou bien calculateur HPC (de l'anglais « High Performance Computing ») ou bien supercalculateur. Chaque ordinateur 102, 104 comporte, comme cela est connu en soi, une unité de traitement centrale (« central processing unit » en anglais), une mémoire principale (« main mcmory » en anglais) dans laquelle des instructions pour l'unité de traitement centrale sont destinées à être enregistrées et au moins une interface réseau. [0067] Les interfaces réseau forment respectivement des noeuds 1...16 de la grappe d'ordinateurs 100. Plusieurs interfaces réseau (et donc plusieurs noeuds 1...16) peuvent appartenir à un même ordinateur 102, 104, ou bien, comme dans l'exemple décrit, chaque ordinateur 102, 104 peut ne comporter qu'une seule interface réseau formant un des noeuds 1...16. [0068] Toujours dans l'exemple décrit, les ordinateurs 102, 104 de la grappe d'ordinateurs 100 comportent des ordinateurs de calcul 102 et des ordinateurs de stockage 104, ces derniers comportant des mémoires de masse telles que des disques durs pour l'enregistrement de données utilisées et/ou produites par les ordinateurs de calcul 102. [0069] Toujours dans l'exemple décrit, les interfaces réseau des ordinateurs de stockage 104 sont des interfaces réseau optiques, tandis que les interfaces réseau des ordinateurs de calcul 102 sont des interfaces réseau électriques présentant un débit inférieur à celui des interfaces réseau optiques. En effet, les ordinateurs de stockage 104 échangent en général plus de données que les ordinateurs de calcul 102. [0070] La grappe d'ordinateurs 100 comporte en outre un réseau 110 d'interconnexion des noeuds 1...16. [0071] Le réseau 110 comporte, d'une part, des commutateurs 1.1...4.8 présentant chacun au moins une interface réseau et, d'autre part, des liens de communication 114 connectant chacun soit un noeud 1...16 et une interface réseau d'un commutateur 1.1...1.8, soit deux interfaces réseau de deux commutateurs 1.1...4.8 respectifs. [0072] La grappe d'ordinateurs 100 présente une certaine topologie définissant l'agencement 6 relatif des noeuds 1...16, des commutateurs 1.1...4.8 et des liens de communication 114. Dans l'exemple décrit, la topologie est celle d'un arbre imposant parallèle généralisé (« Parallel Gencralized Fat Tree » ou PGFT en anglais). La topologie d'un PGFT est définie de manière générale par la nomenclature suivante : PGFT(h ; m 1...ni h ; w 1...w h ; p 1 ...p h), où h est le nombre de niveaux entre lesquels les commutateurs sont répartis, m n est le nombre de commutateurs de niveau n-1 (ou bien de noeuds pour le premier niveau) connectés à chaque commutateur de niveau n, w n est le nombre de commutateurs de niveau n connectés à chaque commutateur de niveau n-1 (ou bien à chaque noeud pour le premier niveau) et p n est le nombre de liens de communication parallèles utilisés entre les niveaux n et n-1 (ou bien entre le niveau n et les noeuds pour le premier niveau). Dans l'exemple décrit, la topologie de la grappe d'ordinateurs 100 est PGFT(4 ; 2, 2, 2, 2 ; 1, 2, 2, 2 ; 1, 1, 1, 1). Ainsi, dans l'exemple décrit les commutateurs de premier niveau sont les commutateurs 1.1 ... 1.8. les commutateurs de deuxième niveau sont les commutateurs 2.1 ... 2.8, etc. [0073] Chaque commutateur 1.1...4.8 comporte des ports de connexion présents dans la ou les interfaces réseau de ce commutateur 1.1...4.8, auxquels les liens de communication 114 sont respectivement connectés. Dans l'exemple décrit, les liens de communication 114 sont tous bidirectionnels, de sorte que tous les ports sont à la fois des ports entrant et sortant. [0074] Par ailleurs, dans l'exemple décrit, chaque commutateur 1.1...4.8 comporte des tables de routage locales respectivement associées à ses ports entrant. Chaque table de routage locale associe un port sortant du commutateur à chaque destination d'un message arrivant par le port entrant considéré. [0075] En outre, chaque commutateur 1.1...4.8 comporte des tables de routages locales par défaut. Dans l'exemple décrit, les tables de routage par défaut sont par exemple préalablement déterminées par l'algorithme d-mod-k ou bien par l'algorithme s-mod-k. [0076] Par exemple, le commutateur 1.3 est illustré sur la figure 2 avec les quatre liens de communication 114 le connectant à ses noeuds 5 et 6 voisins et à ses commutateurs 2.3 et 2.4 voisins. Le commutateur 1.3 comporte ainsi les quatre ports : P_5, P_6, P_2.3 et P_2.4, qui sont à la fois des ports entrant et sortant. Un exemple de table de routage locale par défaut du port P_6 du commutateur 1.3, obtenue par l'algorithme d-mod-k, est illustré dans le tableau 1 ci-dessous. [0077] 7 [Tall 'eaux 1] Table de routage locale par défaut du port P_6 du commutateur 1.3 Noeuds de destination Port de sortie 1 P 2.3 2 P 2.4 3 P 2.3 4 P 2.4 5 P 5 6 P 6 7 P 2.3 8 P_2.4 9 P 2.3 P 2.4 11 P 2.3 12 P 2.4 13 P_2.3 14 P 2.4 P_2.3 16 P 2.4 [0078] De retour à la figure 1, la grappe d'ordinateurs 100 comporte en outre un serveur d'administration 112. Le serveur d'administration 112 est en particulier conçu pour dialoguer avec des clients souhaitant utiliser la grappe d'ordinateurs 100, cette dernière étant alors vue par les clients comme une machine unique. [0079] Le serveur d'administration 112 est conçu pour mettre en oeuvre un procédé de mise en oeuvre de tâches, comme cela sera décrit par la suite. Pour cela, le serveur d'administration 112 comporte des moyens logiciels et/ou matériels, comme par exemple un gestionnaire de ressources (comme le logiciel « slurm ») et un module d'établissement de routage, pour réaliser les étapes qui seront décrites par la suite. Dans l'exemple décrit, le serveur d'administration 112 comporte, comme cela est connu en soi, une unité de traitement centrale et une mémoire principale dans laquelle des instructions pour l'unité de traitement centrale sont destinées à être enregistrées. Ainsi, dans l'exemple décrit, les moyens sont des moyens logiciels, sous la forme de programme d'ordinateur téléchargeable depuis un réseau de communication et/ou en- 8 registré sur un support lisible par ordinateur et/ou exécutable par un processeur, comprenant des instructions pour l'exécution des étapes du procédé lorsque ledit programme d'ordinateur est exécuté sur le serveur d'administration. Alternativement, tout ou partie de ces moyens pourraient être des moyens matériels micro programmés ou micro câblés dans des circuits intégrés dédiés. Ainsi, en variante, le serveur d'administration 112 pourrait être un dispositif électronique composé uniquement de circuits numériques (sans programme d'ordinateur) pour la réalisation des mêmes actions. [0080] Dans d'autres modes de réalisation de l'invention, les différentes fonctions du serveur d'administration 112 pourraient être réparties entre plusieurs dispositifs, par exemple entre plusieurs ordinateurs. Par exemple, le gestionnaire de ressources pourrait être implémenté sur un ordinateur et le module d'établissement de routage sur un autre ordinateur. [0081] La grappe d'ordinateurs 100 permet la répartition de traitements complexes et/ou de calculs parallèles sur au moins une partie des ordinateurs de calcul 102. [0082] Comme cela sera expliqué plus en détail par la suite, à chaque tâche déployée sont alloués, d'une part, des noeuds et, d'autre part, des commutateurs et des liens entre ces commutateurs, formant un sous-réseau d'interconnexion des noeuds alloués. [0083] Dans la description qui va suivre la terminologie suivante sera utilisée. [0084] Un lien est dit inutilisé lorsqu'il n'est alloué à aucune tâche. Ainsi, aucune tâche n'utilise ce lien, de sorte qu'aucune donnée liée à l'exécution d'une tâche ne passe par ce lien. Le lien est dit utilisé dans le cas contraire, c'est-à-dire lorsqu'il est alloué à au moins une tâche, de sorte que des données liées à l'exécution de cette ou ces tâches passent par ce lien. [0085] Un lien est dit disponible lorsqu'il est inutilisé (c'est-à-dire, comme expliqué pré- cédemment, alloué à aucune tâche) ou bien lorsqu'il est alloué à moins de N autres tâches, N étant un nombre prédéfini valant au moins un. Le nombre prédéfini N représente donc le nombre maximal de tâche(s) pouvant utiliser un même lien. Le nombre N peut être égal à un, auquel cas les deux branches de l'alternative précédentes sont équivalentes. Alternativement, le nombre N peut valoir deux ou plus. Le nombre N est par exemple défini avant que des tâches ne soient déployées dans la grappe d'ordinateurs 100, et s'applique pour toutes les tâches déployées ultérieurement, jusqu'à une redéfinition de ce nombre N. Cette redéfinition a par exemple lieu lorsque aucune tâche n'est déployée dans la grappe d'ordinateurs 100. [0086] Un commutateur est dit inutilisé lorsqu'il n'est alloué à aucune tâche. Il est dit utilisé lorsqu'il est alloué à au moins une tâche. [0087] En référence à la figure 3, un procédé 300 de mise en oeuvre d'une tâche, appelée par la suite tâche en cours, dans la grappe d'ordinateurs 100 va à présent être décrit. 9 [0088] Le procédé 300 comporte une étape 302 de déploiement de la tâche en cours dans la grappe d'ordinateurs 100, une étape 304 d'exécution de la tâche en cours et une étape 306 de nettoyage après exécution. [0089] L'étape 302 de déploiement de la tâche en cours comporte les étapes 308 à 316 suivantes. L'étape 308 est par exemple réalisée par le gestionnaire de ressources, tandis que les étapes 310 à 316 sont réalisées par le module d'établissement de routage. [0090] Au cours d'une étape 308, le serveur d'administration 112 reçoit la tâche en cours, ainsi qu'un nombre représentant le nombre de noeuds dont a besoin la tâche en cours pour son exécution. [0091] Au cours d'une étape 310, le serveur d'administration 112 alloue des noeuds à la tâche en cours, connectés au minimum possible de commutateurs inutilisés. Par exemple, le serveur d'administration 112 alloue en priorité les noeuds connectés aux commutateurs déjà utilisés, puis des noeuds consécutifs. [0092] Au cours d'une étape 312, le serveur d'administration 112 détermine un sous-réseau du réseau 110, satisfaisant des critères de détermination prédéfinis. [0093] Les critères de détermination comportent en particulier un premier critère selon lequel le sous-réseau interconnecte les noeuds alloués. [0094] Dans l'exemple décrit, les critères de détermination comporte en outre un deuxième critère selon lequel le sous-réseau utilise uniquement des liens disponibles (c'est-à-dire alloué à aucune autre tâche ou bien alloué à moins de N autres tâches déjà déployées) et un troisième critère selon lequel le sous-réseau déterminé est celui, parmi au moins deux sous-réseaux satisfaisant les autres critères, utilisant le plus de commutateurs déjà utilisés (c'est-à-dire alloués à au moins une tâche déjà déployée). [0095] Dans l'exemple décrit, les au moins deux sous-réseau comportent tous les sous- réseaux satisfaisant les autres critères. [0096] Dans un mode de réalisation, les sous-réseaux recherchés sont des arbres. Ainsi, le serveur d'administration 112 parcourt les commutateurs, par exemple par ordre croissant de niveau, pour trouver chaque arbre (i) ayant ce commutateur pour origine, (ii) n'utilisant que des liens disponibles et (iii) desservant tous les noeuds alloués à la tâche en cours. Ainsi, dans l'exemple décrit, le serveur d'administration 112 détermine tous les arbres possibles ayant le même niveau minimal pour desservir tous les noeuds alloués (en effet, les arbres dont le sommet est de niveau supérieur nécessiteront obligatoirement plus de commutateurs inutilisés) et sélectionne, parmi ces arbres possibles, celui utilisant le plus de commutateurs déjà utilisés. [0097] Alternativement, on pourrait utiliser un algorithme construisant le sous-réseau sa- tisfaisant les trois critères de détermination. Ainsi, il n'y aurait pas besoin de déterminer explicitement tous les sous-réseaux satisfaisant les critères autres que le troisième, pour en sélectionner un. La construction en elle-même s'assurerait que le 10 sous-réseau construit serait celui utilisant le plus de commutateurs déjà utilisés. [0098] Par exemple, un algorithme de construction du sous-réseau est présenté en annexe. [0099] Cet algorithme utilise la notion de sous-topologie. [0100] Une sous-topologie est par exemple un ensemble de un ou plusieurs commutateurs parmi lesquels aucun n'est connecté à un commutateur de niveau inférieur. Ainsi, la topologie complète est un exemple de sous-topologie. Chaque commutateur de premier niveau est également un exemple de sous-topologie. [0101] Une autre définition de sous-topologie est donnée dans l'article de Jean-Noël QUINTIN et Pierre VIGNERAS intitulé « Transitively Deadlock-Free Routing Algorithms » publié en 2016 dans la conférence Conference: HiPINEB, HPCA et accessible à l'adresse suivante : https://www.rescarchgatc.netipublication/301345528 Transitively Deadlock-Frec Ro uting Algorithms [0102] Cet article définit le concept de sous-topology (« enclosing sub-topology »), re- présentée par un tuple I : l'ensemble des commutateurs de niveau k, k