Differences

This shows you the differences between two versions of the page.

--- commit:2018:01_26 [2018/01/26 17:05] – created crutzen
+++ commit:2018:01_26 [2018/01/29 10:18] (current) – crutzen
@@ Line 3: / Line 3: @@
 ===== Contexte =====
-En refaisant le point sur les performances du parallélisme en formalisme ALE, j’ai pu remarquer que le temps passé dans les multiples mises à jour du maillage volumes finis occupe une place significative de plus en plus importante au sein des algorithmes de convection à mesure que le nombre de threads augmente (voir Figure ci-dessous). Ces routines de mises à jour du maillage volumes finis sont exécutées en série, autrement dit de manière non-concurrente par un seul et unique thread. Par conséquent, nous pouvons espérer aller encore un pas plus loin dans l’amélioration de la scalabilité en introduisant des boucles parallèles dans ces routines. Les itérations de ces boucles étant indépendantes entre elles, l’implémentation concurrente est donc immédiate.
+En refaisant le point sur les performances du parallélisme en formalisme ALE, j’ai pu remarquer que le temps passé dans les multiples mises à jour du maillage volumes finis occupe une place significative de plus en plus importante au sein des algorithmes de convection à mesure que le nombre de threads augmente (voir ''updateMeshBuilders'' dans les Figures 1 et 2 ci-dessous). Ces routines de mises à jour du maillage volumes finis sont exécutées en série, autrement dit de manière non-concurrente par un seul et unique thread. Par conséquent, nous pouvons espérer aller encore un pas plus loin dans l’amélioration de la scalabilité en introduisant des boucles parallèles dans ces routines. Les itérations de ces boucles étant indépendantes entre elles, l’implémentation concurrente est donc immédiate.
-Ajouter une figure !!!
+{{:commit:2018:piecharteulerianstep1.png?400|}}\\
+Figure 1: Répartition du temps d'horloge dans le pas Eulérien (1 thread).
-Toutefois, ces petites modifications du code a priori anodines ont débouchés sur des problèmes particulièrement difficiles à cerner et à surmonter. En effet, suite à cette implantation des boucles parallèles dans les mises à jour du maillage volumes finis, j’ai, d’emblée, rencontré de nombreux plantages dans la batterie de cas-tests. Pire, les cas-tests plantés étaient différents selon les stations de travail utilisées et à chaque réalisation de la batterie. Bref, les résultats de la batterie étaient devenus totalement non-déterministes. De toute évidence, l’ensemble des cas-tests concernés par ces plantages était en particulier les cas-tests de remaillage (''apps.remeshing'', ''apps.remeshing2'', ''apps.welding'' et ''apps.welding2'') ainsi que les cas-tests en formalisme ALE.
+{{:commit:2018:piecharteulerianstep6.png?400|}}\\
+Figure 2: Répartition du temps d'horloge dans le pas Eulérien (6 threads).
+Toutefois, ces petites modifications du code a priori anodines ont débouché sur des problèmes particulièrement difficiles à cerner et à surmonter. En effet, suite à cette implantation des boucles parallèles dans les mises à jour du maillage volumes finis, j’ai, d’emblée, rencontré de nombreux plantages dans la batterie de cas-tests. Pire, les cas-tests plantés étaient différents selon les stations de travail utilisées et à chaque réalisation de la batterie. Bref, les résultats de la batterie étaient devenus totalement non-déterministes. De toute évidence, l’ensemble des cas-tests concernés par ces plantages était en particulier les cas-tests de remaillage (''apps.remeshing'', ''apps.remeshing2'', ''apps.welding'' et ''apps.welding2'') ainsi que les cas-tests en formalisme ALE.
 Pour parvenir à identifier l’origine de ces plantages, il nous faut récupérer l’erreur à l’aide du débogueur de Visual Studio. Pour ce faire, deux options sont possibles :
@@ Line 20: / Line 24: @@
 Le défi a été particulièrement difficile à relever. Notre batterie de cas-tests exécutée sur les différentes stations de travail a été décisive pour nous assurer que les solutions implémentées étaient véritablement thread-safe. Une implémentation peut sembler en effet  fonctionner sur une station de travail mais pas sur une autre. Cela dépend, entre autres, du compilateur utilisé et du système d’exploitation utilisé.
