Architectures Parallèles et Distribuées

TOP 500 : 06-17

1. Classification de Flynn

Plusieurs classifications des architectures parallèles ont été proposées dans la littérature. La

plus référencée est celle de Flynn qui se base essentiellement sur le couple ﬂot d’instructions,

ﬂot de données (multiples ou simples) d’où l’obtention des quatre classes suivantes

résumées dans le tableau 1-1 :

 SISD (Single Instruction stream, Single Data stream)

Une machine SISD (dénommée machine séquentielle de von Neumann) utilise un flot

d’instructions unique traitant un flot de données unique aussi.

 SIMD (Single Instruction stream, Multiple Data stream)

Une machine SIMD appelée (appelée aussi tableau de processeurs, en Anglais Array

processor) comporte un seul séquenceur (dénommé aussi unité de contrôle) dirigeant les

autres processeurs, plus particulièrement les unités de calcul lors de l’exécution d’opérations

logiques et arithmétiques. Dans cette machine dénommée aussi machine vectorielle, toutes

les unités de calcul reçoivent la même instruction diffusée par l’unité de contrôle, mais qui

sera exécutée sur des données distinctes. En d’autres termes, chaque unité de calcul traite

une donnée qui lui est propre. D’une manière générale, l’exécution parallèle de la même

instruction se réalise simultanément sur des différents processeurs. On parle ici de

parallélisme de données synchrone. Il est à noter que lorsqu’une machine SIMD comprend

plus d’une unité de contrôle, elle sera de type multiple-SIMD.

 MISD (Multiple Instruction stream, Single Data stream)

Dans ce cas, plusieurs flots d’instructions sont appliqués au même flot de données. Notons

que ce type ne correspond à aucune machine réelle actuelle.

 MIMD (Multiple Instruction stream, Multiple Data stream)

Une machine MIMD comprend plusieurs processeurs dont chacun applique son propre ﬂot

d’instructions pour traiter le ﬂot de données qui lui correspond.

Flot de données Simple Multiple

Flot d’instructions

Simple

SISD

SIMD

Multiple MISD MIMD

Tableau 1-1 : Classification des architectures parallèles selon la taxonomie de Flynn

Figure 1-1 : Les classes de machines selon la taxonomie de Flynn

La figure 1-1 illustre les architectures des quatre classes selon la taxonomie de Flynn.

Notons que les machines les plus utilisées dans la plupart des applications scientifiques sont

celles de la classe MIMD dont fait partie l’architecture multicœurs que nous ciblons. Ainsi,

une étude plus raffinée de cette classe sera présentée dans la section suivante.

2. Classification des architectures parallèles selon la mémoire

Sachant que la plupart des architectures parallèles récentes font partie de la classe MIMD,

conséquemment, de nouvelles classifications plus fines ont été proposées. Ainsi, on définit

les trois sous-classes suivantes : les machines MIMD à mémoire partagée (MIMD-MP), les

machines MIMD à mémoire distribuée (MIMD-MD), et les machines MIMD à mémoire

hybride (MIMD-MH).

Les machines MIMD à mémoire partagée (MIMD-MP)

Les machines MIMD-MP utilisent une mémoire commune accédée par tous les processeurs

mais d’une façon indépendante. Bien qu’ils partagent la même mémoire, les processeurs

d’une telle machine peuvent exécuter des instructions distinctes. Ils existent divers modes

d’accès des processeurs à la mémoire partagée parmi lesquelles nous pouvons citer les trois

suivants : l’accès uniforme (UMA : Uniform Memory Access), l’accès non uniforme

(NUMA : Non Uniform Memory Access) et l’accès à la mémoire cache uniquement

(COMA : Cache-Only Memory Architecture). Ces modes d’accès sont détaillés dans ce qui

suit.

 Accès uniforme à la mémoire (UMA)

La mémoire commune est accessible par les processeurs via un réseau d’interconnexion

(voir figure 1-2). L’accès à la mémoire est équitable pour chaque processeur. Ainsi, il s’agit

de processeurs homogènes (i.e. identiques). En outre, la mémoire partagée est en général

divisée en modules dont chacun dispose de son propre bus d’entrées/sorties. C’est le

contrôleur de cache qui est responsable du dialogue processeur-mémoire cache tout en

