Multithreading, volatile, Cache usw.

Michael E.

So, hab mich jetzt selbst mal ein bisschen informiert. Bei der Verknüpfung der Byteadressen mit ihrer Bedeutung dürfte es tatsächlich keine Probleme geben, weil sich darum die MMU kümmert. Dafür ist bei Shared Caches die Latenz viel größer. Siehe z.B. http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec16.html oder http://realworldtech.com/page.cfm?ArticleID=RWT101405234615&p=2

jenz

Ah, danke.

Du meinst das hier:
Latency. Switch logic will now need to be interposed between the processor and the cache, adding latency to each reference.
Oder?

Das verstehe ich so, dass immer nur ein Prozessor mit dem Cache "verbunden" ist.
Man könnte doch auch einfach x-Leitungen legen und jeder Prozessor kann einfach zugreifen.
Das würde auch gleich das "Bandwidth"-Problem lösen.

Das hier
"Destructive interference—the converse of overlapping working sets"
haben wir ja schon gelöst

Wahrscheinlich scheitert es dann aber an den ganzen Leitungen und dem verfügbaren Platz und der nötigen Länge der Leitung, wodurch es dann wieder langsamer wird.

PhilippHToner

Es gibt viele Cachearten, aber der große Vorteil ist der konstante Speicherzugriff auf den Cache. Manche Caches lösen lediglich den virtuellen Adressraum zur physikalischen Adresse auf (z.B Software: Paging des Betriebsystems), andere speichern Daten (z.B Hardwarecache). Deine Idee, den Cache zu sharen bringt einfach das Problem mit sich, dass der Zugriff auf gecachte Daten synchronisiert werden muss und länger braucht. Der besteht aus sehr vielen gleichen E-Schaltkreisen die echt-parallel zum Ergebnis kommen: "Hier ist der Wert" bzw. "Keiner hat den Wert". worst-case, eine echte RAM Anfrage, die je nach RAM-Timings (wobei man hier nicht 1:1 die Timings auswerten kann) 10 oder mehr Zyklen braucht. Und selbst da darf man nicht zu naiv werden. Auf primitiver Assemblerebene ist die Nebenläufigkeit von so vielen Anweisungen so hoch, dass eine RAM Anfrage geschickt wird und dann wird i=5*3, m=999/34 oder sonst was ausgeführt und irgendwann kommt der erfolgreiche Fetch. Schau dir mal eine Pipeline an. Was der L1,2,3 Cache macht (inklusiv vs. exklusiv). Was direkte Abbildung, assoziativ und mengenassoziativ bedeutet. Caches halten ihre Daten nach Hit-Rates etc. es ist verdammt gut optimiert!

Ich denke dass die Halbleiterindustrie sich täglich etliche Male den Kopf zerbrochen und nachgemessen hat und so ist es am schnellsten. Und wenn du meist, dass sich da noch was rausholen lässt, dann schau die Mal virtuelle Speicheradressen und Paging an. Das ist alles auf OS-Ebene fern von Hardware und es wird geschaut, wie optimiert wird.

jenz

PhilippHToner schrieb:

Deine Idee, den Cache zu sharen bringt einfach das Problem mit sich, dass der Zugriff auf gecachte Daten synchronisiert werden muss und länger braucht.

was genau muss sychronisiert werden?
bzw. wieso muss das vom cache synchronisiert werden?

wenn auf gleiche daten zugegriffen werden soll, dann muss das doch von der software synchronisiert werden.

PhilippHToner

jenz schrieb:

Man könnte doch auch einfach x-Leitungen legen und jeder Prozessor kann einfach zugreifen.

Man betone "einfach". Also sei ma ned böse, aber du hast ja mal gar keine Vorstellung von dem Inhalt einer CPU, geschweige denn, wass das Ding in kürzester Zeit verrichtet! Lass das Thema lieber bevor, du dich hier mehr blamierst!

jenz

naja, es geht nur um speicher bzw. cache zugriff.

klar kann x nicht beliebig groß werden.
aber x = 4 sollte das doch machbar sein.

und ich glaube, ich habe mehr ahnung als du vermutest.

vermutungen müssen wir aber nicht anstellen, ich will das doch nur mal durchdiskutieren und verstehen, wo die grenzen liegen bzw. wo die grenzen herkommen.

PhilippHToner

jenz schrieb:

PhilippHToner schrieb:

Deine Idee, den Cache zu sharen bringt einfach das Problem mit sich, dass der Zugriff auf gecachte Daten synchronisiert werden muss und länger braucht.

was genau muss sychronisiert werden?
bzw. wieso muss das vom cache synchronisiert werden?

