Chache-Miss: Software-Prefetching scheint nicht zu funktionieren

[loks]

Du greifst zufällig auf Bereiche deines Speichers zu die nahezu nie im gleichen Speicherblock liegen, daher bringt der L2 Cache nix. Dabei macht es auch keinen Unterschied ob Du einen Datensatz nun mit Prefetch holst um ihn dann einmal aus dem Cache auszulesen. Caches bringen nur unter 2 Umständen etwas:

1. Du greifst mehrfach hintereinander auf den gleichen Speicher zu und dieser ist schon im Cache: Bingo.
2. Du greifst auf zwei benachbarte Speicherbereiche zu und der zweite Bereich wurde gemeinsam mit dem ersten bereits in den Cache geladen: Ebenfalls Bingo.

So wie Du aber Deinen Zugriff auf Deine Daten beschreibst werden Fall 1 und Fall 2 ehr die Ausnahmen sein und daher hast Du leider Fall 3:

3. Jeder Zugriff geht auf einen Speicherbereich der nicht im Cache ist, also Cache-Miss und reload auf Hauptspeicher. Nach meiner einschätzung ist es dabei egal ob Du jetzt per manuellem Prefetch den Speicehrblock saugst oder ob es durch den Cache-Miss passiert, das eigendliche Problem ist das das nahezu jeder Deiner Zugriffe ein Nachladen aus dem Hauptspeicher erfordert.

Ich würde sogar erwarten das durch manuellen Prefetch das Programm deswegen langsamer wird weil Fall 1 und 2 mit einer gewissen statistischen Wahrscheinlichkeit passieren werden und Du in diesen Fällen trotzdem ein Nachladen erzwingst.

Ohne das Problem zu kennen... Mal ne potentielle Schnapsidee: das Array zufällig umsortieren und dann linear auslesen ist im Grunde ebenso zufällig wie ein zufälliger Zugriff auf unterschiedliche Indizes. Also sowas wie:

Eintragungen per Zufall umsortieren, dann linear vom ersten bis zum letzten bearbeiten, dann wiede rneu umsortieren und wieder linear abarbeiten...

Oder schanpsidee 2: Feststellen wieviele Array-Elemenrte gleichzeitig in einen cache-Block passen, sagen wir mal es sind 5. Dann immer zufällig einen Block von 5 Eintragungen anspringen, aber 5 davon linear abarbeiten... Oder imemr zwei... oder sowas.

[hustbaer]

Ich tippe mal darauf, dass es nix bringt, weil deine CPU den Code auch ohne manuelles Prefetching bereits "perfekt" reordert.

20% Unterschied bei random vs. sequentiell ist auch nicht viel. Das ist eher ganz ganz wenig.

3. Jeder Zugriff geht auf einen Speicherbereich der nicht im Cache ist, also Cache-Miss und reload auf Hauptspeicher. Nach meiner einschätzung ist es dabei egal ob Du jetzt per manuellem Prefetch den Speicehrblock saugst oder ob es durch den Cache-Miss passiert, das eigendliche Problem ist das das nahezu jeder Deiner Zugriffe ein Nachladen aus dem Hauptspeicher erfordert.

Es ist dann nicht egal, wenn die CPU heia gehen muss während sie auf die Daten wartet. Kann sie allerdings reordern, dann macht es nix aus, oder nicht so viel.

[Gast]

hustbaer schrieb:

20% Unterschied bei Randum vs. sequentiell ist auch nicht viel. Das ist eher ganz ganz wenig.

Das kam mir (auch wenn ich solche Probleme nicht wirklich kenne) auch eher wenig vor.

[SeppJ]

Tim schrieb:

hustbaer schrieb:

20% Unterschied bei Randum vs. sequentiell ist auch nicht viel. Das ist eher ganz ganz wenig.

Das kam mir (auch wenn ich solche Probleme nicht wirklich kenne) auch eher wenig vor.

Wenig? Ich fände das fantastisch, weil es mir Tage und Wochen sparen würde. Aber ein paar Kommentare zu den Antworten (die ich allesamt sehr gut finde):

@loks: Vielen Dank für die Erklärung meiner Beobachtungen. Nun wird es mir klar.

