Threads

Threads sind eine Abstraktion des Betriebssystems, die es ermöglicht, mehrere Ausführungsfäden, jeweils mit eigenem Stack und eigenen Registern ausgestattet, in einem gemeinsamen Adressraum arbeiten zu lassen. Der Einsatz lohnt sich insbesondere auf Mehrprozessormaschinen oder Prozessoren mit mehreren Kernen, die auf gemeinsamen Speicher operieren.

Prinzipiell ist festzuhalten, dass der Umgang mit Threads sehr fehleranfällig sein kann, wenn mehrere Threads im gemeinsamen Speicher konkurrierend auf die gleiche Datenstruktur zugreifen. Vielfach ist Programmtext, der bei einer sequentiellen Ausführung wohldefiniert und korrekt ist, nicht thread safe, d.h. nicht mehr länger wohldefiniert, wenn mehrere Threads ihn gleichzeitig nutzen. Ein Problem waren hier die älteren Fassungen der GEMM-Packfunktionen, die mit globalen Speicher gearbeitet haben. Dies kann nicht gut gehen, wenn mehrere Threads konkurrierend die gleichen globalen Datenstrukturen für verschiedene Matrix-Matrix-Multiplikationen nutzen.

Zwar gibt es die Idee für Threads bereits seit 1965, interessant wurden sie aber erst mit der Einführung von Mehrprozessormaschinen mit gemeinsamen Speicher Anfang der 1990er-Jahre. Nach anfänglichen divergierenden Bibliotheksschnittstellen, wurde 1995 im Rahmen des POSIX-Standards eine standardisierte Schnittstelle für Threads entwickelt. Diese Schnittstelle wurde sehr lange auch von C++ genutzt. Wegen ihrer Unhandlichkeit in C++ entstanden darauf aufbauende Bibliotheken, insbesondere in der Boost-Library. Letztere Schnittstelle wurde bei C++11 weitgehend unverändert in den C++-Standard übernommen und diesen werden wir hier im einzelnen vorstellen.

Ein Prozess beginnt zunächst mit genau einem Thread, d.h. wenn main() aufgerufen wird, haben wir noch keine Parallelisierung. Threads können jederzeit erzeugt werden und es ist möglich, auf das Ende eines Threads zu warten. Außerdem stehen weitere Synchronisierungsmöglichkeiten zwischen Threads zur Verfügung.

Threads unterstützen das Fork-and-Join-Pattern, d.h. wir erzeugen mehrere Threads und am Ende warten wir darauf, dass diese mit dem Aufruf des Funktionsobjekt fertig sind. Diese Synchronisierung am Ende ist verpflichtend, wenn die Threads nicht explizit unabhängig gemacht werden (detached).

Um Threads in C++ erzeugen, benötigen wir Objekte des Typs std::thread aus <thread>. Ein solches Objekt kann sich in einem der folgenden Zustände befinden:

Thread-Objekt, das mit dem default constructor erzeugt wurde, d.h. ohne Parameter. Dieses ist noch mit keinem Thread verbunden, somit nur eine leere Hülle.
Thread-Objekt, das mit einem laufenden Thread verbunden ist. Ein solches Objekt wird erzeugt, indem es mit einem Funktionsobjekt konstruiert wird oder indem einem leeren Thread-Objekt ein frisch konstruiertes Thread-Objekt mit Funktionsobjekt zugewiesen wird. Die Aktivität des Threads besteht darin, das Funktionsobjekt ohne Parameter aufzurufen.
Thread-Objekt, dessen Thread beendet ist und für den die join-Methode aufgerufen worden ist, d.h. der Aufruf des Funktionsobjekt ist beendet und eine Synchronisierung hat bereits stattgefunden.
Thread-Objekte, die von ihrem Thread getrennt worden sind (detached).

Bei den größeren Matrizen kann sich die Initialisierung etwas hinziehen. Entsprechend lohnt es sich, diese zu parallelisieren. Dies ist besonders einfach, wenn wir mehrere Matrizen zu initialisieren haben:

using namespace hpc::matvec;
GeMatrix<double> A(1000, 1000);
GeMatrix<double> B(1000, 1000);
GeMatrix<double> C(1000, 1000);

/* start three threads that initialize A, B, and C */
std::thread t1([&](){ randomInit(A); });
std::thread t2([&](){ randomInit(B); });
std::thread t3([&](){ randomInit(C); });

/* wait until they are finished */
t1.join(); t2.join(); t3.join();

Alle drei Thread-Objekte werden hier sofort mit einem Lambda-Ausdruck initialisiert. Entsprechend werden jeweils die Threads sofort erzeugt und diese legen sofort los mit dem Aufruf des Lambda-Ausdrucks. Danach haben wir insgesamt vier Threads: drei neu erzeugte und nach wie vor der erste Thread, der unmittelbar danach weitermacht. Dieser Teil entspricht dem fork des Fork-and-Join-Patterns.

