Cachemisses - relevanz

Hallo,
ich soll ein referat über Chachemisses halten.

Das ganze geht soweit ganz gut. Nur:

Wo haben Cachemisses heutzutage wirklich relevanz?
Gibt es Anwendungsgebiete bei denen es auf die Paar Bruchteile einer Sekunde tatsächlich ankommt?

Beispiele, Quellen, Diskussion erwünscht

Danke

miss me schrieb:

Wo haben Cachemisses heutzutage wirklich relevanz?
Gibt es Anwendungsgebiete bei denen es auf die Paar Bruchteile einer Sekunde tatsächlich ankommt?

Ich glaube dein Denkansatz ist falsch. Ein einzelner chache miss wird dir selten weh tun. Wichtig ist eher wie of ein cache miss auftritt. Sagen wir mal ein Programm/Datensatz/System hat eine cache miss Rate von 50%, also die Hälfte aller Anfragen gehen gut, die andere Hälfte nicht. Im letzteren Fall muss dann auf den nächst langsameren Speicher zugegriffen werden (je nachdem welchen cache man betrachtet). Dieser ist aber typischerweise deutlich langsamer, wir nehmen beispielsweise mal einen Faktor 10 an. Heisst, dass du in 50% der Fälle 10 mal mehr Laufzeit verbrätst als in den anderen 50%. Kannst dir das ja mal für unterschiedliche Zahlen durchdenken.

evtl. könnte man auch den ram messen, wenn man ein array erstellt und dann einmal sequenziell durchgeht und ein anderes mal zufällig auf die werte zugreift. evtl mit nem xorshift damits nicht ganz so zufällig aber trotzdem unique ist?

SeppJ

miss me schrieb:

Gibt es Anwendungsgebiete bei denen es auf die Paar Bruchteile einer Sekunde tatsächlich ankommt?

Alles wo eine CPU 100% Last hat.

Wie kann man das schöner formulieren?

Gibts da so einen "standardsatz" ?

Für dein Referat solltest du dir ein paar Zahlen holen:
- Wie lange dauert es, bis du etwas vom Internet lädtst, von USB?
- Wie lange dauert es ein Datum von Festplatte ins Register zu holen?
- Wie lange von RAM nach Register?
- Wie lange von Cache Level X nach Register?

Und, versuch dir diese Zahlen zu veranschaulichen in verständlichen Größenordnungen.

Damit wird dir erst einmal klar, wie toll und schnell - und leider viel zu klein - die Caches sind. Und: Oft kommt es nicht auf einen Bruchteil einer Sekunde an, das ist der falsche Ansatz. Aber mach die Operation eine Millionen Mal - oder läuft dein Programm nur ein Mal?

Die Beachtung des Caches und die Anpassungen von generellen Algorithmen an diese ist ein äußerst wichtiges Thema. Erst dadurch können viele Probleme in praktischer Zeit gelöst werden.

Deine Frage nach den Anwendungen ist mir nicht klar. Du kennst doch sicherlich die Top 500 Supercomputer-Liste. Nun überlege dir, wie sich Cache-Misses auswirken. 20 Jahre auf den nächsten Supercomputer warten oder lieber Cache-Misses verringern?

Oder ein wenig anders: Da dir der Nutzen vom Cache anscheinend nicht klar ist, rechne dir mal aus, dein PC hätte keinen Cache, also 100% misses . Wie langsam würde dieser werden?

hustbaer

Wo haben Cachemisses heutzutage wirklich relevanz?

Bei jedem Programm das ausreichend viele produziert.
Generell: wenn das Working-Set des Programms/Algorithmus grösser als der Cache ist.
(Umso schlimmer je höher der Cache-Level.)

Beispiel: Raycasting oder 2,5D Voxel-Rendering mit grossen Maps. Die Map passt niemals in den Speicher, und das "Durschiessen" von Strahlen ist - ohne Optimierungen - sehr Cache-unfreundlich. Wenn man da nicht darauf achtet die Map "Cache-freundlich" abzulegen fühlt man sich schnell in die Computersteinzeit zurückversetzt.

Oder, viel einfacheres Beispiel: Bildbearbeitung.

SeppJ

Falls du einen ausreichend alten Rechner zur Verfügung hast: Früher^* konnte man den CPU-Cache noch im BIOS abschalten. Da kannst du dann ja mal die Unterschiede für verschiedene Anwendungen mit und ohne CPU-Cache ansehen.

^*: Wenn du jetzt in der Schule bist, wirst du wohl einen älteren Verwandten fragen müssen. Ich rede von Computern aus der Zeit bis ~1996.

C++ Forumbot

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Themen rund um den PC in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

TGGC

Cache Misses sind in einem normalen PCs das ungefaher langsamste was er so macht. Sie werden immer relevanter, da die Speicheranbindungen langsamer wachsen als alles andere.

SeppJ schrieb:

miss me schrieb:

Gibt es Anwendungsgebiete bei denen es auf die Paar Bruchteile einer Sekunde tatsächlich ankommt?

Alles wo eine CPU 100% Last hat.

Die CPU hat so gut wie nie 100% Last: die Cache Misses entscheiden, ob sie 5% oder 50% Last hat.

rüdiger

Wo haben Cachemisses heutzutage wirklich relevanz?

Die Relevanz ist heutzutage größer denn je. Das liegt nämlich daran, dass die Geschwindigkeit der CPUs drastisch wächst. Aber die Anbindung zum RAM nicht schnell genug nachkommt. Das heißt das Zugriffe zum RAM proportional teurer werden und daher wird es relevanter, dass man sich besser darum kümmert, dass die wichtigen Daten in den Cache passen.

