Einleitung
Technische Entwicklung
Vor nicht ganz zehn Jahren geriet das "Megahertz-Rennen" zwischen den Prozessorherstellern allmählich ins Stocken. Aufgrund der steigenden Taktfrequenz und der kleiner werdenden Strukturen schien vor allem die hohe Wärmeentwicklung die Leistungsgrenzen der damaligen Prozessoren aufzuzeigen. Als Lösung dieses Problems wurden Strategien zur Parallelverarbeitung entwickelt. Die Grundidee hierbei ist, dass zwei parallele Einheiten mit einer Frequenz f die selbe Arbeit leisten wie eine Einheit mit der Frequenz 2*f.
Im Jahr 2004 zeigte AMD den ersten Dual-Core-Prozessor mit x86-Befehlssatz und kurze Zeit später hielten erste Dual-Core-Prozessoren Einzug in den Desktop-Markt. Aktuell (Januar 2010) sind für den Desktop-Markt Multi-Core-Prozessoren mit bis zu vier physikalischen Kernen auf einem Chip erhältlich.
Die volle Leistung dieser Prozessoren kann mit den weit verbreiteten sequenziellen Algorithmen und Programmen jedoch nicht ausgeschöpft werden, da diese nur von einem Kern ausgeführt werden. In Programmiersprachen wie C oder Java verwendet der Softwareentwickler expliziten Parallelismus und nutzt die durch die Sprache gegebenen Möglichkeiten zur Arbeit mit Prozessen und Threads. Da sich nicht jeder Algorithmus effizient parallelisieren lässt, die gegebenen Möglichkeiten oft erheblichen Mehraufwand bei der Entwicklung verursachen und nicht zuletzt auch bis vor fünf Jahren auf Desktop-Systemen keinen Geschwindigkeitszuwachs bei der Ausführung der Programme möglich war, ist die Parallelisierung in der Anwendungsentwicklung nicht sehr weit verbreitet.
Um zukünftige Prozessoren besser Auslasten zu können, müssen Programmiersprachen und Bibliotheken entwickelt werden, die dem Entwickler die Parallelisierung von Programmen erleichtern.
OpenMP
OpenMP ist eine Programmierschnittstelle für die Entwicklung paralleler Programme in C, C++ und Fortran für Shared-Memory-Systeme. Die Spezifikationen werden gemeinsam von vielen namhaften Hard- und Softwareherstellern definiert und dadurch von fast allen kommerziellen Compilern, sowie der GNU Compiler Collection, unterstützt.
OpenMP nutzt spezielle Compiler-Direktiven zur Parallelisierung. Dies hat den Vorteil, dass der Code in der Regel auch von Compilern übersetzt werden kann, die OpenMP nicht unterstützen. Zusätzlich ermöglicht dies ein schrittweises Parallelisieren, da der ursprüngliche Code nicht modifiziert werden muss, sondern nur die Compiler-Direktiven an den richtigen Stellen hinzugefügt werden müssen. Dies hat jedoch auch den Nachteil, dass nur sehr grob Parallelisiert werden kann.
Zielsetzung
In der Algorithmentheorie werden bevorzugt nur asymptotische Laufzeiten ohne genauere Betrachtung der Implementierung angegeben. Viele Konstanten und Faktoren werden hierbei nicht genauer untersucht. Dadurch ist es möglich, dass ein asymptotisch langsamer Algorithmus im realen Einsatz für bestimmte Eingaben (z.B. sehr kleine) schneller ist als sein asymptotisch schnelleres Pendant.
Ziel dieser Arbeit ist die praktische Laufzeitmessung und dessen Auswertung einer sequenziellen und parallelen Implementierung des Mergesort-Algorithmus. Die sequenzielle Implementierung soll mit wenig Aufwand und mit Hilfe von OpenMP parallelisiert werden.
Ein Abriss der Möglichkeiten und des Funktionsumfanges von OpenMP ist nicht beabsichtigt.