assurant la cohérence des données chargées dans la mémoire.

Figure 1-2 : Architecture UMA d’une machine MIMD-MP

 Accès non uniforme à la mémoire (NUMA)

Dans cette architecture, chaque processeur dispose de son propre module de la mémoire

partagée. Ainsi, chacun accède à la mémoire indépendamment des autres (voir figure 1-3). Il

est à noter que les processeurs peuvent être hétérogènes (i.e. de fréquences différentes). Le

temps d’accès dépend alors du processeur. En pratique, une machine NUMA permet de

partager plusieurs données facilitant ainsi le développement des programmes. Toutefois, ceci

est coûteux du point de vue matériel vu que le nombre de processeurs que l’on peut connecter

à une mémoire commune demeure limité.

Figure 1-3 : Architecture NUMA d’une machine MIMD-MP

 Accès à la mémoire cache uniquement (COMA)

Dans ce type de machine, chaque processeur dispose d’une partie de la mémoire partagée

(voir figure 1-4), sauf que les données utilisées par un processeur sont toujours

communiquées à sa propre mémoire cache. La mémoire partagée est ainsi confondue à la

mémoire cache dont l’accès est géré par un contrôleur de cache.

Figure 1-4 : Architecture COMA d’une machine MIMD-MP

Les machines MIMD à mémoire distribuée (MIMD-MD)

Dans ce type de machines, chaque processeur possède sa propre unité de calcul ainsi que sa

propre mémoire. La communication des données inter-processeurs est réalisée en échangeant

des messages à travers un réseau d’interconnexion (voir figure 1-5). Généralement, les

processeurs sont reliés par un graphe complet d’interconnexion.

Sur les machines MIMD à mémoire distribuée, l’exécution des programmes parallèles

dépend principalement du temps de complétion (i.e. d’exécution) des tâches effectuées par

processeur, de l’emplacement du processeur en question dans le réseau et du type du réseau

d’interconnexion des points de vue topologie du réseau, latence et bande passante.

Figure 1-5: Architecture MIMD-MD

Les machines MIMD à mémoire hybride (MIMD-MH)

Pour profiter de l’importance du nombre de processeurs dans l’architecture à mémoire

distribuée et de la facilité de communication au sein d’une machine à mémoire partagée, de

nombreux concepteurs ont eu recours à l’hybridation de ces deux systèmes donnant lieu à

une machine partagée/distribuée (voir figure 1-6).

Il s’agit d’interconnecter divers machines MIMD à mémoire partagée pour obtenir ce qu’on

appelle une grappe. Celle-ci est formée de plusieurs nœuds liés par un réseau

d’interconnexion. Chaque nœud est constitué à son tour plusieurs processeurs accédant à une

mémoire partagée.

Figure 1-6 : Architecture MIMD à mémoire hybride

3. Grappes et grilles de calcul

La combinaison des différentes machines parallèles précédemment étudiées a donné

naissance à des architectures parallèles plus puissantes et performantes des points de vue

rapidité de transfert des données inter-processeurs, croissance du volume de données traitées

simultanément et cohérence des données dans des réseaux d’interconnexion assez étendus

géographiquement. Parmi ces systèmes parallèles puissants, citons les grappes de calcul ainsi

que les grilles de calcul.

- Grappes (Clusters) Une grappe (cluster) n’est pas une machine parallèle unique au sens classique mais est constitué d’un ensemble de nœuds (machines monoprocesseurs, processeurs multi-cœurs ou SMP) interconnectés par un réseau local et (souvent) rapide. C’est donc une réseau d’ordinateurs en général de caractère homogène. Un des objectifs principaux d’un grappe est de fournir un environnement à image d’un système unique pour des applications destinées au cluster. Souvent, on lui associe pour cela un système de mémoire virtuelle partagée. Par sa nature, un cluster/grappe est composé uniquement de composants standards et possède ainsi un très bon ratio coût/performance. En plus, il est facilement extensible et est devenue une des architectures parallèles les plus répandues aujourd’hui. La différence entre un cluster et un MPP décroît de plus en plus. L’existence d’environne- ments adaptés permet aujourd’hui d’arriver à un cluster de même puissance de calcul qu’un serveur parallèle MMP ou SMP qui sont beaucoup plus chers.

