So gut wie jeder Computer, jedes Tablet und jedes Smartphone hat heute einen Multicore-Prozessor verbaut. Leider nutzt eine Software nicht zwangsläufig automatisch alle Kerne der CPU aus (Multithreading). Es muss also durch den Programmierer einiges an Vorarbeit geleistet werden, damit seine Software die volle Leistung des Systems ausnutzen kann und in mehreren Threads läuft.
Die Leibniz-Reihe
In diesem Tutorial wollen wir eine Annäherung der Kreiszahl PI berechnen. Dazu benutzen wir die sogenannte Leibniz-Reihe, welche PI durch folgende Summe berechnet:
Die Formel ist prinzipiell einfach mit einer einfachen for Schleife umzusetzen. Für die Summe von k = 0 bis k = 1000 könnte man mit folgender Schleife eine Annäherung von PI berechnen:
double sum = 0;
for (int k = 0; k <= 1000; k++)
{
sum += Math.Pow(-1, k) / (2 * k + 1);
}
double pi = sum * 4;
Das Ergebnis dieser Berechnung ergibt pi = 3,14259165433954.
Wir sehen, dass das Ergebnis noch ziemlich ungenau ist – und das obwohl wir bereits k bis auf 1000 durchlaufen haben. Aus diesem Grund brauchen wir ein deutlich größeres k und damit deutlich mehr Schleifendurchläufe, was sehr zeitaufwändig ist. Im Moment läuft jedoch alles auf einem einzigen Kern der CPU. Um also unsere Rechenzeit zu verkürzen möchten wir PI unter voller Auslastung der CPU in mehreren Threads auf allen Kernen berechnen. Gleichzeitig wollen wir zumindest die Möglichkeit haben, PI in einer von uns festlegbaren Präzision zu berechnen. Dazu brauchen wir eine unbegrenzte Anzahl an Nachkommastellen sowie ein unbegrenzt maximal großes k (= Anzahl der Schleifendurchläufe).
Da uns C# von sich aus leider keine Möglichkeit bietet mit einer endlosen Anzahl von Nachkommastellen zu arbeiten, müssen wir etwas tricksen und bedienen uns der Klasse BigInteger (System.Numerics), welche zumindest unendlich große (durch RAM begrenzt) Zahlen aus der Reihe der Ganzen Zahlen ( …; -3; -2; -1; 0; 1; 2; 3; …) ermöglicht.
Umsetzung in C#
Beginnen wir mit einer Klasse, die wir PICalculator nennen, und einigen Variablen die wir benötigen:
class PICalculator
{
BigInteger f;
BigInteger[] i;
BigInteger[] sum;
BigInteger depth;
bool[] finish;
}
Die Variable f steht für unseren Faktor. Da wir nicht mit Gleitkommazahlen rechnen sondern mit Ganzen Zahlen, multiplizieren wir den Zähler unserer Summe einfach mit einem Faktor f, welcher einer Zehnerpotenz entspricht, und verschieben am Ende das Komma um die Höhe der Potenz nach vorne.
Beispiel mit f = 10^4 = 10000:
Nach der Kommaverschiebung würde hier also pi = 3,2849 herauskommen.
Die Variable i ist unser k. Da wir in separaten Threads arbeiten, wird das Array die Größe der Anzahl der Threads haben. Somit kann für jeden Thread i separat erhöht werden.
Das gleiche gilt für die Variable sum, welche für jeden Thread die Summe speichert.
Die Variable depth entspricht unserem maximalen k – also der Gesamtanzahl der Schleifendurchläufe.
Die Variable finish speichert, ob der jeweilige Thread seine Schleife beendet hat.
Beispiel: Berechnung mit 4 Threads, einem f von 10000 und einer Tiefe (depth) von 1000.
Es gilt nun: pi = (10000 + sum[0] + sum[1] + sum[2] + sum[3]) * 4 = 31428
Nach Division durch f oder der Verschiebung des Kommas erhalten wir pi = 3,1428.
Wir teilen also die Berechnung der Summe in 4 gleichgroße Schleifen auf. Jeder Thread hat also (depth / Anzahl Threads) Schleifendurchläufe.
Der Konstruktor
public PICalculator(int precision, BigInteger searchdepth, int threads)
{
f = BigInteger.Pow(10, precision);
sum = new BigInteger[threads];
i = new BigInteger[threads];
finish = new bool[threads];
depth = searchdepth;
for (int p = 0; p < threads; p++)
{
i[p] = depth / threads * p + 1;
sum[p] = 0;
finish[p] = false;
}
Task oTask = new Task(outputTask);
oTask.Start();
}
Der Konstruktor übernimmt drei Parameter: Die Präzision, welche der Zehnerpotenz unseres f entspricht, die maximale Gesamtanzahl der Schleifendurchläufe und die Anzahl der Threads.
Im weiteren werden die Variablen initialisiert und die Arrays gefüllt. Dabei wird jedes i auf den Startwert abhängig von der Anzahl der Threads gesetzt.
Beispiel für depth = 1000 und threads = 4:
i[0] = 1
i[1] = 251
i[2] = 501
i[3] = 701
Der Task oTask (outputTask) dient lediglich dazu einen Task im Hintergrund laufen zu haben, der es ermöglicht auf Tastendruck den Fortschritt der einzelnen Threads in Prozent anzuzeigen. Die Implementierung kann man am Ende dieses Tutorials im vollständigem Codebeispiel angucken und spielt hier zunächst keine Rolle.
Die Berechnung eines Schleifenschritt im jeweiligen Thread
public bool performSteps(int thread)
{
if (i[thread] > (depth / i.Length * (thread+1)))
{
finish[thread] = true;
return false;
}
if (BigInteger.Remainder(i[thread], 2) == 0)
{
sum[thread] += f / (i[thread] * 2 + 1);
}
else
{
sum[thread] -= f / (i[thread] * 2 + 1);
}
i[thread]++;
return true;
}
Die Methode performSteps(int thread) berechnet einen einzelnen Schleifendurchlauf und erhöht den Zähler i im entsprechenden Thread um 1.
Zunächst wird überprüft, ob bereits das Ende der für diesen Thread maximalen Höhe von i erreicht wurde, indem das aktuelle i mit dem Startwert des nächsten Threads (thread+1) verglichen wird. Wenn das Ende erreicht wurde, wird finish für diesen Thread auf true gesetzt und keine weitere Berechnung mehr durchgeführt.
if (BigInteger.Remainder(i[thread], 2) == 0)
Hier wird überprüft ob es sich beim aktuellen i um eine gerade oder eine ungerade Zahl handelt. Gemäß der Leibniz-Reihe wird bei ungeradem i subtrahiert und bei geradem i addiert. Die Funktion BigInteger.Remainder entspricht im Prinzip einer Modulo Operation.
Addition aller einzelnen Ergebnisse der Threads
public BigInteger getResult()
{
BigInteger pi = f;
foreach (BigInteger s in sum)
{
pi += s;
}
pi *= 4;
return pi;
}
Die Methode getResult() sumiert alle sum der Threads, multipliziert das Ergebnis mit 4 und gibt das Ergebnis als ganze Zahl (ohne Kommaverschiebung) zurück.
Die Hauptklasse und void Main()
class Program
{
static void Main(string[] args)
{
int numThreads = 25;
int precision = 20;
BigInteger depth = 1000000000; // One Billion = 10^9
PICalculator pi = new PICalculator(precision, depth, numThreads);
Console.WriteLine("Calculation started with " + numThreads.ToString() + " threads, press space to see progress.");
Console.WriteLine();
Parallel.For(0, numThreads, i =>
{
bool unfinished = true;
while (unfinished == true)
{
unfinished = pi.performSteps(i);
}
});
StringBuilder sb = new StringBuilder();
sb.Append(pi.getResult().ToString());
sb.Insert(1,",");
string piString = sb.ToString();
Console.WriteLine("Final Result: " + piString);
ConsoleKeyInfo key = Console.ReadKey();
while (key.Key != ConsoleKey.Escape)
key = Console.ReadKey();
}
}
In unserer Main Methode legen wir in Variablen zunächst fest mit wie vielen Threads wir arbeiten wollen, wie groß unser f ist und wie viele maximale Schleifendurchläufe wir haben wollen.
In diesem Beispiel wollen wir 25 Threads haben, wovon das fertige Programm immer maximal die maximal mögliche Anzahl auslastet. Die Präzision in Höhe von 20 entspricht einem f von 10^20 = 100000000000000000000. Insgesamt sollen eine Milliarden Schleifendurchläufe gemacht werden. Die Berechnung wird auch mit Multithreading einige Zeit in Anspruch nehmen. Dennoch kann man davon ausgehen, dass bei einer Quadcore CPU mit aktiviertem Hyperthreading in diesem Fall die Berechnung nur ca. ein Achtel der Zeit in Anspruch nimmt, wie wenn man die Berechnung ohne Multithreading (wie im ersten Beispiel ganz oben) durchführen würde.
Parallel.For (…)
Parallel.For(0, numThreads, i =>
{
bool unfinished = true;
while (unfinished == true)
{
unfinished = pi.performSteps(i);
}
});
Kommen wir also nun zum wichtigsten Teil. C# bietet uns die Funktion Parallel.For (aus System.Threading.Tasks), welche einer for-Schleife gleicht, die allerdings automatisch auf eine maximale Anzahl an Threads verteilt wird. Das heißt diese Parallel.For-Schleife durchläuft i von 0 bis numThreads und startet für jedes i einen neuen Thread. In jedem dieser Threads rufen wir in einer while-Schleife die oben implementierte Methode performSteps auf. Als Parameter übergeben wir das i, welches dem aktuellen Thread entspricht. Die while-Schleife läuft so lange, bis die Methode performSteps das Ende ihrer abzuarbeitenden Berechnungen erreicht hat und false zurückliefert.
Letztendlich haben wir in unserem Beispiel 25 while-Schleifen, die prinzipiell parallel laufen sollten. Dadurch, dass aber die wenigstens CPUs 25 parallel laufende Threads unterstützen, laufen einige Threads nur in den Momenten, wo andere Threads gerade keine Berechnung durchführen.
Im letzten Teil der Main Methode setzen wir ganz einfach hinter die erste Position des Ergebnis das Komma und geben es aus. Anschließend warten wir darauf, dass der Benutzer die Escape Taste drückt um das Programm zu beenden.
Der komplette Code
Im folgenden könnt ihr den kompletten Code studieren, kopieren und Testen. Er enthält noch zwei Methoden, die hier nicht explizit besprochen wurden. Dabei geht es um die Feststellung des Fortschritts der Berechnung im einzelnen Thread und der Ausgabe in Prozent.
using System;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
namespace CalculatePI
{
class PICalculator
{
BigInteger f;
BigInteger[] i;
BigInteger[] sum;
BigInteger depth;
bool[] finish;
public PICalculator(int precision, BigInteger searchdepth, int threads)
{
f = BigInteger.Pow(10, precision);
sum = new BigInteger[threads];
i = new BigInteger[threads];
finish = new bool[threads];
depth = searchdepth;
for (int p = 0; p < threads; p++)
{
i[p] = depth / threads * p + 1;
sum[p] = 0;
finish[p] = false;
}
Task oTask = new Task(outputTask);
oTask.Start();
}
void outputTask()
{
bool continueThread = false;
while (continueThread == false)
{
continueThread = true;
for (int p = 0; p < finish.Length; p++)
{
continueThread = continueThread && finish[p];
}
if (Console.KeyAvailable)
{
ConsoleKeyInfo key = Console.ReadKey();
if (key.Key == ConsoleKey.Spacebar)
{
Console.Clear();
Console.CursorLeft = 0;
float[] pos = getPositions();
for (int p = 0; p < pos.Length; p++)
{
Console.WriteLine("Thread " + p + ": " + " {0:0.0000000000} %", pos[p]);
}
StringBuilder sb = new StringBuilder();
sb.Append(getResult().ToString());
sb.Insert(1, ",");
string piString = sb.ToString();
Console.WriteLine("Interim result: " + piString);
Console.WriteLine();
}
}
}
}
public bool performSteps(int thread)
{
if (i[thread] > (depth / i.Length * (thread+1)))
{
finish[thread] = true;
return false;
}
if (BigInteger.Remainder(i[thread], 2) == 0)
{
sum[thread] += f / (i[thread] * 2 + 1);
}
else
{
sum[thread] -= f / (i[thread] * 2 + 1);
}
i[thread]++;
return true;
}
public float[] getPositions()
{
float[] positions = new float[i.Length];
for (int p = 0; p < positions.Length; p++)
{
BigInteger size = depth / i.Length;
BigInteger cleanpos = i[p] - size * p;
positions[p] = (float)(cleanpos * 1000000000000 / size)/10000000000f;
}
return positions;
}
public BigInteger getResult()
{
BigInteger pi = f;
foreach (BigInteger s in sum)
{
pi += s;
}
pi *= 4;
return pi;
}
}
class Program
{
static void Main(string[] args)
{
int numThreads = 25;
int precision = 20;
BigInteger depth = 1000000000; // One Billion = 10^9
PICalculator pi = new PICalculator(precision, depth, numThreads);
Console.WriteLine("Calculation started with " + numThreads.ToString() + " threads, press space to see progress.");
Console.WriteLine();
Parallel.For(0, numThreads, i =>
{
bool unfinished = true;
while (unfinished == true)
{
unfinished = pi.performSteps(i);
}
});
StringBuilder sb = new StringBuilder();
sb.Append(pi.getResult().ToString());
sb.Insert(1,",");
string piString = sb.ToString();
Console.WriteLine("Final Result: " + piString);
ConsoleKeyInfo key = Console.ReadKey();
while (key.Key != ConsoleKey.Escape)
key = Console.ReadKey();
}
}
}
Die Ausgabe nach dem Drücken der Leertaste nach einigen Sekunden. Man sieht genau, das einige Threads noch nicht oder kaum mit ihrer Arbeit begonnen haben:
Thread 0: 21,1294500000 %
Thread 1: 0,0000025000 %
Thread 2: 20,8750300000 %
Thread 3: 0,0000025000 %
Thread 4: 20,5217100000 %
Thread 5: 0,0000025000 %
Thread 6: 20,3607900000 %
Thread 7: 0,0000025000 %
Thread 8: 20,4376300000 %
Thread 9: 0,0000025000 %
Thread 10: 20,0706800000 %
Thread 11: 0,0000025000 %
Thread 12: 20,5839600000 %
Thread 13: 0,0000025000 %
Thread 14: 20,7066900000 %
Thread 15: 0,0000025000 %
Thread 16: 20,2433900000 %
Thread 17: 0,0000025000 %
Thread 18: 20,3013200000 %
Thread 19: 0,0000025000 %
Thread 20: 20,1487700000 %
Thread 21: 0,0000025000 %
Thread 22: 20,5862100000 %
Thread 23: 0,0000025000 %
Thread 24: 0,0000025000 %
Interim result: 3,14159247739307800504