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

Sommaire du cours PDF

• Introduction
• KaaPI
• Pthreads
• OpenMP
• Composants parallèles
• MapReduce
• Ordonnancement / Exécution des tâches
• Dépendances 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 parallèle. Sur des architectures multi‑processeurs, le parallélisme permet d'exécuter des calculs simultanément pour obtenir un gain de performance mesurable (speedup) et diminuer la latence globale. Les gains réels dépendent de la fraction séquentielle de l'algorithme et de la qualité de l'ordonnancement des tâches.

Comparaison des modèles

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

Le modèle MPI pour le calcul distribué

MPI (Message Passing Interface) est le standard de fait pour la programmation parallèle sur architectures distribuées. Il fournit des primitives d'envoi/réception et des fonctions collectives permettant de structurer les échanges entre processus s'exécutant on différents nœuds. MPI est conçu pour la scalabilité forte et reste le choix privilégié lorsqu'il faut contrôler explicitement la communication et la topologie des échanges sur des clusters ou super‑calculateurs.

Applications sur Clusters et Supercalculateurs

Sur clusters de calcul et supercalculateurs, MPI orchestre la communication entre nœuds de calcul pour répartir les données et les tâches. Les décisions d'implantation doivent tenir compte des coûts de transfert inter‑nœuds, de la hiérarchie mémoire et des performances d'interconnexion. L'objectif est d'approcher une accélération linéaire lorsque c'est possible, tout en gérant la topologie du réseau, la bande passante et la latence pour limiter l'impact des échanges entre nœuds.

Standard MPI et programmation à mémoire distribuée

Le standard MPI formalise les API, les comportements et les mécanismes pour la programmation à mémoire distribuée. Il permet de gérer la synchronisation, la communication point‑à‑point et les opérations collectives sans supposer de mémoire partagée. Dans les applications HPC, on l'utilise pour répartir données et calculs sur des nœuds distincts, optimiser la bande passante inter‑nœuds et réduire la contention mémoire locale. La conception logicielle doit alors tenir compte des coûts de communication et viser à minimiser les transferts.

Optimisation et Calcul Haute Performance (HPC)

Les techniques d'optimisation ciblent la réduction des goulots d'étranglement mémoire, l'amélioration de la localité des données et l'équilibrage de charge. Dans un contexte HPC, il faut adapter les algorithmes aux caractéristiques matérielles (cache, interconnexion, nombre de cœurs) et choisir le modèle de programmation le plus adapté — OpenMP ou Pthreads pour la mémoire partagée, MPI pour les nœuds distribués. Les optimisations comprennent la transformation des boucles, la réduction des synchronisations et la répartition finement 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). Une accélération linéaire correspond à un speedup égal au nombre de cœurs (speedup ≈ p pour p cœurs) : c'est le cas idéal où chaque processeur apporte un gain proportionnel. Il existe cependant des cas de speedup super‑linéaire (speedup > p), souvent dus à une meilleure utilisation des caches ou à des effets de mémoire qui réduisent le travail global par rapport à l'exécution séquentielle. En pratique, la synchronisation, la communication et la fraction séquentielle limitent ce gain. L'évaluation repose sur mesures expérimentales, profils et benchmarks pour identifier les points critiques.

Outils de profilage courants :

• 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 est limité par 1 / (f + (1 − f) / p) pour p processeurs. Autrement dit, même une petite portion non parallélisable freine fortement l'accélération perçue lorsque le nombre de cœurs augmente. Cette loi guide les choix d'optimisation et la priorisation des efforts pour paralléliser les sections critiques.

Limites théoriques : Loi d'Amdahl et efficacité

Au‑delà de la formule, l'efficacité pratique dépend aussi des coûts de communication, de l'overhead d'ordonnancement et de la contention mémoire. La Loi d'Amdahl insiste sur la nécessité de réduire la fraction séquentielle et d'améliorer la granularité des tâches. Pour certaines classes de problèmes, on privilégie la scalabilité faible (problème croissant avec les ressources) ou la scalabilité forte (même taille de problème, plus de nœuds) selon les besoins opérationnels.

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

👤 À 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)

Qu'est-ce que la programmation parallèle ?
Technique permettant d'exécuter plusieurs tâches simultanément pour améliorer les performances sur matériel multi‑cœur et multi‑nœuds.

Quels outils sont utilisés pour la programmation parallèle ?
Parmi les plus courants : OpenMP et Pthreads pour la mémoire partagée, KaaPI pour certains modèles orientés tâches, et MPI pour les communications entre processus distribués.

Quelle est la différence entre OpenMP et MPI ?
OpenMP cible la mémoire partagée et utilise des directives pour paralléliser des boucles et sections de code au sein d'un même processus. MPI repose sur l'échange explicite de messages entre processus et s'adapte aux environnements distribués où la mémoire n'est pas partagée. Le choix dépend de l'architecture cible et des contraintes de communication.