Programmieren für Multi-Core-Prozessoren

Die Leistung von Computersystemen steigt seit Jahren kontinuierlich an. Dies betrifft nahezu alle Komponenten der Rechner. Am deutlichsten ist der Leistungsgewinn bei den Prozessoren, dem Arbeitsspeicher und den Festplatten zu verfolgen.

Aber auch die Grafikkarten, Netzwerkanbindungen und weitere Kommunikationssysteme, wie etwa USB- oder Wireless-Anbindung verzeichnen rapide steigende Performance-Zuwächse. Die zunehmende Leistungsfähigkeit der Rechner führt zu immer neuen Anwendungsfeldern und Applikationen mit komfortableren Benutzeroberflächen.

Erzielt wurden diese Leistungsgewinne meist auf verschiedenen Wegen:

• einer Erhöhung der Verarbeitungsgeschwindigkeit durch schnellere Taktung,

• einer größeren Funktionsvielfalt,

• einer Verlagerung von Funktionen in die Hardware,

• sowie der Erhöhung der Kapazitäten wie bei Caches, Arbeitsspeicher oder Festplatten.

Meist führten diese genannten Verbesserungen aber auch zu einem höheren Stromverbrauch der IT-Baugruppen. Stromfluss allerdings erzeugt Wärme, die durch Kühlung wieder abgeführt werden muss. Das wiederum erhöht den Strombedarf und damit die Betriebskosten. Um den Stromverbrauch bei den CPUs zu senken, verfolgen die CPU-Hersteller seit einigen Jahren eine andere Strategie und orientieren sich dabei auch an den Techniken der Parallelverarbeitung.

In dieser mehrteiligen Reihe zur Programmierung für Multi-Core-Prozessoren führen wir Sie nach und nach durch die Besonderheiten der Multi-Core-Programmierung. Angefangen bei den wichtigsten Grundlagen der verschiedenen Parallelisierungs-Verfahren in Prozessoren in diesem ersten Teil. Im nächsten Teil befassen wir uns mit der notwendigen Modularisierung in Applikationen und gehen auf das .Net-Framework ein. Nach diesen beiden einführenden Artikeln geht es ans Eingemachte: Deadlocks, Race Conditions und Zugriffe auf die .Net-Thread-Implementation mit Locking, Delegates, Timern und asynchronen Events.

Parallelverarbeitung auf Instruktions-Ebene

Um die Parallelverarbeitung voranzutreiben, wurden verschiedene Techniken eingeführt, die eine Parallelisierung eines sequentiellen Programms ermöglichen sollten. Als Parallelverarbeitung in diesem Kontext wird jegliche Form der parallelen Abarbeitung von Code verstanden.

Dazu zählt auch die vorbereitende Analyse der Instruktionen oder das Laden aus dem Arbeitsspeicher. Die ursprünglichen Ansätze der Parallelverarbeitung subsumieren sich in den Techniken des „Instruction Level Parallelism“ (ILP) mit „Instruction Pipelining“, „Speculative Execution“, “Out-of-order execution” oder „Branch Prediction“. Dabei wird versucht, durch die parallele Abarbeitung von Instruktionen einen Zeitvorteil zu erreichen.

Beim „Instruction Pipelining“ etwa wird der Code durch eine Pipeline geschleust und so schon vor der Ausführung untersucht. Passende Instruktionen, die sich parallel ausführen lassen, benötigen weniger Takte und Gesamtdurchlaufzeit.

In der „Out-of-order execution“ schließlich führt man Instruktionen immer dann parallel aus, wenn sie keine Datenabhängigkeit besitzen. Die Initiierung einer Variablen für eine Schleife könnte so, wenn es nicht bereits durch den Compiler oder Loader passiert, als „Out-of-order execution“ abgearbeitet werden.

Ratespielchen bei der Parallelverarbeitung

In der „Speculative Execution“ werden die Instruktionen bereits im Vorfeld ausgeführt, selbst wenn noch nicht sicher ist, ob die Instruktion tatsächlich benötigt wird. Dies gilt immer dann, wenn Verzweigungen oder Sprünge die lineare Programmausführung unterbrechen.

