From: Florian Forster Date: Sat, 26 Feb 2011 15:03:21 +0000 (+0100) Subject: SN-Evolution-Cut: Versucht mit dem bitonen Mergesort-Netzwerk prinzipiell fertig. X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=commitdiff_plain;h=3c907c76f314340cd13c88eec32a2ab8f3ed961c SN-Evolution-Cut: Versucht mit dem bitonen Mergesort-Netzwerk prinzipiell fertig. --- 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} diff --git a/images/16-muehlenthaler.tex b/images/16-muehlenthaler.tex new file mode 100644 index 0000000..1f69051 --- /dev/null +++ b/images/16-muehlenthaler.tex @@ -0,0 +1,290 @@ +\begin{tikzpicture}[auto] +\node[vertex] (v0) at (0.95,0.00) {}; +\node[vertex] (v1) at (0.95,0.76) {}; +\path[comp] (v0) -- (v1); + +\node[vertex] (v2) at (0.95,1.52) {}; +\node[vertex] (v3) at (0.95,2.28) {}; +\path[comp] (v2) -- (v3); + +\node[vertex] (v4) at (0.95,3.04) {}; +\node[vertex] (v5) at (0.95,3.80) {}; +\path[comp] (v4) -- (v5); + +\node[vertex] (v6) at (0.95,4.56) {}; +\node[vertex] (v7) at (0.95,5.32) {}; +\path[comp] (v6) -- (v7); + +\node[vertex] (v8) at (0.95,6.08) {}; +\node[vertex] (v9) at (0.95,6.84) {}; +\path[comp] (v8) -- (v9); + +\node[vertex] (v10) at (0.95,7.59) {}; +\node[vertex] (v11) at (0.95,8.35) {}; +\path[comp] (v10) -- (v11); + +\node[vertex] (v12) at (0.95,9.11) {}; +\node[vertex] (v13) at (0.95,9.87) {}; +\path[comp] (v12) -- (v13); + +\node[vertex] (v14) at (0.95,10.63) {}; +\node[vertex] (v15) at (0.95,11.39) {}; +\path[comp] (v14) -- (v15); + +\node[vertex] (v16) at (1.90,0.00) {}; +\node[vertex] (v17) at (1.90,1.52) {}; +\path[comp] (v16) -- (v17); + +\node[vertex] (v18) at (2.18,0.76) {}; +\node[vertex] (v19) at (2.18,2.28) {}; +\path[comp] (v18) -- (v19); + +\node[vertex] (v20) at (1.90,3.04) {}; +\node[vertex] (v21) at (1.90,4.56) {}; +\path[comp] (v20) -- (v21); + +\node[vertex] (v22) at (2.18,3.80) {}; +\node[vertex] (v23) at (2.18,5.32) {}; +\path[comp] (v22) -- (v23); + +\node[vertex] (v24) at (1.90,6.08) {}; +\node[vertex] (v25) at (1.90,7.59) {}; +\path[comp] (v24) -- (v25); + +\node[vertex] (v26) at (2.18,6.84) {}; +\node[vertex] (v27) at (2.18,8.35) {}; +\path[comp] (v26) -- (v27); + +\node[vertex] (v28) at (1.90,9.11) {}; +\node[vertex] (v29) at (1.90,10.63) {}; +\path[comp] (v28) -- (v29); + +\node[vertex] (v30) at (2.18,9.87) {}; +\node[vertex] (v31) at (2.18,11.39) {}; +\path[comp] (v30) -- (v31); + +\node[vertex] (v32) at (3.13,0.76) {}; +\node[vertex] (v33) at (3.13,1.52) {}; +\path[comp] (v32) -- (v33); + +\node[vertex] (v34) at (3.13,3.80) {}; +\node[vertex] (v35) at (3.13,4.56) {}; +\path[comp] (v34) -- (v35); + +\node[vertex] (v36) at (3.13,6.84) {}; +\node[vertex] (v37) at (3.13,7.59) {}; +\path[comp] (v36) -- (v37); + +\node[vertex] (v38) at (3.13,9.87) {}; +\node[vertex] (v39) at (3.13,10.63) {}; +\path[comp] (v38) -- (v39); + +\node[vertex] (v40) at (4.08,0.00) {}; +\node[vertex] (v41) at (4.08,3.80) {}; +\path[comp] (v40) -- (v41); + +\node[vertex] (v42) at (4.37,0.76) {}; +\node[vertex] (v43) at (4.37,3.04) {}; +\path[comp] (v42) -- (v43); + +\node[vertex] (v44) at (4.65,1.52) {}; +\node[vertex] (v45) at (4.65,5.32) {}; +\path[comp] (v44) -- (v45); + +\node[vertex] (v46) at (4.94,2.28) {}; +\node[vertex] (v47) at (4.94,4.56) {}; +\path[comp] (v46) -- (v47); + +\node[vertex] (v48) at (4.08,6.08) {}; +\node[vertex] (v49) at (4.08,9.87) {}; +\path[comp] (v48) -- (v49); + +\node[vertex] (v50) at (4.37,6.84) {}; +\node[vertex] (v51) at (4.37,9.11) {}; +\path[comp] (v50) -- (v51); + +\node[vertex] (v52) at (4.65,7.59) {}; +\node[vertex] (v53) at (4.65,11.39) {}; +\path[comp] (v52) -- (v53); + +\node[vertex] (v54) at (4.94,8.35) {}; +\node[vertex] (v55) at (4.94,10.63) {}; +\path[comp] (v54) -- (v55); + +\node[vertex] (v56) at (5.89,1.52) {}; +\node[vertex] (v57) at (5.89,3.80) {}; +\path[comp] (v56) -- (v57); + +\node[vertex] (v58) at (6.17,2.28) {}; +\node[vertex] (v59) at (6.17,3.04) {}; +\path[comp] (v58) -- (v59); + +\node[vertex] (v60) at (5.89,7.59) {}; +\node[vertex] (v61) at (5.89,9.87) {}; +\path[comp] (v60) -- (v61); + +\node[vertex] (v62) at (6.17,8.35) {}; +\node[vertex] (v63) at (6.17,9.11) {}; +\path[comp] (v62) -- (v63); + +\node[vertex] (v64) at (7.12,0.00) {}; +\node[vertex] (v65) at (7.12,0.76) {}; +\path[comp] (v64) -- (v65); + +\node[vertex] (v66) at (7.12,1.52) {}; +\node[vertex] (v67) at (7.12,2.28) {}; +\path[comp] (v66) -- (v67); + +\node[vertex] (v68) at (7.12,3.04) {}; +\node[vertex] (v69) at (7.12,3.80) {}; +\path[comp] (v68) -- (v69); + +\node[vertex] (v70) at (7.12,4.56) {}; +\node[vertex] (v71) at (7.12,5.32) {}; +\path[comp] (v70) -- (v71); + +\node[vertex] (v72) at (7.12,6.08) {}; +\node[vertex] (v73) at (7.12,6.84) {}; +\path[comp] (v72) -- (v73); + +\node[vertex] (v74) at (7.12,7.59) {}; +\node[vertex] (v75) at (7.12,8.35) {}; +\path[comp] (v74) -- (v75); + +\node[vertex] (v76) at (7.12,9.11) {}; +\node[vertex] (v77) at (7.12,9.87) {}; +\path[comp] (v76) -- (v77); + +\node[vertex] (v78) at (7.12,10.63) {}; +\node[vertex] (v79) at (7.12,11.39) {}; +\path[comp] (v78) -- (v79); + +\node[vertex] (v80) at (8.07,0.00) {}; +\node[vertex] (v81) at (8.07,8.35) {}; +\path[comp] (v80) -- (v81); + +\node[vertex] (v82) at (8.35,0.76) {}; +\node[vertex] (v83) at (8.35,7.59) {}; +\path[comp] (v82) -- (v83); + +\node[vertex] (v84) at (8.64,1.52) {}; +\node[vertex] (v85) at (8.64,6.84) {}; +\path[comp] (v84) -- (v85); + +\node[vertex] (v86) at (8.92,2.28) {}; +\node[vertex] (v87) at (8.92,6.08) {}; +\path[comp] (v86) -- (v87); + +\node[vertex] (v88) at (9.21,3.04) {}; +\node[vertex] (v89) at (9.21,11.39) {}; +\path[comp] (v88) -- (v89); + +\node[vertex] (v90) at (9.49,3.80) {}; +\node[vertex] (v91) at (9.49,10.63) {}; +\path[comp] (v90) -- (v91); + +\node[vertex] (v92) at (9.78,4.56) {}; +\node[vertex] (v93) at (9.78,9.87) {}; +\path[comp] (v92) -- (v93); + +\node[vertex] (v94) at (10.06,5.32) {}; +\node[vertex] (v95) at (10.06,9.11) {}; +\path[comp] (v94) -- (v95); + +\node[vertex] (v96) at (11.01,3.04) {}; +\node[vertex] (v97) at (11.01,8.35) {}; +\path[comp] (v96) -- (v97); + +\node[vertex] (v98) at (11.30,3.80) {}; +\node[vertex] (v99) at (11.30,7.59) {}; +\path[comp] (v98) -- (v99); + +\node[vertex] (v100) at (11.58,4.56) {}; +\node[vertex] (v101) at (11.58,6.84) {}; +\path[comp] (v100) -- (v101); + +\node[vertex] (v102) at (11.87,5.32) {}; +\node[vertex] (v103) at (11.87,6.08) {}; +\path[comp] (v102) -- (v103); + +\node[vertex] (v104) at (12.82,0.00) {}; +\node[vertex] (v105) at (12.82,1.52) {}; +\path[comp] (v104) -- (v105); + +\node[vertex] (v106) at (13.10,0.76) {}; +\node[vertex] (v107) at (13.10,2.28) {}; +\path[comp] (v106) -- (v107); + +\node[vertex] (v108) at (12.82,3.04) {}; +\node[vertex] (v109) at (12.82,4.56) {}; +\path[comp] (v108) -- (v109); + +\node[vertex] (v110) at (13.10,3.80) {}; +\node[vertex] (v111) at (13.10,5.32) {}; +\path[comp] (v110) -- (v111); + +\node[vertex] (v112) at (12.82,6.08) {}; +\node[vertex] (v113) at (12.82,7.59) {}; +\path[comp] (v112) -- (v113); + +\node[vertex] (v114) at (13.10,6.84) {}; +\node[vertex] (v115) at (13.10,8.35) {}; +\path[comp] (v114) -- (v115); + +\node[vertex] (v116) at (12.82,9.11) {}; +\node[vertex] (v117) at (12.82,10.63) {}; +\path[comp] (v116) -- (v117); + +\node[vertex] (v118) at (13.10,9.87) {}; +\node[vertex] (v119) at (13.10,11.39) {}; +\path[comp] (v118) -- (v119); + +\node[vertex] (v120) at (14.05,0.00) {}; +\node[vertex] (v121) at (14.05,0.76) {}; +\path[comp] (v120) -- (v121); + +\node[vertex] (v122) at (14.05,1.52) {}; +\node[vertex] (v123) at (14.05,2.28) {}; +\path[comp] (v122) -- (v123); + +\node[vertex] (v124) at (14.05,3.04) {}; +\node[vertex] (v125) at (14.05,3.80) {}; +\path[comp] (v124) -- (v125); + +\node[vertex] (v126) at (14.05,4.56) {}; +\node[vertex] (v127) at (14.05,5.32) {}; +\path[comp] (v126) -- (v127); + +\node[vertex] (v128) at (14.05,6.08) {}; +\node[vertex] (v129) at (14.05,6.84) {}; +\path[comp] (v128) -- (v129); + +\node[vertex] (v130) at (14.05,7.59) {}; +\node[vertex] (v131) at (14.05,8.35) {}; +\path[comp] (v130) -- (v131); + +\node[vertex] (v132) at (14.05,9.11) {}; +\node[vertex] (v133) at (14.05,9.87) {}; +\path[comp] (v132) -- (v133); + +\node[vertex] (v134) at (14.05,10.63) {}; +\node[vertex] (v135) at (14.05,11.39) {}; +\path[comp] (v134) -- (v135); + +\path[edge] (0,0.00) -- (15.00,0.00); +\path[edge] (0,0.76) -- (15.00,0.76); +\path[edge] (0,1.52) -- (15.00,1.52); +\path[edge] (0,2.28) -- (15.00,2.28); +\path[edge] (0,3.04) -- (15.00,3.04); +\path[edge] (0,3.80) -- (15.00,3.80); +\path[edge] (0,4.56) -- (15.00,4.56); +\path[edge] (0,5.32) -- (15.00,5.32); +\path[edge] (0,6.08) -- (15.00,6.08); +\path[edge] (0,6.84) -- (15.00,6.84); +\path[edge] (0,7.59) -- (15.00,7.59); +\path[edge] (0,8.35) -- (15.00,8.35); +\path[edge] (0,9.11) -- (15.00,9.11); +\path[edge] (0,9.87) -- (15.00,9.87); +\path[edge] (0,10.63) -- (15.00,10.63); +\path[edge] (0,11.39) -- (15.00,11.39); +\end{tikzpicture}