C++: Verbessern der Cache-Leistung in einem 3D-Array

Question

Ich weiß nicht, wie Cache-Leistung auf einem sehr niedrigen Niveau zu optimieren, über Cachelinie Größe oder Assoziativität denken. Das kannst du nicht über Nacht lernen. Wenn man bedenkt, dass mein Programm auf vielen verschiedenen Systemen und Architekturen läuft, denke ich nicht, dass es sich auf jeden Fall lohnt. Aber dennoch, es gibt wahrscheinlich einige Schritte, die ich unternehmen kann, um Cache-Misses im Allgemeinen zu reduzieren.

Hier ist eine Beschreibung meines Problems:

I eine 3D-Anordnung von Zahlen aufweisen, wobei Werte an den Punkten im Raum darstellt, wie [x] [y] [z]. Jede Dimension hat die gleiche Größe, also ist es wie ein Würfel. Daraus muss ich ein weiteres 3D-Array machen, wobei jeder Wert in diesem neuen Array eine Funktion von 7 Parametern ist: der entsprechende Wert im ursprünglichen 3D-Array plus die 6 Indizes, die ihn im Raum "berühren". Ich mache mir vorerst keine Sorgen um die Kanten und Ecken des Würfels.

Hier ist, was ich in C++ bedeuten Code:

void process3DArray (int input[LENGTH][LENGTH][LENGTH], 
        int output[LENGTH][LENGTH][LENGTH]) 
{ 
    for(int i = 1; i < LENGTH-1; i++) 
     for (int j = 1; j < LENGTH-1; j++) 
      for (int k = 1; k < LENGTH-1; k++) 
      //The for loops start at 1 and stop before LENGTH-1 
      //or other-wise I'll get out-of-bounds errors 
      //I'm not concerned with the edges and corners of the 
      //3d array "cube" at the moment. 
      { 
       int value = input[i][j][k]; 

       //I am expecting crazy cache misses here: 
       int posX = input[i+1] [j] [k]; 
       int negX = input[i-1] [j] [k]; 
       int posY = input[i] [j+1] [k]; 
       int negY = input[i] [j-1] [k]; 
       int posZ = input[i] [j] [k+1]; 
       int negZ = input[i] [j] [k-1]; 

       output [i][j][k] = 
        process(value, posX, negX, posY, negY, posZ, negZ); 
      } 
} 

aber es scheint, wie wenn LÄNGE groß genug ist, werde ich Tonnen von Cache-Misses, wenn ich die Parameter für process bin holen. Gibt es eine cache-freundlichere Möglichkeit, dies zu tun, oder eine bessere Möglichkeit, meine Daten anders als ein 3D-Array zu repräsentieren?

Und wenn Sie die Zeit haben, diese zusätzlichen Fragen zu beantworten, muss ich den Wert von LÄNGE berücksichtigen? Wie ist es anders, ob LÄNGE 20 gegen 100 gegen 10000 ist. Würde ich auch etwas anderes tun müssen, wenn ich etwas anderes als Ganzzahlen verwende, wie etwa eine 64-Byte-Struktur?

@ ildjarn:

Sorry, ich glaube nicht, dass der Code, der die Arrays erzeugt ich vorbei bin in process3DArray zählte. Aber wenn es so wäre, würde ich gerne wissen warum.

int main() { 
    int data[LENGTH][LENGTH][LENGTH]; 
    for(int i = 0; i < LENGTH; i++) 
     for (int j = 0; j < LENGTH; j++) 
      for (int k = 0; k < LENGTH; k++) 
       data[i][j][k] = rand() * (i + j + k); 

    int result[LENGTH][LENGTH][LENGTH]; 
    process3DArray(data, result); 
} 

Answer 1

