Programmiermodelle für moderne Mehrkernarchitekturen - (article in german)

Submit New Article

November 17, 2008 2:00 PM PST


Dieser Artikel ist erschienen im entwickler magazin - Heft 1.07  - Abdruck mit freundlicher Genehmigung der Zeitschrift: http://derentwickler.de

 

Programmiermodelle für moderne Mehrkernarchitekturen

Dieser Artikel beschreibt mögliche Ansätze zur Parallelisierung von sequentiellen Programmen. Außerdem werden die Herausforderungen und Risiken dargestellt, die den Programmierer bei der Portierung einer bestehenden seriellen Anwendung auf Mehrkernsysteme erwarten.

Dr. Mario Deilmann, Intel GmbH

Einführung

Alle führenden Hersteller von Prozessoren (AMD, IBM, Intel, Sun) haben von der Idee Abstand genommen, die Geschwindigkeit der Prozessoren durch Steigerung der Taktfrequenz und damit die Erhöhung des rohen Instruktionsdurchsatzes zu erreichen. In der Vergangenheit konnte man mit jeder neuen Prozessorgeneration auch eine Performancesteigerung der bestehenden Applikationen erwarten. Diese wurde zum einem durch eine Erhöhung der Taktfrequenz und zum anderen durch Parallelität auf Instruktionsebene (out-of-order execution pipeline, parallel arbeitende Funktionseinheiten) der verschiedenen superskalaren Architekturen erreicht. Die Möglichkeit der Taktfrequenzerhöhung scheint momentan aus verschiedenen Gründen (Herstellungskosten, Abwärme) zu stagnieren, und der Trend geht zur Verwendung von Mehrkernprozessoren. Bei der vielfädigen (Multithreaded) Prozessortechnik geht es in der Hauptsache um Vermeidung von Leerlaufzeiten des Prozessors. Damit bleibt das von Intel Gründer Gordon Moore definierte Gesetz weiter gültig, dass sich die Dichte der Transistoren (Integrationsdichte) auf einem Prozessor jedes Jahr verdoppelt . Dabei werden die zusätzlichen Transistoren für die Implementierung neuer Prozessorkerne verwendet.

 

Ein Mehrkernprozessor bezeichnet einen Mikroprozessor mit mehr als einem physikalischen Prozessor auf einem einzigen Chip, dabei werden die Ressourcen mit Ausnahme des Bus und eventuell verschiedener Cache-Level repliziert. Die verschiedenen Kerne sind also weitgehend voneinander unabhängige Prozessoren . Dieser relativ neue Trend, der grundsätzlich keine bahnbrechend neue Idee ist, setzt auf Parallelität der Prozessoren, oder genauer, der Prozessorkerne. Die rein theoretische Leistungssteigerung beträgt maximal 100% (gegenüber einem Kern) pro zusätzlichem Kern. In der Praxis hängt diese Leistungssteigerung aber hauptsächlich vom Grad und der Qualität der Parallelisierung in der Applikation ab. Das bedeutet also, dass mit der Einführung von Mehrprozessorsystemen ein Performancegewinn nur noch dann stattfindet, wenn die vorhandene Software angemessen parallelisiert und skaliert. Skalierbarkeit bedeutet in diesem Zusammenhang eine signifikante Performancesteigerung beim Übergang zu einer höheren Anzahl von Prozessoren. Abhängig von der Anwendung können z.B. auf Zweikernprozessoren Leistungssteigerungen von 1.3-1.9 der seriellen Performance beobachtet werden. Bis zum Ende dieses Jahres haben alle Prozessorhersteller Mehrprozessorsysteme für den Desktop auf dem Markt gebracht . Es werden Ende diesen Jahres die ersten Prozessoren mit vier Kernen erwartet und bis zum Jahresende 2007 soll es die ersten Prozessoren mit acht Kernen geben. Das heißt, dass in naher Zukunft vom Laptop bis zum Server alle Computer mit mehreren Prozessorkernen ausgerüstet sein werden. Dieser Trend hat bereits den Bereich der Spielkonsolen erreicht. Die Xbox 360 von Microsoft verfügt über drei Prozessorkerne und in der Sony Playstation 3 arbeiten bis zu acht Prozessorkerne parallel. Jetzt liegt es in der Hand der Softwareentwickler und Softwarehersteller, dieses Potential zu nutzen.

 