Les principaux composants d’un cluster d’ordinateurs sont les suivants :

- Plusieurs ordinateurs de haute performance (PCs, stations de travail, ou SMPs) - Systèmes d’exploitation - Réseaux/Switchs haute performance (e.g. Gigabit Ethernet et Myrinet) - Cartes Interface Réseau - Protocoles et Services de Communication rapides (tels que Active et Fast Messages) - - Environnements et outils de programmation parallèle (tels que des compilateurs,

Intergiciel Cluster

PVM (Parallel Virtual Machine), MPI (Message Passing Interface))

- Applications (séquentielles, parallèles ou distribuées)

Grappes de PC

– Grilles (Grids) Une grille est un ensemble de grappes interconnectées entre elles par des réseaux de très haut débit. C’est une architecture très hétérogène puisque les matériels et les systèmes qui la constituent peuvent être très disparates. Citons ici, à titre d’exemple, le projet fédérateur d’une grille pour la recherche en France, appelé Grid 5000.

4. Grilles et Systèmes P2P

Définition et Architecture générale d’une grille de calcul (GRID)

Grid signifie littéralement ‘grille’. Une grille peut être vue comme un environnement informatique et de collaboration sans frontière. Les grilles de calcul permettent d’utiliser les cycles CPU durant lesquels les machines sont inactives pour exécuter une application. Les capacités de stockage des différents utilisateurs sont les ressources agrégées au sein de la grille. Une caractéristique importante des grilles de calcul est de fournir une importante capacité pour le calcul parallèle. Les domaines académique et industriel utilisent énormément de telles capacités. Les ressources partagées rendent possible l’accès à des ressources spéciales et des logiciels dont le prix de licence est élevé. Il s’agit d’une mise en commun des ressources logicielles et matérielles. En raison de la disponibilité d’importantes quantités

de ressources, si certaines ressources deviennent inaccessibles localement, la continuité du service reste assurée. Une des caractéristiques de la grille de calcul est qu’elle se base sur le ‘Push model’, c'est-à- dire qu’il y a un coordinateur qui est responsable du partage du travail sur les différentes ressources. Elle est aussi généralement symétrique, c'est-à-dire qu’un nœud de la grille peut être à la fois consommateur et producteur. L’architecture générale d’une grille peut être décomposée en quatre couches. La première correspond à l’infrastructure matérielle. Elle contient les ressources interconnectées au travers des réseaux. Elle comprend des PCs, des systèmes de stockage, des bases de données, etc. La seconde couche comporte les intergiciels de niveau noyau. Elle offre des services de noyau tels que le contrôle de processus à distance, la co-allocation des ressources, l’accès aux stockages, l’enregistrement de l’information, les mécanismes de sécurité, etc. La troisième couche contient les intergiciels de niveau utilisateur. Elle regroupe tous les outils qui peuvent aider les développeurs à écrire des applications pouvant tourner sur la grille de calcul. On y trouve ainsi des compilateurs, des librairies, des outils de conception d’applications, etc. La dernière couche, appelée couche applications, regroupe les applications utilisateurs comme les projets scientifiques, médicaux, d’ingénierie, etc.

Classification des systèmes de grilles de calcul

Les systèmes de grilles de calcul peuvent être employés pour fournir les services suivants:

 Services calcul (Computational Services)

Il s’agit de fournir des services sécurisés pour exécuter les tâches des applications sur les ressources informatiques distribuées. Quelques exemples de grilles informatiques sont NASA IPG, World-Wide Grid, et NSF TeraGrid.

 Services données (Data Services)

Ils cherchent à permettre le transfert sécurisé aux ensembles de données distribuées et à leur gestion. Un exemple d’application qui a besoin d’un tel service pour la gestion, le partage et le traitement de grands ensembles de données est la Physique des Hautes Energies.

 Services application (Application Services)

Ceux-ci ont pour objectif de gérer des applications et de fournir un accès à distance aux logiciels et aux bibliothèques d’une manière transparente. Un exemple qui peut être employé pour développer de tels services est NetSolve.

 Services information (Information Services)

Ceux-ci se spécialisent dans l’extraction et la présentation des données significatives en employant les services données et application.

 Services connaissance (Knowledge Services)