wenn auf gleiche daten zugegriffen werden soll, dann muss das doch von der software synchronisiert werden.

Stell Dir das so vor. Im Gegensatz zu Intel und AMD sind wird kleine Sesselfurzer, die einfach coden. Wir machen uns nicht über alles Sachen Gedanken, die Architektur spezifisch sind.

Hier ein MUsterbeispiel, dass 100000000 läuft und einmal abstürzt mit Pseudecode

RAM g = 0 // befindet sich im RAM

Thread A führt Block A aus
Thread B führt Block B aus

Block A
Warte 10 Sekunden
g = 5
Blockende

Block B
Warte 20 Sekunden

// Was für Wert ist in g?

Blockende

Schau die den Code an. Ich synchronisiere hier über die Zeit, aber was ist, wenn g noch im Cache ist und das g im RAM noch wie vor 0 ist!?!?!

Deshalb Synchronisierungsverfahren, die die Cores dazu bewegt ihren Abgleich bzgl. RAM durchzuführen!
DIe besten Sync-Verfahren dich ich gesehen habe war sowas wie:

if(millisecs % Threadanzahl == threadid)
// dann darf ich was machen
endif;

NEVER!

Michael E.

PhilippHToner schrieb:

Im Gegensatz zu Intel und AMD sind wird kleine Sesselfurzer, die einfach coden. Wir machen uns nicht über alles Sachen Gedanken, die Architektur spezifisch sind.

Trotzdem wird man sich doch wohl mal Gedanken dazu machen dürfen, oder?

Dein anschließendes Beispiel hat nichts mit Shared Caches zu tun.

PhilippHToner

jenz schrieb:

was genau muss sychronisiert werden?
bzw. wieso muss das vom cache synchronisiert werden?

Ja weil du noch Register hast!
Register <-> Cache <-> RAM

Prozessor P1 holt sich aus dem gemeinsamen Cache die Daten D1 in Register R1.
Prozessor P1 rechnet: R1 = R1 + R1
Prozessor P2 holt sich aus dem gemeinsamen Cache die Daten D1, die eigentlich D1 = R1 entsprechen müssten, tun sie aber nicht, weil im Register von P1.

Wenn du in c++ im selben Thread mit der selben Variable rechnest bekommst du versprochen, dass du mit dem richtigen Wert arbeitest. Dir wird doch ständig verschleiert woher deine Daten kommen. Es kann (unwahrscheinlich, aber theoretisch) sein, dass dein "int i" auf der Festplatte flackt! Weil du es nie gebraucht hast und dein RAM so zugemüllt ist, dass das OS i einfach auf die Festplatte gespeichert hat. Es ist jetzt sehr übertrieben, aber überleg mal, was wir eigentlich für ein gechilltes Leben haben! Das OS supported uns und die CPU supported das OS.

PhilippHToner

Michael E. schrieb:

PhilippHToner schrieb:

Im Gegensatz zu Intel und AMD sind wird kleine Sesselfurzer, die einfach coden. Wir machen uns nicht über alles Sachen Gedanken, die Architektur spezifisch sind.

Trotzdem wird man sich doch wohl mal Gedanken dazu machen dürfen, oder?

Dein anschließendes Beispiel hat nichts mit Shared Caches zu tun.

Klar kann man sich Gedanken machen, aber es haben jetzt 100 Leute gesagt, dass auf der low-low-low-Levelebene nicht mehr synchronisiert werden soll, weil das der Flaschenhals wird! Schaut Euch eure Programm an. Die meisten Aufgaben sind so beschränkt auf ein paar Daten. Und deshalb die Aufteilung in zeitliche Lokalität und räumliche Lokalität. Wenn ich schon länger etwas nicht mehr brauche, dann sinkt mit zunehmender Zeit, dass ich es wieder brauche (HitRates). Beim Abarbeiten entsteht die zeitliche Lokalität und beim allokieren meistens die räumliche Lokalität. Es ist aber theoretisch möglich, dass der Cache kein bisschen Zeit einspart, aber diesem Problem versucht auch der Compiler vorzubeugen und schiebt ähnliche Sachen zusammen!

Speicher allgemein muss bei einem Zugriff von mehreren Parteien mit den erforderlichen Maßnahmen synchronisiert werden! Es ist Wurst ob über das Netzwerk eine Datei geöffnet geändert und gespeichert wird, ob im Arbeitsspeicher, im Cache oder bei den Registern! Macht Euch einfach Gedanken wie ihr gewährleistet, dass der Programmierer, wenn er mit int i arbeitet immer sein richtiges i hat, auch wenn es nach China gepaged wurde, weil Deutschland keinen Speicherplatz mehr hat. Es gibt nur eine Hand voll atomarer Codepassagen (locken und unlocken von threadsync) und der Rest ist nie atomar: ++i auch nicht!!!!

