C++, Wie Kraft-prefetch-Daten-cache? (array-Schleife)

Ich Schleife wie diese

start = __rdtsc();
unsigned long long count = 0;
for(int i = 0; i < N; i++)
    for(int j = 0; j < M; j++)
        count += tab[i][j];
stop = __rdtsc();
time = (stop - start) * 1/3;

Brauchen, um zu überprüfen, wie prefetch Daten, die Einflüsse auf die Effizienz. Wie zu zwingen, prefetch einige Werte aus dem Speicher in den cache, bevor Sie gezählt werden?

nur überprüfen Sie Ihre profiler. wahrscheinlich caching ist noch schlimmer, wenn Sie schalten Sie Ihr for-Schleifen.
Die meisten modernen CPUs umgehen kann pre-fetch automatisch. Sie sollten nur die Ausgabe Ihrer eigenen Anweisungen, wenn es nicht offensichtlich ist. Auch pre-fetch-Anweisungen sind nicht gerade tragbar; jeder compiler hat seine eigenen Interna.
Was Sie tun, ist die stream-Verarbeitung. Ich habe gute Gründe zu glauben, dass aus der Summe der Daten in einer einzelnen cache-Zeile erfordert weniger Zeit als das Befüllen mit Daten aus dem Hauptspeicher und Sie sind tatsächlich begrenzt durch die verfügbare Speicherbandbreite. Ich sehe nicht, wie prefetching (entweder manuell oder automatisch) könnte möglicherweise die Verbesserung der Effizienz.

InformationsquelleAutor lizaczek | 2013-01-09

  1. 3

    Zunächst nehme ich an, dass tab ist ein großes 2D-array wie ein statisches array (z.B. int tab[1024*1024][1024*1024]) oder dynamisch zugewiesen array (z.B. int** tab und folgende mallocs). Hier, wollen Sie die prefetch-Daten aus tab auf den cache, die Ausführungszeit zu reduzieren.

    Einfach, ich glaube nicht, dass Sie müssen manuell einfügen prefetching, um Ihren code, wo eine einfache Herabsetzung für einen 2D-array durchgeführt wird. Moderne CPUs führen Sie den automatischen prefetching, wenn notwendig und gewinnbringend.

    Zwei Fakten, die Sie wissen sollten für dieses problem:

    (1) Sie sind bereits ausnutzen der räumlichen Lokalität tab innerhalb der innersten Schleife. Einmal tab[i][0] ist zu Lesen (nach einem cache-miss oder page fault), werden die Daten aus tab[i][0] zu tab[i][15] werden in der CPU-caches, unter der Annahme, dass die cache-line-Größe 64 bytes.

    (2) Allerdings, wenn der code durchläuft in der Zeile, d.h., tab[i][M-1] zu tab[i+1][0], ist es sehr wahrscheinlich eine kalte cache-miss, vor allem, wenn tab ist ein dynamisch zugewiesen array, wobei jede Zeile, die zugewiesen werden können in einer fragmentierten Weise. Allerdings, wenn das array ist statisch zugewiesen wird, wird jede Zeile befinden, werden zusammenhängend in den Speicher.

    So, dieses Verfahren macht nur Sinn, wenn Sie Lesen (1) das erste Element der nächsten Zeile, und (2) j + CACHE_LINE_SIZE/sizeof(tab[0][0]) vor der Zeit.

    Können Sie dies durch einfügen von prefetch-Vorgang (z.B. __builtin_prefetch) in der oberen Schleife. Doch moderne Compiler können nicht immer Strahlen eine solche prefetch-Anweisungen. Wenn Sie wirklich wollen, das zu tun, sollten Sie überprüfen die erzeugten Binär-code.

    Jedoch, als ich sagte, ich tun nicht empfehlen Sie tun das, weil moderne CPUs werden meist prefetching automatisch, und dass das automatische prefetching wird meist übertreffen in Ihrem Handbuch-code. Zum Beispiel, wenn eine Intel-CPU wie der Ivy-Bridge-Prozessoren, es gibt mehrere Daten-Prefetcher wie prefetching, L1, L2, oder L3-cache. (Ich glaube nicht, dass mobile Prozessoren haben eine ausgefallene Daten-prefetcher). Einige Prefetcher lädt benachbarten cache-Zeilen.

    Wenn du mehr teure Berechnungen auf großen 2D-arrays, gibt es viele alternative algorithmen, die mehr freundlich zu den caches. Ein anschauliches Beispiel wäre blockiert(Titel) - matrix multiplizieren. Eine naive matrix-Multiplikation leidet viel cache findet, aber ein gesperrt-Algorithmus deutlich reduziert cache findet durch die Berechnung auf kleine Teilmengen, die fit sind, um caches. Finden Sie einige Hinweise, wie diese.

    InformationsquelleAutor minjang

  2. 7

    Für GCC nur:

    __builtin_prefetch((const void*)(prefetch_address),0,0);

    prefetch_address können unwirksam sein, wird es keinen segfault. Wenn es zu klein Differenz zwischen prefetch_address - und aktuellen Standort -, es könnte keine Wirkung oder sogar abschwächen. Versuchen Sie es mindestens 1k Voraus.

    InformationsquelleAutor Leonid Volnitsky

  3. 3

    Die einfachste/die meisten tragbaren Methode ist, Lesen Sie einfach einige Daten jeder cacheline bytes auseinander. Vorausgesetzt Registerkarte ist ein einwandfreies zwei-dimensionales array, können Sie:

    char *tptr = (char *)&tab[0][0];
tptr += 64;
char temp;
volatile char keep_temp_alive;
for(int i = 0; i < N; i++)
{
    temp += *tptr;
    tptr += 64;
    for(j = 0; j < M; j++)
        count += tab[i][j];
}
keep_temp_alive = temp;

    Sowas. Aber es hängt von ab:
    1. Sie enden nicht, bis das Lesen außerhalb des zugewiesenen Speichers [zu viel].
    2. die J-Schleife ist nicht viel größer als 64 butes. Wenn es ist, möchten Sie möglicherweise weitere Schritte hinzufügen von temp += *tptr; tptr += 64; im begginning der Schleife.

    Den keep_temp_alive nach der Schleife ist unerlässlich, um zu verhindern, dass der compiler komplett entfernen temp als unnötige Lasten.

    Leider, ich bin zu langsam zu schreiben generischen code zu empfehlen, die eingebauten Anweisungen, die Punkte, geht an Leonid.

    InformationsquelleAutor Mats Petersson

Schreibe einen Kommentar