X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=a861992d1334c2e237723e30188a7815bd3c75b7;hb=6b2c14e2dbbb4a2ca86032cdc228d4fc96ce6543;hp=38c4c56b48e94f15786b1b9c7b7e603a8121cd43;hpb=d0e58231c9ba92a00b21b9e4ea678f5622c2875e;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 38c4c56..a861992 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. -Beispiel: Siehe Abbildung~\ref{fig:odd_even_mergesort_08}. +\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} + +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} @@ -354,7 +485,47 @@ 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} + +Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein +Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung +entfernt. Zunächst wird angenommen, dass das Minimum oder das Maximum an einem +der Eingänge anliegt. Der Weg durch das Netzwerk zum entsprechenden Ausgang +ist dadurch fest vorgegeben, insbesondere welche Komparatoren dafür sorgen, +dass die Leitung gewechselt wird und welche nicht. +Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch +das {\em Odd-Even-Transpositionsort-Netzwerk}. + +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 zeigt Abbildung~\ref{fig:oe-transposition-cut1}. Wenn +man die Maximum-Leitung entfernt (Abbildung~\ref{fig:oe-transposition-cut2}), +erhält man ein Sortiernetzwerk für $(n-1)$~Leitungen. + +\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} + +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. \begin{itemize} \item Min-Richtung @@ -363,6 +534,81 @@ Beispiel: Siehe Abbildung~\ref{fig:odd_even_mergesort_08}. \section{Der evolutionäre Ansatz} +Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden +die vorgestellten Methoden kombiniert. + +\subsection{Bewertungsfunktion} + +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 +631,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 +639,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,15 +647,256 @@ 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} + +% ============ + +\section{Shmoo-Äquivalenz} + +Die folgenden 16-Eingang-Sortiernetzwerke wurden alle mit dem +\emph{Algorithmus~1} gefunden. Sie haben alle 63~Komparatoren in 10~Schichten, +jeweils die selbe Anzahl wie Odd-Even-Mergesort. + +Um wiederkehrende Muster in den hinteren Schichten der erzeugten +Sortiernetzwerke besser untersuchen zu können, wurden die erzeugten Netzwerke +in Gruppen aufgeteilt. Zwei Netzwerke befinden sich dann in der selben +Gruppen, wenn die Nullen bzw. Einsen, die auf einer Leitung vorkommen können, +nach der 5.~Schicht (Schicht~4, da bei Null mit dem Zählen begonnen wird) +nicht mehr ändert. Das heißt, dass die Schichten 0--4 unterschiedlich +aufgebaut sind, aber den selben Effekt erziehlen. Die Schichten 5--9 sind +hingegen innerhalb einer Gruppe austauschbar und oft (immer?) identisch. + +Die Anzahl der Netzwerke in den jeweiligen Gruppen ist unterschiedlich. Zur +Zeit sind in den Gruppen so viele Netzwerke:\\ +\begin{tabular}{|l|r|r|} \hline +Gruppe~0 & 18 & $48,7\%$ \\ +Gruppe~1 & 9 & $24,3\%$ \\ +Gruppe~2 & 6 & $16,2\%$ \\ +Gruppe~3 & 3 & $8,1\%$ \\ +Gruppe~4 & 1 & $2,7\%$ \\ \hline +\end{tabular} + +Die hinteren Schichten zwischen den Gruppen~1 und~3 schauen so aus, als wären +sie nur gespiegelt. Warum kommt Gruppe~1 aber viel häufiger vor? Ggf. eine +Konsequenz aus dem Normieren? + +Dito für die Gruppen~2 und~4. Warum ist die eine häufiger? + +Ist Gruppe~0 symmetrisch bzgl. der Leitungen? + +% Gruppe 0 + +\begin{figure} +\begin{center} +\input{images/16-e1/group0/16-e1-1258009316.tex} +\end{center} +\caption{{\tt images/16-e1/group0/16-e1-1258009316.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258009316} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group0/16-e1-1258010866.tex} +\end{center} +\caption{{\tt images/16-e1/group0/16-e1-1258010866.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258010866} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group0/16-e1-1258011861.tex} +\end{center} +\caption{{\tt images/16-e1/group0/16-e1-1258011861.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258011861} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group0/16-e1-1259060992.tex} +\end{center} +\caption{{\tt images/16-e1/group0/16-e1-1259060992.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1259060992} +\end{figure} + +%\begin{figure} +%\begin{center} +%\input{images/16-e1/group0/16-e1-1259061148.tex} +%\end{center} +%\caption{{\tt images/16-e1/group0/16-e1-1259061148.tex}: 63~Komparatoren in +%10~Schichten.} +%\label{fig:16-e1-1259061148} +%\end{figure} + +% Gruppe 1 + +\begin{figure} +\begin{center} +\input{images/16-e1/group1/16-e1-1258009982.tex} +\end{center} +\caption{{\tt images/16-e1/group1/16-e1-1258009982.tex}: 63~Komparatoren in 10~Schichten. +Schichten 4--9 identisch zu 16-e1-1258030047 (Gruppe~1).} +\label{fig:16-e1-1258009982} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group1/16-e1-1258010023.tex} +\end{center} +\caption{{\tt images/16-e1/group1/16-e1-1258010023.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258010023} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group1/16-e1-1258029734.tex} +\end{center} +\caption{{\tt images/16-e1/group1/16-e1-1258029734.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258029734} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group1/16-e1-1258030047.tex} +\end{center} +\caption{{\tt images/16-e1/group1/16-e1-1258030047.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258030047} +\end{figure} + +%\begin{figure} +%\begin{center} +%\input{images/16-e1/group1/16-e1-1258034768.tex} +%\end{center} +%\caption{{\tt images/16-e1/group1/16-e1-1258034768.tex}: 63~Komparatoren in +%10~Schichten.} +%\label{fig:16-e1-1258034768} +%\end{figure} + +% Gruppe 2 + +\begin{figure} +\begin{center} +\input{images/16-e1/group2/16-e1-1258029063.tex} +\end{center} +\caption{{\tt images/16-e1/group2/16-e1-1258029063.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258029063} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group2/16-e1-1258034821.tex} +\end{center} +\caption{{\tt images/16-e1/group2/16-e1-1258034821.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258034821} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group2/16-e1-1259054993.tex} +\end{center} +\caption{{\tt images/16-e1/group2/16-e1-1259054993.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1259054993} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group2/16-e1-1259058588.tex} +\end{center} +\caption{{\tt images/16-e1/group2/16-e1-1259058588.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1259058588} +\end{figure} + +%\begin{figure} +%\begin{center} +%\input{images/16-e1/group2/16-e1-1259063485.tex} +%\end{center} +%\caption{{\tt images/16-e1/group2/16-e1-1259063485.tex}: 63~Komparatoren in +%10~Schichten.} +%\label{fig:16-e1-1259063485} +%\end{figure} + +%\begin{figure} +%\begin{center} +%\input{images/16-e1/group2/16-e1-1259063618.tex} +%\end{center} +%\caption{{\tt images/16-e1/group2/16-e1-1259063618.tex}: 63~Komparatoren in +%10~Schichten.} +%\label{fig:16-e1-1259063618} +%\end{figure} + +% Gruppe 3 + +\begin{figure} +\begin{center} +\input{images/16-e1/group3/16-e1-1258012027.tex} +\end{center} +\caption{{\tt images/16-e1/group3/16-e1-1258012027.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258012027} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group3/16-e1-1258037039.tex} +\end{center} +\caption{{\tt images/16-e1/group3/16-e1-1258037039.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1258037039} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group3/16-e1-1259065042.tex} +\end{center} +\caption{{\tt images/16-e1/group3/16-e1-1259065042.tex}: 63~Komparatoren in +10~Schichten.} +\label{fig:16-e1-1259065042} +\end{figure} + +% Gruppe 4 + +\begin{figure} +\begin{center} +\input{images/16-e1/group4/16-e1-1259060520.tex} +\end{center} +\caption{{\tt images/16-e1/group4/16-e1-1259060520.tex}: 63~Komparatoren in 10~Schichten. +(Gruppe~4).} +\label{fig:16-e1-1259060520} +\end{figure} + +\begin{figure} +\begin{center} +\input{images/16-e1/group4/16-e1-1259067171.tex} +\end{center} +\caption{{\tt images/16-e1/group4/16-e1-1259067171.tex}: 63~Komparatoren in 10~Schichten. +(Gruppe~4).} +\label{fig:16-e1-1259067171} +\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} @@ -421,6 +908,152 @@ vermute ich)}. \item Anzahl der erreichbaren Sortiernetzwerke. \end{itemize} +\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}