X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=14d0e098928ead9cf605ab5621fb5fa3576cbb27;hb=10f7e26bc636055d9594e7bff4e62d3d93fbd6c9;hp=38c4c56b48e94f15786b1b9c7b7e603a8121cd43;hpb=d0e58231c9ba92a00b21b9e4ea678f5622c2875e;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 38c4c56..14d0e09 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -44,7 +44,7 @@ \begin{document} -\tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5pt,inner sep=0pt] +\tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt] \tikzstyle{comp} = [draw,thick,-] \tikzstyle{compup} = [draw,thick,->] \tikzstyle{compdown} = [draw,thick,<-] @@ -52,6 +52,11 @@ \tikzstyle{diredge} = [draw,thick,->] \tikzstyle{prob} = [font=\tiny] +\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] +\tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10] + \maketitle \begin{abstract} Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden @@ -133,6 +138,11 @@ können?} \todo{$0-1$-Prinzip} +Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft +besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen +ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle +$2^n$~${0-1}$-Folgen sortiert. + Sortiernetzwerke: \begin{itemize} \item Ein Komparator-Netzwerk ist $\ldots$ @@ -167,9 +177,9 @@ als {\em Individuum} bezeichnet. Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen -ausgesucht ({\em Selektion}) und zu einer neuen Lösung kombiniert ({\em +ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em Rekombination}). Unter Umständen wird die neue Lösung noch zufällig -verändert ({\em Mutation}), bevor sie in die bestehende Lösungsmenge +verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em @@ -199,7 +209,7 @@ Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet. Abbildung~\ref{fig:odd_even_transposition_08} zeigt das OET-Netzwerk für -${n = 8}$. +${n = 8}$ Leitungen. \begin{figure} \begin{center} @@ -214,8 +224,9 @@ ${n = 8}$. 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} +\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer} Das Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk, das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine @@ -244,19 +255,19 @@ darf. \begin{figure} \centering \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}} + \qquad \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}} \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden - resultierenden Teilfolgen sind wiederum biton. - } + resultierenden Teilfolgen sind wiederum biton.} \label{fig:bitonic-merge-schema} \end{figure} Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je -${m = \frac{n}{2}}$~Elementen, ${u_0, u_1, \ldots, u_{m-1}}$ und -${v_0, v_1, \ldots, v_{m-1}}$. Die Folge der $u_i$ sei aufsteigend sortiert, -die Folge der $v_i$ sei absteigend sortiert: +${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und +$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend +sortiert, die Folge $V$ sei absteigend sortiert: \begin{eqnarray} u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\ v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1} @@ -288,13 +299,15 @@ Muster nun an einen Trichter. \subsubsection{Batcher's Bitonic-Mergesort-Netzwerk} Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von -$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen, und dem bitonen -Mischer $M(n)$. Die Rekursion bricht bei ${n = 1}$~ab -- eine einelementige +$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen und dem bitonen +Mischer~$M(n)$. Die Rekursion bricht bei ${n = 1}$~ab --~eine einelementige Liste ist immer sortiert. Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen. Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot) sowie der bitone Mischer~$M(8)$ (blau). + + %\begin{figure} %\begin{center} %\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf} @@ -305,30 +318,148 @@ sowie der bitone Mischer~$M(8)$ (blau). %\end{figure} \begin{figure} -\begin{center} -\input{images/batcher-8.tex} -\end{center} -\caption{$S(8)$, as {\em Batcher-Mergesort} Netzwerk für acht Eingänge. -Markiert sind die beiden Instanzen von $S(4)$ (rot) und der bitone Mischer -$M(8)$ (blau).} -\label{fig:batcher_08} + \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} \end{figure} \subsection{Odd-Even-Mergesort} Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und -Odd-Even-Transporisionsort (OET, siehe +{\em Odd-Even-Transpositionsort} (OET, siehe Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen -Mischer definiert. +"`Mischer"' definiert. + +\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer} + +Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte +Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit +weniger Vergleichen aus als der {\em bitone Mischer}, der im +Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde. + +Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die +Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden +sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und +$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei +$W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit: +\begin{equation} +w_i = \left\{ \begin{array}{ll} + u_i, & i < n \\ + v_{i-n}, & i \geqq n + \end{array} \right., + \quad 0 \leqq i < N +\end{equation} + +\begin{figure} + \begin{center} + \input{images/oe-merge.tex} + \end{center} + \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum + bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger + aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.} + \label{fig:oe-merge} +\end{figure} + +Diese werden jetzt in insgesamt vier sortierte Folgen aufgeteilt, je eine +Liste der geraden Indizes und je eine Liste der ungeraden Indizes. +\begin{eqnarray} + U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\ + U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\ + V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\ + V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right) +\end{eqnarray} + +Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die +ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden +rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am +Ausgang der Mischer die Folgen +\begin{eqnarray} + W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\ + W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right) +\end{eqnarray} +ergeben. + +Anschließend werden die Komparatoren zwischen benachbarten Leitungen +hinzugefügt, +\begin{equation} + w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2} +\end{equation} +die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em +Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}. + +Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen +Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde -- +entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was +offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven +Aufbau lauten: +\begin{itemize} + \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer. + \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem + einzelnen Komparator. +\end{itemize} + +Dass die resultierende Folge sortiert ist, lässt sich mit dem +{\em 0-1-Prinzip} leicht zeigen: +Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden +Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder +gleich der Anzahl der Nullen in den ungeraden Teilfolgen +$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten +sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen +$W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu: +\begin{eqnarray} + \left|W_{\textrm{gerade}}\right|_0 + &=& \left|U_{\textrm{gerade}}\right|_0 + + \left|V_{\textrm{gerade}}\right|_0 + = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil + + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\ + \left|W_{\textrm{ungerade}}\right|_0 + &=& \left|U_{\textrm{ungerade}}\right|_0 + + \left|V_{\textrm{ungerade}}\right|_0 + = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor + + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor +\end{eqnarray} +Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält +als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"' +Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall, +wenn $W_{\textrm{gerade}}$ $2$~Nullen mehr enthählt als +$W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu +sortieren. Die jeweiligen Situationen sind in +Abbildung~\ref{fig:oe-post-recursive} dargestellt. + +\begin{figure} + \centering + \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}} + \qquad + \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}} + \qquad + \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}} + \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der + kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der + Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im + letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis + sortiert ist.} + \label{fig:oe-post-recursive} +\end{figure} + +\subsubsection{Das Odd-Even-Mergesort-Netzwerk} -Beispiel: Siehe Abbildung~\ref{fig:odd_even_mergesort_08}. +Auch beim \emph{Odd-Even-Mergesort-Netzwerk} --~wie beim \emph{bitonen +Mergesort-Netzwerk}~-- entsteht das Sortiernetzwerk aus dem {\em +Odd-Even-Mischer} durch rekursives Anwenden auf einen Teil der Eingabe +(üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen. +Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge. \begin{figure} \begin{center} \input{images/oe-mergesort-8.tex} \end{center} -\caption{Das {\em Odd-Even-Mergesort} Netzwerk für acht Eingänge.} +\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge.} \label{fig:odd_even_mergesort_08} \end{figure} @@ -341,10 +472,49 @@ Beispiel: Siehe Abbildung~\ref{fig:odd_even_mergesort_08}. \section{Transformation von Sortiernetzwerken} -\begin{itemize} -\item Komprimieren (Alle Komparatoren so früh wie möglich anwenden). -\item Normalisieren (Transformation zu Standard-Sortiernetzwerken). -\end{itemize} +\subsection{Komprimieren} + +\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?} + +Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können +gleichzeitig ausgewertet werden, wie bereits in +Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter +\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl +von \emph{Schichten} verstanden. + +Diese Anzahl ist insbesondere beim automatisierten Bewerten von +Komparatornetzwerken interessant. \dots + +\subsection{Normalisieren} + +\begin{figure} + \centering + \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}} + \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}} + \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk + transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der + intuitiven Konstruktion und die normalisierte Variante.} + \label{fig:beispiel_normalisieren} +\end{figure} + +Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk} +ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung +zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante +transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis}) +einen Algorithmus an. + +Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das +bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd} +zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch +Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden +die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei +Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist. +In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven +Definition. + +In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen +Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche +Richtung. \subsection{Zwei Netzwerke kombinieren} @@ -354,15 +524,205 @@ Beispiel: Siehe Abbildung~\ref{fig:odd_even_mergesort_08}. \item Nach dem Pairwise sorting-network Schema. \end{itemize} -\subsection{Leitungen entfernen} +\subsection{Leitungen entfernen}\label{sect:leitungen_entfernen} + +Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von +\emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen +ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen +beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass +sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein +Sortiernetzwerk mit $n$~Eingängen erhalten müssen. + +Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein +Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung +„eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem +bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim +durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der +„Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index. +Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche +dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden +Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die +Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch +das {\em Odd-Even-Transpositionsort-Netzwerk}. + +\begin{figure} + \centering + \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}} + \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}} + \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}} + \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}} + \caption{Eine Leitung wird aus dem {\em Odd-Even-Transpositionsort} Netzwerk + $\textrm{OET}(8)$ entfernt: Auf der rot markierten Leitung wird $\infty$ + angelegt. Da der Wert bei jedem Komparator am unteren Ende herauskommt, ist + der Pfad fest vorgegeben. Da die restlichen Werte trotzdem noch richtig + sortiert werden müssen, kann dieser Pfad herausgetrennt werden. In der + letzten Abbildung ist $\textrm{OET}(7)$ markiert.} +\end{figure} + +Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw. +ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt +haben, werden ersatzlos gelöscht. Diese Komparatoren sind in +Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die +zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen +ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise +das Maximum angenommen wird, die an unterster oder oberster Stelle endet und +auf die keine Komparatoren mehr berührt +(Abbildung~\ref{fig:oe-transposition-cut1}). + +Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen +Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position +des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die +Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt. +Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme +auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage +getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste +mit $(n-1)$~Elementen darstellen. + +Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen +(Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für +$(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein +Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als +\emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}. + +Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das +Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot +markierten Komparatoren wurden verschoben, so dass sich eine kompaktere +Darstellung ergibt. Ausserdem ist das +{\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der +zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die +Ausgabe und kann entfernt werden. + +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. + +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 +auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um +ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben +sich insgesamt +\begin{displaymath} + \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. + +\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 +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: +\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!} + = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!} + \quad (n > m) +\end{displaymath} + +Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden +Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf +ein Sortiernetzwerk mit 16~Eingä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. + +Das Programm {\sc SN-Evolution-Cut} implementiert einen evolutionären +Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten +Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer +möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung +von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. \begin{itemize} -\item Min-Richtung -\item Max-Richtung + \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? \end{itemize} \section{Der evolutionäre Ansatz} +Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden +die vorgestellten Methoden kombiniert. + +\subsection{Bewertungsfunktion}\label{sect:bewertung} + +Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die +{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele, +die interessant sind: +\begin{itemize} + \item Möglichst wenige Komparatoren ("`klein"') + \item Möglichst wenige Schichten ("`schnell"') +\end{itemize} + +Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das +kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren +in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur +9~Schichten. + +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}} + + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren} + + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten} +\end{equation} +Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen +dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter +gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide +Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet -- +jegliche Ergebnisse sind dann rein zufälliger Natur. + +Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss +genommen werden. Ist er groß, wird der relative Unterschied der Güten +verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des +gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen +klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative +Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em +Exploitation}, das Finden lokaler Optima, bevorzugt. + +\subsection{Selektion} + +... + +\subsection{Rekombination} + +Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu +einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel +den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den +{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die +beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen. +Anschließend entfernen wir zufällig $n$~Leitungen wie in +Abschnitt~\ref{sect:leitungen_entfernen} beschrieben. + +Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft +erhält. + +\subsection{Mutation} + +Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation +--~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein +Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu +erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese +Eigenschaft zerstören. + +Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die +Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese +Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das +Ausprobieren aller $2^n$~Bitmuster. + +Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären +Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die +Population überprüft das Programm die Notwendigkeit jedes einzelnen +Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft, +ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt. + \begin{itemize} \item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der Schichten, kobiniert) @@ -385,7 +745,7 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} \begin{center} \input{images/08-e2-1237993371.tex} \end{center} -\caption{\tt images/08-e2-1237993371.tex} +\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten} \label{fig:08-e2-1237993371} \end{figure} @@ -393,7 +753,7 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} \begin{center} \input{images/09-e2-1237997073.tex} \end{center} -\caption{\tt images/09-e2-1237997073.tex} +\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten} \label{fig:09-e2-1237997073} \end{figure} @@ -401,26 +761,224 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} \begin{center} \input{images/09-e2-1237999719.tex} \end{center} -\caption{\tt images/09-e2-1237999719.tex} +\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten} \label{fig:09-e2-1237999719} \end{figure} +\begin{figure} +\begin{center} +\input{images/10-e2-1239014566.tex} +\end{center} +\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten} +\label{fig:10-e2-1239014566} +\end{figure} + \subsection{Güte} \begin{itemize} -\item So gut kann man mindestens werden \em{($\rightarrow$ Bitonic-Mergesort, -vermute ich)}. +\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}. \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab. \end{itemize} -\subsection{Vom evolutionären Algorithmus zu einer Markov-Kette} +\section{Markov-Kette} + +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. + +Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das +aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller +Leitungen eliminiert, lassen sich einige interessante Beobachtungen anstellen. +Netzwerke, die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von +$S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen +hervorgehen können, heißen \emph{Nachfolger} von $S_0$. + +Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem +gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei +Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer +Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$ +ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich +selbst erzeugen kann. + +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 +rekombiniert er das aktuelle Sortiernetzwerk mit sich selbst und erhält so +einen zufälligen Nachfolger. + +\begin{itemize} + \item $n \leftarrow \mathrm{Input}$ + \item \texttt{while} \textit{true} + \begin{itemize} + \item $n \leftarrow \operatorname{recombine} (n, n)$ + \end{itemize} +\end{itemize} \begin{itemize} -\item Kombiniere immer das aktuelle Netzwerk mit sich selbst. -\item Kann die Mindestgüte immernoch erreicht werden? ({\em Ich denke schon.}) -\item Anzahl der erreichbaren Sortiernetzwerke. + \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}). + \item Anzahl der erreichbaren Sortiernetzwerke. + \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen + Netzwerke. (Abbildung~\ref{fig:markov-comparators-16}) \end{itemize} +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf} + \end{center} + \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.} + \label{fig:markov-comparators-16} +\end{figure} + +%\input{shmoo-aequivalenz.tex} + +\section{Optimierung der Schnitte} + +Der \emph{evolution-cut}-Algorithmus nimmt ein gegebenes Sortiernetzwerk mit +$n$~Leitungen und sucht die beste Sequenz von $c$~Min- und Max-Schnitten um +ein ${(n-c)}$-Sortiernetzwerk zu erhalten. + +Bei diesem Algorithmus werden die \emph{Schnitt-Sequenzen} als Individuen +verwendet. 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$. + +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. + +\begin{figure} +\begin{center} +\input{images/16-ec-1277186619.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 + \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(32)$ durch + 16~Schnitte erzeugt.} +\label{fig:16-ec-1277186619} +\end{figure} + +Wendet man den \emph{evolution-cut}-Algorithmus auf das +Bitonic-Mergesort-Netzwerk $M(n)$ an und setzt die Anzahl der Schnitte~$c$ auf +$\frac{n}{2}$, so erhält man Sortiernetzwerke, die weniger Komparatoren +benötigen als $M(\frac{n}{2})$. + +Das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619} ist entstanden, +indem der Algorithmus \emph{evolution-cut} auf das $M(32)$-Sortiernetzwerk +angewendet wurde. Der Algorithmus fand eine Schnitt-Sequenz aus 16~Schnitten, +die ein Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in 10~Schichten +erzeugt. Das $M(16)$-Sortiernetzwerk besteht aus 80~Komparatoren in +10~Schichten. + +Dieses Ergebnis deckt sich mit dem Sortiernetzwerk, dass +\emph{Moritz Mühlenthaler} und \emph{Rolf Wanka} in ihrer Veröffentlichung +„Improving Bitonic Sorting by Wire Elimination“ vorstellen. Sie verwenden +Schnitte, um Komparatoren beim bitonen $(n,n)$-Mischer enizusparen. Ein +sukzessive aus optimieren Mischern aufgebautes Sortiernetzwerk spart +--~verglichen mit dem Bitonic-Mergesort-Netzwerk~-- $\frac{1}{4}n(\log n - 1)$ +Komparatoren ein. Bei einem Sortiernetzwerk mit 16~Leitungen also +12~Komparatoren -- 68 statt 80. + +\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 + \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(64)$ durch + 32~Schnitte erzeugt.} +\label{fig:32-ec-1277190372} +\end{figure} + +Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom +\emph{evolution-cut}-Algorithmus aus dem $M(64)$-Netzwerk erzeugt wurde. Es +besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als +$M(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler +und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen +Netzwerken gleich. + +\textbf{TODO:} $M(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten +möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$ +Komparatoren; $M(64)$: 672~Komparatoren. + +Schnitt-Sequenz: +MIN( 92) +MAX( 80) +MIN(100) +MAX( 54) +MAX(102) +MAX( 53) +MAX(105) +MAX( 6) +MAX( 99) +MAX( 79) +MAX( 26) +MIN(111) +MAX( 12) +MIN( 22) +MAX( 61) +MAX( 72) +MAX( 68) +MIN( 80) +MAX( 80) +MAX( 99) +MAX(105) +MAX( 0) +MIN( 8) +MAX( 40) +MAX( 74) +MAX( 40) +MAX( 40) +MIN( 56) +MAX( 27) +MAX( 13) +MAX( 1) +MAX( 81) +MAX( 17) +MAX( 4) +MIN( 36) +MIN( 22) +MAX( 13) +MIN( 72) +MAX( 24) +MAX( 5) +MIN( 10) +MAX( 59) +MIN( 37) +MAX( 65) +MAX( 46) +MAX( 73) +MAX( 58) +MAX( 29) +MAX( 65) +MIN( 23) +MAX( 56) +MAX( 11) +MIN( 75) +MIN( 51) +MIN( 46) +MIN( 34) +MAX( 32) +MAX( 6) +MAX( 37) +MIN( 4) +MIN( 28) +MIN( 20) +MAX( 33) +MAX( 34) + +% images/32-ec-1277190372.tex + \section{Empirische Beobachtungen} \begin{itemize}