Chancen und Risiken paralleler Softwareentwicklung

Was bedeutet im Einzelnen diese Hinwendung zu parallelen Architekturen für die Softwareentwicklung? Ganz allgemein können zum einen mehrere parallele Prozessoren die zu bewältigende Arbeit in kürzerer Zeit erledigen, zum anderen können größere Probleme berechnet werden. Dies erfordert allerdings ein Umdenken oder einen sog. Paradigmenwechsel in der Softwareentwicklung. D.h. weg von der sequentiellen Sicht der Dinge hin zu einer parallelen Beschreibung der Anwendung. In Bezug auf parallele Softwareentwicklung gab es innerhalb der letzten zehn Jahre nichts Revolutionäres zu berichten. Die Entwicklung vollzog sich vielmehr hin zu objektorientierten Ansätzen (C++, Java, C#). In Bezug auf parallele Programmiersprachen wurden verschiedene Ansätze im Bereich des wissenschaftlichen Hochleistungsrechnen etabliert. Interessant ist, dass sich selbst in diesem Bereich nur Sprachergänzungen (OpenMP, Cilk) zu den gängigen Programmiersprachen (C/C++, Fortran) und Bibliotheksansätze (PVM, MPI, Pthreads, Win32 Threads) durchgesetzt haben. Interessanterweise haben sich kaum Programmiersprachen mit komplexen parallelen Elementen entwickelt. Eine Ausnahme bildet die Forschung an symmetrischen Sprachen und die Sprache Erlang, die aber nur wenige Anhänger speziell in der Telekommunikationsbranche gefunden hat.

 

Was sind die Gründe dafür, dass der Großteil der kommerziellen Anwendungen die implizite oder passive Parallelität der Algorithmen nicht zur Performancesteigerung einsetzt? Ein Grund ist bisher das Fehlen von parallelen Systemen auf der Anwenderseite. Ein weiterer Grund liegt darin, dass bei der Programmierung paralleler Algorithmen eine Vielzahl zusätzlicher Schwierigkeiten auftreten, die es in der seriellen Programmierung schlichtweg nicht gibt: Die sequentiellen Kontrollflüsse müssen nebenläufig entworfen werden und es muss sichergestellt sein, dass sich diese nicht gegenseitig beeinflussen. Das heißt, dass parallele Zugriffe auf ein gemeinsames Betriebsmittel (Speicher, I/O, etc) ohne geeignete Synchronisation zu einer Reihe von schwer auffindbaren Fehlern wie Blockierungen und Zugriffskonflikten führen können. Außerdem muss die Skalierbarkeit und damit die Reduzierung der effektiven Ausführungszeit sichergestellt sein. Solch ein Entwurfskonzept stellt wesentlich höhere Anforderungen an die Entwickler und bedingt häufig eine komplette Restrukturierung des Originalentwurfes. In diesem Artikel werden lediglich parallele Ansätze untersucht, die eine Performancesteigerung zum Ziel haben. Parallele Ansätze zur Steigerung der Funktionalität wie die Implementierung von User-Interfacen oder der gleichzeitige Zugriff auf die verschiedenen Ressourcen eines Systems werden nicht behandelt.

 

Die parallelen Ansätze unterteilen sich in implizite und explizite Modelle. Die expliziten Modelle erfordern mehr oder weniger massive Änderungen am Quellcode bis hin zu einem komplett neuen Entwurf, da Programmteile in kausal unabhängigen (nebenläufigen), separaten Prozessen ausgeführt werden müssen. Am einfachsten funktionieren die impliziten Modelle, da sie keine Änderungen am Quellcode erfordern:

  1. Man ersetzt serielle Funktionen durch den Aufruf paralleler Bibliotheksroutinen. Dies kann z.B. eine mathematische Bibliothek wie die Intel® MKL sein.

  2. Man verwendet einen modernen Compiler, der den sequentiellen Quellcode in parallele Instruktionsströme transformiert, auf die vorhandenen CPU-Kerne verteilt oder die mit SSE (Streaming SIMD Extension) eingeführten 128-bit Register zur Ausführung gleichartiger Rechenoperationen benutzt. Dieser viel versprechende Ansatz ist z.B. in dem aktuellen Intel® Compiler implementiert (Compiler-Switch: /Qparallel (Windows) oder -parallel (Linux)), funktioniert jedoch nur bei einfachen Schleifenstrukturen und bestimmten arithmetischen Operationen.

     

Wenn man über Parallelisierung einer eigenen Anwendung nachdenkt, ist die zentrale Frage, was die limitierende Komponente dieser Anwendung ist. Dies kann der Prozessor, der Speicher, die Festplatte, das Netzwerk oder die Datenbank sein. Der erste Schritt ist, mit einem geeigneten Profiler (Gprof, Vtune, Perfmon, etc.) seine Anwendung in dieser Hinsicht zu untersuchen. Die Ansätze zur Parallelisierung, die auf Mehrkernprozessoren basieren, haben natürlich dann die meiste Aussicht auf Erfolg, wenn die Ausnutzung des Prozessors der limitierende Faktor ist. In diesem Fall können zusätzliche Prozessorkerne helfen, die Last zu verteilen.

 

 

Parallele Programmiermodelle

 

Mit den verschiedenen parallelen Programmieransätzen hat man ganz allgemein die Möglichkeit, ein Programm in einzelne nebenläufige Einheiten oder Programmfäden (Threads) zu zerlegen. Bei der Parallelisierung einer seriellen Anwendung gibt es zwei prinzipielle Vorgehensweisen in der praktischen Umsetzung. Bei Anwendung des inkrementellen Ansatzes werden Schritt für Schritt die rechenintensiven Bereiche einzeln parallelisiert (OpenMP). Bei Anwendung des zweiten möglichen Ansatzes werden die rechenintensiven Bereiche nebenläufig ausgelegt, und somit muss der Kontrollfluss sowie der Algorithmus neu entworfen werden (Threads, MPI). Die meisten parallelen Ansätze beruhen auf dem Prozesskontext Modell. Der Prozesskontext beinhaltet den vollständigen zeitabhängigen Zustand eines Prozesses des Prozessors, bestehend aus Befehlszähler, Stackpointer, Registerinhalte, Speicherbelegung und geöffnete Dateien. Es gibt zwei verschiedene Ansätze, die Shared-Memory-Programmierung und die Message-Passing-Programmierung.

 

Bei der Shared-Memory-Programmierung werden mehrere nebenläufige Threads erzeugt, die jeder für sich genommen seriell ablaufen. Die Reihenfolge und Priorität, mit der die einzelnen Instruktionen oder Bereiche der Threads ablaufen, ist dem Betriebssystem überlassen. Die Threads eines Prozesses kommunizieren über einen gemeinsamen Speicher. Die Erzeugung von Threads ist deutlich schneller und effizienter als die Erzeugung von Prozessen, weil kein vollständiger Austausch des Prozesskontextes notwendig ist. Threads teilen sich eine Reihe von Betriebsmitteln mit dem zugehörigen Prozess, wie Code- und Datensegment sowie Dateideskriptoren. Jeder Thread besitzt aber einen eigenen Befehlszähler und Stack. Da Threads demselben Prozess zugeordnet sind, kommunizieren diese über den gemeinsamen Adressraum. Diese Kommunikation ist ausgesprochen schnell, da der limitierende Faktor nur die Speicherzugriffszeit ist. Zu den Shared-Memory Programmiermodellen gehören alle Ansätze, die im weitesten Sinne auf Multithreading basieren, also Thread-Bibliotheken wie Pthreads oder Win32 Threads, Sprachen mit Thread-Erweiterungen wie Java und C# und Spacherweiterungen wie OpenMP.

 

Bei der Programmierung auf Basis des Message-Passing-Interfaces (MPI) werden neue Prozesse erzeugt. Für jeden dieser Prozesse muss ein neuer Prozesskontext erzeugt werden, ein in der Regel kostspieliger Vorgang. Diese parallelen Prozesse kommunizieren über ein anderes Interprozesskommunikationsmodell als die Threads, da sie nicht über einen gemeinsamen Speicher verfügen. Die einzelnen Prozesse kommunizieren über sog. Nachrichten, welche explizit von einem zum anderen Prozess geschickt werden. Der grundlegende Vorteil ist, dass die verschiedenen Prozesse durchaus auf verschiedenen Rechnern laufen können und dann über die vorhandene Netzwerkverbindung kommunizieren. Damit ist dieses Konzept auf Clustern von Computern einsetzbar. Die Vertreter dieses Ansatzes sind die auf dem MPI-1 oder MPI-2 Standard beruhenden kommerziellen Implementierungen wie HP MPI, IBM MPI, Intel® MPI oder die Opensource Implementierungen wie MPICH, Open MPI und LAM-MPI.

 

Die Wahl des Ansatzes und die Festlegung auf eine Implementierung legt die zu erwartende Performancesteigerung und den zu bewältigenden Aufwand fest. Wählt man ein Multithreading-Modell ist der theoretische Speedup, also die Größe, die angibt, um welchen Faktor die Ausführungsgeschwindigkeit im Vergleich zum seriellen Programm zunimmt, von der Anzahl von Prozessoren oder Kernen begrenzt. Wählt man ein Prozessmodell wie MPI ist der theoretische Speedup nur durch die Anzahl der Maschinen und somit der Prozessoren begrenzt, die man sich leisten kann. Der Aufwand, den man betreiben muss, um die Parallelisierung in die Anwendung zu bekommen, ist abhängig davon, ob man sich für ein inkrementelles Modell oder einen parallelen Entwurf des bestehenden Programms entscheidet. In Abb.1 ist eine qualitative Darstellung der verschiedenen Ansätze dargestellt. Der Programmieraufwand für einen parallelen Entwurf ist entsprechend hoch und bei MPI ähnlich den Threadbibliotheken. Es dauert halt einige Zeit bis der erste parallele Entwurf funktioniert. In den meisten Fällen bereitet danach eine ordentliche Skalierung und das Testen auf Korrektheit das meiste Kopfzerbrechen. Lediglich OpenMP mit seinem inkrementellen Ansatz liefert schon nach recht kurzer Zeit die ersten Ergebnisse, da der bestehende Entwurf nicht verändert wird. Message-Passing Modelle werden im Rahmen dieses Artikels nicht weiter behandelt, da der Einsatz diese Ansatzes in der Regel nur sinnvoll auf einem Cluster von Computern ist.

 

>>autorname_thema_1.jpg<<

Abb. 1: Zu erwartende Performancesteigerung im Vergleich zum Programmieraufwand

 

Im folgenden werden die verschiedenen Shared-Memory Modelle kurz vorgestellt, da diese ausschließlich auf Mehrkernsystemen Verwendung finden . Alle in diesem Rahmen untersuchten Multithreading Varianten benötigen die Unterstützung des Betriebssystems in dem Sinne, dass Betriebssystemaufrufe zum Erzeugen und Verwalten von Threads verwendet werden. Dadurch können die einzelnen Threads eines Prozesses auf den verschiedenen Prozessorkernen laufen. Diese Threads werden aus diesem Grund als Kernel-Level-Threads bezeichnet. Die hier nicht behandelten sog. User-Level-Threads laufen innerhalb eines Prozesses ab, benötigen keine Threadunterstützung des Betriebssystems, können damit aber auch nicht auf verschiedenen Prozessorkernen laufen. Der Teil des Betriebssystems, der den meisten Einfluss auf das Verhalten der Threads und Prozesse hat, ist der Scheduler. Bei gleichzeitiger Ausführung mehrerer Prozesse oder Threads muss das Betriebssystem die Zugriffe auf die vorhandenen Ressourcen wie CPU, Speicher und Festplatte regeln. Der Scheduling-Algorithmus entscheidet so z.B., wann und in welcher Reihenfolge die Instruktionen der verschiedenen Thread relativ zueinander ausgeführt werden und wann ein Thread eine Zustandsänderung des Speichers vornimmt. Solche Zustandsänderungen sind besonders kritisch, wenn mehrere Threads auf den gleichen Speicher zugreifen. In solchen Fällen kommt es zu so genannten Wettläufen (engl. race conditions), die in der Praxis unvorhersehbar und oft nicht reproduzierbar sind, da sie vom zeitabhängigen Verhalten des Schedulers abhängig sind. Ein weiteres Problem taucht auf, wenn sich verschiedene Threads durch abhängige Zugriffe auf die gleichen Ressourcen blockieren (engl. Deadlock). Am bekanntesten ist das von Edsger W. Dijkstra formulierte Philosophen-Problem (siehe Kasten). Durch diese Mechanismen bekommen Multithreading Programme eine Unbestimmtheit, die sequentielle Programme nicht haben. Dadurch ergeben sich Probleme, die beim Softwareentwicklungszyklus zusätzliche Werkzeuge notwendig machen, die die Korrektheit des Ablaufs und Speicherzugriffsfehler von Threads aufdecken können (IBM Purify, Intel® Thread Checker, Valgrind).

Die verschiedenen Multithreading Ansätze unterscheiden sich im wesentlichen durch den Grad der Granularität und Funktionalität. Dabei geht es im Kern darum, ob man die maximale Kontrolle bei der Erzeugung und Synchronisation der Threads haben möchte und damit auch den komplexesten und fehleranfälligsten Weg gehen möchte (Win32, Pthreads) oder ob man einen einfachen, inkrementellen Weg wählt, bei dem man die Details wie Erzeugung und Synchronisation im wesentlichen dem Programmiermodell überlässt (OpenMP), aber dadurch natürlich einen Teil der Kontrolle verliert. Ein richtig synchronisiertes, paralleles Programm zu entwerfen ist deutlich komplexer und anfälliger für Fehler als der Entwurf seines sequentielles Pendant. Im folgenden werden kurz die verschiedenen Threading Ansätze vorgestellt, deren Programmierung in einem nachfolgenden Artikel ausführlicher dargestellt wird.

 

Parallele Programmierung mit Thread Bibliotheken

Aus historischen Gründen haben die Hersteller der verschiedenen Hardwareplatformen und Betriebssysteme ihre eigenen, proprietären Versionen zum Thread-Handling implementiert. So gibt es verschiedene Implementierungen für die UNIX Platform (Sun, Digital Equipment) und die Windows-OS/2 Platform (Microsoft, IBM). Seit Einführung des IEEE POSIX® 1003.1c [1] Standards 1995 gibt es eine Basis für eine platformunabhängige POSIX® Thread Implementierung, die auf den verschiedenen Systemen verfügbar ist. Die verschiedenen Implementierungen, wenn auch nicht kompatibel, haben doch die Eigenschaft, sehr betriebssystemnahe Funktionen und Mechanismen zu verwenden. Die Benutzung dieser einfachen Konzepte in abstrakten und objektorientierten Sprachen gestaltet sich oft als schwierig. Dies liegt zum einen an der Verwendung der Betriebssystemfunktionen zur Erzeugung und Synchronisation von Threads sowie an den Verfahren zur Zugriffssteuerung, die so genannten Mutexe und Semaphoren. Ein Mutex verhindert, dass nebenläufige Prozesse bzw. Threads gleichzeitig auf Daten zugreifen und somit inkonsistente Zustände erzeugen können. Eine Semaphore ist eine Datenstruktur zur Zugriffsverwaltung von Daten. Diese Konzepte sind von zentraler Bedeutung für die Synchronisation konkurrierend ablaufende Prozesse und Threads. Allerdings muss man sich bei Verwendung von Multithreading schon sehr tief in die Bereiche der Systemprogrammierung begeben. Im Beispiel (siehe Kasten: „Hello World“ mit Win32 threads) fällt sofort ins Auge, wie viel Aufwand für die Erzeugung eines Threads nötig ist. Die Parameterübergabe ist auch nicht wirklich simpel und man benötigt ein Synchronisationskonstrukt, da man ja warten möchte, bis alle Threads mit ihrer Arbeit fertig sind. Dies ist hier simpel mit Sleep() realisiert, eleganter und richtiger wäre ein WaitForMultipleObjects() aus der Win32API, um wirklich auf die Beendigung der Threads zu warten; das leistet Sleep() nur in diesem einfachen Fall. Im Vergleich zum OpenMP Programm (siehe Kasten: „Hello World“ in OpenMP) fällt außerdem auf, dass man die Anzahl der Prozessorkerne vorher wissen muss, um die Anzahl der Threads zu ermitteln. Dies kann ggf. auf andere Weise realisiert werden, damit das Programm mit der Anzahl der Kerne skaliert. Zum Thema Multithreading gibt es viel Literatur. Stellvertretend seien hier nur die Werke von Butendorf [2] und Neuendorf [3] erwähnt.

Java, C# und Multithreading

Sun's Java Implementierung und die C# Implementierung von Microsoft unterstützen einfache aber nicht POSIX®-konforme Threads, diese sind in der Standard-Bibliothek oder einer speziellen Thread Klassenbibliothek implementiert. Es gibt spezielle Klassen zur Handhabung von Threads sowie Mechanismen zur Synchronisation von Threads. Threads sind somit als integraler Bestandteil der Sprachen von Java und C# implementiert. Dies macht die Verwendung von Threads deutlich einfacher und übersichtlicher. Allerdings muss man hier sagen, dass das objektorientierte Framework auch nur ein dünner Wrapper ist, um den Zugriff auf die feingranularen Betriebssystemfunktionen sowie die Zugriffsbeschränkungen (Monitore, Mutexe und Semaphoren) abzubilden. Es erfordert aber deutlich weniger Aufwand als die Verwendung von Threadbibliotheken und integriert sich deutlich leichter in die objektorientierte Sicht.

Inkrementelle parallele Programmierung mit OpenMP

Das einfachste Modell für die inkrementelle Implementierung eines parallelen Programms ist der OpenMP Standard, der seit 1997 gemeinschaftlich von verschiedenen Compiler- und Hardwareherstellern weiterentwickelt wird (http://www.openmp.org/). Der Standard, der mittlerweile in der Version 2.5 vorliegt, definiert die Shared-Memory-Programmierung für die Sprachen C/C++ und Fortran. Die Parallelisierung findet bei OpenMP auf Algorithmenebene statt. Dazu definiert der Standard spezielle Compiler-Direktiven, die die zu parallelisierenden Aufgaben auf ein Team von Threads verteilen. Dabei wird die Zahl der Threads zur Laufzeit durch Angabe der Prozessoren und Kerne bestimmt. Nach einer Analyse der performancerelevanten Teile kann eine inkrementelle Parallelisierung dieser Programmteile beginnen. Der OpenMP Standard umfasst die Verwaltung des Gültigkeitsbereiches von Daten und Konstrukte zur Synchronisation von Threads. Jede OpenMP Implementierung stellt zudem ein eigenes Application-Programming-Interface (API) zur Verfügung, um das Laufzeitverhalten der OpenMP Programme zu modifizieren (siehe Kasten: „Hello World“ in OpenMP). Der entscheidende Vorteil von OpenMP Parallelisierungen ist die Tatsache, dass das serielle Programm zu jeder Zeit erhalten bleibt. Der Nachteil ist, dass stets Teile des Programms seriell bleiben und somit der maximale Speedup durch das Gesetz von Amdahl begrenzt wird. Amdahls Gesetz [4] gibt eine Abschätzung des maximal zu erwartenden Speedups in Abhängigkeit des seriellen Programmteils. Eine gute Einführung in die OpenMP Programmierung findet sich in [5].

Zusammenfassung

Plant man seine serielle Anwendung für die zukünftigen Mehrkernsysteme zu parallelisieren, gibt es verschiedene Ansätze, die in Abhängigkeit von Kontrolle und Einfachheit das gesamte Spektrum abdecken. Vom einfachen OpenMP Ansatz bis zum detaillierten und komplexen Modell der Threadbibliotheken ist alles für den Entwickler verfügbar. Der gewählte Ansatz legt außerdem fest, ob man sich eher für einen inkrementellen Ansatz oder einen komplett neuen Entwurf entscheidet. Egal für welchen Multithreading Ansatz man sich entscheidet, man öffnet die Büchse der Pandora: Diese enthält eine neuen Klasse von komplexen Problemen, deren Lösung ein Umdenken im Programmentwurf, die Verwendung alternativer Werkzeuge zur Fehlersuche und neue Modelle zur Qualitätssicherung erfordert. Als Preis winkt allerdings eine automatische Steigerung der Ausführungsgeschwindigkeit der Anwendung, die weitgehend nur noch von der Anzahl der Kerne oder Prozessoren in einem Computer abhängt.

 

Edsger Dijkstra - Philosophen-Problem

 

Es sitzen 5 Philosophen an einem runden Tisch und jeder hat einen Teller. Es gibt insgesamt nur fünf Gabeln. Da aber jeder Philosoph zum Essen zwei Gabeln benötigt, können nicht alle gleichzeitig essen. Die Vorgehensweise beim Essen ist nun folgendermaßen definiert. Wenn ein Philosoph nach einer bestimmten Zeit hungrig wird, greift er zuerst zur linken Gabel und dann zur rechten Gabel und isst eine bestimmte Zeit. Nach Ablauf der Zeit legt er die Gabeln wieder zurück und wartet eine bestimmte Zeit bis er wieder zu essen beginnt. Die verschiedenen Zeiten können natürlich unterschiedlich lang sein. Sollte eine Gabel nicht an ihrem Platz liegen, so wartet er, bis die Gabel wieder frei ist.

Die Ablaufsteuerung, also die Definition, wer etwas tut, wie lang und wann, wird durch den Scheduling-Algorithmus definiert. Im einfachsten Fall kann es zu folgendem Muster kommen: Wenn alle fünf Philosophen gleichzeitig anfangen zu essen und die linke Gabel ergreifen, ist damit keine rechte Gabel mehr da und alle sind blockiert. Es kann auch je nach Scheduling-Algorithmus zu extrem komplizierten Abläufen kommen, bei denen erst nach langer Zeit eine Blockierung auftaucht. Zur Lösung dieser Probleme werden die typischen Zugriffssteuerungsmechanismen wie Mutexe oder Semaphoren verwendet. Eine ausführliche Beschreibung findet sich im Web oder in den meisten Büchern zur theoretischen Informatik.

 

„Hello World“ in OpenMP

 

Dies ist das klassische „Hello world“ Programm kompiliert mit dem Intel® Compiler 9.1. Um OpenMP Pragmas zu aktivieren, benötigt man den Compiler Switch (/Qopenmp für Windows). Der Compiler zeigt an, wenn er ein OpenMP Konstrukt erfolgreich parallelisiert hat. Zur Laufzeit ermittelt das OpenMP Runtimesystem durch die Anzahl der Prozessorkerne, auf wieviele Threads die Last verteilt wird. Dieses Verhalten lässt sich durch Setzen der Umgebungsvariable OMP_NUM_THREADS modifizieren.

hello_omp.c:

#include<stdio.h>

 

int main(){

 

#pragma omp parallel

{

printf ("Hello World\n");

}

}

 

Compile & Run:

C:\>icl /Qopenmp hello_omp.c

Intel(R) C++ Compiler for 32-bit applications, Version 9.1 Build 20060816Z Package ID: W_CC_C_9.1.030

Copyright (C) 1985-2006 Intel Corporation. All rights reserved.

 

[...]

hello_omp.c(5) : (col. 3) remark: OpenMP DEFINED REGION WAS PARALLELIZED.

[...]

 

C:\>set OMP_NUM_THREADS=4

C:\>hello_omp.exe

Hello World

Hello World

Hello World

Hello World

 

„Hello World“ mit Win32 threads

 

Um Win32 Threads zu erzeugen, muss man die Anzahl der zur Laufzeit verwendeten Threads im Programm definieren. Der Programmierer ist für die Erzeugung der Threads selbst verantwortlich. Die Synchronisation der Threads ist hier vereinfacht mit dem Aufruf der sleep() Funktion realisiert.

 

Hello_win32th.c:

#include <stdio.h>

#include <windows.h>

 

DWORD WINAPI helloFunc(LPVOID pArg){

printf("Hello World \n");

return 0;

}

 

int main(){

HANDLE hThread;

DWORD threadId;

int num_threads=4,i;

 

for ( i = 0; i < num_threads; i++){

hThread=CreateThread(NULL,0,helloFunc,(LPVOID)&i,0,&threadId);

}

Sleep(200);

return 0;

}

 

 

 

Dr. Mario Deilmann arbeitet seit 2003 als Senior Software Engineer bei der Firma Intel und ist im Bereich des technischen Consulting für die Intel Softwareprodukte tätig.

Links & Literatur

    [1] ISO / IEC 9945-1:1996(E) ANSI / IEEE Std 1003.1, 1996 Edition, Information technology Portable Operating System Interface (POSIX®) - Part 1: System Application Program Interface (API) [C Language]

    [2] David R. Butenhof: Programming with POSIX® Threads, Addison-Wesley

    [3] Olaf Neuendorf: Windows Multithreading mit C+ und C#, mitp-Verlag

[4] Gene Amdahl: Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities, AFIPS Conference Proceedings

    [5] Rohit Chandra et. al: Parallel Programming in OpenMP, Morgan Kaufmann