Calcul à hautes performances et algèbre linéaire

MIMD (Multiple Instructions Multiple Data) 

Ce mode est utilisé dans les machines multi-processeurs, où plusieurs processeurs exécutent différentes instructions sur différentes données. Plus tard, cette classification a été complétée par les deux sous-catégories suivantes du mode MIMD : — SPMD (Single Program Multiple Data) : Un même programme (code) est exécuté par les processeurs, mais les instructions effectuées par chaque processeur peuvent varier. On trouve ce mode dans les processeurs graphiques. — MPMD (Multiple Programs Multiple Data) : On rencontre ce mode par exemple sur un processeur bi-cœur, où on exécute un programme différent sur chaque cœur. Dans la figure 2.1, nous illustrons le fonctionnement des modes SISD, SIMD et SPMD sur des programmes (écrits en pseudo-code), où on traite un tableau d’entiers. Dans la sous-figure 2.1a, il y a un traitement purement séquentiel (SISD). Dans la sous-figure 2.1b, les mêmes instructions sont effectuées en parallèle sur les éléments du tableau (SIMD). Dans la sous-figure 2.1c, le même programme n’exécute pas les mêmes instructions, parce que nous avons ajouté un test (SPMD).

Architectures appropriés à notre type d’algèbre linéaire

 Dans cette section, nous allons réfléchir sur les caractéristiques que doit satisfaire une architecture appropriée à notre contexte applicatif d’algèbre linéaire. Nous avons mentionné à la sous-section 1.4.5 que notre problème est la résolution d’un système linéaire grand et creux sur un grand corps fini (voir section 3.2 pour plus de détails sur les caractéristiques des entrées). La 25 Chapitre 2. Calcul à hautes performances (HPC) brique de base du calcul d’algèbre linéaire, si l’on utilise des algorithmes boîte noire comme ce sera le cas de ceux présentés au chapitre 3, est l’opération de multiplication de la matrice creuse par un vecteur ou par un bloc de vecteurs. Nous avons besoin d’une architecture qui exploite différents niveaux du parallélisme (voir section 3.3). L’architecture doit satisfaire les critères suivants : 1. La taille importante de la matrice et des vecteurs fait que nous avons besoin de pouvoir stocker et traiter d’une manière efficace des données dont les tailles peuvent atteindre quelques dizaines de gigaoctets. 2. La matrice est creuse, avec des zones très creuses. Ceci fait que les accès sur le ou les vecteurs d’entrée risquent d’être irréguliers. C’est pourquoi nous avons besoin de mémoires et de mécanismes de cache qui permettent de limiter les pénalités dues à l’irrégularité des accès. 3. Les opérations arithmétiques sont effectuées sur un grand corps fini. Il est important que l’architecture logicielle permette d’écrire des briques de calcul arithmétique spécifiques et efficaces. De plus, cette arithmétique peut être accélérée en utilisant une représentation qui exploite la vectorisation (voir chapitre 6). 4. Si nous envisageons de distribuer l’algèbre linéaire sur un cluster de machines, les calculs ne peuvent pas être complètement indépendants et sont donc amenés à partager des données de taille importante. C’est pourquoi nous avons besoin d’un réseau et de mécanismes de communication efficaces en terme de latence et de débit pour minimiser les coûts de communication. Nous pourrons aussi mettre en place un parallélisme de tâches, et dans ce cas, nous aurons besoin d’un modèle approprié. À partir de cette description, nous concluons que les circuits configurables ne sont pas appropriés à cause de leur mémoire limitée (le critère 1 est non satisfait). Par contre, les CPU munis de plusieurs cœurs et d’unités vectorielles, ainsi que des accélérateurs de type GPU ou processeur many-cœurs se positionnent comme des architectures appropriées (les critères 1, 2 et 3 sont satisfaits ; le critère 1 peut être contraignant pour les GPU à partir de très grandes tailles). Dans le cadre de ce travail, nous allons étudier l’utilisation des CPU multi-cœurs et vectoriels et des GPU pour le problème d’algèbre linéaire. 

CPU multi-cœurs et vectoriels 

Un CPU multi-cœurs est un processeur qui contient deux cœurs ou plus gravés sur la même puce. Le premier processeur multi-cœur est apparu au milieu des années 80 avec le CPU bi-cœur de Rockwell International. Dès le début des années 2000, différents constructeurs tels que IBM, AMD, Intel ont commencé à commercialiser des processeurs multi-cœurs. L’idée d’introduire plusieurs unités de calcul dans un même processeur permet d’implémenter physiquement le multiprocessing et répond à la problématique du besoin continu d’augmenter la fréquence du CPU. Un processeur vectoriel est un processeur pourvu d’instructions vectorielles, c’est-à-dire d’instructions appropriées au traitement parallèle de données d’un bloc de taillé fixée, qu’on appelle vecteur. Par le passé, les architectures vectorielles ont été développées pour les supercalculateurs, par exemple pour les machines Cray et ILLIAC. De nos jours, la vectorisation est exploitée dans les processeurs incorporant des instructions SIMD, par exemple dans tous les processeurs Intel à partir du Pentium III, dans les processeurs POWER de IBM et également dans le processeur CELL de la PlayStation 3. 

Programmation sur les GPU 

