Speicherklassen und Pipelining

http://udrepper.livejournal.com/19557.html

Zitat von Blubberblase

Registerobjekte werden sicher in Register der CPU geladen und lassen sich schnell verarbeiten und abrufen. Dazu zählen sicherlich Zählvariablen in Schleifen.

"Sicher" ist gar nix, es kann ja z.B. sein, daß alle Register schon belegt sind.

Zitat

Die Hauptspeicherobjekte finden sicherlich im Hauptspeicher platz. Gibt es da etwas zu beachten was die Laufzeit betrifft? Ich habe gehört, dass es günstig ist, wenn die Zieladresse des Sprungs an den Anfang durch 32 teilbar ist.

Das mag auf bestimmten Architekturen von Vorteil sein. Wenn es so ist, wird das ein gescheiter Compiler arrangieren, daß dein Code so ausgelegt ist. Ansonsten kann man mit Heapobjekten nicht sehr viel herumoptimieren außer daß man auf Lokalität achtet, d.h. z.B. bevorzugt benachbarte Array-Elemente begrapschen und nicht weit voneinander entfernte.

Zitat

Es gäbe da angeblich soetwas wie prefetching wo man gleich mehr Cache anfordern kann. Wird das vom Compiler erledigt oder kann das der Programmierer z.B. in c selbst übernehmen?

Als Programmierer kannst du das (in Standard-C) nicht beeinflussen.

Zitat

Gibt es für mich eine Möglichkeit festzustellen welche Variablen von meinem Programm welcher Speicherklasse zugeordnet werden? Werden z.B. arrays grundsätzlich als Hauptspeicherobjekte behandelt?

Sehr wahrscheinlich. Allerdings, wenn du auf Lokalität bei Zugriffen achtest, kommen die Vorteile des Caches zum Tragen, und die Zugriffe sind fast gratis.

Zitat

Kann ich in der Programmiersprache C darauf Einfluss nehmen welche Variable in den Hauptspeicher kommt oder als Zählvariable in ein Register oder macht das ausschließlich der Compiler?

Du kannst bei der Deklaration das register-Keyword verwenden:

register int i;

Das ist zwar nur ein Vorschlag an den Compiler, aber er kann einiges bringen. Ob es so ist, kannst du nur messen. Beachte, daß die x86-Architektur sehr sehr sehr sehr sehr sehr wenige general-purpose-Register besitzt.

Zitat

Code

for (int a = 0; a < N; a++)
   m1[a] += m2[a];

BTW, du weißt eh, daß das nicht (Standard-) C89 ist?

Mal abgesehen vom Unrolling, ein optimierender Compiler wird diesen Code für eine passende Konstante (z.B. 4) ungefähr so lesen:

a = 0;
while (a < N) {
    *(m1 + a*4) = *(m2 + a*4);
    a++;
}

Ein paar einfache Transformationen, zuerst common subexpression elimination:

a = 0;
temp = 0;
while (temp < N*4) {
    temp = a*4;
    a++;
    *(m1 + temp) = *(m2 + temp);
}

Strength reduction:

a = 0;
temp = 0;
while (temp < N*4) {
    temp += 4;
    a++;
    *(m1 + temp) = *(m2 + temp);
}

Elimination der unnötigen Variablen a;

temp = 0;
while (temp < N*4) {
    temp += 4;
    *(m1 + temp) = *(m2 + temp);
}

Elimination der unnötigen Variablen temp:

temp2 = m1 + N*4;
p1 = m1;
p2 = m2;
while (p1 < temp2) {
    *p1++ = *p2++;
}

Hübsch, nicht? Und du brauchst dich um die Zählvariable nicht kümmern, weil es sie nicht gibt.

Der Schlüssel zu optimalem Code: Möglichst klaren Code schreiben, bei dem kennt sich der Compiler am besten aus. Keine Pointer auf lokale Variablen setzen, Variablen möglichst lokal halten, Array-Zugriffe möglichst einfach halten (z.B. nicht in einer Schleife an verschiedenen Stellen in einem Array rumgurken), Pointer nur dort einsetzen, wo unbedingt nötig.

Zitat von Blubberblase

Code

typedef unsigned int BLOCK; // sind 32 Bit
//typedef uint8_t BLOCK;
//typedef uint16_t BLOCK;


int creatematrixBPB(BLOCK *pos) {
 int row, col;
 for (row = 0; row < N; row++) {
        for(col = 0; col < N; col++) {
            if(col&1)
                (*pos++) = (BLOCK)1;
            else (*pos++) = (BLOCK)0;
   }   
 }   
    return 0; 
}

