MaDOS/gi4_uebung07

GI4 - Übung 7

Übung 7: Funktionen und parallele Programmierung II

In den nachfolgenden Aufgaben wird der zweite Teil der letzten Übung fortgesetzt. Es soll die näherungsweise Lösung des linearen Gleichungssystems

Ax=b, A=a_i,j ∈ ℜ^{n x n} und b,x ∈ ℜ

also

∑ a_i,j x_j = b_i, i ∈ {1,...,n}

ermittelt. Dabei soll das Jacobi-Verfahren verwendet werden, welches die i-te Gleichung nach x_i auflöst. Hieraus ergibt sich folgende Iterationsvorschrift für den m+1-ten Iterationsschritt:

x_i^m+1 = 1 / a_i,i (b_i - ∑ a_i,j^m)

Um zu erkennen, ob das Iterationsverfahren die Lösung gefunden hat, soll der Euklidische Abstand zwischen x^m und x^m+1 verwendet werden. Ist dieser sehr klein (bei uns kleiner als √ (n 􏰄􏰂0.0000001 · n)), wurde der Lösungsvektor gefunden und das Iterationsverfahren kann abgebrochen werden. Der Abstand wird wie folgt bestimmt: √ (∑ (x_i^m - x_i^m+1)²)

Hinweis: Im L2P finden Sie eine äquivalentes PDF-Dokument, welches die Formeln schöner und eventuell lesbarer darstellt.

1. Parallelisieren Sie das Jacobi-Verfahren (und nicht die Bestimmung des Euklidischen Abstands) durch die Verwendung von POSIX-Threads. Gehen Sie dabei zur Vereinfachung davon aus, dass n durch die Anzahl der Threads ohne Rest teilbar ist.
2. Verbessern Sie Ihre Lösung, indem Sie SSE-Instruktionen zur Bestimmung des Euklidischen Abstands verwenden. Gehen Sie zur Vereinfachung davon aus, dass n eine gerade Zahl ist.
3. Verbessern Sie Ihre zuvor entwickelte Lösung des Jacobi-Verfahrens, in dem Sie neben den POSIX-Threads nun auch SSE-Instruktionen verwenden. Nutzen Sie dabei die beiden in den vorherigen Aufgabenteilen genannten Vereinfachungen.
4. Welchen Geschwindigkeitszuwachs erzielen Sie gegenüber der ursprünglichen, nicht parallelisierten Version aus der vorherigen Übung?