hgraph/doc/ausarbeitung/hgraph_doc.tex

\documentclass[a4paper]{scrartcl}
\usepackage{titling}

% LANGUAGE and LOCALE
\usepackage[USenglish,ngerman]{babel} % Deutsches Wörterbuch usw.
\newcommand{\en}[1]{\selectlanguage{USenglish}#1\selectlanguage{ngerman}}

% FONT
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[babel=true]{microtype} % after babel
\usepackage{lmodern}
%\usepackage{times}
\makeatletter
\g@addto@macro\@verbatim{\microtypesetup{activate=false}}
\makeatother

% ENUMERATE and ITEMIZE
\usepackage{enumerate}
\usepackage{paralist}

% SCIENCE and MATH
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{icomma}
%\usepackage{units}
\usepackage{xfrac} % Brüche im Stil von ½ (\sfrac)

% PROGRAMMING
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

% TABLES
%\usepackage{array}
%\usepackage{multicol}	
%\usepackage{dcolumn}
%\usepackage{slashbox} % diagonale Linie in Tabellenzelle
%\usepackage{tabularx}

% LINKS and REFS
\usepackage[obeyspaces]{url}
\usepackage{hyperref}
\usepackage{todonotes} % todos..

% BIBLIOGRAPHY
\usepackage[style=german,german=quotes]{csquotes}
\usepackage[style=alphabetic,backend=biber,babel=hyphen,maxbibnames=10]{biblatex}
%\usepackage[authordate,backend=biber,babel=hyphen]{biblatex-chicago} 
\bibliography{hgraph.bib}

% FORMATING
\usepackage{enumitem} % nicer itemize
\usepackage{listings}
\usepackage{color}
\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
  basicstyle=\scriptsize,        % the size of the fonts that are used for the code
  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  breaklines=true,                 % sets automatic line breaking
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{mygreen},    % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
  extendedchars=true,              % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible)
  keywordstyle=\color{blue},       % keyword style
  language=Haskell,                % the language of the code
  morekeywords={*,Graph,Adj,Attr,Density,MaxDivergence,L,expand,filterLayer,...},            % if you want to add more keywords to the set
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showspaces=false,                % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
  showstringspaces=false,          % underline spaces within strings only
  showtabs=false,                  % show tabs within strings adding particular underscores
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
  stringstyle=\color{mymauve},     % string literal style
  tabsize=2,                       % sets default tabsize to 2 spaces
  title=\lstname                   % show the filename of files included with \lstinputlisting; also try caption instead of title
}
\usepackage{anysize} % Makros zum Einstellen der Seitenränder
\parindent0em % Keine amerikanische Einrückung am Anfang von Paragraphen
\clubpenalty = 10000  % Schusterungen bestrafen
\widowpenalty = 10000 % Hurenkinder bestrafen
\displaywidowpenalty = 10000

