Anwendung von SMP-Systemen

3. Anwendung von SMP-Systemen

In diesem Kapitel geht es um die Anwendung von SMP-Systemen. Dabei betrachten wir sowohl die Programmierung eines SMP-Rechners als auch konkrete SMP-taugliche Anwendungen. Die Beispielprogramme dienen auch der Beantwortung der schon einmal aufgeworfenen Frage, ob ein SMP-System mit N Prozessoren auch einen N-fachen Leistungszuwachs bringt. Urspünglich stellte sich diese Frage bei der Anwendung von Parallelrechnern, wo man aber festgestellen mußte, daß es nur sehr wenige Probleme gibt, die linear mit der Prozessoranzahl skalieren, d.h. bei denen sich mit wachsender Prozessoranzahl die Rechenzeit so verkürzt, daß wenn man z.B. die doppelte Anzahl von Prozessoren nimmt, die Rechenzeit nur noch die Hälfte der ursprünglichen beträgt. Die Mehrzahl der Anwendungen, besonders im Betriebsumfeld, skalieren nicht linear. Das Problem ist im Allgemeinen, daß sich viele Anwendungen nur sehr schlecht in voneinander unabhängige Teile zerlegen lassen (also schlecht parallelisierbar sind), sodaß sie auf unterschiedlichen Prozessoren abgearbeitet werden können. Bei SMP-Rechnern kommt noch die Tatsache hinzu, daß diese überwiegend aus Standardkomponenten bestehen, die nicht an die Leistung von speziell konstruierten Parallelrechnerkomponenten herankommen. Ein weiteres Problem ist, daß SMP-Systeme nicht mit beliebig vielen Prozessoren gebaut werden können, da sonst die "Shared-Memory"-Eigenschaft teuer bezahlt werden muss: Der Verwaltungsaufwand und der Preis für einen entsprechend breiten und sicheren Speicherbus wächst dann ins Unermessliche.

3.1. Speedup

Betrachtet man die Laufzeiten eines SMP-tauglichen parallelen Programmes und die eines seriellen Programmes, so interessiert am meißten, um wieviel schneller (oder langsamer) das parallele Programm ist. Bezeichnet t1 die Ausführungszeit eines Algorithmus auf einem Rechner mit einem Prozessor und tP die Zeit, die ein entsprechender paralleler Algorithmus auf einem Rechner mit P Prozessoren benötigt, so definiert man das Verhältnis

SP = t1 / tP

als Speedup. SP ist der Faktor, um den das parallele Programm ggf. schneller läuft, gibt also die Beschleunigung gegenüber dem seriellen Programm an. Fairerweise sollte man nur Algorithmen der selben "Güte" gegenüberstellen, denn es nützt nichts, einen hocheffizienten seriellen Algorithmus mit einem schlechten parallelen zu vergleichen und vice versa. Der Speedup wird insbesondere in den noch folgenden Messungen eine Rolle spielen.

3.2. Linux und SMP

Bevor Linux SMP-fähig wurde, hatte man nur die Wahl, einen Intel SMP-Rechner mit Windows NT, OS/2 bzw. einem kommerziellen PC-UNIX zu betreiben, was sehr teuer war und ist. Bei der neuesten Version von Windows NT, Windows 2000 muss man sogar die Unterstützung für jeden weiteren Prozessor (bzw. Prozessorpaar) teuer erkaufen. Aus diesem und aus anderen naheliegenden Gründen habe ich die Beispielprogramme unter Linux entwickelt, wo der Aufwand zum Herstellen eines SMP-fähigen Kernels mittlerweile nur noch darin besteht, die entsprechende Konstante SMP in den Make-Dateien auf 1 zu setzen (obwohl SMP=1 eigentlich etwas ironisch ist ;-) ) und den Kernel neu zu kompilieren. Da Linux schon seit längerem POSIX-konform ist, unterstützt es auch die üblichen SMP-Programmiermodelle (Stichwort "Multithreading"), auf die wir im folgenden noch kommen. Linux ist auch zur Intel-SMP-Spezifikation in den Versionen 1.1 und 1.4 konform und kann theoretisch mit bis zu 16 Prozessoren arbeiten, obwohl das in der Praxis relativ selten ist; der Standardfall wird eher ein 4-fach SMP-Rechner sein.

