[A] OpenMP

[Ben04]

OpenMP

Einleitung...

Compiler Unterstüzung

• GCC >= 4.2
• MinGW technology preview
• Intel
• VC 2005 ?

Syntax

OpenMP besteht zu einem Großteil aus Compiler-Erweiterungen. Es gibt eine Reihe von Pragma-Anweisungen welche die OpenMP-Funktionalität bereit stellen. Jede von ihnen folgt folgendem Syntax:

#pragma omp Anweisung
C++ Code auf den sich die Anweisung bezieht

Neben diesen pragma-Konstrukten gibt es noch eine Reihe von normalen Funktionen. Diese werden im Header [i]omp.h* definiert. Alle haben den Prefix omp_.

Parallel

Die grundlegene Anweisung, ohne die bei OpenMP nichts auskommt, ist die parallel-Anweisung. Sie erzeugt eine Reihe von Threads und führt den nachfolgenden C++ Block mit jedem Thread aus. Wenn es mehrere Threads erzeugt werden, dann wird der Block auch mehrmals ausgeführt. Wie viele Threads erstellt werden, ist der Implementierung von OpenMP freigestellt. Meistens werden aber so viele Threads erzeugt wie es im Rechner Kerne gibt.

Es ist also in der Regel nicht möglich vorher zu sagen wie oft ein parallel-Block ausgeführt wird.

int main(){
	printf("Hier ist noch alles einfach und sequentiell.\n");
	#pragma omp parallel
	{
		printf("Hallo ");
		printf("Welt!\n");
	}
	printf("Alle Threads haben Hallo gesagt.");
}

Im parallel-Block ist ganz normaller C++-Code erlaubt. Man kann C++-Objekte anlegen und auch Funktionen aufrufen. Sogar Ausnahmen sind erlaubt, solange sie nicht aus dem parallel-Block rausfliegen.

Solange sich die Threads nicht in die Quere kommen, ist das auch schon alles was man machen muss um sämtliche Kerne seines Rechners zu benutzen. Allerdings ist dies leider nur sehr selten der Fall ist. Bereits in diesem einfachen ist es möglich, dass Threads sich streiten. Wenn zwei Threads gleichzeitig etwas ausgeben, ist es nähmlich nicht klar welcher zuerst dran kommt. Alles von Funktionieren-wie-erwartet bis hin zu Abstürzen ist eine möglich Konsequenz.

Was das Problem noch komplizierter macht, ist dass das Verhalten nicht vollständig deterministisch ist. Wieviele Threads erzeugt werden kann von Lauf zu Lauf unterschiedlich sein und welcher Thread wann dran kommt kann man noch schlechter vorhersagen. Dies führt dazu, dass manche Bugs noch mit einer gewissen Wahrscheinlichkeit eintreten. Solche Fehler zu debuggen ist sehr schwer.

An sich müsste ich hier sicherstellen, dass zu jedem Zeitpunkt immer höchstens nur ein Thread etwas auf die Konsole schreibt. Bei printf kann man aber normalerweise davon ausgehen, dass legendlich die Reihenfolge der Ausgaben etwas durcheinander geraten kann. Abstürze gehören eher in den Bereich der Theorie. printf leidet normallerweise weniger unter diesem Problem als std::cout, deswegen werde ich in diesem Artikel ausnahmsweise printf bevorzugen. Im folgenden werde ich davon ausgehen, dass Ausgaben mit printf einfach funktionieren. Alles andere würde die Beispiele zu kompliziert machen.

Mit Hilfe der num_threads(n) Anweisung kann man festlegen wie viele Threads erstellt werden. n muss eine Ganzzahl sein und braucht nicht zum Zeitpunkt der Übersetzung bekannt zu sein.

int main(){
	printf("Wie viele Threads sollen es sein?\n");
	int n;
	scanf("%d", &n);
	#pragma omp parallel num_threads(n)
	{
		printf("Hallo ");
		printf("Welt!\n");
	}
	printf("Alle Threads haben Hallo gesagt.");
}

Wenn man für n eine große Zahl eingibt, kann man mit großer Wahrscheinlichkeit beobachten wie sich die Threads in die Quere kommen. Es folgt eine Beispielausgabe, so wie ich sie beobachten konnte.

