C-Code für die Parallelisierung analysieren

Mit dem Vormarsch von Multicore-Architekturen rückt auch das Thema Parallelisierung von Software wieder in den Mittelpunkt des Interesses. Wo aber sollte man für eine effiziente Parallelisierung ansetzen?

Anbieter zum Thema

Axivion GmbH

Parasoft® Deutschland GmbH

RTI Real-Time Innovations

Die Idee ist nicht neu: Ein Ansatz zur Beschleunigung der Programmausführung führt darüber, den Parallelismus auszunutzen, der in einem Programmfluss naturgemäß vorliegt. Wäre es möglich, die Bereiche eines Programms ausfindig zu machen, die parallel ausgeführt werden können, den Programmfluss dementsprechend umzuorganisieren und Hardware bereitzustellen, um jedes parallele Fragment zu hosten, sollte die Gesamtaufgabe in wesentlich kürzerer Zeit erledigt werden.

In der Praxis erweist sich dieses Problem als recht hartnäckig. Für geraume Zeit musste man sich darüber keine großen Gedanken machen, da die Halbleiterindustrie immer mehr Datenverarbeitungsleitung durch schnellere CPU-Taktraten bereitstellte. Diese Ära geht nun dem Ende entgegen. Die Anbieter von Mikroprozessoren nutzen Multicore-Architekturen, um den Datendurchsatz weiter zu erhöhen. Die Verfügbarkeit dieser Hardware-Plattform, auf der parallele Tasks ablaufen können, steigert wieder das Interesse daran, Programmflüsse zu parallelisieren.

Ob sich ein gesamtes sequenzielles Programm in parallel laufende Teile zerlegen lässt, hängt davon ab, ob diese im Rahmen der Programmausführung zueinander in Beziehung stehen. Damit sind die Abhängigkeiten innerhalb eines Programms von Bedeutung. Diese zu verstehen ist bei der Entwicklung einer parallelen Implementierung entscheidend, die ja funktional identisch mit der ursprünglichen sequenziellen Version sein soll.

Das Amdahlsche Gesetz gilt immer noch

Das Amdahlsche Gesetzt besagt, dass die Leistungssteigerung, die durch parallele Datenverarbeitung erzielt werden kann, durch die Programmteile beschränkt wird, die in einer bestimmten Reihenfolge ablaufen müssen. Für n Prozessoren ist die einzige Möglichkeit, das Programm n Mal so schnell laufen zu lassen, das Aufteilen in n voneinander unabhängige Teilstücke gleicher Länge – was fast nie möglich ist. Programmierer müssen sich daher mit einer Geschwindigkeitszunahme zufrieden geben, die etwas weniger als n Mal so schnell ist. Die Herausforderung besteht also darin, diese Geschwindigkeitszunahme zu maximieren.

In einem Programm gibt es Bereiche, deren Performance entscheidend ist, wie auch solche, die weniger kritisch sind. Um die kritischen Teile so schnell wie möglich ablaufen zu lassen setzt es voraus, dass die nicht kritischen Teile beseitigt sind. Alle Anstrengungen beim Parallel-Computing beruhen darauf, vermeidbare Abhängigkeiten zu beseitigen und jene zu bearbeiten, die übrigbleiben.

Die ideale Programmiersprache

Die verwendete Programmiersprache beeinflusst die Analyse des Programms prinzipiell nicht. Eine ideale parallele Programmiersprache würde aber kein Analyse-Tool erfordern – die Abhängigkeiten wären bei der Überprüfung offensichtlich. ANSI C ist von diesem Ideal weit entfernt, jedoch die gängigste Sprache zur Programmierung von Embedded-Systemen. In der Praxis ist das Problem der Parallelisierung von neuem und bereits bestehenden Codes demnach ähnlich.

Threads und Prozesse

Eine Parallelisierung erzeugt einen Programmbereich, der gleichzeitig mit anderen Bereichen ausgeführt werden muss. Ein solcher Bereich kann als Thread oder Prozess implementiert werden. Threads sind einem Prozess untergeordnet und teilen sich einen gemeinsamen Speicherbereich; Prozesse sind vollständig unabhängig.

Ein Multicore-Programm lässt sich als Einzelprozess mit mehreren Threads implementieren oder als Gruppe kleiner Single-Thread-Prozesse in einer asymmetrischen Multiprocessing-Umgebung (AMP), die prozessinterne Kommunikation (IPC) nutzt, um erforderliche Informationen auszutauschen. Eine Kombination aus beiden ist ebenfalls möglich.

Wo für die Parallelisierung ansetzen?

