\newcommand{\ps}[1]{\ensuremath{\operatorname{PS}(#1)}}
\newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}(#1)}}
\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}(#1)}}
+\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}(#1)}}
\newtheorem{definition}{Definition}
\newtheorem{satz}{Satz}
\maketitle
\begin{abstract}
+\todo{Einleitung schreiben.}
+
Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
vorgestellt (Odd-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
-das hinbekomme bzw. Recht behalte.}
+das hin bekomme bzw. Recht behalte.}
\end{abstract}
\newpage
\subsection{Motivation}\label{sect:motivation}
-\begin{itemize}
-\item Sortiernetzwerke sind toll, weil $\ldots$
-\item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
-\item Bisher noch kein evolutionärer Algorithmus zur automatischen
- Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
-\end{itemize}
+\emph{Sortiernetzwerke} sind ein theoretisches Konstrukt, dass auch von
+Personen ohne Zugang zum Thema beziehungsweise der theoretischen Informatik
+schnell verstanden werden kann. Eine Einführung wird in
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} gegeben. Nichtsdestotrotz ist
+das Finden von Sortiernetzwerken sowie das Beweisen, dass ein
+Komparatornetzwerk jede beliebige Eingabe sortiert, im Allgemeinen sehr
+schwierig und nach heutigem Kenntnisstand nur mit exponentiellem Aufwand zu
+bewältigen.
+
+Einfacher ist der Korrektheitsbeweis bei konstruktiven Verfahren, da hier die
+Konstruktionsvorschrift genutzt werden kann um die Korrektheit für beliebige
+Eingabegrößen zu beweisen. Im Abschnitt~\ref{sect:konstruktive_netzwerke}
+geschieht dies beispielsweise für zwei von \emph{Kenneth~E. Batcher} 1968
+gefundenen Konstruktionsvorschriften.
+
+Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon früh
+Computer und automatische Suchverfahren eingesetzt. Bisherige Ansätze
+versuchen meist, in der Menge aller Komparatornetzwerke jene zu finden, die
+die Sortiereigenschaft besitzen und aus wenigen Komparatoren bestehen. Die
+Eigenschaft, jede Eingabepermutation zu sortieren, ist also ein
+Optimierungsziel und nicht durch das Vorgehen gewährleistet. Dafür können
+theoretisch alle Sortiernetzwerke durch diese Algorithmen gefunden werden --
+genügend Laufzeit vorausgesetzt.
+
+In dieser Arbeit werden Methoden verwendet, die die Menge der Sortiernetzwerke
+nie verlassen, dafür aber auch nicht alle existierenden Sortiernetzwerke
+erzeugen können. So muss für ein gefundenes Komparatornetzwerk nicht mehr
+nachgewiesen werden, dass es jede beliebige Eingabe sortiert, weil diese
+Eigenschaft durch das Verfahren sichergestellt ist.
\subsection{Einleitung}\label{sect:einleitung}
eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die
\emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je
zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von
-\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichlichkeit
+\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichtlichkeit
durch schwarze Punkte symbolisiert.
Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in
-das Netzwerk hineingegeben. Jeder Komparator vergleicht die Zahlen „auf“ den
+das Netzwerk hinein gegeben. Jeder Komparator vergleicht die Zahlen „auf“ den
beiden Leitungen, die er verbindet. Nach einem Komparator befindet sich die
kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat.
Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine
Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man
-eine \emph{Schicht} des Komparatornetwerks. Die \emph{Verzögerung} eines
+eine \emph{Schicht} des Komparatornetzwerks. Die \emph{Verzögerung} eines
Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die
sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der
benötigten parallelen Schritte darstellt.
erzeugen, die der Sortierung der Eingabe entspricht, heißen
\emph{Sortiernetzwerke}. Das in
Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
-ist \emph{kein} Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur
+ist \emph{kein} Sortiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur
Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar
zerstört.
sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
-4,3~Millarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
+4,3~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
beschäftigen.
\subsubsection{Evolutionäre Algorithmen}
Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
die beziehungsweise eine der {\em optimalen} Lösungen als einzige Ausgabe des
Algorithmus zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele
-dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
-beispielsweise imitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
-auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
+dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur.
+Beispielsweise imitieren die „Ameisenalgorithmen“ das Verhalten von Ameisen
+auf der Futtersuche, um kurze Rundreisen auf Graphen zu berechnen.
Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
\emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
zu optimieren~\cite{H1992}. Diese \emph{Parasiten} genannten Eingaben wurden
-daran gemessen, bei wievielen Komparatornetzwerken sie beweisen konnten, dass
+daran gemessen, bei wie vielen Komparatornetzwerken sie beweisen konnten, dass
sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen~/
Komparatornetzwerken nicht alle 0-1-Folgen, sondern nur erfolgreiche
Parasiten~/ schwierige Eingaben überprüft werden. Auf diese Art und Weise
\label{fig:13-juille}
\end{figure}
\textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
-Non-Determinism} (END) nannte. Dabei handelt es sich nicht um einen
-\emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, sondern um
-eine verteilte, probabilistische Breitensuche, die an die \emph{Strahlsuche}
-(englisch: \textit{beam search}), ein Verfahren der Künstlichen Intelligenz,
-angelehnt ist. Die aufwendigste Operation bei diesem Ansatz ist die
-Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu einem
-Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
+Non-Determinism} (END) nannte~\cite{J1995}. Dabei handelt es sich nicht um
+einen \emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden,
+sondern um eine verteilte, probabilistische Breitensuche, die an die
+\emph{Strahlsuche} (englisch: \textit{beam search}), ein Verfahren der
+Künstlichen Intelligenz, angelehnt ist. Die aufwendigste Operation bei diesem
+Ansatz ist die Bewertungsfunktion, die abschätzt, wie viele Komparatoren zu
+einem Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
Bekannten (Abbildung~\ref{fig:13-juille}).
Übersicht über bekannte konstruktive Sortiernetzwerke.
+\todo{Einleitungssatz}
+
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
\label{fig:odd-even-transposition-08}
\end{figure}
-Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe
+Dass das Odd-Even-Transpositionsort-Netzwerk tatsächlich jede beliebige
Eingabe sortiert ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt. Beim
-Odd-Even-Transporitionsort-Netzwerk mit drei Eingängen,
+Odd-Even-Transpositionsort-Netzwerk mit drei Eingängen,
$\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert.
Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
Herausschneiden einer Leitung aus $\operatorname{OET}(8)$.
-Das Odd-Even-Transporitionsort-Netzwerk ist weder in Bezug auf die Anzahl der
+Das 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
Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser
-\emph{„bitoner Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein
+\emph{„bitone Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein
verleiht dem Sortiernetzwerk seinen Namen.
Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
-Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen
-Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige
-\emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone
-Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden
-Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton}
-zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts
-entstehen können. Die wichtigsten Varianten für das \emph{bitone
-Mergesort-Netzwerk} zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
-und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
-eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen
-ist wichtig zu beachten, dass das letzte Element nicht größer
-(Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
-(Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
-darf.
+Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen
+Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine
+beliebige \emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine
+\emph{bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton
+absteigenden Folge, oder ein zyklischer Shift davon.
+Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten
+die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das
+\emph{bitone Mergesort}-Netzwerk zeigen die
+Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie
+erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste
+aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass
+das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw.
+kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge
+sein darf.
\begin{figure}
\centering
lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
„echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
-Schema des bitonen Mischers für zwei aufsteigend sortierte Foglen. Durch das
+Schema des bitonen Mischers für zwei aufsteigend sortierte Folgen. Durch das
Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
Statt an eine Treppe erinnert das Muster nun an einen Trichter.
\begin{center}
\input{images/batcher-8.tex}
\end{center}
- \caption{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk}
- für acht Eingänge. Markiert sind die beiden Instanzen von
- $\operatorname{BS}(4)$ (rot), die beiden bitonen
- Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten
+ \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht
+ Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden
+ bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten
rekursiven Schritt hinzugefügt wurden (grün).}
\label{fig:bitonic-08}
\end{figure}
Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
Schichten angeordnet sind.
-%\begin{figure}
-%\begin{center}
-%\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
-%\end{center}
-%\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
-%$S(n/2)$ und dem Mischer $M(n)$.}
-%\label{fig:bms_rekursiver_aufbau}
-%\end{figure}
-
\subsection{Das Odd-Even-Mergesort-Netzwerk}
Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
-\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
+\subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer}
-Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein
-Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$
+Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein
+Komparatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$
Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
\emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
-vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter
+vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even}-Mischer unter
Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH}
-Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
+Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die
Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
\end{center}
\caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
- aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
+ aus. Der Effekt wird durch den rekursiven Aufbau noch verstärkt.}
\label{fig:oe-merge}
\end{figure}
Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
-rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
+rekursiv von kleineren \emph{Odd-Even}-Mischern zusammengefügt, so dass sich am
Ausgang der Mischer die Folgen
\begin{eqnarray}
W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
\begin{equation}
w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
\end{equation}
-die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
-Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
+die die Folge~$W$ sortieren. Den schematischen Aufbau des
+\emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}.
Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
-wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthählt als
+wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält als
$W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte
Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind
\qquad
\subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
\caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
- kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
+ kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der
Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
sortiert ist.}
Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie
das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von
-sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die
+sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die
effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
$\operatorname{OES}(n)$ aus
\end{center}
\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
- \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade
+ \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade
Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
Komparatoren zwischen benachbarten Leitungen (grün).}
\label{fig:odd-even-mergesort-08}
In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk
$\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven
Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den
-\emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind
+\emph{Odd-Even}-Mischer für acht Leitungen dar: Die beiden blauen Blöcke sind
die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
die Komparatoren, die in ersten Rekursionsschritt hinzugefügt werden.
Komprimierung durchgeführt werden.
\subsection{Normalisieren}
+\label{sect:normalisieren}
\begin{figure}
\centering
In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
-Richtung. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen-
+Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen-
und das Trichtermuster zu sehen.
\subsection{Zwei Netzwerke kombinieren}
neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun
Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten
benötigen. Kombiniert man zwei dieser Netzwerke mit dem
-\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das
+\emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit 18~Eingängen, das
80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt
82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so
schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Sherenaz~W.
Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber
6~Komparatoren weniger.
-% 9 9
-% 9 18
-% 9 27
-% 9 36
-% 9 45
-% 8 53
-% 8 61
-% 7 68
-% 7 75
-% 6 81
-% 5 86
-
Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
nur mit exponentiellem Aufwand möglich ist.
-%\begin{itemize}
-%\item Mit dem Bitonic-Merge
-%\item Mit dem Odd-Even-Merge
-%\item Nach dem Pairwise sorting-network Schema.
-%\end{itemize}
-
\subsection{Leitungen entfernen}
\label{sect:leitungen_entfernen}
Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
„eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem
-bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim
-durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der
-„Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index.
-Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche
-dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden
-Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
+bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das
+Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an
+einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten
+Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und
+welche dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum
+jeden Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
das {\em Odd-Even-Transpositionsort-Netzwerk}.
\begin{figure}
\centering
- \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
- \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
- \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
- \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
+ \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
+ durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
+ \subfigure[Komparatoren, die einen Wechsel der Leitungen bewirken, werden
+ durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
+ \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit
+ 7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
+ \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die
+ Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
\caption{Eine Leitung wird aus dem
- \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(8)$ entfernt:
- Auf der rot markierten Leitung wird $\infty$ angelegt. Da der Wert bei jedem
- Komparator am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die
- restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
- Pfad herausgetrennt werden. In der letzten Abbildung ist
- $\operatorname{OET}(7)$ markiert.}
+ \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
+ markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
+ am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die restlichen
+ Werte trotzdem noch richtig sortiert werden müssen, kann dieser Pfad
+ heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
\label{fig:oe-transposition-cut}
\end{figure}
(Abbildung~\ref{fig:oe-transposition-cut1}).
Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
-Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position
-des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die
-Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt.
-Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme
+Komparatornetzwerk immer noch sortiert werden: Wir haben lediglich die
+Position des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss
+die Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum
+liegt. Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme
auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
mit $(n-1)$~Elementen darstellen.
-Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen
-(Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für
-$(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein
-Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als
-\emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}.
+Wenn man die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
+Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das
+Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung
+ein Minimum oder ein Maximum angenommen wird, bezeichnen wir das eliminieren
+einer Leitung als \emph{Minimum-Schnitt} beziehungsweise
+\emph{Maximum-Schnitt}.
Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
-Darstellung ergibt. Ausserdem ist das
-{\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
-zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
-Ausgabe und kann entfernt werden.
+Darstellung ergibt. Außerdem ist das
+\emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
+zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
+kann entfernt werden.
+
+Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig
+\emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen
+\emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu
+\emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben.
\subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
\label{sect:anzahl_schnittmuster}
Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und
-Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke
-mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die
+Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
+$n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die
nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
\emph{$k$-Schnittmuster}.
\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
-vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert,
-die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die
-Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von
-Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen
-Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl
-der möglichen Schnittmuster:
+vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken.
+Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der
+so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der
+möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten,
+$k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/
+Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen
+Schnittmuster:
\begin{displaymath}
2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
= 2^{k} \cdot \frac{n!}{k! (n-k)!}
Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
-ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit
+ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schnittmuster mit
16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$
Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große
Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich.
Werte unterscheiden.
Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
-Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des
+Ausgangsmuster abgebildet, weil die Position des Minimums beziehungsweise des
Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
$\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
- \emph{Odd-Even-Mergesort-Netzwerk}, 4973 für das \emph{bitone
- Mergesort-Netzwerk} und 18764 für das \emph{Pairwise-Sorting-Netzwerk}.}
+ \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone
+ Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.}
\label{fig:count-cuts-16}
\end{figure}
Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen
Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen}
Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des
-\emph{Odd-Even-Mergesort-Netzwerks}, 4973 ($\approx 0,15\%$) beim
-\emph{bitonen Mergesort-Netzwerk} und 18764 ($\approx 0,57\%$) beim
-\emph{Pairwise-Sorting-Netzwerk}. Zwar ist es möglich, dass mehr Iterationen
+\emph{Odd-Even-Mergesort}-Netzwerks, 4973 ($\approx 0,15\%$) beim
+\emph{bitonen Mergesort}-Netzwerk und 18764 ($\approx 0,57\%$) beim
+\emph{Pairwise-Sorting}-Netzwerk. Zwar ist es möglich, dass mehr Iterationen
die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen
in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass
die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
können, kann man sich einer stochastischen Methode bedienen, der sogenannten
-\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
+\emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für
+schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von
$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$
enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der
-unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
+unterschiedlichen Schnittmuster insgesamt entspricht, kann man die Anzahl der
unterschiedlichen Schnittmuster abschätzen.
\begin{figure}
\begin{center}
\includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
\end{center}
- \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
\emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
$\operatorname{BS}(32)$.}
\label{fig:collisions-10000-1000000-32}
\begin{center}
\includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
\end{center}
- \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der
+ \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
\emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem
kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen
Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
-$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen
+$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedlichen
Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
sind. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
-vorherigen Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als
+vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als
die Anzahl der \emph{möglichen} Schnittmuster.
\newpage
\section{Der \textsc{SN-Evolution}-Algorithmus}
+\label{sect:sn-evolution}
Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
\subsection{Bewertungsfunktion}\label{sect:bewertung}
Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
-{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
+{\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
die bei Sortiernetzwerken verfolgt werden können:
\begin{itemize}
\item Möglichst wenige Komparatoren („effizient“)
Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
Pseudocode wie folgt beschreiben:
\begin{verbatim}
-Gütesumme := 0
-Auswahl := (leer)
-
-für jedes Individuum in Population
-{
- reziproke Güte := 1.0 / Guete(Individuum)
- Wahrscheinlichkeit P := reziproke Güte / (reziproke Güte + Gütesumme)
- Gütesumme := Gütesumme + reziproke Güte
-
- mit Wahrscheinlichkeit P
+ Gütesumme := 0
+ Auswahl := (leer)
+
+ für jedes Individuum in Population
{
- Auswahl := Individuum
+ reziproke Güte := 1.0 / Guete(Individuum)
+ Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
+ Gütesumme := Gütesumme + reziproke Güte
+
+ mit Wahrscheinlichkeit P
+ {
+ Auswahl := Individuum
+ }
}
-}
-gib Auswahl zurück
+ gib Auswahl zurück
\end{verbatim}
\subsection{Rekombination}
Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
-{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
+\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
-Anschließend entfernen wir zufällig $n$~Leitungen wie in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
+Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
-erhält.
+erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
+Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass
+nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können.
\subsection{Mutation}
wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende
Netzwerk die Sortiereigenschaft noch besitzt.
-Trotz des hohen Rechenaufwandes -- bei 16-Sortiernetzwerken sind gut
+Trotz des hohen Rechenaufwands -- bei 16-Sortiernetzwerken sind gut
4~Millionen Tests notwendig, um alle Komparatoren zu überprüfen -- waren die
Ergebnisse ernüchternd: Nach circa 1~Million Iterationen mit
16-Sortiernetzwerken fand der so modifizierte Algorithmus keinen einzigen
Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus
wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale
Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist
-als das bitone Mergesort-Netzwerk: $\operatorname{BS}(16)$ benötigt
-80~Komparatoren, das Sortiernetzwerk in
-Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt lediglich~67.
+als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren,
+das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt
+lediglich~67.
-\subsection{Versuche mit dem Odd-Even-Mischer}
+\subsection{Versuche mit dem \emph{Odd-Even}-Mischer}
\begin{figure}
\begin{center}
\end{center}
\caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
10~Schichten. Das Netzwerk wurde von dem Algorithmus
- \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even-Mischers}
+ \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers
erzeugt.}
\label{fig:16-e1-oddeven-1296543330}
\end{figure}
Leider lies sich das Ergebnis des bitonen Mischers -- das von
\textsc{SN-Evolution} ausgegebene Netzwerk war effizienter als das rekursiv
aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem
-\emph{Odd-Even-Mischer} nicht wiederholen. Zwar erreichen die
+\emph{Odd-Even}-Mischer nicht wiederholen. Zwar erreichen die
Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
-\emph{Odd-Even-Mischers} findet, das \emph{Odd-Even-Mergesort}-Netzwerk
+\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk
bezüglich Schnelligkeit und Effizienz, ein Beispiel hierfür ist in
Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Ein Netzwerk, das
$\operatorname{OES}(n)$ in mindestens einem Merkmal übertrifft, konnte jedoch
nicht beobachtet werden.
-\begin{itemize}
-\item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der Schichten, kombiniert)
-\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \emph{Mischer} ab.
-\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.
-\item Möglicherweise: Verwende den rekursiven Aufbau des \emph{Pairwise-Sorting}-Netzwerks um Sortiernetzwerke zu mergen.
-\end{itemize}
-
%\begin{figure}
%\begin{center}
%\input{images/08-e2-1237993371.tex}
Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
gute Schnittmuster gesucht.
-Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster},
-die in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als
-Individuen. Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte
-des einen Schnittmusters verwendet und die letzten ${c-r}$~Schnitte des
-zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
+in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
+Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte des einen
+Schnittmusters verwendet und die letzten ${c-r}$~Schnitte des zweiten
+Schmittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
-Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
-auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
+Die Mutation setzt entweder die Leitungsnummer eines Schnitts~$i$ zufällig auf
+einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
Schnitt-Richtung.
\subsection{Versuche mit dem bitonen Mergesort-Netzwerk}
-In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
+\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
Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger
-als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers
-Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$
-Komparatoren ein.
+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.
\begin{figure}
\begin{center}
\label{fig:32-ec-from-bs64}
\end{figure}
-Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen
+Das Ergebnis von \textit{Mühlenthaler} und \textit{Wanka}, die den bitonen
Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk
konstruiert haben, kann demnach auch erreicht werden, wenn
$\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen
unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
gute Schnittmuster anzugeben.
-Entscheidend für das Ergebnis eines Schnittmusters scheint beim bitonen
-Mergesort-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
+Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
+Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
+\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}
+
+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.
+Abbildung~\ref{fig:23-ec-from-bs46} zeigt beispielhaft ein
+23-Sortiernetzwerk, das aus \bs{46} generiert wurde.
+\begin{center}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
+ & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} &
+ \bs{n} \\
+\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 \\
+\hline
+\end{tabular}
+\end{center}
+
+\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}
+\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
$m$~Schnitten gestartet, so ist das beste Ergebnis immer das
$\operatorname{OET}(n-m)$-Netzwerk.
-\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}
-
\subsection{Versuche mit dem Pairwise-Sorting-Netzwerk}
Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
-Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
+\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 der
$\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 Sortiernetzerke, die
-strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die
+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}
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 Verwandschaft von $\operatorname{PS}(n)$ und \oes{n}
+konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
\subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
\emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen
16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es
wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
-$\operatorname{OES}(32)$ sehr schnell ein gutes 16-Schnittmuster findet.
-
-Eines der eher zufälligen Schnittmuster ist $\operatorname{MIN}(1, 6, 11, 14,
-17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8, 13, 18, 21, 27, 31)$. Das
-Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht,
-das resultierende Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
+$\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese
+Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine
+Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes
+16-Schnittmuster findet.
+
+Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
+bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
+$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
+8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
+Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
+Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
\begin{figure}
\begin{center}
\label{fig:16-ec-from-oes32}
\end{figure}
+Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
+4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
+Beobachtung kann man das regelmäßige Schnittmuster
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
+ -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
+Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
+Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
+32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
+ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-ec-from-oes64.tex}
+ \end{center}
+ \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten.
+ Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
+ \label{fig:32-ec-from-oes64}
+\end{figure}
+
+Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
+erzeugten Sortiernetzwerke die Effizienz des
+\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
+beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
+43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
+beider Sortiernetzwerke ist mit 10~Schichten identisch.
+
+Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
+und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
+verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
+Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
+22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
+Abbildung~\ref{12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
+Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
+werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
+gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
+werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
+16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
+dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
+sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
+angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so
+effizient wie \oes{12} ist, dafür aber schneller als \oes{12} und \bs{12}.
+
+\begin{figure}
+ \centering
+ \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
+ das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
+ generiert
+ wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
+ \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
+ 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Odd-Even-Mergesort}-Netzwerk generiert
+ wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
+ \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
+ Ergebnis von der Bewertungsfunktion ab.}
+ \label{fig:12-ec-from-oes24}
+\end{figure}
+
+Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
+findet Sortiernetzwerke, die schneller sind als das entsprechende
+\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das
+\emph{Odd-Even-Mergesort}-Netzwerk mit 22, 24, 38, 40, 42, 44 und 46
+Eingängen. In der folgenden Tabelle sind einige schnelle Netzwerke, die von
+\textsc{SN-Evolution-Cut} generiert werden können, charakterisiert. Die
+Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
+\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
+Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
+23-Sortiernetzwerk, das aus \oes{46} generiert wurde.
+\begin{center}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
+(Resultat) & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
+\hline
+11 & 38 & 9 & 37 & 10 \\
+12 & 43 & 9 & 41 & 10 \\
+19 & 93 & 13 & 91 & 14 \\
+20 & 101 & 13 & 97 & 14 \\
+21 & 108 & 14 & 107 & 15 \\
+22 & 116 & 14 & 114 & 15 \\
+23 & 125 & 14 & 122 & 15 \\
+\hline
+\end{tabular}
+\end{center}
+
+\begin{figure}
+ \begin{center}
+ \input{images/23-ec-from-oes46-fast.tex}
+ \end{center}
+ \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten.
+ Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
+ Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
+ 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
+ erzeugt.}
+ \label{fig:23-ec-from-oes46}
+\end{figure}
+
\newpage
\section{Der \textsc{SN-Markov}-Algorithmus}
\label{sect:markov}
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 20000, bei den untersuchten 32-Sortiernetzwerken
-wurden jedoch bereits bis zu $2,6 \cdot 10^8$ unterschiedliche Schnittmuster
-geschätzt.
+Nachfolger zwar noch unter 20.000, bei den untersuchten
+32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$
+unterschiedliche Schnittmuster geschätzt.
Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
Algorithmus wie folgt beschreiben:
\begin{verbatim}
-Netzwerk := Eingabe
-
-für n Iterationen
-{
- Nachfolger := kombiniere (Netzwerk, Netzwerk)
- Netzwerk := Nachfolger
-}
-
-gib Netzwerk zurück
+ Netzwerk := Eingabe
+
+ für n Iterationen
+ {
+ Nachfolger := kombiniere (Netzwerk, Netzwerk)
+ Netzwerk := Nachfolger
+ }
+
+ gib Netzwerk zurück
\end{verbatim}
-\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}
-
-
-\begin{itemize}
- \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
- \item Anzahl der erreichbaren Sortiernetzwerke.
- \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
- Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
-\end{itemize}
+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 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 in Abbildung~\ref{fig:markov-comparators}
+eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
+Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
+um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
+Beispielsweise war die kleinste erreichte Komparatorzahl bei
+16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$
+gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$
+und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem
+Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
+unter den Graphen angegeben.
\begin{figure}
- \begin{center}
- \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-12-pct.pdf}
- \end{center}
- \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen),
- die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
- \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.}
- \label{fig:markov-comparators-12}
+ \centering
+ \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}}
+ \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}}
+ \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}}
+ \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}}
+ \caption{Anzahl der Komparatoren von Sortiernetzwerken,
+ die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet
+ ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der
+ gemessenen Daten darstellt.}
+ \label{fig:markov-comparators}
\end{figure}
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf}
+ \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.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}
+ \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}
-\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}
+Dass der \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
+\textsc{SN-Evolution}-Algo\-rithmus, ist aus dem Graphen in
+Abbildung~\ref{fig:comparison-comparators} ersichtlich. Analog zu dem Versuch
+mit \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die
+Anzahl der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
+Startnetzwerk diente bei beiden Algorithmen das
+\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
+x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
+ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
+wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden außerdem nach
+dem verwendeten Mischer-Netzwerk -- \oem{32} beziehungsweise \bm{32}.
+
+Sowohl der \textsc{SN-Markov}-Algorithmus, der das
+\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
+\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die
+bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind.
+Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger:
+Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit
+63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335
+\%$ rund 20~mal höher.
+
+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, traten auch jeweils ein
+Sortiernetzwerk mit 121 und 124~Komparatoren auf. Da Sortiernetzwerke mit so
+vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
+Iterationen nicht noch einmal erzeugt wurden, handelt es sich vermutlich um
+ein Phänomen, das mit der Initialisierung mit dem
+\emph{Odd-Even-Transpositionsort}-Netzwerk zusammenhängt.
-\begin{figure}
- \begin{center}
- \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-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-comparators-14-pct.pdf}
+% \end{center}
+% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
+% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+% \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.}
+% \label{fig:markov-comparators-14}
+%\end{figure}
+%
+%\begin{figure}
+% \begin{center}
+% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf}
+% \end{center}
+% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
+% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+% \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.}
+% \label{fig:markov-comparators-16}
+%\end{figure}
+%
+%\begin{figure}
+% \begin{center}
+% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf}
+% \end{center}
+% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen),
+% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
+% \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.}
+% \label{fig:markov-comparators-18}
+%\end{figure}
-\newpage
-\section{Empirische Beobachtungen}
+%\begin{figure}
+% \begin{center}
+% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
+% \end{center}
+% \caption{Zyklen, die beim \textit{Random Walk} des
+% \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
+% Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
+% y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
+% Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
+% \label{fig:markov-cycles-16}
+%\end{figure}
+
+\todo{Schreibe noch etwas zu …}
\begin{itemize}
-\item So schnell konvergiert der Algorithmus.
-\item $\ldots$
+ \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
+ \item Anzahl der erreichbaren Sortiernetzwerke.
+ \item \textsc{SN-Count-Markov} (ggf)
\end{itemize}
\newpage
-\section{Ausblick}
+\section{Fazit und Ausblick}
-Das würde mir noch einfallen$\ldots$
+\todo{Ausformulieren}
+\begin{itemize}
+\item Mit \textsc{SN-Evolution} und \oem{n} kann man nicht besser werden als
+ \oes{n}.
+\item Mit \textsc{SN-Evolution} und \bm{n} kann man besser werden als \bs{n}.
+\item Vermutlich kann man mit \textsc{SN-Evolution} und \bm{n} so gut werden
+wie \textsc{SN-Evolution-Cut}, wenn er mit \bs{2n} gestartet wird.
+\item Leider sind keine konstruktiven Methoden erkannt worden.
+\end{itemize}
-- SN-Evolution mit Pairwise als „Mischer“.
-- Co-Evolution von Netzwerken und Schnittmustern.
+Die Möglichkeiten, die Evolutionäre Algorithmen bei der Optimierung von
+Sortiernetzwerken bieten, sind durch die in dieser Arbeit vorgestellten
+Herangehensweisen bei weitem nicht erschöpft.
+
+Im Folgenden werden Ansätze umrissen, mit denen an die Untersuchungen in
+dieser Arbeit nahtlos angeknöpft werden könnte.
+
+\subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}
+
+Die aktuelle Implementierung von \textsc{SN-Evolution}
+(Abschnitt~\ref{sect:sn-evolution}) kann sowohl den \emph{bitonen Mischer} als
+auch den \emph{Odd-Even}-Mischer verwenden, um zwei Individuen zu
+rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen
+Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich
+selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von
+$\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
+die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
+Ausgaben sorgen. Anstelle von $\ps{\frac{n}{2}}$ kann man natürlich beliebige
+Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwenden.
+
+Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
+rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
+\emph{unterschiedliche} Schnittmuster gibt
+(Abschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
+Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider
+wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine
+$n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren
+$n$-Sortiernetzwerken als \ps{n} führen.
+
+\subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}}
+
+Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
+in~\cite{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution}
+und \textsc{SN-Evolution-Cut} versuchen zu kombinieren. Nach dem Zusammenfügen
+von zwei $n$-Sortiernetzwerken könnte der Algorithmus
+\textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
+\emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
+Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
+verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut}
+die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern.
+
+Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} --
+eine zweite Population von Schnittmustern evolvieren, die für die
+Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut
+funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge
+Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten
+Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster
+eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses}
+Schnittmuster zur nächsten Generation beiträgt. Im Gegensatz zum Ansatz der
+parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die
+das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern
+könnte.
\newpage
\section{Implementierung}
Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet
werden:
\begin{verbatim}
-$ sn-bitonicsort 18 | sn-normalize >sn-18
+ $ sn-bitonicsort 18 | sn-normalize >sn-18
\end{verbatim}
Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
es einfach zu ermöglichen, Programme zu verketten, ist eines der
Komparatornetzwerks auf eine Eingabe-Permutation.
\textit{libsortnetwork} kann unter der Web-Adresse
-\url{http://octo.it/libsortnetwork/} unentgeldlich heruntergeladen werden.
+\url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden.
\newpage
\bibliography{references}
\end{document}
-% vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 :
+% vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 spelllang=de :