Speicherklassen und Pipelining

  • Hallo Forum!
    Ich habe gehört dass es drei unterschiedliche Speicherklassen gibt:
    - Registerobjekte
    - Hauptspeicherobjekte
    - Cacheobjekte

    Diese Speicherklassen würden durch den Compiler beeinflusst werden. Wie kann man diese Speicherklassen grundsätzlich beschreiben und welchen Einfluss haben sie auf die Laufzeit?

    Registerobjekte werden sicher in Register der CPU geladen und lassen sich schnell verarbeiten und abrufen. Dazu zählen sicherlich Zählvariablen in Schleifen. Wie ist das eigentlich wenn ich 3 Schleifen ineinander verschachtelt habe (mit 3 Zählvariablen)? Z.b.

    Code
    for(int a=0; a < N; a++)
     for(int b=0; b < N; b++)
      for(int c=0; c < N; c++)

    Wird dann beim Eintritt in eine untere Schleife die Zählvariable irgendwo zwischengelagert während die Zählvariable der unteren Schleife in das Register geladen wird?

    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. Warum ist das so?

    Ich kann mir noch nicht so richtig vorstellen wie das mit dem Pufferspeicher (Cache) funktioniert. Das ist also ein Zwischenspeicher auf dem schneller zugegriffen werden kann als auf den Hauptspeicher. Es wird immer ein bestimmter Teil geladen (Cacheline?) auf den zugegriffen werden kann. Wird jedoch mehr Cache benötigt, dauert das ganze länger, weil ja erst wieder Cache aus dem Hauptspeicher geholt werden muss. 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?

    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? 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?

    Nun zu dem zweiten Teil meiner Frage, dem Pipelining. Was gibt es da bei der Programmierung zu beachten? Ich habe z.B. folgenden Quelltext:

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

    Hier hätte der Compiler doch ersteinmal kein Problem mit den Werten von m1. Beispielweise wird m1[0] verändert und es muss auch nicht mehr damit gearbeitet werden. Also kann der Compiler ohne probleme den nächsten Befehl laden. Aber wie ist das mit der Zählvariable a? Diese muss ja immer um 1 erhöht werden und das Ergebnis wird auch gleich wieder benötigt (m1[a]).
    Welche grundsätzlichen Möglichkeiten habe ich zur Verfügung in dieser Hinsicht besseren Code zu schreiben?

  • 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:

    Code
    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:

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


    Ein paar einfache Transformationen, zuerst common subexpression elimination:

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


    Strength reduction:

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


    Elimination der unnötigen Variablen a;

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


    Elimination der unnötigen Variablen temp:

    Code
    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.

    *plantsch*

  • Ich habe nocheinmal eine Frage bezüglich Cacheobjekten.
    Meine Funktion sieht wie folgt aus:

    Vor dem Funktionsaufruf habe ich schon Speicher angefordert:
    BLOCK *pos = malloc(N * N * sizeof(BLOCK));

    Ich habe die Funktion für verschiedene Blockgrößen getestet. Und dabei folgende Messungen erhalten(für N = 12000)

    32 Bit: 0,93 s
    16 Bit: 0,56 s
    8 Bit: 0,41 s

    Nun habe ich den Algorithmus nocheinmal gestartet, wobei ich KEINE Zeigererhöhungen (++pos) eingebaut habe, sondern nur *pos = 1 geschrieben habe.
    Dabei habe ich bei einem N von 12000 eine konstante Zeit von 0,34s gemessen.

    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?
    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)?

    Oder sind die Unterschiede ganz anders zu erklären?
    (PS: Mehrfachmessungen wurden durchgeführt und jeweils ein Mittelwert gebildet)


  • Diese Variante könnte signifikant schneller sein:

    Code
    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:

    Code
    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.)

    *plantsch*

  • Vielen Dank für die Hilfe!
    Die optimierte Variante scheint wirklich viel besser zu sein.
    Also kann ich zusammenfassen, dass die Zeit vor allem ersteinmal durch den Zugriff auf den Cache zu verzeichnen ist.
    Dauert es also länger wenn ich auf ein Double Word im Cache zugreife, als auf ein Word?


    Zitat


    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.

    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?

    Wegen dem C-Code... Das mit dem Deklaration in der for Schleife ist mir beim Beitragschreiben passiert (ich habe den Code nach dem Einfügen noch etwas verändert). Aber mein Compiler meckert, wenn ich das so compilieren würde. Aber ich verstehe nicht wieso man keine // als Kommentarzeichen in C verwenden kann?

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


    Nein.

    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.


  • 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.

    Willfähriges Mitglied des Fefe-Zeitbinder-Botnets und der Open Source Tea Party.

  • Super, bis dahin konnte ich alles nachvollziehen.
    Wie kann man eigentlich herausbekommen wie groß diese Cacheline ist?

    Nun noch zu einem anderem Problem. Jetzt habe ich folgende Funktion wieder für verschiedene Blockgrößen gemessen:

    (Das col&1 ist wie eine Art Platzhalter für eine sehr viel komplexere Bedingung, die aber unabhängig von der Blockgröße ist, aber zur Vereinfachung bei den Messungen weggelassen wurde)
    Der Sinn der Funktion sei jetzt mal unwichtig.

    Ich habe folgende Messergebnisse bei einem N von 60000 für die Blockgröße 32 Bit, 16 Bit und 8 Bit erhalten:

    32 Bit: 8,15
    16 Bit: 8,57
    8 Bit: 9,22

    Das Ergebnis verblüfft mich ehrlich gesagt etwas.
    Die einzigen Variablen, die abhängig von der Blockgröße sind, sind shift und BPB. 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. Und das kostet Zeit? Während das beim 32 Bit-shift ja nicht möglich ist...
    Jetzt habe ich folgendes gemacht: Ich habe bei der Deklaration von shift ein "register" mit beigefügt. Das bewirkt seltsamerweise, dass für alle(!!) Laufzeiten der Wert etwa bei 7,08 liegt. Also fällt meine Erklärung schoneinmal weg, denn offensichtlich wird shift in der obigen Funktion nicht als Registerobjekt behandelt.
    An dieser Stelle bin ich mit meinen Erklärungen am Ende und weiß leider nicht mehr weiter...

  • 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.

  • 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.

    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.

    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


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

    Code
    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.

    *plantsch*

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!