Frage zu Critical Section bei Array Zugriff

[alleinherrscher]

Hi@all.

Ich habe ein großes "Array of Array of Array of double";

In diesem möchte ich per Finite-Differenzen-Methode die Lösung einer Poission Gleichung iterieren. Um eine Verbesserte Lösung an der Stelle (x,y,z) zu berechnen, muss auf alle Nachbarpunkte lesend, und auf die Stelle x,y,z schreibend zugegriffen werden.

Um das Verfahren zu beschleunigen, habe ich n Threads eingeführt.
Jeder Thread iteriert zunächst eine x-y-Ebene in diesem Array, erhöht dann z um 1 und iteriert die nächste x-y Ebene. Ist ein Thread beim Maximalwert von z angekommen, wird z wieder auf 0 gesetzt.
Damit ein Thread den anderen nicht "überholen" kann (Konsistenz der Lösung), fragt der i+1 Thread, ob die z Position des i-ten Thread mindestens um 1 größer ist, als die Position des i+1-ten Threads:

Delphi-Quellcode:

       while (not Iterrationsgenauigkeit_erreicht) do
       begin
        inc(j);
        for z := 0 to NodeCount_z-1 do
          begin
            current_z:=z;
            i:=Thread_id-1;
            if i=-1 then i:=Num_Thread-1;
            if assigned(Threads[i]) then
               while (Threads[i].Current_z>Current_z) and (Threads[i].Current_z-Current_z<=1) do
                  sleep(10);
            for x := 0 to NodeCount_x-1 do
               for y := 0 to NodeCount_y-1 do
                    begin
                        //Führe FDM-Iteration aus
                    end;
            end;
        end;

Zur kurzen und knappen Frage: Benötige ich irgendwo eine Critical-Section?
Da ich ja nicht auf den selben Array-Eintrag mit zwei verschiedenen Threads zugreife, gibts hier eig. kein Problem oder?
Benötige ich vielleicht für die variable current_z eine Critical-Section?

Besten Dank für eure Hilfe!

Euer Michael

[alleinherrscher]

Hat niemand eine Idee?

[sx2008]

Zitat von alleinherrscher:

Da ich ja nicht auf den selben Array-Eintrag mit zwei verschiedenen Threads zugreife, gibts hier eig. kein Problem oder?

Wenn du das sicherstellen kannst dann brauchst du keine Critical Section.
Du könntest auch jedem Thread eine Kopie der Daten geben (ein Teilarray) und am Ende die Ergebnisse wieder zusammensetzen.
Das ist das Prinzip "Teile und Herrsche".
Wenn jeder Thread nur auf seinen eigenen Daten arbeitet dann kann er keinem anderen Thread in die Quere kommen.
Natürlich geht beim Kopieren von Arrays etwas Performance verloren; dann könnte aber im Vergleich zur Gesamtaufgabe unter einem Promille liegen.
Das Kopieren liese sich aber auch vermeiden, indem jeder Thread die Indexgrenzen (oder Zeiger auf Anfang und Ende) bekommen innerhalb dessen er arbeiten soll.
Das ist ja die Strategie die du z.Zt. verfolgst.
Bei harten Rechenaufgaben wie z.B. FFT sollte man übrigens nur soviele parallele Threads einsetzen wie der Prozessor an Kernen hat.

[alleinherrscher]

Hey, danke für die Infos. In der Tat hatte ich diese Methode (Teile und Herrsche) schon einmal implementiert. Allerdings geht aus folgendem Grund die performance sehr in den Keller:

1. An der Array-Grenze von zwei Threads, muss Thread 1 auf den Bereich von Thread 2 zugreifen und umgekehrt, da ich für die Berechnung am Punkt x,y,z jeweils die Punkte x+1,y,z ; x-1,y,z ; x,y+1,z ; x,y-1,z; x,y,z+1 ; x,y,z+1 benötige.

2. Ich muss sicherstellen, dass Thread 1 sein Teilgebiet nicht schon 200 mal durchlaufen hat, während Thread 2 erst 180 mal durchgelaufen ist.

3. Aus physikalischen Gründen benötigen die verschiedenen Teilgebiete unterschiedlich lange zur Berechnung. D.h.: Wegen dem vorher genannten Grund warten sich n-1 Thread die Füße in den Bauch, während Thread n noch rechnet....

[BUG]

Man muss die Teilstücke ja auch nicht starr einem Thread zuordnen, sondern kann einen Worker-Pool nutzen. Der enhält so viele Worker, wie es Prozessoren gibt.
Zu den Teilbereiche werden die angrenzenden Punkte mitgespeichert (sog. Geisterpunkte). Es sollte mehr Teilstücke geben als Worker.

Der Hauptthread macht nun folgendes:

1. die Teilstücke initialisieren
2. alle Teilstücke in Auftrag geben
3. blockieren, bis alle Teilstücke berechnet wurden
4. die Geisterpunkte aktualisieren
5. Abbruchkriterium prüfen, wenn nicht erfüllt: gehe zu 2.

Ein schöner Nebeneffekt ist, dass du nach Schritt 4. auch mal einen Zwischenstand speichern kannst.

Eine andere Sache: Wenn du weder Synchronisationsmittel nutzt, noch dich selbst darum kümmerst, können "merkwürdige" Sachen mit den Caches passieren. In den meisten Varianten sollte die Implementierung des Workerpool mit klassischen Synchronisationsmitteln schon ausreichen, um solche Effekte zu vermeiden.

[alleinherrscher]

Ah verstehe. Ja die Methode hört sich auch gut an

Zitat:

Eine andere Sache: Wenn du weder Synchronisationsmittel nutzt, noch dich selbst darum kümmerst, können "merkwürdige" Sachen mit den Caches passieren. In den meisten Varianten sollte die Implementierung des Workerpool mit klassischen Synchronisationsmitteln schon ausreichen, um solche Effekte zu vermeiden.

Ich sorge ja dafür dass nicht gleichzeitig auf gleiche Array-Einträge zugegriffen wird (mittels "current_z", s.o.)...hatte gehofft, dass das ausreicht?

[Sir Rufo]

Wenn du die Teilbereiche etwas intelligenter machst (kennt seine Nachbarn, kann sich und die Nachbarn sperren), dann erstellst du die Teilbereiche, packst diese in eine Queue und aus dieser Queue werden die Worker bedient.

Code:

repeat
  TB = Queue.Dequeue
  if not TB.TryLock then
    Queue.Enqueue( TB )
    TB = nil
until TB <> nil
WorkerThread.WorkOn( TB )

Dadurch organisieren sich die Teilbereiche und WorkerThreads selber und du kannst eine allgemein gültige Klasse schreiben, die solche Arten von Aufgaben durch Threads erledigen lässt.