Infos aus erster Hand zu Cilk

Wie ich ja kürzlich per Twitter vermeldet habe, saß ich am Dienstag mit Mario Deilmann von Intel beisammen, um über ein paar mögliche Themen für das Software Dev Blog zum Thema Multicore-Programmierung zu reden. Und so haben wir diverse Themen evaluiert und identifiziert, und als erstes Ergebnis veröffentliche ich heute ein paar Infos zu Cilk, die mir Mario in mein iPhone diktiert hat. Und so gibt es dann nach und nach zu Cilk und den anderen Themen weitere interessante Informationen.

Die Idee von Cilk ist recht einfach: Man erhält ein serielles Programm, wie man das schon von OpenMP kennt. Allerdings kann das mit OpenMP “unterwandert” werden, indem man Abhängigkeiten in den Code einbaut. Bei Cilk hingegen werden die zu parallelisierenden Codeteile einfach mithilfe bestimmter Spawn-Konstrukte ausgelagert. Zudem können die so parallelisierten Abschnitte wieder serialisiert werden, indem man die Spawn-Befehle einfach wieder aus dem Code herausnimmt. Daneben gibt es ein weiteres Cilk-Konstrukt, das mittels einer for-Methode Schleifen parallelisiert.

Das Tolle an Cilk ist der zugeghörige Scheduler, der sehr schlau ist und task-orientiert arbeitet, und nicht wie bei OpenMP thread-basiert. Dabei werden stets möglichst viele Tasks an den Scheduler übergeben, der diese mit einem intelligenten Algorithmus auf die vorhandenen Thread-Ressourcen verteilt. Der Scheduler ist übrigens derart skalierend, dass auch große Rechensysteme optimal ausgenutzt werden.

So skalierte ein cilk-optimiertes Schachprogramm auf einem Rechner mit 512 Kernen so gut, dass es den dritten Platz in einem großen Schachturniert belegte. Der Trick des Cilk-Schedulers besteht übrigens darin, dass die Tasks per Zufall auf die Threads verteilt werden und nicht nach “menschlichen” Kriterien. Ach ja: Das Work Stealing hat seinen Ursprung im Cilk-Scheduler und wurde sukzessive in die Microsoft-Scheduler eingebaut.

Daneben muss mit Cilk nicht darauf geachtet werden, dass die zu parallelisierenden Aufgaben (Tasks) logisch angeordnet sind. Einzige Voraussetzung für eine cilk-basierte Parallelisierung ist die Unabhängigkeit der Tasks zueinander, so dass jeder Task eine Spawn-Methode zugewiesen werden kann. Darüber hinaus dürfen die jeweiligen Codeabschnitte nicht von globalen Variablen abhängen beziehungsweise diese nicht modifizieren. Ansonsten bekommt man es ganz leicht mit Data Races zu tun.

Allerdings ist zu berücksichtigen, dass es mit Cilk wie bei OpenMP, TPL und PPL vor allem um eine Lastverteilung geht, und nicht um eine Verteilung von Funktionalitäten auf die vorhandenen Ressourcen.

Schön an Cilk ist auch die einfache Handhabung: Außer den beiden Spawn- und For-Konstrukten muss man nichts lernen, sodass selbst ungeübte C- und C++-Entwickler Cilk ziemlich schnell einsetzen können. Das Gute an Cilk ist auch seine Vorhersehbarkeit: Sobald das cilk-optimierte Programm vorliegt, kann man anhand der gegebenen Parameter genau berechnen, was die Parallelisierung in Sachen Rechenleistung bringen wird.

Eine Besonderheit an Cilk sind die sogenannten Hyperobjects, mit denen ein parallelisierter Codeabschnitt seine eigene Sicht auf globale Variablen bekommt. Soll heißen, dass jeder Thread seinen eigenen Zugriff auf die globalen Variablen erhält, ohne diese zu verändern, so dass es nicht zu Data Races kommen kann. Dabei wird das Ganze lock-frei realisiert, da für jeden Thread eine eigene Speicherzelle angelegt wird, deren Inhalte am Schluss wieder zusammen geführt werden, so dass das richtige Ergebnis in der globalen Variable steht. Praktisch an Hyperobjects ist auch die Tatsache, dass man eigene anlegen kann. Damit ist Cilk ein ganzes Stück flexibler als OpenMP oder TBB.