X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=c6d3fe8a98f413dd0c3c22260dfa73cab3ddc2e6;hb=c383c2d71472004127a6ae08d689c02b94aa8661;hp=110b37e15a5a17b91b49169b4917ca59f01a6278;hpb=8c3620f715482f736048ffecea55af6c37e99f00;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 110b37e..c6d3fe8 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,21 @@ \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 active minimum maximum} = [vertex,color=violet!50, fill=violet!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 active minimum maximum} = [comp,color=black!20] +\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] @@ -261,10 +276,11 @@ Algorithmen. \subsection{Das bitone Mergesort-Netzwerk} Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein -Sortiernetzwerk, das 1968 von \emph{K.~E.~Batcher} veröffentlicht wurde. Es -ist deutlich effizienter als das Odd-Even-Transporitionsort-Netzwerk -- sowohl -in Bezug auf die Anzahl der Komparatoren als auch bezüglich der benötigten -Zeit, also der Anzahl der Schichten. +Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968} +veröffentlicht wurde. Es ist deutlich effizienter als das +Odd-Even-Transporitionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der +Komparatoren als auch bezüglich der benötigten Zeit, also der Anzahl der +Schichten. Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser @@ -275,11 +291,6 @@ Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die Instanzen des Netzwerks, deren Leitungszahl eine Zweierpotenz ist, $\operatorname{BS}(n = 2^t)$. -Ein Netzwerk von K.~E.~Batcher. Siehe: -K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring -Joint Comput. Conf., Vol. 32, 307-314 (1968) -\todo{Bibtex!} - \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer} Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen @@ -387,15 +398,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 @@ -422,8 +434,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} @@ -828,13 +841,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 @@ -845,19 +864,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!} @@ -865,12 +884,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 @@ -880,32 +919,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 @@ -916,20 +947,98 @@ Komparatoren ein. \begin{figure} \begin{center} - \input{images/16-ec-1277186619.tex} + \input{images/16-ec-from-bs32.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk} + $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.} + \label{fig:16-ec-from-bs32} +\end{figure} + +\begin{figure} + \begin{center} + \input{images/16-ec-from-bs32-normalized.tex} \end{center} - \caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen - und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem - Algorithmus \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk + \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.} - \label{fig:16-ec-1277186619} + \label{fig:16-ec-from-bs32-normalized} \end{figure} Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk $\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der 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. +16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den +Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized} +zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$ +und das +${\operatorname{MIN}(0,5,9,11,15,17,20,22,26,29,30)}$-${\operatorname{MAX}(2,4,13,19,24)}$-Schnittmuster, +das durch \textsc{SN-Evolution-Cut} gefunden wurde. +Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk +nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine +Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in +diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des +Netzwerks scheinen rein zufällig zu sein. + +\begin{figure} + % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX + % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX + % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX + % 63:MAX + \begin{center} + \input{images/32-ec-from-bs64.tex} + \end{center} + \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in + 15~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk + $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige + Schnittmuster ist + $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$, + $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37, + 40, 43, 47, 48, 49, 55, 56, 60, 63)$.} + \label{fig:32-ec-from-bs64} +\end{figure} + +Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen +Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk +konstruiert haben, kann demnach auch erreicht werden, wenn +$\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen +Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein +32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden, +wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode +konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den +optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf +208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte +Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller +dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die +Verzögerung dieser Sortiernetzwerke gleich ist. + +Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr +unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für +gute Schnittmuster anzugeben. + +Entscheidend für das Ergebnis eines Schnittmusters scheint beim bitonen +Mergesort-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein. +Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in +Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 +ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten +ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich +die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks +leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und +der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden. + + + +% Odd-Even-Transpositionsort-Netzwerk + +Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur +haben, 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} @@ -942,43 +1051,64 @@ 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 $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die -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. +strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die +Schichten~1 und~2 sowie 4~und~5 sind vertauscht. + +\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} @@ -1005,7 +1135,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} @@ -1116,13 +1246,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 @@ -1138,6 +1268,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 @@ -1161,9 +1300,31 @@ einen zufälligen Nachfolger. \begin{figure} \begin{center} - \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf} + \end{center} + \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen), + die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die + \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.} + \label{fig:markov-comparators-12} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-14-pct.pdf} + \end{center} + \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen), + die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die + \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.} + \label{fig:markov-comparators-14} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16-pct.pdf} \end{center} - \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.} + \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), + die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die + \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.} \label{fig:markov-comparators-16} \end{figure} @@ -1173,18 +1334,7 @@ einen zufälligen Nachfolger. \todo{In den Abschnitt "`Leitungen entfernen"' einbauen.} -\begin{figure} -\begin{center} -\input{images/32-ec-1277190372.tex} -\end{center} -\caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen - und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution-Cut} aus dem Bitonic-Mergesort-Netzwerk $BS(64)$ durch - 32~Schnitte erzeugt.} -\label{fig:32-ec-1277190372} -\end{figure} - -Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom +Abbildung~\ref{fig:32-ec-from-bs64} zeigt ein 32-Sortiernetzwerk, dass vom \textsc{SN-Evolution-Cut}-Algorithmus aus dem $BS(64)$-Netzwerk erzeugt wurde. Es besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als $BS(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler @@ -1274,8 +1424,8 @@ MAX( 34) Das würde mir noch einfallen$\ldots$ -%\bibliography{references} -%\bibliographystyle{plain} +\bibliography{references} +\bibliographystyle{plain} %\listoffigures