Bei der „Branch Prediction“ versucht man das Sprungziel bei einer Codeverzeigung vorauszusehen, wie sie etwa bei den Instruktionen eines „If-else“ oder „Switch-case“ auftritt. Dies basiert auf der Analyse der vergangenen Befehle, unterstützt durch eine Berechnung der Wahrscheinlichkeit für den nachfolgenden Code. Ist das Sprungziel bereits im Vorfeld bekannt, so kann die weitere Ausführung des Codes an dieser Stelle auch früher einsetzen. „Branch Prediction“ wird meist in Verbindung mit der „Speculative Execution“ eingesetzt.

SIMD (Single Instruction, Multiple Data) ermöglicht die parallele Bearbeitung von Daten mit äquivalentem Aufbau. Die SIMD-Konzepte wurden ursprünglich bei den Großrechnern und Supercomputern angewandt und fanden dann auch Eingang in die x86-Architektur. SIMD ermöglicht die gleichzeitige Bearbeitung der parallelen Datenströme. Eingesetzt wird SIMD vor allem bei der Bearbeitung von Bild-, Ton- und Videodaten.

Code-Optimierungen

Neben diesen Verfahren steht die Code-Optimierung, die durch ausgefeilte Compiler-Techniken erreicht wird. Im folgenden Beispiel etwa sind die ersten beiden Operationen parallel ausführbar, da diese keine Abhängigkeit (Data Dependency) zueinander aufweisen. Bei der Parallelisierung dieses Codes muss aber unbedingt sichergestellt werden, dass die dritte Anweisung - die Summenbildung - erst dann ausgeführt wird, wenn die beiden Teilsummen ermittelt sind.

C = A + B
Z = X * Y
Sum = C + Z

Das Ziel der Compiler- und der CPU-Optimierung ist es, möglichst viele dieser parallelisierbaren Code-Abschnitte ausfindig zu machen und parallel abzuarbeiten. Dies ist allerdings nicht einfach, denn die eigentliche Programmierung und nahezu alle heute verwendeten Programmiersprachen und begleitenden Entwicklungs-Tools sind an sequenziellen Abläufen ausgerichtet.

Die Umsetzung eines sequentiellen Programms in parallele Codestücke wird durch die Techniken des „Instruction Level Parallelism“ zwar gefördert, hat aber auch ihre besonderen Anforderungen. Moderne CPUs setzen sich meist aus mehreren Modulen zusammen. Dies sind der Registersatz zur Zwischenspeicherung der Daten, die Arithmetical and Logical Unit (ALU, Rechenwerk) zur Berechnung der Operationen, sowie eine Dekodierlogik für die Befehle.

Caching

Um schneller an Daten und Instruktionen heranzukommen, werden außerdem Zwischenspeicher (Caches) eingesetzt. Diese sind heute immer mehrstufig aufgebaut und werden meist als first, second oder third Level Cache bezeichnet.

Generell gilt: Je näher der Cache an der CPU ist, umso schneller kann diese darauf zugreifen, aber umso kleiner ist er auch. Bei heutigen Systemen umfassen die Level-1-Caches circa 32 KByte, Level-2-Caches reichen schon an einige MBytes heran und Level-3-Caches können mehr als 16 MByte groß sein.

In keinem Fall allerdings wird der Cache jemals die Größe des Arbeitsspeichers erreichen, der heute mehrere Gigabyte umfasst. Der Cache dient, wie erwähnt, nur dem schnelleren Zugriff auf benötigte Daten und Instruktionen.

Bei Verzweigungen, also der Fortführung des Codes an einer anderen Stelle, sorgen spekulative Ausführung und Branch Prediction dafür, dass der Cache rechtzeitig mit den benötigten Inhalten gefüllt wird. Die Verwaltung der Caches erfolgt durch die CPU und läuft unbemerkt vom Programmcode.

Dennoch sollte sich ein Software-Entwickler über die Existenz und Arbeitweise des Caches unbedingt im Klaren sein, denn viele Verzweigungen oder Sprünge im Code ziehen unweigerlich viele Cache-Operationen nach sich. Auch beim parallelen Zugriff auf Daten muss der Inhalt des Caches berücksichtigt werden.

Der nächste Schritt: Hyper-Threading

