Multithreaded Java Programm für Conways Spiel des Lebens - Streit in den Grenzzellen

8

Ich lerne die gleichzeitige Programmierung in Java und schreibe eine Simulation für Game of Life.

Hier ist was ich denke:

  • Verwenden Sie int [] [], um die Zustände der Zellen zu speichern
  • partitioniere das int [] [] in t Segmente und verwende t worker threads
  • Die t-Threads lesen von ihrem Segment, berechnen neue Werte für alle Zellen in ihrem Segment und aktualisieren die Zellen.
  • Sobald sie mit der Berechnung fertig sind, warten sie auf eine Schranke für andere Arbeiter, um zu beenden
  • Wenn die Schranke überschritten wird, aktualisiert der Haupt-Thread die Benutzeroberfläche.
  • Die Arbeiter fahren fort, den nächsten Zustand zu berechnen.

Jetzt wird es Streit an den gemeinsamen Grenzen der Segmente geben. Wenn ein Thread den Zustand einer Grenzzelle überschrieb, bevor sein Nachbar den vorherigen Wert gelesen hat, wird die Berechnung des Nachbarn falsch sein.

Was sind meine Optionen?

  • Verwenden Sie callable statt runnable und lassen Sie die Worker-Threads den neuen Wert zurückgeben (anstatt die Segmente selbst zu aktualisieren). Der Haupt-Thread kann die Matrix aktualisieren, nachdem die Barriere überschritten wurde. Diese Option beinhaltet das Kopieren der von Worker-Threads zurückgegebenen Ergebnisse in die Matrix.
  • Benutze zwei Barrieren. Der Worker-Thread erstellt eine Kopie der Grenzzellen aus den Segmenten ihrer Nachbarn und wartet an der ersten Barriere. Sobald diese Barriere überschritten ist, fahren sie damit fort, die nächsten Zustände zu berechnen und die Segmente an Ort und Stelle zu aktualisieren. Dann warten sie an der 2. Schranke. Der Haupt-Thread aktualisiert die Benutzeroberfläche.

Meine Frage ist, gibt es eine andere Möglichkeit, mit den Konflikten an den Grenzzellen umzugehen, die kein Kopieren von Daten beinhalten oder effizienter ist als die beiden oben genannten Optionen? Kann ReaderWriterLock, volatile Variable oder andere Synchronisierungsmechanismen verwendet werden?

UPDATE: Bis jetzt das doppelte Pufferlösung von Peter ist die sauberste. Aber ich habe eine Frage. Da die beiden Arrays gemeinsame Daten sind und wir keine Synchronisation verwenden (synchronisierter Zugriff oder flüchtige Variable), wird dadurch kein Sichtbarkeitsproblem verursacht ? Können mehrere CPUs die Array-Werte zwischenspeichern und bei jeder Iteration nur einen Teil des Arrays aktualisieren? Dann erhalten die Threads veraltete Werte für die Grenzzellen. Ist das möglich? Wenn nicht, warum. Wenn ja, wie löse ich es? Es scheint, zwei volatile Arrays zu deklarieren wird ihre einzelnen Elemente nicht volatil machen .

    
Helen 24.02.2010, 19:50
quelle

5 Antworten

5

Ich schlage vor, 2 int [] [] Arrays zu haben. Nennen wir sie A und B. A wird die Werte aller ungeraden "Ticks" enthalten und B wird die geradzahligen Ticks enthalten.

Initialisiere A auf deinen ursprünglichen Zustand. Lassen Sie dann Ihre Threads los, um den nächsten Zustand jeder Zelle zu berechnen, und platzieren Sie die Ergebnisse in die entsprechende Zelle in B. Sobald alle Ihre Threads fertig sind, haben Sie Ihren neuen Zustand in B. Verwenden Sie nun B, um den nächsten Zustand jeder Zelle zu berechnen, und speichern Sie die Ergebnisse in A. Zu jeder Zeit wird ein Array nur gelesen, und das andere schreib nur, so wird es nie Streit geben.

