| 

.NET C# Java Javascript Exception

5
Hallo codekicker

Ich hab ein kleines Projekt in C# angefangen: Game of Life.
Der Algorithmus ist soweit klar, alles wird sauber berechnet und gezeichnet.
Jetzt möchte ich aber mehr Performance rausholen. Im Moment gehe ich mit 2 Schleifen durch ein verschachteltes Array und wende den Algorithmus auf jedes Feld an. Bei 10x10 Feldern oder auch bei 100x100 Feldern ist das auch noch schnell genug. Aber bei 500x500 (250000 Felder) sieht das schon anders aus. Jetzt habe ich mir überlegt, die Berechnung auf 4 Threads aufzuteilen. Jeder Thread soll ein Viertel berechnen.
Und da kommt mein Problem ins Spiel: wie kann ich feststellen, das alle 4 Threads durchgelaufen sind, und die nächste Generation berechnet werden kann?

Der Code sieht im Moment so aus:

// Arbeitsarray initialisieren
m_nextPopulation = new Cell[m_RowCount][];
for (int r = 0; r < m_RowCount; r++) { m_nextPopulation[r] = new Cell[m_ColumnCount]; }

m_CellsAlive = 0;
m_CellsDead = 0;

System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
sw.Start();

CalcFirstQuarter(); //berechnet das erste Viertel im Arbeitsarray m_nextPopulation
CalcSecondQuarter(); //berechnet das zweite Viertel im Arbeitsarray m_nextPopulation
CalcThirdQuarter(); //berechnet das dritte Viertel im Arbeitsarray m_nextPopulation
CalcFourthQuarter(); //berechnet das vierte Viertel im Arbeitsarray m_nextPopulation

sw.Stop();
System.Diagnostics.Debug.WriteLine(string.Format("calc: {0}", sw.Elapsed.TotalMilliseconds));

// hier muss sichergestellt sein, das alle 4 Threads durchlaufen wurden
m_Population = m_nextPopulation; // Anzeigearray mit Arbeitsarray überschreiben
m_Generation++;
News:
10.07.2011
Christian M. Müller 251 1 7
gfoidl 9,4k 3 5
4 Antworten
4
Du kannst Du pro Viertel auch
Task t1 = Task.Factory.StartNew(() => CalcFirstQuarter());
Task t2 = Task.Factory.StartNew(() => CalcSecondQuarter());
...

aufrufen und auf die Abarbeitung aller Tasks mit

Task.WaitAll(t1,t2,...)

warten.

Gruß
Florian
10.07.2011
ffordermaier 8,4k 3 9
Werde ich direkt mal ausprobieren...
Christian M. Müller 10.07.2011
Das funktioniert super!
Die Berechnung braucht jetzt gut 25% weniger Zeit.
Christian M. Müller 10.07.2011
4
Hallo,

das ist eigentlich ein "Klassiker" für "phasengesteuertes Threading". Ab .net 4.0 gibts dazu den Barrier. Mit dem lässt sich das komfortabel umsetzen.

mfG Gü
10.07.2011
gfoidl 9,4k 3 5
Sorry, das ist mir zu hoch XD
Christian M. Müller 10.07.2011
Defintiv die sauberste Lösung
Dustin Klein 11.07.2011
Stimme ich bedingt zu: für den geposteten SourceCode ist die Verwendung von Tasks minimalinvasiv. Wenn man der MSDN Glauben schenkt (Link von gfoidl zu Barrier): "Barriers are especially useful when the threads are performing multiple phases in loops. If your code requires only one or two phases of work, consider whether to use System.Threading.Tasks.Task objects with any kind of implicit join". Nichtsdestotrotz passt die Barrier hier natürlich wie die Faust aufs Auge.
ffordermaier 11.07.2011
Wenn ich das richtig verstanden habe würde man die Barrier doch nur einsetzen, wenn unterschiedliche Threads aufeinander folgen sollen (bitte korrigiert mich, wenn ich das falsch sehe).
In meinem Anwendungsfall dürfen ruhig alle Threads (oder Tasks) parallel laufen. Ich muss halt nur wissen wann tatsächlich alle durchgelaufen sind. Und das Task.WaitAll() erscheint mir da besser geeignet, und ist für mich auch leichter anzuwenden / zu duchschauen.
Christian M. Müller 11.07.2011
Was machst du denn nach dem Task.WaitAll()? Die Task erneut starten? Wenn ja ist der Barrier genau dafür eine Erleichterung. Er wartet bis alle Thread (oder als Task abstrahiert) bis zum Barrier (~Schranke) kommen und danach lässt er entweder alle Threads weiterarbeiten oder in einer Post-Phase nur einen und dann wieder alle. Steht aber auch so in der RTFM.
gfoidl 11.07.2011
Nach dem WaitAll wird das Anzeigearray mit Arbeitsarray überschreiben. Und danach ist im Prinzip Schluß. Erst mit einem Timer-Ereignis oder einem Button-Click-Ereignis wird der ganze Vorgang wieder gestartet.
Christian M. Müller 11.07.2011
3
Hallo,

ich weiß jetzt zwar nicht was genau dein Algorithmus macht und ob es damit möglich ist.
Aber um Multithreading gut in der Schleife einsetzen zu können müssen die einzelnen Berechnungen unabhängig voneinander sein
D.h. r=2 darf nicht das resultat von r=1 benötigen

Wenn das funktioniert, dann könntest du es einfach mit der Parallel.Foreach versuchen.
Dabei wird es automatisch in mehrere Threads ausgelagert

Gruß
Michael
10.07.2011
michlG 1,7k 1 5
1
Die einzelnen Berechnungen beziehen sich immer genau auf ein bestimmtes Feld im Array.
Mit Parallel.For habe ich mal runexperimentiert, habe es aber nicht zum laufen gekriegt. Mal sehen obs mit Foreach klappt.
Christian M. Müller 10.07.2011
Game of Life berechnet die Existenz einer Zelle anhand seiner umliegenden Zellen. Ich glaube, dass ist ein Problem beim Multitheading. Die Lösung kann demnach nicht sein, die Berechnung einfach nur auf 4 Threads zu verteilen.
oopexpert 11.07.2011
... das ist ein Problem beim Multithreading ...
oopexpert 11.07.2011
Das Multithreading soll ja nur die Berechnung beschleunigen.
Ich arbeite in meiner Implementierung mit 2 Arrays, eins das die aktuelle Generation wiederspiegelt, und eins in dem die nächste Generation berechnet wird. In jedem der 4 Threads wird in anderer Bereich der aktuellen Generation betrachtet. Insofern lässt sich das Multithreading da gut anwenden.
Christian M. Müller 11.07.2011
1
Hallo,

bin gerade zufällig über Game of Life vom MS Pfx-Team gestolpert. Das kannst du auch als Referenz hernehmen.

mfG Gü
14.07.2011
gfoidl 9,4k 3 5
Sehr interessant, Danke!
Christian M. Müller 15.07.2011

Stelle deine .net-Frage jetzt!