\usepackage{listings}
\usepackage{graphicx}
\usepackage{url}
+\usepackage[table]{xcolor}
%\usepackage{longtable}
\usepackage{subfigure}
\usepackage{icomma}
\newcommand{\todo}[1]{{\bf TODO:} #1}
\newcommand{\qed}{\hfill $\Box$ \par \bigskip}
-\newcommand{\oes}[1]{\ensuremath{\operatorname{OES}(#1)}}
-\newcommand{\bs}[1]{\ensuremath{\operatorname{BS}(#1)}}
-\newcommand{\ps}[1]{\ensuremath{\operatorname{PS}(#1)}}
-\newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}(#1)}}
-\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}(#1)}}
+\newcommand{\oes}[1]{\ensuremath{\operatorname{OES}\left(#1\right)}}
+\newcommand{\bs}[1]{\ensuremath{\operatorname{BS}\left(#1\right)}}
+\newcommand{\ps}[1]{\ensuremath{\operatorname{PS}\left(#1\right)}}
+\newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}\left(#1\right)}}
+\newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
+\newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}
+
+\newcommand{\gcell}{\cellcolor{green!10}}
+\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}}
\newtheorem{definition}{Definition}
\newtheorem{satz}{Satz}
\maketitle
\begin{abstract}
-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.
-Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
-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.}
+Sortiernetzwerke erweisen sich als sehr schwieriges Optimierungsproblem. Zwar
+ist das Konzept leicht verständlich und schnell erklärt, effiziente und
+schnelle Sortiernetzwerke zu finden oder zu konstruieren bleibt aber eine
+Herausforderung.
+
+Diese Arbeit verwendet „Schnitte“ oder „Leitungselimination“ und
+Mischer-Netz\-werke, um evolutionäre Algorithmen anzugeben, deren Individuen
+die Menge der gültigen Sortiernetzwerke nie verlassen. Bisherige Ansätze
+bewegten sich in der Regel in der Menge aller Komparatornetzwerke und suchten
+dort nach Sortiernetzwerken. Nach dem Vorstellen der zwei Algorithmen
+\textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} sowie einiger Ergebnisse,
+die mit diesen Algorithmen erzielt werden konnten, wird -- basierend auf dem
+evolutionären Algorithmus \textsc{SN-Evolution} -- eine Markov-Kette für
+Sortiernetzwerke angegeben.
\end{abstract}
\newpage
+\section*{Eidesstattliche Erklärung}
+
+Ich versichere, dass ich die vorliegende wissenschaftliche Arbeit
+selbstständig verfasst und keine anderen als die angegebenen Hilfsmittel
+verwendet habe. Die Stellen der Arbeit, die anderen Werken dem Wortlaut oder
+dem Sinn nach entnommen sind, wurden unter Angabe der Quelle als Entlehnung
+deutlich gemacht. Das Gleiche gilt auch für beigegebene Skizzen und
+Darstellungen. Diese Arbeit hat in gleicher oder ähnlicher Form meines Wissene
+nach noch keiner Prüfungsbehörde vorgelegen.
+\\[3cm]
+München, den 20.~März 2011,\\
+\\[1cm]
+Florian Forster
+\newpage
+
\tableofcontents
\newpage
\subsection{Motivation}\label{sect:motivation}
-\todo{Schreibe noch etwas zu …}
-\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
+gefundene Konstruktionsvorschriften.
+
+Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon wiederholt
+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}
zugrunde liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten
können und zwei Ausgänge, auf denen die Zahlen wieder ausgegeben werden. Dabei
sind die Ausgänge im Gegensatz zu den Eingängen unterscheidbar, da die größere
-der beiden Zahlen wird immer auf dem einen, die kleinere der beiden Zahlen
-immer auf dem anderen Ausgang ausgegeben ausgegeben wird.
+der beiden Zahlen immer auf dem einen, die kleinere der beiden Zahlen
+immer auf dem anderen Ausgang ausgegeben wird.
-Kombiniert man mehrere \emph{Komparatoren} miteinander, das heißt, dass die
+Kombiniert man mehrere \emph{Komparatoren} in der Form miteinander, dass die
Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind,
erhält man ein {\em Komparatornetzwerk}.
\begin{figure}
-\begin{center}
-\input{images/einfaches_komparatornetzwerk.tex}
-\end{center}
-\caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend
-aus 5~Komparatoren.}
-\label{fig:einfaches_komparatornetzwerk}
+ \begin{center}
+ \input{images/einfaches_komparatornetzwerk.tex}
+ \end{center}
+ \caption{Einfaches Komparatornetzwerk mit 4~Ein- beziehungsweise Ausgängen,
+ bestehend aus 5~Komparatoren.}
+ \label{fig:einfaches_komparatornetzwerk}
\end{figure}
Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
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.
-
-Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
-gleichzeitig angewandt werden. Das Beispiel in
+befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat. Wenn in
+einem Komparatornetzwerk alle Komparatoren in die gleiche Richtung zeigen --
+die Konvention in dieser Arbeit ist, dass das Minimum auf der unteren Leitung
+ausgegeben wird -- werden die Pfeile durch einfache Linien ersetzt. Zu diesen
+sogenannten \emph{Standard-Netzwerken} siehe auch
+Abschnitt~\ref{sect:normalisieren}.
+
+Komparatoren, die \emph{unterschiedliche} Leitungen miteinander vergleichen,
+können gleichzeitig angewendet werden. Das Beispiel in
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{Geschwindigkeit} 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.
\begin{center}
\input{images/09-e2-c24-allbut1.tex}
\end{center}
- \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
- 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
- alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
+ \caption{Ein \emph{Komparatornetzwerk} mit 9~Eingängen und 24~Komparatoren,
+ die in 8~Schichten angeordnet sind. Das Netzwerk sortiert alle Eingaben, bei
+ denen das Minimum nicht auf dem mittleren Eingang liegt.}
\label{fig:09-e2-c24-allbut1}
\end{figure}
Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich. Das
Komparatornetzwerk wird auf das Gegenbeispiel angewendet und anschließend wird
-überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht heißt das, dass es
+überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht, heißt das, dass es
mindestens eine Eingabefolge gibt, die nicht sortiert wird. Entsprechend der
Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich
\emph{nicht} um ein \emph{Sortiernetzwerk}. Ein solches Gegenbeispiel für ein
gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
-nicht \emph{effizient} möglich.
+nicht \emph{effizient}\footnote{In diesem Zusammenhang heißt \emph{effizient},
+dass keine Algorithmen bekannt sind, die eine polynomielle Laufzeit (in
+Abhängigkeit von der Eingabelänge) haben.} möglich.
Beispielsweise sortiert das im Rahmen dieser Arbeit entdeckte
Komparatornetzwerk in Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880
Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
-über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
-Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
+so schnell, dass ein Ausprobieren aller möglichen Permutationen schon bei
+16~Leitungen praktisch nicht mehr zu bewerkstelligen
ist.\footnote{1.307.674.368.000 Permutationen}
\label{sect:0-1-prinzip}
1 & e_j > a_i
\end{array} \right.
\end{displaymath}
-auf eine 0-1-Folge abgebildet werden, die entsprechen der Annahme vom
+auf eine 0-1-Folge abgebildet werden, die entsprechend der Annahme vom
Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine
Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
-zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$
-oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei
-gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich
-der Komparator so verhält, wie er sich bei der Permutation verhalten hat --
-ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$
-und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im
-Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.
-
-Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
-Komplexitätsklasse
-$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
-ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$
-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,
-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
-beschäftigen.
+zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als
+$a_i$, beziehungsweise zwei Zahlen größer oder gleich $a_i$. Da im Fall der
+0-1-Folge zwei gleiche Zahlen am Komparator anliegen, dürfen wir davon
+ausgehen, dass sich der Komparator so verhält, wie er sich bei der Permutation
+verhalten hat -- ohne das Ergebnis zu beeinflussen. Entsprechend müssen an den
+Ausgängen $i-1$ und $i$ eine Null und eine Eins in der falschen Reihenfolge
+ankommen. Das steht im Widerspruch zu der Annahme, dass alle 0-1-Folgen
+sortiert werden.
+
+Im Gegensatz zum Überprüfen aller möglichen Permutationen, was mit dem Aufwand
+$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ verbunden ist, besitzt
+das Überprüfen aller 0-1-Folgen „nur“ den Aufwand $\Theta(2^n)$. 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, 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~Milliarden Tests notwendig, die einen Rechner durchaus
+mehrere Stunden beschäftigen. Das ist deshalb problematisch, weil die im
+Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
+Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
+Zwischenergebnisses drei Stunden in Anspruch nimmt, sind für eine Million
+Iterationen etwa 340~Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, wird etwa ein Monat für
+einen Lauf benötigt.
\subsubsection{Evolutionäre Algorithmen}
Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
-\textit{NP}, das heißt das keine Verfahren bekannt sind, die das Problem
-effizient exakt lösbar. Sollte sich herausstellen, dass diese Probleme nicht
-in der Komplexitätsklasse~\textit{P} liegen, wäre eine Konsequenz, dass es
-effiziente exakte Algorithmen für diese Probleme nicht geben kann. Falls sich
-hingegen herausstellt, dass diese Probleme in der
-Komplexitätsklasse~\textit{P} liegen, wird es mit großer Wahrscheinlichkeit
-noch einige Zeit dauern, bis auch Algorithmen mit praktikablen Zeitkonstanten
-gefunden werden.
-
-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.
-
-Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
+$\mathcal{NP}$-vollständig. Das heißt, dass keine Verfahren bekannt sind, die
+diese Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese
+Probleme außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine
+Konsequenz, dass es für diese Probleme keine effizienten exakten Algorithmen
+gibt. Stellt sich hingegen heraus, dass diese Probleme neben
+$\mathcal{NP}$-vollständig auch in der Komplexitätsklasse~\textit{P} liegen,
+gibt es effiziente Algorithmen. Es ist jedoch wahrscheinlich, dass die
+Zeitkonstanten solcher Algorithmen sehr groß wären, so dass der praktische
+Nutzen fraglich bleibt.
+
+Aus diesem Grund besteht die Notwendigkeit, einen Kompromiss einzugehen: Statt
+die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen Lösungen}
+als einzige Ausgabe des Algorithmus zuzulassen, wird eine "`möglichst gute"'
+Lösung ausgegeben. Dafür verringert sich die Laufzeit des Algorithmus. 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.
+
+Bei {\em Evolutionären Algorithmen} stand die Evolution Pate. Die Grundidee
ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em
Individuen} bezeichnet.
-Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
+Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben: Aus einer
bestehenden Lösungsmenge, der {\em Population}, werden zufällig Lösungen
ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
Gütefunktion}.
-Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
+Nicht alle Probleme eignen sich für diese Strategie. Zum einen muss es möglich
sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
-es oft einfach ist {\em irgendeine} Lösung anzugeben. Die angegebenen
-Algorithmen verwenden als einfache, initiale Lösung häufig das
+es oft einfach ist, {\em irgendeine} Lösung anzugeben. Die angegebenen
+Algorithmen verwenden als einfache initiale Lösung häufig das
\emph{Odd-Even-Transpositionsort}-Netzwerk, das in
Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
-problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen.
+problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen. Die in
+dieser Arbeit verwendeten Rekombinationsmethoden sind so gewählt, dass die
+Nebenbedingungen nicht verletzt werden.
Beim Aussuchen von zufälligen Lösungen aus der Population, der
\emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
\textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
-findet er aber in der Regel bessere Lösungen.
+findet er aber in der Regel bessere Lösungen. Die Rolle, die
+\textit{Exploitation} und \textit{Exploration} bei evolutionären
+Optimierungsalgorithmen spielen, wird von \textit{Eiben} und
+\textit{Schippers} in~\cite{ES1998} untersucht.
Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
-zwischen verschiedenen Leitungszahlen stark unterscheiden.
+zwischen verschiedenen Leitungszahlen stark unterscheiden. Einen Überblick
+geben \textit{Kalyanmoy Deb} und \textit{Samir Agrawal} in~\cite{DA1998}.
-Die \textit{Exploration} kann von einem weiteren Mechanismus unterstützt
-werden, der ebenfalls der Evolutionslehre entliehen ist, der \emph{Mutation}.
-Dabei werden Lösungen zufällig verändert, so dass auch andere Lösungen „in der
-Nähe“ von direkten Nachfolgern erreicht werden können. Das hilft insbesondere
-bei der intensiven Suche in der Nähe eines lokalen Optimums aber auch beim
-„Ausbrechen“ und finden noch besserer Lösungen.
+Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
+unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
+\emph{Mutation}. Dabei werden Lösungen zufällig verändert, so dass auch andere
+Lösungen „in der Nähe“ von direkten Nachfolgern erreicht werden können. Das
+hilft insbesondere bei der intensiven Suche in der Nähe eines lokalen Optimums
+aber auch beim „Ausbrechen“ aus lokalen Optima und finden noch besserer
+Lösungen.
Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
verbunden, dass anschließend die Sortiereigenschaft des resultierenden
\emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
-Hinzufügen eines zufälligen Komparators diese Eigenschaft zerstören kann. Beim
-Suchen möglichst effizienter Netzwerke ist natürlich das zufällige Entfernen
-von Komparatoren interessanter, was die Sortiereigenschaft sehr oft aufhebt.
+Hinzufügen eines zufälligen Komparators diese Eigenschaft zer\-stö\-ren kann.
+Beim Suchen möglichst effizienter Netzwerke ist das zufällige Entfernen von
+Komparatoren interessanter, was die Sortiereigenschaft fast immer aufhebt.
Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
-die \emph{Sortiernetzwerke} selbst, sondern verzichten auf Mutation oder
-mutieren lediglich Transformationen von Sortiernetzwerken, die die
-Sortiereigenschaft erhält. Transformationen von Sortiernetzwerken werden in
-Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation
-einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
-
+die \emph{Sortiernetzwerke} selbst, sondern verzichten entweder ganz auf
+Mutation oder mutieren lediglich Transformationen von Sortiernetzwerken, die
+die Sortiereigenschaft erhalten. Transformationen von Sortiernetzwerken werden
+in Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der
+Mutation einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
\begin{figure}
\begin{center}
\input{images/16-hillis.tex}
\end{center}
- \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1992} angibt.
+ \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
Es besteht aus 61~Komparatoren in 11~Schichten.}
\label{fig:16-hillis}
\end{figure}
Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
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
-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
+zu optimieren~\cite{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
+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
gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
+\textit{Michael~L. Harrison} und \textit{James~A. Foster} nutzten ebenfalls
+\emph{Co-Evolution} in~\cite{HF2004}, um die Stabilität von Sortiernetzwerken
+zu erhöhen. Die zweite Population bestand aus \emph{Fehlern} -- der
+Information, welche Komparatoren defekt, beziehungsweise inaktiv sind. So
+generierte Sortiernetzwerke können auch dann noch für viele Eingaben eine
+korrekt sortierte Ausgabe erzeugen, wenn ein oder mehrere Komparatoren
+(zufällig) entfernt werden.
+
\begin{figure}
\centering
\subfigure{\input{images/13-juille-0.tex}}
\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 der \emph{Evolutionären Algorithmen}, 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}).
+bekannten (Abbildung~\ref{fig:13-juille}).
\newpage
-\section{Bekannte konstruktive Sortiernetzwerke}
+\section[Konstruktionsverfahren]{Konstruktionsverfahren für Sortiernetzwerke}
\label{sect:konstruktive_netzwerke}
-Übersicht über bekannte konstruktive Sortiernetzwerke.
-
-\todo{Einleitungssatz}
+Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere ein
+häufig verwendeter Baustein, sogenannte \emph{Mischer}\footnote{Eine
+Fehlübersetzung aus dem Englischen, von \textit{to~merge} (Deutsch:
+zusammenfügen). Da der Begriff des "`mischens"' beziehungsweise der
+"`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
+in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
+beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
+Eingabe. Im Folgenden werden daher drei Konstruktionsverfahren vorgestellt.
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
\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}
-Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe
-Eingabe sortiert ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
+Dass das \emph{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,
-$\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert.
+Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt.
Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
Herausschneiden einer Leitung reduziert. In
Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
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
-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. Andere Sortiernetzwerke benötigen deutlich weniger
-Komparatoren, beispielsweise $\mathcal{O}(n (\log n)^2)$, die in weniger
-Schichten, zum Beispiel $\mathcal{O}(\log n)$, angeordnet sind.
+Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. Die Rekursion endet
+beim \emph{Odd-Even-Transpositionsort}-Netzwerk mit drei Eingängen, bei dem
+das Minimum auf der untersten, das Maximum auf der obersten und der mittlere
+Wert auf der mittleren Leitung landet. Folglich ist die Ausgabe bei
+$\operatorname{OET}(3)$ sortiert.
+
+Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
+Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
+sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
+(n-1)} = \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.
Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
Algorithmen.
+Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer,
+beziehungsweise mehrerer Leitungen, um die Anzahl der Leitungen eines
+Sortiernetzwerks zu reduzieren. Die Technik wird in Detail im
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
+
\subsection{Das bitone Mergesort-Netzwerk}
Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
veröffentlicht wurde. Es ist deutlich effizienter als das
Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
-Komparatoren als auch bezüglich der benötigten Zeit, also der Anzahl der
-Schichten.
+Komparatoren als auch der benötigten Zeit, also der Anzahl der 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
+sortierte Listen zusammenfügen (Englisch: \textit{to~merge}) kann. Dieser
+\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
-Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
-Es ist jedoch möglich das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
+Instanzen des Netzwerks, deren Leitungszahl $n = 2^d$ eine Zweierpotenz ist.
+Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
-Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen
-Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige
-\emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone
-Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden
-Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton}
-zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts
-entstehen können. Die wichtigsten Varianten für das \emph{bitone
-Mergesort-Netzwerk} zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
-und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
-eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen
-ist wichtig zu beachten, dass das letzte Element nicht größer
-(Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
-(Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
-darf.
+Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen
+Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine
+beliebige \emph{bitone Folge} in eine sortierte Liste 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}) beziehungsweise
+kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge
+sein darf.
\begin{figure}
\centering
gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
> v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
-"`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der
-"`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass das Resultat in zwei bitone
-Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
+"`linken"' Folge $u_{m-1}$ kleiner ist als das kleinste Element der
+"`rechten"' Folge $v_{m-1}$. Daraus folgt, dass sich das Resultat in zwei
+bitone Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
-zeigt die Situationen vor und nach diesem Schritt des Mischers.
+zeigt die Situationen vor und nach diesem Schritt des Mischers schematisch.
Um die Folge vollständig zu sortieren, müssen anschließend die beiden
resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
definiert ist.
-Der bitonen Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
+Der bitone Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
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.
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}
Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
-zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe,
-$\operatorname{BS}(\frac{n}{2})$, für je die Hälfte der Eingänge, sowie dem
-bitonen Mischer für $n$~Leitungen, $\operatorname{BM}(n)$. Das Rekursionsende
-ist das bitone Mergesort-Netzwerk mit nur einer Leitung,
-$\operatorname{BS}(1)$, welches als leeres Komparatornetzwerk definiert ist.
-Entsprechend sind die Komparatornetzwerke $\operatorname{BM}(2)$ und
-$\operatorname{BS}(2)$ identisch.
+zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe
+$\bs{\frac{n}{2}}$ für je die Hälfte der Eingänge, sowie dem bitonen Mischer
+für $n$~Leitungen $\operatorname{BM}(n)$. Das Rekursionsende ist das bitone
+Mergesort-Netzwerk mit nur einer Leitung $\operatorname{BS}(1)$, welches als
+leeres Komparatornetzwerk definiert ist. Entsprechend sind die
+Komparatornetzwerke $\operatorname{BM}(2)$ und $\operatorname{BS}(2)$
+identisch.
Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
(Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
\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
- 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}
-Das konkrete Netzwerk~$\operatorname{BS}(8)$ ist in
+Das Sortiernetzwerk~$\operatorname{BS}(8)$ ist in
Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
grün hinterlegt.
-Das \emph{bitone Mergesort-Netzwerk} $\operatorname{BS}(8)$ besteht aus
-$\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$
-Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$
-Schichten angeordnet sind.
+Das \emph{bitone Mergesort}-Netzwerk mit einer Leitungszahl $n = 2^d$, die
+eine Zweierpotenz ist, besteht aus $\frac{1}{4} n \log(n) \log(n+1) =
+\Theta\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2}
+\log(n) \log(n+1) = \Theta(\log(n)^2)$ Schichten angeordnet sind.
\subsection{Das Odd-Even-Mergesort-Netzwerk}
-Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk}
-(OES) und das \emph{Odd-Even-Transpositionsort-Netzwerk} (siehe
+Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort}-Netzwerk
+(OES) und das \emph{Odd-Even-Transpositionsort}-Netzwerk (siehe
Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
-OES dem \emph{bitonen Mergesort-Netzwerk}, das im vorherigen Abschnitt
+OES dem \emph{bitonen Mergesort}-Netzwerk, das im vorherigen Abschnitt
vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
\textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
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, das 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
-Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH}
+vorgestellt wurde. Im allgemeinen Fall, wenn die Anzahl der Leitungen keine
+Zweierpotenz ist, kann das \emph{bitonic-Merge}-Netzwerk schneller sein
+als das \emph{Odd-Even-Merge}-Netzwerk.~\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
\begin{center}
\input{images/oe-merge.tex}
\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.}
+ \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}
V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
\end{eqnarray}
-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
-Ausgang der Mischer die Folgen
+Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$,
+beziehungsweise die ungeraden Folgen $U_{\textrm{ungerade}}$ und
+$V_{\textrm{ungerade}}$ werden 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) \\
W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \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 --
einzelnen Komparator.
\end{itemize}
-Dass die resultierende Folge sortiert ist, lässt sich mit dem
-{\em 0-1-Prinzip} zeigen:
-Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
-Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
-gleich der Anzahl der Nullen in den ungeraden Teilfolgen
-$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten
-sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
-$W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
+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
+ungeraden Teilfolgen $U_{\textrm{ungerade}}$ beziehungsweise
+$V_{\textrm{ungerade}}$ --~die Einsen verhalten sich entsprechend umgekehrt.
+Das trifft demnach auch auf die Folgen $W_{\textrm{gerade}}$ und
+$W_{\textrm{ungerade}}$ entsprechend zu:
\begin{eqnarray}
\left|W_{\textrm{gerade}}\right|_0
&=& \left|U_{\textrm{gerade}}\right|_0
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
+Ausgabe zu sortieren. Diese wird von den Komparatoren ausgeführt, die
+benachbarte Leitungen miteinander vergleichen. Die jeweiligen Situationen sind
in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
\begin{figure}
\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.}
\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
+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$.
Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
-allgemeinen Fall verwendet, ist Gemäß der rekursiven Definition in
-Abhängigkeit der Länge der Eingabefolgen, $n$ und $m$:
+allgemeinen Fall verwendet, hängt gemäß der rekursiven Definition von der
+Länge der Eingabefolgen, $n$ und $m$ ab:
\begin{displaymath}
K(n,m) = \left\{ \begin{array}{ll}
nm, & \mathrm{falls} \quad nm \leqq 1 \\
\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}$, lässt sich die Anzahl
-der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der erste
-Rekursionsschritt der OEM-Konstruktion fügt
+Für den wichtigen Spezialfall, dass $n = m = 2^{d-1}$ beträgt, lässt sich die
+Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
+erste Rekursionsschritt der OEM-Konstruktion fügt
$\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
-diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer,
+diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer
$\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
\frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
\end{displaymath}
Komparatoren eingespart. Damit ergibt sich
\begin{displaymath}
- K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
+ K\left(n = 2^{d-1}, n = 2^{d-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
\end{displaymath}
-für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
+für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^d)$
benötigt werden.
\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
-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
+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
effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
-$\operatorname{OES}(n)$ aus
-$\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$,
-$\operatorname{OES}\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$
-und $\operatorname{OEM}\left(\left\lceil\frac{n}{2}\right\rceil,
-\left\lfloor\frac{n}{2}\right\rfloor\right)$. Die Rekursion endet mit
-$\operatorname{OES}(1)$ und $\operatorname{OES}(0)$, die als leere
-Komparatornetzwerke definiert sind.
+\oes{n} aus $\oes{\left\lceil\frac{n}{2}\right\rceil}$,
+$\oes{\left\lfloor\frac{n}{2}\right\rfloor}$ und
+$\oem{\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor}$.
+Die Rekursion endet mit $\operatorname{OES}(1)$ und $\operatorname{OES}(0)$,
+die als leere Komparatornetzwerke definiert sind.
\begin{figure}
\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
+ \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}
\end{figure}
-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
+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 8~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.
+die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.
Im Allgemeinen ist die Anzahl der Komparatoren, die vom
\emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der
-Definition beziehungsweise der Konstruktionsanleitung abzulesen:
+Definition, beziehungsweise der Konstruktionsanleitung abzulesen:
\begin{displaymath}
k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
+ k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
+ K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
\end{displaymath}
-Eine geschlossene Form dieser Formel ist schon alleine deshalb schwierig, weil
-sie für $K(n,m)$ schwierig anzugeben ist. Es ist allerdings bekannt, dass
-$k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist.
+Da es schwierig ist für $K(n,m)$ eine geschlossene Form anzugeben, ist eine
+geschlossene Darstellung von $k(n)$ ebenfalls nicht ohne weiteres möglich. Es
+ist allerdings bekannt, dass $k(n)$ in $\Theta\left(n \left(\log
+(n)\right)^2\right)$ enthalten ist.
-Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
+Für den wichtigen Spezialfall, dass $n = 2^d$ eine Zweierpotenz ist, kann die
Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
\begin{displaymath}
- k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
+ k(n = 2^d) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
\end{displaymath}
gilt.
-% gnuplot:
-% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
-% oem1(n) = oem(ceil(.5*n),floor(.5*n))
-% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
-
-%\begin{itemize}
-%\item Pairwise sorting-network
-%\end{itemize}
+%\subsection{Das Pairwise-Sorting-Netzwerk}
+%
+%Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
+%für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
+%Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
+%Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
+%\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
+%das \emph{Odd-Even-Mergesort}-Netzwerk.
\newpage
\section{Transformation von Sortiernetzwerken}
Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
gleichzeitig ausgewertet werden, wie bereits in
Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
-Transformationen, insbesondere das Entfernen einer Leitung, das in
-Abschnitt~\ref{sect:leitungen_entfernen} beschrieben wird, kann es vorkommen,
-dass die Komparatoren eines Sortiernetzwerks nicht mehr in der
-kleinstmöglichen Anzahl von \emph{Schichten} angeordnet sind. Unter
-\emph{Komprimierung} wird eine (Neu-)Gruppierung der Komparatoren verstanden,
-die jeden Komparator so früh wie möglich ausführt. So entsteht die
-kleinstmögliche Anzahl von \emph{Schichten}, in die sich ein Sortiernetzwerk
-unterteilen lässt.
+Transformationen, insbesondere das Entfernen einer Leitung wie in
+Abschnitt~\ref{sect:leitungen_entfernen} beschrieben, kann es vorkommen, dass
+die Komparatoren eines Sortiernetzwerks nicht mehr in der kleinstmöglichen
+Anzahl von \emph{Schichten} angeordnet sind. Unter \emph{Komprimierung} wird
+eine (Neu-)Gruppierung der Komparatoren verstanden, die jeden Komparator so
+früh wie möglich ausführt. So entsteht die kleinstmögliche Anzahl von
+\emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
Diese Anzahl ist insbesondere beim automatisierten Bewerten von
-Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
+Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:sn-evolution:bewertung}
beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
-Komparatoren später angewandt werden. Deshalb sollte vor einer Bewertung, die
+Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
Komprimierung durchgeführt werden.
\subsection{Normalisieren}
+\label{sect:normalisieren}
\begin{figure}
\centering
Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
-zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
-transformiert werden. Dazu gibt beispielsweise \emph{Donald~E. Knuth}
-in~\cite{KNUTH} einen Algorithmus an.
-
-Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
-bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
+zeigen.\footnote{Die Konvention in dieser Arbeit ist, dass in diesem Fall alle
+Pfeile nach unten zeigen. Das Minimum wird auf der untersten, das Maximum auf
+der obersten Leitung ausgegeben.} Jedes Sortiernetzwerk kann in eine
+normaliesierte Variante transformiert werden. Dazu gibt beispielsweise
+\emph{Donald~E. Knuth} in~\cite{KNUTH} einen Algorithmus an.
+
+Abbildung~\ref{fig:beispiel_normalisieren} stellt das \emph{bitone
+Mergesort}-Netzwerk in zwei Varianten dar. Abbildung~\ref{fig:bitonic-nonstd}
zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
-die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
-Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist.
-In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
-Definition.
+die untere und die obere Hälfte gegenläufig sortiert. Das heißt, dass nach
+drei Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert
+ist. In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der
+rekursiven Definition.
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-
+Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die selbe
+Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen-
und das Trichtermuster zu sehen.
\subsection{Zwei Netzwerke kombinieren}
zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
Sortiernetzwerk zusammenzufassen.
-Wir haben diese Technik in den vorangegangen Abschnitten bereits verwendet,
-beispielsweise um zwei \emph{bitone Mergesort-Netzwerke} mit jeweils der
+Diese Technik wurde in den vorangegangen Abschnitten bereits verwendet,
+beispielsweise um zwei \emph{bitone Mergesort}-Netzwerke mit jeweils der
halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
-\emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ wurde auf diese Art
+\emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ wurde auf diese Art
und Weise rekursiv aufgebaut.
Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
-Folgen. \emph{Wie} diese Folgen sortiert wurden, ist unerheblich. Entsprechend
+Folgen. \emph{Wie} diese Folgen sortiert wurden ist unerheblich. Entsprechend
können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
-zu sortieren, und die Ausgaben mit einem der beschriebenen Mischer
+zu sortieren und die Ausgaben mit einem der beschriebenen Mischer
zusammenfügen.
-Beispielsweise kann man die Ausgabe von zwei \emph{bitonen
-Mergesort-Netzwerken} $\operatorname{BS}(8)$ mit je acht Leitungen mit dem
-\emph{Odd-Even-Merge} $\operatorname{OEM(8,8)}$ zu einer sortierten
-Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt
+Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
+$\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
80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
-Verbesserungen in der Anzahl der benötigten Komparatoren beziehungsweise der
-Schichten eines „kleinen“ Sortiernetzwerks übertragen sich direkt auf das
-resultierende Gesamtnetzwerk. Das \emph{Odd-Even-Mergesort-Netzwerk}
-$\operatorname{OES}(9)$ benötigt beispielsweise 26~Komparatoren, die in in
-neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun
-Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten
-benötigen. Kombiniert man zwei dieser Netzwerke mit dem
-\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das
-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.
-Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer Arbeit „An 11-Step
-Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber
-6~Komparatoren weniger.
+Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren),
+beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“
+Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk.
+Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt
+beispielsweise 26~Komparatoren, die in 9~Schichten angeordnet sind. Es sind
+allerdings Sortiernetzwerke mit 9~Eingängen bekannt, die lediglich
+25~Komparatoren in 7~Schichten benötigen. Wenn zwei dieser Netzwerke mit dem
+\emph{Odd-Even}-Mischer kombiniert werden, entsteht ein 18-Sortiernetzwerk,
+das aus 80~Komparatoren in 11~Schichten besteht. Damit ist das resultierende
+Netzwerk genauso schnell wie das Sortiernetzwerk mit 18~Eingängen, das
+\textit{Sherenaz~W. Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer
+Arbeit „An 11-Step Sorting Network for 18~Elements“~\cite{BB2009} vorstellen,
+benötigt aber 6~Komparatoren weniger. $\operatorname{OES}(18)$ benötigt
+82~Komparatoren in 13~Schichten.
Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
\subsection{Leitungen entfernen}
\label{sect:leitungen_entfernen}
-Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
-\emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
+Im vorherigen Abschnitt wurde gezeigt, dass es mithilfe von \emph{Mischern}
+möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
-sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein
-Sortiernetzwerk mit $n$~Eingängen erhalten müssen.
+sich die Anzahl der Eingänge nicht verändert. Es soll wieder ein
+Sortiernetzwerk mit $n$~Eingängen entstehen.
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
+„eliminiert“. Dazu wird angenommen, dass das Minimum oder das Maximum an einem
+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 wechselt, 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}.
+das \emph{Odd-Even-Transpositionsort}-Netzwerk.
+
+Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf
+dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk
+eindeutig festgelegt.
\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
+ \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
+ markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
+ nach unten weiter gegeben wird, 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.}
+ Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
\label{fig:oe-transposition-cut}
\end{figure}
-Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
-ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
-haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
+Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht,
+beziehungsweise ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der
+Leitung geführt haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
-auf die keine Komparatoren mehr berührt
+die keine Komparatoren mehr berührt
(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
-auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
+Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die
+\emph{Position} des Minimums oder des Maximums in der Eingabe angenommen. Ein
+Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher
+Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese
+Annahme auszuwerten -- über die verbleibenden Eingänge wurde 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}.
+Wird 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, wird das eliminieren einer
+Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise
+\emph{Maximum-Schnitt} bezeichnet.
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.
+markierten Komparatoren sind verschoben, so dass sich eine kompaktere
+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
+Der Eliminierungsschritt kann iterativ angewendet 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
-nacheinander angewendet ein $n$-Sortiernetzwerk auf ein
-${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als
-\emph{$k$-Schnittmuster}.
+Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
+$n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man
+die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein
+$n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren.
Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
ergeben sich insgesamt
-\begin{equation}\label{eqn:anzahl_schnittmuster}
+\begin{displaymath}
\prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!}
\quad (n > m)
-\end{equation}
+\end{displaymath}
\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
-unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
-und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
-führen beide Reihenfolgen zum selben Ergebnis.
+unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung
+und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks
+angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis.
\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
-vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert,
-die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die
-Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von
-Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen
-Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl
-der möglichen Schnittmuster:
-\begin{displaymath}
+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{equation}\label{eqn:anzahl_schnittmuster}
2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
= 2^{k} \cdot \frac{n!}{k! (n-k)!}
= 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
\quad (1 \leqq k < n)
-\end{displaymath}
+\end{equation}
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.
Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
-als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der
-ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
+als die Anzahl der \emph{möglichen} Schnittmuster. Für jeden Komparator auf
+der ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
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
vernachlässigbar klein ist.
Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
-Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar.
-Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen
-Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich
-für „kleine“ x-Werte verlässt.
+Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
+Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern
+vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
+„kleine“ x-Werte verlässt.
Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
können, kann man sich einer stochastischen Methode bedienen, der sogenannten
-\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von
+\emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für
+schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von
$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
-der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$
-enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der
-unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der
-unterschiedlichen Schnittmuster abschätzen.
+der Annahme, dass auf diese Art und Weise Sortiernetzwerke zufällig und
+gleichverteilt erzeugt werden, entspricht das Verhältnis der zufälligen
+Schnittmuster, die in $S$ enthalten sind, und $n$ gleich dem Verhältnis von
+$k$ und der Anzahl der unterschiedlichen Schnittmuster insgesamt. Damit kann
+die Anzahl der unterschiedlichen Schnittmuster abgeschätzt werden.
\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$
\label{fig:collisions-100000-1000000-32-ps}
\end{figure}
-Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting-Netzwerk}
+Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting}-Netzwerk
$\operatorname{PS}(32)$ nicht betrachtet, da es für dieses Netzwerk viel mehr
unterschiedliche 16-Schnittmuster gibt als für $\operatorname{OES}(32)$ und
$\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der
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$
+waren. 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
(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
-in Abschnitt~\ref{sect:bewertung} behandelt.
+in Abschnitt~\ref{sect:sn-evolution:bewertung} behandelt. Informationen zur Implementierung
+von \textsc{SN-Evolution} befinden sich in
+Abschnitt~\ref{sect:implementierung}.
-\subsection{Bewertungsfunktion}\label{sect:bewertung}
+\subsection{Bewertungsfunktion}\label{sect:sn-evolution: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“)
\item Möglichst wenige Schichten („schnell“)
\end{itemize}
-Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
-effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
-60~Komparatoren in 10~Schichten. Das schnellste Netzwerk besteht aus
-61~Komparatoren in nur 9~Schichten.
-
-Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
-berücksichtigen kann, hat die folgende allgemeine Form:
+\begin{figure}
+ \centering
+ \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in~\cite{G1972}
+ veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
+ \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textit{D. Van~Voorhis} 1974 in~\cite{V1974}
+ veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
+ \caption{Das effizienteste und das schnellste Sortiernetzwerk für
+ 16~Leitungen, das derzeit bekannt ist.}
+ \label{fig:16-best-known}
+\end{figure}
+Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken.
+Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für
+16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in
+Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte
+16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
+Abbildung~\ref{fig:16-voorhis} zu sehen.
+
+\textsc{SN-Evolution} verwendet eine Gütefunktion, die die beiden Ziele
+"`effizient"' und "`schnell"' berücksichtigen kann. Sie hat die folgende
+generelle Form:
\begin{equation}
\operatorname{Guete}(S) = w_{\mathrm{Basis}}
+ w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
-Exploitation}, das Finden (lokaler) Optima, bevorzugt.
+Exploitation}, das Streben zu (lokalen) Optima, verstärkt. In~\cite{WW2002}
+geben \textit{Karsten und Nicole Weicker} einen Überblick über
+Selektionsmethoden und Rekombinationsmöglichkeiten.
Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
-Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es
-kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
+Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
+es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
Leitungszahlen und Mischer-Typen experimentiert werden muss.
+Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
+Werte herausgestellt:
+\begin{eqnarray*}
+ w_{\mathrm{Basis}} &=& 0 \\
+ w_{\mathrm{Komparatoren}} &=& 1 \\
+ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
+\end{eqnarray*}
+Sofern nicht anders angegeben, werden diese Werte im Folgenden zur Bewertung
+von Sortiernetzwerken verwendet. Die Bewertungsfunktion bevorzugt mit diesen
+Konstanten \emph{schnelle} Sortiernetzwerke, da das Einsparen einer Schicht
+ein höheres Gewicht als das Einsparen von Komparatoren hat.
+
+Wenn der \textsc{SN-Evolution}-Algorithmus nach \emph{effizienten}
+Sortiernetzwerken suchen soll, werden alternative Werte für die Konstanten der
+Bewertungsfunktion verwendet. Die Werte
+\begin{eqnarray*}
+ w_{\mathrm{Basis}} &=& 0 \\
+ w_{\mathrm{Komparatoren}} &=& 2 \\
+ w_{\mathrm{Schichten}} &=& 1
+\end{eqnarray*}
+geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
+einer Schicht.
+
\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)
-
-für jedes Individuum in Population
-{
- reziproke Güte := 1.0 / Guete(Individuum)
- Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
- Gütesumme := Gütesumme + reziproke Güte
-
- mit Wahrscheinlichkeit P
+ Gütesumme := 0
+ Auswahl := (leer)
+
+ für jedes Individuum in Population
{
- Auswahl := Individuum
+ reziproke Güte := 1.0 / Guete(Individuum)
+ Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
+ Gütesumme := Gütesumme + reziproke Güte
+
+ mit Wahrscheinlichkeit P
+ {
+ Auswahl := Individuum
+ }
}
-}
-gib Auswahl zurück
+ gib Auswahl zurück
\end{verbatim}
+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}
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
-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.
+einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
+einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
+bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
+\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
+Anschließend werden $n$~Leitungen mit einem zufälligen $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}
eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population
überprüft eine Funktion die Notwendigkeit jedes einzelnen Komparators. Dazu
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
-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
-Komparator, den er hätte entfernen können.
-
-\subsection{Güte}
-
-Die Qualität der erreichten Sortiernetzwerke wurde mit eine Gütefunktion
-beurteilt, die entsprechend dem im Abschnitt~\ref{sect:bewertung}
-vorgestellten Muster definiert ist. Wie beschrieben müssen die Faktoren häufig
-an die aktuelle Problemgröße angepasst werden, damit \textsc{SN-Evolution}
-schnell gute Ergebnisse liefert. Als guter Standardansatz haben sich die
-folgenden Werte herausgestellt:
-\begin{eqnarray*}
-w_{\mathrm{Basis}} &=& 0 \\
-w_{\mathrm{Komparatoren}} &=& 1 \\
-w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
-\end{eqnarray*}
+Netzwerk die Sortiereigenschaft noch besitzt. 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 Komparator, den er hätte entfernen können. Daher
+wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet.
+
+\subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer}
+
+Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
+als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
+Mischer} verwendet, gibt der Algorithmus \emph{effiziente} und in einigen
+Fällen \emph{schnelle} Sortiernetzwerke aus. Die Ergebnisse des
+\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
+sind in Tabelle~\ref{tbl:sn-ev-bm-fast} zusammengefasst.
+
+\begin{table}\label{tbl:sn-ev-bm-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\
+\cline{2-5}
+ ($n$) & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & \gcell 20 & 6 & 24 & 6 \\
+ 9 & \Gcell 26 & 8 & 28 & 8 \\
+ 10 & \gcell 31 & \gcell 8 & 33 & 9 \\
+ 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\
+ 12 & \gcell 42 & \gcell 9 & 46 & 10 \\
+ 13 & \Gcell 48 & 10 & 53 & 10 \\
+ 14 & \gcell 54 & 10 & 61 & 10 \\
+ 15 & \Gcell 61 & 10 & 70 & 10 \\
+ 16 & \gcell 67 & 10 & 80 & 10 \\
+ 17 & \Gcell 76 & 12 & 85 & 12 \\
+ 18 & \gcell 87 & \gcell 12 & 91 & 13 \\
+ 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\
+ 20 & \gcell 104 & \gcell 13 & 106 & 14 \\
+ 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
+ 22 & \gcell 118 & \gcell 14 & 123 & 15 \\
+ 23 & \Gcell 129 & \Gcell 14 & 133 & 15 \\
+ 24 & \gcell 133 & 15 & 144 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus
+ wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet
+ und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die
+ Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
+ $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
-\subsection{Versuche mit dem bitonen Mischer}
+Alle Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser Konfiguration
+gefunden wurden, waren \emph{effizienter} als das \emph{bitone
+Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
+Merge}-Netzwerk \bm{n} beruht. Zum Beispiel benötigt das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
+67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
\begin{figure}
\begin{center}
\label{fig:16-e1-bitonic-1296542566}
\end{figure}
-Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von
-\textsc{SN-Evolution}, so erhält man Netzwerke wie das in
-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.
+Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
+bevorzugt, werden in einigen Fällen Netzwerke zurückgegeben, die
+\emph{schneller} und \emph{effizienter} als \bs{n} sind. Das
+19-Sortiernetzwerk in Abbildung~\ref{fig:19-e1-bm-fast} besitzt beispielsweise
+nur 13~Schichten und benötigt damit einen parallelen Schritt weniger als
+\bs{19}.
-\subsection{Versuche mit dem Odd-Even-Mischer}
+\begin{figure}
+ \begin{center}
+ \input{images/19-e1-bm-fast.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+ unter Verwendung des \emph{bitonen Mischers} erzeugt.}
+ \label{fig:19-e1-bm-fast}
+\end{figure}
+
+\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
+
+Die folgenden Ergebnisse wurden erzielt, indem \textsc{SN-Evolution} mit dem
+\emph{Odd-Even-Transpositionsort}-Netzwerk als Eingabe gestartet wurde und in
+der Rekombinationsphase das \emph{Odd-Even-Merge}-Netzwerk verwendete. So
+erzeugt der Algorithmus entweder Sortiernetzwerke, die genauso schnell und
+effizient wie das \oes{n}-Netzwerk, oder Sortiernetzwerke, die schneller aber
+weniger effizient als das \oes{n}-Netzwerk sind. Die Ergebnisse von
+\textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer sind in
+Tabelle~\ref{tbl:sn-ev-oem-fast} zusammengefasst.
+
+\begin{table}\label{tbl:sn-ev-oem-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
+\cline{2-5}
+ & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & 19 & 6 & 19 & 6 \\
+ 9 & 26 & 8 & 26 & 8 \\
+ 10 & 31 & 9 & 31 & 9 \\
+ 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
+ 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
+ 13 & 48 & 10 & 48 & 10 \\
+ 14 & 53 & 10 & 53 & 10 \\
+ 15 & 59 & 10 & 59 & 10 \\
+ 16 & 63 & 10 & 63 & 10 \\
+ 17 & 74 & 12 & 74 & 12 \\
+ 18 & 82 & 13 & 82 & 13 \\
+ 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
+ 20 & 97 & 14 & 97 & 14 \\
+ 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
+ 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
+ 23 & 127 & \Gcell 14 & \Gcell 122 & 15 \\
+ 24 & 128 & 15 & \gcell 127 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
+ Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
+ gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
+ nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
+ 1$, $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
+
+Im vorherigen Abschnitt wurde gezeigt, dass der
+\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
+Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
+\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
+Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
+erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
+\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
+\emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
+nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
+Abbildung~\ref{fig:16-e1-oem-fast} dargestellt.
\begin{figure}
\begin{center}
- \input{images/16-e1-oddeven-1296543330.tex}
+ \input{images/16-e1-oem-fast.tex}
\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}
+ \label{fig:16-e1-oem-fast}
\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
-Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
-\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.
+Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
+mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
+Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Beispielsweise
+benötigt das 19-Sortiernetzwerk, das in Abbildung~\ref{fig:19-e1-oem-fast}
+dargestellt ist, nur 13~Schichten, während \oes{19} 14~Schichten benötigt.
-\todo{Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen.}
+\begin{figure}
+ \begin{center}
+ \input{images/19-e1-oem-fast.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+ unter Verwendung des \emph{Odd-Even}-Mischers erzeugt.}
+ \label{fig:19-e1-oem-fast}
+\end{figure}
%\begin{figure}
%\begin{center}
%\label{fig:10-e2-1239014566}
%\end{figure}
+\subsection{Zufälliger Mischer}
+
+Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
+Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
+\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
+Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
+12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
+82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
+um das beste Ergebnis beider Konstruktionen zu erreichen.
+\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
+Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
+\emph{Odd-Even}-Mischer wählen. Die Ergebnisse von \textsc{SN-Evolution} bei
+einer zufälligen Wahl des Mischers in der Rekombinationsphase sind in
+Tabelle~\ref{tbl:sn-ev-rnd-fast} zusammengefasst.
+
+\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 & 129 & 14 & \Gcell 127 & 14 & 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 beiden Mischer-Netzwerke. 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$ und
+ $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
+
+Bei einigen Leitungszahlen kann der Algorithmus durch die Verfügbarkeit beider
+Mi\-scher-Netzwerke Sortiernetzwerke zurückgeben, die effizienter als die
+vorherigen Ergebnisse sind. Beispielsweise ist das 19-Sortiernetzwerk in
+Abbildung~\ref{fig:19-e1-rnd-fast} mit 92~Komparatoren effizienter als die
+19-Sortiernetzwerke, die mit nur einem der beiden Mischer-Netzwerke erreicht
+wurden (Abbildungen~\ref{fig:19-e1-bm-fast} und~\ref{fig:19-e1-oem-fast}).
+
+\begin{figure}
+ \begin{center}
+ \input{images/19-e1-rnd-fast.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 92~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+ unter Verwendung des \emph{bitonen Mischers} und des
+ \emph{Odd-Even}-Mischers erzeugt.}
+ \label{fig:19-e1-rnd-fast}
+\end{figure}
+
+Die Ergebnisse anderer Leitungszahlen erreichen die Geschwindigkeit der
+Ergebnisse, die mit dem \emph{bitonen Mischer} erzielt wurden. Die Effizienz
+liegt zwischen den Ergebnissen, die mit dem \emph{bitonen Mischer} erzielt
+wurden, und den Ergebnissen, die mit dem \emph{Odd-Even}-Mischer erzielt
+wurden. Beispielsweise ist das 18-Sortiernetzwerk in
+Abbildung~\ref{fig:18-e1-rnd-fast} so schnell wie das Ergebnis, das mit dem
+\emph{bitonen Mischer} ausgegeben wurde. Mit 83~Komparatoren liegt die
+Effizienz des Sortiernetzwerks zwischen den Ergebnissen, die mit dem
+\emph{bitonen Mischer} (87~Komparatoren), beziehungsweise dem
+\emph{Odd-Even}-Mischer (82~Komparatoren) erreicht werden konnten.
+
+\begin{figure}
+ \begin{center}
+ \input{images/18-e1-rnd-fast.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 18~Leitungen und 83~Komparatoren in
+ 12~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+ unter Verwendung des \emph{bitonen Mischers} und des
+ \emph{Odd-Even}-Mischers erzeugt.}
+ \label{fig:18-e1-rnd-fast}
+\end{figure}
+
+In einigen Fällen hat \textsc{SN-Evolution} in dieser Konfiguration
+Sortiernetzwerke ausgegeben, die weniger effizient und genauso schnell wie die
+bisherigen Ergebnisse unter Verwendung des \emph{Odd-Even}-Mischers sind.
+Prinzipiell könnte der Algorithmus in jeder Iteration zufällig den
+\emph{Odd-Even}-Mischers auswählen, um die selektierten Individuen zu
+rekombinieren. Das heißt, das die Ergebnisse auch bei einer zufälligen Wahl
+des Mischer-Netzwerks theoretisch erreicht werden können. Allerdings sind
+unter Umständen mehr Iterationen notwendig, bis die gleiche Effizienz erreicht
+wird.
+
%\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.
-
-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$.
-
-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
-Schnitt-Richtung.
-
-\subsection{Versuche mit dem bitonen Mergesort-Netzwerk}
-
-In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka},
-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 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.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:sn-evolution: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 ungleich Null.
+
+Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
+Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
+verwendet. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq n$. Anschließend
+werden zufällig Werte auf Null beziehungsweise 1 oder $-1$ gesetzt, um die
+Anzahl der Schnitte zu korrigieren.
+
+Die Mutation vertauscht entweder die Werte von zwei zufälligen Positionen oder
+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}
+
+% Effizienz
+
+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.
+
+% Beispiel Effizienz
\begin{figure}
\begin{center}
- \input{images/16-ec-from-bs32.tex}
+ \input{images/16-ec-from-bs22.tex}
\end{center}
- \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+ \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}(32)$ durch 16~Schnitte erzeugt.}
+ \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.
+
+% Geschwindigkeit
+
+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.
+
+% Beispiel Geschwindigkeit
+
+\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 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.
+
+% Detaillierte Betrachtung fuer m = 19
+
+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}
+
+% 2-er Potenz
+
+\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
+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}
+ \input{images/16-ec-from-bs32.tex}
+ \end{center}
+ \caption{Visualisierung eines 16-Schnittmusters, das von
+ \textsc{SN-Evolution-Cut} für das \emph{bitone Mergesort}-Netzwerk \bs{32}
+ berechnet wurde. Das resultierende Sortiernetzwerk besteht aus
+ 68~Komparatoren in 10~Schichten und ist in
+ Abbildung~\ref{fig:16-ec-from-bs32-normalized} als
+ Standard-Sortiernetzwerk dargestellt.}
\label{fig:16-ec-from-bs32}
\end{figure}
\input{images/16-ec-from-bs32-normalized.tex}
\end{center}
\caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
- 10~Schichten. Das Netzwerk wurde von dem Algorithmus
- \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
- $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+ 10~Schichten. Das Netzwerk wurde mit einem 16-Schnittmuster, das von
+ \textsc{SN-Evolution-Cut} berechnet wurde, aus dem \emph{bitone
+ Mergesort}-Netzwerk \bs{32} erzeugt. Das Schnittmuster ist in
+ Abbildung~\ref{fig:16-ec-from-bs32} dargestellt.}
\label{fig:16-ec-from-bs32-normalized}
\end{figure}
-Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
+Startet man {\sc SN-Evolution-Cut} mit dem \emph{bitonen Mergesort}-Netzwerk
$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den
Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
-und das
-${\operatorname{MIN}(0,5,9,11,15,17,20,22,26,29,30)}$-${\operatorname{MAX}(2,4,13,19,24)}$-Schnittmuster,
-das durch \textsc{SN-Evolution-Cut} gefunden wurde.
+und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26,
+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} von \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
-Verzögerung 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
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
ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
-die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks
-leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und
-der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden.
-
-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.
-
-\begin{figure}
+die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
+Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
+mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
+
+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.
+
+\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:oes}
+
+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}
- \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 & 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
+\oes{m}&19& 26 & 31 & 37 & 41 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
+\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}
-
-\subsection{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, dass die gleiche
-Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
-$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
-Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
-
-Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
-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
-Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
+ \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/32-pairwise-cut-16-pairwise.tex}
- \end{center}
- \caption{PS(32) mit 16 Schnitten zu PS(16).}
- \label{fig:ps16-from-ps32}
+ \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}
-Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
-regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen 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}
+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.
+
+Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim
+\emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die
+Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war
+jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere
+Geschwindigkeit zu erreichen.
+
+In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von
+\textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots
+19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles
+19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die
+resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit
+$k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des
+\emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in
+13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht.
+
+\begin{table}
\begin{center}
- \input{images/16-pairwise.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{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 Verwandschaft von $\operatorname{PS}(n)$ und \oes{n}
-untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
+ \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}
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 91 & 14 \\
+ 21 & 91 & 14 \\
+ 22 & 91 & 14 \\
+ 23 & 91 & 14 \\
+ 24 & 91 & 14 \\
+ 25 & 91 & 14 \\
+ 26 & 91 & 14 \\
+ 27 & 91 & 14 \\
+ 28 & 91 & 14 \\
+ 29 & 95 & 13 \\
+ \rowcolor{green!10}
+ 30 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 31 & 93 & 13 \\
+ \rowcolor{green!10}
+ 32 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 33 & 93 & 13 \\
+ \rowcolor{green!10}
+ 34 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 35 & 93 & 13 \\
+ \rowcolor{green!10}
+ 36 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 37 & 93 & 13 \\
+ \rowcolor{green!10}
+ 38 & 93 & 13 \\
+ \hline
+ \bs{19} & 98 & 14 \\
+ \oes{19} & 91 & 14 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Komparatoren und Schichten von Sortiernetzwerken, die von
+ \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$
+ ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die
+ Effizienz von 91~Komparatoren nicht mehr erreichbar.}
+ \label{tbl:ec-oes-19}
+\end{table}
-\subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+% 2-er Potenzen
In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
-viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
-$\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$
-besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das
-\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.
+viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
+Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und
+$\operatorname{PS}(32)$ besitzen. Eines der Ergebnisse war, dass von diesen
+Sortiernetzwerken das \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\footnote{Ein
+entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen
+geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe
+Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf
+derzeitigen Computern.} ein gutes 16-Schnittmuster findet.
+
+Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
+bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} ist, 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}
\input{images/16-ec-from-oes32-cut.tex}
\end{center}
\caption{Visualisierung eines 16-Schnittmusters, das auf
- $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes
- Sortiernetzwerk ergibt.}
+ $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
+ bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
+ resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
+ dargestellt.}
\label{fig:16-ec-from-oes32-cut}
\end{figure}
\input{images/16-ec-from-oes32.tex}
\end{center}
\caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
- Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem
- \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(32)$ durch
- 16~Schnitte erzeugt.}
+ Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
+ einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
+ berechnet wurde. Das Schnittmuster ist in
+ Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
\label{fig:16-ec-from-oes32}
\end{figure}
-\newpage
-\section{Der \textsc{SN-Markov}-Algorithmus}
-\label{sect:markov}
+% Regelmaessiges Schnittmuster fuer n = 2^d
-Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
-Abschnitt verwendete 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.
+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 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}
+abgeleitet werden. 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.
-Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das
-aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
-Leitungen eliminiert, 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$.
+\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}
-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 man $S_1$ durch die Rekombination von $S_0$ mit sich
-selbst erzeugen kann.
+Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die durch
+dieses regelmäßige Schnittmuster 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.
+
+% SN-Evolution-Cut vs. regelmaessiges Schnittmuster
+
+Wird der \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{n}, $n = 22, 23, 24$
+und $k = 10, 11, 12$ gestartet, hängt die Ausgabe von der verwendeten
+Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der Algorithmus
+Schnittmuster wie das 12-Schnittmus\-ter $\operatorname{MIN}(6, 7, 8, 9, 16, 17,
+20, 22)$, $\operatorname{MAX}(2, 4, 12, 14)$ für \oes{24}, dessen Ergebnis in
+Abbildung~\ref{fig: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, weitere Ergebnisse für diese Gütefunktion sind in den
+Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} zusammengefasst.
+Das resultierende 12-Sortiernetzwerk besteht aus 43~Komparatoren, die
+in 9~Schichten angeordnet sind. Das resultierende Netzwerk zwar nicht so
+effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
-Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
-der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
-sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
-Nachfolger zwar noch unter 20.000, bei den untersuchten 32-Sortiernetzwerken
-wurden jedoch bereits bis zu $2,6 \cdot 10^8$ unterschiedliche Schnittmuster
-geschätzt.
+\begin{figure}
+ \centering
+ \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}}
+ \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}}
+ \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}
-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 dich der
-Algorithmus wie folgt beschreiben:
+\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
+
+Eine weitere interessante Eingabe für \textsc{SN-Evolution-Cut} ist das
+\emph{Pairwise-Sorting}-Netzwerk \ps{n}, das \textit{Ian
+Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
+definiert. Einerseits wurde in Abschnitt~\ref{sect:anzahl_schnittmuster}
+gezeigt, dass es für \ps{n} sehr viele \emph{unterschiedliche} Schnittmuster
+gibt. Andererseits sind die Sortiernetzwerke, die nach \textit{Parberrys}
+Methode erzeugt werden, genauso schnell und effizient wie das
+\emph{Odd-Even-Mergesort}-Netzwerk, wenn die Leitungszahl $n = 2^d$ eine
+Zweierpotenz ist.
+
+% Effizienz
+
+Für viele Kombinationen von \ps{n} und $k$ sind die Sortiernetzwerke, die
+\textsc{SN-Evolution-Cut} ausgibt, weniger effizient als das entsprechende
+\ps{m}-Netzwerk. Für einige Kombinationen werden jedoch auch effizientere
+Netzwerke generiert, beispielsweise für $m = 11$ und $m = 20$. Die Effizienz
+der Sortiernetzwerke, die \textsc{SN-Evolution-Cut} auf Basis des
+\emph{Pairwise-Sorting}-Netzwerks berechnet, ist tabellarisch in
+Tabelle~\ref{tbl:ec-ps-efficiency} dargestellt.
+
+\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-efficiency}
+\end{table}
+
+% Beispiel Effizienz
+
+Zwei Ergebnisse, die effizienter als die entsprechenden
+\emph{Pairwise-Sorting}-Netzwerke sind, zeigt
+Abbildung~\ref{fig:ec-ps-efficient_networks}. Sie erreichen die
+Geschwindigkeit und Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks mit der
+entsprechenden Leitungszahl. Bei größeren Netzwerken, beispielsweise $m = 19$,
+ist dies mit der in Tabelle~\ref{tbl:ec-ps-efficiency} dargestellten Größe der
+Schnittmuster noch nicht zu beobachten.
-\begin{verbatim}
-Netzwerk := Eingabe
+\begin{figure}
+ \centering
+ \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Pairwise-Sorting}-Netzwerk \ps{13}
+ erzeugt.]{\input{images/11-ec-from-ps13.tex}}
+ \subfigure[12-Sortiernetzwerk aus 41~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Pairwise-Sorting}-Netzwerk \ps{16}
+ erzeugt.]{\input{images/12-ec-from-ps16.tex}}
+ \caption{Zwei effiziente Sortiernetzwerke, die durch Schnittmuster, die von
+ \emph{SN-Evolution-Cut} berechnet wurden, aus dem
+ \emph{Pairwise-Sorting}-Netzwerk \ps{n} erzeugt wurden.}
+ \label{fig:ec-ps-efficient_networks}
+\end{figure}
-für n Iterationen
-{
- Nachfolger := kombiniere (Netzwerk, Netzwerk)
- Netzwerk := Nachfolger
-}
+% Wie viele Schnitte man braucht.
-gib Netzwerk zurück
-\end{verbatim}
+Bei welchen Parametern \textsc{SN-Evolution-Cut} effiziente
+19-Sortiernetzwerke findet, ist Tabelle~\ref{tbl:ec-ps-19} zu entnehmen. Für
+$n = 31$, $k = 12$ und $n = 32$, $k = 13$ werden 19-Sortiernetzwerke mit der
+selben Effizienz und Geschwindigkeit wie \oes{19} erzeugt. Das
+19-Sortiernetzwerk, das auf diese Art und Weise aus \ps{32} erzeugt wurde, ist
+in Abbildung~\ref{fig:19-ec-from-ps32} dargestellt.
-Die Abbildungen~\ref{fig:markov-comparators-12},
-\ref{fig:markov-comparators-14}, \ref{fig:markov-comparators-12},
-\ref{fig:markov-comparators-16} und~\ref{fig:markov-comparators-18} zeigen die
-Anzahl der Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf
-seinem zufälligen Pfad durchläuft. Ausserdem eingezeichnet ist eine
-\emph{Gamma-Verteilung}.
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 97 & 15 \\
+ 21 & 96 & 15 \\
+ 22 & 96 & 15 \\
+ 23 & 97 & 14 \\
+ 24 & 96 & 14 \\
+ 25 & 93 & 14 \\
+ 26 & 92 & 14 \\
+ 27 & 94 & 14 \\
+ 28 & 94 & 14 \\
+ 29 & 92 & 14 \\
+ 30 & 92 & 14 \\
+ \rowcolor{green!10!white!95!black}
+ 31 & 91 & 14 \\
+ \rowcolor{green!10}
+ 32 & 91 & 14 \\
+ 33 & 101 & 15 \\
+ 34 & 104 & 15 \\
+ 35 & 106 & 15 \\
+ 36 & 107 & 15 \\
+ 37 & 106 & 15 \\
+ 38 & 102 & 15 \\
+ \hline
+ \ps{19} & 97 & 15 \\
+ \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 \ps{n}, $n = 20, \dots, 38$ erzeugt
+ wurden.}
+ \label{tbl:ec-ps-19}
+\end{table}
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
+ \input{images/19-ec-from-ps32.tex}
\end{center}
- \caption{Zyklen, die beim \textit{Random Walk} des
- \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
- Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
- y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
- Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
- \label{fig:markov-cycles-16}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 91~Komparatoren in
+ 14~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+ $\operatorname{PS}(32)$ erzeugt.}
+ \label{fig:19-ec-from-ps32}
\end{figure}
-\todo{Schreibe noch etwas zu …}
-\begin{itemize}
- \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
- \item Anzahl der erreichbaren Sortiernetzwerke.
- \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
- Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
-\end{itemize}
+An den Daten in Tabelle~\ref{tbl:ec-ps-19} fällt auf, dass die Effizienz und
+Geschwindigkeit der Ergebnisse für $n > 32$ schlechter werden. Das
+\emph{Pairwise-Sorting}-Netzwerk ist Leitungszahlen, die Zweierpotenzen sind,
+besonders effizient und schnell. Um der Vermutung nachzugehen, dass der
+\textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente
+Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1
+\dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32}
+zusammengefasst.
-\begin{figure}
+\begin{table}
\begin{center}
- \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-12-pct.pdf}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $m$ & Komp. & Schichten \\
+ \hline
+ 16 & 69 & 11 \\
+ 17 & 77 & 13 \\
+ 18 & 89 & 13 \\
+ 19 & 91 & 14 \\
+ 20 & 97 & 14 \\
+ 21 & 107 & 15 \\
+ 22 & 114 & 15 \\
+ 23 & 122 & 15 \\
+ 24 & 127 & 15 \\
+ 25 & 138 & 15 \\
+ 26 & 146 & 15 \\
+ 27 & 155 & 15 \\
+ 28 & 161 & 15 \\
+ 29 & 171 & 15 \\
+ 30 & 178 & 15 \\
+ 31 & 186 & 15 \\
+ \hline
+ \end{tabular}
\end{center}
- \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen),
- die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
- \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.}
- \label{fig:markov-comparators-12}
-\end{figure}
+ \caption{Anzahl der Komparatoren und Schichten von $m$-Sortiernetzwerken,
+ die von \textsc{SN-Evolution-Cut} nach 5.000.000 Iterationen aus \ps{32}
+ erzeugt wurden.}
+ \label{tbl:ec-ps-32}
+\end{table}
+
+% Geschwindigkeit
+
+Die Schnittmuster, die \textsc{SN-Evolution-Cut} für das
+\emph{Pairwise-Sorting}-Netzwerk berechnet, können zu schnelleren
+Sortiernetzwerken als \ps{m} führen. Beispielsweise konnte aus \ps{24} ein
+18-Sortiernetzwerk erzeugt werden, das mit 13~Schichten zwei parallele
+Schritte im Vergleich zu \ps{18} einspart. Eine Darstellung dieses
+Sortiernetzwerks befindet sich in Abbildung~\ref{fig:18-ec-from-ps24}. Für
+andere $m$ wurde die Geschwindigkeit des \emph{Pairwise-Sorting}-Netzwerks
+nicht übertroffen und im Fall von $m = 16$ wurde die Geschwindigkeit nicht
+einmal erreicht.
+
+\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 & 10 & & & & & & & & & & & & & & \\
+ 11 & 6 & 9 & 10 & & & & & & & & & & & & & \\
+ 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 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & & & & & & & \\
+ 18 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & & & & & & \\
+ 19 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & & & & & \\
+ 20 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & 15 & & & & \\
+ 21 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 15 & 15 & 15 & & & \\
+ 22 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 14 & 15 & 15 & 15 & & \\
+ 23 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 14 & 14 & 15 & 15 & 15 & \\
+ 24 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 13 & 14 & 14 & 15 & 15 & 15 \\
+ \hline
+ \ps{m} & 6 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 15 & 15 & 15 & 15 & 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{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}
+
+% Beispiel Geschwindigkeit
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf}
+ \input{images/18-ec-from-ps24.tex}
\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{Sortiernetzwerk mit 18~Leitungen und 89~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+ $\operatorname{PS}(24)$ erzeugt.}
+ \label{fig:18-ec-from-ps24}
\end{figure}
+% 2-er Potenz
+
+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.
+
+Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet
+man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
+16~Leitungen zu entfernen, kann der Algorithmus ein Sortiernetzwerk
+zurückgeben, das die gleiche Anzahl Komparatoren und Schichten wie
+$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$ hat. Eines dieser
+Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+Dieses Ergebnis demonstriert, dass sich die Ergebnisse in den gezeigten
+Tabellen oft durch zusätzliche Iterationen verbessern lassen.
+
\begin{figure}
\begin{center}
- \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf}
+ \input{images/16-ec-from-ps32.tex}
\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}
+ \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/markov-comparators-18-pct.pdf}
+ \input{images/32-pairwise-cut-16-pairwise.tex}
\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}
+ \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}
-\newpage
-\section{Ausblick}
+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.
-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.
+\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}
-Im Folgenden werden Ansätze umrissen, mit denen an die Untersuchungen in
-dieser Arbeit nahtlos angeknöpft werden könnte.
+Ein Spezialfall ergibt sich, wenn \textsc{SN-Evolution-Cut} auf
+$\operatorname{PS}(16)$ angewendet wird: In diesem Fall kann ein
+8-Schnittmuster ausgegeben werden, das \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{8} aus \ps{16} erzeugt.. 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{Verwendung des Pairwise-Sorting-Netzwerk in \textsc{SN-Evolution}}
+\newpage
+\section{Fazit und Ausblick}
+
+Mit dem Entfernen von Leitungen aus bekannten Sortiernetzwerken lassen sich
+interessante Ergebnisse erzielen. Dies zeigte \textit{Moritz Mühlenthaler}
+bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und
+Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere
+interessante Beobachtungen machen lassen.
+
+Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution},
+\textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der
+Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres
+Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in
+Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt.
+
+Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den
+vorgestellten Algorithmen übertroffen werden. Der Algorithmus
+\textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und
+\textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und
+für ein 32-Sortiernetzwerk sogar noch übertreffen. Der
+\textsc{SN-Evolution}-Algorithmus fand 16-Sortiernetzwerke, die gegenüber dem
+Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen
+weiteren Komparator einsparen.
+
+Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen
+zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer
+Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das
+\emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden
+regelmäßige Schnittmuster angegeben. Diese ergeben Sortiernetzwerke, die so
+schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
+Netzwerke.
+
+Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen
+Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich
+weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das
+bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
+Schnittmustern erreicht werden können.
+
+Die Möglichkeiten der Optimierung von Sortiernetzwerken mit
+\emph{Evolutionären Algorithmen} 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
+(Abschnitte~\ref{sect:sn-evolution}
+beziehungsweise~\ref{sect:implementierung}) 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.
+Ausgabe sorgen. Anstelle von $\ps{\frac{n}{2}}$ können beliebige
+Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwendet werden.
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{unterscheidliche} Schnittmuster gibt
-(Abbschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
+\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{Kooperation von \textsc{SN-Evolution} und
-\textsc{SN-Evolution-Cut}}
+\subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}}
Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
-in~\cite{H1992} beschreibt, könnte man die Algorithmen \textsc{SN-Evolution}
-und \textsc{SN-Evolution-Cut} versuchen zu kombinieren. Nach dem Zusammenfügen
-von zwei $n$-Sortiernetzwerken könnte der Algorithmus
+in~\cite{H1990} beschreibt, könnte man versuchen, die Algorithmen
+\textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} 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
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ächten Generation beiträgt. Im Gegensatz zum Ansatz der
+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}
+\label{sect:implementierung}
Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens
entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen
Die meisten Kommandozeilen-Programmen lesen ein Komparatornetzwerk von der
Standard-Eingabe und schreiben ihr Ergebnis auf die Standard-Ausgabe. Um
Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen
-Mergesort}-Netzwerks \bs{18} zu erzeugen, kann folgendes Kommando verwendet
+Mergesort}-Netzwerks \bs{42} zu erzeugen, kann folgendes Kommando verwendet
werden:
\begin{verbatim}
-$ sn-bitonicsort 18 | sn-normalize >sn-18
+ $ sn-bitonicsort 42 | sn-normalize >sn-42
\end{verbatim}
Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
es einfach zu ermöglichen, Programme zu verketten, ist eines der
erwiesen.
Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden,
-sind unter anderem das Erzeugen von Odd-Even-Mergesort-, bitonic Mergesort-
-und Pairwise-Sorting-Netzwerken, das Normalisieren von Sortiernetzwerken,
-Anwendung von Schnittmustern auf Sortiernetzwerke und Anwendung eines
-Komparatornetzwerks auf eine Eingabe-Permutation.
+sind unter anderem das Erzeugen des \emph{Odd-Even-Mergesort}-, \emph{bitonen
+Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von
+Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und
+Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das
+Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise
+wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex}
+visualisiert.
\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 :
projects / diplomarbeit.git / blobdiff