Vorteile:

  • Kein Kopieren von Daten im Vergleich zu dem, was Sie jetzt tun. Es findet nur ein Schreibvorgang pro Zelle statt.
  • Sie müssen sich keine Gedanken über Rand- / Eckfälle machen, da der Algorithmus einfach ist.
  • Keine laufende Speicherzuweisung. Ordnen Sie die beiden Arrays beim Start einfach zu.

Nachteile:

  • Sie müssen doppelt so viel Speicher reservieren.
Peter Recore 24.02.2010 20:47
quelle
1

Es beantwortet nicht Ihre eigentliche Frage, aber meine Empfehlung wäre Ihre erste Option ... die neuen Werte zurückgegeben zu haben, anstatt dass die Worker-Threads sie aktualisieren. Ich würde noch einen Schritt weiter gehen und den "Aggregator" dazu bringen, die Ergebnisse der Worker-Threads in ein neues Board-State-Array zu kombinieren und dann das erste zu verwerfen. Mein Argument ist, dass es die allgemeine Lesbarkeit der Logik verbessern wird, da es wenig oder gar keine "globalen Interaktionen" geben wird, um die Sie sich sorgen müssen.

Davon abgesehen bin ich ein bisschen voreingenommen, weil ich es vorziehe, auf eine funktionale Weise zu programmieren, außer wenn es einen starken Grund gibt, das nicht zu tun.

    
RHSeeger 24.02.2010 20:22
quelle
1

Ich würde den folgenden Ansatz versuchen:

  • Lassen Sie die Arbeiter die Berechnungen durchführen, aber schreiben Sie nur die Werte in die inneren Zellen zurück.
  • Speichern Sie die Ergebnisse für Grenzzellen.
  • Wenn die Berechnungen abgeschlossen sind, warten Sie an einer Schranke.
  • Wenn sich alle Arbeiter an der ersten Barriere befinden, dann lass sie los und erlaube jedem, die Grenzzellen zu schreiben.
  • Warte auf eine zweite Barriere, während die Benutzeroberfläche aktualisiert wird

Speicher, der für eine n x m Kachel benötigt wird, ist 2 * (n + m - 1) , also benötigen im Allgemeinen größere Kacheln (8x8 oder mehr) proportional weniger Speicher für die zwischengespeicherten Werte.

    
Devon_C_Miller 24.02.2010 20:31
quelle
0
___ qstnhdr ___ Multithreaded Java Programm für Conways Spiel des Lebens - Streit in den Grenzzellen ___ answer23000052 ___

Ich bin gerade auf java.util.concurrent.Exchanger<V> gestoßen. Es fungiert als ein Austauschpunkt. Ich kann es wahrscheinlich verwenden, um Listen von Zellenzuständen zwischen benachbarten Threads auszutauschen. Das wäre besser als eine Barriere, weil ich nur zwischen benachbarten Arbeitern synchronisieren muss.

    
___ answer2329202 ___

Es beantwortet nicht Ihre eigentliche Frage, aber meine Empfehlung wäre Ihre erste Option ... die neuen Werte zurückgegeben zu haben, anstatt dass die Worker-Threads sie aktualisieren. Ich würde noch einen Schritt weiter gehen und den "Aggregator" dazu bringen, die Ergebnisse der Worker-Threads in ein neues Board-State-Array zu kombinieren und dann das erste zu verwerfen. Mein Argument ist, dass es die allgemeine Lesbarkeit der Logik verbessern wird, da es wenig oder gar keine "globalen Interaktionen" geben wird, um die Sie sich sorgen müssen.

