Auswirkung der Cache-Größe auf Code

Question

Ich möchte den Effekt der Cache-Größe auf Code untersuchen. Bei Programmen, die mit großen Arrays arbeiten, kann es zu einer erheblichen Beschleunigung kommen, wenn das Array in den Cache passt.

Wie kann ich das messen?

ich versuchte, dieses c-Programm auszuführen:

#define L1_CACHE_SIZE  32  // Kbytes 8192 integers 
#define L2_CACHE_SIZE  256  // Kbytes 65536 integers 
#define L3_CACHE_SIZE  4096 // Kbytes 

#define ARRAYSIZE 32000 
#define ITERATIONS 250 

int arr[ARRAYSIZE]; 

/*************** TIME MEASSUREMENTS ***************/ 

double microsecs() { 
    struct timeval t; 
    if (gettimeofday(&t, NULL) < 0) 
    return 0.0; 
    return (t.tv_usec + t.tv_sec * 1000000.0);  
} 

void init_array() { 
    int i; 
    for (i = 0; i < ARRAYSIZE; i++) { 
     arr[i] = (rand() % 100); 
    } 
} 

int operation() { 
    int i, j; 
    int sum = 0; 
    for (j = 0; j < ITERATIONS; j++) { 
     for (i = 0; i < ARRAYSIZE; i++) { 
      sum =+ arr[i]; 
     } 
    } 

    return sum; 
} 

void main() { 

    init_array(); 

    double t1 = microsecs(); 
    int result = operation(); 
    double t2 = microsecs(); 

    double t = t2 - t1; 

    printf("CPU time %f milliseconds\n", t/1000); 
    printf("Result: %d\n", result);  
} 

Werte von ARRAYSIZE und ITERATIONS (wobei das Produkt und damit die Anzahl von Befehlen, konstant), um, wenn das Programm schneller laufen, wenn das zu überprüfen, nehmen Array passt in den Cache, aber ich bekomme immer die gleiche CPU-Zeit.

Kann jemand sagen, was ich falsch mache?

Answer 1

In Ihrem Code ist ein Tippfehler enthalten. = + anstelle von + =.

Answer 2

Das Array arr ist mit dem Abschnitt BSS [nicht initialisiert] verknüpft. Der Standardwert für die Variablen in diesem Abschnitt ist Null. Alle Seiten in diesem Abschnitt werden anfänglich R/O zu einem einzigenzero page zugeordnet. Das ist Linux/Unix centric, aber wahrscheinlich gilt es für die meisten modernen Betriebssysteme

Also, unabhängig von der Array-Größe, holen Sie nur von einer einzigen Seite, die im Cache abgerufen wird, deshalb erhalten Sie die gleichen Ergebnisse .

Sie müssen das "zero page mapping" brechen, indem Sie etwas an alle arr schreiben, bevor Sie Ihre Tests durchführen. Das heißt, zuerst etwas wie memset tun. Dies führt dazu, dass das Betriebssystem eine lineare Seitenzuordnung für arr unter Verwendung seines COW-Mechanismus (Copy-on-Write) erstellt.

Answer 3

Was Sie wirklich wollen, ist ein "Speicher Berg" zu bauen. Ein Memory Mountain hilft Ihnen dabei, zu visualisieren, wie Speicherzugriffe die Programmleistung beeinflussen. Insbesondere misst es Lesedurchsatz gegen räumliche Lokalität und zeitliche Lokalität. Gute räumliche Lokalität bedeutet, dass aufeinanderfolgende Speicherzugriffe nahe beieinander liegen und eine gute zeitliche Lokalität bedeutet, dass auf einen bestimmten Speicherort mehrere Male in einer kurzen Menge an Programmzeit zugegriffen wird. Hier ist a link, die kurz Cache Leistung und Speicher Berge erwähnt. Die 3. Ausgabe des Lehrbuchs, das in diesem Link erwähnt wird, ist eine sehr gute Referenz, speziell Kapitel 6, um mehr über Speicher- und Cache-Leistung zu erfahren. (Tatsächlich verwende ich zur Zeit diesen Abschnitt als Referenz, wie ich diese Frage beantworten.)

Another link zeigt eine Testfunktion, die Sie verwenden könnten Cache-Leistung zu messen, die ich hier kopiert haben:

void test(int elems, int stride) 
{ 
    int i, result = 0; 
    volatile int sink; 
    for (i = 0; i < elems; i+=stride) 
     result += data[i]; 
    sink = result; 
} 

Stride ist die zeitliche Lokalität - wie weit entfernt die Speicherzugriffe sind. Die Idee ist, dass diese Funktion die Anzahl der Zyklen schätzen würde, die zum Ausführen benötigt wurden. Um den Durchsatz zu erhalten, sollten Sie (Größe/Schritt)/(Zyklen/MHz) verwenden, wobei Größe die Größe des Arrays in Byte ist, Zyklen das Ergebnis dieser Funktion und MHz die Taktgeschwindigkeit Ihres Prozessors ist . Sie sollten dies einmal aufrufen, bevor Sie Messungen vornehmen, um Ihren Cache aufzuwärmen. Führen Sie dann die Schleife aus und nehmen Sie Messungen vor.

Ich habe eine GitHub repository gefunden, mit der Sie einen 3D-Speicherberg auf Ihrer eigenen Maschine erstellen können. Ich ermutige Sie, es auf mehreren Rechnern mit unterschiedlichen Prozessoren zu versuchen und Unterschiede zu vergleichen.