-Le cheminement poursuivi étape après étape est expliqué en détail dans le rapport scientifique et technique n°6 du projet HPC4WE. Ce rapport décrit les différentes solutions que nous avons implémentées dans le code, les obstacles que nous avons rencontrés, mais aussi comment nous avons surmonté ces obstacles et comment nous avons affiné nos implémentations. Nous avons aussi analysé méticuleusement les performances de chacune des solutions implémentées (voir les différentes courbes tirées en fonction du nombre de threads qui sont relatives à chacun de nos essais d’implémentation sur la Figure ci-dessous). A cette fin, nous avons identifié des cas-tests pour lesquels les coûts CPU se montrent particulièrement sensibles aux accès à la base de données.
+Le cheminement poursuivi étape après étape est expliqué en détail dans le rapport scientifique et technique n°6 du projet HPC4WE. Ce rapport décrit les différentes solutions que nous avons implémentées dans le code, les obstacles que nous avons rencontrés, mais aussi comment nous avons surmonté ces obstacles et comment nous avons affiné nos implémentations. Nous avons aussi analysé méticuleusement les performances de chacune des solutions implémentées (voir les différentes courbes tirées en fonction du nombre de threads qui sont relatives à chacun de nos essais d’implémentation sur la Figure 3 ci-dessous). A cette fin, nous avons identifié des cas-tests pour lesquels les coûts CPU se montrent particulièrement sensibles aux accès à la base de données.
+L’objectif de l’implémentation proposée dans ce commit est de permettre des agrandissements et accès concurrents de la base de données. L'implémentation finalement retenue est décrite ci-dessous.
+==== Instanciation des objets DBValue ====
+Dans l’implémentation originelle, l’allocation en mémoire des objets ''DBValue'' était réalisée à la volée lors de leur premier accès.
+Ici, nous avons fait le choix d’une allocation dès à présent directe des objets ''DBValue'' lors de l’agrandissement du vecteur. Ce choix présente deux avantages. D’une part, nous n’avons pas de gaspillage de la mémoire. En effet, un élément important à noter est notre système actuel de numérotation des nœuds de la base de données nous permet avantageusement de ne pas avoir de trous dans le vecteur, autrement dit de ne pas être creux. D’autre part, ce choix nous permet surtout de simplifier la mise en place d’une implémentation qui soit à la fois thread-safe et peu coûteuse. En effet, cette implémentation nous permet de nous dispenser de définir les éléments du vecteur comme des pointeurs atomiques (''tbb::atomic'') de ''DBValue''. De simples pointeurs de ''DBValue'' suffisent comme éléments du vecteur.
+==== Agrandissement de la base de données ====
+L’agrandissement du vecteur de la classe ''DBSet'' (''growTo(DBIndex n)'') est dès à présent réalisé avec un patron de conception de type verrouillage à double test. Dans ce dernier, l’indice ''DBIndex'' //n// du nœud est comparé à la taille du vecteur qui est une variable atomique synchronisée entre les différents threads, et ce avant et après acquisition du verrou.
+L’avantage de ce patron de conception est que le coût du verrou n’est pas significatif : nous en payons le prix uniquement au premier accès de l’élément, les accès ultérieurs ne nécessitent plus aucune acquisition du verrou.
+Il est important de noter que la taille du vecteur se doit d’être déclarée comme une variable atomique, que ce soit par la librairie TBB ou bien par le C++11. Dans le cas contraire, si cette variable n’est pas déclarée comme atomique, il n’est pas garanti que le patron de conception ait le comportement attendu.
+==== Vecteur std ====
+L’hypothèse fondamentale d’un vecteur de type concurrent est d’éviter toutes réallocations de la mémoire lors de l’agrandissement du vecteur. Un vecteur concurrent ne déplace jamais ses éléments existants lorsqu’il s’agrandit. Il alloue une série de tableaux contigus. Ainsi, nous pouvons agrandir le vecteur dynamiquement pendant d’autres accès concurrents.
-L’objectif de l’implémentation proposée dans ce commit est de permettre des agrandissements et accès concurrents de la base de données.
+A contrario, avec un vecteur ''std'', des réallocations de la mémoire peuvent survenir si la nouvelle taille du vecteur est supérieure à sa capacité. Lors d’une réallocation de la mémoire, d’un vecteur ''std'', un nouvel espace mémoire est alloué pour un nouveau vecteur, les éléments de l’ancien vecteur sont déplacés successivement vers le nouveau vecteur et l’espace mémoire de l’ancien vecteur est libéré. En conséquence, les agrandissements et accès concurrents ne peuvent être garantis thread-safe au cours des réallocations de la mémoire.
+Toutefois, nous avons fait le choix de nous affranchir du type concurrent du vecteur de la base de données, c’est-à-dire de retourner à un simple vecteur ''std''. Ainsi, un premier avantage est que nous ne payons plus le surcoût du vecteur concurrent par rapport au vecteur ''std''; autrement dit, le code exécuté en série n’est plus pénalisé sur le surcoût CPU associé à ce type de vecteur. Une seconde raison de ce choix est que notre implémentation ne repose ainsi plus sur une implémentation spécifique d’un conteneur de la librairie TBB (''tbb::concurrent_vector'').
-Dans l’implémentation originelle, l’allocation en mémoire des objets ''DBValue'' était réalisée à la volée lors de leur premier accès. Ici, nous avons fait le choix d’une allocation dès à présent directe des objets ''DBValue'' lors de l’agrandissement du vecteur. Ce choix présente deux avantages. D’une part, nous n’avons pas de gaspillage de la mémoire. En effet, un élément important à noter est notre système actuel de numérotation des nœuds de la base de données nous permet avantageusement de ne pas avoir de trous dans le vecteur, autrement dit de ne pas être creux. D’autre part, ce choix nous permet surtout de simplifier la mise en place d’une implémentation qui soit à la fois thread-safe et peu coûteuse. En effet, cette implémentation nous permet de nous dispenser de définir les éléments du vecteur comme des pointeurs atomiques (''tbb::atomic'') de ''DBValue''. De simples pointeurs de ''DBValue'' suffisent comme éléments du vecteur.
+Pour ce faire, la solution retenue consiste à réserver l’espace mémoire nécessaire des différents vecteurs de la base de données avant d’exécuter les parties concurrentes du code. Ainsi, nous empêchons toute réallocation de la mémoire au cours des accès à la base de données.
+Par conséquent, il nous faut connaître la taille //a priori// des vecteurs de la base de données avant même d’entamer chacune des boucles parallèles. Lors de ces opérations d'agrandissements, nous opérons de la manière suivante :
+  * Nous avons pris la taille du vecteur ''positionSet'' comme capacité mémoire des vecteurs des champs ''actualAccSet3'', ''actualVelocSet3'' et ''actualDispSet3''.
+  * Pour les champs ''oldResSet3'', ''actualDispTempSet'', ''absoluteTempSet'', ''velocTempSet'', ''remeshedDispSet3'', ''remeshedVelocSet3'', ''remeshedAccSet3'', ''remeshedDispTempSet'', ''remeshedVelocTempSet'' et ''lagrangianSet'', nous avons pris comme capacité mémoire la taille du vecteur positionSet pour autant que leur taille soit strictement supérieure à zéro.
+  * La capacité mémoire des champs ''actualExtForcesSet3'', ''actualIntForcesSet3'', ''actualInertForcesSet3'', ''actualDampForcesSet3'' est respectivement mise égale à celle des champs ''previousExtForcesSet3'', ''previousIntForcesSet3'', ''previousInertForcesSet3'' et ''previousDampForcesSet3''.
-L’agrandissement du vecteur de la classe ''DBSet'' (''growTo(DBIndex n)'') est dès à présent réalisé avec un patron de conception de type verrouillage à double test. Dans ce dernier, l’indice ''DBIndex'' //n// du nœud est comparé à la taille du vecteur qui est une variable atomique synchronisée entre les différents threads, et ce avant et après acquisition du verrou. L’avantage de ce patron de conception est que le coût du verrou n’est pas significatif : nous en payons le prix uniquement au premier accès de l’élément, les accès ultérieurs ne nécessitent plus aucune acquisition du verrou. Il est important de noter que la taille du vecteur se doit d’être déclarée comme une variable atomique, que ce soit par la librairie TBB ou bien par le C++11. Dans le cas contraire, si cette variable n’est pas déclarée comme atomique, il n’est pas garanti que le patron de conception ait le comportement attendu.
+Enfin, il faut ajouter que cette préallocation de la mémoire est réalisée dans les cas suivants :
+  * Dans ''TimeIntegration::stepInitialisation()'' après le ''setStep(nt, time)''.
+  * Dans ''IPMeshBuilder'', juste avant la boucle parallèle de mises à jour du maillage volumes finis.
+  * Dans ''ALEStepTransfer'', juste avant la première boucle parallèle de mises à jour du maillage volumes finis (convection ALE).
-L’hypothèse fondamentale d’un vecteur de type concurrent est d’éviter toutes réallocations de la mémoire lors de l’agrandissement du vecteur. Un vecteur concurrent ne déplace jamais ses éléments existants lorsqu’il s’agrandit. Il alloue une série de tableaux contigus. Ainsi, nous pouvons agrandir le vecteur dynamiquement pendant d’autres accès concurrents. A contrario, avec un vecteur ''std'', des réallocations de la mémoire peuvent survenir si la nouvelle taille du vecteur est supérieure à sa capacité. Lors d’une réallocation de la mémoire, d’un vecteur ''std'', un nouvel espace mémoire est alloué pour un nouveau vecteur, les éléments de l’ancien vecteur sont déplacés successivement vers le nouveau vecteur et l’espace mémoire de l’ancien vecteur est libéré. En conséquence, les agrandissements et accès concurrents ne peuvent être garantis thread-safe au cours des réallocations de la mémoire. Toutefois, nous avons fait le choix de nous affranchir du type concurrent du vecteur de la base de données, c’est-à-dire de retourner à un simple vecteur ''std''. Ainsi, un premier avantage est que nous ne payons plus le surcoût du vecteur concurrent par rapport au vecteur ''std''; autrement dit, le code exécuté en série n’est plus pénalisé sur le surcoût CPU associé à ce type de vecteur. Une seconde raison de ce choix est que notre implémentation ne repose ainsi plus sur une implémentation spécifique d’un conteneur de la librairie TBB (''tbb::concurrent_vector''). Pour ce faire, la solution retenue consiste à réserver l’espace mémoire nécessaire des différents vecteurs de la base de données avant d’exécuter les parties concurrentes du code. Ainsi, nous empêchons toute réallocation de la mémoire au cours des accès à la base de données. Par conséquent, il nous faut connaître la taille //a priori// des vecteurs de la base de données avant même d’entamer chacune des boucles parallèles.
+==== Conclusions ====
+Finalement, les efforts investis ont été récompensés puisque, outre la gestion dès à présent thread-safe des accès à la base de données, nous avons engrangé des progrès en performances très significatifs par rapport à l’implémentation originelle (voir Figure 3 ci-dessous). Cette Figure 3 illustre le gain apporté par les seules modifications de l’implémentation de la base de données par rapport à la révision officielle précédente.
+Ici, les gains affichés ne prennent pas en compte les gains apportés par l’implémentation concurrente des mises à jour du maillage volumes finis, autrement dit cette partie du code reste exécutée de manière purement séquentielle par un seul et unique thread. La version implémentée dans ce commit correspond à la courbe "Meta H Std" de couleur turquoise sur la Figure.
-Finalement, les efforts investis ont été récompensés puisque, outre la gestion dès à présent thread-safe des accès à la base de données, nous avons engrangé des progrès en performances très significatifs par rapport à l’implémentation originelle (voir Figure ci-dessous). Cette Figure illustre le gain apporté par les seules modifications de l’implémentation de la base de données par rapport à la révision officielle précédente.
+{{:commit:2018:reldiffsofficoncurrentrf.png?400|}}\\
-Ici, les gains affichés ne prennent pas en compte les gains apportés par l’implémentation concurrente des mises à jour du maillage volumes finis, autrement dit cette partie du code reste exécutée de manière purement séquentielle par un seul et unique thread.
+Figure 3 : Comparaison des coûts CPU - Gain du temps d'horloge des nouvelles implémentations par rapport à la révision officielle.
 En résumé, parmi les solutions thread-safe implémentées, celle que nous avons retenue ici dans ce commit offre les meilleurs performances en coût CPU, elle est la plus simple à mettre en place (les modifications apportées dans ce commit sont en effet très limitées dans le code source) et enfin elle nous permet de nous émanciper de notre dépendance à la librairie TBB de Intel (elle ne repose plus sur un conteneur spécifique d’une librairie particulière (''tbb::concurrent_vector'')).
@@ Line 38: / Line 71: @@
 ===== Interaction partielle =====
-Il est à noter que la mise en place de l’implémentation expliquée ci-dessus a eu un des effets collatéraux sur les cas-tests ''apps.welding2''. En effet, j’ai été confronté à d’autres plantages, des plantages systématiques des cas-tests ''apps.welding2''.
+Il est à noter que la mise en place de l’implémentation expliquée ci-dessus a eu un effet collatéral sur les cas-tests ''apps.welding2''. En effet, j’ai été confronté à d’autres plantages, des plantages systématiques des cas-tests ''apps.welding2''.
 L’erreur rencontrée est que les interactions partielles (utilisées pour le transfert de données) ont leur attribut ''shcut'' qui pointe vers ''NULL'' après avoir généré leurs éléments. Cela nous empêche, dans la méthode ''toDofSet(InteractionSet *boundaries, LoadingSet *bcLoads)'' de la classe ''IPMeshBuilder'', de remonter à ''pointersToSets'' pour préallouer la mémoire des vecteurs de la base de données juste avant la génération du maillage volumes finis au travers des boucles parallèles (''update()'').