Zur zufällige Umsortierung und dann linear Durchgehen: Leider ist das nicht das gleiche, da man dann statt Ziehen mit Zurücklegen ein Ziehen ohne Zurücklegen hätte, was mir das Ergebnis kaputt machen würde. Ich habe auch schon ein paar Algorithmen ausprobiert, die mir die Daten im Array grob so sortieren, dass Werte die miteinander etwas zu tun haben auch beieinander stehen. Aber das hat keine Verbesserung gebracht, da es das Ursprungsproblem nicht löst.

SeppJ: Was macht "funktion" denn grob? Bzw. inwiefern ist die Funktion von der zufälligen Reihenfolge der Zufallszahlen abhängig?

Sie führt dann relativ teure Berechnungen auf dem Array aus, anscheinend ca. 80% der Programmlaufzeit. Dabei werden auch andere Werte aus dem Array verwendet, aber das scheint keine Misses zu geben. Außerdem wird das gezogene Element verändert. Die Zufälligkeit ist drin, da es sich um ein statistisches Ergebnis handelt, würde ich linear durchgehen hätte ich einen statistischen Fehler im Ergebnis. Ich habe auch schon daran gedacht, diesen wieder rauszurechnen, aber das würde, wenn ich das richtig sehe, deutlich mehr kosten als die Berechnung des Ergebnisses an sich. Ich müsste daher die Geschwindigkeit durch lineares Durchgehen schon mehr als Verdoppeln, damit sich das lohnt.

Aber sie sind doch noch so zufällig, dass keine fertige Liste infrage kommt? Bzw. hast du mal probiert einfach alle Zufallszahlen vor der Schleife zu erzeugen?

Nun, das ist ziemlich genau das was ich hier versucht habe. Ich hatte die Werte auch in ein separates Array vorladen können, aber dann hätte ich beim Erstellen dieses Arrays die Misses.

[ipsec]

Du könntest vorher ein Array mit Zufallszahlen erstellen und dieses sortieren, bevor du dessen Elemente als Indizes nimmst. Durch das Sortieren wird das zwar erstmal eher länger dauern, möglicherweise kannst du aber das Erstellen des Indizesarrays in einen performanceunkritischen Bereich verlagern.

[SeppJ]

ipsec schrieb:

Du könntest vorher ein Array mit Zufallszahlen erstellen und dieses sortieren, bevor du dessen Elemente als Indizes nimmst. Durch das Sortieren wird das zwar erstmal eher länger dauern, möglicherweise kannst du aber das Erstellen des Indizesarrays in einen performanceunkritischen Bereich verlagern.

Leider nein, denn sortierte Zufallszahlen sind nicht mehr zufällig . Da an den Elementen etwas geändert wird, ist die Reihenfolge schon wichtig. Ich (und im Prinzip auch andere, klügere Kopfe) haben schon über dieses Problem nachgedacht. Um den Zufall kommt man leider nicht herum. Mein Plan ist nun eher eine technische Lösung um die Auswirkungen zu mildern.

[hustbaer]

Mach mal einen Vergleich mit folgendem Code:

for (sehr; sehr; oft) 
 { 
   int r = zufallszahl(); 
//   funktion(datenfeld[r]); 
   datenfeld[r]++; 
 }

Würde mich nicht wundern, wenn das ca. gleich lange braucht, wie mit der eigentlichen Berechnung.
Falls das stimmt, bist du bereits am Limit des L3 Cache (bzw. des RAMs, falls das System keinen L3 Cache hat).

In dem Fall könnte man wohl am ehesten bei der Hardware noch was rausholen.
Ein i7 ist z.B. deutlich viel flotter Speicherzugriffen als ein Core 2.
Bzw. eventuell ein Xeon X5690 mit 12 MB L3 Cache.

SeppJ schrieb:

Tim schrieb:

hustbaer schrieb:

20% Unterschied bei Randum vs. sequentiell ist auch nicht viel. Das ist eher ganz ganz wenig.

Das kam mir (auch wenn ich solche Probleme nicht wirklich kenne) auch eher wenig vor.

Wenig? Ich fände das fantastisch, weil es mir Tage und Wochen sparen würde.

