zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
Ausgabe und kann entfernt werden.
+\subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
+\label{sect:anzahl_schnittmuster}
+
Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
$n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
-mit $n$~Eingängen reduzieren.
+mit $n$~Eingängen reduzieren. Das Anwenden mehrerer Minimum- und
+Maximum-Schnitte bezeichnen wir als \emph{Schnittmuster}.
-\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
+auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
+Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
\prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
\quad (n > m)
\end{displaymath}
-Möglichkeiten. Diese Möglichkeiten sind nicht alle unterschiedlich. Legt man
-beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die
-oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum
-selben Ergebnis.
+\emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
+unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung
+und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks,
+führen beide Reihenfolgen zum selben Ergebnis.
\textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
-Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte
-reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber
-unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus
+Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnittmuster
+reduziert, die Menge der so erzeugbaren Sortiernetzwerke bleibt aber
+unverändert. Die Anzahl der möglichen Schnittmuster setzt sich zusammen aus
der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
-Formel:
+Formel für die Anzahl der Schnittmuster:
\begin{displaymath}
2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
= 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
\quad (n > m)
\end{displaymath}
-Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
+Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
-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.
+ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit
+16~Schnitten notwendig, für das 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.
+
+Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
+als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der
+ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
+Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
+unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
+der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
+Werte unterscheiden.
+
+Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
+Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des
+Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
+unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
+erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
+Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
+Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
+sich die Resultate auch in der ersten Schicht nicht unterscheiden.
+
+\subsubsection{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+\label{sect:sn-evolution-cut}
Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
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$.
+Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet die \emph{Schnittmuster}
+als Individuen. Um zwei Individuen zu rekombinieren werden die ersten
+$r$~Schnitte des einen Schnittmusters verwendet und die letzten
+${c-r}$~Schnitte des zweiten Schmittmusters. $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.
+% bitones Mergesort-Netzwerk
+
In \cite{MW2010} 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
16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in
Abbildung~\ref{fig:16-ec-1277186619} zu sehen.
+% Odd-Even-Transpositionsort-Netzwerk
+
+Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so
+ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$
+erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein
+zufällig zu sein. Dies ist jedoch kein Eigenschaft des Algorithmus, sondern
+hängt insbesondere von der Eingabe ab. Wird \textsc{SN-Evolution-Cut}
+beispielsweise mit dem \emph{Odd-Even-Transpositionsort-Netzwerk}
+$\operatorname{OET}(n)$ und $m$~Schnitten gestartet, so ist das beste Ergebnis
+immer das $\operatorname{OET}(n-m)$-Netzwerk.
+
\begin{figure}
\begin{center}
\input{images/16-ec-from-ps32.tex}
\label{fig:16-ec-from-ps32}
\end{figure}
-Betrachtet man das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619}, so
-ist keine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$
-erkennbar -- insbesondere die ersten Schichten des Netzwerks scheinen rein
-zufällig zu sein. Dies ist jedoch kein Eigenschaft des Algorithmus, sondern
-hängt insbesondere von der Eingaben. Wird \textsc{SN-Evolution-Cut}
-beispielsweise mit dem \emph{Odd-Even-Transpositionsort-Netzwerk}
-$\operatorname{OET}(n)$ und $m$~Schnitten gestartet, so ist das beste Ergebnis
-immer das $\operatorname{OET}(n-m)$-Netzwerk.
+% Pairwise-Sorting-Netzwerk
Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
-Pairwise Sorting Network“ definiert. Startet man \textsc{SN-Evolution-Cut} mit
-$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
-ein Sortiernetzwerk, dass die gleiche Anzahl an Komparatoren und Schichten hat
-wie $\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Der Algorithmus gibt
-auch nach zahlreichen Versuchen nur eines von zwei Sortiernetzwerken zurück,
-die beide sehr symmetrisch sind und eine saubere Struktur aufweisen. Eines der
-beiden Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32}
-dargestellt, das andere Sortiernetzwerk unterscheidet sich lediglich dadurch,
-dass die zweite und dritte Schicht vertauscht sind.
+Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
+\textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
+16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche
+Anzahl an Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
+$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
+Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht
einsetzt und auch nicht auf einem Mischer basiert, ist der
sowie 4~und~5 sind vertauscht, was jeweils zum selben Ergebnis nach dem
Schichtenpaar führt.
+\begin{displaymath}
+\textit{Eingang}_i = \left\{ \begin{array}{rl}
+ -\infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{0, 6\} \\
+ \infty & \quad \textrm{falls } i \operatorname{mod} 8 \in \{2, 4\} \\
+ ? & \quad \mathrm{sonst}
+ \end{array} \right.
+\end{displaymath}
+
+\begin{figure}
+ \begin{center}
+ \input{images/32-pairwise-cut-16-pairwise.tex}
+ \end{center}
+ \caption{PS(32) mit 16 Schnitten zu PS(16).}
+ \label{fig:ps16-from-ps32}
+\end{figure}
+
+\begin{figure}
+ \begin{center}
+ \input{images/16-pairwise.tex}
+ \end{center}
+ \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
+ ($\operatorname{MIN}(0,2,4,6), \operatorname{MAX}(9,11,13,15)$). Das
+ resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
+ \label{fig:16-pairwise}
+\end{figure}
+
Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann
man $\operatorname{OES}(8)$ erhalten.
+% Odd-Even-Mergesort-Netzwerk
+
+\todo{Schreibe noch etwas zum Odd-Even-Mergesort-Netzwerk.}
+
\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 Wieviele Schnitte ergeben das selbe Netzwerk? Oder andersrum: Wieviele
+ unterschiedliche Netzwerke kann ich erhalten? Wieviele Nachfolger hat ein
+ Netzwerk / Knoten in der Markov-Kette?
\item Abschnitt „Optimierung der Schnitte“ hier einbauen.
\end{itemize}
ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
selbst erzeugen kann.
+Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben ist die Anzahl
+(unterschiedlichen) Schnittmuster und damit die Anzahl der Nachfolger sehr
+groß. Wenn $S_0$ ein Sortiernetzwerk mit $n$~Leitungen ist, so hat $S_0$ bis
+zu
+\begin{displaymath}
+ 2^n \cdot \left( \begin{array}{c} 2n \\ n \end{array} \right)
+\end{displaymath}
+Nachfolger.
+
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
projects / diplomarbeit.git / commitdiff