X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=f797cc2f04ad4f0bf9d0dc57c68dd5b032a1d548;hb=40cc8835cd6ee6e506a3286d93e645542080047e;hp=8e7beca45b659efc04c39df648245f61b015ae43;hpb=56c2c5c629b941ea34faf8ee70fe0c0a87a5ebf3;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 8e7beca..f797cc2 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -270,8 +270,8 @@ Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden. Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der Komplexitätsklasse -$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, -ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$ +$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, +ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$ verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen, ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt, @@ -435,7 +435,7 @@ ${n = 8}$ Leitungen. \begin{center} \input{images/oe-transposition-8.tex} \end{center} - \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.} + \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.} \label{fig:odd-even-transposition-08} \end{figure} @@ -458,7 +458,7 @@ $\operatorname{OET}(3)$ sortiert. Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n -(n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind. +(n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind. Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren, ($\Theta(n \log (n)^2)$), die in weniger Schichten, ($\Theta(\log (n)^2)$), angeordnet sind. @@ -574,7 +574,7 @@ Statt an eine Treppe erinnert das Muster nun an einen Trichter. Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus -$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren +$\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren besteht, die in $\log(n)$~Schichten angeordnet werden können. \subsubsection{Das bitone Mergesort-Netzwerk} @@ -598,10 +598,10 @@ alle Komparatoren in die gleiche Richtung zeigen. \begin{center} \input{images/batcher-8.tex} \end{center} - \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).} + \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~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} @@ -656,10 +656,12 @@ w_i = \left\{ \begin{array}{ll} \begin{center} \input{images/oe-merge.tex} \end{center} - \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Im - Vergleich zum bitonen Mischer für acht Leitungen kommt dieses Schema mit - einem Komparator weniger aus. Der Effekt wird durch den rekursiven Aufbau - verstärkt.} + \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die + beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$, + die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der + Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt + dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den + rekursiven Aufbau verstärkt.} \label{fig:oe-merge} \end{figure} @@ -701,7 +703,7 @@ Aufbau lauten: einzelnen Komparator. \end{itemize} -Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass die resultierende Folge +Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise $V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den @@ -746,7 +748,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \end{figure} Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden, -bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$ +bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$ Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit Schichten im Mischer-Netzwerk), hängt von der längeren der beiden Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$. @@ -764,7 +766,7 @@ Länge der Eingabefolgen, $n$ und $m$ ab: \end{displaymath} Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar, -dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist. +dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist. Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der @@ -802,7 +804,7 @@ die als leere Komparatornetzwerke definiert sind. \begin{center} \input{images/oe-mergesort-8.tex} \end{center} - \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert + \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~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 Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten @@ -813,7 +815,7 @@ die als leere Komparatornetzwerke definiert sind. In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk zu sehen. Rot markiert sind die beiden rekursiven Instanzen $\operatorname{OES}(4)$. Die anderen Blöcke stellen den -\emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind +\emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden. @@ -935,7 +937,7 @@ zu sortieren und die Ausgaben mit einem der beschriebenen Mischer zusammenfügen. Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken} -$\operatorname{BS}(8)$ mit je acht Leitungen mit dem +$\operatorname{BS}(8)$ mit je 8~Leitungen mit dem \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt @@ -1252,10 +1254,20 @@ die bei Sortiernetzwerken verfolgt werden können: \item Möglichst wenige Schichten („schnell“) \end{itemize} -Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das -effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus -60~Komparatoren in 10~Schichten. Das schnellste bekannte 16-Sortiernetzwerk -besteht aus 61~Komparatoren in nur 9~Schichten. +\begin{figure} + \centering + \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}} + \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}} + \caption{Das effizienteste und das schnellste Sortiernetzwerk für + 16~Leitungen, das derzeit bekannt ist.} + \label{fig:16-best-known} +\end{figure} +Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. +Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für +16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in +Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte +16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in +Abbildung~\ref{fig:16-voorhis} zu sehen. Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"' berücksichtigen kann, hat die folgende allgemeine Form: @@ -1301,17 +1313,20 @@ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen} \subsection{Selektion} -Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere -Wahrscheinlichkeit haben zur nächsten Generation beizutragen. Diese -Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das -Streben des Algorithmus nach besseren Lösungen. +Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig +aus der Population auswählt. Sie werden im folgenden Schritt miteinander +rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht +gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen +eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen. +Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für +das Streben des Algorithmus nach besseren Lösungen. Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint, -ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der -Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. +passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt +und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. -Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von -Pseudocode wie folgt beschreiben: +Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt +sich mit Pseudocode wie folgt beschreiben: \begin{verbatim} Gütesumme := 0 Auswahl := (leer) @@ -1330,6 +1345,10 @@ Pseudocode wie folgt beschreiben: gib Auswahl zurück \end{verbatim} +Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die +Rekombination zu erhalten. Das heißt, dass die Individuen bei +\textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden. + \subsection{Rekombination} \label{sect:sn-evolution:rekombination} @@ -1460,13 +1479,20 @@ Im vorherigen Abschnitt wurde gezeigt, dass der Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem \emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind. Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht -wiederholen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung -des \emph{Odd-Even}-Mischers findet, erreichen das +erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des +\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in -Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Wenn $n$ keine -Zweierpotenz ist, kann \textsc{SN-Evolution} unter Umständen Sortiernetzwerke -ausgeben, die schneller als \oes{n} sind. +Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. + +Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch +mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution} +Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht +beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt +\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen. +\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der +Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet +sich in Tabelle~\ref{tbl:sn-ev-oem-fast}. %\begin{figure} %\begin{center} @@ -1500,9 +1526,275 @@ ausgeben, die schneller als \oes{n} sind. %\label{fig:10-e2-1239014566} %\end{figure} +\begin{table}\label{tbl:sn-ev-oem-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\ +\cline{2-5} + & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & 19 & 6 & 19 & 6 \\ + 9 & 26 & 8 & 26 & 8 \\ + 10 & 31 & 9 & 31 & 9 \\ + 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\ + 12 & 43 & \gcell 9 & \gcell 41 & 10 \\ + 13 & 48 & 10 & 48 & 10 \\ + 14 & 53 & 10 & 53 & 10 \\ + 15 & 59 & 10 & 59 & 10 \\ + 16 & 63 & 10 & 63 & 10 \\ + 17 & 74 & 12 & 74 & 12 \\ + 18 & 82 & 13 & 82 & 13 \\ + 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\ + 20 & 97 & 14 & 97 & 14 \\ + 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\ + 22 & 117 & \gcell 14 & \gcell 114 & 15 \\ + 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\ + 24 & 128 & 15 & \gcell 127 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der + Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} + gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion + nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = + 1$, $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} + +\subsection{Zufälliger Mischer} + +Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige +Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der +\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das +Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur +12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur +82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen, +um das beste Ergebnis beider Konstruktionen zu erreichen. +\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier +Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem +\emph{Odd-Even}-Mischer wählen. + +Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des +Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast} +zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der +Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem +Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und +20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen +Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz. + +\begin{table}\label{tbl:sn-ev-rnd-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} + & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} + & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\ +\cline{2-7} + ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & 20 & 6 & \gcell 19 & 6 & \gcell 19 & 6 \\ + 9 & 26 & 8 & 26 & 8 & 26 & 8 \\ + 10 & 31 & \gcell 8 & 31 & 9 & 31 & \gcell 8 \\ + 11 & \Gcell 37 & 9 & 38 & 9 & \Gcell 37 & 9 \\ + 12 & 42 & 9 & 43 & 9 & \gcell 41 & 9 \\ + 13 & 48 & 10 & 48 & 10 & 48 & 10 \\ + 14 & 54 & 10 & \gcell 53 & 10 & \gcell 53 & 10 \\ + 15 & 61 & 10 & \Gcell 59 & 10 & \Gcell 59 & 10 \\ + 16 & 67 & 10 & \gcell 63 & 10 & 64 & 10 \\ + 17 & 76 & 12 & \Gcell 74 & 12 & \Gcell 74 & 12 \\ + 18 & 87 & \gcell 12 & \gcell 82 & 13 & 83 & \gcell 12 \\ + 19 & 93 & 13 & 93 & 13 & \Gcell 92 & 13 \\ + 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\ + 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\ + 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\ + 23 & 134 & 14 & 129 & 14 & \Gcell 128 & 14 \\ + 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung der verschiedenen Mischer. Der Algorithmus wurde mit dem + \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach + 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten + $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$, + $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} + %\input{shmoo-aequivalenz.tex} \newpage +\section{Der \textsc{SN-Markov}-Algorithmus} +\label{sect:markov} + +Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen +Abschnitt verwendet 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, kombiniert das aktuelle Netzwerk +\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller +Leitungen, 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 $S_1$ durch die Rekombination von $S_0$ mit sich +selbst erzeugt werden 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-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 +gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu +gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich +selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der +Algorithmus wie folgt beschreiben: + +\begin{verbatim} + Netzwerk := Eingabe + + für n Iterationen + { + Nachfolger := kombiniere (Netzwerk, Netzwerk) + Netzwerk := Nachfolger + } + + gib Netzwerk zurück +\end{verbatim} + +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-Transpositionsort}-Netzwerk gestartet und 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 +prozentuale Verteilung zu sehen. + +Ebenfalls in die Graphen der 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/comparison-comparators-16.pdf} + \end{center} + \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} + +Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der +\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der +\textsc{SN-Evolution}-Algo\-rith\-mus. 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 sich außerdem je +nach verwendetem 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. + +Erwartungsgemäß 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, trat auch jeweils ein +Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so +vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen +Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das +mit der Initialisierung durch das \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} + +\newpage \section{Der \textsc{SN-Evolution-Cut}-Algorithmus} \label{sect:sn-evolution-cut} @@ -1531,6 +1823,19 @@ multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu invertieren. \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk} +\label{sect:sn-evolution-cut:bs} + +\begin{figure} + \begin{center} + \input{images/16-ec-from-bs22.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk + $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4, + 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.} + \label{fig:16-ec-from-bs22} +\end{figure} \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde, @@ -1686,88 +1991,8 @@ Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem \emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und -$m$~Schnitten gestartet, so ist das beste Ergebnis immer das -$\operatorname{OET}(n-m)$-Netzwerk. - -\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk} - -Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk} -$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The -Pairwise Sorting Network“ \cite{P1992} definiert. Startet man -\textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe, -16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, das die gleiche -Anzahl 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. - -\begin{figure} - \begin{center} - \input{images/16-ec-from-ps32.tex} - \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in - 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} - $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} - \label{fig:16-ec-from-ps32} -\end{figure} - -Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht -einsetzt und auch nicht auf einem Mischer basiert, ist das -\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in -Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In -den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die -strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die -Schichten~1 und~2 sowie 4~und~5 sind vertauscht. - -\begin{figure} - \begin{center} - \input{images/32-pairwise-cut-16-pairwise.tex} - \end{center} - \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu - sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk - bilden.} - \label{fig:ps16-from-ps32} -\end{figure} - -Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach -regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres -schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das -einfache Schnittmuster -\begin{displaymath} -\textit{Eingang}_i = \left\{ \begin{array}{rl} - -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\ - \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\ - ? & \quad \mathrm{sonst} - \end{array} \right. -\end{displaymath} -für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk -$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der -dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das -verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32} -dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind -diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden -Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den -„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht -werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende -Netzwerk in schwarz gut zu erkennen. - -\begin{figure} - \begin{center} - \input{images/16-pairwise.tex} - \end{center} - \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten - ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das - resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.} - \label{fig:16-pairwise} -\end{figure} - -Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf -$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein -8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für -größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise -kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} -konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} -untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. +$k$~Schnitten gestartet, so ist das beste Ergebnis immer das +$\operatorname{OET}(n-k)$-Netzwerk. \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk} \label{sect:sn-evolution-cut:oes} @@ -1920,174 +2145,90 @@ effizienter, da es nur 124~Komparatoren benötigt. \label{fig:23-ec-from-oes46} \end{figure} -\newpage -\section{Der \textsc{SN-Markov}-Algorithmus} -\label{sect:markov} - -Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen -Abschnitt verwendet 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, kombiniert das aktuelle Netzwerk -\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller -Leitungen, 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 $S_1$ durch die Rekombination von $S_0$ mit sich -selbst erzeugt werden 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-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 -gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu -gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich -selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der -Algorithmus wie folgt beschreiben: +\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk} -\begin{verbatim} - Netzwerk := Eingabe - - für n Iterationen - { - Nachfolger := kombiniere (Netzwerk, Netzwerk) - Netzwerk := Nachfolger - } - - gib Netzwerk zurück -\end{verbatim} +Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene +Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war +(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise +ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich, +wie und warum es jede beliebige Eingabe sortiert. -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-Transpositionsort}-Netzwerk gestartet und 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 -prozentuale Verteilung zu sehen. - -Ebenfalls in die Graphen der 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. +Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian +Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} +definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit +$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man +ein Sortiernetzwerk, das die gleiche Anzahl 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. \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} + \begin{center} + \input{images/16-ec-from-ps32.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} + $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} + \label{fig:16-ec-from-ps32} \end{figure} +Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht +einsetzt und auch nicht auf einem Mischer basiert, ist das +\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in +Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In +den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die +strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die +Schichten~1 und~2 sowie 4~und~5 sind vertauscht. + \begin{figure} \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf} + \input{images/32-pairwise-cut-16-pairwise.tex} \end{center} - \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} + \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu + sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk + bilden.} + \label{fig:ps16-from-ps32} \end{figure} -Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der -\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der -\textsc{SN-Evolution}-Algo\-rith\-mus. 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 sich außerdem je -nach verwendetem 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. - -Erwartungsgemäß 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, trat auch jeweils ein -Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so -vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen -Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das -mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk -zusammenhängt. +Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach +regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres +schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das +einfache Schnittmuster +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\ + \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} +für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk +$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der +dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das +verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32} +dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind +diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden +Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den +„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht +werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende +Netzwerk in schwarz gut zu erkennen. -%\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} + \input{images/16-pairwise.tex} + \end{center} + \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten + ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das + resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.} + \label{fig:16-pairwise} +\end{figure} -%\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} +Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf +$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein +8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für +größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise +kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} +konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} +untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. \newpage \section{Fazit und Ausblick}