From 6b2c14e2dbbb4a2ca86032cdc228d4fc96ce6543 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Tue, 22 Jun 2010 10:10:39 +0200 Subject: [PATCH] Neuer Abschnitt: "Optimierung der Schnitte". --- diplomarbeit.tex | 146 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 146 insertions(+) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 8123dab..a861992 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -908,6 +908,152 @@ Schichten 4--9 identisch zu 16-e1-1258030047 (Gruppe~1).} \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} -- 2.11.0