Messung von TLB-Effekten auf einem Cortex-A9

Question 1

Nach dem Lesen des folgenden Papiers https://people.freebsd.org/~lstewart/articles/cpumemory.pdf (“Was jeder Programmierer über Speicher wissen sollte”) Ich wollte einen der Tests des Autors ausprobieren, nämlich die Messung der Auswirkungen von TLB auf die endgültige Ausführungszeit.

Ich arbeite an einem Samsung Galaxy S3, in das ein Cortex-A9 eingebettet ist.

Laut Dokumentation:

Wir haben zwei Mikro-TLBs für den Befehls- und Daten-Cache in L1 (http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0388e/Chddiifa.html)

Der Haupt-TLB befindet sich in L2 (http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0388e/Chddiifa.html)
Data Micro TLB hat 32 Einträge (Instruction Micro TLB hat entweder 32 oder 64 Einträge)
L1′-Größe == 32 KByte
L1-Cache-Zeile == 32 Bytes

L2-Größe == 1 MB

Ich habe ein kleines Programm geschrieben, das ein Array von Strukturen mit N Einträgen zuweist. Die Größe jedes Eintrags beträgt == 32 Bytes, sodass er in eine Cache-Zeile passt. Ich führe mehrere Lesezugriffe durch und messe die Ausführungszeit.

typedef struct {
     int elmt; // sizeof(int) == 4 bytes
     char padding[28]; // 4 + 28 = 32B == cache line size
}entry;


volatile entry ** entries = NULL;

//Allocate memory and init to 0
entries = calloc(NB_ENTRIES, sizeof(entry *));
if(entries == NULL) perror("calloc failed"); exit(1);

for(i = 0; i < NB_ENTRIES; i++)
{
      entries[i] = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
      if(entries[i] == MAP_FAILED) perror("mmap failed"); exit(1);
}

entries[LAST_ELEMENT]->elmt = -1

//Randomly access and init with random values
n = -1;
i = 0;
while(++n < NB_ENTRIES -1)
{
      //init with random value
      entries[i]->elmt = rand() % NB_ENTRIES;

      //loop till we reach the last element
      while(entries[entries[i]->elmt]->elmt != -1)
      {
            entries[i]->elmt++;
            if(entries[i]->elmt == NB_ENTRIES)
                     entries[i]->elmt = 0;
      }

       i = entries[i]->elmt;
}


gettimeofday(&tStart, NULL);
for(i = 0; i < NB_LOOPS; i++)
{
     j = 0;
     while(j != -1)
     {
          j = entries[j]->elmt
     }
}
gettimeofday(&tEnd, NULL);

time = (tEnd.tv_sec - tStart.tv_sec);
time *= 1000000;
time += tEnd.tv_usec - tStart.tv_usec;
time *= 100000
time /= (NB_ENTRIES * NBLOOPS);

fprintf(stdout, "%d %3lld.%02lld\n", NB_ENTRIES, time / 100, time % 100);

Ich habe eine äußere Schleife, die NB_ENTRIES von 4 bis 1024 variieren lässt.

Wie man in der Abbildung unten sehen kann, ist die Ausführungszeit länger, während NB_ENTRIES == 256 Einträge sind.

Wenn NB_ENTRIES == 404, erhalte ich ein “out of memory” (Warum? Mikro-TLBs überschritten? Haupt-TLBs überschritten? Seitentabellen überschritten? Virtueller Speicher für den Prozess überschritten?)

Kann mir bitte jemand erklären, was wirklich von 4 auf 256 Einträge los ist, dann von 257 auf 404 Einträge?

BEARBEITEN 1

Wie vorgeschlagen wurde, habe ich membench ausgeführt (src-Code) und darunter die Ergebnisse:

BEARBEITEN 2

Im Folgenden Papier (Seite 3) Sie liefen (vermutlich) den gleichen Benchmark. Aber die verschiedenen Schritte sind aus ihren Plots deutlich ersichtlich, was nicht mein Fall ist.

Im Moment kann ich anhand ihrer Ergebnisse und Erklärungen nur wenige Dinge identifizieren.

Diagramme bestätigen, dass die L1-Cache-Zeilengröße 32 Byte beträgt, da sie, wie sie sagten, 32 Bytes betragen