siehe zB http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf

krümelkacker

TGGC schrieb:

SeppJ schrieb:

miss me schrieb:

Gibt es Anwendungsgebiete bei denen es auf die Paar Bruchteile einer Sekunde tatsächlich ankommt?

Alles wo eine CPU 100% Last hat.

Die CPU hat so gut wie nie 100% Last: die Cache Misses entscheiden, ob sie 5% oder 50% Last hat.

Ersetze CPU durch CPU-Kern und es sollte passen. Wenn es etwas zu tun gibt und der Speicher kommt nicht hinterher -- was heute viel schlimmer ist als früher (*) -- dann wartet der CPU-Kern und es wird (zumindest bei mir unter Linux) als Auslastung gewertet.

(* Heute haben wir sauschnelle CPUs und hohe Latenzen zwischen CPU<->RAM )

hustbaer

@krümelkacker:
Die Latenzen sind heute geringer als früher, nur dass die CPUs einfach mehr zugelegt haben als die RAM-Geschwindigkeit.

Aber dafür sind auch die Caches größer und es gibt idR auch mehr cache levels als früher. Dafür wiederum sind die Datenmengen heute auch um ein vielfaches größer. Hmmm...

otze

Bei uns gab es letztens ein nettes Beispiel für Cachemisses:

Wir hatten ein Programm, dass für einen Lauf ca 40 Sekunden brauchte. Da wir Quadcore Systeme hatten, dachten wir, dass wir 2 Instanzen davon parallel laufen lassen könnten. Falsch gedacht. Die Programme hatten dann eine Ausführungszeit von ca 90 Sekunden.

Warum? beide Programme waren sehr Datenintensiv. Sie haben also immer eine Menge Daten in den Cache gezogen mit denen sie dann weiter gerechnet haben. Nun bedeutet 4 Kerne nicht auch 4 Caches. Effektiv haben sich damit die beiden parallel laufenden Prozesse gegenseitig den Cache zerschossen und fleissig Cachemisses produziert.

Fazit: 2 Programme nacheinander auf Single Core können schneller sein als 2 Programme parallel auf Multicore, wenn das Caching dazwischen funkt.

rüdiger

@otze
Als 2002 oder 2003 die ersten Multicores rauskamen (teure POWER-Maschinen von IBM), waren die ganzen Benchmarks mit nur einem aktivierten Kern schneller. Aus dem gleichen Grund: Ein Kern mit größerem Cache hatte eine bessere Performance als mehrere Kerne auf einem kleineren Cache.

Tim schrieb:

Aber dafür sind auch die Caches größer und es gibt idR auch mehr cache levels als früher. Dafür wiederum sind die Datenmengen heute auch um ein vielfaches größer. Hmmm...

Deswegen ist das Datenlayout heute wichtig und das typische OO-Modell ist da nicht unbedingt gut. Aber siehe die verlinkten Folien.

hustbaer

otze schrieb:

Warum? beide Programme waren sehr Datenintensiv. Sie haben also immer eine Menge Daten in den Cache gezogen mit denen sie dann weiter gerechnet haben. Nun bedeutet 4 Kerne nicht auch 4 Caches. Effektiv haben sich damit die beiden parallel laufenden Prozesse gegenseitig den Cache zerschossen und fleissig Cachemisses produziert.

Bist du sicher? Hast du das nen Thread-Profiler ermitteln lassen, oder ist das einfach nur ne Schätzung?

Es gibt nämlich zumindest einen anderen Effekt, der da kräftig mit reinspielen kann, und den ich für den wahrscheinlicheren Übeltäter halte: False Sharing

Kann mal einer ein Codebeispiel zeigen, bei dem man das mit den Cachemisses wirklich sieht. Ich hab was versucht, aber die 2. Version ist immer langsamer, egal wie groß das Array ist. Oder ist der Cache nur ein paar hundert Byte groß?

int main( int argc, char**)
{
	std::cout<<argc<<"\n";
#define MM
	const int M = 40000000;
	const size_t N = 100*argc;
	std::vector<int> v(N);
	for(size_t i = 0; i<N; i++)
	{
		v[i]=1;
	}
#ifdef MMM
	size_t sum=0;
	clock_t start = clock();
	for(int m = 0; m<M; m++)
	{
		for(size_t i = 0; i<N; i+=2 )
		{
			sum += v[i] + v[i+1];
		}
	}
	clock_t end = clock();
	std::cout << "1. time: " << end-start << " sum: " <<sum << "\n";
#else
	size_t sum = 0;
	const size_t N2 = N/2; 
	clock_t start = clock();
	for(int m = 0; m<M; m++)
	{
		for(size_t i = 0; i<N2; i++ )
		{
			sum += v[i] + v[N2+i];
			//sum += v[i] + v[N-i-1];
		}
	}
	clock_t end = clock();
	std::cout << "2. time: " << end-start << " sum: " <<sum << "\n";
#endif
}

_--

beim cache geht es meines wissens nicht so um die größe das wäre dann eher die cacheline. beim cache kommt es darauf an, dass man häufig auf ein und die selbe adresse(n) zugreift. bsp.

10 mal zugriff auf 10 unterschiedliche adressen vs. zugriff auf 100 unterschiedliche adressen (um das richtig zu messen sollte jede adresse auf einer eigenen cacheline liegen)

otze

der beste Weg das zu zeigen, ist mit unterschiedlichen Schrittlängen durch den Speicher zu gehen.

step = 1;//16 sollte der erste Performance-Breakdown sein
for(size_t i=0;i < N;i+=step){
//mach was mit v[i]
}