Systèmes et traitement parallèles - Ecole Mohammadia d

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 1

Systèmes et traitement parallèles

Mohsine EleuldjDépartement Génie Informatique, EMI

eleuldj@emi.ac.ma

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 2

Système et traitement parallèle

Objectif • Etude des architectures parallèles• Programmation des applications concurrentes (Java et MPI)

Contenu• Introduction au traitement parallèle• Principe de traitement vectoriel et pipeline• Systèmes multiprocesseurs• Analyse et mesures de performance

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 3

Chapitre IIntroduction au traitement parallèle

• Quelques applications parallèles• Evolution de la densité d’intégration• Evolution des systèmes d’ordinateurs• Définition et niveaux• Parallélisme dans un système monoprocesseur• Structures des ordinateurs parallèles• Classification de Flynn

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 4

Quelques applications parallèlesCalcul parallèle : utilisation de ressources multiples simultanément

(processeurs, RAM, Caches, DMA,…)

Applications classiques :• Prévision météorologique• Réactions chimique et nucléaire (temps réel)• Activités géologique et sismique• Recherche biologique• Simulation des circuits intégrés

Applications commerciales : • Moteur de recherche du Web • Exploration minière (pétrole, …) • Réalité virtuelle (simulation de vol d’avion, entertainment industry, …) • Environnement de travail collaboratif • Big Data (données massives)

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 5

Evolution de la densité d’intégration

Processeur Année Transistors Technologie4004 1970 2,3 K 6μm8088 1980 29 K 3μm80286 1983 134 K 2μm80386 1985 275 K 2μm80486 1989 1,2 M 1μmPentium 1995 3,3M 350 nmPentiumPro 1996 5,5M 250 nmPentium II 1997 7,5 M 180 nmPentium III 1999 9,5 M 130 nmPentium IV 2003 42 M 90 nmi7-3770K 2008 1,4 G 22 nm

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 6

Intel Core i7-3770K3,4 GHz, 22 nm, 1,4 G transistors

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 7

Evolution des systèmes d’ordinateurs (1/4)

Générations d'ordinateurs sont déterminées par :• Technologie de fabrication des composants• Mode de traitement• Langage de programmation

Evolution des systèmes d'exploitation• traitement par lot• Multiprogrammation• temps partagé• Multitraitement• Multithread

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 8

Evolution des systèmes d’ordinateurs (2/4)

Première génération : 1938-1953• relais électromécaniques comme organes de commutation• tubes à vide• arithmétique bit à bit (additionner à 1 bit) des nombres en virgule fixe• langage machine binaire• ENIAC, EDVAC (bell laboratoires)

Deuxième génération : 1952-1963 :• transistors et diodes• circuits imprimés (800 transistors)• mémoire à tore• assembleur, FORmula TRANslation 1956, Algol (Algorithmic Langage)

1960, Cobol. (Common business oriented) 1959• traitement par lot• TRADIC, IBM 1620 en 1960

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 9

Evolution des systèmes d’ordinateurs (3/4)

Troisième génération : 1962-1975 :• SSI et MSI• circuits imprimés multicouches• compilateurs intelligents• multiprogrammation (exécution simultanée des programmes et des E/S)• IBM 360/91, Illiac IV, TI-ASC, Cyber-175, STAR-100• temps partagé• mémoire virtuelle (mémoire principale, mémoire secondaire)

Quatrième génération : 1972-1990:• LSI et VLSI pour la logique et la mémoire• langages pour la manipulation des scalaires et des vecteurs (Fortran étendu)• compilateurs avec vectorisation• machine vectorielle CRAY-1 (1976), Cyber-205 (1982)• systèmes multiprocesseurs IBM370/168 MP et IBM3081 (1980), Cray X-

