-- 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
+mehrere Stunden 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.
+Zwischenergebnisses drei Stunden in Anspruch nimmt, sind für eine Million
+Iterationen etwa 340~Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, wird etwa ein Monat für
+einen Lauf benötigt.
\subsubsection{Evolutionäre Algorithmen}
"`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
-Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
-
-\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.}
+Eingabe. Im Folgenden werden daher drei Konstruktionsverfahren vorgestellt.
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
\end{displaymath}
gilt.
-% gnuplot:
-% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
-% oem1(n) = oem(ceil(.5*n),floor(.5*n))
-% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
-
-%\begin{itemize}
-%\item Pairwise sorting-network
-%\end{itemize}
-
-\subsection{Das Pairwise-Sorting-Netzwerk}
-
-Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
-für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
-Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
-Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
-\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
-das \emph{Odd-Even-Mergesort}-Netzwerk.
+%\subsection{Das Pairwise-Sorting-Netzwerk}
+%
+%Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
+%für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
+%Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
+%Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
+%\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
+%das \emph{Odd-Even-Mergesort}-Netzwerk.
\newpage
\section{Transformation von Sortiernetzwerken}
\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}}
+ \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in~\cite{G1972}
+ 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} 1974 in~\cite{V1974}
+ 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}
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:
+\textsc{SN-Evolution} verwendet eine Gütefunktion, die die beiden Ziele
+"`effizient"' und "`schnell"' berücksichtigen kann. Sie hat die folgende
+generelle Form:
\begin{equation}
\operatorname{Guete}(S) = w_{\mathrm{Basis}}
+ w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
-Exploitation}, das Finden (lokaler) Optima, bevorzugt.
+Exploitation}, das Streben zu (lokalen) Optima, verstärkt.
Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
Werte herausgestellt:
\begin{eqnarray*}
-w_{\mathrm{Basis}} &=& 0 \\
-w_{\mathrm{Komparatoren}} &=& 1 \\
-w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
+ w_{\mathrm{Basis}} &=& 0 \\
+ w_{\mathrm{Komparatoren}} &=& 1 \\
+ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
\end{eqnarray*}
+Sofern nicht anders angegeben, werden diese Werte im Folgenden zur Bewertung
+von Sortiernetzwerken verwendet. Die Bewertungsfunktion bevorzugt mit diesen
+Konstanten \emph{schnelle} Sortiernetzwerke, da das Einsparen einer Schicht
+ein höheres Gewicht als das Einsparen von Komparatoren hat.
+
+Wenn der \textsc{SN-Evolution}-Algorithmus nach \emph{effizienten}
+Sortiernetzwerken suchen soll, werden alternative Werte für die Konstanten der
+Bewertungsfunktion verwendet. Die Werte
+\begin{eqnarray*}
+ w_{\mathrm{Basis}} &=& 0 \\
+ w_{\mathrm{Komparatoren}} &=& 2 \\
+ w_{\mathrm{Schichten}} &=& 1
+\end{eqnarray*}
+geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
+einer Schicht.
\subsection{Selektion}
\subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer}
-\begin{figure}
- \begin{center}
- \input{images/16-e1-bitonic-1296542566.tex}
- \end{center}
- \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
- 10~Schichten. Das Netzwerk wurde von dem Algorithmus
- \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers}
- erzeugt.}
- \label{fig:16-e1-bitonic-1296542566}
-\end{figure}
-
Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
-Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in
-Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück.
-
-Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser
-Konfiguration gefunden werden, sind effizienter als das \emph{bitone
-Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
-Merge}-Netzwerk \bm{n} beruht. Das in
-Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
-benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
-
-Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
-bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n}
-sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als
-\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit
-134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von
-schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen
-Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast}
-aufgelistet.
+Mischer} verwendet, gibt der Algorithmus \emph{effiziente} und in einigen
+Fällen \emph{schnelle} Sortiernetzwerke aus. Die Ergebnisse des
+\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
+sind in Tabelle~\ref{tbl:sn-ev-bm-fast} zusammengefasst.
\begin{table}\label{tbl:sn-ev-bm-fast}
\begin{center}
\cline{2-5}
($n$) & Komp. & Schichten & Komp. & Schichten \\
\hline
- 8 & \gcell 20 & 6 & 24 & 6 \\
- 9 & \Gcell 26 & 8 & 28 & 8 \\
- 10 & \gcell 31 & \gcell 8 & 33 & 9 \\
- 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\
- 12 & \gcell 42 & \gcell 9 & 46 & 10 \\
- 13 & \Gcell 48 & 10 & 53 & 10 \\
- 14 & \gcell 54 & 10 & 61 & 10 \\
- 15 & \Gcell 61 & 10 & 70 & 10 \\
- 16 & \gcell 67 & 10 & 80 & 10 \\
- 17 & \Gcell 76 & 12 & 85 & 12 \\
- 18 & \gcell 87 & \gcell 12 & 91 & 13 \\
- 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\
- 20 & \gcell 104 & \gcell 13 & 106 & 14 \\
- 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
- 22 & \gcell 118 & \gcell 14 & 123 & 15 \\
- 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\
- 24 & \gcell 133 & 15 & 144 & 15 \\
+ 8 & \gcell 20 & 6 & 24 & 6 \\
+ 9 & \Gcell 26 & 8 & 28 & 8 \\
+ 10 & \gcell 31 & \gcell 8 & 33 & 9 \\
+ 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\
+ 12 & \gcell 42 & \gcell 9 & 46 & 10 \\
+ 13 & \Gcell 48 & 10 & 53 & 10 \\
+ 14 & \gcell 54 & 10 & 61 & 10 \\
+ 15 & \Gcell 61 & 10 & 70 & 10 \\
+ 16 & \gcell 67 & 10 & 80 & 10 \\
+ 17 & \Gcell 76 & 12 & 85 & 12 \\
+ 18 & \gcell 87 & \gcell 12 & 91 & 13 \\
+ 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\
+ 20 & \gcell 104 & \gcell 13 & 106 & 14 \\
+ 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
+ 22 & \gcell 118 & \gcell 14 & 123 & 15 \\
+ 23 & \Gcell 129 & \Gcell 14 & 133 & 15 \\
+ 24 & \gcell 133 & 15 & 144 & 15 \\
\hline
\end{tabular}
\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
\end{center}
\end{table}
-\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
+Alle Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser Konfiguration
+gefunden wurden, waren \emph{effizienter} als das \emph{bitone
+Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
+Merge}-Netzwerk \bm{n} beruht. Zum Beispiel benötigt das in
+Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
+67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
\begin{figure}
\begin{center}
- \input{images/16-e1-oddeven-1296543330.tex}
+ \input{images/16-e1-bitonic-1296542566.tex}
\end{center}
- \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
+ \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
10~Schichten. Das Netzwerk wurde von dem Algorithmus
- \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers
+ \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers}
erzeugt.}
- \label{fig:16-e1-oddeven-1296543330}
+ \label{fig:16-e1-bitonic-1296542566}
+\end{figure}
+
+Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
+bevorzugt, werden in einigen Fällen Netzwerke zurückgegeben, die
+\emph{schneller} und \emph{effizienter} als \bs{n} sind. Das
+19-Sortiernetzwerk in Abbildung~\ref{fig:19-e1-bm-fast} besitzt beispielsweise
+nur 13~Schichten und benötigt damit einen parallelen Schritt weniger als
+\bs{19}.
+
+\begin{figure}
+ \begin{center}
+ \input{images/19-e1-bm-fast.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+ unter Verwendung des \emph{bitonen Mischers} erzeugt.}
+ \label{fig:19-e1-bm-fast}
\end{figure}
+\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
+
+Die folgenden Ergebnisse wurden erzielt, indem \textsc{SN-Evolution} mit dem
+\emph{Odd-Even-Transpositionsort}-Netzwerk als Eingabe gestartet wurde und in
+der Rekombinationsphase das \emph{Odd-Even-Merge}-Netzwerk verwendete. So
+erzeugt der Algorithmus entweder Sortiernetzwerke, die genauso schnell und
+effizient wie das \oes{n}-Netzwerk, oder Sortiernetzwerke, die schneller aber
+weniger effizient als das \oes{n}-Netzwerk sind. Die Ergebnisse von
+\textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer sind in
+Tabelle~\ref{tbl:sn-ev-oem-fast} zusammengefasst.
+
+\begin{table}\label{tbl:sn-ev-oem-fast}
+\begin{center}
+\rowcolors{4}{black!5}{}
+\begin{tabular}{|r|r|r|r|r|}
+\hline
+Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
+\cline{2-5}
+ & Komp. & Schichten & Komp. & Schichten \\
+\hline
+ 8 & 19 & 6 & 19 & 6 \\
+ 9 & 26 & 8 & 26 & 8 \\
+ 10 & 31 & 9 & 31 & 9 \\
+ 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
+ 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
+ 13 & 48 & 10 & 48 & 10 \\
+ 14 & 53 & 10 & 53 & 10 \\
+ 15 & 59 & 10 & 59 & 10 \\
+ 16 & 63 & 10 & 63 & 10 \\
+ 17 & 74 & 12 & 74 & 12 \\
+ 18 & 82 & 13 & 82 & 13 \\
+ 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
+ 20 & 97 & 14 & 97 & 14 \\
+ 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
+ 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
+ 23 & 127 & \Gcell 14 & \Gcell 122 & 15 \\
+ 24 & 128 & 15 & \gcell 127 & 15 \\
+\hline
+\end{tabular}
+\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
+ unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
+ Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
+ gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
+ nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
+ 1$, $w_{\mathrm{Schichten}} = n$.}
+\end{center}
+\end{table}
+
Im vorherigen Abschnitt wurde gezeigt, dass der
\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
\emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
-Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen.
+Abbildung~\ref{fig:16-e1-oem-fast} dargestellt.
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-e1-oem-fast.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
+ 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers
+ erzeugt.}
+ \label{fig:16-e1-oem-fast}
+\end{figure}
Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
-Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht
-beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt
-\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen.
-\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der
-Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet
-sich in Tabelle~\ref{tbl:sn-ev-oem-fast}.
+Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Beispielsweise
+benötigt das 19-Sortiernetzwerk, das in Abbildung~\ref{fig:19-e1-oem-fast}
+dargestellt ist, nur 13~Schichten, während \oes{19} 14~Schichten benötigt.
+
+\begin{figure}
+ \begin{center}
+ \input{images/19-e1-oem-fast.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+ unter Verwendung des \emph{Odd-Even}-Mischers erzeugt.}
+ \label{fig:19-e1-oem-fast}
+\end{figure}
%\begin{figure}
%\begin{center}
%\label{fig:10-e2-1239014566}
%\end{figure}
-\begin{table}\label{tbl:sn-ev-oem-fast}
-\begin{center}
-\rowcolors{4}{black!5}{}
-\begin{tabular}{|r|r|r|r|r|}
-\hline
-Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
-\cline{2-5}
- & Komp. & Schichten & Komp. & Schichten \\
-\hline
- 8 & 19 & 6 & 19 & 6 \\
- 9 & 26 & 8 & 26 & 8 \\
- 10 & 31 & 9 & 31 & 9 \\
- 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
- 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
- 13 & 48 & 10 & 48 & 10 \\
- 14 & 53 & 10 & 53 & 10 \\
- 15 & 59 & 10 & 59 & 10 \\
- 16 & 63 & 10 & 63 & 10 \\
- 17 & 74 & 12 & 74 & 12 \\
- 18 & 82 & 13 & 82 & 13 \\
- 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
- 20 & 97 & 14 & 97 & 14 \\
- 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
- 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
- 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\
- 24 & 128 & 15 & \gcell 127 & 15 \\
-\hline
-\end{tabular}
-\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
- unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
- Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
- gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
- nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
- 1$, $w_{\mathrm{Schichten}} = n$.}
-\end{center}
-\end{table}
-
\subsection{Zufälliger Mischer}
Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
um das beste Ergebnis beider Konstruktionen zu erreichen.
\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
-\emph{Odd-Even}-Mischer wählen.
-
-Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des
-Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast}
-zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der
-Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem
-Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und
-20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen
-Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz.
+\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.
\begin{table}\label{tbl:sn-ev-rnd-fast}
\begin{center}
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 \\
+ 23 & 129 & 14 & \Gcell 127 & 14 & 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
+ unter Verwendung der beiden Mischer-Netzwerke. 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{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$ und
$w_{\mathrm{Schichten}} = n$.}
\end{center}
\end{table}
+Bei einigen Leitungszahlen kann der Algorithmus durch die Verfügbarkeit beider
+Mi\-scher-Netzwerke Sortiernetzwerke zurückgeben, die effizienter als die
+vorherigen Ergebnisse sind. Beispielsweise ist das 19-Sortiernetzwerk in
+Abbildung~\ref{fig:19-e1-rnd-fast} mit 92~Komparatoren effizienter als die
+19-Sortiernetzwerke, die mit nur einem der beiden Mischer-Netzwerke erreicht
+wurden (Abbildungen~\ref{fig:19-e1-bm-fast} und~\ref{fig:19-e1-oem-fast}).
+
+\begin{figure}
+ \begin{center}
+ \input{images/19-e1-rnd-fast.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 92~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+ unter Verwendung des \emph{bitonen Mischers} und des
+ \emph{Odd-Even}-Mischers erzeugt.}
+ \label{fig:19-e1-rnd-fast}
+\end{figure}
+
+Die Ergebnisse anderer Leitungszahlen erreichen die Geschwindigkeit der
+Ergebnisse, die mit dem \emph{bitonen Mischer} erzielt wurden. Die Effizienz
+liegt zwischen den Ergebnissen, die mit dem \emph{bitonen Mischer} erzielt
+wurden, und den Ergebnissen, die mit dem \emph{Odd-Even}-Mischer erzielt
+wurden. Beispielsweise ist das 18-Sortiernetzwerk in
+Abbildung~\ref{fig:18-e1-rnd-fast} so schnell wie das Ergebnis, das mit dem
+\emph{bitonen Mischer} ausgegeben wurde. Mit 83~Komparatoren liegt die
+Effizienz des Sortiernetzwerks zwischen den Ergebnissen, die mit dem
+\emph{bitonen Mischer} (87~Komparatoren), beziehungsweise dem
+\emph{Odd-Even}-Mischer (82~Komparatoren) erreicht werden konnten.
+
+\begin{figure}
+ \begin{center}
+ \input{images/18-e1-rnd-fast.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 18~Leitungen und 83~Komparatoren in
+ 12~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
+ unter Verwendung des \emph{bitonen Mischers} und des
+ \emph{Odd-Even}-Mischers erzeugt.}
+ \label{fig:18-e1-rnd-fast}
+\end{figure}
+
+In einigen Fällen hat \textsc{SN-Evolution} in dieser Konfiguration
+Sortiernetzwerke ausgegeben, die weniger effizient und genauso schnell wie die
+bisherigen Ergebnisse unter Verwendung des \emph{Odd-Even}-Mischers sind.
+Prinzipiell könnte der Algorithmus in jeder Iteration zufällig den
+\emph{Odd-Even}-Mischers auswählen, um die selektierten Individuen zu
+rekombinieren. Das heißt, das die Ergebnisse auch bei einer zufälligen Wahl
+des Mischer-Netzwerks theoretisch erreicht werden können. Allerdings sind
+unter Umständen mehr Iterationen notwendig, bis die gleiche Effizienz erreicht
+wird.
+
%\input{shmoo-aequivalenz.tex}
\newpage
\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
\label{sect:sn-evolution-cut:bs}
+% Effizienz
+
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
benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
+% Beispiel Effizienz
+
\begin{figure}
\begin{center}
\input{images/16-ec-from-bs22.tex}
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}
+% Geschwindigkeit
Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.
+% Beispiel Geschwindigkeit
+
+\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 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
reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
noch größer gewählt werden.
+% Detaillierte Betrachtung fuer m = 19
+
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
35 & 93 & 13 \\
\rowcolor{green!10}
36 & 92 & 13 \\
- \rowcolor{green!10!white!95!black}
+ \rowcolor{green!10!white!95!black}
37 & 92 & 13 \\
38 & 93 & 13 \\
\hline
\label{tbl:ec-bs-19}
\end{table}
+% 2-er Potenz
+
\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode
konstruiert wurde, durch systematisches Entfernen von Leitungen in einen
\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.}
+ \caption{Visualisierung eines 16-Schnittmusters, das von
+ \textsc{SN-Evolution-Cut} für das \emph{bitone Mergesort}-Netzwerk \bs{32}
+ berechnet wurde. Das resultierende Sortiernetzwerk besteht aus
+ 68~Komparatoren in 10~Schichten und ist in
+ Abbildung~\ref{fig:16-ec-from-bs32-normalized} als
+ Standard-Sortiernetzwerk dargestellt.}
\label{fig:16-ec-from-bs32}
\end{figure}
\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.}
+ 10~Schichten. Das Netzwerk wurde mit einem 16-Schnittmuster, das von
+ \textsc{SN-Evolution-Cut} berechnet wurde, aus dem \emph{bitone
+ Mergesort}-Netzwerk \bs{32} erzeugt. Das Schnittmuster ist in
+ Abbildung~\ref{fig:16-ec-from-bs32} dargestellt.}
\label{fig:16-ec-from-bs32-normalized}
\end{figure}
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
+\oes{m}&19& 26 & 31 & 37 & 41 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
+\hline
\end{tabular}
\end{center}
\caption{Anzahl der Komparatoren der Ergebnisse von
27 & 91 & 14 \\
28 & 91 & 14 \\
29 & 95 & 13 \\
+ \rowcolor{green!10}
30 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
31 & 93 & 13 \\
+ \rowcolor{green!10}
32 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
33 & 93 & 13 \\
+ \rowcolor{green!10}
34 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
35 & 93 & 13 \\
+ \rowcolor{green!10}
36 & 93 & 13 \\
+ \rowcolor{green!10!white!95!black}
37 & 93 & 13 \\
+ \rowcolor{green!10}
38 & 93 & 13 \\
\hline
\bs{19} & 98 & 14 \\
\label{tbl:ec-oes-19}
\end{table}
+% 2-er Potenzen
+
In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und
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
+bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} ist, ist
$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
\label{fig:16-ec-from-oes32}
\end{figure}
+% Regelmaessiges Schnittmuster fuer n = 2^d
+
Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
-Beobachtung kann man das regelmäßige Schnittmuster
+Beobachtung kann das regelmäßige Schnittmuster
\begin{displaymath}
\textit{Eingang}_i = \left\{ \begin{array}{rl}
\infty & \quad \textrm{falls } i \bmod 4 = 0 \\
? & \quad \mathrm{sonst}
\end{array} \right.
\end{displaymath}
-ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
-Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
-Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
-32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
-ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
+abgeleitet werden. Es entfernt die Hälfte der Leitungen, vorausgesetzt die
+Anzahl der Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt
+effiziente Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine
+Zweierpotenz ist. Ein 32-Sortiernetzwerk, das mit diesem Schnittmuster aus
+\oes{64} erzeugt wurde, ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
\begin{figure}
\begin{center}
\label{fig:32-ec-from-oes64}
\end{figure}
-Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
-erzeugten Sortiernetzwerke die Effizienz des
+Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die durch
+dieses regelmäßige Schnittmuster erzeugten Sortiernetzwerke die Effizienz des
\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
beider Sortiernetzwerke ist mit 10~Schichten identisch.
-Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
-und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
-verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
-Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
-22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
+% SN-Evolution-Cut vs. regelmaessiges Schnittmuster
+
+Wird der \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{n}, $n = 22, 23, 24$
+und $k = 10, 11, 12$ gestartet, hängt die Ausgabe von der verwendeten
+Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der Algorithmus
+Schnittmuster wie das 12-Schnittmus\-ter $\operatorname{MIN}(6, 7, 8, 9, 16, 17,
+20, 22)$, $\operatorname{MAX}(2, 4, 12, 14)$ für \oes{24}, dessen Ergebnis in
Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
-sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
-angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
-\oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
+sehen, weitere Ergebnisse für diese Gütefunktion sind in den
+Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} zusammengefasst.
+Das resultierende 12-Sortiernetzwerk besteht aus 43~Komparatoren, die
+in 9~Schichten angeordnet sind. Das resultierende Netzwerk zwar nicht so
+effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
\begin{figure}
\centering
\label{fig:12-ec-from-oes24}
\end{figure}
-Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
-findet Sortiernetzwerke, die schneller sind als das entsprechende
-\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit
-22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige
-schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können,
-charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
-\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
-\begin{center}
-\begin{tabular}{|r|r|r|r|r|}
-\hline
-Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
- & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
-\hline
-11 & 38 & 9 & 37 & 10 \\
-12 & 43 & 9 & 41 & 10 \\
-19 & 93 & 13 & 91 & 14 \\
-20 & 101 & 13 & 97 & 14 \\
-21 & 108 & 14 & 107 & 15 \\
-22 & 116 & 14 & 114 & 15 \\
-23 & 125 & 14 & 122 & 15 \\
-\hline
-\end{tabular}
-\end{center}
-Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
-23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
-Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
-Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
-beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
-\bs{23} beziehungsweise \oes{23} eine Schicht einspart.
-
-\begin{figure}
- \begin{center}
- \input{images/23-ec-from-oes46-fast.tex}
- \end{center}
- \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten.
- Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
- Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
- 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
- erzeugt.}
- \label{fig:23-ec-from-oes46}
-\end{figure}
-
\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
-Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
-Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
-(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
-ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
-wie und warum es jede beliebige Eingabe sortiert.
+Eine weitere interessante Eingabe für \textsc{SN-Evolution-Cut} ist das
+\emph{Pairwise-Sorting}-Netzwerk \ps{n}, das \textit{Ian
+Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
+definiert. Einerseits wurde in Abschnitt~\ref{sect:anzahl_schnittmuster}
+gezeigt, dass es für \ps{n} sehr viele \emph{unterschiedliche} Schnittmuster
+gibt. Andererseits sind die Sortiernetzwerke, die nach \textit{Parberrys}
+Methode erzeugt werden, genauso schnell und effizient wie das
+\emph{Odd-Even-Mergesort}-Netzwerk, wenn die Leitungszahl $n = 2^d$ eine
+Zweierpotenz ist.
+
+% Effizienz
+
+Für viele Kombinationen von \ps{n} und $k$ sind die Sortiernetzwerke, die
+\textsc{SN-Evolution-Cut} ausgibt, weniger effizient als das entsprechende
+\ps{m}-Netzwerk. Für einige Kombinationen werden jedoch auch effizientere
+Netzwerke generiert, beispielsweise für $m = 11$ und $m = 20$. Die Effizienz
+der Sortiernetzwerke, die \textsc{SN-Evolution-Cut} auf Basis des
+\emph{Pairwise-Sorting}-Netzwerks berechnet, ist tabellarisch in
+Tabelle~\ref{tbl:ec-ps-efficiency} dargestellt.
\begin{table}
\begin{center}
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-efficiency}
+\end{table}
+
+% Beispiel Effizienz
+
+Zwei Ergebnisse, die effizienter als die entsprechenden
+\emph{Pairwise-Sorting}-Netzwerke sind, zeigt
+Abbildung~\ref{fig:ec-ps-efficient_networks}. Sie erreichen die
+Geschwindigkeit und Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks mit der
+entsprechenden Leitungszahl. Bei größeren Netzwerken, beispielsweise $m = 19$,
+ist dies mit der in Tabelle~\ref{tbl:ec-ps-efficiency} dargestellten Größe der
+Schnittmuster noch nicht zu beobachten.
+
+\begin{figure}
+ \centering
+ \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Pairwise-Sorting}-Netzwerk \ps{13}
+ erzeugt.]{\input{images/11-ec-from-ps13.tex}}
+ \subfigure[12-Sortiernetzwerk aus 41~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Pairwise-Sorting}-Netzwerk \ps{16}
+ erzeugt.]{\input{images/12-ec-from-ps16.tex}}
+ \caption{Zwei effiziente Sortiernetzwerke, die durch Schnittmuster, die von
+ \emph{SN-Evolution-Cut} berechnet wurden, aus dem
+ \emph{Pairwise-Sorting}-Netzwerk \ps{n} erzeugt wurden.}
+ \label{fig:ec-ps-efficient_networks}
+\end{figure}
+
+% Wie viele Schnitte man braucht.
+
+Bei welchen Parametern \textsc{SN-Evolution-Cut} effiziente
+19-Sortiernetzwerke findet, ist Tabelle~\ref{tbl:ec-ps-19} zu entnehmen. Für
+$n = 31$, $k = 12$ und $n = 32$, $k = 13$ werden 19-Sortiernetzwerke mit der
+selben Effizienz und Geschwindigkeit wie \oes{19} erzeugt. Das
+19-Sortiernetzwerk, das auf diese Art und Weise aus \ps{32} erzeugt wurde, ist
+in Abbildung~\ref{fig:19-ec-from-ps32} dargestellt.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 97 & 15 \\
+ 21 & 96 & 15 \\
+ 22 & 96 & 15 \\
+ 23 & 97 & 14 \\
+ 24 & 96 & 14 \\
+ 25 & 93 & 14 \\
+ 26 & 92 & 14 \\
+ 27 & 94 & 14 \\
+ 28 & 94 & 14 \\
+ 29 & 92 & 14 \\
+ 30 & 92 & 14 \\
+ \rowcolor{green!10!white!95!black}
+ 31 & 91 & 14 \\
+ \rowcolor{green!10}
+ 32 & 91 & 14 \\
+ 33 & 101 & 15 \\
+ 34 & 104 & 15 \\
+ 35 & 106 & 15 \\
+ 36 & 107 & 15 \\
+ 37 & 106 & 15 \\
+ 38 & 102 & 15 \\
+ \hline
+ \ps{19} & 97 & 15 \\
+ \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 \ps{n}, $n = 20, \dots, 38$ erzeugt
+ wurden.}
+ \label{tbl:ec-ps-19}
+\end{table}
+
+\begin{figure}
+ \begin{center}
+ \input{images/19-ec-from-ps32.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 19~Leitungen und 91~Komparatoren in
+ 14~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+ $\operatorname{PS}(32)$ erzeugt.}
+ \label{fig:19-ec-from-ps32}
+\end{figure}
+
+An den Daten in Tabelle~\ref{tbl:ec-ps-19} fällt auf, dass die Effizienz und
+Geschwindigkeit der Ergebnisse für $n > 32$ schlechter werden. Das
+\emph{Pairwise-Sorting}-Netzwerk ist Leitungszahlen, die Zweierpotenzen sind,
+besonders effizient und schnell. Um der Vermutung nachzugehen, dass der
+\textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente
+Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1
+\dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32}
+zusammengefasst.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $m$ & Komp. & Schichten \\
+ \hline
+ 16 & 69 & 11 \\
+ 17 & 77 & 13 \\
+ 18 & 89 & 13 \\
+ 19 & 91 & 14 \\
+ 20 & 97 & 14 \\
+ 21 & 107 & 15 \\
+ 22 & 114 & 15 \\
+ 23 & 122 & 15 \\
+ 24 & 127 & 15 \\
+ 25 & 138 & 15 \\
+ 26 & 146 & 15 \\
+ 27 & 155 & 15 \\
+ 28 & 161 & 15 \\
+ 29 & 171 & 15 \\
+ 30 & 178 & 15 \\
+ 31 & 186 & 15 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren und Schichten von $m$-Sortiernetzwerken,
+ die von \textsc{SN-Evolution-Cut} nach 5.000.000 Iterationen aus \ps{32}
+ erzeugt wurden.}
+ \label{tbl:ec-ps-32}
+\end{table}
+
+% Geschwindigkeit
+
+Die Schnittmuster, die \textsc{SN-Evolution-Cut} für das
+\emph{Pairwise-Sorting}-Netzwerk berechnet, können zu schnelleren
+Sortiernetzwerken als \ps{m} führen. Beispielsweise konnte aus \ps{24} ein
+18-Sortiernetzwerk erzeugt werden, das mit 13~Schichten zwei parallele
+Schritte im Vergleich zu \ps{18} einspart. Eine Darstellung dieses
+Sortiernetzwerks befindet sich in Abbildung~\ref{fig:18-ec-from-ps24}. Für
+andere $m$ wurde die Geschwindigkeit des \emph{Pairwise-Sorting}-Netzwerks
+nicht übertroffen und im Fall von $m = 16$ wurde die Geschwindigkeit nicht
+einmal 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 & 10 & & & & & & & & & & & & & & \\
+ 11 & 6 & 9 & 10 & & & & & & & & & & & & & \\
+ 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 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & & & & & & & \\
+ 18 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & & & & & & \\
+ 19 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & & & & & \\
+ 20 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & 15 & & & & \\
+ 21 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 15 & 15 & 15 & & & \\
+ 22 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 14 & 15 & 15 & 15 & & \\
+ 23 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 14 & 14 & 15 & 15 & 15 & \\
+ 24 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 13 & 14 & 14 & 15 & 15 & 15 \\
+ \hline
+ \ps{m} & 6 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 15 & 15 & 15 & 15 & 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{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
\label{tbl:ec-ps-speed}
\end{table}
-Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
-Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
-definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
-$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
-ein Sortiernetzwerk, das die gleiche Anzahl Komparatoren und Schichten hat wie
-$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser
+% Beispiel Geschwindigkeit
+
+\begin{figure}
+ \begin{center}
+ \input{images/18-ec-from-ps24.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 18~Leitungen und 89~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+ $\operatorname{PS}(24)$ erzeugt.}
+ \label{fig:18-ec-from-ps24}
+\end{figure}
+
+% 2-er Potenz
+
+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.
+
+Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet
+man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
+16~Leitungen zu entfernen, kann der Algorithmus ein Sortiernetzwerk
+zurückgeben, das die gleiche Anzahl Komparatoren und Schichten wie
+$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$ hat. Eines dieser
Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+Dieses Ergebnis demonstriert, dass sich die Ergebnisse in den gezeigten
+Tabellen oft durch zusätzliche Iterationen verbessern lassen.
\begin{figure}
\begin{center}
\label{fig:16-ec-from-ps32}
\end{figure}
-Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
+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
\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}.
+Ein Spezialfall ergibt sich, wenn \textsc{SN-Evolution-Cut} auf
+$\operatorname{PS}(16)$ angewendet wird: In diesem Fall kann ein
+8-Schnittmuster ausgegeben werden, das \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{8} aus \ps{16} erzeugt.. 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}
projects / diplomarbeit.git / blobdiff