Partie 1 Architectures parallèles

1Chapitre 1

1) Introduction :L’architecture des ordinateurs, qu’il s’agisse de microprocesseurs ou de

supercalculateurs, est fortement influencée par l’exploitation d’une propriété fondamentale des applications : le parallélisme. Un grand nombre d’architectures présentes dans les sites informatiques sont parallèles. Ce type d’architecture touche une large gamme de machines depuis les PC biprocesseurs jusqu’aux supercalculateurs. Aujourd’hui, la plupart des serveurs sont des machines parallèles (des multiprocesseurs).

L’exploitation du parallélisme dans l’architecture des ordinateurs est née de la conjonction de trois éléments : les besoins des applications, les limites des architectures séquentielles et l’existence dans les applications de la propriété de parallélisme.

1.1.1 Besoins des applications :La notion de parallélisme est souvent attachée à celle de la performance d’exécution des applications. Ce dernier terme recouvre différentes notions suivant les besoins des applications. En effet, quel que soit le domaine d’application, le parallélisme peut être exploité pour répondre à deux besoins : la puissance de traitement et/ou la disponibilité.

La puissance de traitement recouvre deux grandes notions : la latence de traitement et le débit de traitement. La latence représente le temps nécessaire pour l’exécution d’un traitement. Le débit représente le nombre de traitements exécutables par unité de temps.

1.1.2 Limites de l’approche microprocesseur : L’utilisation simultanée de plusieurs ressources entraîne la nécessité de gérer la coordination de ces ressources et complexifie la programmation.

Aussi, l’exploitation du parallélisme ne peut se concevoir qu’en réponse aux limitations de l’exécution séquentielle. Les ordinateurs séquentiels (équipés d’un seul processeur) sont construits autour des microprocesseurs. La standardisation de ce composant fait queles caractéristiques des différents microprocesseurs sont très semblables. Les limites de l’exécution séquentielle découlent donc des limites des microprocesseurs actuels : performance intrinsèque, temps et débit d’accès à la mémoire. Le parallélisme permet aussi de pallier le problème de la limite de capacité d’accès d’un microprocesseur à la mémoire en multipliant les bancs mémoire. Il permet de proposer une réponse au problème de la tolérance aux pannes, en introduisant de la redondance et en éliminant le point de défaillance unique qui existe lorsque l’architecture ne comporte qu’un seul processeur. La principale motivation est la limite en performance des micro-processeurs. L’objectif de 1 téraFlops avant l’an 2000 ne peut être atteint par un microprocesseur même si l’évolution des performances des microprocesseurs depuis 1985 suit une courbe exponentielle dans le temps. Les microprocesseurs possèdent aussi d’autres limites comme l’inadéquation de leur format de données et de leurs opérations aux caractéristiques de certaines applications telles que le traitement d’images ou la comparaison de séquences biologiques. Il peut être préférable, en termes de performance, de coût et de compacité ,d’avoir recours à une réalisation parallèle spécifique ; c’est-à-dire de concevoir un ordinateur dont les opérateurs de traitement, l’organi-

2Chapitre 1

sation mémoire, etc. sont adaptés aux calculs à réaliser. Toutefois, il faut remarquer que les solutions spécifiques sont vite concurrencées par des standards lorsqu’il existe un marché suffisamment large. Ainsi, les nouveaux microprocesseurs intègrent des unités fonctionnelles spécialisées et de nouveaux jeux d’instructions(MMX, Acti-Vect, etc.) pour répondre aux besoins des applications de traitement d’images.

1.1.3 L’existence dans les applications de la propriété de parallélisme : Parallélisme de données:

la même opérations est réalisée par plusieurs processeurs sur des données différentes: exemple : addition de deux matrices.

Parallélisme de contrôle:

Des opérations différentes sont réalisées simultanément.

Indépendance /dépendance du flot (architecture pipeline: dupliquer les unités de traitements).

1.2 Définition :

