Module CP : Algorithmique et techniques de base du calcul parallèle

Module CP : Algorithmique et techniques de base du calcul parallèle

Equipe pédagogique :

Jean-Louis Roch, Denis Trystram,Thierry Gautier

Volume :

24h.

Spécialité :

S&L

N.B. Ce module est commun aux parcours FTI et SAP.

Selon la hiérarchie mémoire, différents niveaux de parallélisme peuvent être distingués : à l'intérieur d'un noeud multi-processeurs symétriques (SMP), entre noeuds fortement connectés (architecture distribuée avec réseau d'interconnexion), entre noeuds faiblement couplés (du réseau local au metacomputing sur internet). Pour les exploiter, l'algorithmique parallèle fédère les méthodes et outils qui permettent de résoudre plus rapidement un problème donné. L'objectif de ce cours est d'en présenter les principales techniques en les illustrant par des exemples de problèmes applicatifs concrets. Il s'agit d'abord d'extraire le parallélisme fin au sein de l'application puis de l'ordonnancer sur l'architecture cible.

• Modélisation d'un programme parallèle et analyse de coût. Graphe de flot de données d'une exécution; coût d'un algorithme (temps, localité et espace mémoire; granularité); modélisation des communications (BSP, LogP).
• Extraction de parallélisme et schémas algorithmiques : Découpe récursive et graphes série-parallèle (exemple de la compression); .Poly-algorithmes et diviser pour régner en cascade (résolution de systèmes, FFT). Distribution de données (simulation dynamique, recherche d'information).
• Techniques d'ordonnancement : sans communication avec contraintes mémoire (algorithmes de liste); avec grand temps de communication (contrôle de la locatlité); avec prise en compte relative des communications et du parallélisme (techniques de partitionnement).
• Parallélisation automatique. Extraction de parallélisme d'un programme séquentiel. Evaluation d'expressions et de programmes arithmétiques.

Module CP : Algorithmique et techniques de base du calcul parallèle