Wie kann die Größe der L1-Cache-Zeilengröße mit IO-Timing-Messungen ermittelt werden?

Als Schulaufgabe muss ich einen Weg finden, die Zeilengröße des L1-Datencaches zu ermitteln, ohne Konfigurationsdateien zu lesen oder API-Aufrufe zu verwenden. Soll Lese-/Schreib-Timings für Speicherzugriffe verwenden, um diese Informationen zu analysieren und abzurufen. Also wie könnte ich das machen?

In einem unvollständigen Versuch für einen anderen Teil der Aufgabe, um die Ebenen und die Größe des Caches zu finden, habe ich:

for (i = 0; i < steps; i++) {
    arr[(i * 4) & lengthMod]++;
}

Ich dachte, vielleicht brauche ich nur Variationslinie 2, (i * 4) Teil? Sobald ich also die Cache-Line-Größe überschreite, muss ich sie möglicherweise ersetzen, was einige Zeit in Anspruch nimmt? Aber ist es so einfach? Der benötigte Block ist vielleicht schon irgendwo im Speicher? Oder vielleicht kann ich mich immer noch darauf verlassen, dass, wenn ich einen ausreichend großen habe stepswird es trotzdem ziemlich genau klappen?

AKTUALISIEREN

Hier ein Versuch auf GitHub … Hauptteil unten

// repeatedly access/modify data, varying the STRIDE
for (int s = 4; s <= MAX_STRIDE/sizeof(int); s*=2) {
    start = wall_clock_time();
    for (unsigned int k = 0; k < REPS; k++) {
        data[(k * s) & lengthMod]++;
    }
    end = wall_clock_time();
    timeTaken = ((float)(end - start))/1000000000;
    printf("%d, %1.2f \n", s * sizeof(int), timeTaken);
}

Das Problem ist, dass es anscheinend keine großen Unterschiede zwischen dem Timing gibt. FYI. da es sich um einen L1-Cache handelt. Ich habe SIZE = 32 K (Größe des Arrays)

Weisen Sie ein BIG zu char array (stellen Sie sicher, dass es zu groß ist, um in L1 oder L2-Cache). Füllen Sie es mit zufälligen Daten.

Gehen Sie in Schritten von über das Array n Byte. Machen Sie etwas mit den abgerufenen Bytes, wie zum Beispiel das Summieren.

Vergleichen und berechnen Sie, wie viele Bytes/Sekunde Sie mit unterschiedlichen Werten von verarbeiten können n, beginnend bei 1 und gezählt bis etwa 1000. Stellen Sie sicher, dass Ihr Benchmark die berechnete Summe ausgibt, damit der Compiler den Benchmark-Code unmöglich wegoptimieren kann.

Wann n == Ihre Cache-Zeilengröße, jeder Zugriff erfordert das Lesen einer neuen Zeile in den L1-Cache. Die Benchmark-Ergebnisse sollten an diesem Punkt also ziemlich stark langsamer werden.

Wenn das Array groß genug ist, sind die Daten am Anfang des Arrays bereits wieder aus dem Cache, wenn Sie das Ende erreichen, was Sie möchten. Also, nachdem Sie erhöht haben n und neu starten, werden die Ergebnisse nicht dadurch beeinträchtigt, dass benötigte Daten bereits im Cache vorhanden sind.

Schau mal rein Kalibratoralle Arbeiten sind jedoch urheberrechtlich geschützt Quellcode ist frei verfügbar. Von seinem dokumentieren Die Idee, Cache-Line-Größen zu berechnen, klingt viel gebildeter als das, was hier bereits gesagt wurde.

Die unserem Kalibrator-Tool zugrunde liegende Idee ist, einen Mikro-Benchmark zu haben, dessen Leistung nur von der Häufigkeit der auftretenden Cache-Fehler abhängt. Unser Kalibrator ist ein einfaches C-Programm, hauptsächlich eine kleine Schleife, die eine Million Speicherauslesungen ausführt. Indem wir den Stride (dh den Versatz zwischen zwei aufeinanderfolgenden Speicherzugriffen) und die Größe des Speicherbereichs ändern, erzwingen wir unterschiedliche Cache-Miss-Raten.

Grundsätzlich wird das Auftreten von Cache-Miss durch die Array-Größe bestimmt. Array-Größen, die in den L1-Cache passen, erzeugen keine Cache-Fehler, sobald die Daten in den Cache geladen wurden. Analog verursachen Arrays, die die L1-Cachegröße überschreiten, aber immer noch in L2 passen, L1-Fehlschläge, aber keine L2-Fehlschläge. Schließlich verursachen Arrays, die größer als L2 sind, sowohl L1- als auch L2-Fehlschläge.