3.3. Shared-Memory-Programmierung und Threads

Wie wir in Abschnitt 2.2.3. gelernt haben, besitzen SMP-Rechner einen gemeinsamen Speicherbereich, den man als Shared Memory bezeichnet. Bei der Programmierung eines derartigen Rechners unterscheidet man prinzipiell zwei Konzepte voneinander:

Shared Everything
Shared Something

Bei beiden Fällen kommunizieren die Prozessoren über Load/Store-Befehle mit dem Speicher. Der Unterschied ist lediglich, daß bei "Shared Everything" alle Datenstrukture im gemeinsamen Speicher liegen, während bei "Shared Something" der Benutzer angeben muß, welche Datenstrukturen er teilen möchte, und welche privat sind.

Wir werden uns der Multithreading-Programmiermethode bedienen um parallele Programme auf einem SMP-Rechner zu schreiben. Aus diesem Grund kommt für uns nur "Shared Everything" in Frage, weil dieses von Threads unterstützt wird. "Shared Something" ist unter Linux zwar auch möglich (durch Interprozesskommunikation) aber weit weniger komfortabel. Was aber sind Threads eigenlich? Nun, prinzipiell haben Threads und Multithreading nichts mit Multiprozessoren zu tun - es gibt sie auch auf Einprozessor-Rechnern. Ihre Entwicklung reicht bis zu den Ursprüngen von UNIX zurück, also bis in das Jahr 1970, wo sie erstmals in das Betriebssystem Multics implementiert wurden, das später dann von Ken Thompson und Dennis Ritchie in UNIX umbenannt wurde.

In der UNIX- und mittlerweile auch in der Windows-Welt unterscheidet man Prozesse und Threads. Prozesse sind die komplexeren Objekte aus der Betriebssystemsicht. Wenn ein Programm gestartet wird, so ist es ein Prozess innerhalb einer Multitasking-Umgebung. Threads sind sogenannte "lightweight processes"; sie ähneln zwar den Prozessen, teilen aber den selben Adressraum, Datei- Deskriptoren usw. So kann es innerhalb eines Prozesses mehrere "parallel" arbeitende Threads geben, die zusammen ein Programm (eine Anwendung) repräsentieren. Parallel ist hier in Anführungszeichen gesetzt, da sie auf Einprozessor-Rechnern nicht wirklich parallel abarbeiten.

Es gibt heute viele populäre Programme, die "multithreaded" sind. Aus der Windows-Welt z.B. die Programme der Office-Reihe oder der "Explorer". Unter Linux gibt es ebensoviele, wenn nicht mehr Multithreading-Anwendungen. Was ist aber nun der eigentliche Vorteil von Threads gegenüber Prozessen? Nun, der Aufwand, der betrieben werden muss, um von einem Prozess auf einen anderen umzuschalten (was innerhalb einer Multitasking-Umgebung oft vorkommt) ist groß. Bei diesem sog. Kontext-Wechsel muss die gesamte Prozessumgebung gespeichert werden, was viel Betriebssystemzeit verbraucht. Die Threads verbrauchen aber weit weniger Ressourcen, weswegen bei einem Thread-Kontext-Wechsel nur die Register, der Programmzähler und der Stack-Pointer gespeichert werden müssen. Ein solcher Kontext-Wechsel erfolgt natürlich viel schneller. Man kann also ein Programm in viele unterschiedliche Teile (Threads) aufspalten, die voneinander unabhängig sind. Durch die Benutzung von Threads erreicht man somit eine gewisse Parallelität, weil zwischen den einzelnen Threads sehr schnell umgeschaltet werden kann. Gewisse Klassen von Anwendungen können davon profitieren.