Hallo Hallo Welt!
Hallo Welt!
Welt!
Hallo Welt!

Während der eine Thread noch am Schreiben ist, funkt ein anderer ihm einfach dazwischen. Versuchen Sie nach zu vollziehen wie diese Ausgabe zustande kam.

Bei den meisten OpenMP-Implementierungen werden die Threads nur einmal erstellt. Dies gilt auch wenn es mehrere parallel-Blocks gibt. Zwischen den Blocks gehen die zusätzlichen Threads in einen Wartezustand. Sie werden erst am Ende des Programms zerstört. Man darf also ruhig mehrere parallel-Blöcke haben und man muss nicht sparsam mit ihrem Einsatz umgehen.

parallel-Blöcke dürfen verschachtelt werden. In der Standardeinstellung erzeugt der verschachtelte Block aber keine neuen Threads.

Thread ID, single und master

Jeder Thread besitzt eine eindeutige Indentifikationsnummer. Es handelt sich dabei um fortlaufende Nummern und nicht etwa um gecastete Zeiger oder ähnliches. Man kann die ID also als Index in einem Array benutzen. Der Thread mit der ID 0 nennt man auch noch Master.

Mit Hilfe von omp_get_thread_num kann man die ID eines Threads bestimmen und durch einen Aufruf von omp_get_num_threads kann man die Gesamtanzahl der Threads, welche vom parallel-Block erzeugt wurden, herraus finden.

int main(){
	#pragma omp parallel
	{
		printf("Thread %d sagt Hallo \n", omp_get_thread_num());	
		if(omp_get_thread_num() == 0)
			printf("Es gibt %d Threads.\n", omp_get_num_threads());		
	}

}

Wie man an diesem Beispiel sieht, ist es möglich auch in einem parallel-Block, Instruktionen nur einmal aus zu führen. Allerdings gibt es dafür bessere OpenMP-Konstrukte.

int main(){
	#pragma omp parallel
	{
		printf("Thread %d sagt Hallo \n", omp_get_thread_num());	

		#pragma omp master
		{
			printf("Es gibt %d Threads.\n", omp_get_num_threads());	
		}

		#pragma omp single
		{
			printf("Thread %d war hier.\n", omp_get_thread_num());	
		}

		#pragma omp single
		{
			printf("Danach war Thread %d da.\n", omp_get_thread_num());	
		}
	}
}

Ein master-Block wird nur vom Master-Thread ausgeführt. Der Code ist äquivalent zur if-Abfrage aus dem vorherigen Beispiel. Ein single-Block wird genau einmal ausgeführt, allerdings ist es egal von welchem Thread.

Sämtliche Threads wartem am Ende eines single-Blocks bis auch der letzte es bis dahin geschafft hat. Dadurch ist sichergestellt, dass die Blöcke nicht in verkehrter Reihenfolge ausgeführt werden. Durch eine nowait Anweisung kann man das Warten unterdrücken.

int main(){
	#pragma omp parallel
	{
		#pragma omp single nowait
		{
			printf("Manchmal bin ich als erstes da.\n");	
		}

		#pragma omp single nowait
		{
			printf("Hin und wieder gewinne aber auch ich das Rennen.\n");	
		}
	}
}

Bei einem Master-Block wird nicht gewartet.

Bei verschachtelten parallel-Blöcken werden die IDs durch den innsersten Block neuverteilt. Alle Threads erhalten die ID 0 und die Anzahl der Threads wird als 1 gemeldet. Die Idee dahinter ist, dass sich alles auf den innsersten Block bezieht. Dieser hat aber keinen Thread erzeugt und folglich gibt es nur den der den Block angestossen hat. Eine weitere Konsequenz ist, dass single- und master-Blöcke mehrfach ausgeführt werden.

Die Problematik wird durch folgendes Beispiel gut illustriert.

int main(){
	#pragma omp parallel
	{
		#pragma omp parallel
		{
			printf("omp_get_thread_num() = %d,"
				" omp_get_num_threads() = %d\n", 
				omp_get_thread_num(), 
				omp_get_num_threads());	
		}
	}
}

Am besten ist es parallel-Blöcke nicht zu verschachteln.

sections

Alternativ zu den single-Blöcken kann man auch sections verwenden.

