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,
\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}
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.
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}
\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}
\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}
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
\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$.
\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
\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
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.
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
\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)
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}
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. \todo{Daten noch in eine Tabelle einfügen.}
+\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-Evolution-Cut}-Algorithmus}
+\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[\textsc{SN-Evolution-Cut}]{Der \textsc{SN-Evolution-Cut}-Algorithmus}
\label{sect:sn-evolution-cut}
Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
-von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
-Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
-gute Schnittmuster gesucht.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$
oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem
-$k$-Schnittmuster sind genau $k$ Zahlen nicht Null.
+$k$-Schnittmuster sind genau $k$ Zahlen ungleich Null.
Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu
invertieren.
+Die Eingabe für \textsc{SN-Evolution-Cut} ist ein $n$-Sortiernetzwerk und eine
+Zahl $k$, $1 \leqq k < n$, die angibt wie viele Leitungen entfernt werden
+sollen. Der Rückgabewert des \textsc{SN-Evolution-Cut}-Algorithmus ist ein
+\emph{$k$-Schnittmuster}. Wird das Schnittmuster auf das Sortiernetzwerk, mit
+dem der Algorithmus gestartet wurde, angewendet, entsteht ein möglichst
+schnelles und effizientes Sortiernetzwerk mit $m = n - k$ Leitungen. Da mit
+dem Eingabe-Netzwerk und dem zurückgegebenen $k$-Schnittmuster das
+$m$-Sortiernetzwerk eindeutig bestimmt ist, werden im Folgenden sowohl das
+$k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von
+\textsc{SN-Evolution-Cut} bezeichnet.
+
\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:bs}
+
+Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen
+Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll,
+ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke
+als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k
+= 6$ gestartet, resultiert das gefundene Schnittmuster in einem
+Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16}
+benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
+wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
+
+\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}
+
+Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen
+Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden,
+gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde
+mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten
+der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$,
+$w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder
+Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten
+befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des
+Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des
+resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der
+Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu
+können.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+ \hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+ \hline
+ 9 & 21 & & & & & & & & & & & & & & & \\
+ 10 & 20 & 27 & & & & & & & & & & & & & & \\
+ 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\
+ 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\
+ 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\
+ 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\
+ 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\
+ 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\
+ 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\
+ 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\
+ 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\
+ 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\
+ 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\
+ 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\
+ 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\
+ 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
+ \hline
+\bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+ Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+ die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
+ Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
+ \label{tbl:ec-bs-efficiency}
+\end{table}
+
+Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut}
+mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der
+gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von
+$m=23$) ein Ergebnis, das effizienter als \bs{m} ist.
+
+In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein
+effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut}
+gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren
+3~weniger als \bs{19}.
+
+Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke,
+beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein
+Sortiernetzwerk mit 31~Komparatoren gefunden.
+
+\begin{figure}
+ \centering
+ \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}}
+ \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}}
+ \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}}
+ \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}}
+ \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
+ 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+ erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
+ \label{fig:ec-bs-fast_networks}
+\end{figure}
+
+Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
+\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
+das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
+Tabelle~\ref{tbl:ec-bs-speed} ist die Anzahl der Schichten, die die Ergebnisse
+von \textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren,
+aufgelistet. Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n},
+jede Spalte enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die
+Zellen enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 9 & 6 & & & & & & & & & & & & & & & \\
+ 10 & 6 & 8 & & & & & & & & & & & & & & \\
+ 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
+ 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
+ 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
+ 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
+ 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
+ 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
+ 17 & 6 & 8 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
+ 18 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
+ 19 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
+ 20 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
+ 21 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
+ 22 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
+ 23 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
+ 24 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\bs{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\end{tabular}
+ \end{center}
+ \caption{Anzahl der Schichten der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+ Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+ die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
+ Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
+ \label{tbl:ec-bs-speed}
+\end{table}
+
+Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die
+schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke,
+die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
+werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.
+
+Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das
+Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m}
+führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt
+werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht
+einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m
+= 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu
+reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
+noch größer gewählt werden.
+
+Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von
+\textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten
+werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in
+Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im
+Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n =
+37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19}
+und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein
+Beispiel für ein solches Netzwerk ist in
+Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 95 & 14 \\
+ 21 & 94 & 14 \\
+ 22 & 93 & 14 \\
+ 23 & 93 & 14 \\
+ 24 & 93 & 14 \\
+ 25 & 96 & 13 \\
+ 26 & 96 & 13 \\
+ 27 & 96 & 13 \\
+ 28 & 96 & 13 \\
+ 29 & 95 & 13 \\
+ 30 & 96 & 13 \\
+ 31 & 95 & 13 \\
+ 32 & 96 & 13 \\
+ 33 & 93 & 13 \\
+ 34 & 94 & 13 \\
+ 35 & 93 & 13 \\
+ \rowcolor{green!10}
+ 36 & 92 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 37 & 92 & 13 \\
+ 38 & 93 & 13 \\
+ \hline
+ \bs{19} & 98 & 14 \\
+ \oes{19} & 91 & 14 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
+ von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt
+ wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als
+ \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit
+ 13~Schichten die Effizienz der vorherigen
+ Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese
+ Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37}
+ auf diese Art erzeugt wurde, ist in
+ Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.}
+ \label{tbl:ec-bs-19}
+\end{table}
\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
-wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
-durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
-Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer
-sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
-werden, Komparatoren ein.
-
-Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
-Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
-konstruiert wurde. Dieses Sortiernetzwerk be\-nö\-tigt 68~Komparatoren,
-12~weniger als das \emph{bitone Mergesort}-Netzwerk nach Batchers Methode.
-Gegenüber Batchers Methode sparen so konstruierte Sortiernetzwerke
-${\frac{1}{4}n(\log n - 1)}$ Komparatoren ein.
+wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode
+konstruiert wurde, durch systematisches Entfernen von Leitungen in einen
+ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert werden
+kann, so dass dieser alternative Mischer im Vergleich zu $\bm{\frac{n}{2} =
+2^{d-1}}$ Komparatoren einspart.
+
+Basierend auf diesen alternativen Mischern geben \textit{Mühlenthaler} und
+\textit{Wanka} eine Konstruktionsvorschrift für Sortiernetzwerke an, die
+gegenüber \bs{n} ${\frac{1}{4}n(\log n - 1)}$ Komparatoren einspart.
+Beispielsweise wird ein 16-Sortiernetzwerk angegeben, das nur 68~Komparatoren
+benötigt. Dieses Netzwerk ist in Abbildung~\ref{fig:16-muehlenthaler}
+dargestellt.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-muehlenthaler.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde 2010 von \textit{Mühlenthaler} und
+ \textit{Wanka} aus optimierten bitonen Mischern konstruiert und
+ in~\cite{MW2010} veröffentlicht.}
+ \label{fig:16-muehlenthaler}
+\end{figure}
\begin{figure}
\begin{center}
29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch
\textsc{SN-Evolution-Cut} gefunden wurde.
Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
-nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine
-Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in
-diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des
-Netzwerks scheinen rein zufällig zu sein.
+nachdem das Schnittmuster angewendet und das Netzwerk normalisiert wurde.
+% Eine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist
+% in diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten
+% des Netzwerks scheinen rein zufällig zu sein.
\begin{figure}
% 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
\label{fig:32-ec-from-bs64}
\end{figure}
-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
-Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein
-32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden,
-wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode
-konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den
-optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf
-208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte
-Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller
-dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die
-Geschwindigkeit dieser Sortiernetzwerke gleich ist.
+Wenn \textsc{SN-Evolution-Cut} mit dem \bs{64}-Netzwerk und $k = 32$ gestartet
+wird, findet der Algorithmus 32-Sortiernetzwerke, die effizienter sind als
+32-Sortiernetzwerke, die nach \textit{Mühlenthalers} und \textit{Wankas}
+Methode konstruiert werden. Ein von \textsc{SN-Evolution-Cut} aus \bs{64}
+generiertes 32-Sortiernetzwerk ist in Abbildung~\ref{fig:32-ec-from-bs64}
+dargestellt. Das \emph{bitone Mergesort}-Netzwerk \bs{32} benötigt
+240~Komparatoren, ein aus den optimierten Mischern aufgebautes Netzwerk
+verbessert die Effizienz auf 208~Komparatoren. Das Ergebnis von
+\textsc{SN-Evolution-Cut} kommt mit nur 206~Komparatoren aus. Die
+Geschwindigkeit aller genannten Sortiernetzwerke ist mit 15 parallelen
+Schritten identisch.
+
+Wenn die Leitungszahl des Eingabenetzwerks keine Zweierpotenz ist, kann
+\textsc{SN-Evo\-lu\-tion-Cut} auch 16-Sortiernetzwerke erzeugen, die diese
+Effizienz unterbieten. Das geht aus den Daten in
+Tabelle~\ref{tbl:ec-bs-efficiency} hervor. Ein 16-Sortiernetzwerk mit
+67~Komparatoren, das von \textsc{SN-Evolution-Cut} generiert wurde, ist in
+Abbildung~\ref{fig:16-ec-from-bs22} dargestellt.
Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
-\begin{figure}
- \centering
- \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}}
- \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}}
- \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann
- der Algorithmus schnelle Sortiernetzwerke ausgeben.}
- \label{fig:11-12-ec-from-bs22-bs24}
-\end{figure}
+Dass die Sortiernetzwerke, die mit den Schnittmustern von
+\textsc{SN-Evolution-Cut} entstehen, 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
+$k$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-k)$-Netzwerk.
-Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des
-\emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist,
-können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch
-effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die
-folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für
-\textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit
-der doppelten Leitungszahl. Die Abbildungen~\ref{fig:11-12-ec-from-bs22-bs24}
-und~\ref{fig:23-ec-from-bs46} zeigen beispielhaft ein 11-, 12- und
-23-Sortiernetzwerk, die aus \bs{22}, \bs{24} und \bs{46} generiert wurden.
+\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:oes}
-\begin{center}
-\begin{tabular}{|r|r|r|r|r|}
+Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die
+genauso effizient und schnell wie das entsprechende
+\emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der
+Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus
+\oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency}
+tabellarisch.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
\hline
-Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
- & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} &
- \bs{n} \\
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
\hline
-11 & 37 & 9 & 39 & 10 \\
-12 & 42 & 9 & 46 & 10 \\
-19 & 93 & 13 & 98 & 14 \\
-20 & 102 & 13 & 106 & 14 \\
-% 20: # sn-cut 2:MAX 3:MIN 4:MIN 9:MIN 10:MIN 13:MIN 14:MIN 15:MIN 19:MIN 20:MAX 24:MAX 26:MIN 27:MAX 29:MIN 31:MAX 33:MIN 34:MAX 35:MIN 37:MIN 39:MAX
-21 & 109 & 14 & 114 & 15 \\
-22 & 116 & 14 & 123 & 15 \\
-23 & 124 & 14 & 133 & 15 \\
+ 9 & 19 & & & & & & & & & & & & & & & \\
+ 10 & 19 & 26 & & & & & & & & & & & & & & \\
+ 11 & 19 & 26 & 31 & & & & & & & & & & & & & \\
+ 12 & 19 & 26 & 31 & 37 & & & & & & & & & & & & \\
+ 13 & 19 & 26 & 31 & 37 & 41 & & & & & & & & & & & \\
+ 14 & 19 & 26 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
+ 15 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
+ 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
+ 17 & 19 & 26 & 31 & 38 & 41 & 48 & 53 & 59 & 63 & & & & & & & \\
+ 18 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & & & & & & \\
+ 19 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & & & & & \\
+ 20 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & & & & \\
+ 21 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & & & \\
+ 22 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & & \\
+ 23 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & \\
+ 24 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
\hline
\end{tabular}
-\end{center}
+ \end{center}
+ \caption{Anzahl der Komparatoren der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-oes-efficiency}
+\end{table}
\begin{figure}
- \begin{center}
- \input{images/23-ec-from-bs46-fast.tex}
- \end{center}
- \caption{23-Sortiernetzwerk mit 124~Komparatoren in 14~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{46} mit dem
- Schnittmuster $\operatorname{MIN}(2, 4, 9, 12, 20, 22, 28, 30, 32, 33, 37,
- 38, 41)$, $\operatorname{MAX}(1, 5, 16, 19, 21, 24, 25, 35, 36, 43)$
- erzeugt.}
- \label{fig:23-ec-from-bs46}
+ \centering
+ \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{17} erzeugt.]{\input{images/11-ec-from-oes17-fast.tex}\label{fig:11-ec-from-oes17-fast}}
+ \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{18} erzeugt.]{\input{images/12-ec-from-oes18-fast.tex}\label{fig:12-ec-from-oes18-fast}}
+ \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m =
+ 11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+ erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m}
+ sind.}
+ \label{fig:ec-oes-fast_networks}
\end{figure}
-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}
+Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt
+schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein
+$m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes
+Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit
+war allerdings in allen beobachteten Fällen nur dann möglich, wenn
+zusätzliche Komparatoren in Kauf genommen wurden. In den
+Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser
+Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu
+beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
+Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.
+
+\begin{table}
\begin{center}
- \input{images/16-ec-from-ps32.tex}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 9 & 6 & & & & & & & & & & & & & & & \\
+ 10 & 6 & 8 & & & & & & & & & & & & & & \\
+ 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
+ 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
+ 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
+ 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
+ 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
+ 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
+ 17 & 6 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
+ 18 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
+ 19 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
+ 20 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
+ 21 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
+ 22 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
+ 23 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
+ 24 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\oes{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\end{tabular}
\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}
+ \caption{Anzahl der Schichten der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-oes-speed}
+\end{table}
In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
-\bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das
-Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46})
-effizienter, da es nur 124~Komparatoren benötigt.
+\bs{23} beziehungsweise \oes{23} eine Schicht einspart.
\begin{figure}
\begin{center}
\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.
+\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
-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:
+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.
-\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.
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 9 & 20 & & & & & & & & & & & & & & & \\
+ 10 & 20 & 27 & & & & & & & & & & & & & & \\
+ 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\
+ 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\
+ 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\
+ 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
+ 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
+ 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
+ 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\
+ 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\
+ 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\
+ 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\
+ 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\
+ 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\
+ 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\
+ 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\
+\hline
+\ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\
+\hline
+\end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-ps-speed}
+\end{table}
-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}
projects / diplomarbeit.git / blobdiff