erhält man ein {\em Komparatornetzwerk}.
\begin{figure}
-\begin{center}
-\input{images/einfaches_komparatornetzwerk.tex}
-\end{center}
-\caption{Einfaches Komparatornetzwerk mit vier Ein- beziehungsweise Ausgängen, bestehend
-aus 5~Komparatoren.}
-\label{fig:einfaches_komparatornetzwerk}
+ \begin{center}
+ \input{images/einfaches_komparatornetzwerk.tex}
+ \end{center}
+ \caption{Einfaches Komparatornetzwerk mit 4~Ein- beziehungsweise Ausgängen,
+ bestehend aus 5~Komparatoren.}
+ \label{fig:einfaches_komparatornetzwerk}
\end{figure}
Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
\begin{center}
\input{images/09-e2-c24-allbut1.tex}
\end{center}
- \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
- 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
- alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
+ \caption{Ein \emph{Komparatornetzwerk} mit 9~Eingängen und 24~Komparatoren,
+ die in 8~Schichten angeordnet sind. Das Netzwerk sortiert alle Eingaben, bei
+ denen das Minimum nicht auf dem mittleren Eingang liegt.}
\label{fig:09-e2-c24-allbut1}
\end{figure}
Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
-über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
-Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
+so schnell, dass ein Ausprobieren aller möglichen Permutationen schon bei
+16~Leitungen praktisch nicht mehr zu bewerkstelligen
ist.\footnote{1.307.674.368.000 Permutationen}
\label{sect:0-1-prinzip}
Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
-zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$
-oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei
-gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich
-der Komparator so verhält, wie er sich bei der Permutation verhalten hat --
-ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$
-und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im
-Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.
-
-Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
-Komplexitätsklasse
-$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
-ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$
-verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
-schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
-ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
-sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
-aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
-eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
-4,3~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
-beschäftigen.
+zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als
+$a_i$, beziehungsweise zwei Zahlen größer oder gleich $a_i$. Da im Fall der
+0-1-Folge zwei gleiche Zahlen am Komparator anliegen, dürfen wir davon
+ausgehen, dass sich der Komparator so verhält, wie er sich bei der Permutation
+verhalten hat -- ohne das Ergebnis zu beeinflussen. Entsprechend müssen an den
+Ausgängen $i-1$ und $i$ eine Null und eine Eins in der falschen Reihenfolge
+ankommen. Das steht im Widerspruch zu der Annahme, dass alle 0-1-Folgen
+sortiert werden.
+
+Im Gegensatz zum Überprüfen aller möglichen Permutationen, was mit dem Aufwand
+$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ verbunden ist, besitzt
+das Überprüfen aller 0-1-Folgen „nur“ den Aufwand $\Theta(2^n)$. Entsprechend
+ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist
+bisher allerdings nicht bekannt.
+
+Um zu überprüfen, ob ein Komparatornetzwerk mit 16~Leitungen die
+Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig
+-- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt.
+Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch
+bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus
+mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
+Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
+Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
+Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
+Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
+für einen Lauf benötigt.
\subsubsection{Evolutionäre Algorithmen}
Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
-$\mathcal{NP}$. Das heißt, dass keine Verfahren bekannt sind, die diese
-Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese Probleme
-außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine Konsequenz,
-dass es effiziente exakte Algorithmen für diese Probleme nicht gibt. Falls
-sich hingegen herausstellt, dass diese Probleme neben $\mathcal{NP}$ auch in
-der Komplexitätsklasse~\textit{P} liegen, gibt es effiziente Algorithmen. Es
-ist jedoch wahrscheinlich, dass die Zeitkonstanten solcher Algorithmen sehr
-groß sein würden, so dass der praktische Nutzen fraglich bleibt.
-
-Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
-die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen
-Lösungen}, als einzige Ausgabe des Algorithmus zuzulassen, wird eine
-"`möglichst gute"' Lösung ausgegeben. Viele dieser Optimierungsalgorithmen
-orientieren sich an Vorgängen in der Natur. Beispielsweise imitieren die
-„Ameisenalgorithmen“ das Verhalten von Ameisen auf der Futtersuche, um kurze
-Rundreisen auf Graphen zu berechnen.
+$\mathcal{NP}$-vollständig. Das heißt, dass keine Verfahren bekannt sind, die
+diese Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese
+Probleme außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine
+Konsequenz, dass es für diese Probleme keine effizienten exakten Algorithmen
+gibt. Stellt sich hingegen heraus, dass diese Probleme neben
+$\mathcal{NP}$-vollständig auch in der Komplexitätsklasse~\textit{P} liegen,
+gibt es effiziente Algorithmen. Es ist jedoch wahrscheinlich, dass die
+Zeitkonstanten solcher Algorithmen sehr groß wären, so dass der praktische
+Nutzen fraglich bleibt.
+
+Aus diesem Grund besteht die Notwendigkeit, einen Kompromiss einzugehen: Statt
+die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen Lösungen}
+als einzige Ausgabe des Algorithmus zuzulassen, wird eine "`möglichst gute"'
+Lösung ausgegeben. Dafür verringert sich die Laufzeit des Algorithmus. Viele
+dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur.
+Beispielsweise imitieren die „Ameisenalgorithmen“ das Verhalten von Ameisen
+auf der Futtersuche, um kurze Rundreisen auf Graphen zu berechnen.
Bei {\em Evolutionären Algorithmen} stand die Evolution Pate. Die Grundidee
ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
-% \todo{Drei oder vier Verfahren?}
+\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.}
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
\begin{center}
\input{images/oe-transposition-8.tex}
\end{center}
- \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
+ \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.}
\label{fig:odd-even-transposition-08}
\end{figure}
\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}
\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
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.
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
beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“
Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk.
Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt
-beispielsweise 26~Komparatoren, die in neun Schichten angeordnet sind. Es sind
-allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich
-25~Komparatoren in sieben Schichten benötigen. Kombiniert man zwei dieser
-Netzwerke mit dem \emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit
-18~Eingängen, das 80~Komparatoren in 11~Schichten benötigt.
-$\operatorname{OES}(18)$ benötigt 82~Komparatoren in 13~Schichten. Damit ist
-das resultierende Netzwerk genauso schnell wie das Sortiernetzwerk mit
-18~Eingängen, das \textit{Sherenaz~W. Al-Haj Baddar} und \textit{Kenneth~E.
-Batcher} in ihrer Arbeit „An 11-Step Sorting Network for
-18~Elements“~\cite{BB2009} vorstellen, benötigt aber 6~Komparatoren weniger.
+beispielsweise 26~Komparatoren, die in 9~Schichten angeordnet sind. Es sind
+allerdings Sortiernetzwerke mit 9~Eingängen bekannt, die lediglich
+25~Komparatoren in 7~Schichten benötigen. Wenn zwei dieser Netzwerke mit dem
+\emph{Odd-Even}-Mischer kombiniert werden, entsteht ein 18-Sortiernetzwerk,
+das aus 80~Komparatoren in 11~Schichten besteht. Damit ist das resultierende
+Netzwerk genauso schnell wie das Sortiernetzwerk mit 18~Eingängen, das
+\textit{Sherenaz~W. Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer
+Arbeit „An 11-Step Sorting Network for 18~Elements“~\cite{BB2009} vorstellen,
+benötigt aber 6~Komparatoren weniger. $\operatorname{OES}(18)$ benötigt
+82~Komparatoren in 13~Schichten.
Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
\subsection{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)
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}
%\end{figure}
\newpage
-\section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+\section[\textsc{SN-Evolution-Cut}]{Der \textsc{SN-Evolution-Cut}-Algorithmus}
\label{sect:sn-evolution-cut}
Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
-von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
-Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
-gute Schnittmuster gesucht.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$
oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem
-$k$-Schnittmuster sind genau $k$ Zahlen nicht Null.
+$k$-Schnittmuster sind genau $k$ Zahlen ungleich Null.
Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu
invertieren.
+Die Eingabe für \textsc{SN-Evolution-Cut} ist ein $n$-Sortiernetzwerk und eine
+Zahl $k$, $1 \leqq k < n$, die angibt wie viele Leitungen entfernt werden
+sollen. Der Rückgabewert des \textsc{SN-Evolution-Cut}-Algorithmus ist ein
+\emph{$k$-Schnittmuster}. Wird das Schnittmuster auf das Sortiernetzwerk, mit
+dem der Algorithmus gestartet wurde, angewendet, entsteht ein möglichst
+schnelles und effizientes Sortiernetzwerk mit $m = n - k$ Leitungen. Da mit
+dem Eingabe-Netzwerk und dem zurückgegebenen $k$-Schnittmuster das
+$m$-Sortiernetzwerk eindeutig bestimmt ist, werden im Folgenden sowohl das
+$k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von
+\textsc{SN-Evolution-Cut} bezeichnet.
+
\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
\label{sect:sn-evolution-cut:bs}
+Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen
+Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll,
+ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke
+als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k
+= 6$ gestartet, resultiert das gefundene Schnittmuster in einem
+Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16}
+benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
+wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-ec-from-bs22.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk
+ $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4,
+ 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.}
+ \label{fig:16-ec-from-bs22}
+\end{figure}
+
+Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen
+Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden,
+gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde
+mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten
+der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$,
+$w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder
+Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten
+befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des
+Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des
+resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der
+Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu
+können.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+ \hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+ \hline
+ 9 & 21 & & & & & & & & & & & & & & & \\
+ 10 & 20 & 27 & & & & & & & & & & & & & & \\
+ 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\
+ 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\
+ 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\
+ 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\
+ 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\
+ 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\
+ 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\
+ 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\
+ 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\
+ 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\
+ 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\
+ 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\
+ 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\
+ 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
+ \hline
+\bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+ Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+ die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
+ Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
+ \label{tbl:ec-bs-efficiency}
+\end{table}
+
+Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut}
+mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der
+gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von
+$m=23$) ein Ergebnis, das effizienter als \bs{m} ist.
+
+In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein
+effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut}
+gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren
+3~weniger als \bs{19}.
+
+Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke,
+beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein
+Sortiernetzwerk mit 31~Komparatoren gefunden.
+
+\begin{figure}
+ \centering
+ \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}}
+ \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}}
+ \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}}
+ \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}}
+ \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
+ 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+ erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
+ \label{fig:ec-bs-fast_networks}
+\end{figure}
+
+Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
+\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
+das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
+Tabelle~\ref{tbl:ec-bs-speed} ist die Anzahl der Schichten, die die Ergebnisse
+von \textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren,
+aufgelistet. Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n},
+jede Spalte enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die
+Zellen enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 9 & 6 & & & & & & & & & & & & & & & \\
+ 10 & 6 & 8 & & & & & & & & & & & & & & \\
+ 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
+ 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
+ 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
+ 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
+ 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
+ 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
+ 17 & 6 & 8 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
+ 18 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
+ 19 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
+ 20 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
+ 21 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
+ 22 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
+ 23 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
+ 24 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\bs{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\end{tabular}
+ \end{center}
+ \caption{Anzahl der Schichten der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
+ Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
+ die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
+ Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
+ \label{tbl:ec-bs-speed}
+\end{table}
+
+Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die
+schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke,
+die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
+werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.
+
+Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das
+Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m}
+führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt
+werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht
+einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m
+= 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu
+reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
+noch größer gewählt werden.
+
+Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von
+\textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten
+werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in
+Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im
+Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n =
+37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19}
+und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein
+Beispiel für ein solches Netzwerk ist in
+Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 95 & 14 \\
+ 21 & 94 & 14 \\
+ 22 & 93 & 14 \\
+ 23 & 93 & 14 \\
+ 24 & 93 & 14 \\
+ 25 & 96 & 13 \\
+ 26 & 96 & 13 \\
+ 27 & 96 & 13 \\
+ 28 & 96 & 13 \\
+ 29 & 95 & 13 \\
+ 30 & 96 & 13 \\
+ 31 & 95 & 13 \\
+ 32 & 96 & 13 \\
+ 33 & 93 & 13 \\
+ 34 & 94 & 13 \\
+ 35 & 93 & 13 \\
+ \rowcolor{green!10}
+ 36 & 92 & 13 \\
+ \rowcolor{green!10!white!95!black}
+ 37 & 92 & 13 \\
+ 38 & 93 & 13 \\
+ \hline
+ \bs{19} & 98 & 14 \\
+ \oes{19} & 91 & 14 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
+ von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt
+ wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als
+ \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit
+ 13~Schichten die Effizienz der vorherigen
+ Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese
+ Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37}
+ auf diese Art erzeugt wurde, ist in
+ Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.}
+ \label{tbl:ec-bs-19}
+\end{table}
+
\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
-wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
-durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
-Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer
-sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
-werden, Komparatoren ein.
-
-Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
-Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
-konstruiert wurde. Dieses Sortiernetzwerk be\-nö\-tigt 68~Komparatoren,
-12~weniger als das \emph{bitone Mergesort}-Netzwerk nach Batchers Methode.
-Gegenüber Batchers Methode sparen so konstruierte Sortiernetzwerke
-${\frac{1}{4}n(\log n - 1)}$ Komparatoren ein.
+wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode
+konstruiert wurde, durch systematisches Entfernen von Leitungen in einen
+ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert werden
+kann, so dass dieser alternative Mischer im Vergleich zu $\bm{\frac{n}{2} =
+2^{d-1}}$ Komparatoren einspart.
+
+Basierend auf diesen alternativen Mischern geben \textit{Mühlenthaler} und
+\textit{Wanka} eine Konstruktionsvorschrift für Sortiernetzwerke an, die
+gegenüber \bs{n} ${\frac{1}{4}n(\log n - 1)}$ Komparatoren einspart.
+Beispielsweise wird ein 16-Sortiernetzwerk angegeben, das nur 68~Komparatoren
+benötigt. Dieses Netzwerk ist in Abbildung~\ref{fig:16-muehlenthaler}
+dargestellt.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-muehlenthaler.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde 2010 von \textit{Mühlenthaler} und
+ \textit{Wanka} aus optimierten bitonen Mischern konstruiert und
+ in~\cite{MW2010} veröffentlicht.}
+ \label{fig:16-muehlenthaler}
+\end{figure}
\begin{figure}
\begin{center}
29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch
\textsc{SN-Evolution-Cut} gefunden wurde.
Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
-nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine
-Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in
-diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des
-Netzwerks scheinen rein zufällig zu sein.
+nachdem das Schnittmuster angewendet und das Netzwerk normalisiert wurde.
+% Eine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist
+% in diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten
+% des Netzwerks scheinen rein zufällig zu sein.
\begin{figure}
% 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
\label{fig:32-ec-from-bs64}
\end{figure}
-Das Ergebnis von \textit{Mühlenthaler} und \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
-Geschwindigkeit dieser Sortiernetzwerke gleich ist.
+Wenn \textsc{SN-Evolution-Cut} mit dem \bs{64}-Netzwerk und $k = 32$ gestartet
+wird, findet der Algorithmus 32-Sortiernetzwerke, die effizienter sind als
+32-Sortiernetzwerke, die nach \textit{Mühlenthalers} und \textit{Wankas}
+Methode konstruiert werden. Ein von \textsc{SN-Evolution-Cut} aus \bs{64}
+generiertes 32-Sortiernetzwerk ist in Abbildung~\ref{fig:32-ec-from-bs64}
+dargestellt. Das \emph{bitone Mergesort}-Netzwerk \bs{32} benötigt
+240~Komparatoren, ein aus den optimierten Mischern aufgebautes Netzwerk
+verbessert die Effizienz auf 208~Komparatoren. Das Ergebnis von
+\textsc{SN-Evolution-Cut} kommt mit nur 206~Komparatoren aus. Die
+Geschwindigkeit aller genannten Sortiernetzwerke ist mit 15 parallelen
+Schritten identisch.
+
+Wenn die Leitungszahl des Eingabenetzwerks keine Zweierpotenz ist, kann
+\textsc{SN-Evo\-lu\-tion-Cut} auch 16-Sortiernetzwerke erzeugen, die diese
+Effizienz unterbieten. Das geht aus den Daten in
+Tabelle~\ref{tbl:ec-bs-efficiency} hervor. Ein 16-Sortiernetzwerk mit
+67~Komparatoren, das von \textsc{SN-Evolution-Cut} generiert wurde, ist in
+Abbildung~\ref{fig:16-ec-from-bs22} dargestellt.
Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
-\begin{figure}
- \centering
- \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}}
- \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}}
- \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann
- der Algorithmus schnelle Sortiernetzwerke ausgeben.}
- \label{fig:11-12-ec-from-bs22-bs24}
-\end{figure}
+Dass die Sortiernetzwerke, die mit den Schnittmustern von
+\textsc{SN-Evolution-Cut} entstehen, keine erkennbare Struktur haben, ist
+jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere von der
+Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
+\emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(n)$ und
+$k$~Schnitten gestartet, so ist das beste Ergebnis immer das
+$\operatorname{OET}(n-k)$-Netzwerk.
+
+\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
+\label{sect:sn-evolution-cut:oes}
-Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des
-\emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist,
-können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch
-effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die
-folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für
-\textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit
-der doppelten Leitungszahl. Die Abbildungen~\ref{fig:11-12-ec-from-bs22-bs24}
-und~\ref{fig:23-ec-from-bs46} zeigen beispielhaft ein 11-, 12- und
-23-Sortiernetzwerk, die aus \bs{22}, \bs{24} und \bs{46} generiert wurden.
+Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die
+genauso effizient und schnell wie das entsprechende
+\emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der
+Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus
+\oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency}
+tabellarisch.
-\begin{center}
-\begin{tabular}{|r|r|r|r|r|}
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
\hline
-Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
- & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} &
- \bs{n} \\
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
\hline
-11 & 37 & 9 & 39 & 10 \\
-12 & 42 & 9 & 46 & 10 \\
-19 & 93 & 13 & 98 & 14 \\
-20 & 102 & 13 & 106 & 14 \\
-% 20: # sn-cut 2:MAX 3:MIN 4:MIN 9:MIN 10:MIN 13:MIN 14:MIN 15:MIN 19:MIN 20:MAX 24:MAX 26:MIN 27:MAX 29:MIN 31:MAX 33:MIN 34:MAX 35:MIN 37:MIN 39:MAX
-21 & 109 & 14 & 114 & 15 \\
-22 & 116 & 14 & 123 & 15 \\
-23 & 124 & 14 & 133 & 15 \\
+ 9 & 19 & & & & & & & & & & & & & & & \\
+ 10 & 19 & 26 & & & & & & & & & & & & & & \\
+ 11 & 19 & 26 & 31 & & & & & & & & & & & & & \\
+ 12 & 19 & 26 & 31 & 37 & & & & & & & & & & & & \\
+ 13 & 19 & 26 & 31 & 37 & 41 & & & & & & & & & & & \\
+ 14 & 19 & 26 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
+ 15 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
+ 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
+ 17 & 19 & 26 & 31 & 38 & 41 & 48 & 53 & 59 & 63 & & & & & & & \\
+ 18 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & & & & & & \\
+ 19 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & & & & & \\
+ 20 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & & & & \\
+ 21 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & & & \\
+ 22 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & & \\
+ 23 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & \\
+ 24 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
\hline
\end{tabular}
-\end{center}
+ \end{center}
+ \caption{Anzahl der Komparatoren der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-oes-efficiency}
+\end{table}
\begin{figure}
- \begin{center}
- \input{images/23-ec-from-bs46-fast.tex}
- \end{center}
- \caption{23-Sortiernetzwerk mit 124~Komparatoren in 14~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{46} mit dem
- Schnittmuster $\operatorname{MIN}(2, 4, 9, 12, 20, 22, 28, 30, 32, 33, 37,
- 38, 41)$, $\operatorname{MAX}(1, 5, 16, 19, 21, 24, 25, 35, 36, 43)$
- erzeugt.}
- \label{fig:23-ec-from-bs46}
+ \centering
+ \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{17} erzeugt.]{\input{images/11-ec-from-oes17-fast.tex}\label{fig:11-ec-from-oes17-fast}}
+ \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{18} erzeugt.]{\input{images/12-ec-from-oes18-fast.tex}\label{fig:12-ec-from-oes18-fast}}
+ \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m =
+ 11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+ erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m}
+ sind.}
+ \label{fig:ec-oes-fast_networks}
\end{figure}
-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.
+Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt
+schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein
+$m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes
+Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit
+war allerdings in allen beobachteten Fällen nur dann möglich, wenn
+zusätzliche Komparatoren in Kauf genommen wurden. In den
+Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser
+Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu
+beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
+Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.
+
+Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim
+\emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die
+Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war
+jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere
+Geschwindigkeit zu erreichen.
+
+In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von
+\textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots
+19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles
+19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die
+resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit
+$k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des
+\emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in
+13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 9 & 6 & & & & & & & & & & & & & & & \\
+ 10 & 6 & 8 & & & & & & & & & & & & & & \\
+ 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
+ 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
+ 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
+ 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
+ 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
+ 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
+ 17 & 6 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
+ 18 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
+ 19 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
+ 20 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
+ 21 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
+ 22 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
+ 23 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
+ 24 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\oes{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
+\hline
+\end{tabular}
+ \end{center}
+ \caption{Anzahl der Schichten der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-oes-speed}
+\end{table}
-\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
-\label{sect:sn-evolution-cut:oes}
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 91 & 14 \\
+ 21 & 91 & 14 \\
+ 22 & 91 & 14 \\
+ 23 & 91 & 14 \\
+ 24 & 91 & 14 \\
+ 25 & 91 & 14 \\
+ 26 & 91 & 14 \\
+ 27 & 91 & 14 \\
+ 28 & 91 & 14 \\
+ 29 & 95 & 13 \\
+ 30 & 93 & 13 \\
+ 31 & 93 & 13 \\
+ 32 & 93 & 13 \\
+ 33 & 93 & 13 \\
+ 34 & 93 & 13 \\
+ 35 & 93 & 13 \\
+ 36 & 93 & 13 \\
+ 37 & 93 & 13 \\
+ 38 & 93 & 13 \\
+ \hline
+ \bs{19} & 98 & 14 \\
+ \oes{19} & 91 & 14 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Komparatoren und Schichten von Sortiernetzwerken, die von
+ \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$
+ ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die
+ Effizienz von 91~Komparatoren nicht mehr erreichbar.}
+ \label{tbl:ec-oes-19}
+\end{table}
In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
-viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
-$\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$
-besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das
-\emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen
-16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es
-wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
-$\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese
-Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine
-Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes
-16-Schnittmuster findet.
+viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
+Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und
+$\operatorname{PS}(32)$ besitzen. Eines der Ergebnisse war, dass von diesen
+Sortiernetzwerken das \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten
+unterschiedlichen 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen.
+Entsprechend ist es wenig verwunderlich, dass \textsc{SN-Evolution-Cut}
+gestartet mit $\operatorname{OES}(32)$ sehr schnell\footnote{Ein
+entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen
+geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe
+Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf
+derzeitigen Computern.} ein gutes 16-Schnittmuster findet.
Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
\input{images/16-ec-from-oes32-cut.tex}
\end{center}
\caption{Visualisierung eines 16-Schnittmusters, das auf
- $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes
- Sortiernetzwerk ergibt.}
+ $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
+ bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
+ resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
+ dargestellt.}
\label{fig:16-ec-from-oes32-cut}
\end{figure}
\input{images/16-ec-from-oes32.tex}
\end{center}
\caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
- Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem
- \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(32)$ durch
- 16~Schnitte erzeugt.}
+ Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
+ einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
+ berechnet wurde. Das Schnittmuster ist in
+ Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
\label{fig:16-ec-from-oes32}
\end{figure}
Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
-\bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das
-Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46})
-effizienter, da es nur 124~Komparatoren benötigt.
+\bs{23} beziehungsweise \oes{23} eine Schicht einspart.
\begin{figure}
\begin{center}
ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
wie und warum es jede beliebige Eingabe sortiert.
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+\begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+\hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+\hline
+ 9 & 20 & & & & & & & & & & & & & & & \\
+ 10 & 20 & 27 & & & & & & & & & & & & & & \\
+ 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\
+ 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\
+ 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\
+ 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
+ 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
+ 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
+ 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\
+ 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\
+ 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\
+ 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\
+ 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\
+ 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\
+ 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\
+ 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\
+\hline
+\ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\
+\hline
+\end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
+ \label{tbl:ec-ps-speed}
+\end{table}
+
Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
projects / diplomarbeit.git / blobdiff