Davon abgesehen bin ich ein bisschen voreingenommen, weil ich es vorziehe, auf eine funktionale Weise zu programmieren, außer wenn es einen starken Grund gibt, das nicht zu tun.

    
___ tag123java ___ Java (nicht zu verwechseln mit JavaScript oder JScript oder JS) ist eine universelle objektorientierte Programmiersprache, die für die Verwendung in Verbindung mit der Java Virtual Machine (JVM) entwickelt wurde. "Java-Plattform" ist der Name für ein Computersystem, auf dem Tools zum Entwickeln und Ausführen von Java-Programmen installiert sind. Verwenden Sie dieses Tag für Fragen, die sich auf die Java-Programmiersprache oder Java-Plattform-Tools beziehen. ___ answer2336775 ___

Um Ihr Update über das Caching-Problem mit Double-Buffering zu beantworten, ist das kein Problem. CPUs haben kohärenten Cache und sie wissen, wann Daten in einem anderen CPU-Cache geändert wurden.

    
___ tag123synchronization ___ Synchronisation bezieht sich auf die Verwendung von Steuerelementen, um eine kohärente Darstellung zu erhalten, entweder eine Gruppe von Prozessen, die dasselbe Programm ausführen (Prozesssynchronisierung), oder Darstellungen von Daten (Datensynchronisierung). ___ tag123congensgameoflife ___ Das Spiel des Lebens, auch einfach als Leben bekannt, ist ein zellulärer Automat, der 1970 vom britischen Mathematiker John Horton Conway erfunden wurde. Das "Spiel" findet auf einem 2D-Gitter statt, das aus Zellen besteht, die entweder "lebendig" oder "tot" sein können. Bei jeder Iteration wird der Zustand jeder Zelle basierend auf den Zuständen der Zelle und ihrer 8 Nachbarn bei der vorherigen Iteration berechnet. ___ tag123multithreading ___ Multi-Threading ist die Fähigkeit eines Computers oder eines Programms, Arbeit gleichzeitig oder asynchron auszuführen, indem mehrere gleichzeitige Ausführungsströme (im Allgemeinen als Threads bezeichnet) verwendet werden. ___ tag123javamemorymodel ___ Das Java Memory Model (JMM) beschreibt, welche Ausführungen eines Programms legal sind, indem es festlegt, welche Werte beim Lesen einer gemeinsamen Variablen nach bestimmten Regeln beobachtet werden können. ___ answer2329383 ___

Ich schlage vor, 2 int [] [] Arrays zu haben. Nennen wir sie A und B. A wird die Werte aller ungeraden "Ticks" enthalten und B wird die geradzahligen Ticks enthalten.

Initialisiere A auf deinen ursprünglichen Zustand. Lassen Sie dann Ihre Threads los, um den nächsten Zustand jeder Zelle zu berechnen, und platzieren Sie die Ergebnisse in die entsprechende Zelle in B. Sobald alle Ihre Threads fertig sind, haben Sie Ihren neuen Zustand in B. Verwenden Sie nun B, um den nächsten Zustand jeder Zelle zu berechnen, und speichern Sie die Ergebnisse in A. Zu jeder Zeit wird ein Array nur gelesen, und das andere schreib nur, so wird es nie Streit geben.

Vorteile:

  • Kein Kopieren von Daten im Vergleich zu dem, was Sie jetzt tun. Es findet nur ein Schreibvorgang pro Zelle statt.
  • Sie müssen sich keine Gedanken über Rand- / Eckfälle machen, da der Algorithmus einfach ist.
  • Keine laufende Speicherzuweisung. Ordnen Sie die beiden Arrays beim Start einfach zu.

Nachteile:

  • Sie müssen doppelt so viel Speicher reservieren.
___ answer2329263 ___

Ich würde den folgenden Ansatz versuchen:

  • Lassen Sie die Arbeiter die Berechnungen durchführen, aber schreiben Sie nur die Werte in die inneren Zellen zurück.
  • Speichern Sie die Ergebnisse für Grenzzellen.
  • Wenn die Berechnungen abgeschlossen sind, warten Sie an einer Schranke.
  • Wenn sich alle Arbeiter an der ersten Barriere befinden, dann lass sie los und erlaube jedem, die Grenzzellen zu schreiben.
  • Warte auf eine zweite Barriere, während die Benutzeroberfläche aktualisiert wird