Diese Parallelität kann auch schon auf einem Einprozessor-System erreicht werden, was aber nur in den wenigsten Fällen eine Leistungssteigerung bringen wird, eher das Gegenteil. Dadurch sind Threads auf Einprozessor-Maschinen oftmals nur ein Komfort-Gewinn, da man "weiterarbeiten" kann (wenn auch langsamer), während andere Dinge im Hintergrund erledigt werden. Sinnvoll werden Threads auf einem SMP-System, weil hier das Betriebssystem, wenn es SMP-tauglich ist, idealerweise einen Thread pro Prozessor unterbringen kann, was letztendlich eine echte parallele Abarbeitung bewirkt.

3.4. Multithreading unter Linux

Die erste Bibliothek, die Multithreading unter Linux anbot, wobei die Threads auch auf die einzelnen Prozessoren eines SMP-Systemes verteilt wurden, war die bb_threads-Library ("Bare Bones"-Threads). Die Bibliothek ist sehr einfach gehalten (der Quellcode ist gepackt nur 7K groß!) und für gößere Anwendungen praktisch nicht nutzbar, da die Aufrufe nicht standardisiert sind.

Besser ist da die Linux Threads-Library, die eine mittlerweile fast komplette Implementation des POSIX-Standard 1003.1c darstellt. Diese POSIX-Konformität bedeutet aber, daß es relativ einfach ist, viele vorhandene auf diesem Standard basierende Anwendungen nach Linux zu portieren (zumindest hinsichtlich des Multithreading). Die kommerziellen UNIX-Varianten wie Solaris, AIX, HP-UX usw. sind ebenfalls POSIX-konform. Beide Varianten von Thread-Libraries offerieren "Kernel-Level Threads". Das bedeutet, daß die Threads als echte UNIX-Prozesse über den UNIX-clone()-Aufruf gestartet werden - mit dem Unterschied jedoch, daß sie sich einen gemeinsamen Speicher teilen. Daraus resultiert, daß der Verwaltungsaufwand bei Kontext-Wechsel nicht ganz so groß ist, wie bei normalen Prozessen.

3.5. Anwendungsbeispiele

In diesem Abschnitt wollen wir schließlich 3 konkrete Programme unter Linux betrachten, die mit Multithreading programmiert wurden. Zum Vergleich betrachten wir die selbe Anwendung als serielle Version bzw. mit 2, 3 und 4 Threads. Bei den Vergleichen ist jedesmal der in 3.1. eingeführten Speedup angegeben, so daß man sofort sehen kann, wie gut eine Anwendung von den 4 Prozessoren profitiert. Die Messungen wurden auf einem 4-fach Xeon-Server (500 Mhz) mit einem Intel "SC450NX MP"-Board durchgeführt, der unter Redhat Linux, Kernel 2.2.15 lief. Der SMP-Server war mit 2 GB Hauptspeicher bestückt, was insbesonders bei der dritten Anwendung von Bedeutung ist. Einschränkend muß allerdings gesagt werden, daß die Anwendungen nur aus dem numerischen Bereich kommen, der vielleicht nicht unbedingt der Haupteinsatzbereich eines SMP-Rechners ist. Jedoch sind umfangreichere Testbenches, die alle Systemkomponeten mit in den Test einbeziehen schwierig zu programmieren und zu verstehen (d.h. sie überschreiten noch die Programmierkünste des Autors ;-) ), weshalb ich mich für numerische Programme entschieden habe. Die Beispielprogramme können als komprimiertes Unix-Archiv (.tar.gz) heruntergeladen werden, weshalb sich ein seitenlanges Einfügen des Quellcodes erübrigt. Ich werde nur bestimmte Ausschnitte aus dem Programm präsentieren, die mir als wichtig und erklärenswert erscheinen.

3.5.1. Pi-Berechnung

piserial.c und pilinuxthread.c

Dieses Programm habe ich nicht selbst erstellt, sondern es stammt aus dem Linux-Parallel-HOWTO. Ich habe es jedoch für die Benutzung mit 4 Threads und zur Zeitmessung ein wenig modifiziert. Es berechnet die allseits bekannte Konstante Pi. Jeder Thread benutzt zur Berechnung von Pi die gleiche Funktion, die lediglich mit anderen Parametern aufgerufen wird. Hier sehen wir die Funktion "process" (eigentlich ist der Name schlecht gewählt!), welche die Berechnung durchführt:

