Bibliothèques parallèles à mémoire partagée basées sur les tâches dans le calcul scientifique

10

Au cours des dernières années, plusieurs bibliothèques / projets logiciels sont apparus qui offrent une forme ou une autre de parallélisme à mémoire partagée basé sur des données à usage général.

L'idée principale est qu'au lieu d'écrire un code explicitement threadé, les programmeurs implémentent leurs algorithmes en tant que tâches interdépendantes qui sont ensuite planifiées dynamiquement par un middleware à usage général sur une machine à mémoire partagée.

Des exemples de telles bibliothèques sont:

  • QUARK : Conçu à l'origine pour la bibliothèque d'algèbre linéaire parallèle MAGMA , semble également avoir été utilisé pour une méthode multipolaire rapide parallèle .

  • Cilk : à l'origine un projet basé sur le MIT, désormais pris en charge par Intel, implémenté en tant qu'extensions de langage / compilateur pour C, utilisé dans le logiciel d'échecs informatique Cilkchess et expérimentalement dans FFTW .

  • SMP superscalar : développé au Barcelona Supercomputing Center, similaire à Cilk à bien des égards, basé sur des #pragmaextensions.

  • StarPU : bibliothèque similaire de "codelets" qui peut être compilée et planifiée sur plusieurs architectures différentes, y compris les GPU.

  • Tâches OpenMP: à partir de la version 3.0, OpenMP a introduit des "tâches" qui peuvent être planifiées de manière asynchrone (voir la section 2.7 de la spécification).

  • Intel's Threading Building Blocks : utilise des classes C ++ pour créer et lancer des tâches asynchrones, voir la section 11 du didacticiel.

  • OpenCL : prend en charge le parallélisme basé sur les tâches sur plusieurs cœurs.

Bien qu'il y ait beaucoup de littérature décrivant le fonctionnement interne de ces bibliothèques / extensions de langage et leur application à des problèmes spécifiques, je n'ai rencontré que très peu d'exemples de leur utilisation dans la pratique dans les applications de calcul scientifique.

Alors, voici la question: quelqu'un connaît-il des codes de calcul scientifique utilisant l'une de ces bibliothèques / extensions de langage, ou similaire, pour le parallélisme à mémoire partagée?

Pedro
la source
Êtes-vous à la recherche d'un parallélisme basé sur les tâches? Y a-t-il une raison pour laquelle vous avez ignoré OpenCL et Intel TBB? Je dois admettre que je ne peux pas dire exactement ce que vous cherchez ici.
Aron Ahmadia du
1
@AronAhmadia: Ignorance, principalement ... :) J'ai ajouté TBB et OpenCL à la liste, mais la question est toujours la même: ces composants, c'est-à-dire leurs composants basés sur les tâches, ont-ils été utilisés dans n'importe quel logiciel important pour la science l'informatique?
Pedro
Que pensons-nous de transformer cette question et ses réponses en un wiki communautaire par rapport à essayer de l'étendre davantage?
Aron Ahmadia
@AronAhmadia: Je suis un peu inquiet que si je laisse le format de question, cela dégénérera rapidement en longues discussions sur les avantages / inconvénients de la programmation basée sur les tâches et / ou à mémoire partagée en général. Je serais cependant en faveur de le changer après avoir obtenu quelques réponses supplémentaires.
Pedro
Le titre n'est pas approprié. Cette question concerne le parallélisme des tâches, pas la mémoire partagée.
Jeff

Réponses:

8

