Herausforderungen bei Mehrkern-Rechnern

Nahezu alle Prozessoren, die in neueren Systemen zu finden sind, sind Mehrkern-Prozessoren, auf Servern werden auch mehrere Prozessoren verbaut. Eine möglichst gute Nutzung der Geschwindigkeitsvorteile der echten parallelen Ausführung stellt die Informatik vor verschiedene Herausforderungen.

Zunächst erfolgt ein kurzer Rückblick, weshalb eine Änderung des Prinzips zur Parallelität bei der Softwareentwicklung erforderlich ist. Danach werden die Herausforderungen sowie mögliche Lösungen für eine bessere Nutzung der neuen Architektur beschrieben. Abschließend erfolgt eine Zusammenfassung und ein kurzer Ausblick.

Historie

In der Vergangenheit wurden die Prozessoren durch die Hersteller von den Prozessoren beschleunigt. Dies wurde durch drei Strategien realisiert: Zum einen wurde der Takt erhöht, womit der Prozessor mehr Befehle in derselben Zeit ausführen kann. Damit wird auch der Prozessor schneller, allerdings steigt auch der Stromverbrauch. Darüber hinaus wird der sog. Cache vergrößert, wodurch die Zugriffszeiten auf häufig verwendete Speicheradressen reduziert werden. Die dritte Strategie besteht in dem Optimieren der Ausführung: So werden mehrere Befehle pro Takt-Zyklus ausgeführt, Befehle umgeordnet und Abzweigungen vorhergesagt.

Mit diesen Mitteln wurde die Ausführungsgeschwindigkeit von Programmen erhöht, ohne größere Veränderungen an den Programmen zu erfordern.

Das Erhöhen der Taktrate auf 4 GHz führte allerdings zu einer hohen Wärmeabgabe, die nur schwer kühlbar ist. Vor ca. zehn Jahren erfolgte aufgrund von diesen technischen Problemen eine Abkehr von der permanenten Erhöhung der Frequenz. Stattdessen begann man, mehrere Recheneinheiten in die Prozessoren zu “verbauen”. Damit ist es möglich, verschiedene Befehle echt parallel auszuführen. Der Vorteil gegenüber dem Verbauen mehrerer Einkern-Prozessoren liegt in der Kosten-Reduzierung: Für einen Mehrkernprozessor muss nur ein Sockel (Anschluss) verbaut werden. Einen Unterschied zwischen mehreren Kernen und mehreren Prozessoren gibt es für die Programme jedoch nicht. Heute werden bis zu 12 physiche Kerne in einen Prozessor verbaut.

Probleme und Herausforderungen

Allerdings können ältere Programme, die für einen Einkern-Prozessor geschrieben wurden, die Leistung eines Mehrkernprozessors oder von mehreren Prozessoren nicht optimal ausnutzen: Ein solches Programm besteht aus einer Befehlsfolge, die nacheinander abgearbeitet wird, und ist nicht für Parallelität geschrieben. In den Programmen müssen (z.T. größere) Veränderungen vorgenommen werden, damit von dem Programm mehrere Kerne gleichzeitig genutzt werden können.

Bei der Ausführung eines Programmes wird ein Prozess erstellt, der das Programm bearbeitet und einen zugewiesenen Speicherbereich hat. Einen Prozess, der keinen eigenen Speicherbereich hat, sondern den eines anderen Prozesses nutzt, nennt man Thread.

Bei einem Programm, welches für einen Mehrkern-Prozessor optimiert/geschrieben ist, besteht der Prozess (die Ausführung eines Programms) nicht nur aus einem, sondern aus mehreren Threads, die gleichzeitig ausgeführt werden. Bei der Entwicklung und Portierung von Software für Mehrkernprozessoren ergeben sich mehrere Herausforderungen:

  • Aufteilung von Operationen auf verschiedene Threads
  • Verwaltung von Abschnitten, die nur von einem Thread gleichzeitig betreten werden können. (Beispiel: I/O)
  • Algorithmen
  • Debugging

Aufteilung

Das Programm muss in verschiedene Teile aufgeteilt werden, die parallel ausführbar sind. Dafür unterscheiden wir zwei Sorten von Programmen: Zum einen die Programme, die Berechnungen auf Daten durchführen, und möglichst schnell Ergebnisse liefern sollen. Zum anderen gibt es Programme, die für Benutzerinteraktionen konzipiert sind. Dort ist der Fokus auf eine schnelle Reaktion auf Eingaben des Benutzers, wobei es hier meist nur wenig Daten zu verarbeiten gibt.

