Commit 2011-04-05

J'ai remis un coup sur mon travail FABULOUS pour avancer un peu sur le parallélisme dans Metafor. Depuis un bout de temps, j'étais arrivé à la conclusion que l'utilisation d'OpenMP n'était vraiment pas intéressante pour faire du parallélisme de type SMP en C++:

• OpenMP est initialement prévu pour du FORTRAN. Il est bien sûr possible de l'utiliser en C++ mais ça conduit à une réécriture des belles boucles utilisant la STL en boucles pourries (for(int i,…). Même le type size_t (généralement un unsigned long int codé sur 8 octets), utilisé pour tirer parti du 64 bits et éviter une belle chiée de warnings, n'est pas supporté par OpenMP… Un petit espoir vient de OpenMP 3.0, qui est proposé par le compilateur Intel 11.1 et gcc 4.4, qui supporte la notion de “tâches parallèles”.
• OpenMP (2.x ou 3.0) n'est pas utilisable avec tous les compilateurs. Par exemple, gcc 4.1 sous clifton ou gaston ne supporte pas du tout OpenMP. De plus, Microsoft vient d'annoncer qu'il ne compte pas supporter OpenMP 3.0 à court terme… Bref, il faudrait idéalement se limiter à OpenMP 2.0 pour garder le compilateur Microsoft que tout le monde utilise par défaut.
• Même en OpenMP 3.0, les problèmes ne sont pas résolus: le code doit être rendu tout laid pour fonctionner et le support des tâches complexes (récursion par exemple) reste extrêmement limité.
• Les perfs OpenMP sous Windows sont abominables (un peu moins avec le compilateur Intel que personne utilise sauf moi). Mon rapport FABULOUS en témoigne.
• Linux a vraiment du mal à gérer les threads sur les machines NUMA. C'est encore pire quand l'hyperthreading est activé. Les tests OpenMP que j'ai effectués sont très difficilement reproductibles.

dans ce contexte bien décevant, j'avais vu quelques infos sur la bibliothèque Threading Building Blocks (TBB) dans les pubs que je reçois d'Intel et ça me semblait plutôt (très) bien ficelé. Je m'étais dit que j'allais essayer, ou plutôt que j'allais faire essayer ça à un TFiste si j'en trouvais un. Finalement, à défaut d'étudiant, j'ai décidé de me lancer moi-même là dedans et le résultat est vraiment très intéressant. Tous les points mentionnés ci-dessous sont résolus:

