X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=a1145c4d08b69f5f07959b53c5281a83afaaa450;hb=728535ac0e3596f77674a1084891d6bea2da65e4;hp=7652e83afea7f206cd21e86796a77da738e5cbbd;hpb=722308a3028582c1c3f88a17e3d21cb718f4084b;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 7652e83..a1145c4 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} @@ -19,7 +19,7 @@ % Fuer mathtoolsset \usepackage{mathtools} -\geometry{paper=a4paper,margin=25mm} +\geometry{paper=a4paper,margin=30mm} \pagestyle{fancy} %\fancyhf{} @@ -52,10 +52,25 @@ \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] +\tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10] \maketitle \begin{abstract} @@ -71,8 +86,8 @@ das hinbekomme bzw. Recht behalte.} \newpage \tableofcontents -\newpage +\newpage \section{Motivation und Einleitung} \subsection{Motivation}\label{sect:motivation} @@ -88,16 +103,16 @@ das hinbekomme bzw. Recht behalte.} \subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke} -{\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde -liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können. -Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den -Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf -dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang -ausgegeben. +\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 wird immer auf dem einen, die kleinere der beiden Zahlen +immer auf dem anderen Ausgang ausgegeben ausgegeben wird. -Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die -Ausgänge von {\em Komparatoren} mit dem Eingängen anderer {\em Komparatoren} -verbindet, erhält man ein {\em Komparatornetzwerk}. +Kombiniert man mehrere \emph{Komparatoren} miteinander, das heißt, dass die +Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind, +erhält man ein {\em Komparatornetzwerk}. \begin{figure} \begin{center} @@ -109,136 +124,276 @@ aus 5~Komparatoren.} \end{figure} Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches -Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise: -Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken -Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile -symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"' -vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die +\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 Übersichlichkeit +durch schwarze Punkte symbolisiert. + +Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in +das Netzwerk hineingegeben. Jeder Komparator vergleicht die Zahlen „auf“ den +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. - -Komparatornetzwerke, die für jede beliebige Eingabepermutation eine -Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen -{\em Sortiernetzwerke}. Das in +befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat. + +Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können +gleichzeitig angewandt werden. Das Beispiel in +Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und +vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine +Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man +eine \emph{Schicht} des Komparatornetwerks. Die \emph{Verzögerung} eines +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 kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe -${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar +ist \emph{kein} Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur +Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar zerstört. -Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft -{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel also einfach möglich. -Dieses Gegenbeispiel zu finden ist allerdings aufwendig. - -\todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein -Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines -Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?} -\todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig -ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben -können?} - -\todo{$0-1$-Prinzip} - -Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft -besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen -ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle -$2^n$~${0-1}$-Folgen sortiert. - -Sortiernetzwerke: -\begin{itemize} -\item Ein Komparator-Netzwerk ist $\ldots$ -\item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$ -\item Die Frage nach der Sortiereigenschaft ist NP-vollständig. -\end{itemize} +\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} möglich. + +Beispielsweise sortiert das 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} + +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 entsprechen der Annahme von +Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das +Verhalten jedes einzelnen Komparators nicht, so dass die Annahme auf einen +Widerspruch geführt wird. + +Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der +Komplexitätsklasse +$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, +ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$ +verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein +schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen, +ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt, +sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für +aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung +eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa +4,3~Millarden Tests notwendig, die einen Rechner durchaus mehrere Minuten +beschäftigen. \subsubsection{Evolutionäre Algorithmen} Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse -$NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte -sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$ -liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese -Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese -Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer -Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit -praktikablen Zeitkonstanten gefunden werden. +\textit{NP}, das heißt das keine Verfahren bekannt sind, die das Problem +effizient exakt lösbar. Sollte sich herausstellen, dass diese Probleme nicht +in der Komplexitätsklasse~\textit{P} liegen, wäre eine Konsequenz, dass es +effiziente exakte Algorithmen für diese Probleme nicht geben kann. Falls sich +hingegen herausstellt, dass diese Probleme in der +Komplexitätsklasse~\textit{P} liegen, wird es mit großer Wahrscheinlichkeit +noch einige Zeit dauern, bis auch Algorithmen mit praktikablen Zeitkonstanten +gefunden werden. Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt -die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus -zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser -Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur, -beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen +die beziehungsweise eine der {\em optimalen} Lösungen als einzige Ausgabe des +Algorithmus zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele +dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur, +beispielsweise imitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen. Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee -ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu +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 häufig -als {\em Individuum} bezeichnet. +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 +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 -integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em -Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise -werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em +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. Zum anderen muss eine -Methode für die Rekombination existieren. Das insbesondere dann problematisch -wenn {\em Nebenbedingungen} eingehalten werden müssen. - -\begin{itemize} -\item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$ -\item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die -Mutation \textit{(vermutlich)} nicht (effizient) möglich. -\end{itemize} +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. + +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 \textit{Exploration} kann von einem weiteren Mechanismus unterstützt +werden, der ebenfalls der Evolutionslehre entliehen ist, der \emph{Mutation}. +Dabei werden Lösungen zufällig verändert, so dass auch andere Lösungen „in der +Nähe“ von direkten Nachfolgern erreicht werden können. Das hilft insbesondere +bei der intensiven Suche in der Nähe eines lokalen Optimums aber auch beim +„Ausbrechen“ und finden noch besserer Lösungen. + +Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit +verbunden, dass anschließend die Sortiereigenschaft des resultierenden +\emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das +Hinzufügen eines zufälligen Komparators diese Eigenschaft zerstören kann. Beim +Suchen möglichst effizienter Netzwerke ist natürlich das zufällige Entfernen +von Komparatoren interessanter, was die Sortiereigenschaft sehr oft aufhebt. + +Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht +die \emph{Sortiernetzwerke} selbst, sondern verzichten auf Mutation oder +mutieren lediglich Transformationen von Sortiernetzwerken, die die +Sortiereigenschaft erhält. Transformationen von Sortiernetzwerken werden in +Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der Mutation +einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt. +\newpage \section{Bekannte konstruktive Sortiernetzwerke} +\label{sect:konstruktive_netzwerke} Übersicht über bekannte konstruktive Sortiernetzwerke. -\subsection{Odd-Even-Transpositionsort} +\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 +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 {\em Odd-Even-Transpositionsort} Netzwerk für acht Eingänge.} -\label{fig:odd_even_transposition_08} + \begin{center} + \input{images/oe-transposition-8.tex} + \end{center} + \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.} + \label{fig:odd-even-transposition-08} \end{figure} -\subsection{Batcher's Mergesort} - -Ein Netzwerk von K.~E.~Batcher. Siehe: -K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring -Joint Comput. Conf., Vol. 32, 307-314 (1968) -\todo{Bibtex!} +Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe +Eingabe sortiert ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass +sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene +Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt. Beim +Odd-Even-Transporitionsort-Netzwerk mit drei Eingängen, +$\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert. + +Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen, +indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch +Herausschneiden einer Leitung reduziert. In +Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail +beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das +Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. + +Das Odd-Even-Transporitionsort-Netzwerk ist weder in Bezug auf die Anzahl der +Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die +Komparatoren anordnen lassen, effizient. Es benötigt +${\frac12 n (n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten +angeordnet sind. Andere Sortiernetzwerke benötigen deutlich weniger +Komparatoren, beispielsweise $\mathcal{O}(n (\log n)^2)$, die in weniger +Schichten, zum Beispiel $\mathcal{O}(\log n)$, angeordnet sind. + +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. + +\subsection{Das bitone Mergesort-Netzwerk} + +Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein +Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968} +veröffentlicht wurde. Es ist deutlich effizienter als das +Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der +Komparatoren als auch bezüglich der benötigten Zeit, also der Anzahl der +Schichten. + +Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei +sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser +\emph{„bitoner Mischer“} (englisch: \textit{bitonic merger}) genannte Baustein +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 Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk, -das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine -{\em bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton -fallenden Folge, oder ein zyklischer Shift davon. -Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinipiellen Möglichkeiten -die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für -Batcher's Mergesort-Netzwerk zeigen die Abbildungen~\ref{fig:beispiel-biton-0} +Das \emph{bitone Mergesort-Netzwerk} basiert auf dem sogenannten \emph{bitonen +Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine beliebige +\emph{bitone Folge} in eine sortierte Listen umordnen kann. Eine \emph{bitone +Folge} ist eine monoton steigende Folge gefolgt von einer monoton absteigenden +Folge, oder ein zyklischer Shift davon. Abbildung~\ref{fig:beispiel-biton} +zeigt die vier prinzipiellen Möglichkeiten die durch zyklische Shifts +entstehen können. Die wichtigsten Varianten für das \emph{bitone +Mergesort-Netzwerk} zeigen die Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und -eine absteigend sortierte Liste aneinanderhängt. Bei den -anderen beiden Formen ist wichtig zu beachten, dass das letzte Element nicht -größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner +eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen +ist wichtig zu beachten, dass das letzte Element nicht größer +(Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein darf. @@ -265,9 +420,9 @@ darf. \end{figure} Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je -${m = \frac{n}{2}}$~Elementen, ${u_0, u_1, \ldots, u_{m-1}}$ und -${v_0, v_1, \ldots, v_{m-1}}$. Die Folge der $u_i$ sei aufsteigend sortiert, -die Folge der $v_i$ sei absteigend sortiert: +${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} @@ -284,27 +439,73 @@ 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 die entstehende Folge aus -zwei bitonen Folgen besteht, die rekursiv zusammengeführt werden können. -Abbildung~\ref{fig:bitonic-merge-normal} zeigt die Situationen vor und nach -diesem Schritt des Mischers. - -Mit dem bitonen Mischer auch zwei aufsteigend sortierte Folgen sortiert -werden. Dazu ist lediglich das "`Umbenennen"' der Leitungen notwendig. -Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das Schema des bitonen -Mischers für zwei aufsteigend sortierte Foglen. Durch das Umbenennen verändert -sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das -Muster nun an einen Trichter. - -\subsubsection{Batcher's Bitonic-Mergesort-Netzwerk} - -Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von -$S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen, und dem bitonen -Mischer $M(n)$. Die Rekursion bricht bei ${n = 1}$~ab -- eine einelementige -Liste ist immer sortiert. -Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen. -Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot) -sowie der bitone Mischer~$M(8)$ (blau). +"`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass 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. + +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 bitonen Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist +lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt +notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine +„echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das +Schema des bitonen Mischers für zwei aufsteigend sortierte Foglen. Durch das +Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig: +Statt an eine Treppe erinnert das Muster nun an einen Trichter. + +Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet +die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden +$\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus +$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren +besteht, die in $\log(n)$~Schichten angeordnet werden können. + +\subsubsection{Das bitone Mergesort-Netzwerk} + +Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone +Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich +zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe, +$\operatorname{BS}(\frac{n}{2})$, für je die Hälfte der Eingänge, sowie dem +bitonen Mischer für $n$~Leitungen, $\operatorname{BM}(n)$. Das Rekursionsende +ist das bitone Mergesort-Netzwerk mit nur einer Leitung, +$\operatorname{BS}(1)$, welches als leeres Komparatornetzwerk definiert ist. +Entsprechend sind die Komparatornetzwerke $\operatorname{BM}(2)$ und +$\operatorname{BS}(2)$ identisch. + +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{$\operatorname{BS}(8)$, Batchers {\em bitones Mergesort-Netzwerk} + für acht Eingänge. Markiert sind die beiden Instanzen von + $\operatorname{BS}(4)$ (rot), die beiden bitonen + Mischer~$\operatorname{BM}(4)$ (blau) und die Komparatoren, die im letzten + rekursiven Schritt hinzugefügt wurden (grün).} + \label{fig:bitonic-08} +\end{figure} + +Das konkrete Netzwerk~$\operatorname{BS}(8)$ ist in +Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die +beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone +Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade, +die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist +grün hinterlegt. + +Das \emph{bitone Mergesort-Netzwerk} $\operatorname{BS}(8)$ besteht aus +$\frac{1}{4} n \log(n) \log(n+1) = \mathcal{O}\left(n (log (n))^2\right)$ +Komparatoren, die in $\frac{1}{2} \log(n) \log(n+1) = \mathcal{O}(\log(n))$ +Schichten angeordnet sind. %\begin{figure} %\begin{center} @@ -315,33 +516,28 @@ sowie der bitone Mischer~$M(8)$ (blau). %\label{fig:bms_rekursiver_aufbau} %\end{figure} -\begin{figure} - \begin{center} - \input{images/batcher-8.tex} - \end{center} - \caption{$S(8)$, Batcher's {\em bitone Mergesort-Netzwerk} für acht - Eingänge. Markiert sind die beiden Instanzen von $S(4)$ (rot), die beiden - bitonen Mischer~$M(4)$ (blau) und die Komparatoren, die im letzten rekursiven - Schritt hinzugefügt wurden (grün).} - \label{fig:batcher_08} -\end{figure} +\subsection{Das Odd-Even-Mergesort-Netzwerk} -\subsection{Odd-Even-Mergesort} +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. -Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und -{\em Odd-Even-Transpositionsort} (OET, siehe -Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses -Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen -"`Mischer"' definiert. +\subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer} -\subsubsection{Der Odd-Even-Mischer} +Der \emph{Odd-Even-Mischer} $\operatorname{OEM}(n,m)$ ist ein +Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ +Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen +zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der +\emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer} +vorgestellt wurde. Allerdings benötigt der \emph{Odd-Even-Mischer} unter +Umständen mehr Schichten als der \emph{bitone Mischer}.~\cite{KNUTH} -Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte -Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit -weniger Vergleichen aus als der {\em bitone Mischer}, der im -Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde. - -Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die +Der \emph{Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei @@ -364,8 +560,8 @@ w_i = \left\{ \begin{array}{ll} \label{fig:oe-merge} \end{figure} -Diese werden jetzt in insgesamt vier sortierte Folgen aufgeteilt, je eine -Liste der geraden Indizes und je eine Liste der ungeraden Indizes. +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) \\ @@ -403,11 +599,11 @@ Aufbau lauten: \end{itemize} Dass die resultierende Folge sortiert ist, lässt sich mit dem -{\em 0-1-Prinzip} leicht zeigen: +{\em 0-1-Prinzip} zeigen: Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder gleich der Anzahl der Nullen in den ungeraden Teilfolgen -$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ -- die Einsen verhalten +$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu: \begin{eqnarray} @@ -425,10 +621,11 @@ $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu: 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}}$ $2$~Nullen mehr enthählt als -$W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu -sortieren. Die jeweiligen Situationen sind in -Abbildung~\ref{fig:oe-post-recursive} dargestellt. +wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthählt als +$W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die +Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte +Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind +in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \begin{figure} \centering @@ -445,45 +642,255 @@ Abbildung~\ref{fig:oe-post-recursive} dargestellt. \label{fig:oe-post-recursive} \end{figure} +Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden, +bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$ +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, ist Gemäß der rekursiven Definition in +Abhängigkeit der Länge der Eingabefolgen, $n$ und $m$: +\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 $\mathcal{O}(N \log (N))$ enthalten ist. + +Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$, lässt sich die Anzahl +der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der erste +Rekursionsschritt der OEM-Konstruktion fügt +$\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} -Auch beim {\em Odd-Even-Mergesort-Netzwerk} -- wie beim {\em bitonen -Mergesort-Netzwerk} -- entsteht das Sortiernetzwerk aus dem {\em -Odd-Even-Mischer} durch resursives Anwenden auf einen Teil der Eingabe -(üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen. -Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge. +Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht --~wie +das \emph{bitone Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von +sich selbst und einem abschließenden \emph{Odd-Even-Mischer}. Die +effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl +entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht +$\operatorname{OES}(n)$ aus +$\operatorname{OES}\left(\left\lceil\frac{n}{2}\right\rceil\right)$, +$\operatorname{OES}\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$ +und $\operatorname{OEM}\left(\left\lceil\frac{n}{2}\right\rceil, +\left\lfloor\frac{n}{2}\right\rfloor\right)$. Die Rekursion endet mit +$\operatorname{OES}(1)$ und $\operatorname{OES}(0)$, die als leere +Komparatornetzwerke definiert sind. \begin{figure} -\begin{center} -\input{images/oe-mergesort-8.tex} -\end{center} -\caption{Das {\em Odd-Even-Mergesort} Netzwerk für acht Eingänge.} -\label{fig:odd_even_mergesort_08} + \begin{center} + \input{images/oe-mergesort-8.tex} + \end{center} + \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert + sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden + \emph{Odd-Even-Mischer} $\operatorname{OEM}(4)$ für gerade und ungerade + Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten + Komparatoren zwischen benachbarten Leitungen (grün).} + \label{fig:odd-even-mergesort-08} \end{figure} -\begin{itemize} -\item Odd-Even-Transpositionsort -\item Bitonic-Mergesort -\item Odd-Even-Mergesort -\item Pairwise sorting-network -\end{itemize} +In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk +$\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven +Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den +\emph{Odd-Even-Mischer} für acht Leitungen dar: Die beiden blauen Blöcke sind +die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert +die Komparatoren, die in 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} +Eine geschlossene Form dieser Formel ist schon alleine deshalb schwierig, weil +sie für $K(n,m)$ schwierig anzugeben ist. Es ist allerdings bekannt, dass +$k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist. + +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} +\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, das in +Abschnitt~\ref{sect:leitungen_entfernen} beschrieben wird, kann es vorkommen, +dass die Komparatoren eines Sortiernetzwerks nicht mehr in der +kleinstmöglichen Anzahl von \emph{Schichten} angeordnet sind. Unter +\emph{Komprimierung} wird eine (Neu-)Gruppierung der Komparatoren verstanden, +die jeden Komparator so früh wie möglich ausführt. So entsteht die +kleinstmögliche Anzahl von \emph{Schichten}, in die sich ein Sortiernetzwerk +unterteilen lässt. + +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 angewandt werden. Deshalb sollte vor einer Bewertung, die +die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine +Komprimierung durchgeführt werden. + +\subsection{Normalisieren} -\begin{itemize} -\item Komprimieren (Alle Komparatoren so früh wie möglich anwenden). -\item Normalisieren (Transformation zu Standard-Sortiernetzwerken). -\end{itemize} +\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. Jedes Sortiernetzwerk kann in eine normaliesierte Variante +transformiert werden. Dazu gibt beispielsweise \emph{Donald~E. Knuth} +in~\cite{KNUTH} einen Algorithmus an. + +Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das +bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd} +zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch +Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden +die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei +Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist. +In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven +Definition. + +In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen +Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche +Richtung. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen- +und das Trichtermuster zu sehen. \subsection{Zwei Netzwerke kombinieren} -\begin{itemize} -\item Mit dem Bitonic-Merge -\item Mit dem Odd-Even-Merge -\item Nach dem Pairwise sorting-network Schema. -\end{itemize} +Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden +zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen +Sortiernetzwerk zusammenzufassen. + +Wir haben diese Technik in den vorangegangen Abschnitten bereits verwendet, +beispielsweise um zwei \emph{bitone Mergesort-Netzwerke} mit jeweils der +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 man die Ausgabe von zwei \emph{bitonen +Mergesort-Netzwerken} $\operatorname{BS}(8)$ mit je acht Leitungen mit dem +\emph{Odd-Even-Merge} $\operatorname{OEM(8,8)}$ zu einer sortierten +Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt +73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt +80~Komparatoren, $\operatorname{OES}(16)$ nur 63). + +Verbesserungen in der Anzahl der benötigten Komparatoren beziehungsweise der +Schichten eines „kleinen“ Sortiernetzwerks übertragen sich direkt auf das +resultierende Gesamtnetzwerk. Das \emph{Odd-Even-Mergesort-Netzwerk} +$\operatorname{OES}(9)$ benötigt beispielsweise 26~Komparatoren, die in in +neun Schichten angeordnet sind. Es sind allerdings Sortiernetzwerke mit neun +Eingängen bekannt, die lediglich 25~Komparatoren in sieben Schichten +benötigen. Kombiniert man zwei dieser Netzwerke mit dem +\emph{Odd-Even-Mischer} erhält man ein Sortiernetzwerk mit 18~Eingängen, das +80~Komparatoren in 11~Schichten benötigt -- $\operatorname{OES}(18)$ benötigt +82~Komparatoren in 13~Schichten. Damit ist das resultierende Netzwerk so +schnell wie das Sortiernetzwerk mit 18~Eingängen, das \textit{Sherenaz~W. +Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer Arbeit „An 11-Step +Sorting Network for 18~Elements“~\cite{BB2009} vorstellen, benötigt aber +6~Komparatoren weniger. + +% 9 9 +% 9 18 +% 9 27 +% 9 36 +% 9 45 +% 8 53 +% 8 61 +% 7 68 +% 7 75 +% 6 81 +% 5 86 + +Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung +ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits +sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine +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. + +%\begin{itemize} +%\item Mit dem Bitonic-Merge +%\item Mit dem Odd-Even-Merge +%\item Nach dem Pairwise sorting-network Schema. +%\end{itemize} \subsection{Leitungen entfernen} +\label{sect:leitungen_entfernen} + +Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von +\emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen +ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen +beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass +sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein +Sortiernetzwerk mit $n$~Eingängen erhalten müssen. + +Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein +Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung +„eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem +bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim +durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der +„Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index. +Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche +dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden +Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die +Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch +das {\em Odd-Even-Transpositionsort-Netzwerk}. \begin{figure} \centering @@ -491,20 +898,350 @@ Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge. \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}} \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}} \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}} - \caption{Eine Leitung wird aus dem {\em Odd-Even-Transpositionsort} Netzwerk - $\textrm{OET}(8)$ entfernt: Auf der rot markierten Leitung wird $\infty$ - angelegt. Da der Wert bei jedem Komparator am unteren Ende herauskommt, ist - der Pfad fest vorgegeben. Da die restlichen Werte trotzdem noch richtig - sortiert werden müssen, kann dieser Pfad herausgetrennt werden. In der - letzten Abbildung ist $\textrm{OET}(7)$ markiert.} + \caption{Eine Leitung wird aus dem + \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(8)$ entfernt: + Auf der rot markierten Leitung wird $\infty$ angelegt. Da der Wert bei jedem + Komparator am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die + restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser + Pfad herausgetrennt werden. In der letzten Abbildung ist + $\operatorname{OET}(7)$ markiert.} + \label{fig:oe-transposition-cut} +\end{figure} + +Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw. +ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt +haben, werden ersatzlos gelöscht. Diese Komparatoren sind in +Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die +zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen +ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise +das Maximum angenommen wird, die an unterster oder oberster Stelle endet und +auf die keine Komparatoren mehr berührt +(Abbildung~\ref{fig:oe-transposition-cut1}). + +Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen +Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position +des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die +Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt. +Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme +auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage +getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste +mit $(n-1)$~Elementen darstellen. + +Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen +(Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für +$(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein +Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als +\emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}. + +Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das +Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot +markierten Komparatoren wurden verschoben, so dass sich eine kompaktere +Darstellung ergibt. Ausserdem ist das +{\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der +zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die +Ausgabe und kann entfernt werden. + +\subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster} +\label{sect:anzahl_schnittmuster} + +Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem +Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$, +$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und +Weise einen Sortiernetzwerke mit $2n$~Eingängen wieder auf Sortiernetzwerke +mit $n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die +nacheinander angewendet ein $n$-Sortiernetzwerk auf ein +${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als +\emph{$k$-Schnittmuster}. + +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{equation}\label{eqn:anzahl_schnittmuster} + \prod_{i=n}^{1+n-k} 2i = 2^k \frac{n!}{(n-k)!} + \quad (n > m) +\end{equation} +\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle +unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung +und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks, +führen beide Reihenfolgen zum selben Ergebnis. + +\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass es +möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum +vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, +die Menge der so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die +Anzahl der möglichen Schnittmuster setzt sich zusammen aus der Anzahl von +Möglichkeiten, $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen +Minimum-~/ Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl +der möglichen Schnittmuster: +\begin{displaymath} + 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right) + = 2^{k} \cdot \frac{n!}{k! (n-k)!} + = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!} + \quad (1 \leqq k < n) +\end{displaymath} + +Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden +Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf +ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit +16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$ +Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große +Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich. + +Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner +als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der +ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide +Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und +unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen +der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die +Werte unterscheiden. + +Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe +Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des +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 360 216,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 +$\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{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~\ref{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 leider nicht sinnvoll durchführbar. +Die Hashtabelle benötigt mehr Arbeitsspeicher als in derzeitigen Rechnern +vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für +„kleine“ x-Werte verlässt. + +Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu +können, kann man sich einer stochastischen Methode bedienen, der sogenannten +\emph{Monte-Carlo-Methode}. Zunächst generiert man eine Menge~$S$ von +$k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster +zufällig erzeugt und überprüft, ob sie sich in der Menge~$S$ enthalten sind. +Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in +$S$ enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der +unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der +unterschiedlichen Schnittmuster abschätzen. + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/collisions-10000-1000000-32.pdf} + \end{center} + \caption{Abschnä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} +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 Schnittmustern für $\operatorname{OES}(32)$ und +$3,4 \cdot 10^6$ für $\operatorname{BS}(32)$. + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf} + \end{center} + \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der + \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} + +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. In einem kombinierten Graphen hätte +man keine Details mehr erkennen können. Aufgrund der hohen Anzahl +unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit +$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen +Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385 +Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent +sind. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$ +unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den +vorherigen Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als +die Anzahl der \emph{möglichen} Schnittmuster. + +\newpage +\section{Der \textsc{SN-Evolution}-Algorithmus} + +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 Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele, +die bei Sortiernetzwerken verfolgt werden können: \begin{itemize} -\item Min-Richtung -\item Max-Richtung + \item Möglichst wenige Komparatoren („effizient“) + \item Möglichst wenige Schichten („schnell“) \end{itemize} -\section{Der evolutionäre Ansatz} +Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das +effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus +60~Komparatoren in 10~Schichten. Das schnellste Netzwerk besteht aus +61~Komparatoren in nur 9~Schichten. + +Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"' +berücksichtigen kann, hat die folgende allgemeine Form: +\begin{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 verrennt. Leider gibt es +kein Patentrezept für die Wahl der Parameter, so dass für verschiedene +Leitungszahlen und Mischer-Typen experimentiert werden muss. + +\subsection{Selektion} + +Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere +Wahrscheinlichkeit haben, zur nächsten Generation beizutragen. Diese +Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das +Streben des Algorithmus nach besseren Lösungen. + +Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint, +ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der +Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. + +Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von +Pseudocode wie folgt beschreiben: +\begin{verbatim} +Guetesumme := 0 +Auswahl := (leer) + +fuer jedes Individuum in Population +{ + reziproke Guete := 1.0 / Guete(Individuum) + Wahrscheinlichkeit P := reziproke Guete / (reziproke Guete + Guetesumme) + Guetesumme := Guetesumme + reziproke Guete + + mit Wahrscheinlichkeit P + { + Auswahl := Individuum + } +} +gebe Auswahl zurueck +\end{verbatim} + +\subsection{Rekombination} + +Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu +einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel +den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den +{\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die +beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen. +Anschließend entfernen wir zufällig $n$~Leitungen wie in +Abschnitt~\ref{sect:leitungen_entfernen} beschrieben. + +Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft +erhält. + +\subsection{Mutation} + +Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation +--~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein +Sortiernetzwerk zufällig zu verändern aber trotzdem 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. + +Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären +Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die +Population überprüft das Programm die Notwendigkeit jedes einzelnen +Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft, +ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt. \begin{itemize} \item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der @@ -528,7 +1265,7 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} \begin{center} \input{images/08-e2-1237993371.tex} \end{center} -\caption{\tt images/08-e2-1237993371.tex} +\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten} \label{fig:08-e2-1237993371} \end{figure} @@ -536,7 +1273,7 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} \begin{center} \input{images/09-e2-1237997073.tex} \end{center} -\caption{\tt images/09-e2-1237997073.tex} +\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten} \label{fig:09-e2-1237997073} \end{figure} @@ -544,26 +1281,314 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} \begin{center} \input{images/09-e2-1237999719.tex} \end{center} -\caption{\tt images/09-e2-1237999719.tex} +\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} + \subsection{Güte} \begin{itemize} -\item So gut kann man mindestens werden \em{($\rightarrow$ Bitonic-Mergesort, -vermute ich)}. +\item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}. \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab. +\item Ggf. Abschnitt „Shmoo-Äquivalenz“ kürzen und hier einbauen. +\end{itemize} + +%\input{shmoo-aequivalenz.tex} + +\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 die \emph{Schnittmuster} +als Individuen. Um zwei Individuen zu rekombinieren werden die ersten +$r$~Schnitte des einen Schnittmusters verwendet und die letzten +${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit +$0 \leqq r \leqq c$. + +Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig +auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die +Schnitt-Richtung. + +\subsection{Versuche mit dem bitonen Mergesort-Netzwerk} + +In \cite{MW2010} zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka}, +wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde, +durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen +Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer +sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert +werden, Komparatoren ein. + +Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein +Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer +konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger +als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers +Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$ +Komparatoren ein. + +\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 bitonen Mergesort-Netzwerk +$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der +Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein +16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den +Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized} +zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$ +und das +${\operatorname{MIN}(0,5,9,11,15,17,20,22,26,29,30)}$-${\operatorname{MAX}(2,4,13,19,24)}$-Schnittmuster, +das durch \textsc{SN-Evolution-Cut} gefunden wurde. +Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk +nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine +Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in +diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des +Netzwerks scheinen rein zufällig zu sein. + +\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} + +Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen +Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk +konstruiert haben, kann demnach auch erreicht werden, wenn +$\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen +Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein +32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden, +wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode +konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den +optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf +208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte +Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller +dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die +Verzögerung dieser Sortiernetzwerke gleich ist. + +Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr +unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für +gute Schnittmuster anzugeben. + +Entscheidend für das Ergebnis eines Schnittmusters scheint beim bitonen +Mergesort-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein. +Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in +Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 +ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten +ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich +die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks +leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und +der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden. + +Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur +haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere +von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem +\emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und +$m$~Schnitten gestartet, so ist das beste Ergebnis immer das +$\operatorname{OET}(n-m)$-Netzwerk. + +\begin{figure} + \begin{center} + \input{images/16-ec-from-ps32.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} + $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} + \label{fig:16-ec-from-ps32} +\end{figure} + +\subsection{Versuche mit dem Pairwise-Sorting-Netzwerk} + +Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk} +$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The +Pairwise Sorting Network“ \cite{P1992} definiert. Startet man +\textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe, +16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche +Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und +$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in +Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. + +Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht +einsetzt und auch nicht auf einem Mischer basiert, ist der +$\operatorname{OEM}(8,8)$ im Sortiernetzwerk in +Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In +den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die +strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die +Schichten~1 und~2 sowie 4~und~5 sind vertauscht. + +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\ + \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} + +\begin{figure} + \begin{center} + \input{images/32-pairwise-cut-16-pairwise.tex} + \end{center} + \caption{PS(32) mit 16 Schnitten zu PS(16).} + \label{fig:ps16-from-ps32} +\end{figure} + +\begin{figure} + \begin{center} + \input{images/16-pairwise.tex} + \end{center} + \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten + ($\operatorname{MIN}(0,2,4,6), \operatorname{MAX}(9,11,13,15)$). Das + resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.} + \label{fig:16-pairwise} +\end{figure} + +Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann +man $\operatorname{OES}(8)$ erhalten. + +\subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk} + +\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.} + +\begin{itemize} + \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort. + \item Wie gut kann man durch wegschneiden werden? + \item Wieviele Schnitte ergeben das selbe Netzwerk? Oder andersrum: Wieviele + unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein + Netzwerk / Knoten in der Markov-Kette? + \item Abschnitt „Optimierung der Schnitte“ hier einbauen. \end{itemize} -\subsection{Vom evolutionären Algorithmus zu einer Markov-Kette} +\newpage +\section{Der \textsc{SN-Markov}-Algorithmus} +\label{sect:markov} + +Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen +Abschnitt verwendete immer zwei zufällige Sortiernetzwerke („Individuen“) aus +einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander +ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal +verwendet und mit sich selbst kombiniert wird. + +Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das +aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller +Leitungen eliminiert, lassen sich einige interessante Beobachtungen anstellen. +Netzwerke, die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von +$S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen +hervorgehen können, heißen \emph{Nachfolger} von $S_0$. + +Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem +(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei +Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer +Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von +$S_0$ ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich +selbst erzeugen kann. + +Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl +(unterschiedlicher) Schnittmuster und damit die Anzahl der Nachfolger sehr +groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis +zu +\begin{displaymath} + 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right) +\end{displaymath} +Nachfolger. + +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. \begin{itemize} -\item Kombiniere immer das aktuelle Netzwerk mit sich selbst. -\item Kann die Mindestgüte immernoch erreicht werden? ({\em Ich denke schon.}) -\item Anzahl der erreichbaren Sortiernetzwerke. + \item $n \leftarrow \mathrm{Input}$ + \item \texttt{while} \textit{true} + \begin{itemize} + \item $n \leftarrow \operatorname{recombine} (n, n)$ + \end{itemize} \end{itemize} +\begin{itemize} + \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}). + \item Anzahl der erreichbaren Sortiernetzwerke. + \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen + Netzwerke. (Abbildung~\ref{fig:markov-comparators-16}) +\end{itemize} + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf} + \end{center} + \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen), + die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die + \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.} + \label{fig:markov-comparators-12} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 360 216,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 360 216,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} + +\newpage \section{Empirische Beobachtungen} \begin{itemize} @@ -571,12 +1596,19 @@ vermute ich)}. \item $\ldots$ \end{itemize} +\newpage \section{Ausblick} Das würde mir noch einfallen$\ldots$ -%\bibliography{references} -%\bibliographystyle{plain} +\newpage +\section{Implementierung} + +So habe ich die ganzen Versuche durchgeführt. + +\newpage +\bibliography{references} +\bibliographystyle{plain} %\listoffigures