In welchem Bereich sollten die Möglichkeiten für eine parallele Ausführung näher untersucht werden? Auf niedrigster Stufe kann über Parallelismus auf Befehlsebene eine Neuordnung und Parallelisierung von Low-Level-Befehlen stattfinden. Dies hängt jedoch stark von der Architektur des Target-Prozessors ab und wird von Compilern bereits berücksichtigt. Hier ist es schwierig, zusätzliche Vorteile zu erzielen.

Das andere Extrem: Werden sehr große Programmteile untersucht, hängen diese meist immer voneinander ab, sobald die Verarbeitung nicht triviale Bestandteile enthält.

Ein günstiger Zugriffspunkt ist die Grenze zwischen Prozessor und Speicher. Während der Prozessor selbst und seine Register über den Compiler verwaltet werden, wird die Speicherarchitektur nicht unbedingt durch den Compiler berücksichtigt. Hier ist die Untersuchung von Beziehungen hilfreich. Die zwei entscheidenden Befehle sind hier „Store“ und „Load“.

Der Compiler verwaltet die Variablen in den Prozessorregistern; sobald diese aber in den Speicher geladen oder aus diesem gelesen werden, bietet sich die Gelegenheit, die entstehenden Abhängigkeiten näher zu untersuchen. Dieses Konzept kann um die Peripherie, die oft im Speicher abgebildet ist, erweitert werden: Jedes mal, wenn eine Variable den Prozessor-/Compilerbereich verlässt, wird diese interessant.

Eine weitere Frage ist, wie groß ein Code-Block sein darf, um sinnvoll analysiert zu werden. Es ist üblich, das Programmverhalten auf Funktionsebene zu untersuchen. Ein Großteil der Datenverarbeitung wird aber vor allem bei Embedded-Systemen durch Schleifen abgearbeitet. Diese sind von speziellem Interesse, wenn herausgefunden werden muss, wie ein Programm parallelisiert werden kann.

Statische und dynamische Analyse

Vieles über das Verhalten eines Programms lässt sich durch Überprüfung oder statische Analyse lernen. Dabei können aber kritische Verhaltensweisen übersehen werden, vor allem in Bezug wie sich Pointer und andere speicherbezogene Befehle in Echtzeit verhalten, die sich nur durch eine dynamische Analyse erkunden lassen, bei der untersucht wird, was passiert, während ein Programm einen bestimmten Datensatz ausführt.

Der Schlüssel für eine effiziente Parallelisierung sequenziellen Codes sind Abhängigkeiten, die unterschiedlicher Art sein können. Verwendet eine Berechnung das Ergebnis einer anderen Berechnung, muss diese mit der Ausführung warten, bis das vorhergehende Ergebnis vorliegt: diese Berechnungsabhängigkeit basiert auf dem Berechnungsfluss des Programms.

Um Einblick in Events zu erlangen, ist es hilfreich, wenn eine Rechenabhängigkeit mit einem Ladebefehl beginnt und einen Wert aufrecht erhält, mit dem gearbeitet wird bis die Sequenz in einem Speicherbefehl endet. Diese Art der Abhängigkeit wird über die statische Analyse identifiziert.

Berechnungsabhängigkeiten und Pointer

Die nächste Art der Abhängigkeit ist weniger offensichtlich und setzt sich aus der schwierig verfolgbaren Aktivität zusammen, die vor allem mit Pointern in Bezug steht. Vor allem die Programmiersprache C erlaubt die undisziplinierte, unstrukturierte Verwendung von Pointern in einer Art, die je nach Sichtweise als kreativ oder nachlässig bezeichnet werden kann.

Eine solche Verwendung ist die größte Einzelursache unerwarteter, schwer auffindbarer Fehler und Probleme bei der Parallelisierung sequenzieller Programme. Sie lassen sich über Compiler und Standard-Profiler nicht handhaben.

Frühere Versuche, die von Pointern verursachten Probleme zu vermeiden, mündeten darin, Pointer zu verbieten. Ein Entwickler musste dann erheblichen Aufwand in die Umprogrammierung stecken – und war dann möglicherweise nicht einmal der Original-Autor des Codes, was ihm auch keine Einsicht in die ursprünglichen Programmierabsichten brachte.

Ein besserer Ansatz ist die getrennte Analyse des Pointer-Verhaltens und das Auffinden der dazugehörigen kritischen Abhängigkeiten. Durch ihren Bezug zu Pointern und Speicherzugriff bezeichnet man sie als Speicherabhängigkeiten. Sie beginnen mit einem Speicherbefehl, der typischerweise (aber nicht immer) ein Pointer-Write ist und endet mit einem oder mehreren Ladebefehlen, die typischerweise Pointer-Referenzen sind.