Die Häufigkeit von Cache-Fehlschlägen hängt von der Zugriffsschrittweite und der Cache-Zeilengröße ab. Bei Schritten, die gleich oder größer als die Cache-Zeilengröße sind, tritt bei jeder Iteration ein Cache-Miss auf. Bei Schritten, die kleiner als die Cache-Zeilengröße sind, tritt ein Cache-Mißerfolg nur alle n Iterationen (im Durchschnitt) auf, wobei n das Verhältnis Cache-Zeilengröße/Schrittweite ist.

Somit können wir die Latenz für einen Cache-Miss berechnen, indem wir die Ausführungszeit ohne Misses mit der Ausführungszeit mit genau einem Miss pro Iteration vergleichen. Dieser Ansatz funktioniert nur, wenn Speicherzugriffe rein sequentiell ausgeführt werden, dh wir müssen sicherstellen, dass sich weder zwei oder mehr Ladebefehle noch Speicherzugriffe und reine CPU-Arbeit überschneiden können. Um dies zu erreichen, verwenden wir einen einfachen Pointer-Chasing-Mechanismus: Der Speicherbereich, auf den wir zugreifen, wird so initialisiert, dass jeder Ladevorgang die Adresse für den nachfolgenden Ladevorgang in der nächsten Iteration zurückgibt. Somit können superskalare CPUs nicht von ihrer Fähigkeit profitieren, die Speicherzugriffslatenz durch spekulative Ausführung zu verbergen.

Um die Cache-Eigenschaften zu messen, führen wir unser Experiment mehrmals durch, wobei wir die Schrittweite und die Array-Größe variieren. Wir stellen sicher, dass der Stride mindestens zwischen 4 Bytes und dem Doppelten der maximal erwarteten Cache-Zeilengröße variiert und dass die Array-Größe von der Hälfte der minimal erwarteten Cache-Größe bis mindestens zum Zehnfachen der maximal erwarteten Cache-Größe variiert.

Ich musste auskommentieren #include "math.h" um es zu kompilieren, danach wurden die Cache-Werte meines Laptops korrekt gefunden. Ich konnte auch keine generierten Postscript-Dateien anzeigen.

Du kannst den … benutzen CPUID Funktion in Assembler, obwohl nicht portabel, gibt es Ihnen, was Sie wollen.

Für Intel-Mikroprozessoren kann die Cache-Zeilengröße berechnet werden, indem bh mit 8 multipliziert wird, nachdem die CPUID-Funktion 0x1 aufgerufen wurde.

Für AMD-Mikroprozessoren ist die Daten-Cache-Zeilengröße in cl und die Anweisungs-Cache-Zeilengröße ist in dl, nachdem die cpuid-Funktion 0x80000005 aufgerufen wurde.

Davon habe ich das übernommen Artikel hier.

Ich denke, Sie sollten ein Programm schreiben, das das Array in zufälliger Reihenfolge durchläuft, anstatt direkt, da moderne Prozesse Hardware-Vorabrufe durchführen. Erstellen Sie zum Beispiel ein Array von int, dessen Werte die Nummer der nächsten Zelle sind. Ich habe vor 1 Jahr ein ähnliches Programm gemacht http://pastebin.com/9mFScs9Z
Sorry für mein Deutsch, ich bin kein Muttersprachler.

Sehen Sie, wie memtest86 implementiert wird. Sie messen und analysieren die Datenübertragungsrate auf irgendeine Weise. Punkte der Ratenänderung entsprechen der Größe von L1, L2 und möglicher L3-Cache-Größe.

Wenn Sie im Schlamm stecken bleiben und nicht herauskommen, schauen Sie nach hier.

Es gibt Handbücher und Code, die erklären, wie Sie das tun, was Sie fragen. Der Code ist auch ziemlich hochwertig. Sehen Sie sich “Unterprogrammbibliothek” an.

Der Code und die Handbücher basieren auf X86-Prozessoren.

Ich denke, es sollte ausreichen, eine Operation zu timen, die eine gewisse Menge an Speicher verwendet. Erhöhen Sie dann nach und nach den Speicher (z. B. Operanden), der von der Operation verwendet wird. Wenn die Betriebsleistung stark nachlässt, haben Sie die Grenze gefunden.

Ich würde einfach ein paar Bytes lesen, ohne sie zu drucken (das Drucken würde die Leistung so stark beeinträchtigen, dass es zu einem Engpass würde). Beim Lesen sollte das Timing direkt proportional zur Menge der gelesenen Bytes sein, bis die Daten nicht mehr in den L1 passen, dann erhalten Sie den Leistungseinbruch.

Außerdem sollten Sie den Speicher einmal zu Beginn des Programms allokieren und bevor Sie mit dem Zählen der Zeit beginnen.