void *process(void *arg)
{
   register double width, localsum;
   register int i;
   register int iproc = (*((char *) arg) - '0');

   width = 1.0 / intervals;
   localsum = 0;

   for(i = iproc; i < intervals; i += 4)
   {
      register double x = (i + 0.5) * width;
      localsum += 4.0 / (1.0 + x * x);
   }

   localsum *= width;

   pthread_mutex_lock(&pi_lock);
   pi += localsum;
   pthread_mutex_unlock(&pi_lock);

  return(NULL);
}

Was ist daran aber multithreaded? Wie wir an der for-Schleife sehen, läuft die Berechnung in einem Intervall ab. Das geht so, daß der aktuelle Wert des Intervalls in die Berechnung eingeht, nämlich durch

register double x = (i + 0.5) * width;

Nun könnte ein serielles Programm das ganze Intervall durchforsten, also z.B. für i nacheinander die Werte 0, 1, 2, 3, 4,... usw. einsetzen. Das parallele Programm mit 4 Threads geht aber anders vor: Jeder Thread startet mit einem anderen Anfangswert: Thread 0 mit 0, Thread 1 mit 1, Thread 2 mit 2 und schließlich Thread 3 mit 3 (Variable iproc). Nun wird der Wert für i nicht um 1, wie bei einem seriellen Programm, sondern um 4 erhöht. Thread 0 hat für i also als nächsten Wert die 4, Thread 1 die 5, Thread 2 die 6 und Thread 3 die 7. Wie man sieht, wird die Schleife auch nacheinander abgearbeitet, mit dem Unterschied, daß immer 4 Werte von i gleichzeitig in der Berechnung sind.

Interessant ist hierbei folgendes: Die Variable i ist für jeden Thread privat, da innerhalb des Funktionskontextes. Die Variablen intervals und pi können aber von allen benutzt werden - wie man sieht handelt es sich bei dem Programm um eine echte Shared-Memory-Anwendung. Die Anweisungen

pthread_mutex_lock(&pi_lock);

bzw.

pthread_mutex_unlock(&pi_lock);

verhindern, daß zwei Threads gleichzeitig auf die Shared-Memory-Variable pi zugreifen und somit u.U. nur eine Addition effektiv ausgeführt wird. Das liegt daran, daß der Zugriff auf i in zwei Speichertransaktionen ausgeführt wird, wobei während der ersten Transaktion weiterhin von der Variable gelesen werden kann. Mit den Befehlen wird ein Lock gesetzt bzw. gelöscht; ein in der Shared-Memory-Programmierung wichtiges Konzept, auf das ich aber nicht näher eingehen möchte.

Hier nun die Ergebnisse meiner Zeitmessung (Speedup < 1 ist mit "-" gekennzeichnet worden):

Anzahl der Intervalle	Zeit(µs) für serielle Version	Speedup für 2 Threads	Speedup für 3 Threads	Speedup für 4 Threads
1	1	-	-	-
10	2	-	-	-
100	9	-	-	-
1000	76	-	-	-
10000	747	-	-	-
100000	7596	1.3	1.8	2.28
1000000	74102	1.4	2.13	2.87
10000000	741103	1.4	2.16	2.87

Tabelle 3.1.

Die Werte sind überraschend: in 60% der Fälle läuft das Programm mit 2 oder mehr Threads langsamer, als die serielle Variante. Was sind die Ursachen dafür? Zunächst einmal dauert die Initialisierung der Threads eine ganze Weile, was zumindest bei geringen Intervallgrößen (1, 10, 100) einen großen Unterschied zur seriellen Variante ausmacht. Später dann sind die CPUs wahrscheinlich nicht genügend ausgelastet, und die multithreaded-Variante erweist sich eher als Behinderung für die relativ einfache Berechnung. Erst ab 100000 ist eine Beschleunigung meßbar. Hier ist die Grenze erreicht, wo eine CPU schneller als vier ist, weil die CPUs offenbar gleichmäßig ausgelastet werden können. Doch der stärkste Speedup mit 4 Threads ist lediglich 2.87, was keineswegs linear ist. Wir hätten sicherlich einen Wert um die 4 erwartet. Möglicherweise ist der Speicherbus das Problem, da durch das ständige Schreiben auf den Shared-Memory (Variable pi) der Speicherbus stark benutzt wird. Hinzu kommen noch Locks, durch die bei den einzelnen Threads Wartezyklen entstehen, die im Endeffekt die Gesamtperformance beeinflussen. Leider sieht es im nächsten Beispiel noch schlechter aus.

