Was kostet ein L1-Cache-Miss?

StackOverflow https://stackoverflow.com/questions/1126529

  •  13-09-2019
  •  | 
  •  

Frage

Bearbeiten:Zu Referenzzwecken (falls jemand über diese Frage stolpert) schrieb Igor Ostrovsky a guter Eintrag über Cache-Fehler.Es werden verschiedene Themen besprochen und Beispielzahlen angezeigt. Bearbeiten beenden

Ich habe einige Tests durchgeführt <long story goes here> und ich frage mich, ob ein Leistungsunterschied auf Speicher-Cache-Fehler zurückzuführen ist.Der folgende Code veranschaulicht das Problem und reduziert es auf den kritischen Timing-Teil.Der folgende Code enthält einige Schleifen, die den Speicher in zufälliger Reihenfolge und dann in aufsteigender Adressreihenfolge durchsuchen.

Ich habe es auf einem XP-Rechner ausgeführt (kompiliert mit VS2005:cl /O2) und auf einer Linux-Box (gcc –Os).Beide produzierten ähnliche Zeiten.Diese Zeiten werden in Millisekunden angegeben.Ich glaube, dass alle Schleifen laufen und nicht optimiert sind (sonst würde es „sofort“ laufen). 

*** Testing 20000 nodes
Total Ordered Time: 888.822899
Total Random Time: 2155.846268