% math commands
\newcommand{\trans}[1]{{#1}^\intercal}
\newcommand{\abs}[1]{\left\vert #1 \right\vert}
\newcommand{\card}[1]{\left\vert #1 \right\vert} % cardinality
\newcommand{\norm}[1]{\left\Vert #1 \right\Vert}

\newcommand{\condset}[2]{\ensuremath{\left\lbrace #1\vphantom{#2}\right.\left\vert\; #2 \vphantom{#1}\right\rbrace}}

\newcommand{\setR}{\mathbb{R}}
\newcommand{\setN}{\mathbb{N}}

\DeclareMathOperator*{\argmin}{\arg\min}
\DeclareMathOperator*{\argmax}{\arg\max}

\hyphenation{IEEE} % hyphenation of default language
\begin{hyphenrules}{USenglish} % hyphenation of secondary language
  \hyphenation{IEEE}
\end{hyphenrules}

\begin{document}

\title{\en{Densely Connected Biclusters}}
\author{Stefan Dresselhaus \and Thomas Pajenkamp}
\date{\today} % TODO: Abgabedatum
\newcommand{\thesemester}{Wintersemester 2013/14}
\newcommand{\thecategory}{Programmierprojekt}
\newcommand{\thecourse}{Parallele Algorithmen und Datenverarbeitung}


%
% Deckblatt
%
\begin{titlepage}
  \begin{center} 
    \mbox{}
     \vspace{1cm}\\
     {\Huge \textbf{\thetitle}} \\[3em]
     {\huge \theauthor} \\[4em]
     {\Large \thecourse}\\[1em]
     {\Large \thecategory{} im \thesemester}\\[1em]
     
     \vspace{3cm}
     
     {\LARGE Universität Bielefeld -- Technische Fakultät}\\[2em]
     {\large \thedate}
  \end{center}
\end{titlepage}
%
% Inhaltsverzeichnis
%
%\setcounter{page}{1}
\microtypesetup{protrusion=false}
\tableofcontents
\microtypesetup{protrusion=true}

\listoftodos
\newpage

\section{Zielsetzung des Projekts}

Im Rahmen dieses Programmierprojekts wurde ein Programm entworfen und entwickelt, um \en{Densely Connected Biclusters}, im weiteren DCB, in einem biologischen Netzwerk zu ermitteln. Bei DCB handelt es sich um Teilgraphen eines Netzwerks, dessen Knoten untereinander hoch vernetzt sind und Objekte mit ähnlichen Eigenschaften repräsentieren. \par
Die Suche nach DCB ist ein NP-schweres Problem. Da mit einem geeigneten Algorithmus jedoch voneinander unabhängige Lösungspfade einzeln verfolgt werden können, ist das Problem gut für eine parallele Berechnung geeignet, wodurch die Gesamtlaufzeit stark reduziert werden kann. Zudem sind  real verwendete biologische Netze üblicherweise nur schwach vernetzt. Daher können durch die Forderung nach einer hohen Konnektivität der DCB viele Lösungskandidaten schnell ausgeschlossen werden und die schlimmstenfalls nichtdeterministisch polynomielle Laufzeit findet kaum Anwendung. \par

%TODO ein bisschen biologische Motivation?
% ... Sind wir Biologen? :p

\en{
\subsection{Densely Connected Biclusters}
\label{dcb}
}

Ausgangsbasis ist ein ungerichteter ungewichteter Graph $G = (V, E)$, dessen Knoten $n \in V$ mit jeweils $p$ Attributen versehen sind. Jedem Knoten $n$ ist zu jedem Attribut $i$ ein numerischer Wert $a_{ni}$ zugewiesen. \par
Ein DCB $D_k = (V_k, E_k)$ ist ein Teilgraph von $G$, der durch die Parameter $\alpha \in [0, 1]$, $\delta \in \setN$ und $\omega \in \setR^p$ beschränkt wird und die folgende drei Eigenschaften erfüllt.
\begin{itemize}
\item Der Teilgraph ist zusammenhängend.
\item Die Dichte des Teilgraphen unterschreitet einen Schwellenwert $\alpha$ nicht, also $\frac{2 \cdot \card{E_k}}{\card{V_k}(\card{V_k}-1)} \geq \alpha$.
\item Für mindestens $\delta$ Attribute liegen die Werte aller Knoten des Teilgraphen höchstens $\omega_i$ auseinander. Anders ausgedrückt
\begin{equation*}
\delta \leq \card{\condset{1\leq i \leq p}{\omega_k \geq \left(\max_{n\in V_k} a_{ni} - \min_{n\in V_k} a_{ni}\right)}} \text{\@.}
\end{equation*}
\end{itemize}


\section{Wahl der Programmiersprache und Konzept der Parallelisierung}

Die Wahl der Programmiersprache zur Verwirklichung des Projekts beeinflusst stark die Methoden der Programmierung und die Art der Parallelisierung. Klassischerweise werden für sequentielle und parallele Programme gleichermaßen imperative Sprachen wie C(++), Fortran oder auch Java verwendet, wofür Erweiterungen zur parallelen Programmierung existieren oder einige Werkzeuge direkt in die Sprache eingebaut sind. Bekannte Ansätze hierfür sind MPI und openMP. \par
Unser Projekt geht in eine etwas andere Richtung. Bei imperativer Programmierung muss ein großes Augenmerk auf die Vermeidung unerwünschter wechselseitiger Beeinflussungen verschiedener Threads und Prozesse gelegt werden, die fehlerhafte Rechenergebnisse zur Folge haben. Außerdem muss bei der Thread-/Prozesskommunikation immer die Gefahr von Verklemmungen beachtet werden, die schlimmstenfalls zu einem kompletten Stillstand der Programmausführung führen. Beide Probleme sind schwierig zu detektieren und zu lokalisieren.\par
Die genannten klassischen Probleme des Parallelrechnens können mit pur funktionaler Programmierung gut vermieden werden. Nebenbedingungen treten in pur funktionalem Programmcode (einen korrekten Compiler/Interpreter vorausgesetzt) garantiert nicht auf. Da das DCB-Problem bis auf das Einlesen der Eingabedaten und die Ausgabe pur funktional realisierbar ist, ist es optimal für eine derartige Implementierung geeignet Die konkrete Wahl der funktionalen Programmiersprache fiel auf \emph{Haskell}. \par
\medskip
Für Haskell wurden Bibliotheken entwickelt, die eine einfache und effiziente Programmierung paralleler Programme erlauben. Wir verwenden das Paket \emph{parallel} in Verbindung mit \emph{repa}-Arrays. Durch \emph{parallel} können geeignete Algorithmen mit wenig Aufwand, aufgeteilt werden. Dabei werden Funktionsaufrufe unevaluiert in einem Array gespeichert und dort von freien Threads abgearbeitet. Diese Technik nennt man Work-Stealing und die noch nicht ausgewerteten Funktionen werden in Haskell \emph{Sparks} genannt.
Man kann sich dies als einen auf den Funktionsaufruf beschränkten light-weight-Thread vorstellen -- mit weniger Overhead. Die \emph{repa}-Arrays bieten Funktionen, um die einzelnen Elemente eines Arrays parallel zu berechnen. Mit diesen Techniken lässt sich sequentieller Programmcode einfach parallelisieren, da hierfür nur wenige Änderungen im Programmcode erforderlich sind. Es müssen lediglich die Berechnungsfunktionen an die parallelisierende Funktion übergeben und die Funktion zur Auswertung der Arrayelemente ausgetauscht werden. \par
\medskip
Zwei wichtige Punkte müssen dennoch beachtet werden. Zum einen verwendet Haskell das Konzept \emph{\en{Lazy Evaluation}}. Befehle werden immer nur soweit berechnet, wie sie an anderer Stelle benötigt werden. Dadurch entstehen manchmal zur Laufzeit große Bäume nur teilweise ausgewerteter Befehle, welche die Ausführungszeit durch eine hohe Garbage-Collector-Auslastung stark negativ beeinflussen. Es muss demnach darauf geachtet werden, die Berechnung später ohnehin erforderlicher Werte frühzeitig zu erzwingen. Zum anderen ist die Anzahl der Sparks standardmäßig nicht begrenzt, sodass auch hier zu große Arrays entstehen können, deren Abarbeitung allerdings im Verlaufe des Programms durch o.\,g. Lazy Evaluation evtl.\ gar nicht erforderlich ist.
Daher beschränken wir die Anzahl der möglichen Sparks, und somit der maximal möglichen Worker-Threads, auf 1000. Erwähnenswert ist noch, dass diese Technik \emph{nicht} von Hyper-Threading profitiert,da kein Kontextwechsel der Threads nötig ist, und wir somit 1000 \glqq echte\grqq \ Kerne für eine maximale Auslastung benötigen. Die obere Grenze wird eher durch Amdahls Gesetz, denn durch die verfügbaren Kerne beschränkt.\par


\section{Der Algorithmus}

Für die Darstellung des Eingabegraphen, in dem die DCB gesucht werden, verwenden wir eine Adjazenzmatrix. Die anschließende Laufzeitbetrachtung bezieht sich auf diese Datenstruktur. \par
Der DCB-Algorithmus besteht aus einer Vorverarbeitungsphase, in der Cluster-Seeds aus 2 jeweils verbundenen Knoten generiert werden, und einer anschließenden Expansion dieser Seeds unter Berücksichtigung der in Abschnitt~\ref{dcb} vorgestellten Nebenbedingungen (Constraints). Diese Cluster (im Folgenden Graphen genannt) bestehen zu Anfang aus genau 2 Knoten, die sämtliche Bedingungen erfüllen. Eine erste Optimierung findet nun statt, da es nach diesem Schritt auch verbundene Knoten geben kann, die nicht zur initialen Bildung der Graphen beigetragen haben. Diese Paare können im Folgenden komplett ausgeschlossen werden, da sie die Attributsbedingung nicht erfüllen können\footnote{Ein Graph aus 2 verbundenen Knoten ist immer maximal dicht und zusammenhängend.}. Folglich würde jeder Graph mit diesem Knotenpaar insgesamt auch gegen selbige Attributsbedingung verstoßen. Alle hiervon betroffenen Kanten können somit aus der Adjazenzmatrix gelöscht werden.\par

\begin{figure}[h!]
 \centering
 \includegraphics[scale=0.5,keepaspectratio=true]{./img/DCB-Module.png}
 % DCB-Module.png: 1024x512 pixel, 96dpi, 27.09x13.54 cm, bb=0 0 768 384
 \caption{Übersicht über die Hierarchie des DCB-Moduls. Gelb hinterlegte Funktionen sind nach außen hin sichtbar.}
 \label{fig:DCB-Overview}
\end{figure}

Wir exportieren 2 Funktionen nach außen, die in der Lage sind, die Graphen zu expandieren: \texttt{step} und \texttt{maxDCB}. \texttt{step} liefert alle möglichen expandierten Graphen aus einer Liste von bestehenden DCB -- allerdings verliert man somit alle Graphen, die nicht expandiert werden konnten. Als Ergebnis hat man eine gewisse Mindestzahl an Knoten im Graphen. Da die Seeds mit 2 Knoten beginnen, man aber z.\,B. alle DCB mit 4 Knoten oder mehr haben möchte, kann man \texttt{step} so häufig aufrufen, dass alle Graphen mit weniger Knoten gar nicht zurückgegeben werden. Wir verwenden dies in unserem Algorithmus einmalig, da wir nur Cluster mit 3 oder mehr Knoten zurückliefern.\par
\medskip
Die Funktion \texttt{maxDCB} übernimmt die eigentliche Berechnung, sodass wir diese im Detail besprechen. Zunächst jedoch geben wir einen kleinen Überblick über die Hilfsfunktionen im Hintergrund:
\begin{description}[style=multiline,leftmargin=2.75cm,font=\bfseries]
 \item[filterLayer] filtert eine Menge von $s$ Graphen der Größe $m$, indem es Duplikate herausfiltert. \\ Laufzeit: $\mathcal{O}(m \cdot s \log s)$.
 \item[constraint] überprüft, ob der Graph noch die Constraints erfüllt und wenn ja, wie diese aussehen. \\ Laufzeit: $\mathcal{O}(k)$ bei $k$ Attributen, da die Maximal- und Minimalwerte des Graphen tabelliert werden.
 \item[updateDensity] errechnet die Änderung der Dichte des Graphen anhand des hinzuzufügenden Punktes. \\ Laufzeit: $\mathcal{O}(m)$ bei $m$ Knoten im Ursprungsgraph, da die Graphendichten gespeichert werden.
 \item[reduceDim] ist eine interne Hilfsfunktion, die eine Dimension einer Array-Shape verwirft. \\ Laufzeit: $\mathcal{O}(1)$.
 \item[addablePoints] traversiert die Adjazenzmatrix und liefert alle mit einem Graphen verbundenen Knoten, die nicht selbst im Graphen enthalten sind. \\ Laufzeit: $\mathcal{O}(n \cdot m)$ bei $m$ Knoten im Ursprungsgraphen und einer Adjazenzmatrix $n\times n$.
 \item[addPoint] erweitert wenn möglich einen bestehenden Graphen um einen Knoten, indem es zunächst ein \texttt{updateDensity} durchführt und anschließend mittels \texttt{constraint} alle Nebenbedingungen überprüft. \\ Laufzeit: $\mathcal{O}(k + m)$, falls die Density-Constraint erfüllt bleibt, sonst $\mathcal{O}(k)$.
 \item[expand] wendet \texttt{addPoint} auf alle Ergebnisse von \texttt{addablePoints} an.\\
 Laufzeit: $\mathcal{O}(n \cdot m \cdot (k + m))$ im worst-case einer voll besetzten Adjazenzmatrix. In der Praxis sind die Eingabegraphen kaum vernetzt und die Attributzahl $k$ ist klein, sodass sich die average-case-Laufzeit unter Berücksichtigung der alternativen Laufzeit von \texttt{addPoint} an $\mathcal{O}(n \cdot m \cdot k) \approx \mathcal{O}(n \cdot m)$ annähert.
 
\end{description}

\begin{lstlisting}[caption={Die maxDCB-Funktion},label=lst:maxDCB]
-- | Calculates all maximum DCB. A maximum DCB is a densely connected bicluster that
--   cannot be expanded by any additional node without breaking the constraints.
--   
--   This function does return the seed graphs themselves if they cannot be expanded.
maxDCB :: [Graph] -> Adj -> Attr -> Density -> MaxDivergence -> Int -> [Graph]
maxDCB [] _ _ _ _ _ = []
maxDCB gs adj attr dens maxDiv minHit =
    let next = L.map (expand adj attr dens maxDiv minHit) gs
                     +|| (parBuffer 1000 rdeepseq)
        (maximal, expandable) = part (\_ rm -> rm == []) (zip gs next)
        expandable' = filterLayer $ concat expandable
        -- Divide solutions into expandable solutions and maximum solutions.
        -- Expandable solutions yield a result via the 'expand' function.
    in maxDCB expandable' adj attr dens maxDiv minHit L.++ maximal
    -- append maximum solutions of prospective function calls and maximum solutions
    -- of this iteration
\end{lstlisting}

Der rekursive Funktionsaufruf findet in Zeile~14 statt. Hier werden iterativ alle expandierbaren Möglichkeiten evaluiert bis sie maximal erweitert sind und an die nicht erweiterbaren Graphen angehängt. In den Zeilen~8/9 wird die Expansion auf den Eingabegraphen \texttt{gs} parallel in einem Puffer von höchstens 1000 parallelen Anweisungen ausgeführt. Die Strategie, welche wir für die parallele Evaluation verwenden, lautet \texttt{rdeepseq}. Dadurch werden diese Graphen direkt vollständig ausgewertet und müssen nicht (z.\,B. durch Lazy Evaluation) nachberechnet werden.\par
\medskip
Anschließend partitionieren wir die expandierten Graphen in maximal erweiterte und in weiter expandierbare (Z.~10). Letztere filtern wir noch (Z.~11) nach Duplikaten, um redundante Weiterberechnung (und damit einen erhöhten Rechenaufwand) zu vermeiden. Zurückgeliefert werden somit alle Graphen, die maximal expandiert sind. \par
\medskip
Die Funktion \texttt{expand} wird letztendlich für jeden Graphen genau einmal aufgerufen. Der Rechenaufwand der $m$-ten Expansionsstufe mit $s$ Graphen ist zusammen mit der Filterung doppelter Graphen $\mathcal{O}(s m \cdot (n (k+m)+ \log s))$, für schwach vernetzte Eingabegraphen eher $\mathcal{O}(s m \cdot (n k + \log s))$. $k$ ist die Anzahl an Attributen und $n$ die Größe der Adjazenzmatrix. Allerdings wächst die Anzahl der Graphen pro Iteration im ungünstigsten Fall exponentiell an, woraus sich die Schwierigkeit des Problem als NP-schwer ergibt. In schwach vernetzten Eingabegraphen ist jedoch zu erwarten, dass die anfänglichen Seeds kaum erweiterbar sind, wodurch sich der gesamte Rechenaufwand stark reduziert. Dennoch besteht viel Potential zur Parallelisierung der Berechnung zur Verkürzung der Rechenzeit.

\section{Ausführung und Auswertung}
Im folgenden Abschnitt gehen wir genauer auf die verwendeten Compileroptionen und den durchgeführten Benchmark ein, sowie eine Auswertung der dadurch angefallenen Daten.
\subsection{Compileroptionen}
Als Compileroptionen sind in der mitgelieferten \texttt{.cabal}-Datei folgende Angaben eingestellt:\par
\texttt{ghc-options: -Odph -rtsopts -threaded -fno-liberate-case -funfolding-use-threshold1000 -funfolding-keeness-factor1000 -optlo-O3 -fllvm}.
Hierbei stehen die einzelnen Flags für:
\begin{description}[style=multiline,leftmargin=6.5cm,font=\ttfamily\bfseries]
 \item[-Odph] maximale GHC-Optimierung,
 \item[-rtsopts] Runtime-Optionen (+RTS -Nx -l -s etc.),
 \item[-threaded] Multithreading,
 \item[-fno-liberate-case] Code-Duplizierung jenseits von \texttt{-O2} vermeiden,
 \item[-funfolding-use-threshold1000] Analogon zu \texttt{\#pragma unroll 1000} in C++ wo möglich,
 \item[-funfolding-keeness-factor1000] empfohlen für besseres Unfolding,
 \item[-fllvm] auf llvm kompilieren, statt direkt Maschienencode zu erzeugen,
 \item[-optlo-O3] llvm-Compiler mit \texttt{-O3} starten.
\end{description}
Insbesondere das Unfolding der Funktionen und das Weiterreichen des Codes an LLVM bringt einen starken Performance-Zugewinn. LLVM kann hier auf die jeweils benutzte Architektur weiter optimieren.

\subsection{Garbage-Collector-Optimierung}
\begin{figure}[h!]
 \centering
 \includegraphics[width=15cm]{./img/gc_total.png}
 % gc_total.png: 1280x960 pixel, 96dpi, 33.86x25.40 cm, bb=0 0 960 720
 \caption{ghc-gc-tune Ausgabe}
 \label{fig:ghctune}
\end{figure}
Da Programmiersprachen mit Garbage-Collector immer den Ruf haben langsam zu sein, haben wir auch versucht den Garbage-Collector zu analysieren und zu optimieren. Der GHC benutzt einen Mehrstufigen GC. Dieser setzt sich zusammen ausr einem kleinen Speicher, der häufig collected wird (für z.b. Zwischenergebnisse, Funktionsvariablen und andere kurzlebige Daten) und einem selten collectedent Speicher, in dem langlebige Objekte liegen (z.b. Konfigurationseinstellungen, etc.). Noch mehr Level sind theoretisch möglich, liefern aber meist nicht mehr Performance. Auch versucht der GC diese Bereiche so klein wie möglich zu halten - wobei er zwischen neuallokation (=mögliche "Speicherverschwendung") und aufräumen (=Speicher freigeben; Zeitaufwändig) abwägen muss.\par \medskip
Generell kann man beim GHC-GC 2 grundlegende Optionen einstellen: Die Allokationsgröße (-A) und die Heap-Größe (-H). Hiermit wird mindestens -H Speicher allokiert und falls dieser nicht reicht in Blöcken von -A weiterer Speicher geholt. Weitere Optionen\footnote{\url{http://www.haskell.org/ghc/docs/7.6.3/html/users_guide/runtime-control.html}} (z.b. Initiale Stackgröße bei neuen Threads, etc.) sind möglich, aber in unserem Kontext nicht relevant.

Das Programm \texttt{ghc-gc-tune} probiert einfach brute-force die möglichen (meist sinnvollen) Kombinationen von -A und -H aus. Wir haben die Analyse auf dem Datensatz einer sparse 2000x2000-Adjazenzmatrix mit 20000 Einträgen durchgeführt um realistische Daten zu erhalten.\par
Da der Heap nur bei Schwankungen massiv zur Laufzeitverschlimmerung beiträgt lässt sich sehen, dass dieses sich erst negativ auswirkt, wenn wir einen zu großen Heap anfragen. Unser Programm liest zu Beginn alle Daten komplett ein. Von diesem Zeitpunkt aus werden die Datenstrukturen nur unwesentlich größer, da sie sich prinzipiell auf das Ergebnis des Algorithmus reduzieren lassen. So legen wir z.B. keine großen Zwischenergebnisse an, die sich hier negativ auswirken würden.
Die Allocation-Area (-A) ist standardmäßig auf $512k$ auseglegt, was sich hier als ideal herausstellt. Insbesondere in der Graph $Residency \cdot Time$ (in Abbildung \ref{fig:ghctune} oben links) zeigt, dass der GC am effektivsten mit nahe Standardeinstellungen (-A 512k, -H 0) ist. Wenn wir den Heap noch minimal erhöhen, ersetzen wir die inital ersten Allokationen durch eine einzelne, welches hier als Minimum bei (-A 512k -H 0) zu sehen ist.\par
\medskip
Alles in allem ist in unserem Falle kein GHC-GC-Tuning notwendig, da der GHC von sich aus schon sinnvolle Werte hat und so ein Test immer nur eine Einzelprüfung sein kann. Außerdem hat so ein \texttt{ghc-gc-tune}-Durchlauf eine Laufzeit, die weit über der Ausführung des Einzelfalles liegt.\footnote{Insgesamt wird das Programm $15\cdot10\times$ aufgerufen - häufig mit einer viel schlechteren Laufzeit als Ideal. Im Beispiel dauerte der längste Aufruf ca. 14 Sekunden, der schnellste ca. 2.}

\subsection{Laufzeit und Amdahls Gesetz} \label{test}
\begin{figure}[h!]
 \centering
 \includegraphics[scale=0.75,keepaspectratio=true]{./img/CPUvsAmdahl.png}
 % DCB-Module.png: 1024x512 pixel, 96dpi, 27.09x13.54 cm, bb=0 0 768 384
 \caption{Graphische Darstellung der Benchmark-Auswertung. Dieser Benchmark wurde auf einer 4-Kern-Maschine (i7-2600) gemacht, sodass die Laufzeit bei 4 Kernen nicht optimal ist, da durch Hintergrundaufgaben ca.\ 5\,\% CPU-Last auf einem Kern liegen.}
 \label{fig:Benchmark}
\end{figure}

Wir haben den Test mit einer bereitgestellten $4000\times 4000$-Adjazenzmatrix (spärlich besetzt, 80000 Einträge) insgesamt $10\times$ für jede Konfiguration (1, 2, 3 oder 4 Kerne) durchrechnen lassen. Dies ist in Abbildung~\ref{fig:Benchmark} zu sehen. Die Varianz war mit $< 0,003\,s$ zu gering um sinnvoll eingezeichnet zu werden. \par
Wir haben das Programm in zwei Teile unterteilt. Zum einen das Einlesen, welches Single-Threaded jeweils $0,9447\pm2e{-5}\,s$ und $\approx 1,05\,s$ im Multi-Threaded-Fall benötigte. Bei einer Single-Threaded-Laufzeit von $44,6581\pm2,30e{-2}\,s$ für den Rest des Programms ergibt sich nach Amdahl die in Tabelle~\ref{tab:Amdahl} angegebene Minimallaufzeit für das gesamte Programm.

\begin{table}
\caption{Speedup nach Amdahl und tatsächliche Messung}
\centering
 \begin{tabular}[h!]{l||r|r}
  Kerne & Speedup & Erreicht \\
  \hline
  \hline
   1 & 1,000& 1,000 \\
   2 & 1,959 & 1,965 \\
   3 & 2,878 & 2,839 \\
   4 & 3,761 & 3,629
 \end{tabular}
 \label{tab:Amdahl}
\end{table}

Man muss hierbei berücksichtigen, dass das Amdahlsche Gesetz positive Effekte, wie Superlinearität, nicht berücksichtigt. Diese können zwar auftreten, tun es aber in der Realität selten. Im Fall von 2 Kernen ist unser ermittelter Speedup leicht schneller als nach Amdahl möglich, was vermutlich auf Ungenauigkeiten der Messungen und unterschiedliches Vorgehen des Programms bei mehreren Rechenkernen zurückzuführen ist.\par
\medskip
Insgesamt lässt sich hierbei sehen, dass wir fast immer gleichauf mit Amdahls Gesetzt liegen und somit im ideal zu erwartenden Bereich der Parallelisierung.


\section{Fazit}

Die Versuche aus Abschnitt~\ref{test} belegen, dass der Algorithmus gut parallelisierbar ist und unser Programm nahezu optimal die Teilaufgaben auf die verfügbaren Ressourcen aufteilt. Für eine Berechnung auf noch mehr Rechenkernen ist zu erwarten, dass der Speedup zusätzlich durch Kommunikation leicht reduziert wird, da nach jedem Erweiterungsschritt die Teilergebnisse gesammelt werden müssen und nach doppelten Graphen gefiltert wird. Allerdings kommt uns dabei die Parallelisierung über \emph{Sparks} zugute, da durch die kleinen Teilaufgaben die Berechnungen gut aufgeteilt werden können und kein Prozess im Leerlauf auf die Synchronisation warten muss. \par
\medskip
Auch konnten wir zeigen, dass der Garbage-Collector nicht massiv die laufzeit verlängert. Die Speicherallokation machte bei unserem Programm im Falle von 4 Kernen lediglich 2,06s der 13,41s Gesamtlaufzeit aus. Auch wird die Garbage-Collection parallel auf allen Kernen ausgeführt, sodass sich auch hier die Arbeit geteilt wird und das System nicht nur auf einem Kern rechnet, da während der Garbage-Collection keine schreibenden Speicherzugriffe stattfinden können.
Auch eine Optimierung der Heap und Allocation-Parameter bringt in unserem Falle keinen weiteren Zugewinn, da diese schon von sich aus nahezu optimal gewählt sind. Präventiv allerdings zu große Werte zu nehmen würde die Laufzeit etwas verschlechtern und eine Analyse hat einen zu großen Zeitaufwand, sodass sie nur im einzelfalle sinnvoll sein kann.\par
\medskip
Eine parallelen Berechnung auf sehr vielen Rechenkernen bringt wie beschrieben einen sehr guten erwarteten Speedup, verglichen mit dem Amdahlschen Gesetz. Allerdings ist nach Amdahls Gesetz auch der Speedup bei einem Faktor von etwa 47,27 beschränkt, welcher nicht durch hinzufügen weiterer Kerne erreicht werden kann.\par
Grundsätzlich wäre auch eine GPU-beschleunigte Berechnung denkbar. Diese würde allerdings Probleme aufgrund der Natur des Algorithmus haben. Wir haben es hier nicht mit einem "flachen" Daten-Parallelen Algorithmus zu tun, sondern die Graphen können in einer beliebigen Generation nicht mehr expandierbar sein. Dieser Ablauf entspricht eher einem extrem unbalancierten Baum, welcher durch massiven Kommunikations-Overhead und die nötigen Kopiervorgänge auf Speicher(bus)ebene eine effiziente Grafikkartenberechnung behindert. Dennoch könnte man hier gegenüber einer herkömmlichen 4 oder 6-Kern-Maschiene noch etwas Performance herausholen.

%\newpage
%\printbibliography[heading=bibintoc]

\end{document}