Si A et B sont exécutées séquentiellement, on pourra observer l’exécution suivante :

Le point important, c’est que B ne commencera à s’exécuter QUE lorsque A sera terminée. Dit autrement, à tout instant, seule UNE tâche est en cours (commencée mais pas encore terminée) : soit A, soit B, mais on n’observe jamais de moment où A et B ont toutes deux commencé leur exécution, sans l’avoir encore terminée.

À l’inverse, si A et B sont exécutées de façon concurrente, on pourra observer l’exécution suivante :

Ici, B n’a pas attendu la fin de A pour démarrer : il existe des moments (qui sont même majoritaires) où A et B ont toutes deux commencé leur exécution, sans l’avoir encore terminée.

Alors, est-ce que A et B s’exécutent "en même temps" ? Ça dépend du sens donné à "en même temps" :

Le premier point est particulièrement vrai si l’alternance a lieu trop vite pour être suivie à l’oeil nu (par exemple si la durée de chaque tick est de 10 ms) : un observateur humain aura l’impression que les deux tâches s’exécutent "en même temps", sans voir qu’en réalité elles s’exécutent plutôt "chacune à leur tour".

Voyons la définition qu’en donne Wikipedia :

Ici aussi, une illustration aide à comprendre la différence :

Il y a une différence de taille par rapport à la situation précédente : à un instant donné, les tâches A et B progressent réellement en même temps, et ce quelle que soit notre définition de en même temps :

Une exécution parallèle n’est donc possible que sur un processeur qui dispose d’au moins deux cœurs, afin qu’à un instant donné celui-ci puisse faire progresser A et B en même temps plutôt que tour à tour. Jusqu’à l’avènement des processeurs multi-cœurs, le fait pour un ordinateur de faire "plusieurs choses en même temps" (par exemple jouer au solitaire en attendant qu’un encodage d’une vidéo en tâche de fond se termine) n’était qu’une illusion : les deux tâches alternaient juste très vite, l’exécution était concurrente non-parallèle. Certes cette illusion ne fait pas gagner de temps par rapport à une exécution séquentielle (dans les deux cas, le temps total est de 40 ticks), mais on y gagne tout de même en utilisabilité : il ne serait pas très pratique qu’un ordinateur freeze complètement tant que l’encodage d’une vidéo n’est pas terminé…​

À noter que l’exécution parallèle illustrée ci-dessus est un cas particulier d’exécution concurrente : ici non plus, B n’a pas eu à "attendre" la fin de A pour progresser.

Il n’est donc pas du tout pertinent d’opposer exécution concurrente et exécution parallèle, on a plutôt les catégories suivantes :

En théorie, avec une exécution réellement parallèle, on peut espérer un temps d’exécution total plus rapide, ce qu’on voit sur l’illustration ci-dessus : pour le même nombre de ticks (25 A et 15 B), le temps total pour l’exécution parallèle est de 25 ticks contre 40 ticks pour les exécutions séquentielle et concurrente précédentes.

En fait, l’illustration ci-dessus est idéalisée. Dans la pratique, il se peut que l’exécution parallèle se rapproche plutôt de cette illustration plus réaliste :

On passe de 40 à 32 ticks, le temps total est divisé par 1,25.

En pratique, le gain de temps d’exécution théorique est donc à prendre avec des pincettes : on ne le divise pas toujours par deux, et comme illustré en fin d’article, on peut même ralentir un programme en le parallélisant ! Sans aller jusque là, de nombreux facteurs peuvent expliquer que le temps d’exécution observé est supérieur à celui attendu :

Comme partout ailleurs quand on parle de perfs, il faut mesurer et benchmarker son cas d’usage plutôt que de faire des prédictions ou des suppositions.

Tout d’abord, on va simuler un travail à réaliser : _heavy_work. Celui-ci va faire une série de amount calculs inutiles :

Il serait plus illustratif de randomiser un peu, ou d’avoir une charge de travail asymétrique entre A et B, mais ça nuirait à la simplicité de l’exemple, et surtout aux mesures qu’on va faire : on va en rester à cet exemple simpliste.

Ce travail est exécuté en boucle dans une computer_task, identifiée par une letter (A ou B), et ce autant de fois qu’il y a de ticks nb_of_ticks. Lorsqu’elle a fini un tick, la task publie son identifiant dans une queue data_to_write, et notifie une condition-variable cv :

Une autre tâche displayer_task est chargée de consommer les lettres publiées dans la queue lorsqu’elle est notifiée par la condition-variable cv, et convertit progressivement une string result depuis un état initial (initial_string) du type ------------ vers un état final indiquant comment le travail a progressé BAABBABBBAAA :