Ils se focalisent sur la manière d’acquérir, d’employer, de rechercher, d’éditer, et de maintenir des connaissances pour aider les utilisateurs à atteindre leurs buts et objectifs

particuliers. Un exemple est le datamining pour établir automatiquement de nouvelles connaissances.

Classification de l’usage des grilles de calcul

Les utilisateurs des grilles de calcul désirent obtenir le plus simplement possible les solutions de leurs problèmes en tirant profit de façon transparente des ressources de calcul les plus adaptées. Le calcul distribué repose sur une architecture client serveur traditionnelle. On peut aussi classer l’usage des grilles de calcul en trois catégories :

 Utilisation pour la diffusion d’information qui permet un plus grand partage des

informations.

 Utilisation pour l’augmentation des capacités de stockage.  Utilisation pour le calcul ou l’augmentation de la puissance des ordinateurs.

5. Systèmes distribués à grande échelle et systèmes pair-à-pair

Définition d’un système distribué à grande échelle

Les termes système distribué à grande échelle (SDGE) ou système volontaire ou encore système de calcul global sont utilisés pour désigner les environnements de développement et d’exécution pour les applications sur Internet. On peut considérer les SDGE comme une extension du concept de vol de cycles à l’échelle d’Internet i.e. des machines volontaires qui se connectent à un serveur pour recevoir des tâches à exécuter. De tels systèmes se basent sur le ‘Pull model’ c'est-à-dire qu’ils demandent périodiquement au serveur, du travail puisque les ressources participantes utilisent généralement des ‘Firewalls’. Le système volontaire n’est pas symétrique car ce sont les (nœuds) volontaires qui fournissent les ressources informa-tiques aux projets, et non le contraire. Comme exemples de SDGE, citons Distributed.net, SETI@home, XtremWeb et XtremWeb-CH. Différences entre SDGE, système P2P et grille de calcul Dans la littérature, les SDGE sont considérés comme une forme de système pair à pair (peer-to-peer ou P2P). Néanmoins, plusieurs paramètres sont discriminants. En effet, un système est dit P2P lorsqu’il autorise la communication directe entre entités d’un réseau, sans passer par une autorité centrale, telle qu’un serveur. Dans un réseau P2P, chaque entité se comporte à la fois comme un client et un serveur. L’architecture des systèmes P2P est donc généralement décentralisée. Les SDGE comme SETI@home ne respectent pas nécessairement ces propriétés.

Classification des systèmes P2P D’un autre côté, on confond les systèmes volontaires et P2P avec les grilles de calcul (GC) alors qu’ils se distinguent par les quatre caractéristiques suivantes : 1) Le nombre de ressources connectées est plus élevé de plusieurs ordres de grandeur (typiquement 100 000 ressources) et les ressources sont rarement parallèles (biprocesseur au maximum) 2) Les ressources sont extrêmement volatiles 3) Les réseaux connectant les réseaux sont des LAN, des Intranets et l’Internet 4) Les utilisateurs sont aussi en nombre très important (typiquement un utilisateur par ressource). Comparativement aux grilles de calcul, il faut composer avec une infrastructure matérielle déjà présente, évoluant de façon non coordonnée et en fonction d’impératifs sans relation évidente avec le calcul à grande échelle. L’ordre de grandeur et l’impossibilité d’action ou d’influence sur l’infrastructure engendrent des problèmes spécifiques qui ne se présentent pas dans le cas des GD. Ainsi : 

la sécurité doit être fondée sur des mécanismes extensibles à plusieurs centaines de milliers d’utilisateurs et de ressources et, le placement et l’ordonnancement des tâches doivent prendre en compte l’évolution à court terme (connexion et déconnexion des ressources) et l’évolution à long terme (modification d’infrastructure) du système.



Globalement, les techniques adaptées dans le cadre des grilles de calcul sont inapplicables dans celui du calcul à très grande échelle. Les fonctions traditionnellement associées à la procédure de login (identification, sélection des utilisateurs, droits d’accès, priorité d’exécution, protection du site et traçage des opérations) ne passent pas à l’échelle. Inversement, la confiance de l’utilisateur envers les résultats renvoyés et la facturation de l’utilisation des ressources ne peuvent pas reposer, comme dans le cas des grilles de calcul, sur le caractère institutionnel des sites accédés. Les sites de calcul sont des machines quelconques appartenant à des utilisateurs auxquels on ne peut pas accorder a priori une confiance absolue. Le calcul à très grande échelle repose donc sur la capacité de certifier les résultats ou d’être capable de distinguer entre les bons et les mauvais résultats. De même, contrairement au cas des grilles de calcul, l’ordonnancement d’un très grand nombre de tâches sur une centaine de milliers de ressources ne peut être géré à long terme et coordonné à court terme par des mécanismes centralisés.