Modèle CUDA Dans le cadre de ce travail, nous allons considérer les microprocesseurs de type x86 et les jeux d’instructions SIMD suivants : — SSE (Streaming SIMD Extensions) qui fournit des registres 128 bits ; — AVX (Advanced Vector Extensions) qui fournit des registres 256 bits. Un registre SSE peut contenir 2 composantes 64 bits et exécuter deux instructions en parallèle, il peut aussi être configuré de sorte à contenir 4 composantes, sur 32 bits chacune. Un registre AVX peut contenir 4 composantes 64 bits ou 8 composantes 32 bits. 2.3 Programmation sur les GPU : Modèle CUDA Dans ce travail, nous allons nous restreindre aux plate-formes NVIDIA et nous allons utiliser le modèle de programmation CUDA. Le nom CUDA (Compute Unified Device Architecture) désigne l’architecture matérielle et logicielle spécifique aux GPU NVIDIA et qui permet d’exploiter leur capacité de traitement massivement parallèle pour des tâches plus génériques que les traitements graphiques et qui vont s’étendre à des applications de calcul scientifique, de simulation, etc. Cette orientation vers l’utilisation du processeur graphique pour des applications pas nécessairement graphiques est communément désignée par l’acronyme GPGPU (General-purpose Processing on Graphics Processing Units), qu’on traduirait par le calcul généraliste sur processeurs graphiques. CUDA met à disposition de programmeurs grand public une plate-forme de calcul parallèle qui supporte conjointement les langages C, C++ et Fortran. Il existe aussi des interfaces pour d’autres langages telles que PyCUDA pour Python, jCUDA pour Java, etc. La description qui suit, ainsi que le travail présenté dans ce mémoire, sont basés sur le modèle de programmation de CUDA, parce que nous allons nous limiter aux plate-formes NVIDIA. Néanmoins, il est possible d’utiliser d’autres modèles de programmation, en l’occurrence celui de OpenCL [OpenCL]. OpenCL propose un modèle de programmation multi-plateforme qui cible plusieurs systèmes parallèles hétérogènes tels que les GPU (NVIDIA, AMD, Intel, etc), les CPU multi-cœurs et les processeurs CELL de la PlayStation 3. Le modèle CUDA est assez largement décrit dans la littérature [SK10, CUDAa] et des plateformes de documentation en ligne lui sont consacrées 2, 3 . 

Architectures considérées

 Les cartes graphiques NVIDIA sont classées selon leur architecture. L’architecture correspond à des évolutions chronologiques de la structure et de l’organisation matérielles du GPU et du modèle de programmation qui permet de l’utiliser. Dans le cadre de ce travail, nous avons eu accès à différents modèles de cartes graphiques qui appartiennent à deux architectures : — Fermi [Fermi] ; — Kepler [Kepler]. Pour distinguer les révisions d’une architecture, NVIDIA utilise un identifiant numérique appelé compute capability, de la forme x.y, où x désigne l’architecture (par exemple 2 pour Fermi et 3 pour Kepler) et y désigne la révision [CUDAa]. À titre d’exemples, nous trouvons pour l’architecture Fermi les compute capabilities 2.0 et 2.1 et pour l’architecture Kepler les compute capabilities 3.0, 3.5 et 3.7. Les cartes que nous utilisons sont soit de compute capability 2. NVIDIA CUDA ZONE : https://developer.nvidia.com/cuda-zone 3. GTC On-Demand : http://on-demand-gtc.gputechconf.com/gtcnew/on-demand-gtc.php 27 Chapitre 2. Calcul à hautes performances (HPC) 2.0 soit de compute capability 3.0. Les mécanismes et les spécifications que nous allons décrire dans la suite référent à ces deux compute capability. Nous utilisons les cartes suivantes : — GeForce GTX 580 (Fermi, compute capability 2.0) ; — Tesla M2050 (Fermi, compute capability 2.0) ; — GeForce GTX 680 (Kepler, compute capability 3.0). Il existe une autre classification des cartes graphiques NVIDIA selon la gamme : GeForce, Quadro et Tesla. La gamme GeForce est une gamme « grand public » destinée principalement au marché des jeux vidéo. La gamme Quadro est destinée aux « professionnels » et cible des applications de type CAO (Conception Assistée par Ordinateur). La gamme Tesla a été conçue pour des applications de calcul scientifique, en fournissant des fonctionnalités spécifiques telles que les codes ECC (Error Correction Codes) qui certifient l’exactitude des calculs et la fonctionnalité Direct GPU qui améliore les communications. Contrairement à la classification selon l’architecture, la classification selon la gamme est peu pertinente dans notre contexte. 

Modèle d’exécution

 Le CPU qui est connecté au GPU et qui le contrôle est appelé hôte (host). Le GPU est désigné par le terme périphérique (device). Un programme CUDA est composé d’un code exécuté sur l’hôte et d’un code exécuté sur le périphérique. Le code exécuté sur le périphérique est composé de fonctions, appelés kernels, qui lorsqu’elles sont appelées sont exécutées plusieurs fois en parallèle par plusieurs threads CUDA en suivant le mode SPMD (Single Program, Multiple Data). L’exécution typique d’un programme CUDA qui lance un seul kernel est composée des actions suivantes, qui sont spécifiées explicitement par le programmeur dans le code, qui exploite à ces fins des appels de l’interface CUDA (voir figure 2.2) : 1. créer des données sur la mémoire de l’hôte ; 2. transférer les données vers la mémoire du périphérique ; 3. lancer un kernel depuis le CPU ; 4. exécuter le kernel en parallèle sur le GPU ; 5. synchroniser le GPU et le CPU ; 6. copier les résultats vers la mémoire du CPU.