parprog.tex

\documentclass[8pt]{extarticle}
\usepackage{helvet}
\usepackage[T1]{fontenc}
\usepackage[a4paper,landscape,margin=0.5cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{xcolor}

\usepackage{listings}
\usepackage{tcolorbox}
\tcbuselibrary{breakable}
\tcbuselibrary{skins}
\usepackage{caption}
\usepackage{multicol}

\BeforeBeginEnvironment{lstlisting}{\begin{tcolorbox}[boxsep=-3mm]}
\AfterEndEnvironment{lstlisting}{\end{tcolorbox}}

\lstset{basicstyle=\tiny}

\renewcommand{\familydefault}{\sfdefault}

\let\oldtextbf\textbf
\renewcommand{\textbf}{\tiny\oldtextbf}

\parindent0pt

\begin{document}
\begin{multicols*}{5}
\textbf{[Java Thread]}
In Java können Threads mittels Vererbung hergestellt werden. Hierzu gibt es die Basisklasse \textbf{Thread}. Beim Ableiten von der Klasse muss nur \textbf{public void run()} überschrieben werden. Für den Start des Threads muss dann die Methode \textbf{start()} aufgerufen werden. EIN AUFRUF VON \textbf{run()} WÜRDE BLOCKIEREN!
\begin{lstlisting}[language=java]
class MyThread extends Thread {
  public void run() {
    do_something();
  }
}
//...
public static void main(String args[]) {
  (new MyThread()).start();
}
\end{lstlisting}
Des Weiteren gibt es das \textbf{Runnable} Interface, welches ähnlich dem Thread funktioniert. Es kann von einer Klasse implementiert werden. Auch hier muss die Methode \textbf{public void run()} überschrieben werden. Jedoch muss dann eine Instanz des neuen Runnables der Thread-Klasse im Konstruktor übergeben werden.
\begin{lstlisting}[language=java]
class MyRunnable implements Runnable {
  public void run() {
    do_something();
  }
}
//...
public static void main(String args[]) {
  (new Thread(new MyRunnable())).start();
}
\end{lstlisting}
\textbf{Lambdas} sind eine weitere Möglichkeit um einen Thread zu erstellen. Hier wird dem Konstruktor von \textbf{Thread} ein Lambda übergeben und der Thread gleich gestartet.
\begin{lstlisting}[language=java]
public static void main(String args[]) {
  (new Thread(() -> {
    do_something();
  })).start();
}
\end{lstlisting}
Eine vierte Möglichkeit wäre eine \textbf{anonyme innere Klasse}.
\begin{lstlisting}[language=java]
public static void main(String args[]) {
  (new Thread(new Runnable() {
    @Override
    public void run() {
      do_something();
    }
  })).start();
}
\end{lstlisting}
Eine spezielle Art von Threads sind \textbf{Daemon Threads}. Diese Threads verhindern das Beenden des Programms NICHT. Der \textbf{Garbage Collector} ist ein solcher Thread.
\begin{lstlisting}[language=java]
public static void main(String args[]) {
  // ...
  someThread.setDaemon(true);
  someThread.start();
  // wait for user input
  // otherwise program will stop
  System.in.read();
}
\end{lstlisting}
Mit \textbf{Runtime.getRuntime().availableProcessors()} kann man bestimmen wieviele Prozessoren in einem System vorhanden sind. Die maximale Anzahl Threads errechnet sich aus dem verfügbaren Speicher des Systems und der Grösse eines Threads; z.B. entsprechen ca. 110'000 Threads auf Windows 64-Bit in etwa 7GB Speicher. Bei mehr Threads beginnt das System zu swappen und wird langsam.\\\\
\textbf{[synchronized]} Für einfachen (ineffizienten) \textbf{gegenseitigen Ausschluss} (mutual exclusion) gibt es das \textbf{synchronized} Schlüsselwort. Es muss vor dem Typ der Funktion angegeben werden. Der Auschluss via synchronized funktioniert mittels eines \textbf{Monitor-Locks} (siehe Monitor Object [POSA2]). Es kann immer nur ein Thread eine synchronized Methode auf einem Objekt ausführen. Alle anderen müssen warten, \textbf{selbst wenn sie eine andere synchronized Methode aufrufen}. \textbf{synchronized} kann auch auf Block-level verwendet werden. Die Synchronisierung mittels \textbf{synchronized} ist \textbf{reentrant}, das heisst ein Thread kann mehrere \textbf{synchronized} Methoden verschachtelt aufrufen.
\begin{lstlisting}[language=java]
public class MyClass {
  public synchronized void syncMethOne(){
    dangerous_things();
  }
  public synchronized void syncMethTwo(){
    dangerous_things();
  }
  public void partlySync(){
    non_dangerous_things();
    synchronized(this) {
      dangerous_things();
    }
  }
}
\end{lstlisting}
Da jedes Objekt ein \textbf{Monitor Lock} besitzt kann auf jedem Objekt ge\textbf{synchronized} werden (also auch auf Member-Objekten). Bedingungen sollten in \textbf{synchronized} Methoden mit \textbf{while} geprüft werden, da sonst die Gefahr besteht dass man fälschlicherweise weitermacht. Warten kann man mit \textbf{wait()} und notifizieren mit \textbf{notify} und \textbf{notifyAll()} wobei \textbf{notify()} \textbf{irgendeinen (!!!) wartenden Thread} weckt. FAUSTREGEL: Bei unterschiedlichen Wartebedingungen mit \textbf{notifyAll()} wecken.\\\\
Vorsicht: Sobald \textbf{wait()} benutzt wird, muss die \textbf{throws InterruptedException} verwendet werden.\\\\
\textbf{[Semphore]} sind "Zähler". Mit \textbf{acquire()} wird eine "Marke" entfernt, mit \textbf{release()} eine zurückgelegt. \textbf{acquire()} blockiert, falls gerade keine "Marke" frei ist. \textbf{Semaphore} können fair sein (\textbf{new Semaphore(n, true)}) und folgen dan dem FIFO-Prinzip.\\\\
\textbf{[Locks \& Conditions]} können verwendet werden um ähnliche Funktionalität wie beim \textbf{Monitor} zu erreichen, mit dem grossen Unterschied, dass hier die Wartebedingungen gezielt "notifiziert" (via \textbf{signal()}) werden können. Jedem \textbf{Lock} können mehrere \textbf{Conditions} zugeordnet sein, auf welche Threads via \textbf{await()} warten können.
\begin{lstlisting}[language=java]
public class MyClass {
  // fair lock
  private Lock mon = new ReentrantLock(true);
  // Conditions
  private Condition con1 = mon.newCondition();
  private Condition con2 = mon.newCondition();

  public void put(){
    mon.lock()
    try {
      while(canPut == false) {
        con1.await();
      }
      // do put
      con2.signal();
    } finally { mon.unlock(); }
  }

  public void get(){
    mon.lock()
    try {
      while(canGet == false) {
        con2.await();
      }
      // do put
      con1.signal();
    } finally { mon.unlock(); }
  }
}
\end{lstlisting}
\textbf{[Read-Write-Locks]} erlauben feingranulares Sperren. Da Sperren nicht nötig ist wenn alle Threads \textbf{nur lesen}, können beliebig viele Threads gleichzeitig ein \textbf{Read-Lock} halten, jedoch \textbf{nur einer} ein \textbf{Write-Lock}. \textbf{Read-Write-Locks} können NICHT geupgraded werden.\\\\
\textbf{[CountdownLatch]} bietet einen "Einweg-Synchronisationspunkt". Bei der Initialisierung muss angegeben werden, auf wieviele Threads gewartet werden soll. Threads verwenden \textbf{countDown()} auf dem Latch um den Zähler zu dekrementieren. Mit \textbf{await()} wird gewartet bis der Latch auf 0 ist. Der Latch kann nicht wiederverwendet werden.\\\\
\textbf{[CyclicBarrier]} ist ähnlich wie \textbf{CountdownLatch}, kann aber wiederverwendet werden. Sie wird bei \textbf{await()} dekrementiert; \textbf{getParties()} ermittelt die Anzahl Teilnahmer der Barriere.\\\\
\textbf{[Phaser]} stellt eine verallgemeinerte \textbf{CyclicBarrier} dar. Mit \textbf{arriveAndAwaitAdvance()} wird auf die Freigabe gewartet. Threads können sich mit \textbf{register()} am Phaser an- und mit \textbf{arriveAndDeregister} abmelden.\\
\textbf{[Exchanger]} ermöglicht es, zwischen zwei Threads Objekte auszutauschen. \textbf{exchange(obj1)} wartet, bis der andere Thread auch \textbf{exchange(obj2)} aufgerufen hat.\\\\
\textbf{[Race Conditions]} werden in \textbf{low-level (Data Race)} und \textbf{high-level (Semantic Race)} unterteilt. \textbf{Low-level} Races treten auf wenn unsynchronisiert auf den gleichen Speicher (Variable, Array-Element, ...) zugegriffen wird. \textbf{High-level} Races sind Race-Conditions in der Programmlogik. Sie treten auf, wenn die Critical Sections nicht ausreichend geschützt sind.\\\\
Auf Synchronisierung kann verzichtet werden, wenn entweder \textbf{Unveränderlichkeit} (z.B Java final) gegeben ist oder veränderliche Objekte in breits synchronisierte Objekte eingesperrt sind (\textbf{Confinement}).\\\\
\textbf{[Collections]} aus \textbf{java.util} sind grundsätzlich \textbf{nicht threadsafe}. Es gibt jedoch threadsafe Collections in \textbf{java.util.concurrent}.\\\\
\textbf{[Deadlocks]} treten auf wenn sich Threads gegenseitig sperren. Folgende Bedingungen müssen eintreten damit es einen Deadlock gibt: \textbf{Geschachtelte Locks} UND \textbf{Zyklische Warteabhängigkeiten} UND \textbf{Gegenseitiger Ausschluss} UND \textbf{Kein Timeout}. Deadlocks lassen sich durch Einführen einer \textbf{linearen Sperrordnung} oder \textbf{grobgranularer Sperrung} lösen.\\\\
\textbf{[Starvation]} tritt ein wenn einem Thread immer wieder die Möglichkeit zu arbeiten "weggeschnappt" wird. Dies lässt sich durch \textbf{faire} Synchronisationsprimitiven lösen.\\\\
\textbf{[Thread-Pools]} besitzen eine \textbf{Task Queue} in welcher Tasks eingereiht und dann von einem freien \textbf{Worker Thread} bearbeitet werden. In Java erzeugt man \textbf{Thread Pools} mit der Factory Klasse \textbf{Executors}. Zur Auswahl stehen \textbf{newFixedThreadPool(nofThreads)}, \textbf{newChachedThreadPool()} (automatische Thread Zahl) und \textbf{newWorkStealingPool()}. Gesondert gibt es noch den \textbf{ForkJoinPool}, welcher es erlaubt, rekursive Tasks zu formulieren. \textbf{Thread Pools} haben den Vorteil, dass nicht unnötig viele Threads erzeugt werden. Einschränkung: Tasks dürfen nicht von einander abhängig sein (\textbf{Deadlock}-Gefahr!). Nur der \textbf{ForkJoinPool} setzt \textbf{Daemon Threads} ein, alle anderen Pools müssen mit \textbf{myPool.shutdown()} beendet werden. Tasks werden mittels des \textbf{Callable} Interfaces implementiert:
\begin{lstlisting}[language=java]
class CalcTask implements Callable<Integer> {
  @Override
  public Integer call() throws Exception {
    int val = 42;
    // long running stuff
    return val;
  }
}
ExecutorService pool =
  Executors.newFixedThreadPool(2);
Future<Integer> fut1, fut2;
// ...
fut1 = pool.submit(new CalcTask());
fut2 = pool.submit(new CalcTask());
// ...
int res1 = fut1.get();
int res2 = fut2.get();
// ...
pool.shutdown();
\end{lstlisting}
\begin{lstlisting}[language=java]
class MSTask extends RecursiveAction {
  private static final int THRESHOLD = 1;
  private int[] array;
  private int p1, p2;

  public MSTask(int[] array,int p1, int p2) {
    this.p1 = p1; this.p2 = p2;
    this.array = array;
  }

  @Override
  public void compute() {
    if (parameter > THRESHOLD) {
      int mid = (p1+p2)/2;
      MSTask t1 = new MSTask(array, p1, mid);
      MSTask t2 = new MSTask(array, mid, p2);
      invokeAll(t1, t2);
      merge(array, p1, mid, p2);
    } else {
      mergeSort(array, p1, p2);
    }
  }
}

ForkJoinPool pool = new ForkJoinPool();
pool.invoke(new MSTask(array, 0, array.length));
\end{lstlisting}
\textbf{[Futures]} repräsentieren zukünftige Ergebnisse (sie sind Proxies im Sinne des PROXY Patterns [GoF]) welche mittels \textbf{get()} abgeholt werden. \textbf{get()} blockiert, bis ein Ergebenis da ist! Beim Auftreten einer unbehandelten Exception liefert \textbf{get()} diese geschachtelt in einer \textbf{ExecutionException}. Mittels \textbf{cancel()} kann ein Task aus der Warteschlange entfert werden (bricht aber nicht den laufenden Task ab).\\\\
\textbf{[Work Stealing]} ist ein Verfahren das bei Thread Pools eingesetzt wird bei welchem es eine \textbf{globale FIFO} Queue und für jeden Worker Thread eine \textbf{locale LIFO} Queue gibt. Tasks in der globalen Queue werden (per Default) "vernachlässigt" aber der Work Stealing Pool kann auch auf FIFO umgestellt werden.\\\\
\textbf{[Asynchrone Aufrufe]} erlauben das Auslagern von langen Operationen auf einen anderen Thread oder Pool. Es gibt zwei Ansätze: Caller-zentrisch (\textbf{pull}) und Callee-zentrisch (\textbf{push}). Pull setzt auf \textbf{Future} Objekte während pull auf \textbf{Completion Callbacks} setzt. Für Completion Callbacks eignet sich als Interface, z.B. \textbf{java.util.function.Consumer}.
\begin{lstlisting}[language=java]
interface Consumer<T> {
  void accept(T result);
}
// ...
void asyncOp(int in, Consumer<Integer> cb) {
  pool.submit(() -> {
    Integer res = longOperation(in);
    cb.accept(res);
  });
}
// ...
asyncOp(42, res -> {
  System.out.println(res);
});
\end{lstlisting}
\textbf{[Continuations]} bieten in Java 8 eine Möglichkeit, eine Folgeoperation an einen Task anzuhängen. Dazu verwendet man \textbf{CompletableFuture<T>}:
\begin{lstlisting}[language=java]
CompletableFuture<Long> fut = 
  CompletableFuture.supplyAsync(() -> longOp());
//...
fut.thenAccept(res -> System.out.println(res));
\end{lstlisting}
Die Continuation läuft auf dem Initiator \textbf{NUR WENN} die Future das Ergebnis schon hat, sonst auf einem beliebigen Worker Thread. Mittels \textbf{allOf()} und \textbf{any()} kann eine Continuation an mehrere Futures gebunden werden:
\begin{lstlisting}[language=java]
// wait for ALL Futures to arrive
CompletableFuture.allOf(fut1, fut2)
  .thenAccept(cont);
// wait for ANY Future to arrive
CompletableFuture.any(fut1, fut2)
  .thenAccept(cont);
\end{lstlisting}
\textbf{[.NET]} Threads "funktionieren" ähnlich wie Java Threads, nur ohne Vererbung sondern mit \textbf{Delegates} und mit dem Unterschied, dass \textbf{uncaught Exceptions} per Default zum \textbf{Programmabbruch} führen. Hier ein Threading-Beispiel mit einem Lambda:
\begin{lstlisting}[language=c++]
Thread myThread = new Thread(() => {
  for(int i = 0; i < 100; ++i) {
    Console.WriteLine("Step {0}", i);
  }
});
// ...
myThread.Start();
myThread.Join();
\end{lstlisting}
Im Gegensatz zu Java 8 können in .NET Lambdas auch \textbf{non-final} Variablen aus dem umgebenden Scope (via Referenzen) zugegriffen werden (AUCH SCHREIBEND!!!) was die Chance auf \textbf{low-level} Races erhöht.\\\\
\textbf{[Delegates]} sind vergleichbar mit Funktionszeigern welche ein implizites \textbf{this} besitzen. Sie sind damit leichgewichtiger als Java Interfaces, da sie keine Vererbungshierarchie aufweisen. Lambdas sind im Prinzip eine Abbildung von Delegates.\\\\
\textbf{[Monitor]} ist in .NET über \textbf{lock(someObj)} verfügbar, welches ähnlich wie \textbf{synchronized} vor einen Block gehängt wird. Best Practice: sperre ein Hilfsobjekt und nicht das eigene Objekt. Zum Warten und Benachrichten werden \textbf{Monitor.Wait(lock)}, \textbf{Monitor.Pulse()} und \textbf{Monitor.PulseAll()} verwendet. Der .NET Monitor ist fair und \textbf{Pulse()} weckt immer den Thread, der schon am längsten wartet.
\begin{lstlisting}[language=c++]
class Account {
  // ...
  private object syncObject = new object();

  public void syncOp1() {
    //...
    lock(syncObject) {
      dangerous_things();
      Monitor.PulseAll();
    }
  }
}
\end{lstlisting}
\textbf{[Andere Primitiven]} in .NET sind analog zu Java, ausser den fehlenden \textbf{Locks \& Conditions} und den  fehlenden Fairness Flags. Dazu kommen \textbf{ReadWriteLockSlim} (upgradable), \textbf{Mutex} (binärer Semaphor) und speziellere. \textbf{Ausser} den Collections in \textbf{System.Collections.Concurrent} sind alle Collection NICHT Threadsafe.\\\\
\textbf{[TPL]} (Task Parallel Library) ist ein \textbf{Work Stealing Thread Pool} mit verschiedenen Abstraktionsebenen (Task Parallelism, Data Parallelism, Asynchronous Programming with Continuations). Die \textbf{TPL} erkennt geschachtelte Tasks selber und es sind keine speziellen Vorkehrungen zu treffen. Des Weiteren erzeugt die \textbf{TPL} selber neue Threads wenn sie merkt, dass alle Threads blockiert sind. ACHTUNG: \textbf{TPL} Threads sind Background Threads (analog Java Daemon Threads). Via \textbf{ThreadPool.SetMaxThreads(n)} kann die maximale Anzahl Threads festgelegt werden -> \textbf{Deadlock}-Gefahr
\begin{lstlisting}[language=c++]
Task task1 = Task.Factory.StartNew(() => {
  // do stuff
});

// wait for task to finish
task1.Wait();

// tasks can have return values
Task<int> task2 = Task.Factory.StartNew(() => {
  int res = 42;
  return res;
});

// this blocks until task2 is finished
Console.WriteLine(task2.Result);
\end{lstlisting}
\textbf{[Exceptions]} in Tasks werden seit .NET 4.5 stillschweigend ingoriert und müssen explizit via den Event \textbf{TaskScheduler.UnobservedTaskException} aboniert werden.\\\\
\textbf{[Datenparallelität]} kann mittels Bordmitteln erreicht werden. Voraussetzung ist, dass die Unabhängigkeit der Daten gegeben ist! Nach dem Aufruf wird auf die Beendigung ALLER Tasks gewartet.
\begin{lstlisting}[language=c++]
Parallel.Invoke(
  () => Console.WriteLine("foo"),
  () => Console.WriteLine("bar")
);

Parallel.ForEach(list,
  entry => DoStuff(entry)
);

Parallel.For(0, arr.Length,
  idx => MoreStuff(arr[idx])
);
\end{lstlisting}
\textbf{[async/await]} erlauben das teil-asynchrone Ausführen von Funktionen. Der Compiler zerlegt die Funktion in zwei Hälften: bis zum ersten \textbf{await} wird die Funktion vom Caller synchron ausgeführt, Der Rest wird auf einem \textbf{TPL}-Thread erledigt. \textbf{await} darf nur in Funktionen vorkommen die mit \textbf{async} gekennzeichtet sind und Funktionen die mit \textbf{async} gekennzeichnet sind MÜSSEN ein \textbf{await} enthalten! Das was nach dem await kommt ist die \textbf{Continuation}. Ist der Aufrufer ein \textbf{UI-Thread} dann wird die Continuation auf den \textbf{UI-Thread} dispatched, andernfalls auf einen \textbf{TPL-Thread}. ACHTUNG: \textbf{async/await} kann zu einem Threadwechsel INNERHALB eines Funktionsaufrufs führen.
\begin{lstlisting}[language=c++]
class MainClass {
  public static async void DoStuff() {
    await Task.Delay(1000);
    Console.WriteLine("Knights!");
  }

  public static void Main(string[] args) {
    Console.WriteLine("foo");
    DoStuff();
    // In the meantime 'Knights!' gets
    // written to the console
    Thread.Sleep(5000);
    Console.WriteLine("bar");
  }
}
\end{lstlisting}
Beispiel für UI-Thread-Dispatching:
\begin{lstlisting}[language=java]
threadPool.submit( () -> {
  longOperation(); // in different thread
  SwingUtilities.invokeLater(() -> {
    // in UI thread again b/c label
    someLabel.setText("Done!");
   });
});
\end{lstlisting}
Das \textbf{[Java Memory Model]} garantiert Atomicity für \textbf{Lese-/Schreiboperationen} bis 32-Bit (mit \textbf{volatile} auch für long und double) und auf Referenzen. Visibility ist bei Locks \textbf{Release/Acquire} garantiert (Änderungen \textbf{vor} Release werden bei Acquire sichtbar). Bei \textbf{volatile} Variablen werden alle vorhergehenden Änderungen beim Zugriff sichtbar. \textbf{final}-Variablen werden nach dem Ende des Konstruktors sichtbar. Sichtbarkeit ist auch bei Thread-Start und -Join sowie Task-Start und -Ende garantiert.\\\\
\textbf{[volatile in JAVA]} garantiert, dass kein Reordering über einen Zugriff (lesend oder schreibend) auf eine derart markierte Variable hinaus statt findet. Das Ordering vor und nach \textbf{volatile} folgt innerhalb eines Threads der "As-If-Serial"-Semantik. Das heisst, der Compiler darf optimieren, falls die Semantik INNERHALB des Threads gleich bleibt. Zwischen Threads ist Ordering nur bei Zugriffen auf \textbf{volatile}-Variablen und bei Synchronisationsbefehlen garantiert. \textbf{volatile} Zugriffe führen nicht zu locking.\\\\
\textbf{[Atomare Operationen]} erlauben das atomare Ändern einer Variable mit einer zusätzlichen Operation (meistens return des alten Werts). Es gibt für Atomare Klassen für Boolean, Integer, Long und Referenzen (auch für Array-Elemente). Seit Java 8 gibt es auf diesen sogar Operationen welche ein "Expression-Lambda" nehmen. \textbf{Atomare Operationen} garantieren Ordering und Visibility. Beispiele für atomare Operationen sind \textbf{getAndSet(newVal)}, \textbf{getAndAdd(delta)} und \textbf{updateAndGet(lambda)}.
\begin{lstlisting}[language=java]
public class SLock {
  private AtomicBoolean locked =
    new AtomicBoolean(false);

  public void acquire() {
    // spin if already locked
    // else set locked to true
    while(locked.getAndSet(true)) {
      Thread.yield();
    }
  }

  public void release() {
    // set false and make visible
    locked.set(false);
  }
}
\end{lstlisting}
\textbf{[compareAndSet(old, new)]} erlaubt das atomare Prüfen einer Variable auf einen bestimmten Wert und ersetzt sie bei Übereinstimmung mit \textbf{new}. Rückgabewert zeigt ob die Ersetzung stattgefunden hat. ACHTUNG: Hier kann man in das \textbf{ABA-Problem} laufen.
\begin{lstlisting}[language=java]
do {
  oldV = var.get();
  newV = calcChanges(oldV);
} while (!var.compareAndSet(oldV, newV));
\end{lstlisting}
Das \textbf{[ABA-Problem]} beschreibt, was passiert wenn ein anderer Thread dazwischen schreibt und sich der zu vergleichende Wert scheinbar nicht ändert. Dies ist besonders bei lockfreien Datenstrukturen wie Stacks und Listen ungünstig.\\\\
\textbf{[Das .NET Memory Model]} unterscheided sich vom Java Memory Model darin, dass long und double auch mit \textbf{volatile} nicht atomar sind. Auch die Visibility ist nicht explizit definiert, da sie durch das Ordering gegeben ist. Beim Ordering ist es wichtig, dass \textbf{volatile} in .NET nur ein "Partial Fence" ist.\\\\
\textbf{[volatile in .NET]} verfolgt beim Lesen die sogenannte \textbf{Acquire-Semantik}, was bedeutet, dass alles was \textbf{VOR dem LESEN} einer volatile Variable nach "unten" optimiert werden darf. Beim Schreiben wird die \textbf{Release-Semantik} angewandt: alles was \textbf{NACH dem SCHREIBEN} kommt, darf nach oben optimiert werden. Da diese Semantik of ungenügend ist, gibt es mit \textbf{Thread.MemoryBarrier()} einen "Full-Fence".\\\\
\textbf{[GPU Vokabular]}: Eine GPU besteht aus mehreren \textbf{Streaming Multiprocessors (SM)}. Jeder SM besteht aus mehreren \textbf{Streaming Processors (SP)}. In CUDA sind Threads in \textbf{Blöcke} zusammengefasst. Jeder SM kann mehrere Blöcke beherbergen, jeder Block ist intern in \textbf{Warp}s zu je 32 Threads zerlegt.\\\\
\textbf{[SIMD]} ist die Abkürzung für "Single Instruction Multiple Data". Dies entspricht dem Paradigma der Verktorparallelität. GPUs sind inherent für SIMD-Applikationen geeignet, denn innerhalb eines SM führen alle Cores die gleiche Instruktion auf unterschiedlichen Daten aus. Es gibt auch in CPU begrenzt mächtige SIMD-Instruktionen.\\\\
\textbf{[CUDA]} ist die "Computer Unified Device Architecture" von NVIDIA. CUDA arbeitet mit sogenannten \textbf{Kernels} welche auf der GPU laufen. Jeder Kernel bekommt Informationen darüber, auf welchem Block er läuft (\textbf{blockIdx.x}), welcher Thread innerhalb des Blocks er ist (\textbf{threadIdx.x}) und wie gross ein Block ist (\textbf{blockDim.x}). Auch die \textbf{y}- und \textbf{z}-Dimensionen sind nutzbar. Als Programmierer muss man die Datenaufteilung selber modellieren.
\textbf{Divergenz} heisst, dass im selben Warp unterschiedliche Instruktionen vorhanden sind (z.B. via if/else). Dies bewirkt, dass je für die "if"- und "else"-Elemente ein Cycle gebraucht wird --> Performance-Probleme.
\begin{lstlisting}[language=c]
// vector addition kernel
__global__
void vecAKern(float *A, float *B,
              float *C, int N) {
  int i = blockIdx.x * blockDim.x + threadIdx.x;
  // bounds check
  if(i < N) {
    C[i] = A[i] + B[i];
  }
}
\end{lstlisting}
Das \textbf{[CUDA Memory Management]} kennt die drei wichtigen Funktionen \textbf{cudaMalloc}, \textbf{cudaFree} und \textbf{cudaMemcpy} welche ähnlich wie ihre C-Geschwister funktionieren. Mit \textbf{cudaMalloc} kann Speicher im \textbf{Device Global Memory} alloziert werden. \textbf{cudaFree} gibt allozierten Speicher auf dem Device wieder frei und \textbf{cudaMemcpy} wird verwendet um Daten vom Host zum Device zu kopieren.\\\\
\textbf{Maximale Thread-Zahl}:\\
Gegeben: Threads per Block: 1024, Matrix size: 256*512, Anzahl SMs: 3, Max. Resident Threads/SM: 2048, Max. Resident Blocks/SM: 16\\
Limit A: 3 * 2048 (Max. Res. Threads/SM) \textbf{tiefste Zahl = Limit}\\
Limit B: 3 * 16 * 1024 (Max. Res. Blocks)\\
Limit C: 256 * 512 (\# Threads überhaupt, wegen Matrix Size)\\\\
Das "CUDA-Grundgerüst" ohne Error Handling sieht in etwa so aus:
\begin{lstlisting}[language=c]
void CudaVAdd(float* A, float* B,
              float* C, int N) {
  size_t size = N * sizeof(float);
  float *d_A, *d_B, *d_C;

  cudaMalloc(&d_A, size);
  cudaMalloc(&d_B, size);
  cudaMalloc(&d_C, size);

  cudaMemcpy(d_A, A, size,
             cudaMemcpyHostToDevice);
  cudaMemcpy(d_B, B, size,
             cudaMemcpyHostToDevice);
  
  // for 2/3 dimensions: dim3 gDim(32, 32);
  int bDim = 512; //block size
  int gDim = (N + bDim - 1) / bDim;
  vecAKern<<<gDim, bDim>>>(d_A, d_B, d_C, N);

  cudaMemcpy(C, d_C, size,
             cudaMemcpyDeviceToHost);

  cudaFree(d_A); cudaFree(d_B); cudaFree(d_C);
}
\end{lstlisting}
\textbf{[CUDA Function Keywords]} sind \textbf{\_\_global\_\_}(läuft auf Device wird von Host aufgerufen), \textbf{\_\_device\_\_}(läuft auf Device und wird von Device aufgerufen) und \textbf{\_\_host\_\_}(läuft auf Host und wird auch vom Host aufgerufen).\\\\
\textbf{[Die Launch-Configuration]} muss dynamisch bestimmt werden und sich am Problem und den Fähigkeiten des Device (ermittelt mit \textbf{cudaGetDeviceProperties()}) orientieren. Aus Effizienzgründen sollte die Blockgrösse ein Vielfaches von 32 sein (remember: 32 Threads per Warp, multiple Warps per Block). Die Blockgrösse sollte auch nicht zu gross gewählt werden, um die Anzahl der unnützen Threads zu minimieren. Die SM sollten voll ausgeschöpft werden (also ans Limit von Resident Blocks und Resident Threads gehen). Grosse Blöcke haben den Vorteil, dass die Threads interagieren können.\\\\
\textbf{[Memory Access]} in den \textbf{Device Global Memory} ist viel teuerer (ca. Faktor 125) als Zugriff in den \textbf{Shared Memory(\_\_shared\_\_)} eines SM. Um \textbf{Memory Coalescing}(das Zusammenfassen mehrerer Ladevorgänge zu einem) zu verwenden sollten Speicherzugriffe möglichst folgende Gestalt haben:
\begin{lstlisting}[language=c]
data[(Ausdruck ohne threadIdx.x) + threadIdx.x]
\end{lstlisting}
\textbf{[Synchronisierung]} in CUDA kann mit \textbf{\_\_syncthreads()} erreicht werden, was alle Threads in einem Block zum Synchronisieren zwingt.\\\\
\textbf{[Effiziente Matrix Multiplikation]}:
\begin{lstlisting}[language=c]
__shared__ float Asub[TILE_SIZE][TILE_SIZE];
__shared__ float Bsub[TILE_SIZE][TILE_SIZE];

int tx = threadIdx.x, ty = threadIdx.y;
int col = blockIdx.x * TILE_SIZE + tx;
int row = blockIdx.y * TILE_SIZE + ty;

for (int tile = 0; tile < nofTiles; tile++) {

  Asub[ty][tx] = A[row*K + tile*TILE_SIZE + tx];
  Bsub[ty][tx] = B[(tile*TILE_SIZE + ty)*M + col];

  __syncthreads();

  for (int ksub = 0; ksub < TILE_SIZE; ksub++) {
    sum += Asub[ty][ksub] * Bsub[ksub][tx];
  }
  __syncthreads();
}
\end{lstlisting}
\textbf{[Cluster]} weisen spezielle Eigenschafen auf. Erstens gibt es nur \textbf{innerhalb eines Nodes} Shared Memory und nicht über die Grenzen eines Nodes hinweg. Zweitens sind Cluster durch die grosse Anzahl von General Purpose CPUs sehr gut für "allgemeine" Rechenaufgaben geeignet. Im Allgemeinen wird der Austausch von Informationen in Clustern mit \textbf{Dateien} oder über \textbf{Sockets} bewerkstelligt.\\\\
\textbf{[MPI] (Message Passing Interface} basiert auf dem Actor- bzw. dem CSP-Modell und ist sehr gut für heterogene Umgebungen geeignet. MPI ist ein Industriestandard einer Bibliothek für Cluster-Anwendungen. MPI ist sogenanntes \textbf{SPMD} (Single Program Multiple Data), da jeder Node das gleiche Programm mit anderen Daten ausführt. Ein Beispiel in C:
\begin{lstlisting}[language=c]
#include <stdio.h>
#include "mpi.h"

int main(int argc, char* argv[]){
  MPI_Init(&argc, &argv);
  int rank;
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  printf("Process:%i", rank);
  MPI_Finalize();
  return 0;
}
\end{lstlisting}
Und eines in .NET:
\begin{lstlisting}[language=c++]
using MPI;
using System;
class Program {
  public static void Main(string[] args) {
    using (new MPI.Environment(ref args)) {
      int rank = Communicator.world.Rank;
      Console.WriteLine("Process:{0}", rank);
    }
  }
}
\end{lstlisting}
\textbf{[Kommunikation]} in MPI kann leicht über \textbf{Communicator.world} erfolgen. Um direkt einem Node eine Nachricht zu senden, verwendet man \textbf{world.Send(value, receiverRank, messageTag)}. Analog funktioniert das Empfangen mit \textbf{world.Receive(senderRank, messageTag, out value)}. Nachrichten an alle können mit \textbf{world.Broadcast(ref value, senderRank)} abgesetzt UND empfangen werden.\textbf{Synchronisierung} kann mit \textbf{Communicator.world.Barrier()} erreicht werden. Alle Nodes warten darauf, dass alle die Barriere erreichen. Ergebnisse können mittels \textbf{Allreduce(T value, Op<T>)}(Broadcast) oder \textbf{Reduce(T value, Op<T>, int rank)}(ohne Brodcast) reduziert werden. Es existieren noch weitere Kommunikationsmöglichkeiten wie \textbf{outputArray = Alltoall(inputArray)}, \textbf{value = Scatter(array, rank)} oder \textbf{outputArray = Gather(value, rank)}.\\\\
\textbf{[.NET PLINQ]} via "Extension Methods":
\begin{lstlisting}[language=c++]
salesEurope.
  Union(salesAsia).
  Union(salesAmerica).
GroupBy(item => item.Article,
        item => item.Volume).
Select(category => new {Key = category.Key,
                        Value = category.Sum()}).
Where(category => category.Value >= 1000);
\end{lstlisting}
oder mit der eingebetteten Syntax:
\begin{lstlisting}[language=c++]
from entry in
  salesEurope.AsParallel().
  Union(salesAsia.AsParallel()).
  Union(salesAmerica.AsParallel())
group
  entry by entry.Article into category
  let sum = category.Sum(e => e.Volume)
where
  sum >= 1000
select
  new { category.Key, sum };
\end{lstlisting}
In PLINQ ist die Reihenfolge der Resultate beliebig (Ordering ist opt-in \textbf{AsOrdered()}).\\\\
\textbf{[Reactive Programming mit Rx.NET]} erlaubt das Reagieren auf eine aktive Quelle (\textbf{push}). Das System basiert auf dem Observer Pattern [GoF]. Um eine Pipeline zu bauen, benötigt man ein \textbf{Subject} das sowohl \textbf{Observer} als auch \textbf{Observable} ist:
\begin{lstlisting}[language=c++]
var subject = new Subject<string>();

subject.Subscribe(Console.WriteLine);

subject.OnNext("A");
subject.OnNext("B");
subject.OnNext("C");

subject.OnCompleted();
\end{lstlisting}
Normalerweise haben Subjects kein Gedächtnis, es gibt jedoch \textbf{ReplaySubject}, \textbf{BehaviorSubject} und \textbf{AsyncSubject}.\\\\
\textbf{[Software Transactional Memory (STM)]} nimmt Ideen aus der Datenbankwelt und versucht damit das Problem des \textbf{Shared Mutable State} ohne Locks und Starvation anzugehen. Es gibt auch Implementationen in Hardware. Meistens wird \textbf{Optimistic Concurrency Control}(Rollback bei Konflikt) als Umsetzung verwendet. In der Java Welt gibt es ScalaSTM, ein deskriptiver Ansatz ("was", nicht "wie") und somit ein relativ einfaches Programmiermodell. Die Implementierung ist jedoch sehr komplex und "teuer".\\\\
Das \textbf{[Actor Model]} versucht das Problem zu lösen, dass herkömmliche Sprachen nicht für Nebenläufigkeit entworfen wurden. Dass Threads oft nur \textbf{Second-Class}-Features sind und Speicher per Default nicht \textbf{threadsafe} ist, macht es extrem schwierig \textbf{KORREKTE} nebenläufige Programme zu schreiben.\\\\
\textbf{[Active Objects]} (siehe auch [POSA2]) sind Objekte welche ein "Eigenleben" führen. Im \textbf{Actor Model} sind alle Actors \textbf{Active Objects}. \textbf{Active Objects} weist grosse Ähnlichkeiten zu CSP (Communicating Sequencial Processes) auf.\\\\
\textbf{[Akkas Actor Konzept]} besteht aus Actors welche nebenläufig zueinander laufen. Sie verfügen jeweils über eine \textbf{Mail-Box} um Nachrichten zu empfangen. Beim Empfangen einer Nachricht wird eine spezielle Empfangsmethode (\textbf{onReceive}) im Actor ausgeführt.
\begin{lstlisting}[language=java]
public class NumberPrinter extends UntypedActor {
  public void onReceive(final Object message) {
    if (message instanceof Integer) {
      System.out.print(message);
    }
  }
}
ActorSystem system =
  ActorSystem.create("System");
ActorRef printer =
  system.actorOf(Props.create(
                  NumberPrinter.class));
for (int i = 0; i < 100; i++) {
  printer.tell(i, ActorRef.noSender());
}

system.shutdown();
\end{lstlisting}
\textbf{[ActorRef]} speichert eine \textbf{Referenz} auf eine Instanz eines Actors. Dadurch wird verhindert, dass direkt auf Variablen und Methoden des Actors zugegriffen wird. Falls der Actor neu gestartet werden muss, \textbf{behält er seine Adresse}. \textbf{ActorRef}s können in Nachrichten verschickt werden.\\\\
\textbf{[Remoting]} wird dadurch vereinfacht, dass Nachrichten \textbf{immutable} sind. Ein Lookup für einen Actor kann mittels \textbf{system.actorSelection(urlString)} durchgeführt werden. Das Ergebnis (eine \textbf{ActorSelection}) kann 0-n Aktoren umfassen und zu einer \textbf{ActorRef} aufgelöst werden.\\\\
\textbf{[Messaging]} in Akka ist grundsätzlich asynchron. Es kann jedoch \textbf{mittels Futures} synchron auf eine Antwort gewartet werden. Messages müssen \textbf{Serializable} sein, dürfen nur \textbf{final} Felder haben und nicht über Methoden mit Seiteneffekten verfügen. Collections müssen in \textbf{Collections.unmodifiableList} verpackt werden.
\begin{lstlisting}[language=java]
// synchronous responses
Future<Object> result =
  Patterns.ask(actorRef, msg, timeout);
// ...
result.get();

// custom messages (Java)
public class Booking {
  final String name;

  public Booking(String name) {
    this.name = name;
  }

  public String getName() {
    return name;
  }
}

// the same (!!!) in Scala
class Booking(val name: String)
\end{lstlisting}
\textbf{[Das Akka Laufzeitsystem]} setzt typischerweise auf \textbf{ForkJoinPools} auf, jedoch wird aus Effizienzgründen nicht ein Thread pro Actor verwendet. \textbf{Synchrones Senden und Empfangen} von Nachrichten führt zu Warteabhängigkeiten, was wiederum zu \textbf{Deadlocks} führen kann. Deshalb wird von \textbf{synchroner Kommunikation abgeraten}.\\\\
\textbf{[Akka Supervision]} bezeichnet das Überwachen von Actors durch andere Actors. Eltern überwachen per Default immer ihre Kinder. Bei einer Exception wird der Supervisor informiert und muss dand entscheiden, wie es weiter geht. Der Supervisor hat die Wahl zwischen vier Möglichkeiten: mit \textbf{Resume} kann er dem Kind sagen es soll weitermachen, \textbf{Restart} startet das Kind neu, \textbf{Stop} beendet das Kind und \textbf{Escalate} (siehe Fault Tolerance Patterns) meldet seinem \textbf{eigenen Supervisor}, dass er nicht weiss, wie er reagieren soll.\\\\
Der \textbf{[System Shutdown]} erfolgt durch das Stoppen der Actors. Mittels \textbf{getContext().stop(actorRef)} wird einem Actor mitgeteilt, dass er \textbf{nach Bearbeitung der aktuellen Message} anhalten soll. Mit \textbf{actor.tell(PoisonPill.getInstance(), sender)} wird eine Terminierungsnachricht eingereiht, deren Bearbeitung den Actor stoppt. Als "last measure" dient \textbf{actor.tell(Kill.getInstance(), sender)}, was eine \textbf{Supervision Behandlung} auslöst.\\\\
Verteilung: Actor (Comm. via Messages, no shared state), Reactive\\
No Race Conditions: Actor (no shared mem., Comm synch'd), Reactive, STM (autom. isoliert)\\
No deadlocks: Reactive (Flow ist async, non-blocking, STM (kein Warten, nur Transakt.)
\end{multicols*}
\end{document}