4 · OpenMP et threads¶

Complément de ICPA24. Ce chapitre traite ce qui dépasse l'API : les modèles mémoire, les structures non bloquantes, la vérification de correction, et les runtimes de tâches.

Il comble aussi partiellement le renoncement à PRCV24 (programmation concurrente et vérification), inaccessible depuis le cursus FISA.

Difficulté : ★★★ · ⏱ 25 h

Le noyau utile d'OpenMP¶

Le standard OpenMP compte plusieurs centaines de constructions. En pratique, une vingtaine suffisent à écrire du code performant — c'est la thèse du livre The OpenMP Common Core. Voici cette vingtaine.

Le parallélisme de boucle : parallel, for, parallel for, avec les clauses private, shared, firstprivate, reduction, schedule, collapse, nowait.

La synchronisation : barrier, critical, atomic, single, master, ordered, les verrous omp_lock_t.

Les tâches : task, taskwait, taskgroup, depend, taskloop.

Le SIMD : simd, for simd, declare simd.

Les accélérateurs : target, target data, map, teams, distribute.

L'environnement : omp_get_num_threads, omp_get_thread_num, omp_get_wtime, et les variables OMP_NUM_THREADS, OMP_PROC_BIND, OMP_PLACES, OMP_SCHEDULE, OMP_DISPLAY_ENV, OMP_DISPLAY_AFFINITY.

C'est tout. Le reste est de la spécialisation.

Les cinq causes d'échec d'une parallélisation¶

Quand #pragma omp parallel for ne donne pas l'accélération attendue, c'est presque toujours l'une de ces cinq causes. Les diagnostiquer dans cet ordre.

1. Le noyau est limité par la bande passante mémoire¶

Symptôme : l'accélération plafonne à 4, 6 ou 8 threads et n'augmente plus, quel que soit le nombre de cœurs. C'est le cas le plus fréquent et le plus surprenant pour un débutant.

Explication : quelques cœurs suffisent à saturer le contrôleur mémoire. Les cœurs supplémentaires attendent. Un noyau à faible intensité arithmétique n'accélérera jamais linéairement.

Diagnostic : calculer l'intensité arithmétique et la comparer à l'intensité de bascule. Voir Modèles de performance.

Remède : aucun au niveau de la parallélisation. Il faut augmenter l'intensité arithmétique, donc changer l'algorithme ou la disposition des données.

2. Le faux partage¶

Symptôme : la version parallèle est plus lente que la séquentielle, et l'écart s'aggrave avec le nombre de threads.

Explication : deux threads écrivent dans la même ligne de cache. Le protocole de cohérence de cache invalide la ligne chez l'autre à chaque écriture, et la ligne fait des allers-retours entre les cœurs.

Diagnostic : perf c2c, qui identifie la ligne et les adresses en cause.

Remède : séparer les données par thread d'au moins une ligne de cache (64 octets), ou utiliser des variables locales accumulées en fin de boucle, ou reduction.

3. La localité NUMA¶

Symptôme : l'accélération est correcte jusqu'au nombre de cœurs d'un domaine NUMA, puis se dégrade.

Explication : la règle de la première touche. Si les données ont été initialisées par un seul thread, elles sont toutes dans un seul domaine.

Diagnostic : numastat, et comparer l'accélération en limitant l'exécution à un domaine (numactl --cpunodebind=0 --membind=0).

Remède : initialiser en parallèle avec le même découpage. Voir Architecture et mémoire.

4. Le déséquilibre de charge¶

Symptôme : l'accélération est de l'ordre de 50 à 70 % de l'idéal, sans plafonnement franc.

Diagnostic : mesurer le temps passé par chaque thread. Un profileur parallèle le montre immédiatement ; à défaut, un chronométrage manuel par thread suffit.

Remède : schedule(dynamic) ou schedule(guided), ou passer aux tâches. Mais attention, dynamic a un coût de distribution : sur une boucle équilibrée, il est moins bon que static.

5. Le surcoût de la région parallèle¶

Symptôme : la boucle parallélisée est plus lente, et elle est courte.

Explication : créer et synchroniser une équipe de threads coûte quelques microsecondes. Si le corps de la boucle prend moins que cela, la parallélisation est une perte nette.