jenz

PhilippHToner schrieb:

Ja weil du noch Register hast!
Register <-> Cache <-> RAM

Prozessor P1 holt sich aus dem gemeinsamen Cache die Daten D1 in Register R1.
Prozessor P1 rechnet: R1 = R1 + R1
Prozessor P2 holt sich aus dem gemeinsamen Cache die Daten D1, die eigentlich D1 = R1 entsprechen müssten, tun sie aber nicht, weil im Register von P1.

Wenn du in c++ im selben Thread mit der selben Variable rechnest bekommst du versprochen, dass du mit dem richtigen Wert arbeitest. Dir wird doch ständig verschleiert woher deine Daten kommen. Es kann (unwahrscheinlich, aber theoretisch) sein, dass dein "int i" auf der Festplatte flackt! Weil du es nie gebraucht hast und dein RAM so zugemüllt ist, dass das OS i einfach auf die Festplatte gespeichert hat. Es ist jetzt sehr übertrieben, aber überleg mal, was wir eigentlich für ein gechilltes Leben haben! Das OS supported uns und die CPU supported das OS.

Ja, das ist ja auch klar.

Wir sind aber bei einem ganz anderen Problem bzw. Fragestellung:
"Sind mehrere L1 Caches sinnvoller als ein gemeinsamer, bzw. warum nimmt man nicht einen gemeinsamen."

jenz

hustbaer

@jenz
Du stellst dir das alles viel zu einfach vor.
Fakt ist, dass ein Cache auf den 2 oder mehr Cores gleichzeitig zugreifen können komplizierter und langsamer ist als ein Cache auf den nur eine CPU zugreifen kann.

Deswegen baut man CPUs die für jeden Core einen eigenen L1 und L2 Cache haben, und schaltet dann erst einen gemeinsamen L3 Cache dahinter.
(Zumindest die aktuellen Intel und AMD CPUs machen das genau so)

was genau muss sychronisiert werden?
bzw. wieso muss das vom cache synchronisiert werden?

wenn auf gleiche daten zugegriffen werden soll, dann muss das doch von der software synchronisiert werden.

Ich wiederhole mich nicht gerne, aber... du stellst dir das alles viel zu einfach vor.

PhilippHToner

jenz schrieb:

Ja, das ist ja auch klar.

Wir sind aber bei einem ganz anderen Problem bzw. Fragestellung:
"Sind mehrere L1 Caches sinnvoller als ein gemeinsamer, bzw. warum nimmt man nicht einen gemeinsamen."

jenz

Is des jetzt so schwer? Google mal: Datenkonsistenz. Wie willst du eine Datenkonsistenz in einem gemeinsamen Cache realisieren ...
// edit Zusatz: bei gleicher Geschwindigkeit!

jenz

Naja,
in dem schönen link von Michael E.
http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec16.html
steht jedenfalls, dass man das für SingleChipMultiProzessoren genau so machen kann und anscheinend auch solche Architekturen existieren.
Also einen gemeinsamen L1 Cache.

INTEL hat aber zum Beispiel nur den L3 geshared.

jenz

PhilippHToner

Hier lesen: http://www.elektronik-kompendium.de/sites/com/0309291.htm

DIe Frage die Ihr euch stellen könnt ist auch, warum hat der L1 Cache N kB und nicht 2*N kB? Weil einfach alles sehr kompakt ist! Es gibt platztechnische Probleme. Es gibt noch 100 Probleme, die vielleicht Grund sind, warum es nicht so ist.

Wie viel Strecke legt der Strom bei 3,6 GHz bei 70°C in Kupfer zurück, zzgl. der "Gatter". Angenommen er fließt Lichtgeschw. 0,3Gm/s (300 000km/s), würde er 8cm weit kommen.
Ich befasse zur Zeit mit OpenCL und da geht es um das Thema, wieviel Zukunft unsere Multicore CPUs haben. Nämlich 0! Mit zunehmender Frequenz steigt die Hitzeentwicklung (nicht nur linear). Würde man das Problem der Hitze lösen können, würde man an die physikalische Grenze der elektronische Flussgeschwindigkeit kommen, in Kombination der Schaltzeiten von "Gatter" uvm... also Manycore-ARchitekturen werden kommen und spätestens da, werden wir uns um mehrere SPeicherebenen kümmern dürfen, wie es in OpenCL bereits der Fall ist: Register, lokaler Speicher, konstanter Speicher (vergleichbar L3), globaler Speicher (RAM). Man sagt, dass der globale Speicher mit Faktor 100 langsamer arbeitet als der lokale. Bei solch einem Thema der Speicherverwaltung, ist es sinnvoll, dass der Programmierer Hirn investieren sollte, damit nicht unnötige Sachen passieren, aber synchronisieren darf er den lokalen Speicher und den globalen Speicher.

