X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=0358d88fd7e21f040e2607f0b11ab6ee9a155d41;hb=46edfe5592d85122354f2f39674d0e28986c856d;hp=bdb72963a3b33a2281c822d0ca8597e5edf97178;hpb=670f49dbdf6633678fb19ac01b03d5697bf81249;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index bdb7296..0358d88 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1,4 +1,4 @@ -\documentclass[a4paper,10pt]{article} +\documentclass[a4paper,11pt]{article} \usepackage[utf8]{inputenc} \usepackage{ngerman} \usepackage{fancyhdr} @@ -9,14 +9,18 @@ \usepackage{listings} \usepackage{graphicx} \usepackage{url} +\usepackage[table]{xcolor} %\usepackage{longtable} \usepackage{subfigure} \usepackage{icomma} +\usepackage{tikz} +\usetikzlibrary{arrows,shapes} + % Fuer mathtoolsset \usepackage{mathtools} -\geometry{paper=a4paper,margin=25mm} +\geometry{paper=a4paper,margin=30mm} \pagestyle{fancy} %\fancyhf{} @@ -33,6 +37,16 @@ \newcommand{\todo}[1]{{\bf TODO:} #1} \newcommand{\qed}{\hfill $\Box$ \par \bigskip} +\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} @@ -41,38 +55,2634 @@ \begin{document} +\tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt] +\tikzstyle{comp} = [draw,thick,-] +\tikzstyle{compup} = [draw,thick,->] +\tikzstyle{compdown} = [draw,thick,<-] +\tikzstyle{edge} = [draw,thick,-] +\tikzstyle{diredge} = [draw,thick,->] +\tikzstyle{prob} = [font=\tiny] + +\tikzstyle{edge minimum} = [edge,color=blue!20] +\tikzstyle{edge maximum} = [edge,color=red!20] +\tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50] +\tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50] +\tikzstyle{vertex active minimum maximum} = [vertex,color=violet!50, fill=violet!50] +\tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20] +\tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20] +\tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20] +\tikzstyle{comp active minimum} = [comp] +\tikzstyle{comp active maximum} = [comp] +\tikzstyle{comp active minimum maximum} = [comp,color=black!20] +\tikzstyle{comp inactive minimum} = [comp,color=blue!20] +\tikzstyle{comp inactive maximum} = [comp,color=red!20] +\tikzstyle{comp inactive minimum maximum} = [comp,color=black!20] + +\tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10] +\tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10] +\tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10] +\tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10] + \maketitle \begin{abstract} -Dies ist der Abstract. +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 \tableofcontents -\newpage +\newpage \section{Motivation und Einleitung} -\subsection{Motivation} +\subsection{Motivation}\label{sect:motivation} + +\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} + +\subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke} + +\emph{Komparatoren} sind die Bausteine, die \emph{Komparatornetzwerken} +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 immer auf dem einen, die kleinere der beiden Zahlen +immer auf dem anderen Ausgang ausgegeben wird. + +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- beziehungsweise Ausgängen, bestehend +aus 5~Komparatoren.} +\label{fig:einfaches_komparatornetzwerk} +\end{figure} + +Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches +\emph{Komparatornetzwerk} aus fünf Komparatoren. Insgesamt gibt es vier +verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch +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 Übersichtlichkeit +durch schwarze Punkte symbolisiert. + +Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in +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. 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 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. + +\emph{Komparatornetzwerke}, die für \emph{jede} Eingabefolge eine Ausgabe +erzeugen, die der Sortierung der Eingabe entspricht, heißen +\emph{Sortiernetzwerke}. Das in +Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk +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{figure} + \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.} + \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 +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}\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 +möglichen Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4, +8, 6)$ lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die +Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1, +0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt. + +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 +ist.\footnote{1.307.674.368.000 Permutationen} + +\label{sect:0-1-prinzip} +Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie +\textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende: +Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine +Permutation $E = (e_0, \dots, e_{n-1})$ beliebiger Zahlen, die nicht sortiert +wird. Die Ausgabefolge sei $A = (a_0, \dots, a_{n-1})$. Sei $i$ eine Position +in der Ausgabe, die die Sortierbedingung verletzt: +\begin{displaymath} + a_0 \leqq a_1 \leqq \dots \leqq a_{i-1} > a_i \dots +\end{displaymath} +Die Eingabe kann mittels +\begin{displaymath} + \hat{e}_j = \left\{ + \begin{array}{cl} + 0 & e_j \leqq a_i \\ + 1 & e_j > a_i + \end{array} \right. +\end{displaymath} +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 +$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, +ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$ +verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein +schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen, +ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt, +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 Minuten +beschäftigen. + +\subsubsection{Evolutionäre Algorithmen} + +Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die +entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse +$\mathcal{NP}$. 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 effiziente exakte Algorithmen für diese Probleme nicht gibt. Falls +sich hingegen herausstellt, dass diese Probleme neben $\mathcal{NP}$ auch in +der Komplexitätsklasse~\textit{P} liegen, gibt es effiziente Algorithmen. Es +ist jedoch wahrscheinlich, dass die Zeitkonstanten solcher Algorithmen sehr +groß sein würden, 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. 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 +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 +verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge +eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der +{\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise +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 +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 +\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. 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 +bevorzugt werden, hat einen starken Einfluss auf das Verhalten des +Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus +schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch +für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus +schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale +Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt, +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. + +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. + +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 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 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{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{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. + +\begin{figure} + \centering + \subfigure{\input{images/13-juille-0.tex}} + \subfigure{\input{images/13-juille-1.tex}} + \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des + END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in + 10~Schichten.} + \label{fig:13-juille} +\end{figure} +\textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving +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}). + +\newpage +\section[Konstruktionsverfahren]{Konstruktionsverfahren für Sortiernetzwerke} +\label{sect:konstruktive_netzwerke} + +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 vier Konstruktionsverfahren vorgestellt. + +% \todo{Drei oder vier Verfahren?} + +\subsection{Das Odd-Even-Transpositionsort-Netzwerk} +\label{sect:odd_even_transpositionsort} + +Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der +einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede +"`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet. +Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für +${n = 8}$ Leitungen. + +\begin{figure} + \begin{center} + \input{images/oe-transposition-8.tex} + \end{center} + \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.} + \label{fig:odd-even-transposition-08} +\end{figure} + +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. + +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)$. 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 +Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu +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 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{„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. + +\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 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 + \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}} + \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}} + \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}} + \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}} + \caption{Beispiele bitoner Folgen.} + \label{fig:beispiel-biton} +\end{figure} + +\begin{figure} + \centering + \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}} + \qquad + \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}} + \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der + aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element + der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden + resultierenden Teilfolgen sind wiederum biton.} + \label{fig:bitonic-merge-schema} +\end{figure} + +Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je +${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und +$V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend +sortiert, die Folge $V$ sei absteigend sortiert: +\begin{eqnarray} + u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\ + v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1} +\end{eqnarray} +Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen +Positionen verglichen und ggf. vertauscht: +\begin{equation} +u_i \longleftrightarrow v_i, \quad 0 \leqq i < m +\end{equation} +Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die +durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass +Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$ +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 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 schematisch. + +Um die Folge vollständig zu sortieren, müssen anschließend die beiden +resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls +mithilfe des bitonen Mischers, mit zwei Instanzen von +$\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem +bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als +Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen +definiert 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 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) = \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 +$\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 +rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so +alle Komparatoren in die gleiche Richtung zeigen. + +\begin{figure} + \begin{center} + \input{images/batcher-8.tex} + \end{center} + \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 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 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 +Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist +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 \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer} + +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. 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 +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 +$W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit: +\begin{equation} +w_i = \left\{ \begin{array}{ll} + u_i, & i < n \\ + v_{i-n}, & i \geqq n + \end{array} \right., + \quad 0 \leqq i < N +\end{equation} + +\begin{figure} + \begin{center} + \input{images/oe-merge.tex} + \end{center} + \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} + +Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der +geraden Indizes und je eine Liste der ungeraden Indizes. +\begin{eqnarray} + U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\ + U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\ + V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\ + V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right) +\end{eqnarray} + +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) +\end{eqnarray} +ergeben. + +Anschließend werden die Komparatoren zwischen benachbarten Leitungen +hinzugefügt, +\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 +\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 -- +entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was +offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven +Aufbau lauten: +\begin{itemize} + \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer. + \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem + einzelnen Komparator. +\end{itemize} + +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 + + \left|V_{\textrm{gerade}}\right|_0 + = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil + + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\ + \left|W_{\textrm{ungerade}}\right|_0 + &=& \left|U_{\textrm{ungerade}}\right|_0 + + \left|V_{\textrm{ungerade}}\right|_0 + = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor + + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor +\end{eqnarray} +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ält als +$W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die +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} + \centering + \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}} + \qquad + \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}} + \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 \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.} + \label{fig:oe-post-recursive} +\end{figure} + +Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden, +bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$ +Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit +Schichten im Mischer-Netzwerk), hängt von der längeren der beiden +Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$. + +Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im +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 \\ + K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right) + + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right) + + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1 + \end{array} \right. +\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 $\Theta(N \log (N))$ enthalten ist. + +Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die +Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der +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 +$\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 +\begin{displaymath} + \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1 +\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 +\end{displaymath} +für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$ +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 +effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl +entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht +\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 8~Eingänge. Markiert + sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden + \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade + Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten + Komparatoren zwischen benachbarten Leitungen (grün).} + \label{fig:odd-even-mergesort-08} +\end{figure} + +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 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: +\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} +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 +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 +\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} +\label{sect:tranformation} + +\subsection{Komprimieren} + +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 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} +beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem +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 + \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}} + \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}} + \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk + transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der + intuitiven Konstruktion und die normalisierte Variante.} + \label{fig:beispiel_normalisieren} +\end{figure} + +Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk} +ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung +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 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 selbe +Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen- +und das Trichtermuster zu sehen. + +\subsection{Zwei Netzwerke kombinieren} + +Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden +zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen +Sortiernetzwerk zusammenzufassen. + +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 +und Weise rekursiv aufgebaut. + +Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte +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 +zusammenfügen. + +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 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 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 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. + +Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung +ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits +sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine +Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die +letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen +die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden +Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand +nur mit exponentiellem Aufwand möglich ist. + +\subsection{Leitungen entfernen} +\label{sect:leitungen_entfernen} + +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. 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 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 \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[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 \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 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, +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 +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 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. + +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 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 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 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 +Schnittmuster \emph{unterschiedlich} bezüglich~$S$. + +Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine +Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als +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{displaymath} + \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!} + \quad (n > m) +\end{displaymath} +\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle +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, 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{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 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 \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 +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 +Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die +Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass +sich die Resultate auch in der ersten Schicht nicht unterscheiden. + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf} + \end{center} + \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch + 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.} + \label{fig:count-cuts-16} +\end{figure} + +Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl +der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der +\emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der +\emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je +eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke \oes{16}, +\bs{16} und \ps{16} angewandt. Anschließend wurde mithilfe einer Hashtabelle +überprüft, ob das resultierende Sortiernetzwerk schon von einem +\emph{äquivalenten} Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk +noch nicht in der Hashtabelle enthalten war, wurde der Zähler für +unterschiedliche Schnittmuster erhöht und das Sortiernetzwerk eingefügt. + +Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der +\emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen +Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten +Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der +Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr +nahe ist. + +Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der +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 +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 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}, 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 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. -Das habe ich gemacht, bzw. darum habe ich das gemacht. +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf} + \end{center} + \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} +\end{figure} -\subsection{Einleitung}\label{sect:introduction} +In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des +Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf +$\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von +jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000 +\emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000 +zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster, +die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet. +Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für +$\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2 +\cdot 10^6$ unterschiedlichen 16-Schnittmustern für $\operatorname{OES}(32)$ +und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$. -Das sind Sortiernetzwerke und so. +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf} + \end{center} + \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$ + unterschiedlichen Schnittmustern.} + \label{fig:collisions-100000-1000000-32-ps} +\end{figure} -\section{Die Algorithmen} +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 +unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in +Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die +Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$, +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 unterschiedlichen +Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385 +Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent +waren. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$ +unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den +vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als +die Anzahl der \emph{möglichen} Schnittmuster. -... +\newpage +\section{Der \textsc{SN-Evolution}-Algorithmus} +\label{sect:sn-evolution} + +Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer +Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer +(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. + +\subsection{Bewertungsfunktion}\label{sect:bewertung} + +Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die +{\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} + +\begin{figure} + \centering + \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}} + \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}} + \caption{Das effizienteste und das schnellste Sortiernetzwerk für + 16~Leitungen, das derzeit bekannt ist.} + \label{fig:16-best-known} +\end{figure} +Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. +Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für +16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in +Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte +16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in +Abbildung~\ref{fig:16-voorhis} zu sehen. + +Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"' +berücksichtigen kann, hat die folgende allgemeine Form: +\begin{equation} + \operatorname{Guete}(S) = w_{\mathrm{Basis}} + + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren} + + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten} +\end{equation} +Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen +dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter +gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide +Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet -- +jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht +so schlecht ist wie man intuitiv vermuten könnte, zeigt der +\textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.} + +Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen, +ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert. +Das heißt, dass das Ziel von \textsc{SN-Evolution} ist, +$\operatorname{Guete}(S)$ zu \emph{minimieren}. + +Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss +genommen werden. Ist er groß, wird der relative Unterschied der Güten +verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des +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. + +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 "`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*} + +\subsection{Selektion} + +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, +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 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 + { + Auswahl := Individuum + } + } + 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. 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. 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} + +Zu einem vollständigen evolutionären Algorithmus gehört außerdem die Mutation +--~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein +Sortiernetzwerk zufällig zu verändern und dabei die Sortiereigenschaft zu +erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese +Eigenschaft zerstören. + +Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die +Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese +Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das +Ausprobieren aller $2^n$~Bitmuster, wie in Abschnitt~\ref{sect:0-1-prinzip} +beschrieben. + +Um das Potenzial einer Mutation abzuschätzen wurde in \textsc{SN-Evolution} +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 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} + +\begin{figure} + \begin{center} + \input{images/16-e1-bitonic-1296542566.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers} + erzeugt.} + \label{fig:16-e1-bitonic-1296542566} +\end{figure} + +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 Sortiernetzwerke wie das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück. + +Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser +Konfiguration gefunden werden, sind effizienter als das \emph{bitone +Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen +Merge}-Netzwerk \bm{n} beruht. Das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk +benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}. + +Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke +bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n} +sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als +\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit +134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von +schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen +Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast} +aufgelistet. + +\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 & 134 & \Gcell 14 & \Gcell 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[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} + +\begin{figure} + \begin{center} + \input{images/16-e1-oddeven-1296543330.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 + erzeugt.} + \label{fig:16-e1-oddeven-1296543330} +\end{figure} + +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-oddeven-1296543330} zu sehen. + +Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch +mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution} +Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht +beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt +\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen. +\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der +Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet +sich in Tabelle~\ref{tbl:sn-ev-oem-fast}. + +%\begin{figure} +%\begin{center} +%\input{images/08-e2-1237993371.tex} +%\end{center} +%\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten} +%\label{fig:08-e2-1237993371} +%\end{figure} +% +%\begin{figure} +%\begin{center} +%\input{images/09-e2-1237997073.tex} +%\end{center} +%\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten} +%\label{fig:09-e2-1237997073} +%\end{figure} +% +%\begin{figure} +%\begin{center} +%\input{images/09-e2-1237999719.tex} +%\end{center} +%\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten} +%\label{fig:09-e2-1237999719} +%\end{figure} +% +%\begin{figure} +%\begin{center} +%\input{images/10-e2-1239014566.tex} +%\end{center} +%\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten} +%\label{fig:10-e2-1239014566} +%\end{figure} + +\begin{table}\label{tbl:sn-ev-oem-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\ +\cline{2-5} + & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & 19 & 6 & 19 & 6 \\ + 9 & 26 & 8 & 26 & 8 \\ + 10 & 31 & 9 & 31 & 9 \\ + 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\ + 12 & 43 & \gcell 9 & \gcell 41 & 10 \\ + 13 & 48 & 10 & 48 & 10 \\ + 14 & 53 & 10 & 53 & 10 \\ + 15 & 59 & 10 & 59 & 10 \\ + 16 & 63 & 10 & 63 & 10 \\ + 17 & 74 & 12 & 74 & 12 \\ + 18 & 82 & 13 & 82 & 13 \\ + 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\ + 20 & 97 & 14 & 97 & 14 \\ + 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\ + 22 & 117 & \gcell 14 & \gcell 114 & 15 \\ + 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\ + 24 & 128 & 15 & \gcell 127 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der + Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} + gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion + nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = + 1$, $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} + +\subsection{Zufälliger Mischer} + +Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige +Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der +\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das +Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur +12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur +82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen, +um das beste Ergebnis beider Konstruktionen zu erreichen. +\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier +Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem +\emph{Odd-Even}-Mischer wählen. + +Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des +Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast} +zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der +Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem +Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und +20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen +Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz. + +\begin{table}\label{tbl:sn-ev-rnd-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} + & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} + & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\ +\cline{2-7} + ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & 20 & 6 & \gcell 19 & 6 & \gcell 19 & 6 \\ + 9 & 26 & 8 & 26 & 8 & 26 & 8 \\ + 10 & 31 & \gcell 8 & 31 & 9 & 31 & \gcell 8 \\ + 11 & \Gcell 37 & 9 & 38 & 9 & \Gcell 37 & 9 \\ + 12 & 42 & 9 & 43 & 9 & \gcell 41 & 9 \\ + 13 & 48 & 10 & 48 & 10 & 48 & 10 \\ + 14 & 54 & 10 & \gcell 53 & 10 & \gcell 53 & 10 \\ + 15 & 61 & 10 & \Gcell 59 & 10 & \Gcell 59 & 10 \\ + 16 & 67 & 10 & \gcell 63 & 10 & 64 & 10 \\ + 17 & 76 & 12 & \Gcell 74 & 12 & \Gcell 74 & 12 \\ + 18 & 87 & \gcell 12 & \gcell 82 & 13 & 83 & \gcell 12 \\ + 19 & 93 & 13 & 93 & 13 & \Gcell 92 & 13 \\ + 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\ + 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\ + 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\ + 23 & 134 & 14 & 129 & 14 & \Gcell 128 & 14 \\ + 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung der verschiedenen Mischer. Der Algorithmus wurde mit dem + \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach + 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten + $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$, + $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} + +%\input{shmoo-aequivalenz.tex} + +\newpage +\section{Der \textsc{SN-Markov}-Algorithmus} +\label{sect:markov} + +Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen +Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus +einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander +ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal +verwendet und mit sich selbst kombiniert wird. + +Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk +\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller +Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke, +die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit +sich selbst und anschließendem Eliminieren der Hälfte der Leitungen hervorgehen +können, heißen \emph{Nachfolger} von $S_0$. + +Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem +(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei +Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer +Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von +$S_0$ ist, das heißt, dass $S_1$ durch die Rekombination von $S_0$ mit sich +selbst erzeugt werden kann. + +Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl +der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger +sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der +Nachfolger zwar noch unter 20.000, bei den untersuchten +32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$ +unterschiedliche Schnittmuster geschätzt. + +Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen +zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem +gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu +gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich +selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der +Algorithmus wie folgt beschreiben: + +\begin{verbatim} + Netzwerk := Eingabe + + für n Iterationen + { + Nachfolger := kombiniere (Netzwerk, Netzwerk) + Netzwerk := Nachfolger + } + + gib Netzwerk zurück +\end{verbatim} + +Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der +Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem +zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der +\textsc{SN-Markov}-Algorithmus auf einem entsprechenden +\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens +1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der +Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler +erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende +prozentuale Verteilung zu sehen. + +Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators} +eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen +Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der +um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde. +Beispielsweise war die kleinste erreichte Komparatorzahl bei +16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$ +gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$ +und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem +Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$ +unter den Graphen angegeben. + +\begin{figure} + \centering + \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}} + \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}} + \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}} + \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}} + \caption{Anzahl der Komparatoren von Sortiernetzwerken, + die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet + ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der + gemessenen Daten darstellt.} + \label{fig:markov-comparators} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf} + \end{center} + \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von + \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem + \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.} + \label{fig:comparison-comparators} +\end{figure} + +Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der +\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der +\textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit +\textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl +der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als +Startnetzwerk diente bei beiden Algorithmen das +\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der +x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der +ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt +wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je +nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}. + +Sowohl der \textsc{SN-Markov}-Algorithmus, der das +\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit +\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die +bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind. +Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger: +Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit +63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335 +\%$ rund 20~mal höher. + +Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem +\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist +jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die +mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16} +ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für +Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein +Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so +vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen +Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das +mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk +zusammenhängt. + +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.} +% \label{fig:markov-comparators-14} +%\end{figure} +% +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.} +% \label{fig:markov-comparators-16} +%\end{figure} +% +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.} +% \label{fig:markov-comparators-18} +%\end{figure} + +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} +% \end{center} +% \caption{Zyklen, die beim \textit{Random Walk} des +% \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die +% Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der +% y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale +% Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} +% \label{fig:markov-cycles-16} +%\end{figure} + +\newpage +\section{Der \textsc{SN-Evolution-Cut}-Algorithmus} +\label{sect:sn-evolution-cut} + +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 \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. + +\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk} +\label{sect:sn-evolution-cut:bs} + +Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen +Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll, +ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke +als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k += 6$ gestartet, resultiert das gefundene Schnittmuster in einem +Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16} +benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert +wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen. + +\begin{figure} + \begin{center} + \input{images/16-ec-from-bs22.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk + $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4, + 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.} + \label{fig:16-ec-from-bs22} +\end{figure} + +Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen +Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden, +gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde +mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten +der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$, +$w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder +Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten +befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des +Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des +resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der +Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu +können. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|rrrrrrrrrrrrrrrr|} + \hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ + \hline + 9 & 21 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\ + 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\ + 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\ + 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\ + 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\ + 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\ + 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\ + 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\ + 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\ + 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\ + 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\ + 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\ + 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\ + \hline +\bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen + Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt + die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die + Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.} + \label{tbl:ec-bs-efficiency} +\end{table} + +Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut} +mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der +gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von +$m=23$) ein Ergebnis, das effizienter als \bs{m} ist. -\subsection{Ausblick} +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}. -So geht's jetzt weiter. +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. -%\bibliography{references} -%\bibliographystyle{plain} +\begin{figure} + \centering + \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}} + \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}} + \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}} + \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}} + \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11, + 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke + erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.} + \label{fig:ec-bs-fast_networks} +\end{figure} + +Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der +\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als +das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In +Tabelle~\ref{tbl:ec-bs-speed} sind die Schichten, die die Ergebnisse von +\textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren, aufgelistet. +Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n}, jede Spalte +enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die Zellen +enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 6 & & & & & & & & & & & & & & & \\ + 10 & 6 & 8 & & & & & & & & & & & & & & \\ + 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\ + 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\ + 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\ + 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\ + 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\ + 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\ + 17 & 6 & 8 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\ + 18 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\ + 19 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\ + 20 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\ + 21 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\ + 22 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\ + 23 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\ + 24 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\ +\hline +\bs{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\ +\hline +\end{tabular} + \end{center} + \caption{Anzahl der Schichten der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen + Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt + die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die + Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.} + \label{tbl:ec-bs-speed} +\end{table} + +Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die +schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke, +die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt +werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt. + +Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das +Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m} +führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt +werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht +einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m += 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu +reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise +noch größer gewählt werden. + +Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von +\textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten +werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in +Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im +Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n = +37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19} +und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein +Beispiel für ein solches Netzwerk ist in +Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|r|r|} + \hline + $n$ & Komp. & Schichten \\ + \hline + 20 & 95 & 14 \\ + 21 & 94 & 14 \\ + 22 & 93 & 14 \\ + 23 & 93 & 14 \\ + 24 & 93 & 14 \\ + 25 & 96 & 13 \\ + 26 & 96 & 13 \\ + 27 & 96 & 13 \\ + 28 & 96 & 13 \\ + 29 & 95 & 13 \\ + 30 & 96 & 13 \\ + 31 & 95 & 13 \\ + 32 & 96 & 13 \\ + 33 & 93 & 13 \\ + 34 & 94 & 13 \\ + 35 & 93 & 13 \\ + \rowcolor{green!10} + 36 & 92 & 13 \\ + \rowcolor{green!10!white!95!black} + 37 & 92 & 13 \\ + 38 & 93 & 13 \\ + \hline + \bs{19} & 98 & 14 \\ + \oes{19} & 91 & 14 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die + von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt + wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als + \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit + 13~Schichten die Effizienz der vorherigen + Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese + Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37} + auf diese Art erzeugt wurde, ist in + Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.} + \label{tbl:ec-bs-19} +\end{table} + +\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, +wie 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{Sortiernetzwerk mit 16~Leitungen und 68~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.} + \label{fig:16-ec-from-bs32} +\end{figure} + +\begin{figure} + \begin{center} + \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.} + \label{fig:16-ec-from-bs32-normalized} +\end{figure} + +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 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 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 + % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX + % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX + % 63:MAX + \begin{center} + \input{images/32-ec-from-bs64.tex} + \end{center} + \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in + 15~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk + $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige + Schnittmuster ist + $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$, + $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37, + 40, 43, 47, 48, 49, 55, 56, 60, 63)$.} + \label{fig:32-ec-from-bs64} +\end{figure} + +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 \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 \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} + \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 +\end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} + \label{tbl:ec-oes-efficiency} +\end{table} + +\begin{figure} + \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} + +Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt +schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein +$m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes +Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit +war allerdings in allen beobachteten Fällen nur dann möglich, wenn +zusätzliche Komparatoren in Kauf genommen wurden. In den +Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser +Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu +beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in +Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt. + +\begin{table} + \begin{center} + \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{Anzahl der Schichten der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} + \label{tbl:ec-oes-speed} +\end{table} + +In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie +viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke +$\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{Auf dem Computer, auf dem diese +Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine +Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes +16-Schnittmuster findet. + +Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das +bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist +$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, +8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in +Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende +Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen. + +\begin{figure} + \begin{center} + \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.} + \label{fig:16-ec-from-oes32-cut} +\end{figure} + +\begin{figure} + \begin{center} + \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.} + \label{fig:16-ec-from-oes32} +\end{figure} + +Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3, +4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser +Beobachtung kann man das regelmäßige Schnittmuster +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + \infty & \quad \textrm{falls } i \bmod 4 = 0 \\ + -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} +ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der +Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente +Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein +32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde, +ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen. + +\begin{figure} + \begin{center} + \input{images/32-ec-from-oes64.tex} + \end{center} + \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten. + Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem + \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.} + \label{fig:32-ec-from-oes64} +\end{figure} + +Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so +erzeugten Sortiernetzwerke die Effizienz des +\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster +beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit +43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit +beider Sortiernetzwerke ist mit 10~Schichten identisch. + +Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24} +und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der +verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der +Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20, +22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in +Abbildung~\ref{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. Das 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}. + +\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} + +Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut} +findet Sortiernetzwerke, die schneller sind als das entsprechende +\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit +22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige +schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können, +charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das +\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl. +\begin{center} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\ + & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\ +\hline +11 & 38 & 9 & 37 & 10 \\ +12 & 43 & 9 & 41 & 10 \\ +19 & 93 & 13 & 91 & 14 \\ +20 & 101 & 13 & 97 & 14 \\ +21 & 108 & 14 & 107 & 15 \\ +22 & 116 & 14 & 114 & 15 \\ +23 & 125 & 14 & 122 & 15 \\ +\hline +\end{tabular} +\end{center} +Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein +23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem +Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der +Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In +beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu +\bs{23} beziehungsweise \oes{23} eine Schicht einspart. + +\begin{figure} + \begin{center} + \input{images/23-ec-from-oes46-fast.tex} + \end{center} + \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten. + Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem + Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38, + 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$ + erzeugt.} + \label{fig:23-ec-from-oes46} +\end{figure} + +\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk} + +Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene +Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war +(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise +ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich, +wie und warum es jede beliebige Eingabe sortiert. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 20 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\ + 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\ + 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\ + 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\ + 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\ + 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\ + 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\ + 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\ + 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\ + 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\ + 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\ + 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\ + 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\ +\hline +\ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\ +\hline +\end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} + \label{tbl:ec-ps-speed} +\end{table} + +Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian +Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} +definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit +$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man +ein Sortiernetzwerk, das die gleiche Anzahl Komparatoren und Schichten hat wie +$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser +Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. + +\begin{figure} + \begin{center} + \input{images/16-ec-from-ps32.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} + $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} + \label{fig:16-ec-from-ps32} +\end{figure} + +Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht +einsetzt und auch nicht auf einem Mischer basiert, ist das +\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in +Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In +den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die +strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die +Schichten~1 und~2 sowie 4~und~5 sind vertauscht. + +\begin{figure} + \begin{center} + \input{images/32-pairwise-cut-16-pairwise.tex} + \end{center} + \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu + sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk + bilden.} + \label{fig:ps16-from-ps32} +\end{figure} + +Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach +regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres +schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das +einfache Schnittmuster +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\ + \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} +für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk +$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der +dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das +verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32} +dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind +diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden +Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den +„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht +werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende +Netzwerk in schwarz gut zu erkennen. + +\begin{figure} + \begin{center} + \input{images/16-pairwise.tex} + \end{center} + \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten + ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das + resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.} + \label{fig:16-pairwise} +\end{figure} + +Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf +$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein +8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für +größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise +kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} +konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} +untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. + +\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} +(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 +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{unterschiedliche} Schnittmuster gibt +(Abschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die +Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider +wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine +$n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren +$n$-Sortiernetzwerken als \ps{n} führen. + +\subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}} + +Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis} +in~\cite{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 +verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut} +die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern. + +Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} -- +eine zweite Population von Schnittmustern evolvieren, die für die +Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut +funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge +Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten +Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster +eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses} +Schnittmuster zur nächsten Generation beiträgt. Im Gegensatz zum Ansatz der +parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die +das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern +könnte. + +\newpage +\section{Implementierung} +\label{sect:implementierung} + +Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens +entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen +Kommandozeilen-Programmen durchgeführt. Die Bibliothek wurde unter der +\textit{GNU Lesser General Public License} (LGPL) in der Version~2.1 +veröffentlicht; die Kommandozeilen-Programme, die in vielen Fällen lediglich +Funktionalität der Bibliothek auf der Kommandozeile zur Verfügung stellen, +stehen unter der \textit{GNU General Public License}, Version~2. Diese +Lizenzen räumen einem Benutzer weitreichende Rechte ein, unter anderem das +Programm beliebig zu verwenden, zu studieren, zu verändern sowie veränderte +und unveränderte Kopien zu veröffentlichen. + +Die Programmierschnittstelle (API) der Bibliothek orientiert sich an +Paradigmen der \textit{objektorientierten Programmierung}. Beispielsweise kann +mit der Funktion \texttt{sn\_network\_ create()} ein neues Zustands-Objekt +erzeugt werden, für das mehrere Manipulations-Methoden, zum Beispiel +\texttt{sn\_network\_comparator\_add()}, zur Verfügung stehen. Auf diese Art +und Weise kann die Bibliothek leicht erweitert werden, ohne dass bestehende +Programme angepasst werden müssen. + +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{42} zu erzeugen, kann folgendes Kommando verwendet +werden: +\begin{verbatim} + $ 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 +Grundprinzipien des UNIX-Be\-triebs\-sys\-tems. Es hat sich in den letzten +Jahrzehnten und beim Verfassen dieser Arbeit als sehr flexibel und mächtig +erwiesen. + +Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden, +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/} unentgeltlich heruntergeladen werden. + +\newpage +\bibliography{references} +\bibliographystyle{plain} %\listoffigures \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 :