Calcule parallel - Introduction

ARCHITECTURES PARALLELES DES SYSTEMES INFORMATIQUES

Par Abdullah BOUKERRAM [email protected]

Université de BBA 2011

SOMMAIRE

Cours architecrtures Parallèles Dr A. Boukerram 2

CHAPITRE I : LES ORDINATEURS CONVENTIONNELSI PRESENTATION

II. PRINCIPE DE FONCTIONNEMENT

III. CARACTERISTIQUES DES MACHINES CONVENTIONNELLES

IV LIMITES DES ORDINATEURS CONVENTIONNELS


CHAPITRE II. CLASSIFICATION DES MACHINES PARALLELES

I. CLASSIFICATION DE FENGII. CLASSIFICATION DE FLYNNIII. NIVEAUX DE CALCULS PARALLELISABLESIV. GRANULOMETRIE :V. ANALYSE DE PERFORMANCES :VI. LES MICROPROCESSEURS


CHAPITRE III : ARCHITECTURE SIMD

I. PRÉSENTATIONII. ETUDE DU PROCESSEUR GAPP DE NCRIII. LA MÉMOIRE RAMIV. LES REGISTRES ET LES INSTRUCTIONSV. GESTION DES ENTREES/SORTIES (E/S)


CHAPITRE IV: LES PROCESSEURS PIPELINE

I. PARALLELISME D’OPERATEURS

II. QUELQUES MACHINES PIPELINE

III. Etude du Processeur Vectoriel ZIP3216

IV. Programme ZIP/C


CHAPITRE V: ARCHITECTURES MIMD : LES TRANSPUTERSI. ARCHITECTUREII. RESEAU DE TRANSPUTERSIII. SYSTEME DE DEVELOPPEMENT POUR

TRANSPUTERIV. LE LANGAGE OCCAMV. MACHINE RESEAU DE TRANSPUTERSVI. APPLICATION OCCAMVII. PARALLELISME SPMD


CHAPITRE VI: LES GRILLES DE CALCUL

I. Architecture des Grilles

II. Etude du WMS

III. Programmation du JLD


CHAPITRE I : LES ORDINATEURS CONVENTIONNELS


I PRESENTATION

• Les ordinateurs conventionnels sont dits de type SISD (simple flot d’instructions, simple flot de données). Ils fonctionnent selon le mode séquentiel et sont appelés également modèle de VON NEUMAN.

• Un ordinateur conventionnel se compose de :• une mémoire banalisée où sont rangées données et instructions (MC).

• une unité de traitement (UT)• une unité de commande( UC)• un bus de communication reliant l’ensemble du système.


II. PRINCIPE DE FONCTIONNEMENT

Le déroulement ou l’exécution d’un programme se fait de manière séquentielle, instruction après instruction. Et souvent l’exécution d’une instruction elle même obéit à une certaine chronologie.

• lecture d’une instruction en MC• décodage de l’instruction par l’UC• exécution de l’instruction, une fois les opérandes prêtes

• rangement des résultats en MC


III. CARACTERISTIQUES DES MACHINES CONVENTIONNELLES• Ces machines sont caractérisées par :• Une seule instruction est exécutée à un instant donné

• Une instruction n’est exécutée qu’une fois la précédente entièrement terminée

• Le passage d’une instruction à une autre se fait de façon automatique (maintien d’un compteur ordinal).


IV LIMITES DES ORDINATEURS CONVENTIONNELS

• L’évaluation des temps de calcul nécessaire à l’exécution d’un programme dépend de :

• quantité de données à traiter• temps d’accès à la mémoire principale• complexité de l’algorithme• temps nécessaire à l’exécution d’une instruction• Cycle d’accès mémoire


Débit

accès vers mémoire (externe ou centrale) est déterminé par le débit du bus de communication.

• Unité de mesure du débit est donné en bits/ seconde, Kbits/s, Mbit/s, Gigabits/s

• bytes/ seconde, • mots/seconde .


Cycle d’instruction• Cycle d’instruction = cycle machine qui dépend de la

puissance de calcul de l’unité de traitement, qui elle se mesure en :

• MIPS (million d’instructions par seconde)• MOPS (million d’opérations par seconde)• MFLOPS (million d’opération flottantes par seconde)


Limites des machines //• Pour déterminer les limites des machines

conventionnelles, il suffit d’évaluer les temps de traitement nécessaires à l’exécution d’une application manipulant une grande quantité de données et confronter ces temps aux exigences temps réel du monde industriel.

• Ce sont ces limites, qui imposent l’utilisation des machines parallèles.


Exemple :• Calculer le temps d’exécution d’un algorithme de calcul

matriciel, sur une machine séquentielle cadencée par un processeur d’une fréquence de1 Mhz.

Algorithme

- Entrée : Matrice (1000*1000) éléments, rangée en MC

- Chacun des éléments de la matrice nécessite 50 instructions

- 1 cycle machine = 1 cycle d’accès en MC


