\end{abstract}
\newpage
+\section*{Eidesstattliche Erklärung}
+
+Ich versichere, dass ich die vorliegende wissenschaftliche Arbeit
+selbstständig verfasst und keine anderen als die angegebenen Hilfsmittel
+verwendet habe. Die Stellen der Arbeit, die anderen Werken dem Wortlaut oder
+dem Sinn nach entnommen sind, wurden unter Angabe der Quelle als Entlehnung
+deutlich gemacht. Das Gleiche gilt auch für beigegebene Skizzen und
+Darstellungen. Diese Arbeit hat in gleicher oder ähnlicher Form meines Wissene
+nach noch keiner Prüfungsbehörde vorgelegen.
+\\[3cm]
+München, den 20.~März 2011,\\
+\\[1cm]
+Florian Forster
+\newpage
+
\tableofcontents
\newpage
-- 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}
erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
\textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
-findet er aber in der Regel bessere Lösungen.
+findet er aber in der Regel bessere Lösungen. Die Rolle, die
+\textit{Exploitation} und \textit{Exploration} bei evolutionären
+Optimierungsalgorithmen spielen, wird von \textit{Eiben} und
+\textit{Schippers} in~\cite{ES1998} untersucht.
Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
-zwischen verschiedenen Leitungszahlen stark unterscheiden.
+zwischen verschiedenen Leitungszahlen stark unterscheiden. Einen Überblick
+geben \textit{Kalyanmoy Deb} und \textit{Samir Agrawal} in~\cite{DA1998}.
Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
in Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der
Mutation einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
-\begin{figure} \begin{center} \input{images/16-hillis.tex} \end{center}
-\caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
-Es besteht aus 61~Komparatoren in 11~Schichten.} \label{fig:16-hillis}
-\end{figure} Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
+\begin{figure}
+ \begin{center}
+ \input{images/16-hillis.tex}
+ \end{center}
+ \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
+ Es besteht aus 61~Komparatoren in 11~Schichten.}
+ \label{fig:16-hillis}
+\end{figure}
+Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
\emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
zu optimieren~\cite{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
+\textit{Michael~L. Harrison} und \textit{James~A. Foster} nutzten ebenfalls
+\emph{Co-Evolution} in~\cite{HF2004}, um die Stabilität von Sortiernetzwerken
+zu erhöhen. Die zweite Population bestand aus \emph{Fehlern} -- der
+Information, welche Komparatoren defekt, beziehungsweise inaktiv sind. So
+generierte Sortiernetzwerke können auch dann noch für viele Eingaben eine
+korrekt sortierte Ausgabe erzeugen, wenn ein oder mehrere Komparatoren
+(zufällig) entfernt werden.
+
\begin{figure}
\centering
\subfigure{\input{images/13-juille-0.tex}}
"`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}
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 Streben zu (lokalen) Optima, verstärkt.
+Exploitation}, das Streben zu (lokalen) Optima, verstärkt. In~\cite{WW2002}
+geben \textit{Karsten und Nicole Weicker} einen Überblick über
+Selektionsmethoden und Rekombinationsmöglichkeiten.
Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
w_{\mathrm{Schichten}} &=& 1
\end{eqnarray*}
geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
-einer Schicht. \todo{Fehler hier noch was?}
+einer Schicht.
\subsection{Selektion}
\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
\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