Programmierstrategien für Multicore-Prozessoren: Pipelining

In der Zeit von Multicore-Prozessoren und multithreading-fähigen Anwendungen müssen Programmierer immer wieder überlegen, wie sie am besten die Leistung von hochmodernen CPUs für die Entwicklung ihrer Applikationen nutzen. Obwohl die Strukturierung parallelen Programmcodes in traditionellen textbasierten Sprachen schwer zu programmieren und darzustellen sein kann, wird es durch grafische Entwicklungsumgebungen wie NI LabVIEW zunehmend möglich, die von Anwendern benötigte Entwicklungszeit zu verkürzen und Ideen zügig umzusetzen.

Da LabVIEW aufgrund des Datenflusses einen parallelen Charakter aufweist, ist die Programmierung multithreading-fähiger Applikationen in der Regel eine relativ einfache Aufgabe. Unabhängige Tasks auf dem Blockdiagramm (Prinzipschaltbild) werden automatisch parallel ausgeführt und erfordern keine zusätzliche Arbeit vom Programmierer. Wie verhält es sich aber bei Programmcode, der nicht unabhängig ist? Was kann bei der Implementierung sequenziell ablaufender Anwendungen getan werden, um die Leistung von Multicore-CPUs auszunutzen?

Eine weit verbreitete Technik zur Leistungsverbesserung sequenzieller Programmaufrufe ist Pipelining. Einfach ausgedrückt ist Pipelining der Prozess der Aufteilung eines sequenziellen Tasks in konkrete Stufen, die ähnlich einem Fließband ausgeführt werden können.

Im folgenden Beispiel werden Automobile auf einem automatisierten Fließband gefertigt. Das Ziel besteht darin, ein vollständiges Auto zu bauen. Die Aufgabe kann aber in drei konkrete Stufen aufgeteilt werden: Bau des Fahrgestells, Einbau der Teile (wie Motor etc.) und Lackierung.

Es wird davon ausgegangen, dass der Bau des Fahrgestells, die Installierung der Teile sowie die Lackierung jeweils eine Stunde dauern. Somit würde beim Bau jeweils eines Fahrzeugs die Fertigstellung drei Stunden in Anspruch nehmen (siehe Abbildung 1).

Abb. 1: In diesem Beispiel (ohne Pipelining) dauert der Bau eines Fahrzeugs drei Stunden.

Wie kann dieser Prozess verbessert werden? Eine Überlegung wäre, eine Station für das Fahrgestell, eine für die Installation und eine für die Lackierung einzurichten. Dann kann ein Fahrzeug lackiert werden, während bei einem anderen die Teile eingebaut werden und beim dritten das Fahrgestell konstruiert wird.

Zwar werden für die Fertigstellung jedes Autos immer noch drei Stunden benötigt, doch kann nun pro Stunde ein Auto gebaut werden, statt nur eins alle drei Stunden. Dadurch verbessert sich der Durchsatz beim Fertigungsprozess um das Dreifache. Dies ist ein stark vereinfachtes Beispiel. Weitere Details zum Pipelining werden im Abschnitt „Wesentliche Punkte beim Pipelining“ aufgeführt.

[+] Bild vergrößern

Abb. 2: Pipelining kann den Durchsatz einer Anwendung stark erhöhen.

Dasselbe Pipelining-Konzept kann auf jede LabVIEW-Applikation angewendet werden, bei der ein sequenzieller Task ausgeführt wird. Das bedeutet im Wesentlichen, dass Schieberegister und Feedback-Knoten von LabVIEW eingesetzt werden, um aus jedem Programm ein „Fließband“ zu machen. Die folgende Konzeptdarstellung zeigt, wie eine Pipeline-Ausführung einer Beispielanwendung auf mehreren CPU-Kernen möglicherweise aussehen kann:

Abb. 3: Timing-Diagramm für eine Pipeline-Ausführung einer Anwendung auf mehreren CPU-Kernen

  Werden reale Multicore-Anwendungen mithilfe von Pipelining erstellt, muss ein Programmierer mehrere wichtige Punkte berücksichtigen. Der Ausgleich von Pipeline-Stufen und die Verringerung des Speichertransfers zwischen Kernen sind besonders entscheidend bei der Verwirklichung von Leistungssteigerungen mithilfe des Pipelinings.

Ausgleich der Pipeline-Stufen

Sowohl beim Beispiel der Fahrzeugfertigung als auch bei den LabVIEW-Beispielen wurde vorausgesetzt, dass jede Pipeline-Stufe dieselbe Zeit zur Ausführung benötigt. Man kann also sagen, dass diese Pipeline-Stufen ausgeglichen waren. Bei realen Anwendungen ist dies jedoch selten der Fall. Wenn im folgenden Diagramm „Stage 1“ drei Mal so lange für die Ausführung benötigt wie „Stage 2“, dann hat ein Pipelining der zwei Stufen nur eine minimale Leistungssteigerung zur Folge.

Ohne Pipelining (Gesamtzeit = 4s):

Pipelined (total time = 3s):

Mit Pipelining (Gesamtzeit = 3s):

Leistungssteigerung um den Faktor 1,33 (kein idealer Fall fürs Pipelining)

Um diese Situation zu ändern, muss der Programmierer Tasks von Stage 1 zu Stage 2 verschieben, bis beide Stufen in etwa dieselbe Ausführungszeit benötigen. Bei einer großen Anzahl von Pipeline-Stufen kann dies schwierig werden.

In LabVIEW ist es hilfreich, jede Pipeline-Stufe zu beurteilen, um sicherzugehen, dass die Pipeline ausgewogen ist. Das lässt sich am einfachsten mit einer flachen Sequenzstruktur in Verbindung mit der Tick-Count-Funktion (ms) verwirklichen (siehe Abbildung 4).

Abb. 4: Die Bewertung der Pipeline-Stufen ermöglicht eine ausgeglichene Pipeline.

Datenübertragung zwischen Cores

Am besten wird die Übertragung großer Datenmengen zwischen Pipeline-Stufen wann immer möglich vermieden. Da die Stufen einer Pipeline auf separaten Prozessorkernen ausgeführt werden könnten, ist es möglich, dass jede Datenübertragung zwischen einzelnen Stufen einen Speichertransfer zwischen physikalischen Prozessorkernen zur Folge hat. Falls sich zwei Prozessorkerne nicht ein Cache teilen (oder falls die Speichertransfergröße die Cache-Größe übertrifft), stellt der Endnutzer der Anwendung eventuell eine Verringerung der Effektivität des Pipelinings fest.

Pipelining ist also eine Technik, die Programmierer zur Erzielung von Leistungssteigerungen bei sequenziellen Anwendungen (auf Multicore-Rechnern) nutzen können. Der Trend der CPU-Branche, die Cores pro Chip zu erhöhen, bedeutet, dass Strategien wie das Pipelining in naher Zukunft für die Anwendungsentwicklung entscheidend sein werden.

Um die größtmögliche Leistungssteigerung aus dem Pipelining zu erzielen, müssen einzelne Stufen ausgeglichen sein, so dass keine Stufe länger für die Ausführung benötigt als die anderen Stufen. Außerdem sollte jede Datenübertragung zwischen den Pipeline-Stufen möglichst gering gehalten werden, damit eine Leistungsabnahme aufgrund von Speicherzugriff von mehreren Kernen vermieden wird.

• Serie zu den „Grundlagen der Multicore-Programmierung“ 
  
• Programmierstrategien für Multicore-Prozessoren: Datenparallelität
• Programmierstrategien für Multicore-Prozessoren: Task-Parallelität
• Mehr über NI LabVIEW