3.5.2. Primzahl-Berechnung

primeserial.c und primelinuxthread.c

In meinem multithreaded-Primzahl-Programm habe ich eine parallele Variante des Sieb des Eratosthenes implementiert. Der serielle Algorithmus ist sehr einfach: Angenommen wir wollen alle Primzahlen bis 1000 ausrechnen. Wir schreiben dazu alle Zahlen nacheinander bis zu dieser Zahl auf. Dann fangen wir an, alle Vielfachen von 3 zu streichen, danach die von 5, 7, ... usw. (die geraden Zahlen können wir weglassen) bis wir alle Vielfachen von Zahlen herausgestrichen haben. Die übrigbleibenden Zahlen (bis auf die geraden Zahlen) sind nicht Vielfache der anderen Zahlen, also durch diese nicht teilbar, weswegen sie Primzahlen sein müssen. Ebenso kann man das serielle Programm implementieren (mit ein paar Beschleunigungen, z.B. das nur Vielfache von Zahlen gestrichen werden, die selbst noch nicht gestrichen wurden u.a.). Man benötigt nur ein Zahlenfeld, indem man die Elemente am entsprechenden Index "markieren" kann (z.B. durch 0 oder 1). Am Ende durchläuft man das Feld und gibt den Index aus, der nicht als gestrichen markiert wurde.

Die parallele Version arbeitet ähnlich dem Pi-Programm. Jeder Thread startet bei einer anderen Zahl, also Thread 0 bei 3, Thread 1 bei 5, Thread 2 bei 7 und Thread 3 bei 9. Nun wird in der Schleife der Index der aktuell zu bearbeitenden Zahl um die doppelte Threadanzahl hochgezählt, da man sonst irgendwann in einen Zyklus kommt, indem die Threads die selben Zahlen prüfen. Die nächsten zu prüfenden Zahlen wären also im obigen Beispiel 11, 13, 15 und 17. Da wir alle geraden Zahlen herauslassen (wir fangen bei 3 an!), muss am Ende nur noch sichergestellt werden, das die 2 als Primzahl mit ausgegeben wird und der Index in der Ausgabeschleife keine geraden Werte überstreicht, da wir den Inahlt der Elemente an geraden Indexstellen nie geändert haben.

Die Ergebnisse:

Anzahl der Primzahlen	Zeit(µs) für serielle Version	Speedup für 2 Threads	Speedup für 3 Threads	Speedup für 4 Threads
1	1	-	-	-
10	3	-	-	-
1000	135	-	-	-
10000	1545	-	-	-
100000	17018	1.19	1.17	1.00
1000000	321774	1.08	1.17	1.14
10000000	3876768	1.05	1.03	1.06

Tabelle 3.2.

Das Primzahl-Programm skaliert offenbar noch schlechter als die Pi-Berechnung (bzw. skaliert überhaupt nicht :-) ). Aber dabei handelt es sich doch um ein schön parallelisierbares Programm, warum kann es dann nicht von den weiteren Prozessoren profitieren? Die Ursache dafür ist wieder beim Speicher, bzw. wohl auch beim Cache zu finden: Greift ein Prozessor auf eine bestimmte Zeile im Speicher schreibend zu, so kann es passieren, daß andere Prozessoren eben diese Zeile auch in ihrem Cache haben und aus Gründen der Cache-Kohärenz bzw. der Cache-Konsistenz über die Änderungen informiert werden müssen. Das wiederrum resultiert in einer starken Benutzung des Speicherbusses, worunter natürlich auch die Gesamtleistung des Programmes leidet. Im Programm kann man sehen, daß immer wieder lesend und schreibend auf den Array primes zugegriffen wird - wohl der Flaschenhals des Programmes.

