X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=c4ac16576f2e133b358bd7100d87b48476fdc336;hb=502386e80e6d483ad822488ee630e35f5b828827;hp=c5d64e5ce8dd919c2e8db37988605c8e20bf1dea;hpb=461b195a7aec442b519e401b07c0faa8ff99f6a9;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index c5d64e5..c4ac165 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -41,6 +41,7 @@ \newcommand{\ps}[1]{\ensuremath{\operatorname{PS}(#1)}} \newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}(#1)}} \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}(#1)}} +\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}(#1)}} \newtheorem{definition}{Definition} \newtheorem{satz}{Satz} @@ -433,7 +434,7 @@ Schichten. Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser -\emph{„bitoner Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein +\emph{„bitone Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein verleiht dem Sortiernetzwerk seinen Namen. Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die @@ -442,20 +443,20 @@ Es ist jedoch möglich das Sortiernetzwerk für beliebige~$n$ zu erzeugen. \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer} -Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen -Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige -\emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone -Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden -Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton} -zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts -entstehen können. Die wichtigsten Varianten für das \emph{bitone -Mergesort-Netzwerk} zeigen die Abbildungen~\ref{fig:beispiel-biton-0} -und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und -eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen -ist wichtig zu beachten, dass das letzte Element nicht größer -(Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner -(Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein -darf. +Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen +Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine +beliebige \emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine +\emph{bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton +absteigenden Folge, oder ein zyklischer Shift davon. +Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten +die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das +\emph{bitone Mergesort}-Netzwerk zeigen die +Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie +erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste +aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass +das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. +kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge +sein darf. \begin{figure} \centering @@ -547,10 +548,9 @@ alle Komparatoren in die gleiche Richtung zeigen. \begin{center} \input{images/batcher-8.tex} \end{center} - \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 + \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht + Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden + bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven Schritt hinzugefügt wurden (grün).} \label{fig:bitonic-08} \end{figure} @@ -578,17 +578,17 @@ vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von 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} +\subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer} -Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein +Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer} -vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter +vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even}-Mischer unter Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH} -Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die +Der \emph{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 @@ -622,7 +622,7 @@ geraden Indizes und je eine Liste der ungeraden Indizes. 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 +rekursiv von kleineren \emph{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) \\ @@ -635,8 +635,8 @@ 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}. +die die Folge~$W$ sortieren. Den schematischen Aufbau des +\emph{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 -- @@ -686,7 +686,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \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 + kleineren \emph{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.} @@ -737,7 +737,7 @@ benötigt werden. Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von -sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die +sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht $\operatorname{OES}(n)$ aus @@ -754,7 +754,7 @@ Komparatornetzwerke definiert sind. \end{center} \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden - \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade + \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten Komparatoren zwischen benachbarten Leitungen (grün).} \label{fig:odd-even-mergesort-08} @@ -763,7 +763,7 @@ Komparatornetzwerke definiert sind. In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk $\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den -\emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind +\emph{Odd-Even}-Mischer für acht Leitungen dar: Die beiden blauen Blöcke sind die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden. @@ -822,6 +822,7 @@ die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine Komprimierung durchgeführt werden. \subsection{Normalisieren} +\label{sect:normalisieren} \begin{figure} \centering @@ -886,7 +887,7 @@ $\operatorname{OES}(9)$ benötigt beispielsweise 26~Komparatoren, die in in neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten benötigen. Kombiniert man zwei dieser Netzwerke mit dem -\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das +\emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit 18~Eingängen, das 80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt 82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Sherenaz~W. @@ -927,17 +928,20 @@ 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}} + \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad + durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}} + \subfigure[Komparatoren, die einen wechsel der Leitungen bewirken, werden + durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}} + \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit + 7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}} + \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die + Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}} \caption{Eine Leitung wird aus dem - \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{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 - $\operatorname{OET}(7)$ markiert.} + \emph{Odd-Even-Transpositionsort}-Netzwerk \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 \oet{7} markiert.} \label{fig:oe-transposition-cut} \end{figure} @@ -960,19 +964,25 @@ 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}. +Wenn man die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in +Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, 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. +\emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der +zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und +kann entfernt werden. + +Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig +\emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen +\emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu +\emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben. \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster} \label{sect:anzahl_schnittmuster} @@ -980,8 +990,8 @@ 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 auf diese Art und -Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke -mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die +Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit +$n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als \emph{$k$-Schnittmuster}. @@ -1006,12 +1016,13 @@ führen beide Reihenfolgen zum selben Ergebnis. \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise 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, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen -Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl -der möglichen Schnittmuster: +vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken. +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, +$k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/ +Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen +Schnittmuster: \begin{displaymath} 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right) = 2^{k} \cdot \frac{n!}{k! (n-k)!} @@ -1051,8 +1062,8 @@ sich die Resultate auch in der ersten Schicht nicht unterscheiden. 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das - \emph{Odd-Even-Mergesort-Netzwerk}, 4973 für das \emph{bitone - Mergesort-Netzwerk} und 18764 für das \emph{Pairwise-Sorting-Netzwerk}.} + \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone + Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.} \label{fig:count-cuts-16} \end{figure} @@ -1078,9 +1089,9 @@ Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen} Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des -\emph{Odd-Even-Mergesort-Netzwerks}, 4973 ($\approx 0,15\%$) beim -\emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx 0,57\%$) beim -\emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr Iterationen +\emph{Odd-Even-Mergesort}-Netzwerks, 4973 ($\approx 0,15\%$) beim +\emph{bitonen Mergesort}-Netzwerk und 18764 ($\approx 0,57\%$) beim +\emph{Pairwise-Sorting}-Netzwerk. Zwar ist es möglich, dass mehr Iterationen die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster @@ -1094,7 +1105,8 @@ für „kleine“ x-Werte verlässt. Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können, kann man sich einer stochastischen Methode bedienen, der sogenannten -\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von +\emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für +schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$ @@ -1228,21 +1240,21 @@ Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von Pseudocode wie folgt beschreiben: \begin{verbatim} -Gütesumme := 0 -Auswahl := (leer) - -für jedes Individuum in Population -{ - reziproke Güte := 1.0 / Guete(Individuum) - Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte) - Gütesumme := Gütesumme + reziproke Güte - - mit Wahrscheinlichkeit P + Gütesumme := 0 + Auswahl := (leer) + + für jedes Individuum in Population { - Auswahl := Individuum + reziproke Güte := 1.0 / Guete(Individuum) + Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte) + Gütesumme := Gütesumme + reziproke Güte + + mit Wahrscheinlichkeit P + { + Auswahl := Individuum + } } -} -gib Auswahl zurück + gib Auswahl zurück \end{verbatim} \subsection{Rekombination} @@ -1250,13 +1262,15 @@ gib Auswahl zurück 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 +\emph{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. +Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in +Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt. Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft -erhält. +erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das +Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass +nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können. \subsection{Mutation} @@ -1320,7 +1334,7 @@ als das bitone Mergesort-Netzwerk: $\operatorname{BS}(16)$ benötigt 80~Komparatoren, das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67. -\subsection{Versuche mit dem Odd-Even-Mischer} +\subsection{Versuche mit dem \emph{Odd-Even}-Mischer} \begin{figure} \begin{center} @@ -1328,7 +1342,7 @@ Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67. \end{center} \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even-Mischers} + \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers erzeugt.} \label{fig:16-e1-oddeven-1296543330} \end{figure} @@ -1336,9 +1350,9 @@ Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67. Leider lies sich das Ergebnis des bitonen Mischers -- das von \textsc{SN-Evolution} ausgegebene Netzwerk war effizienter als das rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem -\emph{Odd-Even-Mischer} nicht wiederholen. Zwar erreichen die +\emph{Odd-Even}-Mischer nicht wiederholen. Zwar erreichen die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des -\emph{Odd-Even-Mischers} findet, das \emph{Odd-Even-Mergesort}-Netzwerk +\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Schnelligkeit und Effizienz, ein Beispiel hierfür ist in Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das $\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch @@ -1392,11 +1406,11 @@ 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{Schnittmuster}, -die in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, 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$. +Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die +in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, 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 @@ -1474,7 +1488,7 @@ Netzwerks scheinen rein zufällig zu sein. \label{fig:32-ec-from-bs64} \end{figure} -Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen +Das Ergebnis von \textit{Mühlenthaler} und \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 @@ -1531,7 +1545,7 @@ 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 +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 @@ -1651,9 +1665,9 @@ selbst erzeugen kann. Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der -Nachfolger zwar noch unter 20.000, bei den untersuchten 32-Sortiernetzwerken -wurden jedoch bereits bis zu $2,6 \cdot 10^8$ unterschiedliche Schnittmuster -geschätzt. +Nachfolger zwar noch unter 20.000, bei den untersuchten +32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$ +unterschiedliche Schnittmuster geschätzt. Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem @@ -1663,86 +1677,158 @@ selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt dich de Algorithmus wie folgt beschreiben: \begin{verbatim} -Netzwerk := Eingabe - -für n Iterationen -{ - Nachfolger := kombiniere (Netzwerk, Netzwerk) - Netzwerk := Nachfolger -} - -gib Netzwerk zurück + Netzwerk := Eingabe + + für n Iterationen + { + Nachfolger := kombiniere (Netzwerk, Netzwerk) + Netzwerk := Nachfolger + } + + gib Netzwerk zurück \end{verbatim} -Die Abbildungen~\ref{fig:markov-comparators-12}, -\ref{fig:markov-comparators-14}, \ref{fig:markov-comparators-12}, -\ref{fig:markov-comparators-16} und~\ref{fig:markov-comparators-18} zeigen die -Anzahl der Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf -seinem zufälligen Pfad durchläuft. Ausserdem eingezeichnet ist eine -\emph{Gamma-Verteilung}. +Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der +Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem +zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der +\textsc{SN-Markov}-Algorithmus auf einem entsprechenden +\emph{Odd-Even-Transporitionsort}-Netzwerk gestartet hat mindestens +1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der +Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler +erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende +prezenturale Verteilung zu sehen. + +Ebenfalls in die Graphen in Abbildung~\ref{fig:markov-comparators} +eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen +Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der +um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde. +Beispielsweise war die kleinste erreichte Komparatorzahl bei +16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$ +gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$ +und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem +Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$ +unter den Graphen angegeben. + +\begin{figure} + \centering + \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}} + \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}} + \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}} + \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}} + \caption{Anzahl der Komparatoren von Sortiernetzwerken, + die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet + ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der + gemessenen Daten darstellt.} + \label{fig:markov-comparators} +\end{figure} \begin{figure} \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf} \end{center} - \caption{Zyklen, die beim \textit{Random Walk} des - \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die - Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der - y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale - Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} - \label{fig:markov-cycles-16} + \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von + \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem + \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.} + \label{fig:comparison-comparators} \end{figure} +Dass der \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der +\textsc{SN-Evolution}-Algo\-rithmus, ist aus dem Graphen in +Abbildung~\ref{fig:comparison-comparators} ersichtlich. Analog zu dem Versuch +mit \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die +Anzahl der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als +Startnetzwerk diente bei beiden Algorithmen das +\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der +x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der +ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt +wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden außerdem nach +dem verwendeten Mischer-Netzwerk -- \oem{32} beziehungsweise \bm{32}. + +Sowohl der \textsc{SN-Markov}-Algorithmus, der das +\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit +\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die +bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind. +Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger: +Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit +63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335 +\%$ rund 20~mal höher. + +Erwartunggemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem +\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist +jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die +mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort} -- \oet{16} +ist aus 120~Komparatoren aufgebaut, bei dem Lauf, der die Daten für +Abbildung~\ref{fig:comparison-comparators} lieferte, traten auch jeweils ein +Sortiernetzwerk mit 121 und 124~Komparatoren auf. Da Sortiernetzwerke mit so +vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen +Iterationen nicht noch einmal erzeugt wurden, handelt es sich vermutlich um +ein Phänomen, das mit der Initialisierung mit dem +\emph{Odd-Even-Transpositionsort}-Netzwerk zusammenhängt. + +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,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 425 262,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. 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} +% +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.} +% \label{fig:markov-comparators-18} +%\end{figure} + +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} +% \end{center} +% \caption{Zyklen, die beim \textit{Random Walk} des +% \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die +% Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der +% y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale +% Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} +% \label{fig:markov-cycles-16} +%\end{figure} + + \todo{Schreibe noch etwas zu …} \begin{itemize} \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}) + \item \textsc{SN-Count-Markov} (ggf) \end{itemize} -\begin{figure} - \begin{center} - \includegraphics[viewport=0 0 425 262,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 425 262,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 425 262,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. 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} - -\begin{figure} - \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf} - \end{center} - \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen), - die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die - \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.} - \label{fig:markov-comparators-18} -\end{figure} - \newpage -\section{Ausblick} +\section{Fazit und Ausblick} + +\todo{Ausformulieren} +\begin{itemize} +\item Mit \textsc{SN-Evolution} und \oem{n} kann man nicht besser werden als + \oes{n}. +\item Mit \textsc{SN-Evolution} und \bm{n} kann man besser werden als \bs{n}. +\item Vermutlich kann man mit \textsc{SN-Evolution} und \bm{n} so gut werden +wie \textsc{SN-Evolution-Cut}, wenn er mit \bs{2n} gestartet wird. +\item Leider sind keine konstruktiven Methoden erkannt worden. +\end{itemize} Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten @@ -1751,11 +1837,11 @@ Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknöpft werden könnte. -\subsection{Verwendung des Pairwise-Sorting-Netzwerk in \textsc{SN-Evolution}} +\subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}} Die aktuelle Implementierung von \textsc{SN-Evolution} (Abschnitt~\ref{sect:sn-evolution}) kann sowohl den \emph{bitonen Mischer} als -auch den \emph{Odd-Even-Mischer} verwenden, um zwei Individuen zu +auch den \emph{Odd-Even}-Mischer verwenden, um zwei Individuen zu rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von @@ -1773,8 +1859,7 @@ wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine $n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren $n$-Sortiernetzwerken als \ps{n} führen. -\subsection{Kooperation von \textsc{SN-Evolution} und -\textsc{SN-Evolution-Cut}} +\subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}} Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis} in~\cite{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution} @@ -1826,7 +1911,7 @@ Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet werden: \begin{verbatim} -$ sn-bitonicsort 18 | sn-normalize >sn-18 + $ sn-bitonicsort 18 | sn-normalize >sn-18 \end{verbatim} Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und es einfach zu ermöglichen, Programme zu verketten, ist eines der