Notre expérience dans l'utilisation d'un cluster informatique de 480 GPU AMD RX 480 pour résoudre des problèmes mathématiques. Comme problème, nous avons pris la preuve du théorème d'un article du professeur A. Chudnov "
Décompositions cycliques d'ensembles séparant les digraphes et les classes cycliques de jeux avec un gain garanti ." La tâche consiste à trouver le nombre minimum de participants dans une coalition dans des jeux de coalition de type Nim, ce qui garantit la victoire de l'un des partis.
Développement CPU
Le premier processeur qui a vraiment obtenu une distribution de masse est le 8086 d'Intel, développé en 1978. La vitesse d'horloge de 8086 n'était que de 8 MHz. Quelques années plus tard, les premiers processeurs sont apparus à l'intérieur desquels se trouvaient 2, 4 et même 8 cœurs. Chaque noyau a permis à son code d'être exécuté indépendamment des autres. À titre de comparaison, le processeur Intel Core i9-7980XE moderne fonctionne à une fréquence de 2,6 GHz et contient 18 cœurs. Comme vous pouvez le constater, les progrès ne s'arrêtent pas!
Développement GPU
Parallèlement au développement de processeurs centraux, des cartes vidéo ont également été développées. Fondamentalement, leurs caractéristiques sont importantes pour les jeux informatiques, où les nouvelles technologies sont particulièrement colorées et où le rendu des images 3D approche progressivement de la qualité photographique. Au début du développement des jeux informatiques, le calcul de l'image a été effectué sur le CPU, mais l'inventivité des développeurs de graphismes 3D a rapidement été atteinte, qui a réussi à optimiser même les choses évidentes (
InvSqrt () en est un bon exemple). Ainsi, des coprocesseurs avec un ensemble spécial d'instructions pour effectuer des calculs 3D ont commencé à apparaître sur les cartes vidéo. Au fil du temps, le nombre de ces équipes a augmenté, ce qui, d'une part, a permis de travailler avec plus de souplesse et d'efficacité avec l'image, et d'autre part, a compliqué le processus de développement.
Depuis 1996, des accélérateurs graphiques S3 ViRGE, 3dfx Voodoo, Diamond Monster et d'autres ont commencé à être produits. En 1999, nVidia a sorti le processeur GeForce 256, introduisant le terme GPU - un processeur graphique. Il est déjà universel, il peut gérer des calculs géométriques, des transformations de coordonnées, le placement de points d'éclairage et travailler avec des polygones. La différence entre le GPU et les autres puces graphiques était qu'à l'intérieur, en plus des commandes spécialisées, il y avait un ensemble de commandes standard avec lesquelles vous pouviez implémenter votre propre algorithme de rendu. Cela a donné un avantage significatif, car il a permis d'ajouter des effets spéciaux, et pas seulement ceux qui sont déjà programmés dans la carte vidéo. À partir de la GeForce 8000/9000, les processeurs de flux sont apparus dans le GPU - des ordinateurs à part entière. Leur nombre variait de 16 à 128 selon les modèles: dans la terminologie moderne, ils sont appelés unités de shader unifiées, ou simplement unités de shader. Les GPU AMD Vega 64 fabriqués aujourd'hui contiennent 4096 unités de shader et la fréquence d'horloge peut atteindre 1536 MHz!
Que contient un GPU?
L'architecture GPU diffère de la CPU par un grand nombre de cœurs et un ensemble minimaliste d'instructions destinées principalement à l'informatique vectorielle. Au niveau de l'architecture, les problèmes de fonctionnement en parallèle d'un grand nombre de cœurs et d'accès simultané à la mémoire ont été résolus. Les GPU modernes contiennent de 2 à 4 000 unités de shader, qui sont combinées en unités de calcul (unité de calcul). En informatique parallèle, le problème de l'accès simultané à la mémoire est particulièrement aigu. Si chacun des processeurs de flux essaie d'écrire dans la cellule de mémoire, ces commandes se retrouveront dans le verrou et devront être mises en file d'attente, ce qui réduira considérablement les performances. Par conséquent, les processeurs de flux exécutent des instructions en petits groupes: tandis qu'un groupe effectue les calculs, l'autre charge les registres, etc. Vous pouvez également combiner les cœurs en groupes de travail avec une mémoire partagée et des mécanismes de synchronisation interne.
Une autre caractéristique importante du GPU est la présence de registres vectoriels et d'ALU vectorielles, qui peuvent effectuer des opérations simultanément pour plusieurs composants du vecteur. C'est principalement nécessaire pour les graphiques 3D, mais comme notre monde est en trois dimensions, rien ne nous empêche de l'utiliser pour de nombreux calculs physiques. En présence d'ALU vectorielles libres, elles peuvent également être utilisées pour calculer des quantités scalaires.
Ils sont tellement différents, CPU et GPU
Pour le fonctionnement complet du système informatique, les deux types d'appareils sont importants. Par exemple, nous exécutons un programme étape par étape, un certain algorithme séquentiel. Il n'y a aucun moyen d'effectuer la cinquième étape de l'algorithme, donc les données correspondant sont calculées à l'étape quatre. Dans ce cas, il est plus efficace d'utiliser un processeur avec un grand cache et une vitesse d'horloge élevée. Mais il existe des classes entières de tâches qui se prêtent bien à la parallélisation. Dans ce cas, l'efficacité du GPU est évidente. L'exemple le plus courant est le calcul des pixels d'une image rendue. La procédure pour chaque pixel est presque la même, les données sur les objets 3D et les textures sont situées dans la RAM de la carte vidéo et chaque processeur de flux peut calculer indépendamment sa propre partie de l'image.
Voici un exemple d'une tâche moderne - la formation d'un réseau neuronal. Un grand nombre de neurones identiques doivent être entraînés, c'est-à-dire pour changer les coefficients de poids de chaque neurone. Après de tels changements, il est nécessaire de passer des séquences de test à travers le réseau neuronal pour la formation et d'obtenir des vecteurs d'erreur. Ces calculs conviennent bien au GPU. Chaque processeur de flux peut se comporter comme un neurone et lors du calcul il ne sera pas nécessaire de construire la solution de manière séquentielle, tous nos calculs se feront simultanément. Un autre exemple est le calcul des flux aérodynamiques. Il est nécessaire de connaître le comportement possible du pont conçu sous l'influence du vent, de simuler sa stabilité aérodynamique, de trouver les sites d'installation optimaux pour les carénages pour ajuster le débit d'air ou pour calculer la résistance à la résonance du vent. Vous vous souvenez du célèbre «pont dansant» de Volgograd? Je pense que personne ne voudrait être à ce moment sur le pont ...
Le comportement du flux d'air en chaque point peut être décrit par les mêmes équations mathématiques et résoudre ces équations en parallèle sur un grand nombre de cœurs.
GPU entre les mains des programmeurs
Pour effectuer des calculs sur le GPU, un langage spécial et un compilateur sont utilisés. Il existe plusieurs cadres pour effectuer un calcul GPU général: OpenCL, CUDA, C ++ AMP, OpenACC. Les deux premiers ont été largement utilisés, mais l'utilisation de CUDA n'est limitée que par les GPU de nVidia.
OpenCL a été publié en 2009 par Apple. Plus tard, Intel, IBM, AMD, Google et nVidia ont rejoint le groupe Khronos et ont annoncé leur soutien à la norme commune. Depuis lors, une nouvelle version de la norme apparaît tous les ans et demi à deux ans et chacune apporte des améliorations de plus en plus sérieuses.
À ce jour, le langage OpenCL C ++ version 2.2 est conforme à la norme C ++ 14, prend en charge l'exécution simultanée de plusieurs programmes au sein de l'appareil, l'interaction entre eux via des files d'attente et des pipelines internes et permet une gestion flexible des tampons et de la mémoire virtuelle.
Tâches réelles
Un problème intéressant de la théorie des jeux, à la solution de laquelle nous avons participé, est la preuve du théorème d'un article du professeur A. Chudnov "
Décompositions cycliques d'ensembles séparant les digraphes et les classes cycliques de jeux avec un gain garanti ." La tâche consiste à trouver le nombre minimum de participants dans une coalition dans des jeux de coalition de type Nim, ce qui garantit la victoire de l'un des partis.
D'un point de vue mathématique, il s'agit d'une recherche d'une séquence cyclique de support. Si vous représentez la séquence sous la forme d'une liste de zéros et de uns, la vérification de la prise en charge peut être implémentée par des opérations logiques au niveau du bit. Du point de vue de la programmation, une telle séquence est un long registre, par exemple 256 bits. Le moyen le plus fiable pour résoudre ce problème est de trier toutes les options sauf l'impossible pour des raisons évidentes.
Les objectifs de la résolution du problème sont des problèmes de traitement efficace du signal (détection, synchronisation, mesure de coordonnées, codage, etc.).
La difficulté de résoudre ce problème est de trier un grand nombre d'options. Par exemple, si nous recherchons une solution pour n = 25, alors c'est 25 bits, et si n = 100, alors c'est déjà 100 bits. Si nous prenons le nombre de toutes les combinaisons possibles, alors pour n = 25 c'est 2 ^ 25 = 33 554 432, et pour n = 100 c'est déjà 2 ^ 100 = 1 267 650 600 228 229 401 496 703 205 376 combinaisons. L'augmentation de la complexité est tout simplement colossale!
Cette tâche est bien parallélisée, ce qui signifie qu'elle est idéale pour notre cluster GPU.
Programmeurs vs mathématiques
Initialement, les mathématiciens ont résolu ce problème dans Visual Basic dans Excel, ils ont donc réussi à obtenir des solutions principales, mais les faibles performances des langages de script ne nous ont pas permis d'aller de l'avant. La décision de n = 80 a pris un mois et demi ... Nous inclinons la tête devant ces patients.
La première étape, nous avons implémenté l'algorithme de tâche en C et l'avons lancé sur le CPU. Au cours du processus, il s'est avéré que beaucoup de choses peuvent être optimisées lorsque vous travaillez avec des séquences de bits.
Ensuite, nous avons optimisé la zone de recherche et éliminé les doublons. De plus, une analyse du code assembleur généré par le compilateur et une optimisation du code pour les fonctionnalités du compilateur ont donné un bon résultat. Tout cela a permis d'obtenir une augmentation significative de la vitesse des calculs.
L'étape suivante de l'optimisation a été le profilage. La mesure du temps d'exécution de différentes sections du code a montré que dans certaines branches de l'algorithme, la charge sur la mémoire augmentait considérablement, ainsi qu'une ramification excessive du programme a été révélée. En raison de ce «petit» défaut, près d'un tiers de la puissance du processeur n'a pas été utilisé.
Un aspect très important de la résolution de ces problèmes est la précision de l'écriture du code. Personne ne connaît les bonnes réponses à ce problème et, par conséquent, il n'y a pas de vecteurs de test. Il n'y a que la première partie de la gamme de solutions que les mathématiciens ont trouvées. La fiabilité des nouvelles solutions ne peut être garantie que par la précision de l'écriture du code.
La phase de préparation du programme pour la solution sur le GPU est donc arrivée et le code a été modifié pour fonctionner dans plusieurs threads. Le programme de contrôle est désormais engagé dans la répartition des tâches entre les threads. Dans un environnement multi-thread, la vitesse de calcul a été multipliée par 5! Ceci a été réalisé grâce au fonctionnement simultané de 4 threads et à la combinaison de fonctions.
À ce stade, la décision a fait les bons calculs jusqu'à n = 80 en 10 minutes, alors que dans Excel, ces calculs ont pris un mois et demi! Petite victoire!
GPU et OpenCL
Il a été décidé d'utiliser OpenCL version 1.2 pour assurer une compatibilité maximale entre les différentes plates-formes. Le débogage initial a été effectué sur le processeur d'Intel, puis sur le GPU d'Intel. Ensuite, ils sont passés au GPU d'AMD.
La norme OpenCL 1.2 prend en charge les variables entières de 64 bits. La dimension 128 bits est prise en charge de manière limitée par AMD, mais se compile en deux nombres 64 bits. Pour des raisons de compatibilité et pour optimiser les performances, il a été décidé de présenter un nombre 256 bits comme un groupe de nombres 32 bits, opérations logiques au niveau du bit sur lesquelles sont effectuées le plus rapidement possible sur le GPU ALU interne.
Un programme OpenCL contient un noyau - une fonction qui est le point d'entrée d'un programme. Les données à traiter sont téléchargées de la CPU vers la RAM de la carte vidéo et transférées au noyau sous forme de tampons - pointeurs vers un tableau de données d'entrée et de sortie. Pourquoi un tableau? Nous effectuons un calcul haute performance, nous avons besoin de nombreuses tâches qui sont effectuées simultanément. Le noyau s'exécute sur le périphérique dans plusieurs instances. Chaque cœur connaît son identifiant et prend sa propre entrée dans un tampon partagé. Le cas où la solution la plus simple est la plus efficace. OpenCL n'est pas seulement un langage, mais aussi un cadre complet dans lequel tous les détails de l'informatique scientifique et des jeux sont soigneusement pensés. Cela facilite la vie du développeur. Par exemple, vous pouvez démarrer de nombreux threads, le gestionnaire de tâches les placera sur l'appareil lui-même. Les tâches qui n'ont pas démarré l'exécution immédiate seront mises en file d'attente et lancées à mesure que les unités de calcul deviennent libres. Chaque instance du noyau a son propre espace dans le tampon de sortie, où elle place la réponse à la fin du travail.
La tâche principale du gestionnaire OpenCL est d'assurer l'exécution parallèle de plusieurs instances du noyau. L'expérience scientifique et pratique accumulée au fil des décennies est appliquée ici. Alors que certains cœurs chargent des données dans des registres, une autre partie à l'heure actuelle fonctionne avec la mémoire ou effectue des calculs - en conséquence, le cœur du GPU est toujours entièrement chargé.
Le compilateur OpenCL fait un bon travail d'optimisation, mais il est plus facile pour un développeur d'influencer les performances. L'optimisation du GPU va dans deux directions: accélérer l'exécution du code et la possibilité de le paralléliser. La façon dont le code est parallélisé par le compilateur dépend de plusieurs choses: le nombre de registres de travail occupés (qui sont situés dans la mémoire GPU la plus lente - globale), la taille du code compilé (vous devez tenir dans 32 Ko de cache), le nombre de registres vectoriels et scalaires utilisés.
GPU ComBox A-480 ou un million de cœurs
C'est la partie la plus intéressante du projet, lorsque nous sommes passés d'Excel à un cluster informatique composé de 480 cartes graphiques AMD RX 480. Grand, rapide, efficace. Complètement prêt à accomplir la tâche et à obtenir ces résultats que le monde n'a jamais vus auparavant.
Je voudrais noter qu'à toutes les étapes de l'amélioration et de l'optimisation du code, nous avons commencé la recherche d'une solution dès le début et comparé les réponses de la nouvelle version avec les précédentes. Cela nous a permis de nous assurer que l'optimisation et les améliorations du code n'introduisaient pas d'erreurs dans les solutions. Ici, vous devez comprendre qu'il n'y a pas de bonnes réponses à la fin du manuel et que personne au monde ne les connaît.
Le lancement sur le cluster a confirmé nos hypothèses sur la vitesse des solutions: la recherche de séquences pour n> 100 a pris environ une heure. C'était incroyable de voir comment de nouvelles solutions étaient sur le cluster ComBox A-480 en quelques minutes, tandis que sur le CPU, cela a pris de nombreuses heures.
En seulement deux heures de cluster informatique, nous avons obtenu toutes les solutions jusqu'à n = 127. Une vérification des solutions a montré que les réponses obtenues sont fiables et correspondent aux théorèmes du professeur A. Chudnov énoncés dans l'article
Evolution de la vitesse
Si vous examinez le gain de performances au cours de la résolution du problème, les résultats sont approximativement les suivants:
- un mois et demi à n = 80 dans Excel;
- une heure à n = 80 sur Core i5 avec un programme C ++ optimisé;
- 10 minutes à n = 80 sur Core i5 en utilisant le multithreading;
- 10 minutes à n = 100 sur un GPU AMD RX 480;
- 120 minutes à n = 127 sur le ComBox A-480.
Perspectives et avenir
De nombreuses tâches à l'intersection de la science et de la pratique sont en attente pour améliorer notre vie. Le marché de la location de puissance informatique ne fait qu'émerger et le besoin de calcul parallèle continue de croître.
Applications possibles du calcul parallèle:
- tâches de contrôle automatique des véhicules et des drones;
- calculs des caractéristiques aérodynamiques et hydrodynamiques;
- reconnaissance vocale et images visuelles;
- formation au réseau de neurones;
- tâches d'astronomie et d'astronautique;
- analyse statistique et corrélation des données;
- pliage des composés protéine-protéine;
- diagnostic précoce des maladies grâce à l'IA.
Une autre direction est le cloud computing sur le GPU. Par exemple, des géants comme Amazon, IBM et Google louent leur puissance de calcul au GPU. Aujourd'hui, nous pouvons affirmer avec confiance que l'avenir du calcul parallèle haute performance appartiendra aux clusters GPU.