int main(){
	#pragma omp parallel
	{
		#pragma omp sections
		{
			{
				printf("Thread %d war hier.\n", omp_get_thread_num());			
			}
			#pragma omp section
			{
				printf("Aber hier war Thread %d.\n", omp_get_thread_num());		
			}
			#pragma omp section
			{
				printf("und eine weitere section");		
			}
		}
		printf("Thread %d sagt Tschüss \n", omp_get_thread_num());
	}
}

Jede der drei Sektionen wird genau einmal ausgeführt. Am Ende des sections-Block warten die Threads ehe sie fortfahren. Auch hier kann man das Warten durch nowait unterdrücken.

Wenn an einer beliebigen Stelle gewartet werden soll so kann man eine barrier-Anweisung benutzen.

int main(){
	#pragma omp parallel
	{
		printf("Thread %d sagt Hallo \n", omp_get_thread_num());
		#pragma omp barrier
		printf("Thread %d sagt Tschüss \n", omp_get_thread_num());
	}
}

In diesem Beispiel ist sicher gestellt, dass alle Threads "Hallo" sagen ehe sich der erste verabschiedet.

For

Mit Hilfe von OpenMP kann man auch einfache Schleifen parallelisieren.

int main(){
	#pragma omp parallel
	{
		#pragma omp for
		for(int i=0; i<10; ++i)
			printf("%d^2 = %d\n", i, i*i);
	}
}

Anders als bei einer normalen Schleife, werden die Durchläufe hier nicht umbedingt nacheinander abgearbeitet, sondern möglicherweise gleichzeitig und auch in verkehrter Reihenfolge.

Um dies zu bewerkstelligen werden die Durchläufe möglichst gleichmäßig zwischen den Threads verteilt. Zum Beispiel bei zwei Threads, würde der erste die Durchläufe mit 0<=i<=4 abarbeiten und der andere die restlichen mit 5<=i<=9.

OpenMP hält sich stur an diese Verteilung auch wenn sie schwachsinning ist.

int main(){
	#pragma omp parallel
	{
		#pragma omp single nowait
		{
			for(int i=0; i<INT_MAX; ++i)
				for(int j=0; j<INT_MAX; ++j)
					{}
		}

		#pragma omp for
		for(int i=0; i<10; ++i)
			printf("%d^2 = %d\n", i, i*i);
	}
}

Obwohl der eine Thread sehr lange mit dem single-Block beschäftigt ist, kommt keiner der wartenden Threads auf die Idee bei der for-Schleife Überstunden zu leisten. Dazu wird eine dynamische Arbeitsverteilung benötigt.

int main(){
	#pragma omp parallel
	{
		#pragma omp single nowait
		{
			for(int i=0; i<INT_MAX; ++i)
				for(int j=0; j<INT_MAX; ++j)
					{}
		}

		#pragma omp for schedule(dynamic)
		for(int i=0; i<10; ++i)
			printf("%d^2 = %d\n", i, i*i);
	}
}

Wenn ein Thread fertig ist, schaut er ob es noch Arbeit gibt und übernimmt diese dann auch gleich. Ein ähnliches Problem ergibt sich wenn die Durchläufe unterschiedlich lang dauern.

Am Ende eines for-Blocks wird gewartet. Dies kann man wie üblich mit nowait unterdrücken.

Da schedule(dynamic) einen größeren Verwaltungsoverheat als die normalle Version besitzt, kann es sein, dass die normale Version in manchen Fällen schneller ist, obwohl nicht alle Threads immer beschäftigt sind. Die normale Version kommt nämlich ganz ohne Kontakt zwischen den einzelnen Threads zurecht und ist daher fast frei von Overheat.

Damit eine Schleife überhaupt parallelisiert werden kann muss sie eine Reihe von sehr strikten Kriterien erfüllen.

