From: Florian Forster Date: Tue, 11 Jan 2011 18:01:40 +0000 (+0100) Subject: sn-evolution-cut ausgebaut. X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=commitdiff_plain;h=c383c2d71472004127a6ae08d689c02b94aa8661 sn-evolution-cut ausgebaut. --- diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 7c76502..c6d3fe8 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -56,11 +56,13 @@ \tikzstyle{edge maximum} = [edge,color=red!20] \tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50] \tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50] +\tikzstyle{vertex active minimum maximum} = [vertex,color=violet!50, fill=violet!50] \tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20] \tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20] \tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20] \tikzstyle{comp active minimum} = [comp] \tikzstyle{comp active maximum} = [comp] +\tikzstyle{comp active minimum maximum} = [comp,color=black!20] \tikzstyle{comp inactive minimum} = [comp,color=blue!20] \tikzstyle{comp inactive maximum} = [comp,color=red!20] \tikzstyle{comp inactive minimum maximum} = [comp,color=black!20] @@ -945,31 +947,98 @@ Komparatoren ein. \begin{figure} \begin{center} - \input{images/16-ec-1277186619.tex} + \input{images/16-ec-from-bs32.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 + \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk} + $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.} + \label{fig:16-ec-from-bs32} +\end{figure} + +\begin{figure} + \begin{center} + \input{images/16-ec-from-bs32-normalized.tex} + \end{center} + \caption{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} + \label{fig:16-ec-from-bs32-normalized} \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. +16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den +Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized} +zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$ +und das +${\operatorname{MIN}(0,5,9,11,15,17,20,22,26,29,30)}$-${\operatorname{MAX}(2,4,13,19,24)}$-Schnittmuster, +das durch \textsc{SN-Evolution-Cut} gefunden wurde. +Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk +nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine +Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in +diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des +Netzwerks scheinen rein zufällig zu sein. + +\begin{figure} + % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX + % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX + % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX + % 63:MAX + \begin{center} + \input{images/32-ec-from-bs64.tex} + \end{center} + \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in + 15~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk + $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige + Schnittmuster ist + $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$, + $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37, + 40, 43, 47, 48, 49, 55, 56, 60, 63)$.} + \label{fig:32-ec-from-bs64} +\end{figure} + +Das Ergebnis von \textit{Mühlenthaler} von \textit{Wanka}, die den bitonen +Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk +konstruiert haben, kann demnach auch erreicht werden, wenn +$\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen +Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein +32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden, +wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode +konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den +optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf +208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte +Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller +dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die +Verzögerung dieser Sortiernetzwerke gleich ist. + +Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr +unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für +gute Schnittmuster anzugeben. + +Entscheidend für das Ergebnis eines Schnittmusters scheint beim bitonen +Mergesort-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein. +Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in +Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 +ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten +ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich +die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks +leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und +der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden. + + % 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. +Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur +haben, 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} @@ -998,9 +1067,8 @@ 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. +strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die +Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \begin{displaymath} \textit{Eingang}_i = \left\{ \begin{array}{rl} @@ -1232,9 +1300,31 @@ einen zufälligen Nachfolger. \begin{figure} \begin{center} - \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-12-pct.pdf} \end{center} - \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.} + \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 12~Leitungen), + die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die + \emph{Gamma-Verteilung} $f(x - 40)$ mit $k = 8,267$ und $\theta = 0,962$.} + \label{fig:markov-comparators-12} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-14-pct.pdf} + \end{center} + \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen), + die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die + \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.} + \label{fig:markov-comparators-14} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16-pct.pdf} + \end{center} + \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), + die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die + \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.} \label{fig:markov-comparators-16} \end{figure} @@ -1244,18 +1334,7 @@ einen zufälligen Nachfolger. \todo{In den Abschnitt "`Leitungen entfernen"' einbauen.} -\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 - \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 +Abbildung~\ref{fig:32-ec-from-bs64} zeigt ein 32-Sortiernetzwerk, dass vom \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 diff --git a/references.bib b/references.bib index 30da61b..40c86ba 100644 --- a/references.bib +++ b/references.bib @@ -18,3 +18,13 @@ Publisher = {ACM}, Address = {New York, NY, USA} } + +@article{P1992, + Author = {Ian Parberry}, + Title = {The Pairwise Sorting Network}, + Journal = {Parallel Processing Letters}, + Year = 1992, + Pages = {205--211}, + Volume = 2, + Number = {2,3} +}