X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=03be0ac8394252c14d38a6cd25a5887078f1cd66;hb=73495b061c2fa75855a6a068178f93c1d9948fa4;hp=591aa4e6e696453ae5d6cd6f73a19c8d0ebe6700;hpb=6ad09e4aabf63f4ebfbe36cf940615132691bb71;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 591aa4e..03be0ac 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -270,8 +270,8 @@ Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden. Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der Komplexitätsklasse -$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, -ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$ +$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, +ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$ verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen, ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt, @@ -435,7 +435,7 @@ ${n = 8}$ Leitungen. \begin{center} \input{images/oe-transposition-8.tex} \end{center} - \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.} + \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.} \label{fig:odd-even-transposition-08} \end{figure} @@ -458,7 +458,7 @@ $\operatorname{OET}(3)$ sortiert. Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n -(n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind. +(n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind. Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren, ($\Theta(n \log (n)^2)$), die in weniger Schichten, ($\Theta(\log (n)^2)$), angeordnet sind. @@ -574,7 +574,7 @@ Statt an eine Treppe erinnert das Muster nun an einen Trichter. Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus -$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren +$\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren besteht, die in $\log(n)$~Schichten angeordnet werden können. \subsubsection{Das bitone Mergesort-Netzwerk} @@ -598,10 +598,10 @@ alle Komparatoren in die gleiche Richtung zeigen. \begin{center} \input{images/batcher-8.tex} \end{center} - \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht - Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden - bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten - rekursiven Schritt hinzugefügt wurden (grün).} + \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~Eingänge. + Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden bitonen + Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven + Schritt hinzugefügt wurden (grün).} \label{fig:bitonic-08} \end{figure} @@ -656,10 +656,12 @@ w_i = \left\{ \begin{array}{ll} \begin{center} \input{images/oe-merge.tex} \end{center} - \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Im - Vergleich zum bitonen Mischer für acht Leitungen kommt dieses Schema mit - einem Komparator weniger aus. Der Effekt wird durch den rekursiven Aufbau - verstärkt.} + \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die + beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$, + die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der + Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt + dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den + rekursiven Aufbau verstärkt.} \label{fig:oe-merge} \end{figure} @@ -701,7 +703,7 @@ Aufbau lauten: einzelnen Komparator. \end{itemize} -Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass die resultierende Folge +Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise $V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den @@ -746,7 +748,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \end{figure} Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden, -bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$ +bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$ Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit Schichten im Mischer-Netzwerk), hängt von der längeren der beiden Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$. @@ -764,7 +766,7 @@ Länge der Eingabefolgen, $n$ und $m$ ab: \end{displaymath} Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar, -dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist. +dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist. Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der @@ -802,7 +804,7 @@ die als leere Komparatornetzwerke definiert sind. \begin{center} \input{images/oe-mergesort-8.tex} \end{center} - \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert + \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~Eingänge. Markiert sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten @@ -813,7 +815,7 @@ die als leere Komparatornetzwerke definiert sind. In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk zu sehen. Rot markiert sind die beiden rekursiven Instanzen $\operatorname{OES}(4)$. Die anderen Blöcke stellen den -\emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind +\emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden. @@ -935,7 +937,7 @@ zu sortieren und die Ausgaben mit einem der beschriebenen Mischer zusammenfügen. Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken} -$\operatorname{BS}(8)$ mit je acht Leitungen mit dem +$\operatorname{BS}(8)$ mit je 8~Leitungen mit dem \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt @@ -1252,10 +1254,20 @@ die bei Sortiernetzwerken verfolgt werden können: \item Möglichst wenige Schichten („schnell“) \end{itemize} -Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das -effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus -60~Komparatoren in 10~Schichten. Das schnellste bekannte 16-Sortiernetzwerk -besteht aus 61~Komparatoren in nur 9~Schichten. +\begin{figure} + \centering + \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}} + \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}} + \caption{Das effizienteste und das schnellste Sortiernetzwerk für + 16~Leitungen, das derzeit bekannt ist.} + \label{fig:16-best-known} +\end{figure} +Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. +Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für +16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in +Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte +16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in +Abbildung~\ref{fig:16-voorhis} zu sehen. Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"' berücksichtigen kann, hat die folgende allgemeine Form: @@ -1301,17 +1313,20 @@ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen} \subsection{Selektion} -Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere -Wahrscheinlichkeit haben zur nächsten Generation beizutragen. Diese -Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das -Streben des Algorithmus nach besseren Lösungen. +Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig +aus der Population auswählt. Sie werden im folgenden Schritt miteinander +rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht +gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen +eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen. +Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für +das Streben des Algorithmus nach besseren Lösungen. Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint, -ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der -Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. +passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt +und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. -Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von -Pseudocode wie folgt beschreiben: +Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt +sich mit Pseudocode wie folgt beschreiben: \begin{verbatim} Gütesumme := 0 Auswahl := (leer) @@ -1330,6 +1345,10 @@ Pseudocode wie folgt beschreiben: gib Auswahl zurück \end{verbatim} +Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die +Rekombination zu erhalten. Das heißt, dass die Individuen bei +\textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden. + \subsection{Rekombination} \label{sect:sn-evolution:rekombination} @@ -1555,11 +1574,227 @@ Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur um das beste Ergebnis beider Konstruktionen zu erreichen. \textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem -\emph{Odd-Even}-Mischer wählen. \todo{Daten noch in eine Tabelle einfügen.} +\emph{Odd-Even}-Mischer wählen. + +Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des +Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast} +zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der +Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem +Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und +20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen +Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz. + +\begin{table}\label{tbl:sn-ev-rnd-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} + & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} + & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\ +\cline{2-7} + ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & 20 & 6 & \gcell 19 & 6 & \gcell 19 & 6 \\ + 9 & 26 & 8 & 26 & 8 & 26 & 8 \\ + 10 & 31 & \gcell 8 & 31 & 9 & 31 & \gcell 8 \\ + 11 & \Gcell 37 & 9 & 38 & 9 & \Gcell 37 & 9 \\ + 12 & 42 & 9 & 43 & 9 & \gcell 41 & 9 \\ + 13 & 48 & 10 & 48 & 10 & 48 & 10 \\ + 14 & 54 & 10 & \gcell 53 & 10 & \gcell 53 & 10 \\ + 15 & 61 & 10 & \Gcell 59 & 10 & \Gcell 59 & 10 \\ + 16 & 67 & 10 & \gcell 63 & 10 & 64 & 10 \\ + 17 & 76 & 12 & \Gcell 74 & 12 & \Gcell 74 & 12 \\ + 18 & 87 & \gcell 12 & \gcell 82 & 13 & 83 & \gcell 12 \\ + 19 & 93 & 13 & 93 & 13 & \Gcell 92 & 13 \\ + 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\ + 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\ + 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\ + 23 & 134 & 14 & 129 & 14 & \Gcell 128 & 14 \\ + 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung der verschiedenen Mischer. Der Algorithmus wurde mit dem + \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach + 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten + $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$, + $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} %\input{shmoo-aequivalenz.tex} \newpage +\section{Der \textsc{SN-Markov}-Algorithmus} +\label{sect:markov} + +Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen +Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus +einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander +ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal +verwendet und mit sich selbst kombiniert wird. + +Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk +\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller +Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke, +die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit +sich selbst und anschließendem Eliminieren der Hälfte der Leitungen hervorgehen +können, heißen \emph{Nachfolger} von $S_0$. + +Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem +(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei +Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer +Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von +$S_0$ ist, das heißt, dass $S_1$ durch die Rekombination von $S_0$ mit sich +selbst erzeugt werden kann. + +Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl +der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger +sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der +Nachfolger zwar noch unter 20.000, bei den untersuchten +32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$ +unterschiedliche Schnittmuster geschätzt. + +Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen +zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem +gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu +gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich +selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der +Algorithmus wie folgt beschreiben: + +\begin{verbatim} + Netzwerk := Eingabe + + für n Iterationen + { + Nachfolger := kombiniere (Netzwerk, Netzwerk) + Netzwerk := Nachfolger + } + + gib Netzwerk zurück +\end{verbatim} + +Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der +Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem +zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der +\textsc{SN-Markov}-Algorithmus auf einem entsprechenden +\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens +1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der +Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler +erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende +prozentuale Verteilung zu sehen. + +Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators} +eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen +Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der +um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde. +Beispielsweise war die kleinste erreichte Komparatorzahl bei +16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$ +gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$ +und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem +Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$ +unter den Graphen angegeben. + +\begin{figure} + \centering + \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}} + \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}} + \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}} + \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}} + \caption{Anzahl der Komparatoren von Sortiernetzwerken, + die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet + ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der + gemessenen Daten darstellt.} + \label{fig:markov-comparators} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf} + \end{center} + \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von + \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem + \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.} + \label{fig:comparison-comparators} +\end{figure} + +Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der +\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der +\textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit +\textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl +der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als +Startnetzwerk diente bei beiden Algorithmen das +\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der +x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der +ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt +wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je +nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}. + +Sowohl der \textsc{SN-Markov}-Algorithmus, der das +\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit +\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die +bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind. +Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger: +Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit +63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335 +\%$ rund 20~mal höher. + +Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem +\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist +jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die +mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16} +ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für +Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein +Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so +vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen +Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das +mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk +zusammenhängt. + +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.} +% \label{fig:markov-comparators-14} +%\end{figure} +% +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.} +% \label{fig:markov-comparators-16} +%\end{figure} +% +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf} +% \end{center} +% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen), +% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die +% \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.} +% \label{fig:markov-comparators-18} +%\end{figure} + +%\begin{figure} +% \begin{center} +% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} +% \end{center} +% \caption{Zyklen, die beim \textit{Random Walk} des +% \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die +% Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der +% y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale +% Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} +% \label{fig:markov-cycles-16} +%\end{figure} + +\newpage \section{Der \textsc{SN-Evolution-Cut}-Algorithmus} \label{sect:sn-evolution-cut} @@ -1588,6 +1823,19 @@ multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu invertieren. \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk} +\label{sect:sn-evolution-cut:bs} + +\begin{figure} + \begin{center} + \input{images/16-ec-from-bs22.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk + $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4, + 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.} + \label{fig:16-ec-from-bs22} +\end{figure} \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde, @@ -1743,88 +1991,44 @@ 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. - -\subsection[Pairwise-Sorting-Netzwerk]{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, das die gleiche -Anzahl Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und -$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in -Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. - -\begin{figure} - \begin{center} - \input{images/16-ec-from-ps32.tex} - \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in - 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} - $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} - \label{fig:16-ec-from-ps32} -\end{figure} - -Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht -einsetzt und auch nicht auf einem Mischer basiert, ist das -\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in -Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In -den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die -strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die -Schichten~1 und~2 sowie 4~und~5 sind vertauscht. +$k$~Schnitten gestartet, so ist das beste Ergebnis immer das +$\operatorname{OET}(n-k)$-Netzwerk. -\begin{figure} +\begin{table} \begin{center} - \input{images/32-pairwise-cut-16-pairwise.tex} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|rrrrrrrrrrrrrrrr|} + \hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ + \hline + 9 & 21 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\ + 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\ + 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\ + 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\ + 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\ + 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\ + 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\ + 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\ + 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\ + 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\ + 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\ + 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\ + 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\ + \hline +\bs{n} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\ + \hline + \end{tabular} \end{center} - \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu - sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk - bilden.} - \label{fig:ps16-from-ps32} -\end{figure} - -Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach -regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres -schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das -einfache Schnittmuster -\begin{displaymath} -\textit{Eingang}_i = \left\{ \begin{array}{rl} - -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\ - \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\ - ? & \quad \mathrm{sonst} - \end{array} \right. -\end{displaymath} -für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk -$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der -dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das -verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32} -dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind -diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden -Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den -„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht -werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende -Netzwerk in schwarz gut zu erkennen. - -\begin{figure} - \begin{center} - \input{images/16-pairwise.tex} - \end{center} - \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten - ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das - resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.} - \label{fig:16-pairwise} -\end{figure} - -Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf -$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein -8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für -größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise -kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} -konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} -untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. + \caption{Anzahl der Komparatoren der Ergebnisse des + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen + Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt + die Ergebnisse für ein Eingabenetzwerk \bs{n} an, die Spalten + repräsentieren die Anzahl der Leitungen des Ausgabenetzwerks.} + \label{tbl:ec-bs-fast} +\end{table} \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk} \label{sect:sn-evolution-cut:oes} @@ -1977,174 +2181,127 @@ effizienter, da es nur 124~Komparatoren benötigt. \label{fig:23-ec-from-oes46} \end{figure} -\newpage -\section{Der \textsc{SN-Markov}-Algorithmus} -\label{sect:markov} - -Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen -Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus -einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander -ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal -verwendet und mit sich selbst kombiniert wird. - -Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk -\emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller -Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke, -die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit -sich selbst und anschließendem Eliminieren der Hälfte der Leitungen hervorgehen -können, heißen \emph{Nachfolger} von $S_0$. - -Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem -(gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei -Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer -Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von -$S_0$ ist, das heißt, dass $S_1$ durch die Rekombination von $S_0$ mit sich -selbst erzeugt werden kann. - -Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl -der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger -sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der -Nachfolger zwar noch unter 20.000, bei den untersuchten -32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$ -unterschiedliche Schnittmuster geschätzt. +\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk} -Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen -zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem -gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu -gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich -selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der -Algorithmus wie folgt beschreiben: +Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene +Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war +(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise +ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich, +wie und warum es jede beliebige Eingabe sortiert. -\begin{verbatim} - Netzwerk := Eingabe - - für n Iterationen - { - Nachfolger := kombiniere (Netzwerk, Netzwerk) - Netzwerk := Nachfolger - } - - gib Netzwerk zurück -\end{verbatim} - -Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der -Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem -zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der -\textsc{SN-Markov}-Algorithmus auf einem entsprechenden -\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens -1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der -Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler -erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende -prozentuale Verteilung zu sehen. +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 20 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\ + 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\ + 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\ + 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\ + 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\ + 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\ + 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\ + 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\ + 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\ + 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\ + 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\ + 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\ + 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\ +\hline +\ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\ +\hline +\end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} + \label{tbl:ec-bs-fast} +\end{table} -Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators} -eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen -Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der -um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde. -Beispielsweise war die kleinste erreichte Komparatorzahl bei -16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$ -gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$ -und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem -Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$ -unter den Graphen angegeben. +Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian +Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} +definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit +$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man +ein Sortiernetzwerk, das die gleiche Anzahl Komparatoren und Schichten hat wie +$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser +Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. \begin{figure} - \centering - \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}} - \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}} - \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}} - \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}} - \caption{Anzahl der Komparatoren von Sortiernetzwerken, - die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet - ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der - gemessenen Daten darstellt.} - \label{fig:markov-comparators} + \begin{center} + \input{images/16-ec-from-ps32.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} + $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} + \label{fig:16-ec-from-ps32} \end{figure} +Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht +einsetzt und auch nicht auf einem Mischer basiert, ist das +\emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in +Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In +den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die +strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die +Schichten~1 und~2 sowie 4~und~5 sind vertauscht. + \begin{figure} \begin{center} - \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf} + \input{images/32-pairwise-cut-16-pairwise.tex} \end{center} - \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von - \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem - \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.} - \label{fig:comparison-comparators} + \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu + sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk + bilden.} + \label{fig:ps16-from-ps32} \end{figure} -Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der -\textsc{SN-Markov}-Algorithmus nicht schlechter ist als der -\textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit -\textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl -der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als -Startnetzwerk diente bei beiden Algorithmen das -\emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der -x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der -ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt -wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je -nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}. - -Sowohl der \textsc{SN-Markov}-Algorithmus, der das -\emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit -\oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die -bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind. -Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger: -Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit -63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335 -\%$ rund 20~mal höher. - -Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem -\emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist -jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die -mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16} -ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für -Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein -Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so -vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen -Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das -mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk -zusammenhängt. +Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach +regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres +schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das +einfache Schnittmuster +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\ + \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} +für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk +$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der +dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das +verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32} +dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind +diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden +Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den +„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht +werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende +Netzwerk in schwarz gut zu erkennen. -%\begin{figure} -% \begin{center} -% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf} -% \end{center} -% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen), -% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die -% \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.} -% \label{fig:markov-comparators-14} -%\end{figure} -% -%\begin{figure} -% \begin{center} -% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf} -% \end{center} -% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), -% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die -% \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.} -% \label{fig:markov-comparators-16} -%\end{figure} -% -%\begin{figure} -% \begin{center} -% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf} -% \end{center} -% \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen), -% die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die -% \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.} -% \label{fig:markov-comparators-18} -%\end{figure} +\begin{figure} + \begin{center} + \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} -%\begin{figure} -% \begin{center} -% \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf} -% \end{center} -% \caption{Zyklen, die beim \textit{Random Walk} des -% \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die -% Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der -% y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale -% Start-Sortiernetzwerk war $\operatorname{OET}(16)$.} -% \label{fig:markov-cycles-16} -%\end{figure} +Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf +$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein +8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für +größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise +kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} +konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} +untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. \newpage \section{Fazit und Ausblick}