Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • 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.
      
      Statt push_back können Sie Thread-Objekte ohne Kopieren direkt mit emplace_back im Vector-Speicher allokieren. emplace_back erhält dabei dieselben Argumente wie der Konstruktor von std::thread.
   2. void parallel_transform(std::vector<float> &v, size_t num_asyncs, 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. Verteilen Sie hierbei die Einträge wieder gleichmäßig auf die Async-Instanzen.
2. Messen Sie den Laufzeitunterschied für verschieden große Vektoren und Threadzahlen.
   
   Hinweis: Direkt im Code kann die Laufzeitmessung 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 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 thread_a() {
       mutex2.lock();
       std::cout << "Thread A" << std::endl;
       std::this_thread::sleep_for(std::chrono::seconds(1));
       mutex1.lock();
       mutex2.unlock();
       mutex1.unlock();
   }
   
   void thread_b() {
       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(thread_a);
       std::thread t2(thread_b);
       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. Verwenden Sie dafür einen Mutex.
   2. Was bedeutet diese Änderung für den Laufzeitgewinn aus Aufgabenteil 1?

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. Stellen Sie die Mandelbrotmenge mithilfe einer Qt-basierten grafischen Oberfläche dar.
   
   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.
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: Sie können mit repaint das Fenster zwischendurch neuzeichnen.
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.

[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.