3.5.3. Matrixmultiplikation

matmult.c und matmult-thread.c

Das letzte Beispielprogramm führt eine Multiplikation von zwei (n x n)-Matrizen (mit Elementen aus N) durch; eine sehr zeitraubende und langweilige Aufgabe, für die man besser einen Computer benutzt. Der Ansatz hier war der Folgende: Jeder Thread startet mit einer anderen Zeile und führt dann die Multiplikation nach dem bekannten Verfahren durch (also Summe der Produkte aus Zeilenelement der einen Matrix und korrespondierendem Spaltenelement der anderen). Thread 0 startet mit Zeile 1, Thread 1 mit Zeile 2, Thread 2 mit Zeile 3 und Thread 3 mit Zeile 4. Die Threads zählen in der Schleife für die Zeilenauswahl jeweils um die Threadanzahl - im obigen Beispiel 4 - hoch, wodurch im nächsten Schritt Thread 0 mit der Zeile 5 weiterarbeitet, Thread 1 mit Zeile 6 usw. usf. Das Ergebnis wird in eine - in diesem Falle ebenfalls (n x n)-Matrix - zurückgeschrieben. Der Speicheraufwand für das Programm ist enorm. Ausgehend von der Organisation der Daten kann man folgende Formel der Speicherbedarf in MB aufstellen:

M = (12 * N + 12 * N * N) / (1024 * 1024)

Maximal habe ich (3000 x 3000)-Matrizen berechnet, wofür man schon rund 104 MB benötigt. Glücklicherweise stand mir ein Rechner mit 2 GB Hauptspeicher zur Verfügung, mit dem auch z.B. (9000 x 9000)-Matrizen möglich gewesen wären. Die relativ lange Laufzeit bei der Berechnung machte es aber notwendig, einmal abzuschätzen, wie lange das Programm rechnet, d.h. welcher Komplexitätsklasse es angehört (man will ja nicht ewig auf sein Ergebnis warten :-) ). Der Kernpunkt des Programmes ist eine dreifach verschachtelte Schleife, die jeweils n-mal durchlaufen wird. Der Aufwand ergibt sich also zu n * n * n = n³. Das bedeutet eine Verdoppelung der Problemgröße führt zu einer Verachtfachung der Rechenzeit, was durch die Meßergebnisse bestätigt wird. Jetzt wird auch klar, warum ich nur (3000 x 3000)-Matrizen multipliziert habe.

Hier die Ergebnisse der Matrixmultiplikation:

Zeilen- / Spaltengröße	Zeit(s) für serielle Version	Speedup für 2 Threads	Speedup für 3 Threads	Speedup für 4 Threads
10	0.000038	-	-	-
100	0.033	1.13	2.00	2.75
1000	67.03	1.68	2.50	3.20
2000	559.33	1.62	2.40	3.11
3000	1949.03	1.72	2.60	3.30

Tabelle 3.3.

Wie zu erwarten war, ist der Aufwand im unteren Bereich für die Initialisierung der Threads größer als die Rechenzeit für das serielle Programm, weshalb hier Speedup-Werte < 1 herauskommen. Im oberen Bereich skaliert das Programm zwar nicht linear aber immerhin besser als die vorherigen Beispiele. Das mag wohl daran liegen, daß ich viel öfter vom Speicher lese als in ihn schreibe. Deswegen kommt wahrscheinlich der Cache-Effekt mehr zum tragen und wirkt hier nicht so stark als Hindernis. Das Programm ist keineswegs effektiv und könnte sicherlich noch bessere Werte liefern, wenn man die Daten in den Arrays anders organisiert. Man sollte hier aber im Auge behalten, daß die Zeiteinheit in diesem Beispiel nicht µ-Sekunden (wie bei den vorherigen Beispielen) sonder Sekunden ist, und selbst ein Speedup von nur 2 ist hier ein guter Wert, denn es macht schon einen Unterschied ob mein Computer eine halbe oder eine Stunde rechnet!

Vorige Seite Inhalt Nächste Seite