Pour l'exécution séquentielle, la displayer_task s’exécute en tâche de fond dans un thread displayer, mais les deux computer_task sont lancées successivement dans le thread principal :

L'exécution concurrente parallèle est identique à l’exécution séquentielle, sauf que les deux computer_task sont lancées chacune dans un thread indépendant. Le thread principal ne fait rien d’autre que coordonner tout ce beau monde :

Pour l'exécution concurrente non-parallèle, soyons rusé comme le renard : on va réutiliser le code parallèle, mais on va le forcer à s’exécuter sur un seul cœur de processeur avec taskset :

Du coup, si le binaire parallèle est bin_PARALLEL, pour tester le cas où l’exécution est concurrente non-parallèle, on peut lancer :

Ceci aura pour effet d’exécuter bin_PARALLEL sur un seul (le premier) cœur de processeur : à tout instant, le processeur ne pourra faire progresser qu’un seul thread, et il alternera entre les différents threads, c’est bien la définition d’une exécution concurrente non-parallèle. Une alternative est d’utiliser un mutex pour garantir que seul un thread s’exécute à chaque instant.

En séquentiel, ça pourrait donner quelque chose comme :

Sur ma machine, lancé avec un amount de 500000000, time m’indique que ce programme séquentiel mets 2,71 secondes à s’exécuter :

Comme précédemment, les mesures individuelles n’ont pas d’importance en soi, seule leur importance relative compte.

Un dev vigilant remarquera que ce type de calcul, répété deux fois, où les entrées comme les sorties sont indépendantes, se prête particulièrement bien à la parallélisation, et il n’aurait pas tort. Lançons donc les deux calculs en parallèle, dans deux threads :

Ce dev vigilant, mais un peu trop confiant, pourrait se dire qu’il est inutile de benchmarker son cas d’usage, car avec un exemple aussi simple, dans des conditions aussi idéales, on ne peut QUE accélérer le programme en le parallélisant. Pourtant, il aurait tort de ne pas refaire ses mesures :

Surprise ! Le temps d’exécution a AUGMENTÉ, et pas qu’un peu : on est à 151% du temps d’exécution séquentiel !

Incrédule ? Vous pouvez faire l’expérience chez vous, le code est ici. Vu que l’exemple est simpliste, attention à compiler en -O0 pour que g++ n’optimise pas notre code bateau.

Expliquer en détail l’origine de ce ralentissement dépasse le cadre de ce post, mais en résumé, les variables result_even et result_odd étant contigües en mémoire, si un thread modifie la première variable, il invalide le cache du cœur de processeur de l’autre thread, qui doit donc effectuer de coûteuses lectures/écritures mémoire qu’il n’aurait pas eu à faire sinon.

Le surcoût apporté par ces opérations dépasse le gain obtenu par la parallélisation, et au final, on dégrade les performances. La partie contre-intuitive est que ce phénomène intervient alors même que les variables sont indépendantes dans le code, d’où le nom de false sharing. C’est un exemple de situation où les détails bas-niveau du fonctionnement d’un processeur ont un effet direct sur les performances d’un programme ; pour les curieux, ce repo est une mine d’or qui en contient bien d’autres.

Pour éviter ce phénomène, il suffit d’espacer les variables en mémoire, de sorte que la modification d’une variable n’ait pas d’impact sur le cache mémoire du processeur contenant l’autre variable. Voici un exemple d’implémentation avec l’attribut aligned de g++ :

Avec cette modification, on obtient bien un temps d’exécution plus conforme à ce qu’on attendait, à 57% du programme séquentiel :

À noter que le code ci-dessus, s’il permet de montrer qu’on est bien en face d’un false sharing, n’est pas la meilleure façon d’adresse le problème. Mieux vaut en effet ne pas toucher à l’alignement des variables :

Et à la place modifier la fonction heavy_task pour qu’elle travaille principalement sur une variable locale, et ne mute la variable "partagée" qu’une seule fois, à la fin du traitement :

On trouve alors un temps d’exécution encore meilleur, à 53% du programme séquentiel :

Ce qu’il faut retirer de ce bonus, ce n’est ni le phénomène de false sharing, ni la façon de l’éviter.

Ce qu’il faut retenir, c’est qu'il est indispensable de benchmarker son cas d’usage, plutôt que de supposer ou prévoir les résultats d’une parallélisation de son code. Et si possible, sur la machine qui exécutera le programme.

En effet, non seulement paralléliser son code apporte une tétra-chiée d’écueils pas toujours faciles à éviter, et encore moins faciles à reproduire et débugger, mais en plus, le gain en temps d’exécution n’est pas garanti.