Comment aborder la non-associativité numérique pour la réduction parallèle?

Une réduction parallèle suppose que l'opération correspondante est associative. Cette hypothèse est violée pour l'ajout de nombres à virgule flottante. Vous pourriez vous demander pourquoi je m'en soucie. Eh bien, cela rend les résultats moins reproductibles. Et cela empire lorsque le recuit simulé est utilisé pour optimiser (ou ajuster les paramètres) sur des sous-programmes produisant de tels résultats non reproductibles.

Quels sont les moyens courants de résoudre ce problème? Que dire des stratégies suivantes?

• Ne vous souciez pas de la non-reproductibilité.
• N'utilisez pas la réduction parallèle avec des nombres à virgule flottante et l'addition.
• Créez des lots de travaux de taille appropriée de manière reproductible et effectuez la réduction finale à la main.
• Utilisez une précision plus élevée pour l'ajout (mais tous les compilateurs n'offrent pas des types à virgule flottante de précision supérieure).

Une réduction implémentée à l'aide MPI_Allreduce()est reproductible tant que vous utilisez le même nombre de processeurs, à condition que l'implémentation respecte la note suivante figurant à la section 5.9.1 de la norme MPI-2.2.

Conseils aux exécutants . Il est fortement recommandé de MPI_REDUCEl'implémenter afin que le même résultat soit obtenu chaque fois que la fonction est appliquée sur les mêmes arguments, apparaissant dans le même ordre. Notez que cela peut empêcher les optimisations qui tirent parti de l'emplacement physique des processeurs. ( Fin des conseils aux exécutants .)

Si vous devez garantir la reproductibilité à tout prix, vous pouvez suivre les instructions du paragraphe suivant:

Conseils aux utilisateurs . Certaines applications peuvent ne pas être en mesure d'ignorer la nature non associative des opérations en virgule flottante ou peuvent utiliser des opérations définies par l'utilisateur (voir la section 5.9.5) qui nécessitent un ordre de réduction spécial et ne peuvent pas être traitées comme associatives. Ces demandes devraient faire respecter l'ordre d'évaluation de manière explicite. Par exemple, dans le cas d'opérations qui nécessitent un ordre d'évaluation strict de gauche à droite (ou de droite à gauche), cela pourrait être fait en rassemblant tous les opérandes en un seul processus (par exemple, avec MPI_GATHER), en appliquant l'opération de réduction dans l'ordre souhaité (par exemple, avec MPI_REDUCE_LOCAL) et, si nécessaire, diffusez ou diffusez le résultat aux autres processus (par exemple, avec MPI_BCAST). ( Fin des conseils aux utilisateurs .)

Dans le schéma plus large des choses, des algorithmes efficaces pour la plupart des applications tirent parti de la localité. Étant donné que l'algorithme est vraiment différent lorsqu'il est exécuté sur un nombre différent de processus, il n'est tout simplement pas pratique de reproduire exactement les résultats lorsqu'il est exécuté sur un nombre différent de processus. Une exception possible est multigrille avec Jacobi amorti ou lisseurs polynomiaux (par exemple Chebyshev), où il est possible que cette méthode simple fonctionne très bien.

Avec le même nombre de processus, il est souvent avantageux pour la performance de traiter les messages dans l'ordre de leur réception (par exemple en utilisant MPI_Waitany()), ce qui introduit le non-déterminisme. Dans de tels cas, vous pouvez implémenter deux variantes, la plus rapide qui reçoit dans n'importe quel ordre et une "débogage" qui reçoit dans un ordre statique. Cela nécessite que toutes les bibliothèques sous-jacentes soient également écrites pour offrir ce comportement.

Pour le débogage dans certains cas, vous pouvez isoler une partie d'un calcul qui n'offre pas ce comportement reproductible et l'exécuter de manière redondante. Selon la façon dont les composants ont été conçus, ce changement peut être une petite quantité de code ou très intrusif.

Pour la plupart, je répète la réponse de Jed. Cependant, il existe une solution différente: étant donné la taille des nombres à virgule flottante normaux, vous pouvez stocker chaque nombre dans un nombre à virgule fixe de 4 000 bits environ. Donc, si vous faites une réduction sur les nombres à virgule flottante ainsi intégrés, vous obtenez un calcul exact, quelle que soit l'associativité. (Désolé, je n'ai pas la référence à qui a eu cette idée.)

Vous pouvez implémenter un algorithme de réduction numériquement stable en MPI de la même manière que vous pouvez le faire en série. Il peut bien sûr y avoir un impact sur les performances. Si vous pouvez vous permettre de répliquer le vecteur, utilisez simplement MPI_Gather et effectuez la réduction numérique stable en série à la racine. Dans certains cas, vous constaterez peut-être que l'atteinte des performances n'est pas un gros problème.

Une autre solution consiste à utiliser des accumulateurs larges comme décrit ici . Vous pouvez le faire avec MPI en tant que réduction définie par l'utilisateur, bien qu'il utilisera beaucoup plus de bande passante.

Un compromis pour ce qui précède consiste à utiliser la somme compensée. Voir les références «sommation Kahan» pour plus de détails. «La précision et la stabilité des algorithmes numériques » de Higham est une excellente ressource sur ce sujet.

Pour résoudre le problème dans le contexte des threads sur un système de mémoire partagée, j'ai écrit cette page qui explique ce que nous faisons dans l'affaire. II: http://dealii.org/developer/doxygen/deal.II/group__threads.html #MTWorkStream

Je voudrais souligner qu'au lieu d'utiliser une arithmétique de plus grande précision pour l'addition, il y a la possibilité d'utiliser une sommation compensée (voir [1]). Cela pourrait augmenter la précision de la sommation sans avoir à recourir à des types de données plus importants.

[1] Higham, NJ La précision de la sommation à virgule flottante. SIAM Journal on Scientific Computing 14, 783–799 (1993).