Remède : paralléliser une boucle plus externe, ou utiliser if(n > seuil) sur la directive, ou sortir la région parallèle de la boucle temporelle et n'utiliser #pragma omp for à l'intérieur.

La procédure de diagnostic, dans l'ordre

L'accélération est mauvaise
  │
  ├─ Elle plafonne tôt et net ?          → cause 1 : bande passante
  ├─ C'est plus lent que séquentiel ?    → cause 2 : faux partage
  │                                        ou cause 5 : surcoût
  ├─ Ça se dégrade au-delà d'un socket ? → cause 3 : NUMA
  ├─ C'est 50-70 % de l'idéal ?          → cause 4 : déséquilibre
  └─ La boucle est très courte ?         → cause 5 : surcoût

Les tâches OpenMP¶

Le modèle le plus puissant et le moins utilisé d'OpenMP. Introduit dans OpenMP 3.0, enrichi des dépendances dans la version 4.0.

Le principe : au lieu de découper une boucle, on déclare des unités de travail (task) et des dépendances entre elles (depend(in:…), depend(out:…), depend(inout:…)). Le runtime construit le graphe de dépendances et ordonnance les tâches sur les threads disponibles, avec vol de travail.

Pourquoi c'est puissant : sur les algorithmes irréguliers ou les factorisations par blocs, les tâches expriment le parallélisme réel, qui n'est pas celui d'une boucle.

Exemple — une factorisation de Cholesky par blocs. En boucles parallèles, il faut une barrière entre chaque étape de l'élimination. En tâches avec dépendances, le runtime découvre qu'une partie des mises à jour du bloc suivant peut démarrer avant la fin des précédentes, et recouvre naturellement. Le gain sur une factorisation de taille moyenne est substantiel, et c'est le modèle qu'utilisent les bibliothèques d'algèbre linéaire modernes (PLASMA, Chameleon, DPLASMA).

Les pièges des tâches :

La granularité. Une tâche coûte de l'ordre du microseconde à créer. Des tâches de dix microsecondes de travail sont dominées par le surcoût. Il faut des tâches de l'ordre de la milliseconde, donc des blocs assez gros.
Les dépendances par adresse. depend compare des adresses mémoire, pas des régions. Deux tâches qui touchent des parties disjointes du même tableau, si elles déclarent la même adresse de base, seront sérialisées inutilement.
La récursion sans if. Un algorithme diviser-pour-régner qui crée une tâche à chaque niveau produit une explosion de tâches minuscules. Il faut une clause if(taille > seuil) pour arrêter la création et basculer en séquentiel.

Les modèles mémoire, ou pourquoi votre intuition est fausse¶

Le sujet le plus contre-intuitif de la programmation concurrente, et celui que PRCV24 aurait traité.

Le fait de base : le processeur et le compilateur réordonnent les accès mémoire. Ce code, exécuté par deux threads, peut afficher 0 0 sur une architecture à modèle mémoire faible :

// Initialement x = y = 0
// Thread 1 :             // Thread 2 :
x = 1;                    y = 1;
r1 = y;                   r2 = x;
// Résultat possible : r1 == 0 && r2 == 0

Aucun entrelacement séquentiel des instructions ne produit ce résultat. Il vient du réordonnancement matériel, et il est réellement observable. Sur x86-64, ce cas précis n'arrive pas (le modèle x86 est relativement fort), mais sur ARM ou PowerPC, oui.

Les conséquences pratiques :

Un volatile en C ou C++ ne suffit pas à synchroniser. Il empêche certaines optimisations du compilateur mais ne génère aucune barrière mémoire. C'est l'erreur la plus répandue.
Il faut des atomiques avec un ordre mémoire explicite (std::atomic en C++11, _Atomic en C11) ou des primitives de synchronisation (mutex, barrière) qui les contiennent.
OpenMP définit son propre modèle mémoire, avec la directive flush (souvent implicite dans les barrières et les régions critiques). En pratique, on évite de raisonner à ce niveau et on utilise atomic ou critical.

La règle de survie : ne jamais écrire de code de synchronisation sans verrou (lock-free) sans avoir lu la littérature correspondante. Utilisez les primitives existantes, qui sont correctes.