Sind diese Zahlen sinnvoll?Liegt der Unterschied hauptsächlich an L1-Cache-Fehlern oder liegt noch etwas anderes vor?Es gibt 20.000^2 Speicherzugriffe und wenn jeder einzelne ein Cache-Fehler wäre, wären das etwa 3,2 Nanosekunden pro Fehler.Der XP (P4)-Rechner, auf dem ich getestet habe, hat 3,2 GHz und ich vermute (ich weiß es aber nicht), dass er über einen 32 KB L1-Cache und 512 KB L2 verfügt.Bei 20.000 Einträgen (80 KB) gehe ich davon aus, dass es keine nennenswerte Anzahl von L2-Fehlern gibt.Das wäre also (3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss.Das kommt mir hoch vor.Vielleicht ist es das nicht, oder vielleicht ist meine Mathematik schlecht.Ich habe versucht, Cache-Fehler mit VTune zu messen, aber ich habe einen BSOD erhalten.Und jetzt kann ich keine Verbindung zum Lizenzserver herstellen (grrrr). 

typedef struct stItem
{
   long     lData;
   //char     acPad[20];
} LIST_NODE;



#if defined( WIN32 )
void StartTimer( LONGLONG *pt1 )
{
   QueryPerformanceCounter( (LARGE_INTEGER*)pt1 );
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2, llFreq;

   QueryPerformanceCounter( (LARGE_INTEGER*)&t2 );
   QueryPerformanceFrequency( (LARGE_INTEGER*)&llFreq );
   *pdMS = ((double)( t2 - t1 ) / (double)llFreq) * 1000.0;
}
#else
// doesn't need 64-bit integer in this case
void StartTimer( LONGLONG *pt1 )
{
   // Just use clock(), this test doesn't need higher resolution
   *pt1 = clock();
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2 = clock();
   *pdMS = (double)( t2 - t1 ) / ( CLOCKS_PER_SEC / 1000 );
}
#endif



long longrand()
{
   #if defined( WIN32 )
   // Stupid cheesy way to make sure it is not just a 16-bit rand value
   return ( rand() << 16 ) | rand();
   #else
   return rand();
   #endif
}

// get random value in the given range
int randint( int m, int n )
{
   int ret = longrand() % ( n - m + 1 );
   return ret + m;
}

// I think I got this out of Programming Pearls (Bentley).
void ShuffleArray
(
   long *plShuffle,  // (O) return array of "randomly" ordered integers
   long lNumItems    // (I) length of array
)
{
   long i;
   long j;
   long t;

   for ( i = 0; i < lNumItems; i++ )
      plShuffle[i] = i;

   for ( i = 0; i < lNumItems; i++ )
      {
      j = randint( i, lNumItems - 1 );

      t = plShuffle[i];
      plShuffle[i] = plShuffle[j];
      plShuffle[j] = t;
      }
}



int main( int argc, char* argv[] )
{
   long          *plDataValues;
   LIST_NODE     *pstNodes;
   long          lNumItems = 20000;
   long          i, j;
   LONGLONG      t1;  // for timing
   double dms;

   if ( argc > 1 && atoi(argv[1]) > 0 )
      lNumItems = atoi( argv[1] );

   printf( "\n\n*** Testing %u nodes\n", lNumItems );

   srand( (unsigned int)time( 0 ));

   // allocate the nodes as one single chunk of memory
   pstNodes = (LIST_NODE*)malloc( lNumItems * sizeof( LIST_NODE ));
   assert( pstNodes != NULL );

   // Create an array that gives the access order for the nodes
   plDataValues = (long*)malloc( lNumItems * sizeof( long ));
   assert( plDataValues != NULL );

   // Access the data in order
   for ( i = 0; i < lNumItems; i++ )
      plDataValues[i] = i;

   StartTimer( &t1 );

   // Loop through and access the memory a bunch of times
   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Ordered Time: %f\n", dms );

   // now access the array positions in a "random" order
   ShuffleArray( plDataValues, lNumItems );

   StartTimer( &t1 );

   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Random Time: %f\n", dms );

}
War es hilfreich?

Lösung

Ich kann zwar keine Antwort darauf geben, ob die Zahlen sinnvoll sind oder nicht (ich kenne mich mit den Cache-Latenzen nicht gut aus, aber um es mal so zu sagen: ~10 Zyklen L1-Cache-Fehlschläge klingen ungefähr richtig), aber ich kann Ihnen eine Antwort geben Cachegrind als Tool, mit dem Sie die Unterschiede in der Cache-Leistung zwischen Ihren beiden Tests tatsächlich erkennen können.

Cachegrind ist ein Valgrind-Tool (das Framework, das den stets beliebten Memcheck unterstützt), das Cache- und Branch-Hits/Misses profiliert.Dadurch erhalten Sie eine Vorstellung davon, wie viele Cache-Treffer/-Fehler Sie tatsächlich in Ihrem Programm erhalten.

Andere Tipps

Hier ist ein Versuch, einen Einblick in die relativ Kosten des Cache-Misses analog Backe Chocolate Chip Cookies zu schaffen ...

Ihre Hände sind Ihre Register. Es dauert 1 Sekunde Schokoladenstückchen in den Teig fallen zu lassen.

Die Küchentheke ist der L1-Cache, zwölf mal langsamer als Register. Es dauert 12 x 1 = 12 Sekunden, um den Zähler zu Schritt, den Sack Walnüsse holen, und leeren Sie einige in Ihrem Hand.

Der Kühlschrank ist Ihre L2-Cache, viermal langsamer als L1. Es dauert 4 x 12 = 48 Sekunden, um den Kühlschrank zu gehen, öffnen Sie es, letzte Nacht Reste aus dem Weg zu bewegen, nehmen aus einem Karton Eier, öffnen Sie den Karton, legte drei Eier auf den Tresen und legte den Karton zurück in den Kühlschrank stellen.

Der Schrank ist Ihre L3-Cache, dreimal langsamer als L2. Es dauert 3 x 48 = 2 Minuten und 24 Sekunden drei Schritte zum Schrank zu nehmen, bücken, die Tür zu öffnen, Wurzel um die Backversorgung Zinn zu finden, die es aus dem Schrank extrahieren, es öffnen, gräbt das Backpulver zu finden, die es auf dem Tresen gelegt und das Chaos fegen Sie auf dem Boden verschüttet.

Und Hauptspeicher? Das ist der Laden an der Ecke, 5-mal langsamer als L3. Es dauert 5 x 2.24 = 12 Minuten, um Ihre Brieftasche zu finden, setzen auf Ihre Schuhe und Jacke, die Straße stürzen nach unten, einen Liter Milch, dash Hause packen , Ihre Schuhe und Jacke ausziehen, und zurück in die Küche bekommen.

Beachten Sie, dass alle diese Zugriffe sind konstante Komplexität - O (1) - aber die Unterschiede zwischen ihnen kann eine großen Auswirkungen auf die Leistung. Optimierung rein für Big-O Komplexität ist wie die Entscheidung, ob Schokoladenstückchen auf den Teig 1 zu einem Zeitpunkt oder 10 zu einem Zeitpunkt hinzuzufügen, aber vergessen, sie auf Ihrer Einkaufsliste zu setzen.

Moral der Geschichte: Ihr Gedächtnis Organisieren greift, so dass der CPU für Lebensmittel gehen so selten wie möglich

.

Zahlen wurden aus dem CPU Cache Flushing Fallacy genommen Blog-Post, die für einen bestimmten 2012-Ära Intel-Prozessor gibt an, dass die folgenden Bedingungen erfüllt ist:

  • registrieren access = 4 Befehle pro Zyklus
  • L1-Latenz = 3 Zyklen (12 x-Register)
  • L2-Latenz = 12 Zyklen (4 x L1, 48 x-Register)
  • L3 Latenz = 38 Zyklen (3 x L2, L1 12 x, 144 x-Register)
  • DRAM-Latenz = 65 ns = 195 Zyklen auf einem 3 GHz CPU (5 x L3, L2 15 x 60 x L1, 720 x-Register)

Die Galerie der Prozessor-Cache-Effekte auch auf gute Lektüre dieses Thema.

Mmmm, Cookies ...

3.2ns für eine L1-Cache-Miss ist durchaus plausibel. Zum Vergleich, bei einem bestimmten modernem Multi-Core-PowerPC-CPU, ein L1-Fehl über 40 Zyklen - ein wenig länger für einige Kerne als andere, je nachdem, wie weit sie sind aus der L2-Cache (ja wirklich) . Ein L2-Mißerfolg ist mindestens 600 Zyklen.

Cache ist alles in der Leistung; CPUs sind so viel schneller als Speicher jetzt, dass Sie fast die Optimierung für den Speicher-Bus anstelle des Kerns wirklich.

Nun ja, das sieht wie es in erster Linie L1 Cache-Misses sein wird.

10 Zyklen für eine L1-Cache-Miss klingen etwa vernünftig, wahrscheinlich ein wenig auf der unteren Seite.

Ein aus dem RAM gelesen wird in der Größenordnung von 100 s nehmen oder sogar 1000s sein (ist zu müde, um zu versuchen, die Mathematik zu tun, gerade jetzt;)) von Zyklen so seinen immer noch ein großen Sieg über die

