===============================
Aufteilung eines Indexbereiches                                         [TOC:2]
===============================

Es ist ein wiederkehrendes Problem, dass ein Indexbereich $[0, N)$
auf $k$ Threads aufzuteilen ist. Insbesondere wenn die einzelnen Indizes mit
Elementen eines im Speicher konsekutiv hintereinander angeordneten
Arrays verbunden sind, dann es sinnvoll, die von den einzelnen Threads
zu bearbeitenden Bereiche ebenfalls zusammenhängend zu belassen, damit
Cache-Konflikte vermieden werden, bei denen zwei Threads auf die
gleiche Cache-Line zugreifen, wobei mindestens einer der beiden Threads
den Inhalt verändern möchte.

Dies könnte durchaus geschehen, wenn die Aufteilung anders erfolgen
würde. Im folgenden Beispiel sind die Bereiche nicht zusammenhängend.
Stattdessen erhält der erste Thread die Zeilen $0, k, 2k, \dots$,
der zweite Thread die Zeilen $1, k+1, 2k+1, \dots$ usw.:

---- CODE (type=cpp) ----------------------------------------------------------
GeMatrix<double> A(N, N);
std::vector<std::thread> threads(nof_threads);
unsigned int job_size = A.numRows / nof_threads;
unsigned int remainder = A.numRows % nof_threads;
for (int index = 0; index < nof_threads; ++index) {
   GeMatrix<double>::Index num_rows = job_size;
   if (index < remainder) ++num_rows;
   auto A_ = GeMatrixView<double>(num_rows, A.numCols,
      &A(index, 0), A.incRow * nof_threads, A.incCol);
   threads[index] = std::thread([=]() mutable { randomInit(A_); });
}
for (int index = 0; index < nof_threads; ++index) {
   threads[index].join();
}
-------------------------------------------------------------------------------

Da die Matrizen (per Voreinstellung) in `ColMajor` abgelegt sind,
führt dies zu Konflikten und damit zu einer etwas längeren Zeit:

---- SHELL (path=session13) ---------------------------------------------------------
g++ -O3 -std=c++11 -o random_init7 -I/home/numerik/pub/hpc/session13 random_init7.cpp
./random_init7
-------------------------------------------------------------------------------------

:import:session13/random_init7.cpp

Aufgabe
=======

Da es im Normalfall vorteilhaft erscheint, die Bereiche zusammenhängend
zu belassen, lohnt es sich, hierfür eine kleine Hilfsklasse `Slices`
anzulegen mit folgenden Anforderungen:

 * Der Konstruktor sollte die Zahl der Threads und die Intervallgröße $N$ erhalten.
 * Die Methode `offset` sollte für den Beginn des Intervalls für den $i$-ten Thread
   liefern ($i$ wird als Parameter übergeben).
 * Die Methode `size` sollte die Größe des Intervalls für den $i$-ten Thread
   zurückgeben.

Dann könnte die Klasse folgendermaßen genutzt werden:

---- CODE (type=cpp) ----------------------------------------------------------
Slices slices(nof_threads, A.numRows);
for (int index = 0; index < nof_threads; ++index) {
   auto offset = slices.offset(index);
   auto size = slices.size(index);
   threads[index] = std::thread(
      /* lambda expression operating on [offset, offset+size) */
   );
}
-------------------------------------------------------------------------------

Es könnte auch sinnvoll sein, `Slices` als Template-Klasse auszuführen mit
einem wählbaren Typen für einen Wert aus dem Intervall.

Entwickeln Sie eine entsprechende Klasse und passen Sie die Initialisierung
der Matrix so an, dass die Klasse hierfür verwendet wird.

:navigate: up    -> doc:index
           back  -> doc:session13/page06
           next  -> doc:session13/page08