POISSON - ein Beispiel zur Gebietszerlegung

• Aufgabenstellung:

Finde approximative Lösung der Poisson-Gleichung

• 

auf einem rechteckigen Gitter für gegebene Quellen f und Randwerte u

• Sourcen:

poisson.h	Definitionen für POISSON
poisson.c	Hauptprogramm
get_args.c	Initialisierung
set_source.c	Bestimmung der Quellen-Matrix
par_loop.c	Thread-Funktion
sweep1d.c	Jacobi-Iteration
dump.c	Ausgabe der Ergebnis-Matrix
finalize.c	Aufräumen
barrier.h	"summierende" Barrier (Header)
barrier.c	"summierende" Barrier (Implementierung)
matrix.h	dynamische Matrizen (Header)
matrix.c	dynamische Matrizen (Implementierung)

• Bemerkungen zur skalaren Version:

Kontinuum ersetzt durch Gitter, Lösung durch Jacobi-Iteration:

• 

Beispiel-Quelle: 4 Punktsourcen als Quadrupol

Implementierung mit zwei U-Matrizen im Wechsel (vermeidet Umkopieren)

Es gibt wesentlich bessere Algorithmen (SOR, Multigrid).

• Bemerkungen zur parallelen Version:

Parallelisierung durch (möglichst gleichmäßige) Zerlegung des Arrays in Zeilenblöcke, die dann jeweils von einem Thread bearbeitet werden.

Probleme mit dem Überlapp der Bereiche - wie beim analogen Message-Passing-Problem - gibt es hier nicht, da die überlappenden Zugriffe nur lesend sind; jeder Thread schreibt nur in seinem Bereich.

Eine kompliziertere Zerlegung in 2-dimensionale Blöcke, die beim Message-Passing sinnvoll ist, um den Kommunikations-Aufwand zu verringern, ist hier überflüssig.

Zwischen den einzelnen Sweeps muß mit einer Barrier synchronisiert werden, sonst benutzt z.B. ein schneller Thread veraltete Daten. Eine solche Kombination von Loops und Barriers tritt bei der Parallelisierung mit Threads häufig auf.

Bleibt noch: Gesamtfehler für Sweep zum Abbruch der Schleife muß aus den Einzelfehlern der Threads bestimmt werden.

• entweder direkt summieren:

        errors[myid] = localerror;  /* globales array error */
        if (myid == 0) {
           error = sum(errors);
           if (error < EPS) 
             exit_flag = 1;  /* zu 0 initialisiert */
        }
        if (exit_flag == 1)
          return;

• oder besser und einfacher mit "summing barrier":
  barrier verwaltet neben dem count, der jeweils um 1 erhöht wird, noch eine Summe, die um einen vom Caller festgelegten Betrag erhöht wird.