Modèle polyédrique: fondements et application à la parallélisation

de programmes réguliersTanguy Risset

DIF 2001/2002

Présentation

• Tanguy Risset• CR INRIA

• Projet ReMaP/CompSys

• B. 311, Tel. 85 48, Tanguy.Risset@ens-lyon.fr

• Plan• Introduction à la parallélisation automatique

• Modèle polyédrique: fondements

• Ordonnancement de boucles

• Parallélisation de programmes réguliers

• Application: compilation pour FPGA

Plan

• Introduction à la parallélisation automatique– Historique

• Types de machines parallèles

• Modèles pour les machines parallèles

• Langage de programmation parallèle

– Un modèle simple: les architectures systoliques

Historique

• Classification des machines parallèles (Flynn)– En fonction du contrôle de séquences

d’instrutions – Single Instruction Multiple Data : SIMD

– Multiple Instruction Multiple Data : MIMD

– En fonction de l’organisation de la mémoire– Shared Memory: SM

– Distributed Memory: DM

Historique

• Classification des machines parallèles – En fonction du réseau d’interconnexion

– réseaux d’interconnexion dynamique pour SM (crossbar switch, réseaux à base de bus, interconnection multi-étage)

– réseaux d’interconnexion statique pour DM (grille, arbre, hypercube) En fonction de l’organisation de la mémoire

• Autres types: réseaux de neuronnes,processor in memory (circuits reconfigurables)

Tendances

Single Processor

SMP

MPP

SIMD ClusterNOW

0

100

200

300

400

500

Tendances, suite• Grappes de machines SMP

– PCs multiprocesseurs (Pentium,Alpha)– Nœuds de machines parallèles (SP-3)– Connexions de gros serveurs (Origin2K,SUN E10K).

• Processeurs du commerce.

• Logiciels standards performants.

• Linux, NT.

Ecart Processeur/Mémoire

1

10

100

1000

DRAM

CPU

198

0198

1 198

3198

4198

5 198

6198

7198

8198

9199

0199

1 199

2199

3199

4199

5199

6 199

7199

8199

9 200

0198

2

Ecart de PerformanceProcesseur-Mémoire:(croissance 50% / an)

Per

form

ance

Temps

“Loi de Moore”

DRAM9%/an.(2X/10ans)

µProc60%/an.(2X/1.5an)

Hiérarchies mémoires profondes

Contrôle

Bus données

Stockagesecond.(Disque)

Processeur

Registres

Mémoireprincipale(DRAM)

CacheNiveau

2(SRAM)

Cach

eIn

terne

1s 10,000,000s (10s ms)100,000 s(.1s ms)

Vitesse (ns): 10s 100s

100s

Gs

Taille (octets):Ks Ms

Stockagetertiaire(Disque/bande)

Ts

Mémoiredistribuée

Mémoire DistanteGrappe

10,000,000,000s (10s sec)

10,000,000 s(10s ms)

Plan

• Introduction à la parallélisation automatique– Historique

• Types de machines parallèles

• Modèles pour les machines parallèles

• Langage de programmation parallèle

– Un modèle simple: les architectures systoliques

Modèle P-RAM

• P processeurs, une mémoire partagée (modèle SIMD-SM)

• Les processeurs communiquent à travers la mémoire partagée

• Chaque opération prend une unité de temps

Modèle BSP

• BSP: bulk synchronous parallelism (modèle MIMD-DM)

• Un ensemble de paires processeurs-mémoires

• L ’exécution consite en succession de super-step séparés par des phases de communications (synchronisation)

Modèle plus précis

• Modélisation des coûts de communication– coût-envoi(L)=+L

• Modélisation de la hiérarchie mémoire

• Modélisation du matériel spécifique de la machine– ALU spécifique– registres

Limites de la modélisation

• En général, un modèle est soit peu réaliste, soit trop spécifique

• La modélisation ne permet pas de se passer d ’expérimentation pour évaluer un programme parallèle.

• Mais…• elle aide à comprendre la structure du calcul parallèle

• elle permet de formaliser la notion de parallélisation

Plan

• Introduction à la parallélisation automatique– Historique

• Types de machines parallèles

• Modèles pour les machines parallèles

• Langage de programmation parallèle