Les ordinateurs parallèles sont des machines qui comportent une architecture parallèle, constituée de plusieurs processeurs identiques, ou non, qui concourent au traitement d'une application. La performance d'une architecture parallèle est la combinaison des performances de ses ressources et de leur agencement. (Latence, débit).

Architectures parallèles ce résume en :

pas de limite de mémoire. pas de limite de processeurs. accélération des calculs complexes ou coûteux en temps d'occupation CPU(calcul matriciel,

simulation numérique, transformée de fourier...). calcul répétitif sur un large ensemble de données structuré. traitement indépendant.

1.3 Limites du parallélisme : les dépendances de données :

Les instructions doivent être indépendante c’est-à-dire, exécuter dans un ordre quel conque et simultanément.

3Chapitre 1

Les dépendances de contrôle :

les dépendances de ressources :

Nombre insuffisant de processeurs pour effectuer les instructions en parallèle alors qu'elles sont indépendantes les unes des autres.

rapport temps de communication / temps de calcul :

Il n'est pas toujours avantageux de paralléliser une application. Les communications peuvent dans certain cas augmenter le temps d'exécution.

4Chapitre 1

5Chapitre 2

2) Les architectures parallèles :

Afin de définir et comparer les architectures de machines, plusieurs classifications ont été développées.

2.1 Classification de Flynn :La classification la plus connu et celle de Flynn, qui caractérise les machines suivants leurs flot de données et instructions, ce qui donne quatre catégories :

SISD (<< Single Instruction stream, Single Data stream >>). Cette catégorie correspondAux machines séquentielles conventionnelles, pour lesquelles chaque opération s'effectue sur une donnée à la fois.

FIG. 2.1

L’unité de contrôle (UC), recevant son flot d’instruction (FI) de l’unité mémoire (UM), envoie les instructions à l’unité de traitement (UT), qui effectue ses opérations sur flot de données (FD) provenant de l’unité mémoire.

MISD (<< Multiple Instruction stream, Single Data stream >>). Cette catégorie

Regroupe les machines spécialisées de type < systolique >, dont les processeurs, arrangés selon une topologie fixe, sont fortement synchronisées.

FIG. 2.2

6Chapitre 2

SIMD (<< Single Instruction stream, Multiple Data stream >>). Dans cette classe d'architectures, les processeurs sont fortement synchronisés, et exécutent au même instant la même instruction, chacun sur des données différentes. Des informations de contexte (bits de masquage) permettent d'inhiber l'exécution d'une instruction sur une partie des processeurs.

FIG. 2.3Ces machines sont adaptées aux traitements réguliers, comme le calcul matriciel sur matrices pleines ou le traitement d'images. Elles perdent en revanche toute efficacité lorsque les traitements à effectuer sont irréguliers et dépendent fortement des données locales, car dans ce cas les processeurs sont inactifs la majorité du temps.Ainsi, pour exécuter une instruction conditionnelle de type if. . . then. . . else , l'ensemble des instructions des deux branches doit être présenté aux processeurs, qui décident ou non de les exécuter en fonction de leur bit local d'activité, positionné en fonction des valeurs de leurs variables locales.Chacun des processeurs n'exécutera effectivement que les instructions de l'une des branches.

FIG. 2.4

MIMD (<< Multiple Instruction stream, Multiple Data stream >>). Cette classe comprend les machines multi-processeurs, ou chaque processeur exécute son propre code de manière

7Chapitre 2

asynchrone et indépendante. On distingue habituellement deux sous-classes, selon que les processeurs de la machine ont accès à une mémoire commune (on parle alors de MIMD a mémoire partagée, << multiprocessor>>) .ou disposent chacun d'une mémoire propre (MIMD a mémoire distribuée, <<multicomputer>>).Dans ce dernier cas, un réseau d'interconnexion est nécessaire pour échanger les informations entre processeurs.