Solution• cycle de calcul = T= 1/f= 1/106 = 10-6 s = 1µs• nombre d’accès mémoire = 2* 106 accès (1 accès en LOAD, un autre en STORE)

Temps liés aux accès mémoire = 2 106 * 1µs = 2 sTemps de calcul = 106 * 50 * 1 µs = 50 sTemps total d’éxécution = 52 s


Mythes du parallélisme• Les Deux Mythes du Parallélisme :

tendance à penser que les gains en matière de performances croit de façon linéaire.

• 1 machine met T pour exécuter un pgm P• N machines mettront T/N pour exécuter P


Gains exprimés


• La 1ière raison qui pousse les informaticiens vers le parallélisme c'est le mythe Vitesse( puissance de calcul) avec multiplication de processeurs fnt en //

• De nombreuses applications scientifiques, techniques, médicales, ... ont des besoins énormes en puissance de calcul qui ne peuvent pas être satisfaits par les machines séquentielles classiques, aussi performantes soient-elles ?


Mythe holiste

• La seconde raison qui pousse les informaticiens vers le parallélisme c'est le mythe Holiste qui s'intéresse avant tout à la puissance expressive des modèles de calcul parallèles. Cette approche a donné naissance à des modèles de calcul différents du modèle séquentiel classique : par exemple, ils ne comportent pas de compteur ordinal (Data Driven / Demand Driven ...) ou bien ils utilisent une organisation bien particulière (Cellulaire, Neuronal ...)


Chapitre II. CLASSIFICATION DES MACHINES PARALLELES

• Il existe plusieurs méthodes pour exploiter le parallélisme, et celles-ci déterminent les familles de machines.


I. CLASSIFICATION DE FENG

• Pour le classement des architectures Tse-Yun FENG suggère d’utiliser le degré de parallélisme.

• Le nombre maximum de bits qui peuvent être traités pendant une unité de temps est appelé Degré de parallélisme P.

• Degré de parallélisme moyen Pm = ( Pi / T)i = 1, T

• Pi : nbre de bits traités durant le i ème cycle• T : nombre de cycles


• Remarque : en général on a Pm < P, et Feng définit le taux d’utilisation d’une machine pendant T cycles par u = Pm/P

• U = 1 ssi la puissance de calcul du processeur est entièrement utilisée.

• La classification par le degré de parallélisme est donnée par le nombre de bits de la donnée traitée (n) et le nombre de mots (m) traités en parallèle.


• Pour une machine C , le degré maximum de parallélisme P(C) est donné par :

• P(C) = n * m

• n= nombre de bits de la donnée traitée• m= nombre de mots traités en parallèle


II. Classification de Flyn• La classification est basée sur la multiplicité des flots

d’instructions et des données.

• Cette classification amène quatre familles de systèmes. Le terme de flot qualifie une séquence d’instructions (ou de données) exécutées par un processeur unique.


Les quatre familles ainsi définies sont :

• SISD : Simple flot d’instructions, Simple flot de Données

• SIMD : Simple flot d’Instructions, Multiple flot de Données

• MISD : Multiple flot d’instructions, Simple flot de Données

• MIMD : Multiple flot d’Instructions, Multiple flot de Données


Exemple de quelques machines

• SISD (une unité fonctionnelle ) VAX 780• SISD (plusieurs unités fonctionnelles) CRAY 1• SIMD (word slice) ILLIAC IV, BSP, PEPE• SIMD (bit slice) MPP, DAP, CLIP, GAPP• MIMD (couplage serré) CRAY –2• MIMD (couplage lâche) IBM 3081• couplage lâche : interactions sont faibles entre les processeurs

• couplage serré : fortes interactions entre processeurs.


Architecture SISD/SIMDCours architecrtures Parallèles Dr A. Boukerram 30

M

UT UC

Architecture SISDArchitecture SIMD :FonctionnementSynchrone

UC

M M M

UT

RI

UT UT

Architectures MISD/MIMD


M UT UT UT

UC UC UC

Architecture MISD

M : MémoireUC : Unité de commandeUT : Unité de traitementRI : Réseau d’Interconnexion

M M M

RI

UT UT UT

UC UC UC

Architecture MIMD

III. NIVEAUX DE CALCULS PARALLELISABLES• On défini le parallélisme comme l’exécution simultanée de

plusieurs taches.• niveau bit : nombre de bits B, traités en //• niveau mot : nombre de mots P traités en //• niveau voisinage : nombre de voisins V accessibles

simultanément• niveau opérateur : nombre d’opérateurs O traités en //• niveau programme : traitement simultané d’un certain

nombre de modules• niveau données : traitement simultané de plusieurs

paquets de données.• Danielson/ Levialdi utilisent les quatre premiers paramètres

pour mesurer la puissance P du parallélisme P = B x P x V x O

• Avec P et O qui peuvent varier d’une machine à une autre.


IV. GRANULOMETRIE