– Un modèle simple: les architectures systoliques

Langage de programmation parallèle

• Les langages sont à la charnière des modèles et des machines

• Le langage idéal serait:– simple à programmer (et debugger!)– efficace– portable

• …….. Il n ’existe pas

Exprimer le parallélisme

– Parallélisme de données• il exploite la régularité des données et applique en

parallèle un même calcul à des données différentes

– Parallélisme de contrôle• il consiste à faire des tâches différentes simultanément

– Parallélisme de flux• technique du travail à la chaine

• chaque donnée subit une séquence de traitement réalisés en mode pipeline.

Programmer les machines

• Mémoire partagées– espace d ’adressage commun– mécanisme d’exclusion mutuelle

• Mémoire distibuée– communication par passage de message– librairie de communication

Les langages data-parallèles• Fortran 77/90/95 + directives

• L’utilisateur spécifie une partie du parallélisme et la répartition des donnéesPrésenté comme la boite noire pour la parallélisation

d’applications

Bonnes performances pour les codes réguliers

Quelques vraies applications parallélisées

Beaucoup de ré-écriture de codes

• Outil important pour l’avenir du calcul numérique parallèle

Programmation data-parallèle• Style de programmation caractérisé par:

– un flot de contrôle unique: un seul programme définit les opérations data-parallèles,

– un espace de nommage global: le programmeur voit une seule mémoire,

– des opérations parallèles: le parallélisme découle des opérations appliquées aux données distribuées sur les processeurs,

– des directives de compilation.

• Les détails de bas niveau (distribution effective des données, communications) sont transférés du programmeur au compilateur.

• But : s’écarter des spécificités de la machine et encourager une diffusion plus large du parallélisme.

Parallélisation d’applications numériques

Algorithme séquentiel Distribution de données

Algorithme parallèle

HPF/OpenMPBibliothèques de calcul séquentielles parallèles

Bibliothèques de communication

programme HPF/OpenMP

programme F77 + MP

F77/90

Etude perfs + monitoring

High Performance Fortran• Issu d’un forum réunissant chercheurs, constructeurs et développeurs

d ’applications.

• Basé sur Fortran 90 et destiné aux machines MIMD DM.

• Directives de placement des données sur les processeurs.

• Constructions data-parallèles (FORALL) et spécification du parallélisme (INDEPENDENT et PURE).

• Fonctions intrinsèques et bibliothèque standard.

• HPF-2 pour les applications irrégulières.

• Nombreux compilateurs et outils.

• Performances moyennes en général.

Alignement et distribution

Parallélisme implicite

• Langage fonctionnels

• Langages déclaratifs

• Parallélisation de programmes séquentiels

Parallélisation automatique: difficultés

• Analyse de dépendences

Do i=1,Na=0Do j=1,N

a=a+B[i,j]C[i]=a

DoAll i=1,Na[i]=0Do j=1,N

a[i]=a[i]+B[i,j]C[i]=a[i]

Parallélisation automatique: difficultés

• Pointeurs

• Contrôle dynamique

Do i=1,NA[i]=…B[i]=A[C[i]]

While C>0 Do……….

Parallélisation automatique: difficultés

• Granularité– Partitionnement des calculs en fonctions du

rapport de coût calcul/communication

• Génération de code– Compilation descommunications

Outils utilisant le modèle polyédrique

• Pico (HP Palo Alto)

• Compaan (U. Leiden, Berkeley)

• MMAlpha (INRIA Rennes)

Compaan

MMAlpha

FPGA

ASIC

Uniformisation

Dérivation RTL

OrdonnancementAlphaVHDL

Références cours 1

• Transparent et Exos sur– Www.ens-lyon.fr/trisset

• P. Quinton et Y. Robert, Algorithmes et architectures systoliques, Masson, 1989.

• commence à dater, mais la partie algorithmique et les chapitres 11 et 12 sont toujours d'actualité.

• V. Kumar, A. Grama, A. Gupta et G. Karypis, Introduction to Parallel Computing, Benjamin Cummings, 1994.

• Bonne introduction générale

Plan

• Introduction à la parallélisation automatique– Historique

• Types de machines parallèles

• Modèles pour les machines parallèles

• Langage de programmation parallèle

– Un modèle simple: les architectures systoliques