next up previous contents
Next: Paralleles MATLAB Up: Zentrale Systeme Previous: SPP-UX

Kopieren von Speicherbereichen oder ``Cache as Cache Can''

Bei einer Untersuchung mit dem Ziel, die Geschwindigkeit von Message-Passing- und Shared-Memory-Programmiermodell auf dem SPP-System zu vergleichen, trat die Frage auf, wie schnell eigentlich ein Integer-Array in ein anderes kopiert werden kann. Die Beantwortung dieser scheinbar einfachen Frage führte zu einigen interessanten Phänomenen, die im folgenden vorgestellt werden sollen.

Als Rahmen diente ein kleines Testprogramm, das Buffer wachsender Größe mit verschiedenen Methoden kopierte und die Zeit dazu möglichst genau maß. Da jeder Versuch oft wiederholt wurde, spielte sich das Kopieren - bei nicht zu großem Buffer - im Cache ab. Zum Vergleich wurden jedes Mal die Caches geflushed (mit der SPP-spezifischen Routine cache_flush_region). Typische Ergebnisse sahen etwa so aus:

tex2html_wrap1034

Für alle untersuchten Methoden sind die Ergebnisse ähnlich: Bei kleinen Buffern beträgt die Zeit immer etwa 12 Mikrosekunden, die Rate steigt dann bis zu einer Buffergröße von 128 - 256 kB auf einen Maximalwert an und sinkt danach schnell auf den Wert von 20 - 25 MB/s, der der Durchsatzrate ohne Cache-Beteiligung entspricht. Soweit ist das alles nicht sehr erstaunlich und entsprach auch meinen Erwartungen. Zunächst überraschend aber waren die großen Unterschiede der maximalen Durchsatzrate bei verschiedenen Verfahren:

Die einfache Schleife

    for (i=0; i<noInts; i++)
    {
       dest[i] = source[i];
    }

erreichte 80 MB/s, die C-Standardroutine

memcpy(dest, source, noInts*sizeof(int));
dagegen fast 260 MB/s!

Zum Vergleich untersuchte ich verschiedene Möglichkeiten in Fortran. Die folgende Tabelle faßt alle Ergebnisse zusammen:

Schleife C 80 MB/s
Schleife Fortran 104 MB/s
A(1:MAX) = B(1:MAX) Fortran 104 MB/s
A = B Fortran 254 MB/s
icopy (BLAS-Routine) Fortran 254 MB/s
memcpy (Standard-Bibliothek) C 258 MB/s

Wo kommen diese eklatanten Unterschiede her? In Ermangelung des Source-Codes der Bibliotheksroutinen mußte der Assembler-Code herhalten. Außer bei ganz alten Hasen (zu denen ich mich nicht zähle :-) ruft das Wort ``Assembler'' wahlweise Ekel oder Angstschweiß hervor. Es war aber alles gar nicht so schlimm: Mit dem Debugger war die kleine Loop von etwa 20 Zeilen Assembler, die die eigentliche Arbeit macht, schnell gefunden. Und auch ohne jede Zeile im einzelnen verstehen zu wollen, war das Muster leicht gedeutet:

1. memcpy kopiert Double-Zahlen, nicht Integers.

Darauf hätte ich natürlich auch gleich kommen können. Ich schrieb die kleine Schleife in C so um, daß sie die Integer-Arrays über Double-Pointer anfaßt (brrr!) und ab geht's:

Schleife (ints als doubles) C 160 MB/s

Doppelt so schnell wie vorher - wer hät's gedacht.

2. memcpy verteilt Loads und Stores anders:

memcpy eigene Schleife
LOAD LOAD
LOAD STORE
LOAD LOAD
LOAD STORE
STORE LOAD
STORE STORE
STORE LOAD
STORE STORE

Durch das Anstoßen von vier Loads direkt nacheinander wird anscheinend die CPU besser ausgenutzt, Wartezeiten werden minimiert. [1] Soviel Intelligenz hätte ich aber - mit Verlaub - dem Compiler bei einer einfachen Kopier-Schleife auch zugetraut! Dies zeigt wieder einmal, daß der Convex-Compiler, bei allen Vorteilen im Optimierungsbereich auf Source-Ebene, im Code-Generator noch sehr zu wünschen übrig läßt! Zum Vergleich hier die Werte für den HP-C-Compiler bei +O3 (auf der SPP):

Schleife C 97 MB/s
Schleife (double *) C 252 MB/s
memcpy (Standard-Bibliothek) C 111 MB/s

Im Instruktions-Scheduling ist der HP-Compiler eindeutig überlegen, er erzeugt aus der handoptimierten Schleife tatsächlich idealen Code. Aber was macht bloß das memcpy von HP? Wieder ein schon von anderen Untersuchungen her bekanntes Resultat: Die Bibliotheksroutinen von HP können denen von Convex nicht das Wasser reichen. Dies war mir schon im Zusammenhang mit der Veclib für HP-UX aufgefallen. Zum Glück werden die Teams von HP und Convex ja gerade zusammengewürfelt. Hoffen wir, daß sich jeweils die besseren Teile zusammenfinden.

Was lernen wir nun daraus? Zunächst einmal sollte man immer eine Bibliotheksroutine verwenden, wenn eine da ist - selbst bei scheinbar so einfachen Operationen wie einem Kopieren oder etwa einer Matrix-Multiplikation. Wenn man insbesondere die BLAS-Routinen der Veclib verwendet, erreicht man hohe Performance bei weitgehender Portabilität. Außerdem ist es sinnvoll - und der Lesbarkeit des Programmes zuträglich -, in Fortran mit den Array-Operationen von Fortran 90 zu arbeiten.

[1] Ganz verstanden habe ich das nicht - aber die Convex-Leute, die ich gefragt habe, auch nicht :-)


next up previous contents
Next: Paralleles MATLAB Up: Zentrale Systeme Previous: SPP-UX

Marco Budde
Mon Jul 8 18:15:29 MESZ 1996