La vérification de correction¶

C'est ce qui remplace, partiellement, PRCV24.

Outil	Ce qu'il trouve	Coût
ThreadSanitizer (`-fsanitize=thread`)	Courses de données réelles, sur les chemins exécutés	5 à 15× plus lent
Helgrind / DRD (Valgrind)	Courses, mauvais usage des verrous, ordres de verrouillage incohérents	20 à 100× plus lent
Intel Inspector	Courses, interblocages, fuites	Élevé
Archer	Courses spécifiquement dans du code OpenMP, avec moins de faux positifs	Modéré
Model checking (SPIN, TLA+)	Tous les entrelacements possibles d'un modèle abstrait	Effort de modélisation

La pratique minimale, ⏱ 4 h à apprendre

Faites tourner votre code multithread sous ThreadSanitizer une fois par projet. C'est une ligne de compilation, et cela trouve des courses que les tests ne trouveront jamais parce qu'elles ne se manifestent qu'une exécution sur mille.

g++ -fsanitize=thread -g -O1 mon_code.cpp -o mon_code
./mon_code

Limite importante : TSan ne voit que les chemins effectivement exécutés, et il ne comprend pas bien les directives OpenMP (d'où Archer, qui est une extension de TSan pour OpenMP). Il ne remplace pas le raisonnement, mais il trouve l'essentiel.

Pour aller plus loin, le model checking explore tous les entrelacements d'un modèle. C'est puissant et cela demande de modéliser le programme, donc un effort réel. Le TLA+ Video Course de Leslie Lamport est le meilleur point d'entrée si le sujet vous attire.

Les runtimes de tâches, au-delà d'OpenMP¶

Culture utile, parce que ce sont les briques sur lesquelles reposent les codes de production, et parce que c'est le prolongement direct du mini-projet de threads utilisateur de MPPT24.

StarPU (Inria Bordeaux) : ordonnancement de tâches sur machines hétérogènes, avec modèles de performance appris à l'exécution pour décider d'exécuter une tâche sur CPU ou sur GPU. Projet français majeur, utilisé par des bibliothèques d'algèbre linéaire comme Chameleon.
Intel oneTBB : parallélisme de tâches en C++, avec vol de travail. Sert de support d'exécution aux algorithmes parallèles du C++17 dans libstdc++.
Cilk puis OpenCilk : le vol de travail dans sa forme la plus élégante, avec la garantie théorique de Blumofe & Leiserson.
Legion, PaRSEC, HPX : les runtimes de recherche pour l'exascale, qui poussent le modèle à tâches à l'échelle distribuée.
Argobots, Qthreads : des bibliothèques de threads légers en espace utilisateur, exactement ce qu'on écrit dans le mini-projet de MPPT24.

L'article fondateur : Blumofe & Leiserson, Scheduling Multithreaded Computations by Work Stealing (JACM, 1999), qui démontre que le vol de travail atteint un temps d'exécution en \(O(T_1/p + T_\infty)\) où \(T_1\) est le travail total et \(T_\infty\) la profondeur du graphe de dépendances. C'est un excellent candidat pour l'exercice de lecture d'article de PDSP35.

Exercices¶

E1 · ★★ ⏱ 3 h — Les cinq causes, reproduites. Écrire cinq programmes, un par cause d'échec de la section ci-dessus, chacun exhibant son symptôme caractéristique. Mesurer et tracer la courbe d'accélération de chacun. Puis corriger chacun et retracer. Ce jeu de cinq exemples est un excellent support de révision et d'explication à d'autres.

E2 · ★★★ ⏱ 4 h — Cholesky, boucles contre tâches. Implémenter une factorisation de Cholesky par blocs, en deux versions : boucles parallèles avec barrières entre étapes, et tâches avec depend. Mesurer les deux pour plusieurs tailles de bloc. Tracer le temps en fonction de la taille de bloc pour les deux versions : l'optimum n'est pas au même endroit, et la version à tâches est meilleure et moins sensible.

E3 · ★★★ ⏱ 3 h — La granularité des tâches. Un algorithme récursif (tri fusion, ou une somme diviser-pour-régner) avec task, en faisant varier le seuil de basculement en séquentiel de 1 à \(10^6\). Tracer le temps en fonction du seuil. La courbe a un minimum net, et les deux extrémités sont catastrophiques — trop de tâches minuscules d'un côté, pas assez de parallélisme de l'autre.

E4 · ★★ ⏱ 2 h — ThreadSanitizer sur du code cassé. Écrire cinq programmes contenant chacun une course de données subtile — un compteur non protégé, une initialisation paresseuse, un double verrouillage naïf (double-checked locking), un volatile utilisé comme synchronisation, une lecture pendant une écriture de structure. Vérifier que TSan les trouve. Puis vérifier que les tests fonctionnels, eux, passent.

E5 · ★★★ ⏱ 4 h — Le coût des primitives. Mesurer le coût en nanosecondes de : une incrémentation ordinaire, une incrémentation atomic, une section critical, un verrou omp_lock_t, une barrière, et une création de région parallèle. Faire varier le nombre de threads. Tracer. Vous verrez que le coût des opérations atomiques et des verrous croît avec le nombre de threads à cause de la contention, alors que celui d'une incrémentation ordinaire ne bouge pas.

E6 · ★★★★ ⏱ 6 h — Une barrière à la main. Implémenter trois barrières : centralisée avec un compteur atomique, à arbre, et par diffusion (dissemination barrier). Mesurer les trois pour 2 à N threads. La centralisée s'écroule par contention, l'arbre est en \(O(\log p)\). C'est un exercice classique de programmation concurrente, et il enseigne la contention mieux que n'importe quelle explication.

E7 · ★★★★ ⏱ 5 h — Explorer StarPU. Reprendre la Cholesky de E2 et la porter sur StarPU, avec des noyaux CPU et, si vous avez un GPU, des noyaux GPU. Observer comment StarPU décide seul de placer les tâches. C'est un aperçu du modèle de programmation que vise la recherche pour les machines hétérogènes.

Ressources¶

Priorité 1 :

Mattson, He, Koniges, The OpenMP Common Core, MIT Press, 2019. La vingtaine de constructions qui compte.
van der Pas, Stotzer, Terboven, Using OpenMP — The Next Step, MIT Press, 2017. Affinité, accélérateurs, tâches, SIMD : les quatre sujets avancés.
Les cartes de référence OpenMP sur openmp.org : quatre pages, le document le plus utile du site.
Les supports OpenMP de l'IDRIS, en français.

Priorité 2 :

Herlihy & Shavit, The Art of Multiprocessor Programming, 2ᵉ éd. La théorie de la synchronisation correcte.
Paul McKenney, Is Parallel Programming Hard, And, If So, What Can You Do About It?, gratuit. Les modèles mémoire, les barrières, le RCU.
Le blog de Jeff Preshing (preshing.com) sur les modèles mémoire et l'atomique. Le plus pédagogique.
Le blog de Georg Hager (blogs.fau.de/hager) pour la performance OpenMP réelle : saturation, effets NUMA, modèle ECM.

Priorité 3 :

Blumofe & Leiserson, « Scheduling Multithreaded Computations by Work Stealing », JACM, 1999.
La documentation de StarPU (starpu.gitlabpages.inria.fr) et de oneTBB.
Le TLA+ Video Course de Leslie Lamport, pour le model checking.
La documentation de ThreadSanitizer et d'Archer.

À retenir¶

Les cinq choses à retenir

Cinq causes expliquent presque tous les échecs de parallélisation : bande passante, faux partage, NUMA, déséquilibre, surcoût de région. Suivez l'arbre de diagnostic dans cet ordre.
Les tâches avec dépendances sont le modèle le plus puissant d'OpenMP et le plus sous-utilisé ; la granularité est le paramètre critique.
volatile ne synchronise rien. Utilisez des atomiques avec un ordre explicite, ou des primitives qui en contiennent.
ThreadSanitizer une fois par projet : une ligne de compilation, et il trouve ce que les tests ne trouveront jamais.
Le coût des primitives de synchronisation croît avec le nombre de threads. Une solution qui marche à 4 threads peut s'écrouler à 64.

Chapitre suivant : GPU et hétérogène.