Das Wichtigste, was Sie bereits richtig haben. Wenn Sie Fortran verwenden würden, würden Sie es genau falsch machen, aber das ist eine andere Geschichte. Was Sie haben, ist, dass Sie in der inneren Schleife in der Richtung verarbeiten, in der Speicheradressen am nächsten sind. Ein einzelner Speicherabruf (über den Cache hinaus) zieht mehrere Werte ein, die einer Reihe von benachbarten Werten von k entsprechen. Innerhalb Ihrer Schleife enthält der Cache einige Werte von i, j; eine ähnliche Zahl von i +/- 1, j und von i, j +/- 1. Sie haben also grundsätzlich fünf disjunkte Speicherabschnitte aktiv. Für kleine Werte von LENGTH sind dies nur ein oder drei Speicherbereiche. Es liegt in der Natur des Aufbaus von Caches, dass Sie mehr als diese vielen getrennten Speicherabschnitte in Ihrem aktiven Satz haben können.

Ich hoffe, process() ist klein und inline. Sonst ist das vielleicht unbedeutend. Außerdem wirkt sich dies darauf aus, ob der Code in den Anweisungscache passt.

Da Sie an der Leistung interessiert sind, ist es fast immer besser, fünf Zeiger zu initialisieren (Sie brauchen nur einen für Wert, posZ und negZ) und dann * (p ++) innerhalb der Schleife.

fordert den Compiler auf, 3 Adds und zwei Multiplies zu generieren, es sei denn, Sie haben einen sehr guten Optimierer. Wenn Ihr Compiler besonders faul ist, wenn es um die Zuweisung von Registern geht, erhalten Sie auch vier Speicherzugriffe. sonst eins.

*inputIplusOneJK++ 

fragt nach einem Add und einer Speicherreferenz.

Answer 2

auf eine ähnliche Frage eine Antwort gibt es hier: https://stackoverflow.com/a/7735362/6210 (von mir!)

Das Hauptziel eine mehrdimensionales Array-Traversal zu optimieren, ist, dass Sie das Array so besuchen, um sicherzustellen, dass Sie den Cache wieder zu verwenden neigen Zeilen, auf die vom vorherigen Iterationsschritt zugegriffen wurde. Wenn Sie jedes Element eines Arrays einmal und nur einmal besuchen möchten, können Sie dies einfach in der Speicherreihenfolge tun (wie Sie es in Ihrer Schleife tun).

Da Sie etwas komplizierter als ein einfaches Element Traversal (besuchen ein Element plus 6 Nachbarn) tun, müssen Sie Ihre Traversal brechen, so dass Sie nicht zu viele Cache-Zeilen auf einmal zugreifen. Da das Cache-Thrashing von j und k dominiert wird, müssen Sie nur die Traversierung so ändern, dass Sie Blöcke zu einer Zeit statt Reihen auf einmal besuchen.

ZB:

const int CACHE_LINE_STEP= 8; 

void process3DArray (int input[LENGTH][LENGTH][LENGTH], 
        int output[LENGTH][LENGTH][LENGTH]) 
{ 
    for(int i = 1; i < LENGTH-1; i++) 
     for (int k_start = 1, k_next= CACHE_LINE_STEP; k_start < LENGTH-1; k_start= k_next; k_next+= CACHE_LINE_STEP) 
     { 
      int k_end= min(k_next, LENGTH - 1); 

      for (int j = 1; j < LENGTH-1; j++) 
       //The for loops start at 1 and stop before LENGTH-1 
       //or other-wise I'll get out-of-bounds errors 
       //I'm not concerned with the edges and corners of the 
       //3d array "cube" at the moment. 
      { 
       for (int k= k_start; k<k_end; ++k) 
       { 
        int value = input[i][j][k]; 

        //I am expecting crazy cache misses here: 
        int posX = input[i+1] [j] [k]; 
        int negX = input[i-1] [j] [k]; 
        int posY = input[i] [j+1] [k]; 
        int negY = input[i] [j-1] [k]; 
        int posZ = input[i] [j] [k+1]; 
        int negZ = input[i] [j] [k-1]; 

        output [i][j][k] = 
         process(value, posX, negX, posY, negY, posZ, negZ); 
       } 
      } 
     } 
} 

Was dies nicht gewährleistet, dass Sie den Cache nicht tun Thrash durch das Gitter in einem Block orientiert zu besuchen (eigentlich eher wie ein Fettsäule orientiert durch die Cache-Linie begrenzt Größe). Es ist nicht perfekt, da es Überlappungen gibt, die Cache-Zeilen zwischen Spalten kreuzen, aber Sie können es optimieren, um es besser zu machen.