Bei Programmen, die Berechnungen durchführen ergeben sich drei Möglichkeiten, eine Parallelisierung zu realisieren: Zum einen lassen sich die Daten, die die Berechnungsgrundlage darstellen, auf mehrere Threads verteilen. Zum anderen ist es auch möglich, verschiedene Bearbeitungsschritte auf einem Datensatz zu parallelisieren. Die dritte Möglichkeit ist eine Mischform der beiden vorigen.

Eine solche Aufteilung ist bei Programmen, die eine Benutzeroberfläche haben, nicht sinnvoll, da die Operationen im Vorhinein nicht bekannt sind, und es meist keine größeren Datenmengen zu verarbeiten gibt. Dort ist es sinnvoll, eine Trennung zwischen der Darstellung der grafischen Oberfläche, der darunter liegenden Verarbeitung der Nutzereingaben (Events) sowie der dem Lesen und Schreiben von Daten des Festplatte zu haben. Damit kann der Nutzer die Oberfläche flüssig bedienen und das Programm kann in kurzer Zeit reagieren, während länger andauernde Operationen wie das Berechnen oder Schreiben von Daten auf die Festplatte “im Hintergrund” ausgeführt werden können.

Wechselseitiger Ausschluss

Ein (eher theoretisches) Problem bei der Ausführung von parallelen Programmen besteht darin, sicherzustellen, dass nicht zwei Threads sich in einem Abschnitt befinden, in dem beide auf eine Ressource zugreifen wollen. Dies ist beispielsweise dann der Fall, wenn zwei Threads in dieselbe Variable im Hauptspeicher oder in dieselbe Datei schreiben sollen. Einen solchen Abschnitt nennt man kritischen Abschnitt, bei dem ein wechelseitiger Ausschluss (mutual exclusion) sicherzustellen ist. Für dieses Problem existieren im Wesentlichen zwei Lösungsansätze, die i vielen Bibliotheken oder Laufzeitumgebungen implementiert sind, nämlich das Semaphor und das Monitor-Konzept. Das Konzept des Semaphor sieht zwei atomare, ununterbrechbare und nicht gleichzeitig ausführbare Operationen vor: Vor dem Eintreten in einen kritischen Abschnitt ist die Funktion P aufzurufen, die prüft, ob kein anderer Thread in diesem kritischen Abschnitt ist, und ggf. den Thread blockiert, bis der andere Thread den Abschnit verlassen hat. Beim Verlassen des Abschnitts ist die Funktion V aufzurufen, wodurch andere wartende Threads freigegeben werden.

Algorithmen

Bei der Paralellisierung kann man, wie oben beschrieben, nach Daten und nach Operationen aufteilen. Die Vorraussetzung ist allerdings, dass die zugrundeliegenden Algorithmen und mathematischen Verfahren paralellisierbar sind. So lässt sich beispielsweise das Jacobi-Verfahren zur iterativen Lösung von linearen Gleichungssystemen besser parallelisieren als das Gauss-Seidel-Verfahren, da bei letzterem Datenabhängigkeiten innerhalb einer Iteration bestehen.

Debugging

Eine Herausforderung bei der Entwicklung von Programmen ist das Finden und Beheben von Fehlern (Debugging). Bei parallelen Programmen kann man (Programmier-)Fehler allerdings schlecht bestimmen, denn der Fehler kann auch mal nicht auftreten: Ein paralleler Thread kann sich mal in einem solchen Punkt befinden, wo der Fehler auftritt und mal an einem anderen Punkt, wo kein Fehler auftritt. Dies ist möglich, da der Thread echt gleichzeitig ausgeführt wird und die Ausführungsgeschwindigkeit variiert.

Zusammenfassung und Ausblick

Herkömmliche Programme, die für ältere Einkern-Prozessoren geschrieben wurden, nutzen von sich aus auf den mordernen Mehrkern-Prozessoren nur einen Bruchteil der verfügbaren Leistung. Um kürzere Ausführungszeiten zu erhalten, müssen bei Berechnungs-Intensiven Programmen die Daten oder die Operationen parallelisiert werden, während bei Programmen für die Benutzer-Interaktion die Trennung zwischen Interaktion und Verarbeitung der Operationen zu fokussieren ist. Neben der Beachtung von kritischen Abschnitten ist auch das Optimieren von Algorithmen für eine verteilte Ausführung von zentraler Bedeutung. Speziell für die Entwickler von Software ist das Debugging von parallelen Programmen eine Herausforderung.

In der Zukunft werden die Prozessoren wahrscheinlich noch mehr Kerne besitzen, weshalb eine entsprechende Optimierung von Programmen durch eine Aufteilung auf mehrere Threads für die Zukunft unverzichtbar ist.

Referenzen