• Die Schleifenvariable muss eine vorzeichenbehaftete Ganzzahl sein. unsigned ist nicht erlaubt. In der Praxis bedeutet dies, dass man nicht viel außer int einsetzen kann.
• Die Abbruchbedinung muss ein Ordungsvergleich (<,>, <= oder sein und auf der linken Seite muss sich die Schleifenvariable und nur die befinden. Die rechte Seite darf nicht während der Ausführung der Schleife verändert werden.
• Die Inkrementierung muss in immer gleich großen Schritten stattfinden. Dies bedeutet, dass man nur --, ++, += oder -= verwenden darf um die Schleifenvariable zu verändern. Die Größe der Schritte darf nicht während der Ausführung der Schleife verändert werden.
• break und return sind verboten. continue ist erlaubt. goto darf nur verwendet werden wenn man nicht aus der Schleife rausspringt.

Folgende Schleifen lassen sich nicht mit OpenMP parallelisieren.

int n = foo();

// unsigned ist nicht erlaubt (wird aber oft toleriert).
for(unsigned i=0; i<n; ++i)
	printf("%u", i);

// Auf der einen Seite der Bedingung muss ein einfaches i stehen.
for(int i=0; i*i<n; ++i)
	printf("%d", i);

// Die Inkrementierungsschritte sind nicht gleichgroß
for(int i=0; i<n; i*=3)
	printf("%d", i);

// Dies ist erlaubt, allerdings ist unspezifiziert wie oft bar und foobar aufgerufen werden.
for(int i=-10; i<n*n*bar(); i+=foobar(n))
	printf("%d", i);

// Man darf nicht aus der Schleife rausspringen.
int a[10] = { ... }
for(int j=0; j<10; ++j)
	if(a[j] == n)
		return i;

// n darf nicht in der Scheife verändert werden.
for(int i=0; i<n*10; i+=n)
	++n;

OpenMP-for-Schleifen dürfen nicht verschachtelt werden. Man kann allerdings mit einem zusätzlichen parallel-Block Abhilfe schaffen.

#pragma omp parallel
{
	#pragma omp for
	for(int i=0; i<10; ++i)
	{
		#pragma omp parallel
		{
			#pragma omp for
			for(int j=0; j<10; ++j)
			{
				printf("%d*%d = %d\n", i, j, i*j);
			}
		}
	}
}

Es wird aber nur die äußere Schleife parallelisiert und die innere sorgt nur für Probleme und Overheat. Besser ist:

#pragma omp parallel
{
	#pragma omp for
	for(int i=0; i<10; ++i)
	{
		// Dieses for ist ein ganz normales C/C++ for
		for(int j=0; j<10; ++j)
		{
			printf("%d*%d = %d\n", i, j, i*j);
		}

	}
}

Kurzschreibweise

Wenn ein parallel-Block nur eine for Schleife enthält, dann gibt es eine Kurzschreibweise. Das vorherige Beispiel könnte man auch folgendermaßen schreiben.

#pragma omp parallel for
for(int i=0; i<10; ++i)
{
	// Dieses for ist ein ganz normales C/C++ for
	for(int j=0; j<10; ++j)
	{
		printf("%d*%d = %d\n", i, j, i*j);
	}

}

Analog gibt es auch ein parallel sections-Block.

Folgendes Beispiel berechnet alle Primzahlen kleiner als eine gegebene Zahl.

bool is_prime(unsigned n){
	for(unsigned i=2; i<n; ++i)
		if(n%i == 0)
			return false;
	return true;
}

int main(){
	unsigned n;

	printf("Geben sie eine Ganzzahl ein: ");
	scanf("%u", &n);

	// schedule(dynamic) ist notwendig da is_prime keine
	// konstante Laufzeit besitzt. 
	#pragma omp parallel for schedule(dynamic)
	for(int i=2; i<=n; ++i)
		if(is_prime(i))
			printf("%u ist prim\n", i);
}

Gemeinsamer Speicher

Die Zugriffsregeln für Variablen sind die die man erwarten würde.

int a;

int main(){
	int b;
	#pragma omp parallel
	{
		int c;
		// a und b werden geteilt, jeder Thread hat sein eigenens c
	}
}

Wenn ein Thread schreibend aud a zugreift dann ergeben sich sämltiche von Multithreading her bekannte Probleme. OpenMP bietet aber leider nur wenig revolutionäres um dieses alt bekannte Problem zu lösen.

Ciritcal

Ein critical-Block ist ein in dem sich immer nur genau ein Thread befindet. Wenn bereits ein Thread im Block ist, wartet jeder Thread der hinein will, bis der Block wieder frei wird.

Betrachten Sie folgendes Beispiel:

int main(){
	#pragma omp parallel for
	for(int i=0; i<10; ++i){
		int n;
		#pragma omp critical
		{
			printf("Geben sie eine Zahl ein: ");
			scanf("%d", &n);
		}
		printf("%d * %d = %d\n", i, n, i*n);
	}
}

Hier wird ein critical-Block verwendet um sicher zu stellen, dass der Benutzer nie aufgefordert wird zwei Zahlen gleichzeitig einzugeben. Nimmt man das critical weg dann kann es zu folgender Ausgabe kommen.

Geben sie eine Zahl ein: Geben sie eine Zahl ein:

Jeder critical-Block besitzt einen Namen. Wenn zwei Blöcke den selben Namen besitzen, kann nur genau ein Thread in einem der beiden sein. Zwei Blöcke mit verschiedenen Namen beeinflussen sich nicht. Das heißt es ist durchaus möglich, dass 2 Threads in critical-Blöcken sind sofern sie verschiedene Namen haben.

Wenn bei einem critical-Block kein Name angegeben wird, besteht der Name aus dem leeren Wort. Alle leeren Wörter werden als gleich angesehen. Im Klartext bedeutet dies, dass keine zwei Threads gleichzeitig in irgendeinem nameslossen Block sein können.

Leider sind die Namen global und liegen in keinem Namensraum. Dadurch sind Namenskonflikte möglich. Es ist allerdings sehr unwahrscheinlich, dass dies andere Auswirkungen hat als einfach nur ein langsameres Programm. Es ist sichergestellt, dass sie normalen Symbolen nicht in die Quere kommen.

int main(){
	FILE*file = fopen("out.txt", "w");
	#pragma omp parallel for
	for(int i=0; i<10; ++i){
		int n;

		#pragma omp critical(console)
		{
			printf("Geben sie eine Zahl ein : ");
			scanf("%d", &n);
		}

		#pragma omp critical(console)
		{
			printf("%d * %d = %d\n", n, n, n*n);
		}

		#pragma omp critical(file)
		{
			fprintf(file, "%d * %d = %d\n", n, n, n*n);
			fprintf(file, "%d + %d = %d\n", n, n, n+n);
		}

		#pragma omp critical(console)
		{
			printf("%d + %d = %d\n", n, n, n+n);
		}
	}
	fclose(file);
}

In diesem Beispiel ist sicher gestellt, dass nichts auf die Konsole geschrieben wird, falls der Benutzer aufgefordert wurde etwas einzugeben. In der Datei müssen beide zueinander passenden Rechnungen hinter einander ausgegeben werden. Bei der Konsole ist dies nicht garantiert.

flush

So gut wie jeder Rechner besitzt Register und mehrere Level von Speicher-Caches, um den Zugriff auf Variablen zu beschleunigen. Anstatt direkt mit der Variable im Hauptspeicher zu arbeiten wird diese zuerst in einen schnelleren Cache-Speicher kopiert. Anschließend wird mit der Kopie gerechnet und nach einiger Zeit wird die Variable in den Hauptspeicher zurück kopiert. Dies führt dazu, dass es mehrere Versionen von der gleichen Variable gibt welche nicht immer gleich sind.

In einem sequentielen Programm stellt dies kein Problem dar, da zu jedem Zeitpunkt bekannt ist wo sich die rezenteste Version der Variable befindet. Jedoch bei mehreren Threads ist dies nicht mehr so einfach. Der eine weiß nicht wann der andere fertig ist und wann er die Werte syncronisieren muss.

Um dieses Problem zu lösen bietet OpenMP die flush-Answeisung an. Sie synkronisiert die locale Version des Threads mit der des Hauptspeichers. Dies bedeutet, dass jeder Thread nachdem er fertig ist, eine geteilte Variable zu verändern, diese auch flushen muss. Ein Thread der lesend auf eine Variable zugreifen will, muss die Variable auch flushen damit er sicher ist die neuste Version zu Gesicht zu bekommen. Wenn ein Thread auch mit einer varalteten Version arbeiten kann, braucht er die Variable nicht zu flushen. Wenn sicher ist, dass eine Variable nicht in einem parallel-Block verändert wird, dann kann man sich das flush auch sparen.

Folgendes Progamm berechnet das Faktoriel einer Zahl.

int main(){
	unsigned n, fact = 1;
	printf("Geben sie eine Zahl ein : ");
	scanf("%u", &n);

	#pragma omp parallel
	{
		unsigned local_fact = 1;

		// Auf n kann man ohne flush zugreifen,
		// da es nicht verändert wird.
		#pragma omp for
		for(int i=1; i<=n; ++i){
			// local_fact braucht nicht geflusht 
			// zu werden, da es nicht geteilt wird.
			local_fact *= i;
		}

		#pragma omp critical
		{
			// Zuerst holt der Thread sich die neuste Version
			// aus dem Hauptspeicher.
			#pragma omp flush(fact)

			// Danach wird die Variable verändert.
			fact *= local_fact;

			// Anschließend wird die Variable wieder in den
			// Hauptspeicher geschrieben, damit andere Threads
			// sich die neuste Version von dort laden können.
			#pragma omp flush(fact)
		}	
	}

	printf("%u! = %u\n", n, fact);
}

reduction

Mit reduction lassen sich Berechnung vom Typ n += f(1)+f(2)+...+f(n) parallelisieren. Jeder Thread erhält sein eigenens n welches mit dem neutralen Element initialisiert wird. Bei + ist das neutrale Element die 0. Anschließend summiert jeder eine Reihe von Termen auf. Am Ende des parallel-Blocks, wo sich die Threads wieder treffen, werden dann die verschiedene n dem normalen n hinzugefügt.

Neben + lassen sich auch -, *, &, |, ^, && und || auf diese Weise parallelisieren. Es muss bei den Operatoren jedoch um ihre Buildin-Version handeln.

• +, -, | und ^ besitzen das neutrale Element 0.
• * besitzt das neutrale Element 1.
• & besitzt das neutrale Element ~0. (Bei ~0 sind alle Bits gesetzt sind.)
• && besitzt das neutrale Element true.
• || besitzt das neutrale Element false.

Folgendes Beispiel bestimmt ob eine Zahl eine prim ist.

int main(){
	int n;

	printf("Geben sie eine Ganzzahl ein: ");
	scanf("%d", &n);

	// Der Initialwert von is_prime ist wichtig da dieser auch
	// in die Berechnung einbezogen wird.
	bool is_prime = true;

	#pragma omp parallel reduction(&&: is_prime)
	{
		// jeder bekommt sein eigenens is_prime,
		// welches mit true, dem neutralen Element von &&,
		// initialisiert wurde.

		#pragma omp for
		for(int i=2; i<n; ++i)
			if(n%i == 0)
				is_prime = false;

		// Alle is_prime (auch das normale) werden mittels 
		// && verknüpft. Im Klartext bedeutet dies, dass 
		// falls eines false ist, ist das Resultat false.
	}

	if(is_prime)
		printf("%d ist prim\n", n);
	else
		printf("%d ist nicht prim\n", n);

}

Auch hier gibt es eine Kurzschreibweise. Folgendes Beispiel berechnet das Faktoriel einer Zahl.

int main(){
	unsigned n;

	printf("Geben sie eine Ganzzahl ein: ");
	scanf("%u", &n);

	unsigned fact = 1;

	#pragma omp parallel for reduction(*: fact)
	for(int i=2; i<n; ++i)
		fact *= i;

	printf("%u! = %u\n", n, fact);
}

reduction erlaubt es dem Compiler eine Reihe von Optimierungen durchzuführen, welche bei der äquivalenten Formulierungen mit critical und flush nur sehr schwer möglich sind.

Locks

Quellen

• http://bisqwit.iki.fi/story/howto/openmp/
• http://www.openmp.org/drupal/mp-documents/spec25.pdf

[Ben04]

Wie man an diesem Beispiel sieht, ist es möglich auch in einem parallel-Block, Instruktionen nur einmal aus zu führen. Allerdings gibt es dafür bessere OpenMP-Konstrukte.

int main(){
	#pragma omp parallel
	{
		printf("Thread %d sagt Hallo \n", omp_get_thread_num());	

		#pragma omp master
		{
			printf("Es gibt %d Threads.\n", omp_get_num_threads());	
		}

		#pragma omp single
		{
			printf("Thread %d war hier.\n", omp_get_thread_num());	
		}

		#pragma omp single
		{
			printf("Danach war Thread %d da.\n", omp_get_thread_num());	
		}
	}
}