Einen Schritt weiter als Instruction Level Parallelism gehen die Techniken des Hyper-Threading (Hyper-Threading-Technology - HTT), wie es Intel in seinen CPUs der Xeon und Pentium-4-Reihe implementierte. Hierbei wird durch Hardware-Unterstützung in der CPU eine bedingte Parallelverarbeitung realisiert.

Der Leistungsgewinn wird dadurch erzielt, dass CPU-Bestandteile wie der Decoder dupliziert werden. Zu diesen duplizierten Einheiten der CPU zählen all jene, die den Status der CPU und ihrer Ausführung speichern, damit also auch CPU-Register. Dies sind unter anderem die Control Register mit den Flags und die allgemeinen Arbeitsregister.

Nicht dupliziert werden die Ausführeinheit und die ALU. Die Duplizierung soll dafür sorgen, dass die Ausführungseinheit (Execution Unit) der CPU besser ausgelastet wird. Ohne Hyper-Threading würde beispielsweise bei einem Cache-Fehler (Cache-Miss) die Execution Unit untätig (idle) sein, bis der Cache gefüllt ist.

Begleitend dazu sind beim Hyper-Threading die Registersätze in den CPUs verdoppelt. Somit ist eine parallele Ausführung der Operationen möglich. Nach Angaben von Intel wird beim Pentium 4 durch Hyper-Threading eine Leitungssteigerung von bis zu 30 Prozent gegenüber ansonsten identischen Pentium 4 ohne Hyper-Threading erreicht.

Gegenüber dem Betriebssystem erscheint ein Pentium-4 mit Hyper-Threading als zwei Prozessoren. Hyper-Threading dient aber auch wie ILP der parallelen Abarbeitung eines Programms auf einer CPU. Trotz der Einführung des Multi-Core-Designs wird Hyper-Threading auch in Zukunft existieren. In dem für dieses Jahr angekündigten Nehalem-Design wird Hyper-Threading erneut enthalten sein und soll in bis zu 8 Kernen mindestens 16 Threads parallel ausführen.

Duplizierung des CPU-Kerns in Multi-Core-CPUs

Beim nächsten Schritt der Parallelverarbeitung nun dupliziert man gar ganze Rechenkerne in Multi-Core-CPUs. Im Gegensatz zum Hyper-Threading werden nun also nicht mehr ausgewählte Teile einer CPU, sondern die gesamte CPU dupliziert. Multi-Core-CPUs weisen folglich auch mehrere Execution-Units auf.

Die Execution-Unit wiederum ist für die Ausführung der Instruktionen zuständig. Multithreaded Programme, die auf eine Multi-Core-CPU ausgeführt werden, laufen somit vollständig parallel. Jeder dieser Threads wird dann auf einem eigenen CPU-Core, mit eigener Execution-Unit und eigenen Registersatz ausgeführt. Kombiniert mit der Smart Cache Technologie von Intel können Caches dennoch sehr effizient genutzt werden ohne Datensätze unnötig in verschiedenen Cache-Bereichen abzulegen und updaten zu müssen. Auch erlaubt es eine dynamische Cachezuweisung pro CPU-Kern. Damit steht der optimalen Nutzung der Caches und somit der Kerne kaum noch etwas im Wege.

Das Prinzip der Multi-Core-CPUs ist einfach und ist in unserer modernen Welt allgegenwärtig. Die Erhöhung der Taktrate entspricht einer Beschleunigung des Fließbands der industriellen Produktion. Wenn man dabei aber, aus welchen Gründen auch immer, an Grenzen stößt, so platziert man kurzerhand die gesamte Fertigungstrasse ein zweites, drittes oder viertes Mal, just wie die Kassen im Supermarkt und den zahlungswilligen Käufern. So auch bei den Prozessoren, nur spricht man da von Multi-Core. Ihre „Kunden“ sind die anstehenden Programme, die durch die Prozessoren bedient oder besser abgearbeitet werden. Je mehr Prozessoren oder Kassen, umso höher der Gesamtdurchsatz. Soweit die Theorie. Im nächsten Teil dieser Reihe widmen wir uns unter anderem der Parallelverarbeitung in der Praxis. (mha)