Alles anzeigen

Diese Variante könnte signifikant schneller sein:

int creatematrixBPB2(BLOCK *pos) {
 int row, col;
 for (row = 0; row < N; row++) {
        for(col = 0; col < N; col++) {
            *pos++ = col & 1;
   }
 }
    return 0;
}

Vielleicht bringts auch sowas:

int creatematrixBPB3(BLOCK *pos) {
    int i;
    int max = N * N;
    for (i = 0; i < max; i += 2)
    {
        *pos++ = 0;
        *pos++ = 1;
    }
    return 0;
}

Das finde ich übrigens die klarste Variante, leider tut sie in dieser Form nur für gerade N das, was sie tun soll.

Zitat

Jetzt habe ich die Zeit berechnet, die für das Zeigererhöhen draufgeht:

32 Bit: 0,93 s - 0,34 = 0,59
16 Bit: 0,56 s - 0,34 = 0,22
8 Bit: 0,41 s - 0,34 = 0,07

Eine Verdopplung der Blockgröße führt zu ganz grob zu einer Halbierung der Laufzeit?

Hier ja, du berührst bei doppelter Blockgröße doppelt so viele Speicherworte, und das kostet. Die Zeit geht aber nicht fürs Erhöhen des Zeigers drauf, sondern auf den Speicherzugriff.

Zitat

Kann ich diesen Sachverhalt darüber erklären, dass bei 32 Bit der Cache eher voll ist und mehr Cache nachgeladen werden muss, wodurch mehr Zeit verloren geht als bei den anderen Blockgrößen? (wenn ich vorraussetzen kann, das pos ein Cacheobjekt ist)?

Du kannst getrost davon ausgehen, daß (12000 * 12000 * 4) / (1024 * 1024) Bytes = 549.316 MB an Daten nicht in den Cache passen und womöglich sogar die Festplatte ins Spiel kommt, was noch um Größenordnungen lahmer ist.

Edit: Das sollte ich vielleicht etwas qualifizieren. Wie alle anderen Objekte im Speicher wird auch dein Array stückweise durch den Cache geschleift werden, aber auch zwischen Cache und Speicher bleiben bei größerer Blockgröße mehr Speicheroperationen über.

Zitat

(PS: Mehrfachmessungen wurden durchgeführt und jeweils ein Mittelwert gebildet)

Das Minimum ist hier besser als der Mittelwert. Die gemessene Laufzeit ist die Summe aus der idealen Laufzeit und einem Störungsterm; die Störung ist aber immer positiv. Die beste Annäherung an die ideale Laufzeit ist also die kleinste gemessene Zeit, da sicher diese Messung am wenigsten gestört ist.

Edit: Ahja noch was. Ich hab ja schon beiläufig erwähnt, daß du Zählervariablen im Schleifenkopf deklarierst, jetzt hast du auch //-Kommentare. Bist du dir sicher, daß du einen C-Compiler im C-Modus verwendest? Gerade wenn du das Allerletzte aus deiner Maschine rausholen willst, wäre es gut, wenn dein Compiler und du die selbe Sprache sprechen. (Wobei mir im Moment keine subtilen Unterschiede zwischen C und C++ einfallen, die für die Optimierung von diesem konkreten Code relevant wären.)

Zitat von Blubberblase

Dauert es also länger wenn ich auf ein Double Word im Cache zugreife, als auf ein Word?

Nein.

Zitat von Blubberblase

Nun kann ich ja davon ausgehen, dass bei kleinerer Blockgröße der Cache weniger nachgeladen werden muss. Angenommen das Nachladen kostet eine gewisse Zeit t. Meinst du damit, dass für eine kleinere Blockgröße das Nachladen im einzelnen weniger Zeit brauch?

Nein. Die Zeit für das Nachladen von einer Cacheline ist relativ konstant. Aber je größer deine Datenelemente sind, umso weniger davon passen halt in eine Cacheline hinein.

Zitat von Plantschkuh!

Das Minimum ist hier besser als der Mittelwert. Die gemessene Laufzeit ist die Summe aus der idealen Laufzeit und einem Störungsterm; die Störung ist aber immer positiv. Die beste Annäherung an die ideale Laufzeit ist also die kleinste gemessene Zeit, da sicher diese Messung am wenigsten gestört ist.

