Eine parallele Reduktion setzt voraus, dass die entsprechende Operation assoziativ ist. Diese Annahme wird beim Hinzufügen von Gleitkommazahlen verletzt. Sie könnten fragen, warum mir das wichtig ist. Nun, es macht die Ergebnisse weniger reproduzierbar. Und es wird schlimmer, wenn simuliertes Tempern verwendet wird, um Subroutinen zu optimieren (oder Parameter anzupassen), was zu solchen nicht reproduzierbaren Ergebnissen führt.
Was sind die gebräuchlichen Methoden, um mit diesem Problem umzugehen? Was kann über die folgenden Strategien gesagt werden?
- Kümmere dich nicht um die Nichtreproduzierbarkeit.
- Verwenden Sie keine parallele Reduktion mit Gleitkommazahlen und Addition.
- Erstellen Sie auf reproduzierbare Weise Arbeitspakete mit geeigneter Größe und führen Sie die endgültige Reduzierung von Hand durch.
- Verwenden Sie für die Addition eine höhere Genauigkeit (jedoch bieten nicht alle Compiler Gleitkommatypen mit höherer Genauigkeit an).
parallel-computing
reproducibility
Thomas Klimpel
quelle
quelle
Antworten:
Eine mit implementierte Reduzierung
MPI_Allreduce()
ist reproduzierbar, solange Sie dieselbe Anzahl von Prozessoren verwenden, sofern die Implementierung den folgenden Hinweis in Abschnitt 5.9.1 des MPI-2.2-Standards beachtet.Wenn Sie die Reproduzierbarkeit unbedingt gewährleisten müssen, können Sie die Richtlinien im nächsten Absatz befolgen:
Im weiteren Sinne nutzen effiziente Algorithmen für die meisten Anwendungen die Lokalität. Da der Algorithmus bei einer anderen Anzahl von Prozessen sehr unterschiedlich ist, ist es einfach nicht praktikabel, die Ergebnisse bei einer anderen Anzahl von Prozessen exakt zu reproduzieren. Eine mögliche Ausnahme ist Multigrid mit gedämpften Jacobi- oder Polynomglättern (z. B. Chebyshev), bei denen diese einfache Methode sehr gut funktioniert.
Bei der gleichen Anzahl von Prozessen ist es für die Leistung häufig vorteilhaft, Nachrichten in der Reihenfolge zu verarbeiten, in der sie empfangen werden (z. B. unter Verwendung von
MPI_Waitany()
), was einen Nichtdeterminismus einführt. In solchen Fällen können Sie zwei Varianten implementieren, die schnelle, die in einer beliebigen Reihenfolge empfangen wird, und eine "Fehlerbehebung", die in einer statischen Reihenfolge empfangen wird. Dies setzt voraus, dass alle zugrunde liegenden Bibliotheken ebenfalls so geschrieben sind, dass sie dieses Verhalten bieten.In einigen Fällen können Sie zum Debuggen einen Teil einer Berechnung, die dieses reproduzierbare Verhalten nicht bietet, isolieren und redundant ausführen. Je nachdem, wie die Komponenten entworfen wurden, kann diese Änderung eine geringe Menge an Code oder sehr aufdringlich sein.
quelle
Zum größten Teil habe ich auch Jeds Antwort. Es gibt jedoch einen anderen Ausweg: Angesichts der Größe normaler Gleitkommazahlen können Sie jede Zahl in einer Festkommazahl mit etwa 4000 Bit speichern. Wenn Sie also die so eingebetteten Gleitkommazahlen reduzieren, erhalten Sie eine genaue Berechnung, unabhängig von der Assoziativität. (Entschuldigung, ich habe keinen Hinweis darauf, wer auf diese Idee gekommen ist.)
quelle
Sie können einen numerisch stabilen Reduktionsalgorithmus in MPI implementieren, genauso wie Sie es in serieller Form tun können. Natürlich kann es zu einem Leistungseinbruch kommen. Wenn Sie es sich leisten können, den Vektor zu replizieren, verwenden Sie einfach MPI_Gather und führen Sie die numerisch stabile Reduzierung der Seriennummer im Stammverzeichnis durch. In einigen Fällen ist der Leistungsverlust möglicherweise keine große Sache.
Eine andere Lösung besteht darin, breite Akkumulatoren wie hier beschrieben zu verwenden . Sie können dies mit MPI als benutzerdefinierte Reduzierung tun, obwohl dies viel mehr Bandbreite beansprucht.
Ein Kompromiss für das oben Gesagte ist die Verwendung einer kompensierten Summierung. Siehe Referenzen “Kahan Summation” für Details. Highams " Genauigkeit und Stabilität numerischer Algorithmen " ist eine hervorragende Ressource zu diesem Thema.
quelle
Um das Problem im Zusammenhang mit Threads auf einem gemeinsam genutzten Speichersystem zu beheben, habe ich diese Seite geschrieben, auf der unsere Vorgehensweise erläutert wird.II: http://dealii.org/developer/doxygen/deal.II/group__threads.html #MTWorkStream
quelle
Ich möchte darauf hinweisen, dass anstelle einer präziseren Addition eine kompensierte Summation möglich ist (siehe [1]). Dies könnte die Genauigkeit der Summierung erhöhen, ohne auf größere Datentypen zurückgreifen zu müssen.
[1] Higham, NJ Die Genauigkeit der Gleitkommasummierung. SIAM Journal on Scientific Computing 14, 783–799 (1993).
quelle