Cette classification est trop simple, car elle ne prend en compte ni les machines vectorielles (qu'il faut ranger dans la catégorie SISD et non pas SIMD, car elles ne disposent que d'un seul flot mémoire), ni les différences d'architecture mémoire.

8Chapitre 2

2.2 Classification de Raina :Une sous-classification étendue des machines MIMD, due à Raina, et illustrée En Figure 2.7, permet de prendre en compte de manière fine les architectures mémoire, selon deux critères :

l'organisation de l'éspace d'adressage :

SASM (<< Single Address space, Shared Memory >>): memoire partagée. DADM (<< Distributed Address space, Distributed Memory >>) : mémoire distribuée,

sans accès aux données distantes. L'échange de données entre processeurs s'effectue nécessairement par passage de messages, au moyen d'un réseau de communication ;

SADM (<< Single Address space, Distributed Memory >>) : mémoire distribuée, avec espace d'adressage global, autorisant éventuellement l'accès aux données situées sur d'autres processeurs.

le type d'accès mémoire mis en œuvre :

NORMA (« No Remote Memory Access ») : pas de moyen d'accès aux Données distantes, nécessitant le passage de messages ; UMA (« Uniform Memory Access » ) : accès symétrique à la mémoire, de cout identique pour tous les processeurs ; NUMA (« Non-Uniform Memory Access ») : les performances d'accès dépendent de la localisation des données ; CC-NUMA (« Cache-Coherent NUMA ») : type d'architecture NUMA Intégrant des

caches ; OSMA (« Operating System Memory Access ») : les accès aux données distantes sont

gérées par le système d'exploitation, qui traite les défauts de page au niveau logiciel et gère les requêtes d'envoi/copie de pages distantes ;

COMA (« Cache Only Memory Access ») : les mémoires locales se comportent comme des caches, de telle sorte qu'une donnée n'a pas de processeur Propriétaire ni d'emplacement déterminé en mémoire.

9Chapitre 2

2.3 Exemple de machines parallèles :

Marvel : alpha EV7, 2 à 64 processeurs, 16 Go à 512 Go de mémoire. Tore 2D, 8 Go/s par processeur.Puissance : 2.4 Gflops/processeur.

NEC SX-6 : supercalculateur vectoriel, 8 teraflops, 64 Go de mémoire, 32 Gb/s Cray T3E : DEC alpha EV5, 600 Mflops, 16 à 2048 processeurs, 64 Mo à 2Go de mémoire,

réseau d'interconnexion en tore 3D (bande passante de 2 à 128 Go/s). SGI origin 3000 : numa, 2 à 1024 processeurs, 512 Mo à 1 To de mémoire, 0.8 à 1 Gflops HP superdome : 2.2 à 3 Gflops, 2 à 64 processeurs, 4 Go à 256 Go de mémoire, crossbar, 12 à

51 Go/s. IBM SP2 : Scalable POWERparallel, RS/6000 à 480 Mflops, 256 Mo de mémoire, ou 540

Mflops, 1 à 2 Go de mémoire vive. Communication par passage de messages à travers un réseau cross-bar à deux niveaux; bande passante de 150 Mo/s.

SP 4 : 4 à 5.2 Gflops, 1 à 32 processeurs par noeuds, 8, 16 ou 32 noeuds compaq ES45 : 1 à 2 Gflops, 4 processeurs EV68, 32 Go de mémoire, configuration

trucluster.

10Chapitre 2

Partie 2 Cuda : Compute Unified Device Architecture

Plan :

Qu’est-ce que CUDA ? GPU Computing CUDA Caractéristiques GPU / CPU Traitement parallèle avec CUDA Plateforme de traitement parallèle CUDA Informations complémentaire Un Cas d'utilisation

11Chapitre 2

1. Qu’est-ce que CUDA ?CUDA est une architecture de traitement parallèle développée par NVIDIA permettant de décupler les performances de calcul du système en exploitant la puissance des processeurs graphiques (GPU).