Speicher, der für eine %code% Kachel benötigt wird, ist %code% , also benötigen im Allgemeinen größere Kacheln (8x8 oder mehr) proportional weniger Speicher für die zwischengespeicherten Werte.

    
___ qstntxt ___

Ich lerne die gleichzeitige Programmierung in Java und schreibe eine Simulation für Game of Life.

Hier ist was ich denke:

  • Verwenden Sie int [] [], um die Zustände der Zellen zu speichern
  • partitioniere das int [] [] in t Segmente und verwende t worker threads
  • Die t-Threads lesen von ihrem Segment, berechnen neue Werte für alle Zellen in ihrem Segment und aktualisieren die Zellen.
  • Sobald sie mit der Berechnung fertig sind, warten sie auf eine Schranke für andere Arbeiter, um zu beenden
  • Wenn die Schranke überschritten wird, aktualisiert der Haupt-Thread die Benutzeroberfläche.
  • Die Arbeiter fahren fort, den nächsten Zustand zu berechnen.

Jetzt wird es Streit an den gemeinsamen Grenzen der Segmente geben. Wenn ein Thread den Zustand einer Grenzzelle überschrieb, bevor sein Nachbar den vorherigen Wert gelesen hat, wird die Berechnung des Nachbarn falsch sein.

Was sind meine Optionen?

  • Verwenden Sie callable statt runnable und lassen Sie die Worker-Threads den neuen Wert zurückgeben (anstatt die Segmente selbst zu aktualisieren). Der Haupt-Thread kann die Matrix aktualisieren, nachdem die Barriere überschritten wurde. Diese Option beinhaltet das Kopieren der von Worker-Threads zurückgegebenen Ergebnisse in die Matrix.
  • Benutze zwei Barrieren. Der Worker-Thread erstellt eine Kopie der Grenzzellen aus den Segmenten ihrer Nachbarn und wartet an der ersten Barriere. Sobald diese Barriere überschritten ist, fahren sie damit fort, die nächsten Zustände zu berechnen und die Segmente an Ort und Stelle zu aktualisieren. Dann warten sie an der 2. Schranke. Der Haupt-Thread aktualisiert die Benutzeroberfläche.

Meine Frage ist, gibt es eine andere Möglichkeit, mit den Konflikten an den Grenzzellen umzugehen, die kein Kopieren von Daten beinhalten oder effizienter ist als die beiden oben genannten Optionen? Kann ReaderWriterLock, volatile Variable oder andere Synchronisierungsmechanismen verwendet werden?

UPDATE: Bis jetzt das doppelte Pufferlösung von Peter ist die sauberste. Aber ich habe eine Frage. Da die beiden Arrays gemeinsame Daten sind und wir keine Synchronisation verwenden (synchronisierter Zugriff oder flüchtige Variable), wird dadurch kein Sichtbarkeitsproblem verursacht ? Können mehrere CPUs die Array-Werte zwischenspeichern und bei jeder Iteration nur einen Teil des Arrays aktualisieren? Dann erhalten die Threads veraltete Werte für die Grenzzellen. Ist das möglich? Wenn nicht, warum. Wenn ja, wie löse ich es? Es scheint, zwei volatile Arrays zu deklarieren wird ihre einzelnen Elemente nicht volatil machen .

    
___
Helen 24.02.2010 22:17
quelle
0

Um Ihr Update über das Caching-Problem mit Double-Buffering zu beantworten, ist das kein Problem. CPUs haben kohärenten Cache und sie wissen, wann Daten in einem anderen CPU-Cache geändert wurden.

    
Ramónster 25.02.2010 19:01
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Groß- / Kleinschreibung ohne Bedeutung, Vergleich mit linq-to-sql und linq-to-objects