• On distingue également plusieurs niveaux de parallélisme au niveau de la programmation: on parle de granulométrie

• exécution du grain le plus fin au plus gros grain.



Programmes indépendants

Partie de programme

Fonction ou ss-programme

Boucles ou itérations

Instructions

Haut Niveau

Bas niveau

Gros grain

Grain fin

Remarque : les architectures de type SIMD sont réputées performantes pour un parallélisme fin et les architecture MIMD sont adaptées au grain fort.

• Avant de songer au parallélisme, à savoir traduire les logiciels classiques sur des machines parallèles il y a lieu de mesurer le rapport (GAIN / EFFORT) qui doit être donc favorable.


Gains théoriques

•GAIN: lié à la puissance de calcul est mesuré en temps (distinguer toujours entre gain théoriques attendus > gains effectifs obtenus).

•EFFORT : mesuré en coût (temps de développement)


Contraintes à prendre en charge

• A cet effet on doit tenir compte :

- de l’importance du travail à effectuer

- du type de travail à paralléliser

- des difficultés de passage des outils classiques aux architectures parallèles.


• Pour le parallélisme les concepteurs de systèmes informatiques hésitent et butent sur plusieurs problématiques :

Câblage d’algorithmes : efficace mais coûteux et ne peut être généralisé à toute application

Conception de machines dédiées : trop spécialisées marché restreint.


Processeurs généraux

•Conception de machines généralistes :

Machines lourdesDifficiles à programmer Coûteuses


V. ANALYSE DE PERFORMANCES

• LOI d’AMDHAL : Considérons un programme ayant deux parties distinctes, l’une étant très rapide, l’autre plus lente à l’exécution.

Temps de calcul du programme = fn ( vitesse1, vitesse2)

Pgm1 Pgm2

Influence de la partie la plus lente sur le temps de calcul du programme.


• Dans le cas du parallélisme, si Ps représente le pourcentage séquentiel du programme, S le speed-up du programme est donné par :

• S = 1/ ( Ps + ( 1-Ps ) / Np ) (a)• Np : nombre de processeurs• (1-Ps) = Pp représente le % parallèle du code.• Si Ts = temps d’exécution sur un processeur• Tp = temps d’exécution sur P processeurs alors

• (a) Tp = Ts / (Pp / Np + Ps) avec S = Tp/Ts


• La loi d’Amdhal conduit à la question suivante : QUELLE EST LA MEILLEURE ARCHITECTURE PARALLELE : peu de processeurs puissants ou beaucoup de processeurs mais alors, moins puissants.

• Trouver un compromis entre prix et performances : choix

entre microprocesseurs RISC et microprocesseurs CISC


VI. LES MICROPROCESSEURS

• MICROPROCESSEURS RISC ( Reduced Instruction Set Computer)

• un jeu d’instruction limité s’exécutant sur un nombre

limité de cycles (sinon un seul)• une limitation d’accès mémoire aux deux opérations

LOAD et STORE• une utilisation systématique des registres généralement plus

nombreux que sur les microprocesseurs CISC (Complex Instruction Set Computer)

• une dépendance plus forte par rapport aux compilateurs.


• MICROPROCESSEURS CISC (Complex Instruction, Set Computer)

• un jeu d’instructions complexes avec un grand nombre d’adressage

• accès mémoire pratiquement pour chacune des instructions usitées

• un nombre limité de registres d’usage universel • moins d’indépendance vis à vis du compilateur


Avantages & inconvénients

• Pour les RISC, la complexité est supporté par les compilateurs, pour les CISC , le décodage est plus pénalisant vue la complexité des instructions.

• Processeurs CISC :• Toute la famille des INTEL du 8080 jusqu’au Pentium , en

passant par les équipements IBM s’appuyant sur les CISC 8086


• Processeurs RISC :• Les processeurs MOTOROLA dans les micro-ordinateurs

concurrencent bien les processeurs INTEL.• le POWER PC ( APPLE + IBM + MOTOROLA)• IBM POWER 4.


• LOI DE MINSKY : Tendance à penser que le temps d’exécution sur N processeurs est inversement proportionnel à N.

• Ceci n’est pas vrai <======> tenir compte des temps liés aux communications.

• Minsky prédit un SPEED–UP de l’ordre de Log N• N = nombre de processeurs du système.


• Nécessité aux concepteurs de systèmes informatiques de se pencher sur :

• l’organisation des mémoires (mémoire hiérarchiques, mémoires caches, ou autres )

• les bus ou multi-bus comme registres de transport de données.


Accès mémoire

•usage de mémoire locales et /ou communes aux différents processeurs du système

• l’accès aux mémoires ( simple accès, double accès ou multiples accès).

• les réseaux d’interconnexion


CONCLUSION architecture des systèmes informatiques = fonction

(processeurs, mémoires,

bus de communication, réseaux d’interconnexion).

Tendance aux Compilateurs Vectoriseurs

Documents

Calcule parallel - Introduction