Institut für Informatik

Michael Wand
David Hartmann

Sommersemester 2020 • DIGITAL

Aufgabe Anlage zu Threads

Die Anlage enthält ein Tutorial mit den nötigsten Befehlen, um dieses Blatt bearbeiten zu können.

Aufgabe Einfache Parallelisierung

Aufgaben

1. Implementieren Sie die Funktionen
   1. void parallel_transform(std::vector<float> &v, size_t num_threads, std::function<float(float)> f);
      Startet num_threads viele std::threads um die Einträge im Vektor mit f zu transformieren.
      Die Einträge soll gleichmäßig unter den Threads verteilt werden. Der letzte Thread verarbeitet unter Umständen weniger Einträge.
      
      Wenn Sie einen std::vector<std::thread> workers verwenden, reservieren Sie den Speicher (workers.reserve()) des Vectors bevor Sie Threads darin ablegen. Bei der Vergrößerung des Vectors durch push_back werden die Werte kopiert, was bei Threads jedoch nicht funktioniert.
      
      Statt push_back können Sie Thread-Objekte auch ohne Kopien direkt mit emplace_back auf dem Vector-Speicher allokieren. emplace_back erhält dabei die selben Argumente wie der Konstruktor von std::thread.
   2. void parallel_transform(std::vector<float> &v, std::function<float(float)> f)
      Nutzt std::asyncs um die selbe Aufgabe zu lösen. C++ kümmert sich hierbei um das Management der Threads.
2. Messen Sie den Laufzeitunterschied für verschieden große Vektoren und Threadzahlen.
   
   Hinweis: Um den Laufzeitunterschied eines Codeschnipsels zu prüfen können Sie entweder die Ausführungszeit des Aufrufs messen (unter Unix-Systemen etwa mittels time)
   Direkt im Code kann dies aktuell etwa mit folgendem Code erreicht werden:
   

   #include <iostream>
   #include <chrono>
   #include <thread>
   int main(){
       using namespace std::chrono_literals;
       std::cout << "Hello waiter\n" << std::flush;
       auto start = std::chrono::high_resolution_clock::now();
       std::this_thread::sleep_for(2s);
       auto end = std::chrono::high_resolution_clock::now();
       std::chrono::duration<double, std::milli> elapsed = end-start;
       std::cout << "Waited " << elapsed.count() << " ms\n";
   }
   

3. Führen Sie den folgenden Code-Schnipsel aus. Falls „Finished“ bei Ihnen auch nach einigen Sekunden nicht angezeigt wird, erklären Sie, warum das wohl passiert. Welche minimalen Änderungen müssen unternommen werden, damit der Code funktioniert? Erklären Sie diese Wahl kurz.

   #include <iostream>
   #include <thread>
   #include <mutex>
   #include <chrono>
   
   std::mutex mutex1, mutex2;
   
   void ThreadA() {
       mutex2.lock();
       std::cout << "Thread A" << std::endl;
       std::this_thread::sleep_for(std::chrono::seconds(1));
       mutex1.lock();
       mutex2.unlock();
       mutex1.unlock();
   }
   
   void ThreadB() {
       mutex1.lock();
       std::cout << "Thread B" << std::endl;
       std::this_thread::sleep_for(std::chrono::seconds(1));
       mutex2.lock();
       mutex1.unlock();
       mutex2.unlock();
   }
   
   int main() {
       std::thread t1( ThreadA );
       std::thread t2( ThreadB );
       t1.join();
       t2.join();
       std::cout << "Finished" << std::endl;
   
       return 0;
   }
   

4. Wie Sie sicher bemerkt haben, können Sie innerhalb der parallel_transform-Threads keine Ausgabe vornehmen, ohne dass die Zeichen wild durchmischt werden, etwa hier:

   float v_new = f(v);
   std::cout << "alte :" << v << ", neue:" << v_new << std::endl;
   

   
   
   
   1. Erweitern Sie parallel_transform so, dass nach jeder Berechnung eines Wertes durch f das Ergebnis und der Index ausgegeben wird, es aber keine Vermischung der Ausgabe gibt.
      Hinweis: Verwenden Sie dafür einen Mutex.
   2. Was bedeutet diese Änderung für den Laufzeitgewinn aus Aufgabenteil 1?