Wenn Sie sich mit cachegrind planen, beachten Sie bitte, dass es ein Cache-Hit / Miss-Simulator ist nur. Es wird nicht immer korrekt. Zum Beispiel: Wenn Sie etwas Speicherplatz zugreifen, sagen 0x1234 in einer Schleife 1000 mal, cachegrind zeigen Ihnen immer, dass es nur eine Cache-Miss (der erste Zugang) war, auch wenn Sie so etwas wie:

CLFLUSH 0x1234 in der Schleife.

Auf x86, dies führt dazu, dass alle 1000 Cache-Misses.

Einige Zahlen für einen 3,4 GHz P4 von einem Lavalys Everest Lauf:

  • die L1 DCACHE ist 8K (Cache-Zeile 64 Byte)
  • L2 ist 512K
  • L1 holen Latenz ist 2 Zyklen
  • L2 holen Latenz über doppelt so hoch ist, was Sie sehen: 20 Zyklen

Mehr hier: http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt

(für die Latenzen Blick auf die unten auf der Seite)

Es ist schwierig, ohne viel mehr Tests sicher, etwas zu sagen, aber nach meiner Erfahrung, dass Skala von Differenz kann auf jeden Fall an dem CPU L1 und / oder L2-Cache zurückgeführt wird, insbesondere in einem Szenario mit randomisierten Zugang. Sie könnten wahrscheinlich, indem sichergestellt wird es noch schlimmer machen, dass jeder Zugang zumindest einiger Mindestabstand von den letzten.

Die einfachste Sache zu tun ist, um eine skalierte Fotografie des Ziel-CPU zu nehmen und physisch den Abstand zwischen dem Kern und dem Level-1-Cache messen. Multiplizieren Sie diese Distanz durch die Entfernung von Elektronen pro Sekunde in Kupfer reisen. Dann herauszufinden, wie viele Taktzyklen Sie in der gleichen Zeit haben. Das ist die Mindestanzahl der CPU-Zyklen Sie auf einer L1-Cache-Miss verschwenden werden.

Sie können auch auf die gleiche Weise die minimal Kosten von Abrufen von Daten aus dem RAM in Bezug auf die Anzahl der CPU-Zyklen verschwendeten trainieren. Vielleicht wundern.

Beachten Sie, dass hier auf jeden Fall, was Sie sehen hat etwas mit Cache-Misses zu tun (sei es L1 oder beide L1 und L2), denn normalerweise wird die Cache-Daten auf der Linie gleichen Cache herausziehen, sobald Sie etwas an diesem Cache zugreifen -Linie weniger Fahrten erfordern in dem RAM.

Doch was sind Sie wahrscheinlich auch zu sehen, ist die Tatsache, dass RAM (obwohl es nennt Random Access Memory) noch preferres linearen Speicherzugriff.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top