X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=25d6329db092daf40bb3a9311a9c98991c8b7818;hb=678969a72ce687ffdfcb64e9ec8a2f60ad7266c9;hp=6df6048aa637e8eb1c48bcd3f7051962fa626021;hpb=9c25159564439e81b2d237ef32e5697211a63774;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 6df6048..25d6329 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} @@ -52,6 +52,21 @@ \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] @@ -71,8 +86,8 @@ das hinbekomme bzw. Recht behalte.} \newpage \tableofcontents -\newpage +\newpage \section{Motivation und Einleitung} \subsection{Motivation}\label{sect:motivation} @@ -193,7 +208,7 @@ 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 +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 @@ -203,13 +218,35 @@ 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. +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. + \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} +\newpage \section{Bekannte konstruktive Sortiernetzwerke} +\label{sect:konstruktive_netzwerke} Übersicht über bekannte konstruktive Sortiernetzwerke. @@ -253,7 +290,7 @@ 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 (einfaches) Sortiernetzwerk als +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. @@ -263,7 +300,7 @@ Algorithmen. 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-Transporitionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der +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. @@ -273,8 +310,8 @@ sortierte Listen zusammenfügen (englisch: \textit{to~merge}) kann. Dieser verleiht dem Sortiernetzwerk seinen Namen. Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die -Instanzen des Netzwerks, deren Leitungszahl eine Zweierpotenz ist, -$\operatorname{BS}(n = 2^t)$. +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} @@ -383,15 +420,16 @@ alle Komparatoren in die gleiche Richtung zeigen. \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} + \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:batcher_08} zu sehen. Eingezeichnet sind ebenfalls die +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 @@ -418,8 +456,9 @@ Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort-Netzwerk} 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{K.~Batcher} gefunden worden und wird rekursiv durch einen Mischer -definiert. +\textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968} +beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht +darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist. \subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer} @@ -429,8 +468,7 @@ 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}.\footnote{Knuth, -“Bitonic Sorting”, Seite~230} +Umständen mehr Schichten als der \emph{bitone Mischer}.~\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 @@ -579,8 +617,8 @@ benötigt werden. \subsubsection{Das Odd-Even-Mergesort-Netzwerk} -Das \emph{Odd-Even-Mergesort-Netzwerk} $\operatorname{OES}(n)$ besteht, --~wie -das \emph{bitonen Mergesort-Netzwerk}~-- rekursiv aus kleineren Varianten von +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 Bezuf auf Komparator- und Schichtzahl entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht @@ -624,8 +662,8 @@ 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{K.~Batcher} -zeigt in seiner Arbeit\footnote{\todo{Referenz!}}, dass in diesem Fall +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} @@ -640,6 +678,7 @@ gilt. %\item Pairwise sorting-network %\end{itemize} +\newpage \section{Transformation von Sortiernetzwerken} \subsection{Komprimieren} @@ -723,9 +762,10 @@ 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{Baddar} und -\textit{Batcher} in ihrer Arbeit „An 11-Step Sorting Network for 18~Elements“ -vorstellen, benötigt aber 6~Komparatoren weniger. +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 @@ -824,160 +864,174 @@ Darstellung ergibt. Ausserdem ist das 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 wir auf diese Art und -Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk -mit $n$~Eingängen reduzieren. +$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}. -\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus} +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 $m$-Sortiernetzwerk zu reduzieren, ergeben -sich insgesamt -\begin{displaymath} - \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!} +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{displaymath} -Möglichkeiten. Diese Möglichkeiten 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 Schnitte -reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber -unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus -der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen, -und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende -Formel: +\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^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right) - = 2^{n-m} \cdot \frac{n!}{(n-m)! m!} - = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!} - \quad (n > m) + 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 Schnitte wird mit der Anzahl der zu entfernenden +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~Ein\-gängen zu reduzieren sind 16~Schnitte notwendig, -für die 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. - -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{Schnitt-Sequenzen} als Individuen. Eine \emph{Schnitt-Sequenz} ist eine -Liste mit $c$~Schnitten, die jeweils durch die Start-Leitung und die Richtung -\textit{Min} beziehungsweise \textit{Max} gegeben ist. Der Algorithmus wendet -jeden Schnitt einzeln an, so dass eine Leitungsnummer mehrfach in einer -Schnittsequenz vorkommen kann. Die höchste zulässige Leitungsnummer ist -abhängig von der Position des Schnitts in der Sequenz. Der Schnitt an -Position~$i$ darf höchstens die Leitungsnummer~${n-i-1}$ -enthalten.\footnote{Die niedrigste Leitungsnummer ist $0$, die höchste -Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.} - -Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen -Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten -Sequenz. $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. - -In ihrer Arbeit \textit{“Improving Bitonic Sorting by Wire Elimination”} -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. +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} - \input{images/16-ec-1277186619.tex} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/count-cuts-16.pdf} \end{center} - \caption{{\tt images/16-ec-1277186619.tex}: 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-1277186619} + \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} -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 -Abbildung~\ref{fig:16-ec-1277186619} zu sehen. +Um die Anzahl der \emph{unterschiedlichen} Schnittmuster abschätzen zu können, +wurden je eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke +$\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und $\operatorname{PS}(16)$ +angewandt. 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 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. 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} - \input{images/16-ec-from-ps32.tex} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf} \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} + \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} -Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so -ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ -erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein -zufällig zu sein. Dies ist jedoch kein Eigenschaft des Algorithmus, sondern -hängt insbesondere von der Eingaben. 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. - -Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk} -$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The -Pairwise Sorting Network“ 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)$. Der Algorithmus gibt -auch nach zahlreichen Versuchen nur eines von zwei Sortiernetzwerken zurück, -die beide sehr symmetrisch sind und eine saubere Struktur aufweisen. Eines der -beiden Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} -dargestellt, das andere Sortiernetzwerk unterscheidet sich lediglich dadurch, -dass die zweite und dritte Schicht vertauscht sind. - -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 -- die Schichten~1 und~2 -sowie 4~und~5 sind vertauscht, was jeweils zum selben Ergebnis nach dem -Schichtenpaar führt. +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)$. -Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann -man $\operatorname{OES}(8)$ erhalten. +\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} -\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? - \item Abschnitt „Optimierung der Schnitte“ hier einbauen. -\end{itemize} +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} Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden @@ -1001,7 +1055,7 @@ in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"' berücksichtigen kann, hat die folgende allgemeine Form: \begin{equation} - \mathit{Guete}(S) = w_{\mathrm{Basis}} + \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} @@ -1110,15 +1164,220 @@ acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.} \begin{itemize} \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} -\section{Markov-Kette} +\newpage +\section{Der \textsc{SN-Markov}-Algorithmus} -Der evolutionäre 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. +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 @@ -1128,17 +1387,26 @@ $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 +(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 +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. -Der Algorithmus {\sc SN-Markov} legt auf diesem 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 er das aktuelle Sortiernetzwerk mit sich selbst und erhält so -einen zufälligen Nachfolger. +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 $n \leftarrow \mathrm{Input}$ @@ -1157,108 +1425,35 @@ einen zufälligen Nachfolger. \begin{figure} \begin{center} - \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf} \end{center} - \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.} - \label{fig:markov-comparators-16} + \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} -%\input{shmoo-aequivalenz.tex} - -\section{Optimierung der Schnitte} - -\todo{In den Abschnitt "`Leitungen entfernen"' einbauen.} - \begin{figure} -\begin{center} -\input{images/32-ec-1277190372.tex} -\end{center} -\caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen - und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution-Cut} aus dem Bitonic-Mergesort-Netzwerk $BS(64)$ durch - 32~Schnitte erzeugt.} -\label{fig:32-ec-1277190372} + \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} -Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom -\textsc{SN-Evolution-Cut}-Algorithmus aus dem $BS(64)$-Netzwerk erzeugt wurde. -Es besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als -$BS(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler -und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen -Netzwerken gleich. - -\textbf{TODO:} $BS(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten -möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$ -Komparatoren; $BS(64)$: 672~Komparatoren. - -Schnitt-Sequenz: -MIN( 92) -MAX( 80) -MIN(100) -MAX( 54) -MAX(102) -MAX( 53) -MAX(105) -MAX( 6) -MAX( 99) -MAX( 79) -MAX( 26) -MIN(111) -MAX( 12) -MIN( 22) -MAX( 61) -MAX( 72) -MAX( 68) -MIN( 80) -MAX( 80) -MAX( 99) -MAX(105) -MAX( 0) -MIN( 8) -MAX( 40) -MAX( 74) -MAX( 40) -MAX( 40) -MIN( 56) -MAX( 27) -MAX( 13) -MAX( 1) -MAX( 81) -MAX( 17) -MAX( 4) -MIN( 36) -MIN( 22) -MAX( 13) -MIN( 72) -MAX( 24) -MAX( 5) -MIN( 10) -MAX( 59) -MIN( 37) -MAX( 65) -MAX( 46) -MAX( 73) -MAX( 58) -MAX( 29) -MAX( 65) -MIN( 23) -MAX( 56) -MAX( 11) -MIN( 75) -MIN( 51) -MIN( 46) -MIN( 34) -MAX( 32) -MAX( 6) -MAX( 37) -MIN( 4) -MIN( 28) -MIN( 20) -MAX( 33) -MAX( 34) - -% images/32-ec-1277190372.tex +\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} @@ -1266,10 +1461,17 @@ MAX( 34) \item $\ldots$ \end{itemize} +\newpage \section{Ausblick} Das würde mir noch einfallen$\ldots$ +\newpage +\section{Implementierung} + +So habe ich die ganzen Versuche durchgeführt. + +\newpage \bibliography{references} \bibliographystyle{plain}