Aufgabe Back to the Future

In C++ sieht die Verwendung von std::promise und std::future wie folgt aus:
(PS: Durch sleep_for werden teure Rechnungen simuliert, zu warten ergibt in diesem Beispiel natürlich keinen Sinn).

#include <future>
#include <iostream>
#include <thread>
#include <utility>
#include <chrono>

void mult(std::promise<int>& prom, int a, int b){
    prom.set_value(a*b);
    std::this_thread::sleep_for(std::chrono::seconds(2));
}

int main() {
    int a = 12;
    int b = 34;

    // Initialisieren der Promises für einen int-Wert
    std::promise<int> prod_promise;
    std::promise<int> square_promise;

    // Initialisieren der zugehörigen Futures
    std::future<int> prod_result = prod_promise.get_future();
    std::future<int> square_result = square_promise.get_future();

    // Berechnen der jeweilgen Werte in seperablen Threads
    std::thread prod_thread(mult, std::ref(prod_promise), a, b);
    std::thread square_thread([&](int a)->void {
        std::this_thread::sleep_for(std::chrono::seconds(1));
        square_promise.set_value(a*a);
    }, a);

    // Werte holen
    std::cout << "Ergebnisse der Threads:" << std::endl;
    std::cout << a << "*" << b << prod_result.get()   << std::endl;
    std::cout << a << "^2"     << square_result.get() << std::endl;

    prod_thread.join();
    square_thread.join();
    std::cout << "beide Threads sind fertig." << std::endl;
}

Konzeptionell erstellen Sie eine Variable, die aus einem anderen Thread gefüllt werden kann. Zu jedem Promise gibt es genau ein Future, das diese Variable einmalig zurückgeben kann. Das interessante dabei ist, dass das Locking, also das Warten auf die Fertigstellung der Threads erst dann erfolgt, wenn der Wert auch benötigt wird. Der Vorteil davon gegenüber direkter Verwendung von thread.join() besteht darin, dass ein Promise bereits vor der Fertigstellung eines Threads abrufbar ist. Im Beispiel erhält man das Ergebnis von prod_promise bevor der Thread fertig ist. Es ist also damit möglich, voneinander abhängige Threads in gewisser Weise zu synchronisieren.

Aufgaben

Implementieren Sie eine einfache Version der Klassen future und promise, die Sie statt std::future und std::promise im Beispiel oben verwenden können.
(D.h. das Ergebnis des Codes oben lässt sich auch mit Ihrer eigenen Implementierung, also future/promise statt std::future/std::promise ausführen und die Ausgabe ist identisch).

Hierzu ein paar Tipps:

• Weder Promise noch Future sollten den tatsächlichen Wert des Ergebnisses speichern: Im Falle der Speicherung des Wertes im Promise könnte das Promise-Objekt bereits vom Speicher gelöscht worden sein, wenn das Future den Wert holen möchte. Im Falle der Speicherung des Wertes im Future könnte dieses jedoch noch nicht existieren, wenn der Wert geschrieben werden soll. Mit anderen Worten: Sie werden ein Objekt auf den Heap legen müssen und per std::shared_ptr darauf verweisen müssen.
• Promise und Future teilen sich außerdem ein Mutex, damit sie nicht gleichzeitig auf den geteilten Speicher zugreifen.
• Falls Sie nicht die Standardimplementierung von std::shared_ptr nutzen wollen, müssen Sie darauf achten, dass Ihre eigene Implementierung Referenzzähler atomar inkrementiert/dekrementiert. Die Standardimplementierung macht dies von sich aus. Es gibt eigentlich keinen Grund, diese hier nicht zu verwenden.

Aufgabe Parallele Mandelbrotmenge

Wiederholung der Komplexen Zahlen:

Bevor wir uns der Mandelbrotmenge selbst widmen, sollen an dieser Stelle nochmals die komplexen Zahlen wiederholt werden.