Ainsi, les grilles et les systèmes pair à pair ont des racines historiques très différentes qui expliquent leur différence d’organisation et de problématique propre.

6. Clouds

Le terme Cloud fait référence habituellement à un modèle basé sur Internet et dans lequel les données ne sont pas maintenues par l’utilisateur. Plusieurs définitions ont été attribuées à ce terme selon son utilisation. Parmi ces définitions, on peut citer ce qui suit : - Gartner : c’est un style de calcul offrant à plusieurs clients à travers Internet des capacités massives et scalables relatives aux technologies d’information (la scalabilité fait référence à la capacité d’un système à accroître sa capacité de calcul sous une charge accrue quand des ressources généralement matérielles sont ajoutées). - Forrester : c’est une plate-forme composée d’un ensemble de ressources abstraites, hautement scalables et gérées. Cette plate-forme est capable d’accueillir des utilisateurs d’applications qui sont facturés selon leur consommation. - IBM : c’est un paradigme de calcul émergeant, dans lequel les données et services résident dans des centres de calcul massivement scalables qui peuvent être accédés à partir de n’importe quel périphérique connecté à Internet. Le premier cloud qui a été rendu accessible est l’EC2 (Elastic Compute Cloud) lancé en 2006.

7. Architecture multicœurs

Les machines multicœurs représentent actuellement les machines les plus utilisées dans le

monde du calcul au sein desquelles des centaines d’instructions s’exécutent à chaque cycle

d’horloge et des dizaines d’accès simultanées en lecture et/ou écriture de données

s’effectuent entre les processeurs et les mémoires adjacentes. Afin de parvenir à atteindre des

débits réalisables, le système multicœurs est devenu une hiérarchie multiniveaux de

mémoires, à savoir la mémoire cache, la mémoire centrale, etc.

Le principe de base des architectures multicœurs est la duplication des unités d’exécution au

sein du processeur. Ce dernier est dans ce cas vu comme étant deux processeurs indépendants

par le système d’exploitation. C’est ce type d’architecture que nous ciblons dans notre travail.

Nous détaillons ainsi dans la suite plusieurs caractéristiques relatives à l’architecture

multicœurs.

Processeur multicœurs

Un processeur multicœurs (Multicore en Anglais) est un processeur qui possède plusieurs

unités de calcul (cœurs) fonctionnant simultanément. Dans les machines multicœurs, les

cœurs gravés à l’intérieur d'une même puce peuvent exécuter des programmes de façon

autonome et indépendante. En d’autres termes, chaque unité de calcul peut avoir sa propre

mémoire cache et sa propre gestion de données. Toutefois, les différents cœurs ont accès de

manière symétrique au bus de la mémoire partagée. Deux types de processeurs multicœurs

sont utilisés : les processeurs à base de mémoire cache dédiée où chaque cœur possède son

propre cache et les processeurs à base de mémoire cache partagée dont la mémoire cache est

partagée entre les cœurs qui peuvent y accéder de manière concurrente.

Mémoire cache

Afin de réduire les latences d’accès mémoire, une solution classique consiste à intégrer des

mémoires de taille réduite à proximité de l’unité de calcul de façon à minimiser les latences

d’accès aux données. Dans ce cas, se présente la mémoire cache qui représente une mémoire

de petite taille utilisée dans une machine multicœurs. Elle enregistre temporairement des

copies de données provenant en général de la mémoire vive (RAM) pour diminuer le temps

d’un accès ultérieur du cœur à ces données vu que c’est plus rapide que l’accès à la mémoire

centrale.

Généralement, la mémoire cache est directement intégrée dans la puce de l’unité centrale

(UC) ou placée sur une puce distincte dotée d’une interconnexion par bus à l’UC. Le but de

sa conception est de mettre cette petite zone mémoire très réactive à la disposition du cœur