Alors que des millions de GPU compatibles avec CUDA ont été vendus, des milliers de développeurs de logiciels, de scientifiques et de chercheurs utilisent CUDA dans une grande gamme de domaines, incluant notamment le traitement des images et des vidéos, la chimie et la biologie par modélisation numérique, la mécanique des fluides numérique, la reconstruction tomodensitométrique, l’analyse sismique, le ray tracing et bien plus encore.

2. GPU Computing CUDA :

2.1 Caractéristiques GPU / CPU :

Processeur graphique :Un processeur graphique, ou GPU (de l'anglais Graphics Processing Unit) est un circuit intégré présent sur une carte graphique et assurant les fonctions de calcul de l'affichage. Un processeur graphique a généralement une structure hautement parallèle qui le rend efficace pour une large palette de tâches graphiques comme le rendu 3D, en Direct3D, en OpenGL, la gestion de la mémoire vidéo, traitement du signal vidéo, décompression Mpeg, etc.

Voici un tableau vous présentant les différences entre les taches réalisées par le GPU et le CPU :

Le GPU travaille avec des données vectorielles, alors que le CPU travaille avec toutes types de données.

12Chapitre 2

Architecture des GPU et CPU : Nous allons vous présenter la différence entre l'architecture d'un processeur graphique, d'un processeur central. Le schéma suivant permet de mieux comprendre.

Les CPU sont conçus pour tirer un maximum de performances d'un flux d'instructions, leurs traitements sont majoritairement effectués sur des données diverses (entier, flotant), les accès à la mémoire sont aléatoires et, dans un souci de sécurité, celui-ci effectue de nombreux branchements. Depuis un certain nombre d'années, nous pouvons voir que les architectures des processeurs sont construites pour paralléliser le maximum d'instructions simultanément. Ils possèdent un grand nombre de mémoire caché pour accélérer les accès.

Le travail des GPU consiste à prendre un ensemble de données, les polygones, et de créer un ensemble de pixels à partir des polygones. Nous pouvons voir que les deux ensembles sont indépendants, et peuvent être traités simultanément. C'est pourquoi, nous pouvons voir que le GPU comporte un grand nombre d'ALU et non de mémoire. Nous pouvons également voir que le nombre d'unité de contrôle est faible, cela vient du fait qu'aucune sécurité n'est mise en place pour accélérer les calculs. Les vérifications effectuées sont le dépassement de mémoire ou les opérations non autorisées, comme la division par 0.

13Chapitre 2

Puissance de calcul :Le nombre de FLOPS est une mesure commune de la vitesse d'un système informatique. Un FLOP signifie une opération à virgule flottante par seconde.

D'aprés ce graphique, nous pouvons voir qu'avant la sortie du GPU Computing, et plus précisément CUDA, la puissance des GPU et CPU étaient semblables. Après la présentation des outils de NVidia, les constructeurs ont entrepris d'améliorer les performances des cartes graphiques pour attirer un nouveau public, voulant utiliser la puissance des GPU. De plus, nous pouvons voir que la puissance des CPU reste relativement constante, à cause de problèmes matériels, tels que la température croissante causant l'endommagement des composants (Il y a 10 ans, la finesse de gravure était de 96 nm, actuellement elle est de 32 nm. Cela permet un meilleur refroidissement, et ainsi une plus basse consommation calorifique).

Présentation de l'API CUDA :

Composant de l'API :

L'API CUDA se compose en trois parties :

14Chapitre 2

Runtime : C'est l'interface entre le GPU et l'application, en fournissant quelques automatismes.

Driver : Son rôle est de transmettre les calculs de l'application au GPU. Librairies : CUDA est livré avec les implémentations de l'algorithme BLAS et FFT,

optimisée pour cette architecture.

Vocabulaire :

Un certain vocabulaire est associé au développement sur GPU, je vais vous en faire la liste dans les lignes suivantes.

L'hôte est le CPU, c'est lui qui demande au périphérique (le GPU) d'effectuer les calculs.

Un kernel est une portion parallèle de code à exécuter sur le périphérique. Chacune de ses instances s'appelle un thread.

Une grille est constituée de blocs. Chaque bloc est constitué de threads.

Un bloc est un élément des calculs, dissociable des autres blocs : les blocs ne doivent donc pas être exécutés dans un certain ordre : parallèlement, consécutivement ou toute autre combinaison est possible. C'est pourquoi les threads ne peuvent communiquer qu'avec des threads du même bloc. Un thread est exécuté par un processeur : posons donc l'égalité entre le thread et le processeur. Ainsi, le bloc est le multiprocesseur, tandis que la grille représente l'entièreté de la carte.

15Chapitre 2

Architecture Matérielle :

Présentation :L'architecture matérielle, c'est à dire la carte graphique, est composée en deux grandes entités :

Multiprocesseur : ces processeurs implémentent le modèle d'exécution SMIT (single instruction, multiple thread).

Ils sont constitués de plusieurs processeurs exécutant chacun une instance de kernel (thread).

Mémoires : il en existe plusieurs types que nous allons présenter dans la section suivantes.

Mémoire :Dans cette partie, nous allons vous présenter les différents types de mémoire qui composent le matériel. Nous irons de la mémoire la moins rapide, c'est à dire celle qui est en plus grande quantité, jusqu'à la mémoire la plus rapide, celle qui est plus couteuse.

16Chapitre 2

Mémoire globale : Cette mémoire est accéssible à l'ensemble des multiprocesseurs. Sa bande passante est trés importante, environ 150 Go/s, cependant sa latence est importante. Lorsque vous achetez une carte graphique, la capacité de mémoire indiquée fait référence à ce type de mémoire

Mémoire partagée : Cette mémoire est propre à un multiprocesseur .Sa latence est plus faible que la mémoire globale, au détriment de sa taille qui est de environ 8Mo.

Les registres : Cette mémoire est propre à un processeur, son accès est rapide, environ 1 cycle, mais sa taille est réduite, environ 8 Ko.

Les textures : Cette mémoire est propre à un multiprocesseur, et offre des mécanismes d'accélération. Elle permet de stocker les textures, comme dans un jeux et évite certains accès au disque.

Autre : Il existe d'autres types de mémoire en fonction de la carte graphique, et du niveau d'ancienneté du périphérique.

3. Traitement parallèle avec CUDALe calcul informatique a évolué en passant du traitement central exclusif des CPU vers les capacités de co-traitement offertes par l’association du CPU et du GPU. Pour permettre ce nouveau paradigme informatique, NVIDIA a conçu l’architecture de traitement parallèle

17Chapitre 2

CUDA, aujourd’hui incluse dans les GPU GeForce, ION Quadro, et Tesla en offrant ainsi une base matérielle significative aux développeurs d’applications.

Du côté du grand public, la plupart des applications majeures de traitement vidéo, incluant des produits d’Elemental Technologies, MotionDSP et LoiLo, Inc, sont ou seront bientôt accélérées par CUDA.

Du côté de la recherche scientifique, CUDA a été reçu avec enthousiasme. CUDA permet par exemple d’accélérer AMBER, un programme de simulation de dynamique moléculaire utilisé par plus de 60 000 chercheurs du public et du privé afin d’accélérer la découverte de nouveaux médicaments pour l’industrie pharmaceutique.

En matière de finance, Numerix et CompatibL ont annoncé leur support de CUDA pour une nouvelle application de recherche de risques de contrepartie, accélérant jusqu’à 18x les procédures de calcul existantes. La plateforme Numerix est utilisée par plus de 400 institutions financières.

Le parc existant de GPU Tesla, offrant d’importantes capacités en matière de calcul par le GPU, permet également de jauger le succès de CUDA. Plus de 700 clusters de GPU sont aujourd’hui actifs dans le monde entier. De nombreux groupes, allant de Schlumberger et Chevron (secteur énergétique) à BNP Paribas (secteur banquier) et figurant dans la liste des « 500 entreprises les plus importantes au monde » publiée par Fortune, ont adopté CUDA.

Depuis l'avènement de Windows 7 de Microsoft et de Snow Leopard d’Apple, le calcul par le GPU est également une réalité pour le grand public. Dans ces nouveaux systèmes d’exploitation, le GPU ne tiendra pas seulement lieu de processeur graphique, il jouera également un rôle de processeur parallèle pour toutes les applications.

4. PLATEFORME DE TRAITEMENT PARALLÈLE CUDALa plateforme CUDA inclut des extensions C et C++ qui permettent l’expression de données denses et complexes dans un contexte de parallélisme.

Les programmeurs peuvent choisir d’exprimer le parallélisme avec des langages à hautes performances comme C, C++, Fortran ou avec des standards ouverts comme les directives OpenACC.

La plateforme de calcul parallèle CUDA est aujourd’hui déployée dans des milliers d’applications accélérées par les GPU et elle est présentée dans plus de 1000 dossiers de recherche.

18Chapitre 2

5. Informations complémentaire

Compilation :La compilation est réalisée grâce au compilateur NVCC, fournie dans le toolkit de CUDA. Celui-ci génere deux fichiers contenant du code assembleur :

Le premier contient l'ensemble des instructions pour le processeur central, CPU : CPU Code.

Le second fichier contient l'ensemble des instructions pour la carte graphique, GPU : PTX Code.

Pour utiliser la technologie, vous devez installer les éléments suivants :

Driver Spécifique Nvidia : permet d'exploiter les fonctionnalités CUDA de votre hardware. Toolkit : générer l'ensemble des exécutables grâce au compilateur NVCC

19Chapitre 2

6. Un cas d’utilisation :

CRarK :

cRARk est un utilitaire en ligne de commande conçu pour retrouver les mots de passe oubliés des archives RAR des versions 2.x à 3.x. Le programme teste les combinaisons possibles en utilisant des mots de passe définis à partir de liste ou de dictionnaire. L'application exploite la technologie NVIDIA CUDA qui rend les phases de calculs beaucoup plus rapides.

Les tests suivants ont été réalisés : Décodage d'un mot de passe de longueur 4 caractéres alpha-numérique sur le GPU Décodage d'un mot de passe de longueur 4 caractéres alpha-numérique sur le CPU Décodage d'un mot de passe de longueur 5 caractéres alpha-numérique sur le GPU Décodage d'un mot de passe de longueur 5 caractéres alpha-numérique sur le CPU

Ces tests permettent de démontrer la puissance de calculs des cartes graphiques actuelles.

La configuration de test est la suivante :

intel i5 750 @3.4 GHZ 8Go DDR3 1600MhZ Nvidia 560 GTX 1Go

Nous pouvons voir que le décodage sur GPU est beaucoup plus rapide que sur le CPU. Lorsque le mot de passe est de 3 caractères, le gain est minime, cependant, lorsque le mot de passe est de 4 caractères, le temps de calcul est réduit d'environ 200 pourcents.

Cette application n'est pas optimisée pour traiter des mots de passe de plus de 10

20Chapitre 2

caractères. De plus, ce logiciel exploite la version 2.0 de CUDA, alors que la version actuelle est 4.2. Je pense que de nombreuses améliorations peuvent être apportées.

Bibliographie :

Partie 1 : Architecture Paralélle

21Chapitre 2

1) cours de Aurélia Marchand –les architectures parallèles.2) Introduction de parallelisme et au architectures paralleles-

Sciences_de_L_Ingenieur3) Architectures et Systèmes de Calculateurs Parallèles- François PELLEGRINI

ENSEIRB

Partie 2 : Cuda

1) http://www.nvidia.fr/object/gpu-computing-fr.html2) Compute Unified Device Architecture — Wikipédia.html3) http://www-igm.univ-mlv.fr/~dr/XPOSE2011/CUDA/index.html