X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=3caa170557f2e21f2d11f7aea6fda6a5738cb500;hb=3c907c76f314340cd13c88eec32a2ab8f3ed961c;hp=9277debfa64f3dbd88b30ee58c84ca7201e56f39;hpb=4bc4bfe96ff1e1edfdaa0930abd1fb6561906f4b;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 9277deb..3caa170 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -2041,18 +2041,29 @@ Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen. \end{table} \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, -wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde, -durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen -Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer -sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert -werden, Komparatoren ein. - -Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein -Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer -konstruiert wurde. Dieses Sortiernetzwerk be\-nö\-tigt 68~Komparatoren, -12~weniger als das \emph{bitone Mergesort}-Netzwerk nach Batchers Methode. -Gegenüber Batchers Methode sparen so konstruierte Sortiernetzwerke -${\frac{1}{4}n(\log n - 1)}$ Komparatoren ein. +wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode +konstruiert wurde, durch systematisches Entfernen von Leitungen in einen +ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert werden +kann, so dass dieser alternative Mischer im Vergleich zu $\bm{\frac{n}{2} = +2^{d-1}}$ Komparatoren einspart. + +Basierend auf diesen alternativen Mischern geben \textit{Mühlenthaler} und +\textit{Wanka} eine Konstruktionsvorschrift für Sortiernetzwerke an, die +gegenüber \bs{n} ${\frac{1}{4}n(\log n - 1)}$ Komparatoren einspart. +Beispielsweise wird ein 16-Sortiernetzwerk angegeben, das nur 68~Komparatoren +benötigt. Dieses Netzwerk ist in Abbildung~\ref{fig:16-muehlenthaler} +dargestellt. + +\begin{figure} + \begin{center} + \input{images/16-muehlenthaler.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in + 10~Schichten. Das Netzwerk wurde 2010 von \textit{Mühlenthaler} und + \textit{Wanka} aus optimierten bitonen Mischern konstruiert und + in~\cite{MW2010} veröffentlicht.} + \label{fig:16-muehlenthaler} +\end{figure} \begin{figure} \begin{center} @@ -2086,10 +2097,10 @@ und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26, 29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, 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. +nachdem das Schnittmuster angewendet 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 @@ -2110,50 +2121,24 @@ Netzwerks scheinen rein zufällig zu sein. \label{fig:32-ec-from-bs64} \end{figure} -Das Ergebnis von \textit{Mühlenthaler} und \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 -Geschwindigkeit dieser Sortiernetzwerke gleich ist. - -\begin{center} -\begin{tabular}{|r|r|r|r|r|} -\hline -Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\ - & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} & - \bs{n} \\ -\hline -11 & 37 & 9 & 39 & 10 \\ -12 & 42 & 9 & 46 & 10 \\ -19 & 93 & 13 & 98 & 14 \\ -20 & 102 & 13 & 106 & 14 \\ -% 20: # sn-cut 2:MAX 3:MIN 4:MIN 9:MIN 10:MIN 13:MIN 14:MIN 15:MIN 19:MIN 20:MAX 24:MAX 26:MIN 27:MAX 29:MIN 31:MAX 33:MIN 34:MAX 35:MIN 37:MIN 39:MAX -21 & 109 & 14 & 114 & 15 \\ -22 & 116 & 14 & 123 & 15 \\ -23 & 124 & 14 & 133 & 15 \\ -\hline -\end{tabular} -\end{center} - -\begin{figure} - \begin{center} - \input{images/23-ec-from-bs46-fast.tex} - \end{center} - \caption{23-Sortiernetzwerk mit 124~Komparatoren in 14~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{46} mit dem - Schnittmuster $\operatorname{MIN}(2, 4, 9, 12, 20, 22, 28, 30, 32, 33, 37, - 38, 41)$, $\operatorname{MAX}(1, 5, 16, 19, 21, 24, 25, 35, 36, 43)$ - erzeugt.} - \label{fig:23-ec-from-bs46} -\end{figure} +Wenn \textsc{SN-Evolution-Cut} mit dem \bs{64}-Netzwerk und $k = 32$ gestartet +wird, findet der Algorithmus 32-Sortiernetzwerke, die effizienter sind als +32-Sortiernetzwerke, die nach \textit{Mühlenthalers} und \textit{Wankas} +Methode konstruiert werden. Ein von \textsc{SN-Evolution-Cut} aus \bs{64} +generiertes 32-Sortiernetzwerk ist in Abbildung~\ref{fig:32-ec-from-bs64} +dargestellt. Das \emph{bitone Mergesort}-Netzwerk \bs{32} benötigt +240~Komparatoren, ein aus den optimierten Mischern aufgebautes Netzwerk +verbessert die Effizienz auf 208~Komparatoren. Das Ergebnis von +\textsc{SN-Evolution-Cut} kommt mit nur 206~Komparatoren aus. Die +Geschwindigkeit aller genannten Sortiernetzwerke ist mit 15 parallelen +Schritten identisch. + +Wenn die Leitungszahl des Eingabenetzwerks keine Zweierpotenz ist, kann +\textsc{SN-Evo\-lu\-tion-Cut} auch 16-Sortiernetzwerke erzeugen, die diese +Effizienz unterbieten. Das geht aus den Daten in +Tabelle~\ref{tbl:ec-bs-efficiency} hervor. Ein 16-Sortiernetzwerk mit +67~Komparatoren, das von \textsc{SN-Evolution-Cut} generiert wurde, ist in +Abbildung~\ref{fig:16-ec-from-bs22} dargestellt. Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für @@ -2169,10 +2154,11 @@ die Schnittmuster aufgrund der Symmetrie des \emph{bitonen Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung -- mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig. -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 +Dass die Sortiernetzwerke, die mit den Schnittmustern von +\textsc{SN-Evolution-Cut} entstehen, 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 $k$~Schnitten gestartet, so ist das beste Ergebnis immer das $\operatorname{OET}(n-k)$-Netzwerk. @@ -2311,9 +2297,7 @@ Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu -\bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das -Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46}) -effizienter, da es nur 124~Komparatoren benötigt. +\bs{23} beziehungsweise \oes{23} eine Schicht einspart. \begin{figure} \begin{center}