Sinkende Ausführungszeit der parallelen Rot/Blau-Berechnung

Question

Das allgemeine Problem, das ich versuche zu lösen, ist die Rot/Blau-Berechnung. Die allgemeine Idee ist, dass Sie eine NxN-Karte mit Leerzeichen haben, rote Chips, die sich um ein Leerzeichen nach rechts bewegen, und blaue Chips, die sich um ein Leerzeichen nach unten bewegen. Bei jedem Schritt dieser Berechnung bewegen sich alle Rots, die nicht im Weg sind (dh ein roter/blauer Chip) nach rechts, wenn sie am Rand des Boards sind, springen sie nach vorne. Dann, nachdem die rote Bewegung beendet ist, machen die Blues das gleiche, aber sie bewegen sich nach unten. Nun wird die NxN-Karte in TxT-Kacheln aufgeteilt, wobei T N teilt, und die Berechnung stoppt, wenn die Konzentration eines roten/blauen Chips in irgendeinem dieser Kacheln einen Schwellenprozentsatz C erreicht.

Also war mein erster Gedanke zu einer parallelen Lösung, die Berechnung unter den Prozessoren nach Zeilen und Spalten aufzuteilen. Nimm so grob N, teile es durch die Anzahl der Prozessoren und sie tun diese Zeilen und Spalten. Aber diese Lösung war nicht so effizient. Dann dachte ich daran, es in Blöcke aufzuteilen, wo jeder Prozessor einen N/sqrt (P) xN/sqrt (P) -Block erhält, wobei P die Anzahl der Prozessoren ist und dann Mutexe an den Kanten haben, was die Berechnung beschleunigt Menge. Aber ich denke, dass ich eine bessere Lösung gefunden habe, die mit bitweisen Operationen zu tun hat. Ich kann die Anzahl der Zeilen und Spalten durch 32 teilen, also muss ich nur ungefähr 1/32 der Arbeit machen. Aber hier liegt das Problem, hier ist ein Beispiel für ein 4x4-Brett, wo 0 = Raum, 1 = rot, 2 = blau

0202 
0221 
1122 
1102 

So wie ich besetzt Store würde Rottöne in Reihen ist

[0000] 
[0001] 
[1100] 
[1100] 

und die Art und Weise würde ich besetzte Blues Spalten speichern ist

[0000] 
[1100] 
[0110] 
[1011] 

und dann würde ich eine Ergänzung Zeilen- und Spaltenmatrix, die die Informationen aller besetzten Zellen hatte, Beispiel wäre hier alle belegten Zellen in Reihen

[0101] 
[0111] 
[1111] 
[1101] 

und dann ist hier alle belegten Zellen in Spalten,

[0011] 
[1111] 
[0110] 
[1111] 

alle diese Informationen verwenden genug ist für jede Zeile und Spalte im wesentlichen konstant Zeit die ganze Arbeit zu tun. Bis jetzt ist diese Methode nicht wirklich wichtig, weil ich für jede Bewegung, die ich in einer Reihe in der Tafel mache, jede Spalte aktualisieren muss, in der sie speichert, welche Zellen besetzt sind, und dann mache ich die gleiche Arbeit wie ich hat keine dieser bitweisen Operationen ausgeführt. Gibt es eine Möglichkeit, dass ich diese anders speichern könnte oder anders mit ihnen umgehen könnte, damit ich die verringerte Laufzeit halten kann?

Answer 1

Ein paar Alternativen für die Datenspeicherung sind Morton Z-Auftragskurven. Mit Z-geordneten Kurven können Sie Zeilen & Spalten in Blöcken verarbeiten. Siehe https://en.wikipedia.org/wiki/Z-order_curve Aber allgemein eine der Anwendung von Quadtrees für die 2D-Problem betrachten, sehen: http://www.cs.umd.edu/~hjs/pubs/Samettfcgc88-ocr.pdf

Ein weiterer Ansatz ist dies auf parallele Hardware wie eine GPU zu tun von OpenCL oder CUDA.