“Sobald die Arraygröße die Größe des Datencaches (32 KB) überschreitet, beginnen die Lesevorgänge, Fehler zu generieren […] ein Wendepunkt tritt auf, wenn jeder Lesevorgang einen Fehler erzeugt”.

In meinem Fall erscheint der allererste Wendepunkt, wenn Stride == 32 Bytes ist. – Das Diagramm zeigt, dass wir einen Cache der zweiten Ebene (L2) haben. Ich denke, es wird durch die gelbe Linie dargestellt (1 MB == L2-Größe) – Daher spiegeln die beiden letzten Diagramme über letzterem wahrscheinlich die Latenz beim Zugriff auf den Hauptspeicher wider (+ TLB?).

Aus diesem Benchmark kann ich jedoch nicht erkennen:

die Cache-Assoziativität. Normalerweise sind D-Cache und I-Cache 4-fach assoziativ (Cortex-A9 TRM).

Die TLB-Effekte. Wie sie sagten,

In den meisten Systemen weist eine sekundäre Erhöhung der Latenz auf den TLB hin, der eine begrenzte Anzahl von virtuellen zu physischen Übersetzungen zwischenspeichert.[..] Das Fehlen eines Latenzanstiegs, der TLB zuzuschreiben ist, weist darauf hin […]”

Wahrscheinlich wurden große Seitengrößen verwendet/implementiert.

BEARBEITEN 3

Dieser Link erklärt die TLB-Effekte aus einem anderen Membench-Diagramm. Man kann tatsächlich die gleichen Effekte auf meinem Diagramm abrufen.

Auf einem 4-KB-Seitensystem werden Sie mit zunehmenden Fortschritten, während sie immer noch < 4 KB sind, immer weniger Auslastung jeder Seite genießen [...] Sie müssen bei jedem Zugriff auf den TLB der 2. Ebene zugreifen [...]

Der Cortex-A9 unterstützt 4-KB-Seitenmodus. In der Tat, wie man in meinem Diagramm bis zu den Schritten == 4K sehen kann, nehmen die Latenzen dann zu, wenn sie 4K erreichen

Sie profitieren plötzlich wieder davon, da Sie eigentlich ganze Seiten überspringen.

Question 2

tl; dr -> Stellen Sie ein geeignetes MVCE bereit.

Diese Antwort sollte ein Kommentar sein, ist aber zu groß, um als Kommentar gepostet zu werden, also poste stattdessen als Antwort:

Ich musste eine Reihe von Syntaxfehlern (fehlende Semikolons) beheben und undefinierte Variablen deklarieren.
Nach der Behebung all dieser Probleme hat der Code NICHTS getan (das Programm wurde sogar vor der Ausführung des ersten beendet mmap. Ich gebe den Tipp, immer geschweifte Klammern zu verwenden, hier ist Ihr erster und Ihr zweiter Fehler, der dadurch verursacht wird, dass Sie dies NICHT tun:

.

// after calloc:
if(entries == NULL) perror("calloc failed"); exit(1);
// after mmap
if(entries[i] == MAP_FAILED) perror("mmap failed"); exit(1);

beide Zeilen beenden einfach Ihr Programm, unabhängig von der Bedingung.

Hier haben Sie eine Endlosschleife (umformatiert, geschweifte Klammern hinzugefügt, aber keine andere Änderung):

.

//Randomly access and init with random values
n = -1;
i = 0;
while (++n < NB_ENTRIES -1) {
    //init with random value
    entries[i]->elmt = rand() % NB_ENTRIES;

    //loop till we reach the last element
    while (entries[entries[i]->elmt]->elmt != -1) {
        entries[i]->elmt++;
        if (entries[i]->elmt == NB_ENTRIES) {
            entries[i]->elmt = 0;
        }
    }

    i = entries[i]->elmt;
}

Die erste Iteration beginnt mit der Einstellung entries[0]->elmt auf einen zufälligen Wert, dann erhöht sich die innere Schleife, bis sie erreicht ist LAST_ELEMENT. Dann i auf diesen Wert gesetzt ist (d.h LAST_ELEMENT) und die zweite Schleife überschreibt die Endmarke -1 zu einem anderen zufälligen Wert. Dann wird mod NB_ENTRIES in der inneren Schleife ständig erhöht, bis Sie STRG+C drücken.

Fazit

Wenn Sie Hilfe benötigen, posten Sie ein minimales, vollständiges und überprüfbares Beispiel und nichts anderes.