• TBB est conçu pour le C++ avec une philosophie très comparable à la STL de Stroustrup. Les boucles C++ un peu tordues comme nous en avons dans Metafor sont par exemple tout à fait envisageables. Elles doivent néanmoins être réécrites, mais, cette fois-ci, pour renforcer le caractère “orienté objet” du code et non l'amoindrir comme c'était le cas avec OpenMP. Le code reste beau (…ou plutôt, ne devient pas plus laid qu'il ne l'était!).
• TBB est utilisable avec tous les compilateurs (gcc 4.1 et le msvc de bilou!). On peut donc même se passer du compilateur Intel dont la nouvelle version n'est toujours pas vraiment supportée par Incredibuild et qui prend un temps fou pour compiler les wrappers de mtGeo. Ouf!
• Outre les boucles parallèles de base (parallel_for, parallel_reduce), TBB supporte un système de “tâches” (tasks) extrêmement sophistiqué et efficace. Il est ainsi possible de créer des arbres de tâches très complexes sur plusieurs niveaux (je ne dis pas que c'est simple à faire mais c'est faisable d'après la doc - je ne vois pas actuellement de limitations dans ce qui est envisageable).
• Les perfs TBB ont l'air bien supérieures à OpenMP. Mes premiers tests sur des opérations matricielles me donnent de meilleurs résultats qu'OpenMP (sous Windows, c'était pas difficile, mais aussi sous Linux).
• Le scheduler inclus dans TBB semble beaucoup mieux gérer les machines NUMA et l'hyperthreading. Sous Windows, ça marche très bien et même sans le compilateur Intel.
• TBB propose, en plus de son système de tâches, une lib d'allocation mémoire “parallèle” (tbbmalloc) et des conteneurs “parallèles” type STL (je ne les ai pas encore essayés mais ça me semble très bien fait et très utile). Considérons ça comme le coup de grâce pour OpenMP.

Quels sont les défauts de TBB?

• Il n'est pas possible de compiler sans TBB (du moins sans mettre des #ifdef/#endif partout). En pratique, ce n'est pas un gros problème. Intel TBB est très facile à installer (sous Windows, il suffit de dézipper les binaires précompilés et sous Linux, un simple gmake suffit).
• TBB est GPL ou payant (un peu comme Qt avant Nokia). Comme on aura des licences avec le cluster ça posera pas de problème. Aujourd'hui, j'utilise la version GPL.
• TBB est propriété d'Intel… Que faire donc si Intel décide de bloquer le source ou d'arrêter le projet? Je crois que ce n'est pas un gros problème puisqu'à court terme, on possède le code source qui peut être recompilé. A long terme, le code TBB peut être remplacé par du code similaire d'une autre bibliothèque qui verrait le jour. Vu que la syntaxe est très proche de la STL, ça ne devrait pas être très différent. Je me suis aussi rendu compte que le gros du travail de parallélisation est de réécrire les classes pour qu'elles soient “thread-safe”. Ce travail est indépendant du système de thread utilisé et, au final, très peu d'endroits font/feront explicitement appel aux routines TBB.

Bilan très positif donc! Metafor a été mis à jour et nécessite maintenant TBB. Le nombre de threads est géré en ligne de commande par l'option “-j” ou, dans le jeu de données, par une classe IntelTBB similaire aux classes Blas et OpenMP. Par défaut, si on ne spécifie rien, TBB alloue un nombre de threads qui dépend de la charge machine (et qui peut varier en cours de calcul!). Je me suis donc arrangé pour que TBB n'alloue qu'un seul thread par défaut. Ca permet d'avoir une batterie de test reproductible.

J'ai parallélisé le mailleur Gen4 avec Intel TBB. J'ai pris ça comme un exercice “réduit” avant de m'attaquer à Metafor et sa boucle d'assemblage élémentaire. Deux routines ont été parallélisées:

• La routine d'optimisation qui recherche la meilleure découpe du domaine. Il s'agit d'une double boucle sur deux std::list; autrement dit, impossible à faire avec OpenMP. J'utilise un “parallel_do” et un nouvel itérateur customisé qui encapsule les deux itérateurs sur les listes. La mise à jour du minimum de la fonction objectif se fait à l'aide d'un “spin_mutex”. J'obtiens de très bonnes perfs (speedup de x3.25 avec 4 threads sur ma machine quad-core et même x4.87 avec 8 threads et l'hyperthreading!).
• La routine de recherche d'intersection de la ligne de découpe avec le background mesh. Ici, il s'agit d'une simple boucle sur une liste d'arêtes qu'on traite une à une. Le parallel_do ne marche pas bien et j'ai du utiliser un “parallel_for” (j'ai testé aussi un “parallel_reduce” qui n'apporte rien mais qui est plus joli).

La visu permet de voir l'état du maillage pendant de sa construction. L'affichage est mis à jour tous les 0.3 sec. Évidemment, cet affichage ralentit légèrement le mailleur (le thread graphique n'est pas un thread séparé comme dans Metafor - le mailleur est donc arrêté pendant cette mise à jour de l'affichage). Pour obtenir les meilleures perfs, il faut donc désactiver la visu. Par contre, si on l'utilise pour débuguer, on voit enfin ce qui se passe.

Je me suis attaqué à la parallélisation de Metafor. Le solveur linéaire étant déjà parallèle, il fallait paralléliser le calcul des forces et le calcul de la matrice de raideur tangente. Il restera ensuite la détection du contact pour que tout soit parallèle.

Dans Metafor, le calcul des forces est effectué par la classe StrVector et plus particulièrement sa fonction membre generalForce. J'ai modifié la boucle sur les éléments pour qu'elle soit compatible avec TBB. A ce niveau, deux choix étaient possibles:

• soit utiliser un parallel_for: la boucle est alors divisée en un nombre de tâches relativement grosses correspondant à l'assemblage de plusieurs éléments. Néanmoins, dans ce cas, il faut avoir accès à un itérateur aléatoire; il n'est donc pas possible d'utiliser l'itérateur ElementIterator qui permet de “sauter” les éléments cassés. De plus, il y a de fortes probabilités pour que la charge de travail soit mal répartie (certains éléments peuvent se calculer plus vite que d'autres). Enfin, si on veut que ça soit réellement efficace, il faut effectuer un assemblage dans des vecteurs distincts pour chaque thread, suivi d'une “réduction”.
• soit utiliser un parallel_do: chaque itération de la boucle est une seule tâche (évidemment plus petite que dans le cas précédent). L'intérêt est de pouvoir utiliser l'itérateur ElementIterator. Par contre, comme chaque tâche est petite, on risque de subir de grosses pertes de performances dans la gestion des tâches en elle-même. L'assemblage est effectué dans une section critique protégée par un mutex.

Actuellement, je me suis orienté vers un parallel_do mais ce choix n'est peut-être pas définitif.

Au niveau des exceptions qui peuvent se produire pendant le calcul des forces (plasticité non convergée, jacobien négatif, etc.), l'exception est interceptée par TBB et convertie en une tbb::exception. On perd donc le type de l'exception (du moins, dans la version actuelle - Intel corrigera ça dans les versions futures). En pratique, ce n'est pas trop grave. L'important est de savoir que ça a merdouillé pour récupérer la sauce.

Une fois que la boucle d'assemblage de StrVector est parallélisée, il faut être certain que les éléments peuvent calculer leurs forces indépendamment les uns des autres. Bien sûr, ca n'a pas marché du premier coup:

• Il existe des variables statiques qui sont utilisées pour accélérer le code en évitant des allocations de mémoire à tout bout de champ. J'ai dû les supprimer… le code série devient donc inévitablement plus lent (8% sur la batterie).
• Les matériaux utilisent des variables temporaires pour permettre le précalcul de certaines grandeurs tout en évitant de retrouver ces grandeurs dans tous les appels de fonction. La solution n'est pas simple à trouver. Il y a plusieurs manières de résoudre le problème. En voici 2 parmi d'autres:
  • Soit on laisse une liberté totale au programmeur de matériau (qui, pour la plupart, ne liront jamais ces lignes). Il faut alors dupliquer efficacement le matériau pour chaque thread. C'est faisable mais c'est un gros travail qui risque de provoquer un ralentissement du code. De plus, ça nécessite de coder des constructeurs par copie pour tous les matériaux; ce qui peut être relativement complexe dans les cas où des classes auxiliaires sont utilisées (PlasticCriterion, YieldStress, etc).
  • Soit on garde un seul “objet matériau” et il est interdit d'allouer des variables temporaires comme variable membre dans le matériau. Celui qui ne respecte pas cette règle ne peut pas faire de parallèle avec son matériau (tant pis pour lui). Cette solution plus radicale me semble être la plus simple à mettre en oeuvre, du moins dans un premier temps. J'ai donc modifié le matériau le plus utilisé (EvpIsoHHypoMaterial a.k.a. “stupid material” et ses dizaines de clones - no comment) pour qu'il fonctionne en parallèle (dans le cas sans thermique - pour la thermique, on verra plus tard).

Modification au niveau des éléments:

• Modification de ElementIterator. L'itérateur se comporte maintenant comme un itérateur de std::vector<Element*> et non plus std::vector<Element>
• Suppression des variables statiques de l'élément: principalement le vecteur Co (positions nodales), To (températures nodales) et assimilés. La matrice des masses “par défaut” (inutilisée) a été supprimée.
• Suppression du caractère statique de normalAndTangents de TractionElement.

Modifications au niveau des matériaux:

• Suppression des variables membres du matériau utilisées comme variables temporaires de EvpIsoHHypoMaterial, PlasticCriterion (SijE, deuxG, normSijE, res, sig, K, etc.). Toutes ces variables empêchent le calcul de 2 éléments simultanément.

Pour le calcul de la raideur, il n'y a pas de problème particulier mis à part dans le cas de la matrice de raideur tangente numérique qui ne peut pas être parallélisée actuellement puisque chaque perturbation est directement effectuée dans la base de données, commune à tous les éléments.

C'est l'objet MatrixStrBase qui se charge du calcul de la matrice. La boucle a été modifiée selon la syntaxe imposée par Intel TBB, avec un spin_mutex pour l'assemblage. Le parallel_do est actuellement désactivé et remplacé par une boucle série qui utilise néanmoins le nouveau contenu de boucle.

• EulerianReZoner est parallélisé avec TBB au lieu d'OpenMP (à titre d'exercice car le gain de perfs est nul, voire négatif).
• L'algo de convection ALE est toujours parallélisé en OpenMP (je préfère modifier ça après le passage de Philippe)

• Dans la version commitée, seul Gen4 est utilisable en parallèle (je ne le conseille cependant pas puisque le nombre de mailles générées est alors incertain!).
• La boucle d'assemblage (force et raideur) sont mises sous la forme requise par Intel TBB mais sont toujours séquentielles (même en -j 2).
• Tous les tests non thermomec avec raideur analytique et utilisant la loi classique de type “stupid material” son utilisables en parallèle en décommentarisant qq lignes dans VectorStr et MatrixStrBase (ce sera fait dans mon prochain commit).
• On observe une perte de perfs qui devra être analysée par la suite (+8% CPU sur la batterie).
• Commencez à réfléchir à vos matériaux si vous comptez utiliser Metafor en parallèle. Ils ne peuvent plus utiliser des variables temporaires stockées directement en tant que variables membres (ou alors protégées par mutex).
• La détection du contact n'a pas été modifiée et elle est donc toujours séquentielle pour un certain temps.
• Dans certains cas, j'observe (sous Windows et avec le compilateur Visual Studio) un thread “fou” en fin de calcul (metafor.exe bouffe tout le CPU). Ca correspond à un spin_mutex qui spinne dans le vide (un “busy wait”). Si vous observez ce phénomène vous aussi, prévenez moi. Je ne sais pas encore si c'est dû au code où à mes libs. Ce n'est de toutes façons pas reproductible.
• Le “Parallel Studio” (v1.0) est un outil magique pour débuguer le code parallèle. Je le pressentais et je l'ai maintenant vérifié. Il permet de mettre le doigts sur tous les problèmes de threads (principalement les “race conditions” dans ce cas-ci).

• Correction de bugs dans toolbox.utilities (saveFac & convertFac ne fonctionnaient plus).
• Augmentation de la pénalité de contactHertzGen4.py (la valeur utilisée était trop sensible au maillage qui n'était plus le même avec les modifs de Gen4)
• Modif des makefiles de clifton pour supprimer la visu qui n'est plus à jour. Autrement dit, plus personne n'a compilé sur clifton depuis que j'ai mis à jour Qt (ca fait un bail).
• Modif de BPointReZoner pour les tests de la thèse de Roxane: ajout d'une fonction setLineConf qui permet de déplacer les frontières eulériennes au cours du calcul.
• Amélioration du test arcelor.tests.belval.refroid (test de C. Bouffioux)

— Romain BOMAN 2011/04/05 11:35