Mit der aktuellen (beziehungsweise in Ubuntu kommenden) Version 4.9 der GNU Compiler Collection GCC hält auch Intels® Multithreading Werkzeug Cilk™ Einzug in den C- und C++-Compiler. Mit Cilk™ soll es (unter anderem) äußerst einfach sein, die Last von Programmen gleichmäßig auf alle verfügbare Prozessorkerne zu verteilen.

Vorbereitungen

Um Cilk™ mit Ubuntu nutzen zu können, bedarf es Vorbereitung, da es, wie der Titel es schon vermuten lässt, erst ab Version 4.9 in den Compilern enthalten ist. Diese Version wird wohl aber erst unter Ubuntu 14.10 zum Standard werden, also muss GCC auf eine der folgenden Weisen aktualisiert werden:

  • Aus den Quellen kompilieren, wobei ich hierauf nicht weiter eingehen möchte, da der Aufwand nur zum Testen von Cilk™ zu hoch und unnötig und die Vorgehensweise ausreichend im Internet dargelegt ist.
  • Über das Ubuntu Toolchain PPA installieren.

Das PPA kann mittels sudo add-apt-repository ppa:ubuntu-toolchain-r/test ins System eingepflegt werden, anschließend werden mit dem Befehl sudo apt-get install gcc-4.9 g++-4.9 die Compiler installiert. In den deb-Paketen scheint allerdings noch eine Datei zu fehlen, die somit manuell angelegt werden muss, also mit sudo nano /usr/lib/libcilkrts.spec die Datei öffnen und folgendes einfügen:

This spec file is read by gcc when linking.  It is used to specify the
# standard libraries we need in order to link with libcilkrts.
*link_cilkrts: /usr/lib/gcc/i686-linux-gnu/4.9/libcilkrts.so

Der Pfad zur Shared Library muss auf 64-bit Systemen entsprechend angepasst werden. Damit sollte die Installation eigentlich abgeschlossen sein (einfacher als GCC selbst zu kompilieren, oder?).

Tests

Um die Performance von Cilk™ unter Linux zu messen, bediene ich mich der Beispiele, die Intel® auf den entsprechenden Webseiten angibt. Als erstes das Fibonacci-Beispiel, mit dem sich cilk_spawn und cilk_sync für rekursive Algorithmen testen lässt:

#include <iostream>
#include <cilk/cilk.h>
#include <cilk/cilk_api.h>
#include <sstream>

int fibo_wo (int n)
{
	if (n < 2)
		return n;

	int x = fibo_wo (n-1);
	int y = fibo_wo (n-2);

	return x + y;
}

int fibo_w (int n)
{
	if (n < 2)
		return n;

	// Spawn one recursion as a new thread
	int x = cilk_spawn fibo_w (n-1);
	int y = fibo_w (n-2);

	// Wait for all spawned threads to finish
	cilk_sync;

	return x + y;
}

int main (int argc, const char* argv[])
{
	// Thanks to Thomas for char to int conversion (<http://stackoverflow.com/questions/2797813/convert-c-argument-to-int>)
	std::istringstream ss(argv[1]);
	int x;
	if (!(ss >> x))
	{
		std::cerr << "Invalid number " << argv[1] << '\n';
	}
	
	std::cout << "Testing Intel (R) Cilk (TM) with Fibonacci (n = " << argv[1] << ")" << std::endl;
	clock_t start, end;
	start = clock ();
	std::cout << fibo_wo (x) << std::endl;
	end = clock ();
	std::cout << "Time without Intel (R) Cilk (TM): " << (end - start) / CLOCKS_PER_SEC << " sec (CLOCKS_PER_SEC: " << CLOCKS_PER_SEC << ")" << std::endl;
	start = clock ();
	std::cout << fibo_w (x) << std::endl;
	end = clock ();
	std::cout << "Time with Intel (R) Cilk (TM): " << (end - start) / CLOCKS_PER_SEC << " sec (CLOCKS_PER_SEC: " << CLOCKS_PER_SEC << ")" << std::endl;
	
	return 0;
}

Ich habe das Beispiel etwas angepasst, damit sich leichter vergleichbare Ergebnisse erzielen lassen. Die Datei einfach als fibo.cpp speichern und mit

g++-4.9 -fcilkplus -I/usr/include/c++/4.9/ -o fibo fibo.cpp

kompilieren. Ein Aufruf mit ./fibo 40 gibt bei mir folgende, interessante Ergebnisse:

Testing Intel (R) Cilk (TM) with Fibonacci (n = 40)
102334155
Time without Intel (R) Cilk (TM): 3 sec (CLOCKS_PER_SEC: 1000000)
102334155
Time with Intel (R) Cilk (TM): 35 sec (CLOCKS_PER_SEC: 1000000)

Mal abgesehen davon, dass beide Funktionen das gleiche Ergebnis liefern (Glück gehabt!) und mein Computer echt langsam ist, fällt vor allem auf, dass die Version mit Intel® Cilk™ mehr als die zehnfache Laufzeit hat. Ob das an Problemen zwischen meinem betagten Prozessor (Genuine Intel® CPU T2250 @ 1.73GHz × 2) und der doch recht neuen Implementierung von Cilk™ liegt oder daran, dass der Compiler die ‘normale’ Funktion einfach so stark optimiert (die Option -O0 bringt keine Veränderung), kann ich nicht sagen. Allerdings scheint die Cilk™ Funktion tatsächlich nicht (so stark) optimiert zu werden, da nach der Kompilierung mit -O3 folgendes Ergebnis erscheint:

Testing Intel (R) Cilk (TM) with Fibonacci (n = 40)
102334155
Time without Intel (R) Cilk (TM): 1 sec (CLOCKS_PER_SEC: 1000000)
102334155
Time with Intel (R) Cilk (TM): 34 sec (CLOCKS_PER_SEC: 1000000)

Das Ergebnis der Cilk™ Funktion ändert sich also nicht, das der normalen wird um zwei Drittel reduziert. Vielleicht bringt die neue for-Schleife etwas, allerdings hat es cilk_for noch nicht in die GCC geschafft, vielleicht in 4.10.

Bis dahin: Wie sehen eure Ergebnisse mit Cilk™ aus? Übersehe ich nur etwas? Liegt es vielleicht an meinem alten Rechner und wie verhält es sich mit AMD Prozessoren? Schreibt einfach in die Kommentare!

AMD Quad Core (Update)

Ich habe gerade zum Vergleich das Programm auf meinem zweiten Rechner (AMD Athlon™ II X4 645 Processor × 4) kompiliert und ausgeführt, leider auch hier ähnliche Ergebnisse:

$ > ./fibo 40
Testing Intel (R) Cilk (TM) with Fibonacci (n = 40)
102334155
Time without Intel (R) Cilk (TM): 1 sec (CLOCKS_PER_SEC: 1000000)
102334155
Time with Intel (R) Cilk (TM): 12 sec (CLOCKS_PER_SEC: 1000000)
$ > ./fibo 45
Testing Intel (R) Cilk (TM) with Fibonacci (n = 45)
1134903170
Time without Intel (R) Cilk (TM): 12 sec (CLOCKS_PER_SEC: 1000000)
1134903170
Time with Intel (R) Cilk (TM): 134 sec (CLOCKS_PER_SEC: 1000000)

Es scheint mir langsam wirklich so, als würde ich etwas übersehen, habt ihr Ideen?