afin de lui permettre de stocker temporairement les informations qu’il va traiter et ainsi de

gagner en performances (voir figure 1-8). En d’autres termes, la fonction de base du cache

est de stocker les données et/ou les instructions de programmes qui sont fréquemment

référencées. L’accès rapide à telles données et/ou instructions accroît la vitesse globale des

applications. En effet, la taille et les performances des caches peuvent fortement influencer

la vitesse de traitement des programmes. La mémoire cache est d’autant plus utile que le

programme à exécuter demande des accès répétitifs à de petites zones mémoire (section de

code qui se répète (boucle), callbacks en programmation objet, etc).

Figure 1-8 : Hiérarchie mémoire

Plusieurs niveaux de cache sont embarqués sur le processeur. Deux niveaux au moins sont

utilisés pour chaque cœur. Le premier niveau (dénommé L1) est formé d’un cache pour les

instructions et d’un autre pour les données. Sa latence est de quelques cycles d’horloge, mais

sa taille est assez réduite. Toutefois, le second cache (dénommé L2) a une taille plus large

mais sa latence d’accès est plus importante.

Il existe plusieurs techniques gérant les caches L1 et L2. La première considère le cache L2

comme étant inclusif, c’est-à-dire qu’il comporte toutes les données existantes dans le cache

L1. La seconde technique consiste à rendre le cache L2 exclusif. Dans ce cas, aucune donnée

ne se trouve à la fois chargée au sein des deux caches.

Lorsqu’un cœur veut à accéder à une donnée, il la cherche d’abord dans la mémoire cache.

S’il la trouve au sein du cache L1, c’est un succès du cache L1, sinon il s’agit d’un échec (ou

défaut) du cache L1 et le cœur va ainsi interroger le cache L2. Si la donnée n’y est pas, le

cœur va effectuer une lecture de la donnée depuis la mémoire RAM voire sur d’autres

périphériques de stockage, puis il la copie dans le cache L1. Telle copie peut provoquer un

certain remplacement d’un bloc de cache déjà présent (voir section 4.1.3).

Commercialement, la composante du cache a été apparue en 1968 principalement sur le

mainframe IBM 360/85.

8. Processeurs parallèles

– Processeurs multi-cœurs Un processeur multi-cœurs est composé d’au moins deux unités de calcul (cœurs) gravées

au sein d’une même puce. Les cœurs des processeurs dans la plupart des cas sont homogènes

(identiques). Mais IBM, Sony et Toshiba ont exploité le cas de cœurs hétérogènes (différents)

et spécialisés dans des domaines bien précis (audio, affichage, calcul pur). Depuis 2005, les

processeurs multi-cœurs sont sur le marché.

Deux approches différentes d’architectures multi-cœurs

- Processeurs vectoriels Les processeurs vectoriels sont des processeurs pouvant traiter un vecteur entier (tableau de dimension 1) de données en une instruction (dite vectorielle e.g. addition vectorielle). Ces processeurs ont été la clé de performance pour les premiers super-ordinateurs du type Cray dans les années 80 et même pour des plates-formes assez récentes comme l’Earth-simulator qui a marqué ce début de siècle en détenant la tête de la liste du Top500 pendant plus de deux ans successifs.

- Processeurs graphiques Depuis quelques années, les processeurs graphiques ont été envisagés comme accélérateurs de traitements parallèles. Un processeur graphique communément connu sous le nom GPU (Graphical Processing Unit) est un processeur conçu pour décharger les processeurs (CPU : Central Processing Unit) des traitements graphiques. Cependant, vu que les opérations traitées par ces processeurs ne sont q’une forme d’arithmétique, les GPUs se sont progressivement développés vers un modèle utilisable aussi pour les calculs non graphiques. Les GPUs actuels supportent à la fois les deux paradigmes de programmation SIMD et SPMD En effet, les processus légers (threads) exécutés sur un GPU ne sont pas complètement indépendants. Ils sont en fait ordonnés en blocs de threads, où chaque bloc exécute la même instruction (c’est le SIMD). Il est aussi possible d’ordonnancer sur les GPUs le même flot d‟instructions sur plusieurs blocs. Dans ce cas, les blocs de threads sont hors synchronisation (c’est le SPMD).