Warum ist ein Programm mit nur Atomics in SC-DRF, aber nicht in HRF-direkt?

In der Arbeit "Heterogen-Race-Free Memory Models" [1] geben die Autoren an, dass ein Programm, das nur aus Atomic besteht, in SC-DRF rassenfrei ist, aber nicht in HRF-direct. Ich kann nicht verstehen, warum das so ist. Kann jemand erklären, wie das passieren kann?

[1] Derek R. Hower et al. , "Heterogene, rassenfreie Speichermodelle". In Proceedings of ASPLOS '14 , ACM, 2014. ( PDF )

Hoffentlich sagten sie nicht explizit genau: "Ein Programm, das nur aus Atomics besteht, ist in SC-DRF rassenfrei." Das ist falsch

Sie sagen, dass "[in] Scoped Synchronization ... es möglich ist, ein Racey-Programm zu schreiben, das vollständig aus Atomics besteht, wenn diese Atomics Scopes nicht richtig verwenden" [oben auf Seite 2], was etwas anders ist (und verwendet das Wort "Racey" mehrdeutig, was Sie vielleicht zu der Annahme veranlasst, dass sie die falsche Aussage gemeint haben.) Sie hätten vielleicht stattdessen sagen sollen, dass es bei der Synchronisation mit Gültigkeitsbereich möglich ist, ein nicht sequentiell konsistentes Programm zu schreiben , das vollständig aus Atomics besteht, wenn diese Atomics Verwenden Sie die Bereiche nicht richtig.

SC-DRF (etwa: der Speicher Semantik für C ++ und Java) divide Speicherplatz in zwei Klassen, Synchronisationsobjekte, (manchmal genannt atomics) und Datenobjekte. Zum größten Teil ist garantiert, dass alle Operationen an Synchronisationsobjekten sequentiell konsistent sind . [1] ( Nicht rennfrei.) Dies ist eine Einschränkung für den Compiler und nicht für den Programmierer. Es heißt, wenn der Programmierer sagt, dass ein Thread ein Atomobjekt schreibt, adann schreibt er ein Atomobjekt b, alleIn den Threads werden die Schreibvorgänge in dieser Reihenfolge ausgeführt. (Der Compiler darf die Zugriffe nicht neu anordnen und muss die entsprechenden Speicherbarrieren und Zäune auf Computern einfügen, die nicht sequentiell konsistent sind.)

Sequentiell konsistent bedeutet, dass sich alle Threads auf allen Prozessoren auf eine Gesamtreihenfolge aller Speicheroperationen einigen. Wenn ein Thread glaubt, dass die Operation vor der Operation stattgefunden hat , denken alle Threads, dass die Operation vor der Operation stattgefunden hat . Sequentiell konsistent bedeutet nicht nicht rassig und es bedeutet nicht deterministisch . Beispielsweise könnten zwei verschiedene Threads versuchen, dieselbe Synchronisationsvariable ungefähr zur gleichen Zeit zu schreiben. Diese Zugriffe werden rennerisch sein. Ein sequentiell konsistentes System garantiert nur, dass, wenn ein Thread denkt, dass das Schreiben vor dem Schreiben stattgefunden hat$x$ $y$$x$ $y$$x$$y$ , alle Threads stimmen darin überein, dass das Schreiben von vor dem Schreiben von stattgefunden hat . Sequentielle Konsistenz ist nützlich, da Sie damit nützliche nicht deterministische Synchronisationsobjekte wie Mutexe und Bedingungsvariablen erstellen und begründen können.$x$$y$

SC-DRF sagt dann , dass , wenn Ihr Programm Daten Rennen frei, die Operationen auf Daten werden Objekte angezeigt werden sequentiell konsistent . Der Compiler ist zulässig neu anordnen (oder manchmal sogar eliminieren) Operationen auf Datenobjekte, und wenn die darunter liegende Maschine nicht sequentiell konsistent ist, wird der Compiler nicht einzufügen Speicherbarrieren oder Zäunen erforderlich. Aber der Compiler nicht zu Neuordnungsoperationen auf Datenobjekte in Bezug auf Operationen auf Synchronisationsobjekte erlaubt.

Daten Race Free ist nicht dasselbe wie Race Free . Und sequentiell konsistent ist nicht dasselbe wie rennfrei . Ein besonderer Programmausführungsplan ist Daten Rennen frei , wenn für jedes Paar von Datenobjektzugriffe, und , die von zwei verschiedenen Threads (mindestens eine davon ist eine Schreiboperation) können wir die (sequentiell konsistente) Reihenfolge der Ordnungsobjektzugriffe verwenden um zu beweisen, dass entweder vor oder vor passiert ist . Wenn wir den Beweis nicht erbringen können, ist dieser Ausführungsplan datenrassig .$x$$y$$x$ $y$$y$ $x$

Ein Programm ist frei von Datenrennen, wenn alle möglichen Ausführungspläne frei von Datenrennen sind. Ein Programm ist datenabhängig, wenn es einen Ausführungsplan gibt, der datenabhängig ist.

Datenrennen- frei zu sein, ist eine Einschränkung für den Programmierer, nicht für den Compiler. Es heißt, wenn Ihr Programm datenrassig ist, hat Ihr Programm keine Semantik. Der Compiler kann alles tun, was er will, einschließlich Anhalten des Programms, Gehen in eine Endlosschleife oder Sprengen des Computers.

Ach je. TL; DR! Ich habe SC-for-HRC noch nicht einmal erwähnt!

In SC-for-HRC müssen die Atomics angeben, zu welchem Bereich sie gehören. Atomare Zugriffe werden (vom Compiler) garantiert, dass sie nur innerhalb ihres eigenen Bereichs sequentiell konsistent sind. Alle Threads innerhalb des Bereichs stimmen über die Reihenfolge überein, in der die atomaren Zugriffe erfolgen, aber Threads in einem anderen Bereich stimmen möglicherweise nicht überein (und können die Zugriffe möglicherweise überhaupt nicht sehen, geschweige denn ihre Reihenfolge).

Beispielsweise kann es vorkommen, dass alle GPU-Threads übereinstimmen, dass Thread 19 Mutex A und dann Mutex B erworben hat, aber alle CPU-Threads nicht zustimmen (oder wissen), dass Thread 19 Mutex A oder Mutex B überhaupt erworben hat. SC-DRF hat keine "Bereiche", daher tritt dieses Problem nicht auf.

[1] Die Ausnahmen von der sequentiell konsistenten Atomik haben mit der expliziten Verwendung zu tun std::memory_order_relaxed. Also tu das nicht. (Und ich werde die Ausnahmen im Rest von dem, was ich sage, ignorieren.)