Cours de Programmation parallèle en PDF (Avancé)

Programmation parallèle : Ce qu'il faut savoir. Approche avancée axée sur le calcul haute performance et l'optimisation des temps d'exécution sur architectures multi‑processeurs. Rédigé par F. Desprez et F. Zara, ce document de 58 pages présente des modèles, des bibliothèques et des méthodes de mesure pour concevoir des applications parallèles efficaces.

🎯 Ce que vous allez apprendre

• Introduction
• KaaPI
• Pthreads
• OpenMP
• Composants parallèles
• MapReduce
• Exécution des tâches
• Dépendance entre les tâches

Pourquoi utiliser la programmation parallèle ?

Accélérer un traitement, réduire le temps d'exécution et exploiter pleinement le matériel moderne sont au cœur du calcul parallèle. Sur architectures multi‑processeurs, l'exécution simultanée de calculs permet un gain mesurable de performance (speedup) et une réduction de la latence. Les gains réels dépendent de la part séquentielle de l'algorithme, de la granularité des tâches et de la qualité de l'ordonnancement.

Comparaison des modèles

Le parallélisme de données (par exemple MapReduce) répartit des blocs de données indépendants entre unités de calcul et convient aux traitements massifs. Le parallélisme de contrôle (OpenMP, Pthreads) fractionne le flot d'exécution en threads pour les environnements à mémoire partagée et nécessite une coordination fine. MPI, basé sur l'échange de messages, complète ces approches pour les systèmes distribués où la mémoire n'est pas partagée.

Architectures et Modèles de Calcul Parallèle

Les approches matérielles et logicielles diffèrent selon la nature des ressources et les exigences applicatives. Le choix entre mémoire partagée et mémoire distribuée oriente le modèle de programmation, l'ordonnancement et les stratégies d'optimisation des échanges.

Architectures Parallèles : SIMD et MIMD

• SIMD (Single Instruction, Multiple Data) : une même instruction s'applique simultanément à plusieurs données — adapté aux opérations vectorielles et aux noyaux de calcul réguliers.
• MIMD (Multiple Instruction, Multiple Data) : chaque unité exécute son flux d'instructions ; modèle utilisé pour les architectures de type multicœur et clusters hétérogènes.
• Mémoire partagée : threads ou tâches accèdent à un espace mémoire commun — facilite le partage de données mais impose des mécanismes de synchronisation.
• Mémoire distribuée : chaque nœud possède sa mémoire locale ; la communication explicite (MPI) est nécessaire pour échanger données et synchronisation.

Le modèle MPI pour le calcul distribué

MPI (Message Passing Interface) est le standard pour la programmation sur architectures distribuées. Il fournit des primitives point‑à‑point et des opérations collectives pour structurer les échanges entre processus sur différents nœuds. Conçu pour la scalabilité et le contrôle explicite de la communication, MPI est privilégié lorsqu'il faut maîtriser la topologie réseau et optimiser la bande passante et la latence.

Applications au Calcul Scientifique de Haute Performance

En calcul scientifique, MPI orchestre la répartition des données et du travail entre nœuds pour résoudre des problèmes numériques à grande échelle (simulation numérique, méthodes aux différences finies, éléments finis, etc.). Les codes HPC répartissent la grille de calcul en sous‑domaines, exécutent les calculs locaux et échangent les informations aux interfaces. L'utilisation de MPI permet d'optimiser la scalabilité faible (même taille de problème, plus de ressources) ou la scalabilité forte (taille du problème augmentée avec les ressources) selon les objectifs de recherche, tout en réduisant les coûts de transfert inter‑nœuds et en gérant la hiérarchie mémoire.

Optimisation et Calcul Haute Performance (HPC)

Les techniques d'optimisation réduisent les goulots d'étranglement mémoire, améliorent la localité des données et équilibrent la charge. Il faut adapter les algorithmes aux caractéristiques matérielles (tailles de cache, topologie d'interconnexion, nombre de cœurs) et choisir le modèle le plus adapté : OpenMP ou Pthreads pour la mémoire partagée, MPI pour les nœuds distribués. Les transformations courantes incluent la fusion et l'interchange de boucles, la réduction des synchronisations et la répartition contrôlée des données.

Mesurer l'accélération (Speedup) d'un programme parallèle

Le speedup se calcule classiquement comme le rapport du temps d'exécution séquentiel Ts sur le temps parallèle Tp : speedup = Ts / Tp. Le speedup représente le gain en rapidité d'exécution obtenu par parallélisation. Une accélération linéaire correspond à un speedup proche du nombre de cœurs p (speedup ≈ p). Des cas de speedup super‑linéaire (speedup > p) surviennent parfois lorsque la parallélisation améliore l'utilisation du cache ou la répartition du travail, mais la synchronisation, la communication et la fraction séquentielle limitent souvent ce gain. L'évaluation repose sur mesures expérimentales, profils et benchmarks pour identifier les points critiques.

Outils de profilage et de debug

• Gprof
• Intel VTune
• Outils de traces et perf pour Linux

Loi d'Amdahl et limites du parallélisme

La loi d'Amdahl quantifie l'impact d'une portion séquentielle sur le gain total : si une fraction f du travail reste séquentielle, le speedup maximal avec p processeurs est limité par 1 / (f + (1 − f) / p). Même une petite portion non parallélisable freine fortement l'accélération lorsque le nombre de cœurs augmente. Au‑delà de cette formule, l'efficacité pratique dépend des coûts de communication, de l'overhead d'ordonnancement et de la contention mémoire. Ces contraintes règlent les compromis entre granularité des tâches, réduction des synchronisations et optimisation des transferts entre nœuds.

Exemple concret : les simulations numériques par discrétisation spatiale ou temporelle (schémas aux différences finies, éléments finis) divisent le domaine en sous‑domaines traités en parallèle. La communication aux interfaces et la synchronisation à chaque pas de temps illustrent les compromis entre parallélisation et coûts de communication.

Applications sur Clusters et Supercalculateurs

Sur clusters et supercalculateurs, MPI coordonne les échanges entre nœuds pour répartir données et tâches. Les choix d'implantation doivent considérer les coûts de transfert inter‑nœuds, la hiérarchie mémoire et les performances d'interconnexion afin d'approcher une accélération linéaire lorsque possible, tout en limitant l'impact des échanges et de la latence.

👤 À qui s'adresse ce cours ?

• Public cible : Développeurs et étudiants de niveau avancé souhaitant approfondir la conception d'applications parallèles et le HPC.
• Prérequis : Maîtrise du C/C++ et notions de programmation concurrente et d'architecture des systèmes.

❓ Foire Aux Questions (FAQ)