Wenig im Sinn von: wenn die CPU wirklich Däumchen drehen würde während sie auf die Speicherzugriffe wartet, dann wäre der Unterschied vermutlich viel grösser.

[rapso]

SeppJ schrieb:

#include <xmmintrin.h>
#define PREFETCH(addr,nrOfBytesAhead) _mm_prefetch(((char *)(addr))+nrOfBytesAhead,_MM_HINT_T0)

int next = zufallszahl();
int nextnext = zufallszahl();

for (sehr; sehr; oft)
{
  r = next;
  next = nextnext;
  nextnext = zufallszahl();
  PREFETCH(&datenfeld[nextnext], sizeof(datenfeldelement));
  funktion(datenfeld[r]);
}

Aber das bringt überhaupt gar nichts! Null!

sorgt das "(addr))+nrOfBytesAhead" nicht dafuer, dass du den prefetch hinter dem element machst, auf das zu zugreifen willst?

Ich könnte ja verstehen, dass es langsamer wird, wegen des komplexeren Porgrammflusses. Aber der Profiler sagt mir, dass die Cache-Misses immer noch das Problem sind und sie treten immer noch an der gleichen Stelle auf! Ich habe es auch mit bis zu 4 Ebenen von next probiert und mit unterschiedlichen Hints. Compiler ist der Intel-Compiler, sollte aber auch für andere Compiler gehen. Zielplattform x86_64. Größe eines Datenfeldelementes ist 72 Bytes.

72 ist ziemlich cache unfreundlich, dafuer muss pro zugriff 128byte geladen werden, falls du pech mit dem alignment hast, vielleicht sogar 192bytes.
Ich vermute, dass du nicht L2 bound bist wegen dem random zugriff an sich, sondern wegen der bandbreite die du verbrauchst. pruef doch mal nach wieviel loops/s du hast und wieviel MB/s das ist (cacheline, also *128byte).

Muss ich eventuell noch mehr Ebenen als 4 vorspeichern? Kann der x86_64 diese Anweisung möglicherweise gar nicht? Ich habe ein paar Prefetchmakros gefunden die nur auf Itanium gehen, aber diese hier scheinen mir allgemeingültig zu sein. Ich will vor allem wissen, ob das im Prinzip der richtige Weg ist, den ich hier verfolge.

da ein ram zugriff auf PC in etwa 100 cycles dauert, musst du soviel prefetchen, dass du vom code her 100cycles hinterher laeufst.

@loks
wenn es wirklich nur die zwei faelle gebe, dann wuerde ein software prefetch nie etwas bringen, denn
zu 1. das waere nach dem ersten zugriff der fall, auch ohne prefetch
zu 2. das waere nach dem ersten zugriff auf der cacheline der fall, auch ohne prefetch

prefetch ist exact fuer den fall dass 1 und 2 nicht zutrifft. Ram zugriffe werden in der priority behandelt
1. instruction cache miss
2. data cache miss
3. prefetch

prefetch versteckt also nur die latenz von cache misses wenn du noch genug bandbreite uebrig hast.

task list waere
1. align dein array auf 64byte
2. bringt die elementgroesse auf 64, dazu kannst du entweder die daten dichter packen, oder selten benutzte daten in einen externen speicherbereich auslagern.
3.

#define PREFETCH(addr,nrOfBytesAhead) _mm_prefetch(((char *)(addr)),_MM_HINT_T0)\
_mm_prefetch(((char *)(addr))+64,_MM_HINT_T0)

4. notfalls poste hier deinen code + test case und das ganze forum wirft sich auf die competition

ps.schoen dass mal jemand optimiert indem er vorher richtig profiled

[hmmmmm]

Gibt es sicher überhaupt keine Möglichkeit mehr, denn Algorithmus umzubauen? Kann man den Algorithmus parallelisieren?

[otze]

@SeppJ

nur mal aus interesse: mit welcher Software machst du das Profiling? Würde auch gerne mal sowas bei meiner Programmbibliothek ausprobeiren, weiß aber nicht, was dafür unter Linux so eine tolle Software wäre (ich vermute einfach mal, dass du linux verwendest). Bislang kenne ich nur so Sachen die anzeigen, wie lang man in einer Funktion bleibt, aber nicht warum...