Lukas Hübner, Alexandros Stamatakis, Peter Sanders

Christoph Stelz

Die Addition von Gleitkommazahlen kann aufgrund von Rundungsfehlern bei unterschiedlicher Prozessorenanzahl zu unterschiedlichen Ergebnissen führen. Für manche Algorithmen wie RAxML-NG oder Greedy-Algorithmen kann dies den Verlust der Reproduzierbarkeit bei unterschiedlicher Prozessorenanzahl bedeuten. Wir stellen einen Reduktionsalgorithmus vor, der nach dem Schema eines verteilten Binärbaums vorgeht, wodurch die Ausführungsreihenfolge unabhängig von der Prozessorenanzahl p bleibt. Eine naive Implementierung muss bis zu (p − 1) ∗ (log2((N-1)/p) + 1) Nachrichten senden, um N Gleitkommazahlen zu addieren. Um die Nachrichtenanzahl zu senken führen wir einen Nachrichtenpuffer ein und optimieren die Datenverteilung über die Prozessoren, wobei letzteres zur einer Verringerung der Laufzeit um 18 % führt. Wir stellen fest, dass für p = 256 Prozessoren die Laufzeit des Binärbaum-Reduktionsalgorithmus weniger als 200 % der eines naiven, unreproduzierbaren Algorithmus entspricht. Die Binärbaum-Reduktion ist imstande N ≈ 21 ∗ 10^6 Summanden auf p = 256 Prozessoren in 248 µs aufzusummieren.