Modèle polyédrique: fondements et application à la parallélisation de programmes réguliers Tanguy Risset

Modèle polyédrique: fondements et application à la parallélisation de programmes réguliers

• Tanguy Risset

• DIF 2001/2002

Présentation

• Tanguy Risset

• CR INRIA
• Projet ReMaP/CompSys
• B. 311, Tel. 85 48, [e-mail]

• 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

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

Hiérarchies mémoires profondes

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ées

• Pré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

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

Parallélisation automatique: difficultés

• Pointeurs

• Contrôle dynamique

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

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