\section{Transformation von Sortiernetzwerken}
-\begin{itemize}
-\item Komprimieren (Alle Komparatoren so früh wie möglich anwenden).
-\item Normalisieren (Transformation zu Standard-Sortiernetzwerken).
-\end{itemize}
+\subsection{Komprimieren}
+
+\todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
+
+Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
+gleichzeitig ausgewertet werden, wie bereits in
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
+\emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
+von \emph{Schichten} verstanden.
+
+Diese Anzahl ist insbesondere beim automatisierten Bewerten von
+Komparatornetzwerken interessant. \dots
+
+\subsection{Normalisieren}
+
+\begin{figure}
+ \centering
+ \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
+ \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
+ \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
+ transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
+ intuitiven Konstruktion und die normalisierte Variante.}
+ \label{fig:beispiel_normalisieren}
+\end{figure}
+
+Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
+ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
+zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
+transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
+einen Algorithmus an.
+
+Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
+bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
+zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
+Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
+die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
+Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist.
+In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
+Definition.
+
+In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
+Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
+Richtung.
\subsection{Zwei Netzwerke kombinieren}
\begin{center}
\input{images/08-e2-1237993371.tex}
\end{center}
-\caption{\tt images/08-e2-1237993371.tex}
+\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
\label{fig:08-e2-1237993371}
\end{figure}
\begin{center}
\input{images/09-e2-1237997073.tex}
\end{center}
-\caption{\tt images/09-e2-1237997073.tex}
+\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
\label{fig:09-e2-1237997073}
\end{figure}
\begin{center}
\input{images/09-e2-1237999719.tex}
\end{center}
-\caption{\tt images/09-e2-1237999719.tex}
+\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
\label{fig:09-e2-1237999719}
\end{figure}
Die Anzahl der Netzwerke in den jeweiligen Gruppen ist unterschiedlich. Zur
Zeit sind in den Gruppen so viele Netzwerke:\\
\begin{tabular}{|l|r|r|} \hline
-Gruppe~0 & 18 & $48,7\%$ \\
-Gruppe~1 & 9 & $24,3\%$ \\
-Gruppe~2 & 6 & $16,2\%$ \\
-Gruppe~3 & 3 & $8,1\%$ \\
-Gruppe~4 & 1 & $2,7\%$ \\ \hline
+Gruppe~0 & 21 & $50,0\%$ \\
+Gruppe~1 & 10 & $23,8\%$ \\
+Gruppe~2 & 6 & $14,3\%$ \\
+Gruppe~3 & 3 & $7,1\%$ \\
+Gruppe~4 & 2 & $4,8\%$ \\ \hline
\end{tabular}
Die hinteren Schichten zwischen den Gruppen~1 und~3 schauen so aus, als wären
\item Anzahl der erreichbaren Sortiernetzwerke.
\end{itemize}
+\section{Optimierung der Schnitte}
+
+Der \emph{evolution-cut}-Algorithmus nimmt ein gegebenes Sortiernetzwerk mit
+$n$~Leitungen und sucht die beste Sequenz von $c$~Min- und Max-Schnitten um
+ein ${(n-c)}$-Sortiernetzwerk zu erhalten.
+
+Bei diesem Algorithmus werden die \emph{Schnitt-Sequenzen} als Individuen
+verwendet. Eine \emph{Schnitt-Sequenz} ist eine Liste mit $c$~Schnitten, die
+jeweils durch die Start-Leitung und die Richtung \textit{Min} beziehungsweise
+\textit{Max} gegeben ist. Der Algorithmus wendet jeden Schnitt einzeln an, so
+dass eine Leitungsnummer mehrfach in einer Schnittsequenz vorkommen kann. Die
+höchste zulässige Leitungsnummer ist abhängig von der Position des Schnitts in
+der Sequenz. Der Schnitt an Position~$i$ darf höchstens die
+Leitungsnummer~${n-i-1}$ enthalten.\footnote{Die niedrigste Leitungsnummer ist
+$0$, die höchste Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.}
+
+Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen
+Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten
+Sequenz. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
+
+Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
+auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
+Schnitt-Richtung.
+
+\begin{figure}
+\begin{center}
+\input{images/16-ec-1277186619.tex}
+\end{center}
+\caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
+ und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(32)$ durch
+ 16~Schnitte erzeugt.}
+\label{fig:16-ec-1277186619}
+\end{figure}
+
+Wendet man den \emph{evolution-cut}-Algorithmus auf das
+Bitonic-Mergesort-Netzwerk $M(n)$ an und setzt die Anzahl der Schnitte~$c$ auf
+$\frac{n}{2}$, so erhält man Sortiernetzwerke, die weniger Komparatoren
+benötigen als $M(\frac{n}{2})$.
+
+Das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619} ist entstanden,
+indem der Algorithmus \emph{evolution-cut} auf das $M(32)$-Sortiernetzwerk
+angewendet wurde. Der Algorithmus fand eine Schnitt-Sequenz aus 16~Schnitten,
+die ein Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in 10~Schichten
+erzeugt. Das $M(16)$-Sortiernetzwerk besteht aus 80~Komparatoren in
+10~Schichten.
+
+Dieses Ergebnis deckt sich mit dem Sortiernetzwerk, dass
+\emph{Moritz Mühlenthaler} und \emph{Rolf Wanka} in ihrer Veröffentlichung
+„Improving Bitonic Sorting by Wire Elimination“ vorstellen. Sie verwenden
+Schnitte, um Komparatoren beim bitonen $(n,n)$-Mischer enizusparen. Ein
+sukzessive aus optimieren Mischern aufgebautes Sortiernetzwerk spart
+--~verglichen mit dem Bitonic-Mergesort-Netzwerk~-- $\frac{1}{4}n(\log n - 1)$
+Komparatoren ein. Bei einem Sortiernetzwerk mit 16~Leitungen also
+12~Komparatoren -- 68 statt 80.
+
+\begin{figure}
+\begin{center}
+\input{images/32-ec-1277190372.tex}
+\end{center}
+\caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen
+ und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(64)$ durch
+ 32~Schnitte erzeugt.}
+\label{fig:32-ec-1277190372}
+\end{figure}
+
+Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom
+\emph{evolution-cut}-Algorithmus aus dem $M(64)$-Netzwerk erzeugt wurde. Es
+besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
+$M(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
+und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
+Netzwerken gleich.
+
+\textbf{TODO:} $M(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
+möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
+Komparatoren; $M(64)$: 672~Komparatoren.
+
+Schnitt-Sequenz:
+MIN( 92)
+MAX( 80)
+MIN(100)
+MAX( 54)
+MAX(102)
+MAX( 53)
+MAX(105)
+MAX( 6)
+MAX( 99)
+MAX( 79)
+MAX( 26)
+MIN(111)
+MAX( 12)
+MIN( 22)
+MAX( 61)
+MAX( 72)
+MAX( 68)
+MIN( 80)
+MAX( 80)
+MAX( 99)
+MAX(105)
+MAX( 0)
+MIN( 8)
+MAX( 40)
+MAX( 74)
+MAX( 40)
+MAX( 40)
+MIN( 56)
+MAX( 27)
+MAX( 13)
+MAX( 1)
+MAX( 81)
+MAX( 17)
+MAX( 4)
+MIN( 36)
+MIN( 22)
+MAX( 13)
+MIN( 72)
+MAX( 24)
+MAX( 5)
+MIN( 10)
+MAX( 59)
+MIN( 37)
+MAX( 65)
+MAX( 46)
+MAX( 73)
+MAX( 58)
+MAX( 29)
+MAX( 65)
+MIN( 23)
+MAX( 56)
+MAX( 11)
+MIN( 75)
+MIN( 51)
+MIN( 46)
+MIN( 34)
+MAX( 32)
+MAX( 6)
+MAX( 37)
+MIN( 4)
+MIN( 28)
+MIN( 20)
+MAX( 33)
+MAX( 34)
+
+% images/32-ec-1277190372.tex
+
\section{Empirische Beobachtungen}
\begin{itemize}
projects / diplomarbeit.git / blobdiff