deal.II utilise les blocs de construction filetés dans toute la bibliothèque et, dans l'ensemble, nous en sommes raisonnablement satisfaits. Nous avons examiné quelques alternatives, en particulier OpenMP, car tout le monde semble utiliser cela pour des codes plus simples, mais les a trouvées manquantes. En particulier, OpenMP présente l'énorme inconvénient que son modèle de tâche ne vous permet pas d'obtenir un descripteur pour une tâche que vous avez démarrée, et par conséquent, il est difficile d'accéder à l'état d'une tâche (par exemple, pour attendre qu'elle se termine) ou de renvoyer des valeurs de fonctions que vous exécutez sur une tâche distincte. OpenMP est principalement bon pour paralléliser les boucles les plus internes , mais vous gagnez en efficacité parallèle en parallélisant les boucles les plus externes et complexes, et OpenMP n'est pas l'outil pour cela alors que le TBB est raisonnablement bon pour cela.

Wolfgang Bangerth
la source
Merci de l'avoir signalé, je n'avais pas regardé deal.II! Existe-t-il une publication ou un document dans lequel l'utilisation du TBB par deal.II est décrite en détail?
Pedro
Pas de publication, mais cela peut aider: dealii.org/developer/doxygen/deal.II/group__threads.html
Wolfgang Bangerth
4

À mon avis, ces systèmes ont relativement peu réussi en raison principalement des raisons suivantes.

  • La perspective naïve selon laquelle le calcul parallèle consiste davantage à paralléliser le calcul (par exemple les flops) qu'à exposer la localité de la mémoire et supprimer les points de synchronisation. Même si certains problèmes, tels que les algorithmes à matrice dense, sont encore limités en FP, cela ne se produit qu'après une attention particulière au sous-système de mémoire et la plupart des noyaux de calcul (en particulier dans le monde PDE) sont plus sensibles à la mémoire. Les files d'attente de travail ont tendance à échanger la localité de la mémoire pour un meilleur équilibre naïf des flops et davantage d'opérations de mémoire atomique (en raison de la synchronisation via la file d'attente).
  • Recours à une décomposition excessive pour un équilibre de charge dynamique au détriment d'une forte évolutivité. Les tâches ont généralement des dépendances de données qui se chevauchent (valeurs fantômes). À mesure que la taille de l'intérieur diminue, le rapport fantôme / intérieur augmente. Même lorsque cela n'implique pas un travail redondant, cela implique un mouvement de mémoire accru. Des réductions significatives des besoins en bande passante mémoire peuvent être obtenues par des approches telles que la lecture anticipée coopérative par laquelle plusieurs threads partagent un cache L1 ou L2 par la lecture anticipée logicielle pour leur voisin (ce qui maintient implicitement le groupe de threads approximativement cohérent). C'est exactement le contraire de la décomposition excessive.
  • Performances imprévisibles, principalement en raison des problèmes liés à la mémoire ci-dessus.
  • Manque de composants compatibles avec la bibliothèque. Cela peut presque être résumé comme n'ayant pas d'analogue d'un MPI_Commqui permet à différentes bibliothèques d'effectuer des opérations riches sans entrer en collision, ainsi que de passer le contexte entre les bibliothèques et de récupérer les attributs nécessaires. L'abstraction fournie par le "communicateur" est importante pour la composition de la bibliothèque, que la mémoire partagée ou distribuée soit utilisée.
Jed Brown
la source
Je peux mal comprendre votre réponse, mais le premier point est exactement le contraire de ce que Buttari, Kurzak, Dongarra et d'autres ont montré avec MAGMA, une bibliothèque de mémoire partagée basée sur les tâches pour l'algèbre linéaire dense ... Aussi, dans votre deuxième point vous vous référez à des données qui se chevauchent, c'est-à-dire des valeurs fantômes et le rapport surface / volume, mais ce sont des retenues de schémas de décomposition de domaine de mémoire distribuée. Je travaille moi-même avec de telles méthodes pour les codes basés sur les particules, et j'obtiens de bien meilleures performances que les implémentations parallèles basées sur MPI.
Pedro
La question, en tout cas, était différente ... Connaissez-vous des projets de logiciels de calcul scientifique utilisant ces approches?
Pedro
1. Il existe une poignée de projets utilisant ces systèmes, mais je ne pense pas que l'approche puisse être considérée comme "réussie". 2. Les dépendances se chevauchent toujours dans la mémoire partagée. Regardez comment tcmalloc ou le noyau Linux rend les threads plus indépendants pour éviter les goulots d'étranglement tels que la synchronisation via atomics. L'espace d'adressage partagé n'implique pas que vous devez fonctionner comme si vous aviez une mémoire uniforme ou que vous devriez considérer l'atomique comme peu coûteux.
Jed Brown
3. Je ne sais pas quelle "comparaison équitable" vous avez l'intention de citer, mais PLASMA n'obtient qu'environ 25% du pic FPU (par exemple, diapositive 5 de hpcgarage.org/cscads2012/Luszczek-UTK-PowerTools.pdf ) qui serait peut-être mauvais pour la même opération dans la mémoire distribuée où au moins 70% du pic serait attendu. L'algèbre linéaire dense est un cas lié au FPU que j'ai spécifiquement cité comme une exception possible, mais malgré les tailles de matrice énormes, PLASMA est évidemment loin d'être lié au FPU.
Jed Brown
Pedro, la plupart de la physique a une composante à longue portée, donc les particules sont couplées à une mise à jour qui est sujette à l'effet surface-solume ci-dessus (PPPM, particules de vortex, etc.)
Matt Knepley