Werden BLAS-Implementierungen garantiert, um genau das gleiche Ergebnis zu erzielen?

17

Können wir bei zwei verschiedenen BLAS-Implementierungen erwarten, dass sie exakt dieselben Gleitkommaberechnungen durchführen und dieselben Ergebnisse zurückgeben? Oder kann es beispielsweise vorkommen, dass man ein Skalarprodukt als und eines als ( x 1 y 1 + x 2 y berechnet 2 ) + ( x 3 y 3 + x 4

((x1y1+x2y2)+x3y3)+x4y4
also möglicherweise abweichendes Ergebnis bei IEEE-Gleitkomma-Arithmetik?
(x1y1+x2y2)+(x3y3+x4y4),
Federico Poloni
quelle
1
Es gibt einige Beschwerden über die BLAS-Qualität in diesem Thread . Suchen Sie auf der Seite nach CBLAS. Das würde bedeuten, dass sie nicht nur nicht das gleiche Ergebnis liefern, sondern auch nicht alle genau genug für eine Aufgabe sind ...
Szabolcs

Antworten:

15

Nein, das ist nicht garantiert. Wenn Sie einen NETLIB BLAS ohne Optimierungen verwenden, stimmen die Ergebnisse größtenteils überein. Für jede praktische Anwendung von BLAS und LAPACK wird jedoch ein hochoptimiertes paralleles BLAS verwendet. Die Parallelisierung bewirkt, auch wenn sie nur in den Vektorregistern einer CPU parallel arbeitet, dass sich die Reihenfolge, in der die einzelnen Terme ausgewertet werden, und die Reihenfolge der Summierung ändert. Nun folgt aus der fehlenden assoziativen Eigenschaft im IEEE-Standard, dass die Ergebnisse nicht gleich sind. Genau das, was Sie erwähnt haben, kann passieren.

In der NETLIB BLAS ist das Skalarprodukt nur eine um den Faktor 5 abgewickelte for-Schleife:

DO I = MP1,N,5
          DTEMP = DTEMP + DX(I)*DY(I) + DX(I+1)*DY(I+1) +
     $            DX(I+2)*DY(I+2) + DX(I+3)*DY(I+3) + DX(I+4)*DY(I+4)
END DO

und es liegt an dem Compiler, ob jede Multiplikation sofort zu DTEMP hinzugefügt wird oder ob alle 5 Komponenten zuerst aufsummiert werden und dann zu DTEMP hinzugefügt werden. In OpenBLAS handelt es sich je nach Architektur um einen komplizierteren Kernel:

 __asm__  __volatile__
    (
    "vxorpd     %%ymm4, %%ymm4, %%ymm4               \n\t"
    "vxorpd     %%ymm5, %%ymm5, %%ymm5               \n\t"
    "vxorpd     %%ymm6, %%ymm6, %%ymm6               \n\t"
    "vxorpd     %%ymm7, %%ymm7, %%ymm7               \n\t"

    ".align 16                           \n\t"
    "1:                          \n\t"
        "vmovups                  (%2,%0,8), %%ymm12         \n\t"  // 2 * x
        "vmovups                32(%2,%0,8), %%ymm13         \n\t"  // 2 * x
        "vmovups                64(%2,%0,8), %%ymm14         \n\t"  // 2 * x
        "vmovups                96(%2,%0,8), %%ymm15         \n\t"  // 2 * x

    "vmulpd      (%3,%0,8), %%ymm12, %%ymm12 \n\t"  // 2 * y
    "vmulpd    32(%3,%0,8), %%ymm13, %%ymm13 \n\t"  // 2 * y
    "vmulpd    64(%3,%0,8), %%ymm14, %%ymm14 \n\t"  // 2 * y
    "vmulpd    96(%3,%0,8), %%ymm15, %%ymm15 \n\t"  // 2 * y

    "vaddpd      %%ymm4 , %%ymm12, %%ymm4 \n\t"  // 2 * y
    "vaddpd      %%ymm5 , %%ymm13, %%ymm5 \n\t"  // 2 * y
    "vaddpd      %%ymm6 , %%ymm14, %%ymm6 \n\t"  // 2 * y
    "vaddpd      %%ymm7 , %%ymm15, %%ymm7 \n\t"  // 2 * y

    "addq       $16 , %0	  	     \n\t"
	"subq	        $16 , %1            \n\t"      
    "jnz        1b                   \n\t"
...

Dadurch wird das Skalarprodukt in kleine Skalarprodukte der Länge 4 aufgeteilt und summiert.

Bei Verwendung der anderen typischen BLAS-Implementierungen wie ATLAS, MKL, ESSL, ... bleibt dieses Problem gleich, da jede BLAS-Implementierung unterschiedliche Optimierungen verwendet, um schnellen Code zu erhalten. Aber meines Wissens braucht man ein künstliches Beispiel, um wirklich fehlerhafte Ergebnisse zu erzielen.

Wenn es notwendig ist, dass die BLAS-Bibliothek für die gleichen Ergebnisse zurückgibt (bitweise gleich), muss eine reproduzierbare BLAS-Bibliothek verwendet werden, wie zum Beispiel:

MK aka Grisu
quelle
8

Die kurze Antwort

Wenn die beiden BLAS-Implementierungen so geschrieben sind, dass die Operationen in genau derselben Reihenfolge ausgeführt werden, und die Bibliotheken mit denselben Compiler-Flags und demselben Compiler kompiliert wurden, erhalten Sie dasselbe Ergebnis. Fließkomma-Arithmetik ist nicht zufällig, sodass zwei identische Implementierungen zu identischen Ergebnissen führen.

Es gibt jedoch eine Vielzahl von Dingen, die dieses Verhalten aus Gründen der Leistung stören können ...

Die längere Antwort

IEEE gibt außerdem die Reihenfolge an, in der diese Vorgänge ausgeführt werden, und legt fest , wie sich die einzelnen Vorgänge verhalten sollen. Wenn Sie jedoch Ihre BLAS-Implementierung mit Optionen wie "-ffast-math" kompilieren, kann der Compiler Transformationen ausführen, die in exakter Arithmetik wahr, in IEEE-Gleitkommazahlen jedoch nicht "korrekt" sind. Das kanonische Beispiel ist die Nichtassoziativität der Gleitkommazugabe, wie Sie betont haben. Bei aggressiveren Optimierungseinstellungen wird Assoziativität vorausgesetzt, und der Prozessor erledigt so viel wie möglich parallel, indem er die Operationen neu anordnet.

ein+bc

Tyler Olsen
quelle
3
Msgstr "Fließkomma - Arithmetik ist nicht zufällig" . Es ist traurig, dass dies ausdrücklich angegeben werden muss, aber es scheint, dass zu viele Leute denken, dass es ...
Pipe
Nun, unvorhersehbar und zufällig sehen sie ziemlich ähnlich aus, und viele Intro-Programmierklassen sagen "Vergleiche niemals Gleitkommazahlen auf Gleichheit", was den Eindruck erweckt, dass der genaue Wert nicht auf die gleiche Weise wie Ganzzahlen herangezogen werden kann.
Tyler Olsen
@TylerOlsen Dies ist für die Frage nicht relevant, und aus diesem Grund sagen diese Klassen solche Dinge nicht, aber im IIRC gab es früher eine Klasse von Compiler-Fehlern, auf die sich Gleichheit nicht verlassen konnte. Zum Beispiel kann if (x == 0) assert(x == 0) es manchmal scheitern, was aus einer bestimmten Sicht so gut wie zufällig ist.
Kirill
@Kirill Sorry, ich habe nur versucht, darauf hinzuweisen, dass viele Leute nie wirklich lernen, wie Gleitkommazahlen funktionieren. Was den historischen Punkt betrifft, ist das erschreckend, aber es muss gelöst worden sein, bevor ich ins Spiel kam.
Tyler Olsen
@TylerOlsen Hoppla, mein Beispiel ist falsch. Es sollte if (x != 0) assert(x != 0)wegen der erweiterten Genauigkeit der Arithmetik sein.
Kirill
4

Im Allgemeinen nicht. Abgesehen von der Assoziativität kann die Auswahl von Compiler-Flags (z. B. Aktivierung von SIMD-Befehlen, Verwendung von Fused Multiply Add usw.) oder der Hardware (z. B. Verwendung von Extended Precision ) zu unterschiedlichen Ergebnissen führen.

Es gibt einige Anstrengungen, um reproduzierbare BLAS-Implementierungen zu erhalten. Weitere Informationen finden Sie unter ReproBLAS und ExBLAS .

Juan M. Bello-Rivas
quelle
1
Siehe auch die CNR-Funktion (Conditional Numerical Reproducibility) in neueren Versionen von Intels MKL BLAS. Beachten Sie, dass diese Reproduzierbarkeitsstufe in der Regel Ihre Berechnungen verlangsamt und sie möglicherweise erheblich verlangsamt!
Brian Borchers