Reicht das jetzt als Feeling, dass hier keine zusätzlichen Leiterbahnen verbaut werden können, was auch immer der Grund ist.

knivil

1.) I$ braucht nicht geshared sein.
2.) D$ soll nicht geshared sein, da mehrere Prozesse unterschiedliche Daten verarbeiten. Warum soll mein Videoplayer den gleichen Cache benutzen, wie mein Videospiel, dass nebenbei laeuft? Also konsistente Caches bringen nur in wenigen Faellen etwas, z.B. Supercomputing. Dafuer gibts dann von Intel Larrabee/Knights Corner (ka. wie es final heissen wird). Wobei geben zuviel gesagt ist, die Entwicklung dauert offiziell schon 5 Jahre, inoffiziell ...

Wenn alle Prozessoren auf dem selben Cache arbeiten, dann sind die Daten doch automatisch konsistent.

Die Schwierigkeiten ergeben sich bei der Realisierung. Multithreading ist normalerweise so gestrikt, dass eben nicht auf den gleichen Daten gearbeitet wird.

Klar wird der Cache immer dicker, wenn er mehr Leitungen hat, aber das ist doch kein prinzipielles Problem.

Doch!

Warum sollte der gleichzeitige parallele Zugriff auf einen gemeinsamen Cache so problematisch sein? Also rein vom Prinzip her stelle ich mir dir Frage.

Weil es immernoch zu Race Conditions kommen kann.

jenz

PhilippHToner schrieb:

Is des jetzt so schwer? Google mal: Datenkonsistenz. Wie willst du eine Datenkonsistenz in einem gemeinsamen Cache realisieren ...
// edit Zusatz: bei gleicher Geschwindigkeit!

Ach komm, darum geht es doch gar nicht.

Wenn alle Prozessoren auf dem selben Cache arbeiten, dann sind die Daten doch automatisch konsistent. Also sehen wir mal von den Registerwerten ab.

Die Schwierigkeit ergibt sich doch eben erst bei mehreren getrennten Caches.

Und was ich eben noch nicht verstehe:
Warum sollte der gleichzeitige parallele Zugriff auf einen gemeinsamen Cache so problematisch sein? Also rein vom Prinzip her stelle ich mir dir Frage.

Klar wird der Cache immer dicker, wenn er mehr Leitungen hat, aber das ist doch kein prinzipielles Problem.

PhilippHToner

Noch was:

wie es gelöst wurde ist es genau richtig. Ein Problem zu parallelisieren setzt Nebenläufigkeit voraus. Dieses "Nebenläufige" landet im L1 Cache und da es Nebenläufig ist, besteht kein Bedarf an Shared Cache. Danach kommt der Synchronisationspunkt.

Alle Threads fangen gleichzeitig an, aber eine blockiert kurzzeitig beim Syncen alle (oder nur einen Teil), und nach und nach kommen die Threads durch und sind soweit verschoben, dass sich "wahrscheinlich" nie wieder welche blockieren. DIe Frage ist also, wann sollte denn dann ein SharedCache sinnvoll sein?

jenz

knivil schrieb:

1.) I$ braucht nicht geshared sein.
2.) D$ soll nicht geshared sein, da mehrere Prozesse unterschiedliche Daten verarbeiten. Warum soll mein Videoplayer den gleichen Cache benutzen, wie mein Videospiel, dass nebenbei laeuft? Also konsistente Caches bringen nur in wenigen Faellen etwas, z.B. Supercomputing. Dafuer gibts dann von Intel Larrabee/Knights Corner (ka. wie es final heissen wird).

Wenn alle Prozessoren auf dem selben Cache arbeiten, dann sind die Daten doch automatisch konsistent.

Die Schwierigkeiten ergeben sich bei der Realisierung. Multithreading ist normalerweise so gestrikt, dass eben nicht auf den gleichen Daten gearbeitet wird.

Und das würde ja auch nichts machen.
Die Konsistenz diesem gemeinsamen Cache kommt ja "for free", die kostet nix.

knivil

Die Konsistenz diesem gemeinsamen Cache kommt ja "for free", die kostet nix.

Wenn Prozess A den Cache von Prozess B immer kaputt macht als auch anders herum, dann arbeitet Programm A und B langsamer, als wenn sie einen getrennten Cache benutzen. Nix ist for free!