2. Oktober 2009

Programmierkonzepte für Multi-Core-Prozessoren

This article briefly introduces some existing programming concepts. It is a summary of a couple of interesting approaches that were presented at Ferienakademie 2009.

Heute werden mehr und mehr Rechner mit Multi-Core-Prozessoren ausgestattet, welche mit niedrigerer Taktfrequenz laufen und effizienter mit der Energie umgehen als Einkernprozessoren. Diese Entwicklung im Hardwarebereich zwingt Programmierer nun, parallele Programme zu schreiben, die mit der Zahl der Prozessoren skalieren, wenn sie die volle Leistung eines Multi-Core-Prozessors abrufen möchten.

Cilk

Cilk ist eine Erweiterung von C und bietet Parallelisierung auf der Sprachebene. Cilk fügt der Sprache C drei weitere Schlüsselwörter hinzu:

  • cilk – markiert eine C-Funktion als Cilk-Prozedur
  • spawn – ruft eine Cilk-Prozedur auf, die parallel zu ihrem Aufrufer abläuft
  • sync – zwingt die aufrufende Cilk-Prozedur auf alle von ihr mit spawn aufgerufene Cilk-Prozeduren zu warten

Cilk hat ein recht simples Konzept und erspart dem Programmierer, direkt mit Threads zu arbeiten. Es hat das nette Feature, dass man semantisch äquivalenten C-Code erhalten kann, indem man einfach alle Cilk-spezifischen Schlüsselwörter eliminiert. Für C++ existiert mit Cilk++ auch eine entsprechende Variante.

Intel Threading Building Blocks

Intel stellt eine Bibliothek namens Intel Threading Building Blocks (TBB) zur Verfügung, mit welcher man C++-Applikationen aufrüsten kann, um den Vorteil eines Multi-Core-Prozessors zu nutzen. Auch die TBB befreit den Programmierer von der Aufgabe, direkt mit Threads zu arbeiten. Stattdessen bieten die TBB generische Algorithmen und Bausteine mit denen man Aufgaben parallel abarbeiten kann.

  • parallel_for – zur Verwertung von Datenparallelität und zur Parallelisierung von rekursiven Algorithmen
  • parallel_do – zur Verwertung von Datenparallelität. Eingabedaten kommen aus einem Strom.
  • parallel_reduce – führt eine parallele Reduktion durch.
  • pipeline – erlaubt parallele Verarbeitung von Daten in einer Pipeline-Anordnung aus seriellen und parallelen Schritten.

OpenMP

OpenMP ist eine Spezifikation für die parallele Programmierung von Shared-Memory-Systemen in C/C++/FORTRAN. Zum Beispiel kann man in C parallelen Code schreiben, indem man OpenMP-Pragmas benutzt, welch dem Compiler mitteilen, wie der Code zu parallelisieren ist. OpenMP bietet Unterstützung zur Verwertung von sowohl Daten- als auch Aufgaben-Parallelität (task parallelism).

MPI

MPI steht für Message Passing Interface and bietet Mittel zur Parallelisierung von Programmen auf Systemen mit verteiltem Speicher. Eine MPI-Applikation läuft in verschiedenen Threads. In jedem Thread läuft eine eigene Instanz des Programms. Der einzige Weg zwischen diesen Instanzen zu kommunizieren, besteht darin, Nachrichten zu verschicken. Es gibt Implementationen des MPI für verschiedene Sprachen, darunter C und Java.

MapReduce

Google meint: “MapReduce simplifies data processing on Large Clusters” . MapReduce ist ein Framework, das auf den Funktionen map und reduce beruht, welche aus der funktionalen Programmierung bekannt sind. Ein Programm, das MapReduce verwendet, verarbeitet seine Daten in zwei Schritten:

  • map – die Eingabedaten werden in unabhängige Portionen geteilt und an einzelne Arbeiter verteilt, welche dann ihre Daten parallel verarbeiten.
  • reduce – die Ergebnisse der einzelnen Arbeiter werden kombiniert

Es gibt auch Open-Source-Implementationen, wie zum Beispiel Hadoop MapReduce.

CUDA

Mit CUDA ist es möglich massiv datenparallele Programme auf einem Grafikprozessor (GPU) auszuführen, in welchem allerdings Unterstützung für CUDA integriert sein muss. Allgemein übergibt man Daten an die Grafikkarte, welche dann einen Kernel (ein Stück Code) parallel auf Teilfragmenten der Daten ausführt.

Parallel Haskell

Prinzipiell wäre eine komplett funktionale Sprache mit strikter Auswertung von Parametern und keinen Seiteneffekten sehr einfach zu parallelisieren. Haskell wertet seine Parameter nach dem Prinzip der Lazy-Evaluation aus und sobald Ein- und Ausgabeoperationen notwendig werden, wird die Aufgabe der Parallelisierung schon sehr viel komplizierter. Parallel Haskell bietet Unterstützung für die Parallelprogrammierung in Haskell. Dabei werden berücksichtigt:

  • manche Funktionen haben doch Seiteneffekte, welche dazu führen, dass die Reihenfolge der Auswertung von Parametern eine Rolle spielt
  • Parallele Auswertung von Parametern, ohne dabei die Semantik zu ändern

Referenzen

  1. EETimes: Parallel software plays catch-up with multicore
  2. EETimes: Multicore MPUs go mainstream