From 8c3620f715482f736048ffecea55af6c37e99f00 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Fri, 17 Dec 2010 17:35:15 +0100 Subject: [PATCH] Leitungen entfernen: Etwas zu den Ergebnissen mit dem Pairwise Network geschrieben. --- diplomarbeit.tex | 49 +++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 41 insertions(+), 8 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 76b941a..110b37e 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -931,13 +931,6 @@ 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} - \begin{figure} \begin{center} \input{images/16-ec-from-ps32.tex} @@ -946,9 +939,49 @@ Abbildung~\ref{fig:16-ec-1277186619} zu sehen. 10~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} - \label{fig:16-ec-1277186619} + \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. + +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. + +Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even-Mischer} nicht +einsetzt und auch nicht auf einem Mischer basiert, ist der +$\operatorname{OEM}(8,8)$ im Sortiernetzwerk in +Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In +den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die +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. + +Wendet man \textsc{SN-Evolution-Cut} auf $\operatorname{PS}(16)$ an, so kann +man $\operatorname{OES}(8)$ erhalten. + +\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 \textsc{SN-Evolution}-Algorithmus} Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden -- 2.11.0