% Fuer mathtoolsset
\usepackage{mathtools}
-\geometry{paper=a4paper,margin=25mm}
+\geometry{paper=a4paper,margin=30mm}
\pagestyle{fancy}
%\fancyhf{}
ausgegeben.
Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
-Ausgänge von {\em Komparatoren} mit dem Eingängen anderer {\em Komparatoren}
-verbindet, erhält man ein {\em Komparatornetzwerk}.
+Ausgänge von Komparatoren mit dem Eingängen anderer Komparatoren verbindet,
+erhält man ein {\em Komparatornetzwerk}.
\begin{figure}
\begin{center}
kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
+Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
+gleichzeitig angewandt werden. Das Beispiel in
+Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
+vergleicht in einem ersten Schritt die zwei oberen und die zwei unteren
+Leitungen gleichzeitig. Eine Gruppe von Komparatoren, die gleichzeitig
+angewendet werden können, nennt man eine \emph{Schicht} des
+Komparatornetwerks. Die \emph{Verzögerung} eines Komparatornetzwerks ist
+gleichbedeutend mit der Anzahl der Schichten, in die sich die Komparatoren
+mindestens gruppieren lassen, da sie die Anzahl der benötigten parallelen
+Schritte darstellt.
+
Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
{\em Sortiernetzwerke}. Das in
zerstört.
Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
-{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel also einfach möglich.
+{\em nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich.
Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
\todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
-$2^n$~${0-1}$-Folgen sortiert.
+$2^n$~0-1-Folgen sortiert.
Sortiernetzwerke:
\begin{itemize}
\begin{center}
\input{images/oe-transposition-8.tex}
\end{center}
-\caption{Das {\em Odd-Even-Transpositionsort} Netzwerk für acht Eingänge.}
+\caption{Das {\em Odd-Even-Transpositionsort-Netzwerk} für acht Eingänge.}
\label{fig:odd_even_transposition_08}
\end{figure}
\subsection{Odd-Even-Mergesort}
-Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und
-{\em Odd-Even-Transpositionsort} (OET, siehe
+Obwohl der Name ähnlich klingt, haben \emph{Odd-Even-Mergesort} (OEM) und
+\emph{Odd-Even-Transposition\-sort} (OET, siehe
Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
"`Mischer"' definiert.
Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
weniger Vergleichen aus als der {\em bitone Mischer}, der im
-Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde.
+Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde, aus.
Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
\begin{center}
\input{images/oe-mergesort-8.tex}
\end{center}
-\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge.}
+\caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
+sind die Instanzen von $S(4)$ (rot), die beiden \emph{Odd-Even-Mischer}
+$\mathit{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im letzten
+Rekursionsschritt hinzugefügten Komparatoren zwischen benachbarten Leitungen
+(grün).}
\label{fig:odd_even_mergesort_08}
\end{figure}
In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
-Richtung.
+Richtung. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen-
+und das Trichtermuster zu sehen.
\subsection{Zwei Netzwerke kombinieren}
Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
-ein Sortiernetzwerk mit 16~Eingängen zu reduzieren sind 16~Schnitte notwendig,
+ein Sortiernetzwerk mit 16~Ein\-gängen zu reduzieren sind 16~Schnitte notwendig,
für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
erheblichem Ressourcenaufwand möglich.
-Das Programm {\sc SN-Evolution-Cut} implementiert einen evolutionären
+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}.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
+Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
+gute Schnittmuster gesucht.
+
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die
+\emph{Schnitt-Sequenzen} als Individuen. 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.
+
+In ihrer Arbeit \textit{“Improving Bitonic Sorting by Wire Elimination”}
+zeigen \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka}, 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.
+
+Beispeilsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
+Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
+konstruiert wurde. Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger
+als das bitone Mergesort-Netzwerk nach Batchers Methode. Gegenüber Batchers
+Methode sparen so konstruierte Sortiernetzwerke ${\frac{1}{4}n(\log n - 1)}$
+Komparatoren ein.
+
+\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 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
+ $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
+ \label{fig:16-ec-1277186619}
+\end{figure}
+
+Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk
+$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
+Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
+16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
+Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
\begin{itemize}
\item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
\item Wie gut kann man durch wegschneiden werden?
\item Wieviele Schnitte ergeben das selbe Netzwerk?
+ \item Abschnitt „Optimierung der Schnitte“ hier einbauen.
\end{itemize}
\section{Der evolutionäre Ansatz}
\item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
\end{itemize}
-\subsection{Vom evolutionären Algorithmus zu einer Markov-Kette}
+\section{Markov-Kette}
+
+Der evolutionäre Algorithmus aus dem vorherigen Abschnitt verwendete immer
+zwei zufällige Sortiernetzwerke („Individuen“) aus einer Population. Da die
+beiden „Eltern“ zufällig und unabhängig voneinander ausgewählt werden, kann es
+vorkommen, dass das selbe Sortiernetzwerk zweimal verwendet und mit sich
+selbst kombiniert wird.
+
+Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das
+aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
+Leitungen eliminiert, lassen sich einige interessante Beobachtungen anstellen.
+Netzwerke, die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von
+$S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen
+hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
+
+Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
+gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
+Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
+Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$
+ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
+selbst erzeugen kann.
+
+Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg
+(englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen
+Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen
+rekombiniert er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
+einen zufälligen Nachfolger.
\begin{itemize}
-\item Kombiniere immer das aktuelle Netzwerk mit sich selbst.
-\item Kann die Mindestgüte immernoch erreicht werden? ({\em Ich denke schon.})
-\item Anzahl der erreichbaren Sortiernetzwerke.
+ \item $n \leftarrow \mathrm{Input}$
+ \item \texttt{while} \textit{true}
+ \begin{itemize}
+ \item $n \leftarrow \operatorname{recombine} (n, n)$
+ \end{itemize}
\end{itemize}
-%\input{shmoo-aequivalenz.tex}
-
-\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{itemize}
+ \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
+ \item Anzahl der erreichbaren Sortiernetzwerke.
+ \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
+ Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
+\end{itemize}
\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}
+ \begin{center}
+ \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf}
+ \end{center}
+ \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.}
+ \label{fig:markov-comparators-16}
\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.
+%\input{shmoo-aequivalenz.tex}
+
+\section{Optimierung der Schnitte}
+
+\todo{In den Abschnitt "`Leitungen entfernen"' einbauen.}
\begin{figure}
\begin{center}
\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
+ \textsc{SN-Evolution-Cut} aus dem Bitonic-Mergesort-Netzwerk $BS(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
+\textsc{SN-Evolution-Cut}-Algorithmus aus dem $BS(64)$-Netzwerk erzeugt wurde.
+Es besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
+$BS(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
+\textbf{TODO:} $BS(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.
+Komparatoren; $BS(64)$: 672~Komparatoren.
Schnitt-Sequenz:
MIN( 92)
projects / diplomarbeit.git / blobdiff