Diese Abhängigkeiten sind deshalb nicht statisch analysierbar, da viele Pointer während der Programmausführung jederzeit auf die gleiche Adresse verweisen können und jeweils einen anderen Namen haben. Damit ist eine dynamische Analyse erforderlich, um festzustellen, was auf eine bestimmte Adresse geschrieben wird oder was von dieser gelesen wird.

Da dieses Speichern von Daten für das spätere Laden eigentlich eine Datenkommunikation von einem Programmteil zu einem anderen ist, bedeutet eine fehlerhafte Parallelisierung, dass einige Programmteile nicht die korrekten Daten enthalten. Wird ein Programm ohne die richtige Inbezugnahme dieser Abhängigkeiten parallelisiert, verfälscht sich das Verhalten soweit, dass ein Debugging wesentlich erschwert wird.

Diese zwei wesentlichen Abhängigkeitskategorien beziehen sich auf die Daten, die zur Verarbeitung zur Verfügung stehen, d.h. auf das Warten des Datenlesens. Das Gegenteil kann auch zutreffen: Ein Datenstück, das überschrieben wird, muss eventuell seinen Wert behalten, bis dieser nicht mehr benötigt wird. Dabei wird ein Write-Befehl verzögert, bis alle erforderlichen Lese-Befehle abgeschlossen sind. Diese Situation wird „Anti-Abhängigkeit“ genannt.

Eine andere Art von Abhängigkeit involviert die (implizite) Initialisierung des Programms vor dem Ablauf – über das vorherige Laden von Variablen. Bibliotheksaufrufe können auch Abhängigkeiten hervorrufen, die für den korrekten Programmablauf kritisch oder nicht kritisch sein können. So wird z.B. ein printf-Aufruf dann von Bedeutung, wenn die Druckreihenfolge eine wichtige Rolle spielt, aber nicht, wenn nur das Drucken entscheidend ist.

Schleifen und schleifenbezogene Abhängigkeiten

Schleifen lassen sich oft parallelisieren, um die Performance zu verbessern. Jede Iteration einer Schleife lässt sich einer anderen Task zuweisen. Bestehen zwischen den Iterationen keine Abhängigkeiten, kann jede Iteration genau zur gleichen Zeit erfolgen. Es gibt eine wichtige Art von Speicherabhängigkeit oder Anti-Abhängigkeit: der Verbrauch innerhalb einer Iteration einer Schleife, die einen bestimmten Wert einnimmt, der in einer anderen Iteration entstand.

Die Existenz solcher schleifenbedingten Abhängigkeiten macht diesen Programmbereich nicht unbedingt zu einem hoffnungslosen Fall für die Parallelisierung. Es ist jedoch eine Feineinstellung der Analyse erforderlich, z.B. die Einführung von Konzepten wie das der „Abhängigkeitsdistanz“. Dabei handelt es sich um die Anzahl an Iterationen einer Schleife innerhalb eines Programms, die Daten generieren und diese wieder anfordern.

Verschachtelte Schleifen machen die Analyse noch komplexer, die datenzentrisch sein muss und das Erstellen und Anwenden jedes Datenelements verfolgen muss. Programme können zahlreiche verschachtelte Schleifen aufweisen, wobei die verarbeiteten Daten über mehrere Hierarchie-Ebenen von der innersten zur äußersten Schleife weitergegeben werden.

Eine sinnvolle Analyse bereitstellen

Das einfache Abbilden eines Informationsflusses durch diese verschiedenen Abhängigkeitstypen, die durch eine dynamische Analyse ausfindig gemacht werden, ist eine Herausforderung. Dieser hat sich Vector Fabrics’ Analyse-Software vfAnalyst angenommen. Die Visualisierung von Abhängigkeiten und anderer wichtiger Bestandteile vereinfacht die sonst schwierige Aufgabe für Entwickler und Programmierer – selbst wenn es sich um die gleichen Personen handelt, die den Code geschrieben haben oder gerade bearbeiten. Herkömmliche Software-Profiling-Techniken können völlig unnütz sein und sind bei der Parallelisierung von geringem Wert.

Code zu schreiben, der bei seiner Ausführung einen komplexen, verschachtelten Datenaustausch hervorruft, kann recht schnell geschehen. Nach einer manuellen Inspektion kann dies aber zu Parallelisierungsmöglichkeiten führen, die sich als äußerst produktiv erweisen.

* *Mike Beunder ist CEO und Mitbegründer der Software-Firma Vector Fabrics

(ID:23586410)