From 115b6d1044caab5badfbc4a159d205e8fb05f6f7 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Mon, 10 Jan 2011 09:35:39 +0100 Subject: [PATCH] Anzahl Schnittmuster. --- diplomarbeit.tex | 155 ++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 108 insertions(+), 47 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 25a921f..5274b90 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -839,13 +839,19 @@ Darstellung ergibt. Ausserdem ist das 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 @@ -856,19 +862,19 @@ sich insgesamt \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!} @@ -876,12 +882,32 @@ Formel: \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 @@ -891,25 +917,18 @@ 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$. +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 @@ -941,6 +960,17 @@ 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. +% 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} @@ -952,26 +982,16 @@ Abbildung~\ref{fig:16-ec-1277186619} zu sehen. \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 @@ -982,13 +1002,45 @@ strukturell identisch zu $\operatorname{PS}(8)$ sind -- die Schichten~1 und~2 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} @@ -1148,6 +1200,15 @@ Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $ 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 -- 2.11.0