From: Florian Forster Date: Sat, 26 Feb 2011 09:20:40 +0000 (+0100) Subject: Abschnitte "SN-Markov" und "SN-Evolution-Cut" vertauscht. X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=commitdiff_plain;h=d6fe7037c87edd9d38931b1d9c56c959c0e0561b Abschnitte "SN-Markov" und "SN-Evolution-Cut" vertauscht. --- diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 5b66097..0fd8e89 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1617,6 +1617,175 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} %\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} @@ -1645,6 +1814,7 @@ 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} \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde, @@ -1803,86 +1973,6 @@ von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem $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}. - \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk} \label{sect:sn-evolution-cut:oes} @@ -2034,174 +2124,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: - -\begin{verbatim} - Netzwerk := Eingabe - - für n Iterationen - { - Nachfolger := kombiniere (Netzwerk, Netzwerk) - Netzwerk := Nachfolger - } - - gib Netzwerk zurück -\end{verbatim} +\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk} -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. +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. -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}