DIGITAL
Nicht nur Rechenkluster und die haushaltsüblichen Multicpu-Systeme fördern das Arbeiten mit parallelisierbaren Algorithmen. Auch Benutzeroberflächen (Sie möchten nicht, dass Ihr Programm stehen bleibt, wenn sie eine aufwändige Rechnung durchführen) und Webprotokolle, die das Internet mit asynchronen (non-blocking) Ansätzen zu mehr gleichzeitig möglichen Anfragen pro Anwendung führte, benötigen mehr als einen Thread pro Programm. Auf diesem Übungsblatt werden wir uns einige einfache Ansätze zum Thema „Parallelisierung“ anschauen.
Die Anlage enthält ein Tutorial mit den nötigsten Befehlen, um dieses Blatt bearbeiten zu können.
void parallel_transform(std::vector<float> &v, size_t num_threads, std::function<float(float)> f);
num_threads
viele std::thread
s um die Einträge im Vektor mit f
zu transformieren. 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
.void parallel_transform(std::vector<float> &v, size_t num_asyncs, std::function<float(float)> f)
std::async
s 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.#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";
}
#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;
}
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;
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.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\)1 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';
}
Wir beginnen mit einer beliebigen komplexen Zahl \(c\in \mathbb{C}\) und definieren die Folge
\[\begin{aligned} z_0 &= 0 z_{n+1} &= z_n^2 + c, \quad \text{ für } n\ge 0. \end{aligned}\]Die Mandelbrotmenge \(M\) ist die Menge, für die der Absolutbetrag dieser Folge nach oben hin beschränkt ist, mathematisch ausgedrückt:
\[c \in M \Leftrightarrow \limsup_{n\rightarrow \infty} |z_n| \le 2. \]repaint
das Fenster zwischendurch neuzeichnen.MousePressEvent
verwenden. (Siehe Skript: e.X(),e.Y()
liefert Ihnen die Koordinaten in Ihrem selbstdefinierten Gitter.[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.