Die komplexen Zahlen sind die Menge \[\mathbb{C} := \mathbb{R} + i\cdot \mathbb{R} := \{a+ib \,|\, a,b\in \mathbb{R}\},\] die mit der folgenden Struktur versehen sind: Eine komplexe Zahl \(z = a+ib\) besteht damit aus zwei reellen Zahlen \(a,b\)¹ und der imaginären Einheit \(i\), die die Eigenschaft \(i^2=-1\) besitzt. Aus dieser Eigenschaft und der herkömmlichen Multiplikation und Addition auf reellen Zahlen folgen die Rechenregeln: \[\begin{aligned} \text{Addition:}\quad &(a+ib)+(c+id) &= \quad &\, (a+c) + i(b+d)\\ \text{Multiplikation:}\quad &(a+ib)\cdot(c+id) &= \quad &\, (ac-bd) + i(bc+ad)\\ \text{Absolutbetrag (entspr. Länge im } \mathbb{R}^2\text{):} \quad &|(a+ib)| &= \quad &\, \sqrt{a^2 + b^2} \end{aligned}\] Komplexe Zahlen sind glücklicherweise bereits fest in C++ implementiert. Hier ein Beispiel aus der Dokumentation:

#include <iostream>
#include <iomanip>
#include <complex>
#include <cmath>

int main()
{
    using namespace std::complex_literals;
    std::cout << std::fixed << std::setprecision(1);

    std::complex<double> z1 = 1i * 1i;     // imaginary unit squared
    std::cout << "i * i = " << z1 << '\n';

    std::complex<double> z2 = std::pow(1i, 2); // imaginary unit squared
    std::cout << "pow(i, 2) = " << z2 << '\n';

    double PI = std::acos(-1);
    std::complex<double> z3 = std::exp(1i * PI); // Euler's formula
    std::cout << "exp(i * pi) = " << z3 << '\n';

    std::complex<double> z4 = 1. + 2i, z5 = 1. - 2i; // conjugates
    std::cout << "(1+2i)*(1-2i) = " << z4*z5 << '\n';
}

Mandelbrotmenge:

Wir beginnen mit einer beliebigen komplexen Zahl \(c\in \mathbb{C}\) und definieren die Folge

Die Mandelbrotmenge \(M\) ist die Menge, für die der Absolutbetrag dieser Folge nach oben hin beschränkt ist, mathematisch ausgedrückt:

Aufgabe

1. Nun werden wir die Mandelbrotmenge darstellen.
   
   Hinweis: Verwenden Sie anfangs eine geringere Auflösung, damit die Berechnungen schneller sind.
   
   Hier noch ein paar Tipps:
   • Erstellen Sie zuerst eine Qt-GUI, die ein Bild anzeigen kann. (Schauen Sie dazu noch einmal in die Anlage zu Blatt 10.)
   • Generieren Sie nun ein Gitter auf den Komplexen Zahlen. Das Mandelbrotmännchen ist besonders gut im Intervall \([-2,1]\times [-1,1]\) zu sehen; starten Sie also in diesem Intervall.
   • Implementieren Sie die Folge \(z_n\) für jeden Gitterpunkt in dem damit abgetasteten Koordinatensystem. (Für jeden Pixel im Bild a.k.a Gitterpunkt wird die Folge also separat berechnet).
     
     Ferner werden wir \(n\) nicht bis unendlich laufen lassen können; limitieren Sie also die maximal Anzahl an zu berechnenden Folgenelementen. (Eine Größenordnung von \(n=100\) liefert gute Ergebnisse und hat eine relativ kurze Berechnungsdauer.)
     
     Ob die jeweilige Zahl tatsächlich in der Mandelbrotmenge enthalten ist können wir also nicht bestimmen. Was wir jedoch tun können ist zu zählen, wie lange es dauert, bis die Folge die Grenze \(|z_n| > 2\) überschritt. Initialisieren Sie also vor der Schleife ein Array, das die gleichen Abmessungen hat wie das Gitter selbst und zählen Sie in genau den Einträgen hoch, in denen der Betrag der komplexe Zahl noch nicht über die 2 gekommen ist.
   • Wir wollen nun abhängig davon, wie groß die Zahl geworden ist eine Farbe festlegen. Dies kann auf verschiedene Arten und Weisen gelöst werden. Am Einfachsten ist es zwischen zwei Farben \(c_i = (r_i, g_i, b_i), i=1,2\) zu interpolieren, \[ c_1 \cdot t + c_2 \cdot (1-t), t\in [0,1], \] oder noch einfacher: schwarz für kleine Werte und Weiß für Große Werte zu wählen.
     Optional: Eine andere Möglichkeit wäre ein Paket wie etwa https://github.com/yuki-koyama/tinycolormap zu verwenden. Die Einbindung in C++ ist dabei sehr einfach. (Es muss nur eine Header-Datei inkludiert werden.)