fuer den hausgebrauch schon, aber wenn ich so messe, dann habe ich irgendwie das gefuehl ich beschwindle mich selbst. liegt wohl daran dass ich caching generell als cheating empfinde ;). mit caching verliert der begriff "ideale laufzeit" fuer mich so und so jegliche relevanz. aber was soll man groszartig tun um die laufzeit vernuenftig zu bestimmen? den einfluss vom scheduling mit einem RT-OS moeglichst ausschalten? gleich gar keine OS-schicht verwenden? bleiben immer noch caches. bei meinem ganzen halbwissen kommt mir vor man kann moderne architekturen ohnehin nicht wirklich vernuenftig messen und man sollte, wenn es wirklich drauf ankommt, einfachere/ältere/speziellere CPUs verbauen. imho baut zum beispiel das vmars architekturen mit konstanten verarbeitungszeiten.

Da musst du dir wohl den erzeugten Assemblercode im Detail ansehen. Wenn du mit verschiedenen Compilern/Compileroptionen/CPUs herumspielst, wirst du wohl es wohl recht bald schaffen, dass jede der drei Varianten mit irgendeiner Kombination die schnellste ist.

Zitat von Blubberblase

Aber ich verstehe nicht wieso man keine // als Kommentarzeichen in C verwenden kann?

Weil C (die Version von 1989, die noch am weitesten verbreitet ist) keine //-Kommentare unterstützt. Standardkonforme C-Compiler im standardkonformen Modus müssen zumindest irgendeine Meldung ausgeben, wenn du // verwendest; danach dürfen sie den Code gerne kompilieren, wie immer sie möchten. Ich sag nicht, daß du auf keinen Fall // verwenden sollst, aber du solltest dir sicher sein, daß du C schreibst und dein Compiler C von dir erwartet. C mit C++-Compilern übersetzen ist grausig.

Zitat von Kampi

fuer den hausgebrauch schon, aber wenn ich so messe, dann habe ich irgendwie das gefuehl ich beschwindle mich selbst. liegt wohl daran dass ich caching generell als cheating empfinde ;). mit caching verliert der begriff "ideale laufzeit" fuer mich so und so jegliche relevanz.

Naja, "ideale Laufzeit" ist die, die rauskommen würde, wenn es keine cache misses und page faults gäbe. Ganz ohne wirds allgemein nicht gehen, aber wenn man das Minimum von mehreren Messungen gibt, kriegt man etwas raus, was auf dem konkreten System sicher möglich ist.

Aber es stimmt schon, man muß wissen, was und wofür man misst. Wenn man wissen will, wie schnell das Programm "üblicherweise" sein wird, oder welche Schranke "fast immer" unterboten wird, sind andere Statistiken besser als das Minimum.

Zitat von Blubberblase

Wie kann man eigentlich herausbekommen wie groß diese Cacheline ist?

Man liest die Developer-Dokumentation seines Prozessors. Aber wie Ringding auch gemeint hat, irgendwann ist der Punkt erreicht, an dem du nur noch auf eine Plattform hin optimierst und Sachen machst, die woanders völlig kontraproduktiv wären.

Zitat

Code

int creatematrix(BLOCK *pos) {
 BLOCK shift=0; int BPB = BITS_PER_BLOCK -1;
    int row, col;
 for(row = 0; row < N; row++) {
   for(col = 0; col < N; col++) {
    if(col&1)
       shift |= (1 << (col & (BPB)));

   }     
 }
 return 0; 
}

Alles anzeigen

Messungen dieses Codes, und insbesondere des "Einflusses" der Variablen shift, sind völlig unsinnig. Diese Funktion ist semantisch äquivalent:

int creatematrix(BLOCK *ismawurscht)
{
    return 0;
}

und der Compiler darf gern entsprechenden Code erzeugen. Ganz so weit geht mein GCC zwar nicht, aber er generiert praktisch keinen Code für den Körper der innersten Schleife, wie wenn ich ihn ganz auskommentiere! Die Zuweisung an shift ist nämlich sogenannter partial dead code---das Ergebnis wird nie wirklich verwendet. Deswegen wird die Zuweisung munter wegoptimiert (bei dir anscheinend nur mit register, oder hast du noch nicht die maximale Optimierungsstufe aktiviert?).

Jedenfalls: Wenn dich die Performance deines echten Codes interessiert, mußt du deinen echten Code messen. Codeskizzen messen sagt nichts über deinen echten Code aus.

Zitat

Aber warum ist diese Operation shift |= (1 << (col & (BPB))); für 32 Bit schneller als für kleinere Blockgrößen?
Ich habe einen 32 Bit Prozessor. Vielleicht füllt der Rechner ja dieses shift mit zusätzlichen Nullen, damit es im 32 Bit Prozessor gut verarbeitet werden kann.

Sowas. Geladen werden üblicherweise ganze Speicherworte, aus denen muß dann noch was rausmaskiert werden.