MP(1983), MPP massively parrallel processor (1982 composé de 16K microprocesseurs.

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 10

Evolution des systèmes d’ordinateurs (4/4)

Cinquième génération : 1990-aujourd’hui:• VLSI, ULSI, WSI (1G processeurs)• Processeur multicores• Plusieurs niveux de mémoire cache (3 à 7)• CRAY-2 (4 processeurs) plus de 1 GFlops• NEC 5 GFlops et coûte 5 millions de dollars• Mutithreading

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 11

Classement des superordinateurs (juin 2014)

Référence : http://www.top500.org/lists/2014/06/

Rang Site Système Cores PFlops

1 National Super Computer Center in Guangzhou, China

Tianhe-2 NUDT 3 120 000 33,86

2 DOE/SC/Oak Ridge National Laboratory, United States

Titan - Cray XK7 Cray Inc. 560 640 17,59

3 DOE/NNSA/LLNLUnited States

SequoiaIBM 1 572 864 17,17

4 RIKEN Advanced Institute for Computational Science, Japan

K computerFujitsu 705 024 10,51

5 DOE/SC/Argonne National Laboratory, United States

Mira - BlueGene/Q, IBM 786 432 8,58

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 12

Définition et niveaux

Définition : Exploitation d'événements concurents dans le processus de traitement• Concurence : parallélisme, simultaniété et pipeline• Parallèlisme : événements se produisant pendant le même intervalle de temps• Simultaniété : évenements se produisant dans le même instant• Pipeline : événement se produisant pendant des intervalles de temps

cheuvauchésNiveaux du traitement parallèle

• Travail ou programme (multiprogrammation, temps partagé, multitraitements)• Tâche ou procédure (décomposition du programme)• Inter-instruction (analyse de la dépendance des données) ---> vectorisation• Intra-instruction (au niveau de la micro-programmation) ou du cablage

De plus en plus le matériel remplace le logiciel :• Miniaturisation et coût• Vitesse (temps réel)• Tolérance au pannes

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 13

Parallélisme dans un monoprocesseur

• Multiplicité des unités fonctionnelles (10 UAL dans le CDC-6600)• Parallélisme et pipeline dans le CPU• Chevauchement des opérations du CPU et d'E/S (canaux, DMA E/S prog.)• Système de hiérarchie de mémoire (mémoire virtuelle)• Equilibrage des tâches bornées par le calcul et celles bornée par les E/S.• Multiprogrammation (chevauchement entre le CPU et les E/S), et le temps

partagé (efficace en interactif ---> temps réel).

Tous ces mécanismes sont propres aux systèmes d’exploitation

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 14

Structures des ordinateurs parallèles

• Ordinateur pipeline parallélisme temporel

• Tableau d'ordinateurs parallélisme spatial

• Système multiprocesseurs asynchrone

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 15

Ordinateur pipeline

• Exemple du pipeline : Exécution d'une instruction.• CI : Chercher l'instruction de la mémoire• DI : Décoder l'instruction• CO : Chercher les opérandes• EO : Exécuter l'opération

• Problème :• conflit d’accès à la mémoire• branchement et interruption

• Avantage : exécution de la même instruction plusieurs fois (traitement vectoriel)

• Ordinateurs pipeline : IBM3838, CRAY-1, CYBER-205.

CI DI CO EOInstruction

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 16

Tableau d’ordinateurs(mémoire distribuée)

UC : Unité de ContrôlePC : processeur de contrôleMC : mémoire de contrôleET : Elément de traitementP : processeurM : mémoire locale.

PC

MC

P

M

P

M

P

M

P

M

Réseau d’interconnexion

Exemples : Illiac IV et MPP

E/S

ET1 ET2 ET3 ETn

UC

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 17

Système multiprocesseurs(mémoire partagée)

Exemples : S-1, IBM370/168MP, Cray X-MP et Cray-2.

MM1

Réseau d’interconnexion

Réseau d’interconnexionMM2

MMn

P1 ML1 Pp MLp

Canaux d’E/S

MM : module mémoireP : processeurML : mémoire locale

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 18

Classification de Flynn

En 1966 : basée sur la multiplicité du flot d'instructions et le flot de données • SISD : Single Instruction Single Data Stream• SIMD : Single Instruction Multiple Data Stream• MISD : Multiple Instruction Single Data Stream• MIMD : Multiple Instruction Multiple Data Stream.

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 19

Classification de Flynn : SISD

Le systeme peut être pipeline et/ou avoir plus d'une unité fonctionnelle (VAX11/780 une seule unité, IBM370/168 plusieurs unités).

UC P M

FI

FI FD

UC : unité de contrôleP : unité de processeurM : module mémoireFI : flot d'instructionFD : flot de données

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 20

Classification de Flynn : SIMD

Systèmes qui ont une structure de tableaux d'ordinateurs (Illiac IV et MPP)

UC

Pn MmFI

FI

FDn

P1 M1FD1

P2 M2FD2

......

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 21

FI1FInFD

Classification de Flynn : MISD

Architecture ayant moins d’intention et considérée comme impraticable par certains architectes

Pn

Mm

FIn

P1

M1

FD

P2

M2......

UCn

UC1

UC2

...

FI2

FI1

... FI2

Architectures parallèles, M. Eleuldj, Département Génie Informatique, EMI, septembre 2014 22

FI2

FI1

FIn

FD2

FD1

FDn

FI2

FI1

Classification de Flynn : MIMD

Exemples : IBM 360/16 MP, Cray-2, IBM 3081/3084 et S-1

PnFIn

P1 DSn

P2

...UCn

UC1

UC2

...Mm

M1

M2

...

...