2. Nun zum Bezug Parallelisierung: Implementieren Sie auch hier das parallele Rechnen aus Aufgabe 1; Sorgen Sie dafür, dass das Bild in gleichmäßige quadratische Blöcke unterteilt wird und nun unabhängige Threads das Bild bemalen sobald die Rechnungen fertig sind. Es gibt hierbei viele Möglichkeiten das Problem zu lösen. Jede Lösung, bei der man sieht, dass Abschnitte abhängig von der Berechnungsdauer der Menge unterschiedlich schnell werden ist korrekt.
   
   Hinweis: Denken Sie daran die GUI zu neuzuzeichnen, wenn sich etwas ändert.
   (repaint forciert ein neuzuzeichnen des Fensters.)
3. Bonus Sie werden sicher bemerkt haben, dass einige Teile des Bildes deutlich schneller fertig sind als andere. Überlegen Sie sich ein einfaches Schema, wie diese Last verteilt werden kann und implementieren Sie dies.
4. Bonus: Was passiert, wenn Sie die Anzahl der Schleifendurchläufe erhöhen / senken?
5. Bonus: Was passiert, wenn Sie die Schranke 2 verändern? Können Sie erklären warum Sie das beobachten?
6. Bonus:
   Fügen Sie nun Maus-Interaktion hinzu, indem Sie den Nutzer die Möglichkeit geben hinein- und hinauszuzoomen und das Bild zu verschieben. Sie können dazu beispielsweise das MousePressEvent verwenden. (Siehe Skript: e.X(),e.Y() liefert Ihnen die Koordinaten in Ihrem selbstdefinierten Gitter.
   
   Achten Sie bei der Anzeige (und vor allem beim Zoomen) darauf, dass die x-Achse und die y-Achse gleich skaliert sind, da sonst das Ergebnis verzerrt aussieht.
   
   Dies Richtig zu machen und in das bestehende Programm inklusive Multithreading einzubauen Bedarf etwas Umstrukturierung, daher gibt es hier viele Zusatzpunkte.
7. Bonus:
   Mit wenig Aufwand verbunden, jedoch sehr interessant: Die Mandelbrotmenge kann man als Spezialfall einer Funktion ansehen, die die Struktur der Folge ausgehend von einer komplexen Zahl auswertet.
   
   Diese allgemeinere Vorstellung führt zur Julia-Menge. Mit sehr wenig Aufwand können Sie nun andere ähnliche Strukturen wie die Mandelbrotmenge erstellen, indem Sie Ihr Gitter nicht für \(c\) einsetzen sondern für \(z_0\) und für \(c\) eine beliebige andere (feste) komplexe Zahl im Radius \(|c|\le 2\) wählen. Die Folge lautet dann \[\begin{aligned} z_0 &\text{ beliebig}, c \text{ fest für alle } z_0\\ z_{n+1} &= z_n^2 + c, \quad \text{ für } n\ge 0. \end{aligned} \] Testen Sie dies aus und achten Sie insbesondere darauf, wie sich die Mengen ändern, abhängig davon ob die Zahl \(c\) selbst in der ursprünglichen Mandelbrotmenge liegt oder nicht. Sie können aber auch das interaktiv gestalten: Erstellen Sie hierfür ein zweites Fenster, das die Mandelbrotmenge in Gänze zeigt. Per Mausklick wählen sie nun das \(c\), sodass ihr Hauptfenster als „Lupe“ auf der Mandelbrotmenge agiert. Auf YouTube finden sich dazu schöne Visualisierungen. Zum Beispiel dieses.

[1] Die komplexen Zahlen unterscheiden sich von der Menge \(\mathbb{R}\times\mathbb{R}\) der zwei-dimensionalen reellen Vektoren nur dadurch, dass zusätzlich ein „richtiges“ Produkt zwischen Paaren von solchen Vektoren (also den komplexen Zahlen) definiert ist. Die Schreibweise mit dem „\(i\)“ ist historisch bedingt und verwirrt vielleicht eher.