Danach warten wir auf die Vollendung der einzelnen Threads, indem wir für jeden Thread die join-Methode aufrufen. Das blockiert den Aufrufer jeweils bis der Aufruf des jeweiligen Funktionsobjekts beendet ist. Sollte der Aufruf bereits beendet sein, kehrt join sofort zurück.

Auf die Synchronisierung darf nicht ohne weiteres verzichtet werden. Im folgenden Beispiel werden drei Threads erzeugt und jedes der Thread-Objekte wird am Ende des Blocks abgebaut, ohne dass diese Synchronisierung stattfindet:

/* start three threads that initialize A, B, and C */
{
   std::thread t1([&](){ randomInit(A); });
   std::thread t2([&](){ randomInit(B); });
   std::thread t3([&](){ randomInit(C); });
}

Dann kommt es bei der Ausführung zum Crash:

$shell> g++ -O3 -std=c++11 -o bad_init1 -I/home/numerik/pub/hpc/session13 bad_init1.cpp
$shell> ./bad_init1
terminate called without an active exception
/home/borchert/hpc/commons/uebungen/tmp/shell.sh: line 2: 18582 Abort                   (core dumped) ./bad_init1

Der Crash ist hier von C++-Standard vorgeschrieben. Wenn ein Thread-Objekt abgebaut wird (d.h. der destructor aufgerufen wird), dann muss das Objekt in einem der beiden Endzustände sein, d.h. es wurde entweder join oder detach aufgerufen.

Aufgaben

Da das Aufsetzen eines Pseudo-Zufallszahlengenerators nicht ganz billig ist, könnte auch folgende Art der Initialisierung in Erwägung gezogen werden:

session13/bad_init2.cpp

        #include <thread>
        #include <random>
        #include <hpc/matvec/gematrix.h>
        #include <hpc/matvec/apply.h>
        #include <hpc/matvec/print.h>
        
        template<typename MA, typename Func>
        typename std::enable_if<hpc::matvec::IsRealGeMatrix<MA>::value, void>::type
        randomInit(MA& A, Func& f) {
           using ElementType = typename MA::ElementType;
           using Index = typename MA::Index;
        
           hpc::matvec::apply(A, [&](ElementType& val, Index i, Index j) -> void {
              val = f();
           });
        }
        
        int main() {
           std::random_device random;
           std::mt19937 mt(random());
           std::uniform_real_distribution<double> uniform(-100,100);
           auto rand = [&]() -> double { return uniform(mt); };
        
           using namespace hpc::matvec;
           GeMatrix<double> A(1000, 1000);
           GeMatrix<double> B(1000, 1000);
           GeMatrix<double> C(1000, 1000);
        
           /* start three threads that initialize A, B, and C */
           std::thread t1([&](){ randomInit(A, rand); });
           std::thread t2([&](){ randomInit(B, rand); });
           std::thread t3([&](){ randomInit(C, rand); });
        
           /* wait until they are finished */
           t1.join(); t2.join(); t3.join();
        
           /* print a small block of each of the initialized matrices */
           auto A1 = A(500, 500, 5, 5);
           auto B1 = B(500, 500, 5, 5);
           auto C1 = C(500, 500, 5, 5);
           print(A1, "A1");
           print(B1, "B1");
           print(C1, "C1");
        }
        

Wäre das zulässig? Wenn nicht, wo ist das Problem?

Angenommen, es wäre nur eine einzige Matrix A zu initialisieren. Wie könnte die Initialisierung der Matrix auf zwei Threads aufgeteilt werden? Eine Vorlage hierzu:

session13/random_init4.cpp

        #include <thread>
        #include <random>
        #include <hpc/matvec/gematrix.h>
        #include <hpc/matvec/apply.h>
        #include <hpc/matvec/print.h>
        
        template<typename MA>
        typename std::enable_if<hpc::matvec::IsRealGeMatrix<MA>::value, void>::type
        randomInit(MA& A) {
           using ElementType = typename MA::ElementType;
           using Index = typename MA::Index;
        
           std::random_device random;
           std::mt19937 mt(random());
           std::uniform_real_distribution<ElementType> uniform(-100,100);
        
           hpc::matvec::apply(A, [&](ElementType& val, Index i, Index j) -> void {
              val = uniform(mt);
           });
        }
        
        int main() {
           using namespace hpc::matvec;
           GeMatrix<double> A(1000, 1000);
        
           randomInit(A);
        
           /* print a small block of each of the initialized matrices */
           auto A1 = A(500, 500, 5, 5);
           print(A1, "A1");
        }
        