X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=7c76502d7dc81f137a901771baf1c0340838f450;hb=79bfdb02670c94f68482c15778402f745b644899;hp=6df6048aa637e8eb1c48bcd3f7051962fa626021;hpb=9c25159564439e81b2d237ef32e5697211a63774;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 6df6048..7c76502 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1,4 +1,4 @@ -\documentclass[a4paper,10pt]{article} +\documentclass[a4paper,11pt]{article} \usepackage[utf8]{inputenc} \usepackage{ngerman} \usepackage{fancyhdr} @@ -52,6 +52,19 @@ \tikzstyle{diredge} = [draw,thick,->] \tikzstyle{prob} = [font=\tiny] +\tikzstyle{edge minimum} = [edge,color=blue!20] +\tikzstyle{edge maximum} = [edge,color=red!20] +\tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50] +\tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50] +\tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20] +\tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20] +\tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20] +\tikzstyle{comp active minimum} = [comp] +\tikzstyle{comp active maximum} = [comp] +\tikzstyle{comp inactive minimum} = [comp,color=blue!20] +\tikzstyle{comp inactive maximum} = [comp,color=red!20] +\tikzstyle{comp inactive minimum maximum} = [comp,color=black!20] + \tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10] \tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10] \tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10] @@ -383,15 +396,16 @@ alle Komparatoren in die gleiche Richtung zeigen. \begin{center} \input{images/batcher-8.tex} \end{center} - \caption{$S(8)$, Batcher's {\em bitone Mergesort-Netzwerk} für acht - Eingänge. Markiert sind die beiden Instanzen von $S(4)$ (rot), die beiden - bitonen Mischer~$M(4)$ (blau) und die Komparatoren, die im letzten rekursiven - Schritt hinzugefügt wurden (grün).} - \label{fig:batcher_08} + \caption{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk} + für acht Eingänge. Markiert sind die beiden Instanzen von + $\operatorname{BS}(4)$ (rot), die beiden bitonen + Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten + rekursiven Schritt hinzugefügt wurden (grün).} + \label{fig:bitonic-08} \end{figure} Das konkrete Netzwerk~$\operatorname{BS}(8)$ ist in -Abbildung~\ref{fig:batcher_08} zu sehen. Eingezeichnet sind ebenfalls die +Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade, die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist @@ -418,8 +432,9 @@ Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk} Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist OES dem \emph{bitonen Mergesort-Netzwerk}, das im vorherigen Abschnitt vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von -\textit{K.~Batcher} gefunden worden und wird rekursiv durch einen Mischer -definiert. +\textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968} +beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht +darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist. \subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer} @@ -824,13 +839,19 @@ Darstellung ergibt. Ausserdem ist das zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die Ausgabe und kann entfernt werden. +\subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster} +\label{sect:anzahl_schnittmuster} + Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$, $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk -mit $n$~Eingängen reduzieren. +mit $n$~Eingängen reduzieren. Das Anwenden mehrerer Minimum- und +Maximum-Schnitte bezeichnen wir als \emph{Schnittmuster}. -\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus} +Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung +auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die +Schnittmuster \emph{unterschiedlich} bezüglich~$S$. Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als @@ -841,19 +862,19 @@ sich insgesamt \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!} \quad (n > m) \end{displaymath} -Möglichkeiten. Diese Möglichkeiten sind nicht alle unterschiedlich. Legt man -beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die -oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum -selben Ergebnis. +\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle +unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung +und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks, +führen beide Reihenfolgen zum selben Ergebnis. \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise -Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte -reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber -unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus +Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster +reduziert, die Menge der so erzeugbaren Sortiernetzwerke bleibt aber +unverändert. Die Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen, und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende -Formel: +Formel für die Anzahl der Schnittmuster: \begin{displaymath} 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right) = 2^{n-m} \cdot \frac{n!}{(n-m)! m!} @@ -861,12 +882,32 @@ Formel: \quad (n > m) \end{displaymath} -Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden +Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf -ein Sortiernetzwerk mit 16~Ein\-gängen zu reduzieren sind 16~Schnitte notwendig, -für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein -Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter -erheblichem Ressourcenaufwand möglich. +ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit +16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$ +Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große +Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich. + +Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner +als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der +ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide +Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und +unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen +der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die +Werte unterscheiden. + +Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe +Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des +Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun +unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster +erzeugen. In der zweiten und allen folgenden Schichten kann man diesen +Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die +Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass +sich die Resultate auch in der ersten Schicht nicht unterscheiden. + +\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus} +\label{sect:sn-evolution-cut} Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten @@ -876,32 +917,24 @@ von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst gute Schnittmuster gesucht. -Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die -\emph{Schnitt-Sequenzen} als Individuen. Eine \emph{Schnitt-Sequenz} ist eine -Liste mit $c$~Schnitten, die jeweils durch die Start-Leitung und die Richtung -\textit{Min} beziehungsweise \textit{Max} gegeben ist. Der Algorithmus wendet -jeden Schnitt einzeln an, so dass eine Leitungsnummer mehrfach in einer -Schnittsequenz vorkommen kann. Die höchste zulässige Leitungsnummer ist -abhängig von der Position des Schnitts in der Sequenz. Der Schnitt an -Position~$i$ darf höchstens die Leitungsnummer~${n-i-1}$ -enthalten.\footnote{Die niedrigste Leitungsnummer ist $0$, die höchste -Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.} - -Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen -Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten -Sequenz. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$. +Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster} +als Individuen. Um zwei Individuen zu rekombinieren werden die ersten +$r$~Schnitte des einen Schnittmusters verwendet und die letzten +${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit +$0 \leqq r \leqq c$. Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die Schnitt-Richtung. -In ihrer Arbeit \textit{“Improving Bitonic Sorting by Wire Elimination”} -zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka}, wie man einen -bitonen Mischer, der nach Batchers Methode konstruiert wurde, durch -systematisches Entfernen von Leitungen in einen ebenfalls bitonen Mischer mit -der Hälfte der Leitungen transformiert. Diese alternativen Mischer sparen im -Vergleich zu den Mischern, die nach Batchers Methode konstruiert werden, -Komparatoren ein. +% bitones Mergesort-Netzwerk + +In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka}, +wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde, +durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen +Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer +sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert +werden, Komparatoren ein. Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer @@ -927,6 +960,17 @@ Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein 16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in Abbildung~\ref{fig:16-ec-1277186619} zu sehen. +% Odd-Even-Transpositionsort-Netzwerk + +Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so +ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ +erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein +zufällig zu sein. Dies ist jedoch kein Eigenschaft des Algorithmus, sondern +hängt insbesondere von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} +beispielsweise mit dem \emph{Odd-Even-Transpositionsort-Netzwerk} +$\operatorname{OET}(n)$ und $m$~Schnitten gestartet, so ist das beste Ergebnis +immer das $\operatorname{OET}(n-m)$-Netzwerk. + \begin{figure} \begin{center} \input{images/16-ec-from-ps32.tex} @@ -938,26 +982,16 @@ Abbildung~\ref{fig:16-ec-1277186619} zu sehen. \label{fig:16-ec-from-ps32} \end{figure} -Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so -ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ -erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein -zufällig zu sein. Dies ist jedoch kein Eigenschaft des Algorithmus, sondern -hängt insbesondere von der Eingaben. Wird \textsc{SN-Evolution-Cut} -beispielsweise mit dem \emph{Odd-Even-Transpositionsort-Netzwerk} -$\operatorname{OET}(n)$ und $m$~Schnitten gestartet, so ist das beste Ergebnis -immer das $\operatorname{OET}(n-m)$-Netzwerk. +% Pairwise-Sorting-Netzwerk Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The -Pairwise Sorting Network“ definiert. Startet man \textsc{SN-Evolution-Cut} mit -$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man -ein Sortiernetzwerk, dass die gleiche Anzahl an Komparatoren und Schichten hat -wie $\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Der Algorithmus gibt -auch nach zahlreichen Versuchen nur eines von zwei Sortiernetzwerken zurück, -die beide sehr symmetrisch sind und eine saubere Struktur aufweisen. Eines der -beiden Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} -dargestellt, das andere Sortiernetzwerk unterscheidet sich lediglich dadurch, -dass die zweite und dritte Schicht vertauscht sind. +Pairwise Sorting Network“ \cite{P1992} definiert. Startet man +\textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe, +16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche +Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und +$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in +Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht einsetzt und auch nicht auf einem Mischer basiert, ist der @@ -968,13 +1002,45 @@ strukturell identisch zu $\operatorname{PS}(8)$ sind -- die Schichten~1 und~2 sowie 4~und~5 sind vertauscht, was jeweils zum selben Ergebnis nach dem Schichtenpaar führt. +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\ + \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} + +\begin{figure} + \begin{center} + \input{images/32-pairwise-cut-16-pairwise.tex} + \end{center} + \caption{PS(32) mit 16 Schnitten zu PS(16).} + \label{fig:ps16-from-ps32} +\end{figure} + +\begin{figure} + \begin{center} + \input{images/16-pairwise.tex} + \end{center} + \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten + ($\operatorname{MIN}(0,2,4,6), \operatorname{MAX}(9,11,13,15)$). Das + resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.} + \label{fig:16-pairwise} +\end{figure} + Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann man $\operatorname{OES}(8)$ erhalten. +% Odd-Even-Mergesort-Netzwerk + +\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.} + \begin{itemize} \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort. \item Wie gut kann man durch wegschneiden werden? - \item Wieviele Schnitte ergeben das selbe Netzwerk? + \item Wieviele Schnitte ergeben das selbe Netzwerk? Oder andersrum: Wieviele + unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein + Netzwerk / Knoten in der Markov-Kette? \item Abschnitt „Optimierung der Schnitte“ hier einbauen. \end{itemize} @@ -1001,7 +1067,7 @@ in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"' berücksichtigen kann, hat die folgende allgemeine Form: \begin{equation} - \mathit{Guete}(S) = w_{\mathrm{Basis}} + \operatorname{Guete}(S) = w_{\mathrm{Basis}} + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren} + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten} \end{equation} @@ -1112,13 +1178,13 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab. \end{itemize} -\section{Markov-Kette} +\section{Der \textsc{SN-Markov}-Algorithmus} -Der evolutionäre Algorithmus aus dem vorherigen Abschnitt verwendete immer -zwei zufällige Sortiernetzwerke („Individuen“) aus einer Population. Da die -beiden „Eltern“ zufällig und unabhängig voneinander ausgewählt werden, kann es -vorkommen, dass das selbe Sortiernetzwerk zweimal verwendet und mit sich -selbst kombiniert wird. +Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen +Abschnitt verwendete immer zwei zufällige Sortiernetzwerke („Individuen“) aus +einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander +ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal +verwendet und mit sich selbst kombiniert wird. Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller @@ -1134,6 +1200,15 @@ Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $ ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich selbst erzeugen kann. +Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl +(unterschiedlichen) Schnittmuster und damit die Anzahl der Nachfolger sehr +groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis +zu +\begin{displaymath} + 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right) +\end{displaymath} +Nachfolger. + Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen