X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=a58d6290856aac254e20d6b8ce3a269fae18d2c1;hb=204f0ead4d1ccbd87c678cf8c35a4c781781d594;hp=201dd9c5086c119625f548b4efe2fe8fed684b71;hpb=e7b60fe22bd5d51fefe5ec8b3223d241413907d6;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 201dd9c..a58d629 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -280,13 +280,13 @@ Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus -mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im +mehrere Stunden beschäftigen. Das ist deshalb problematisch, weil die im Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines -Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million -Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung -auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden -für einen Lauf benötigt. +Zwischenergebnisses drei Stunden in Anspruch nimmt, sind für eine Million +Iterationen etwa 340~Jahre Rechenzeit notwendig. Selbst wenn die Berechnung +auf 1000~Computern mit je 4~Prozessoren verteilt wird, wird etwa ein Monat für +einen Lauf benötigt. \subsubsection{Evolutionäre Algorithmen} @@ -426,9 +426,7 @@ zusammenfügen). Da der Begriff des "`mischens"' beziehungsweise der "`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale -Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt. - -\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.} +Eingabe. Im Folgenden werden daher drei Konstruktionsverfahren vorgestellt. \subsection{Das Odd-Even-Transpositionsort-Netzwerk} \label{sect:odd_even_transpositionsort} @@ -848,23 +846,14 @@ Batcher} zeigt in~\cite{B1968}, dass in diesem Fall \end{displaymath} gilt. -% gnuplot: -% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0)) -% oem1(n) = oem(ceil(.5*n),floor(.5*n)) -% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n) - -%\begin{itemize} -%\item Pairwise sorting-network -%\end{itemize} - -\subsection{Das Pairwise-Sorting-Netzwerk} - -Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift -für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The -Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der -Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das -\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie -das \emph{Odd-Even-Mergesort}-Netzwerk. +%\subsection{Das Pairwise-Sorting-Netzwerk} +% +%Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift +%für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The +%Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der +%Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das +%\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie +%das \emph{Odd-Even-Mergesort}-Netzwerk. \newpage \section{Transformation von Sortiernetzwerken} @@ -1266,8 +1255,12 @@ die bei Sortiernetzwerken verfolgt werden können: \begin{figure} \centering - \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}} - \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}} + \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das + Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in~\cite{G1972} + veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}} + \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textit{D. Van~Voorhis} 1974 in~\cite{V1974} + veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}} \caption{Das effizienteste und das schnellste Sortiernetzwerk für 16~Leitungen, das derzeit bekannt ist.} \label{fig:16-best-known} @@ -1335,7 +1328,7 @@ Bewertungsfunktion verwendet. Die Werte w_{\mathrm{Schichten}} &=& 1 \end{eqnarray*} geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen -einer Schicht. \todo{Fehler hier noch was?} +einer Schicht. \subsection{Selektion} @@ -1930,6 +1923,8 @@ $k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk} \label{sect:sn-evolution-cut:bs} +% Effizienz + Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll, ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke @@ -1939,6 +1934,8 @@ Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16} benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen. +% Beispiel Effizienz + \begin{figure} \begin{center} \input{images/16-ec-from-bs22.tex} @@ -2014,21 +2011,7 @@ Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke, beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein Sortiernetzwerk mit 31~Komparatoren gefunden. -\begin{figure} - \centering - \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}} - \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}} - \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}} - \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}} - \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11, - 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke - erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.} - \label{fig:ec-bs-fast_networks} -\end{figure} +% Geschwindigkeit Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der \textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als @@ -2080,6 +2063,24 @@ schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke, die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt. +% Beispiel Geschwindigkeit + +\begin{figure} + \centering + \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}} + \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}} + \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}} + \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}} + \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11, + 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke + erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.} + \label{fig:ec-bs-fast_networks} +\end{figure} + Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m} führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt @@ -2089,6 +2090,8 @@ einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise noch größer gewählt werden. +% Detaillierte Betrachtung fuer m = 19 + Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in @@ -2124,7 +2127,7 @@ Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen. 35 & 93 & 13 \\ \rowcolor{green!10} 36 & 92 & 13 \\ - \rowcolor{green!10!white!95!black} + \rowcolor{green!10!white!95!black} 37 & 92 & 13 \\ 38 & 93 & 13 \\ \hline @@ -2145,6 +2148,8 @@ Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen. \label{tbl:ec-bs-19} \end{table} +% 2-er Potenz + \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode konstruiert wurde, durch systematisches Entfernen von Leitungen in einen @@ -2174,10 +2179,12 @@ dargestellt. \begin{center} \input{images/16-ec-from-bs32.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 \emph{bitonen Mergesort-Netzwerk} - $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.} + \caption{Visualisierung eines 16-Schnittmusters, das von + \textsc{SN-Evolution-Cut} für das \emph{bitone Mergesort}-Netzwerk \bs{32} + berechnet wurde. Das resultierende Sortiernetzwerk besteht aus + 68~Komparatoren in 10~Schichten und ist in + Abbildung~\ref{fig:16-ec-from-bs32-normalized} als + Standard-Sortiernetzwerk dargestellt.} \label{fig:16-ec-from-bs32} \end{figure} @@ -2186,9 +2193,10 @@ dargestellt. \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.} + 10~Schichten. Das Netzwerk wurde mit einem 16-Schnittmuster, das von + \textsc{SN-Evolution-Cut} berechnet wurde, aus dem \emph{bitone + Mergesort}-Netzwerk \bs{32} erzeugt. Das Schnittmuster ist in + Abbildung~\ref{fig:16-ec-from-bs32} dargestellt.} \label{fig:16-ec-from-bs32-normalized} \end{figure} @@ -2302,6 +2310,8 @@ tabellarisch. 23 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & \\ 24 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\ \hline +\oes{m}&19& 26 & 31 & 37 & 41 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\ +\hline \end{tabular} \end{center} \caption{Anzahl der Komparatoren der Ergebnisse von @@ -2406,14 +2416,23 @@ $k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des 27 & 91 & 14 \\ 28 & 91 & 14 \\ 29 & 95 & 13 \\ + \rowcolor{green!10} 30 & 93 & 13 \\ + \rowcolor{green!10!white!95!black} 31 & 93 & 13 \\ + \rowcolor{green!10} 32 & 93 & 13 \\ + \rowcolor{green!10!white!95!black} 33 & 93 & 13 \\ + \rowcolor{green!10} 34 & 93 & 13 \\ + \rowcolor{green!10!white!95!black} 35 & 93 & 13 \\ + \rowcolor{green!10} 36 & 93 & 13 \\ + \rowcolor{green!10!white!95!black} 37 & 93 & 13 \\ + \rowcolor{green!10} 38 & 93 & 13 \\ \hline \bs{19} & 98 & 14 \\ @@ -2428,6 +2447,8 @@ $k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des \label{tbl:ec-oes-19} \end{table} +% 2-er Potenzen + In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und @@ -2442,7 +2463,7 @@ Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf derzeitigen Computern.} ein gutes 16-Schnittmuster findet. Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das -bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist +bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} ist, ist $\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7, 8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende @@ -2472,9 +2493,11 @@ Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen. \label{fig:16-ec-from-oes32} \end{figure} +% Regelmaessiges Schnittmuster fuer n = 2^d + Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3, 4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser -Beobachtung kann man das regelmäßige Schnittmuster +Beobachtung kann das regelmäßige Schnittmuster \begin{displaymath} \textit{Eingang}_i = \left\{ \begin{array}{rl} \infty & \quad \textrm{falls } i \bmod 4 = 0 \\ @@ -2482,11 +2505,11 @@ Beobachtung kann man das regelmäßige Schnittmuster ? & \quad \mathrm{sonst} \end{array} \right. \end{displaymath} -ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der -Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente -Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein -32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde, -ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen. +abgeleitet werden. Es entfernt die Hälfte der Leitungen, vorausgesetzt die +Anzahl der Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt +effiziente Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine +Zweierpotenz ist. Ein 32-Sortiernetzwerk, das mit diesem Schnittmuster aus +\oes{64} erzeugt wurde, ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen. \begin{figure} \begin{center} @@ -2498,18 +2521,20 @@ ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen. \label{fig:32-ec-from-oes64} \end{figure} -Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so -erzeugten Sortiernetzwerke die Effizienz des +Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die durch +dieses regelmäßige Schnittmuster erzeugten Sortiernetzwerke die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit 43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit beider Sortiernetzwerke ist mit 10~Schichten identisch. -Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24} -und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der -verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der -Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20, -22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in +% SN-Evolution-Cut vs. regelmaessiges Schnittmuster + +Wird der \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{n}, $n = 22, 23, 24$ +und $k = 10, 11, 12$ gestartet, hängt die Ausgabe von der verwendeten +Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der Algorithmus +Schnittmuster wie das 12-Schnittmus\-ter $\operatorname{MIN}(6, 7, 8, 9, 16, 17, +20, 22)$, $\operatorname{MAX}(2, 4, 12, 14)$ für \oes{24}, dessen Ergebnis in Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit @@ -2517,9 +2542,11 @@ gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt, werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15, 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu -sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten -angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie -\oes{12}, dafür aber schneller als \oes{12} und \bs{12}. +sehen, weitere Ergebnisse für diese Gütefunktion sind in den +Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} zusammengefasst. +Das resultierende 12-Sortiernetzwerk besteht aus 43~Komparatoren, die +in 9~Schichten angeordnet sind. Das resultierende Netzwerk zwar nicht so +effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}. \begin{figure} \centering @@ -2536,55 +2563,27 @@ angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie \label{fig:12-ec-from-oes24} \end{figure} -Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut} -findet Sortiernetzwerke, die schneller sind als das entsprechende -\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit -22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige -schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können, -charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das -\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl. -\begin{center} -\begin{tabular}{|r|r|r|r|r|} -\hline -Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\ - & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\ -\hline -11 & 38 & 9 & 37 & 10 \\ -12 & 43 & 9 & 41 & 10 \\ -19 & 93 & 13 & 91 & 14 \\ -20 & 101 & 13 & 97 & 14 \\ -21 & 108 & 14 & 107 & 15 \\ -22 & 116 & 14 & 114 & 15 \\ -23 & 125 & 14 & 122 & 15 \\ -\hline -\end{tabular} -\end{center} -Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein -23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem -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. - -\begin{figure} - \begin{center} - \input{images/23-ec-from-oes46-fast.tex} - \end{center} - \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten. - Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem - Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38, - 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$ - erzeugt.} - \label{fig:23-ec-from-oes46} -\end{figure} - \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk} -Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene -Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war -(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise -ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich, -wie und warum es jede beliebige Eingabe sortiert. +Eine weitere interessante Eingabe für \textsc{SN-Evolution-Cut} ist das +\emph{Pairwise-Sorting}-Netzwerk \ps{n}, das \textit{Ian +Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} +definiert. Einerseits wurde in Abschnitt~\ref{sect:anzahl_schnittmuster} +gezeigt, dass es für \ps{n} sehr viele \emph{unterschiedliche} Schnittmuster +gibt. Andererseits sind die Sortiernetzwerke, die nach \textit{Parberrys} +Methode erzeugt werden, genauso schnell und effizient wie das +\emph{Odd-Even-Mergesort}-Netzwerk, wenn die Leitungszahl $n = 2^d$ eine +Zweierpotenz ist. + +% Effizienz + +Für viele Kombinationen von \ps{n} und $k$ sind die Sortiernetzwerke, die +\textsc{SN-Evolution-Cut} ausgibt, weniger effizient als das entsprechende +\ps{m}-Netzwerk. Für einige Kombinationen werden jedoch auch effizientere +Netzwerke generiert, beispielsweise für $m = 11$ und $m = 20$. Die Effizienz +der Sortiernetzwerke, die \textsc{SN-Evolution-Cut} auf Basis des +\emph{Pairwise-Sorting}-Netzwerks berechnet, ist tabellarisch in +Tabelle~\ref{tbl:ec-ps-efficiency} dargestellt. \begin{table} \begin{center} @@ -2620,16 +2619,214 @@ wie und warum es jede beliebige Eingabe sortiert. Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.} + \label{tbl:ec-ps-efficiency} +\end{table} + +% Beispiel Effizienz + +Zwei Ergebnisse, die effizienter als die entsprechenden +\emph{Pairwise-Sorting}-Netzwerke sind, zeigt +Abbildung~\ref{fig:ec-ps-efficient_networks}. Sie erreichen die +Geschwindigkeit und Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks mit der +entsprechenden Leitungszahl. Bei größeren Netzwerken, beispielsweise $m = 19$, +ist dies mit der in Tabelle~\ref{tbl:ec-ps-efficiency} dargestellten Größe der +Schnittmuster noch nicht zu beobachten. + +\begin{figure} + \centering + \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem + \emph{Pairwise-Sorting}-Netzwerk \ps{13} + erzeugt.]{\input{images/11-ec-from-ps13.tex}} + \subfigure[12-Sortiernetzwerk aus 41~Komparatoren in 10~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem + \emph{Pairwise-Sorting}-Netzwerk \ps{16} + erzeugt.]{\input{images/12-ec-from-ps16.tex}} + \caption{Zwei effiziente Sortiernetzwerke, die durch Schnittmuster, die von + \emph{SN-Evolution-Cut} berechnet wurden, aus dem + \emph{Pairwise-Sorting}-Netzwerk \ps{n} erzeugt wurden.} + \label{fig:ec-ps-efficient_networks} +\end{figure} + +% Wie viele Schnitte man braucht. + +Bei welchen Parametern \textsc{SN-Evolution-Cut} effiziente +19-Sortiernetzwerke findet, ist Tabelle~\ref{tbl:ec-ps-19} zu entnehmen. Für +$n = 31$, $k = 12$ und $n = 32$, $k = 13$ werden 19-Sortiernetzwerke mit der +selben Effizienz und Geschwindigkeit wie \oes{19} erzeugt. Das +19-Sortiernetzwerk, das auf diese Art und Weise aus \ps{32} erzeugt wurde, ist +in Abbildung~\ref{fig:19-ec-from-ps32} dargestellt. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|r|r|} + \hline + $n$ & Komp. & Schichten \\ + \hline + 20 & 97 & 15 \\ + 21 & 96 & 15 \\ + 22 & 96 & 15 \\ + 23 & 97 & 14 \\ + 24 & 96 & 14 \\ + 25 & 93 & 14 \\ + 26 & 92 & 14 \\ + 27 & 94 & 14 \\ + 28 & 94 & 14 \\ + 29 & 92 & 14 \\ + 30 & 92 & 14 \\ + \rowcolor{green!10!white!95!black} + 31 & 91 & 14 \\ + \rowcolor{green!10} + 32 & 91 & 14 \\ + 33 & 101 & 15 \\ + 34 & 104 & 15 \\ + 35 & 106 & 15 \\ + 36 & 107 & 15 \\ + 37 & 106 & 15 \\ + 38 & 102 & 15 \\ + \hline + \ps{19} & 97 & 15 \\ + \oes{19} & 91 & 14 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die + von \textsc{SN-Evolution-Cut} aus \ps{n}, $n = 20, \dots, 38$ erzeugt + wurden.} + \label{tbl:ec-ps-19} +\end{table} + +\begin{figure} + \begin{center} + \input{images/19-ec-from-ps32.tex} + \end{center} + \caption{Sortiernetzwerk mit 19~Leitungen und 91~Komparatoren in + 14~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk + $\operatorname{PS}(32)$ erzeugt.} + \label{fig:19-ec-from-ps32} +\end{figure} + +An den Daten in Tabelle~\ref{tbl:ec-ps-19} fällt auf, dass die Effizienz und +Geschwindigkeit der Ergebnisse für $n > 32$ schlechter werden. Das +\emph{Pairwise-Sorting}-Netzwerk ist Leitungszahlen, die Zweierpotenzen sind, +besonders effizient und schnell. Um der Vermutung nachzugehen, dass der +\textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente +Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1 +\dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32} +zusammengefasst. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|r|r|} + \hline + $m$ & Komp. & Schichten \\ + \hline + 16 & 69 & 11 \\ + 17 & 77 & 13 \\ + 18 & 89 & 13 \\ + 19 & 91 & 14 \\ + 20 & 97 & 14 \\ + 21 & 107 & 15 \\ + 22 & 114 & 15 \\ + 23 & 122 & 15 \\ + 24 & 127 & 15 \\ + 25 & 138 & 15 \\ + 26 & 146 & 15 \\ + 27 & 155 & 15 \\ + 28 & 161 & 15 \\ + 29 & 171 & 15 \\ + 30 & 178 & 15 \\ + 31 & 186 & 15 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren und Schichten von $m$-Sortiernetzwerken, + die von \textsc{SN-Evolution-Cut} nach 5.000.000 Iterationen aus \ps{32} + erzeugt wurden.} + \label{tbl:ec-ps-32} +\end{table} + +% Geschwindigkeit + +Die Schnittmuster, die \textsc{SN-Evolution-Cut} für das +\emph{Pairwise-Sorting}-Netzwerk berechnet, können zu schnelleren +Sortiernetzwerken als \ps{m} führen. Beispielsweise konnte aus \ps{24} ein +18-Sortiernetzwerk erzeugt werden, das mit 13~Schichten zwei parallele +Schritte im Vergleich zu \ps{18} einspart. Eine Darstellung dieses +Sortiernetzwerks befindet sich in Abbildung~\ref{fig:18-ec-from-ps24}. Für +andere $m$ wurde die Geschwindigkeit des \emph{Pairwise-Sorting}-Netzwerks +nicht übertroffen und im Fall von $m = 16$ wurde die Geschwindigkeit nicht +einmal erreicht. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|rrrrrrrrrrrrrrrr|} + \hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ + \hline + 9 & 6 & & & & & & & & & & & & & & & \\ + 10 & 6 & 10 & & & & & & & & & & & & & & \\ + 11 & 6 & 9 & 10 & & & & & & & & & & & & & \\ + 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\ + 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\ + 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\ + 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\ + 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\ + 17 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & & & & & & & \\ + 18 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & & & & & & \\ + 19 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & & & & & \\ + 20 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & 15 & & & & \\ + 21 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 15 & 15 & 15 & & & \\ + 22 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 14 & 15 & 15 & 15 & & \\ + 23 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 14 & 14 & 15 & 15 & 15 & \\ + 24 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 13 & 14 & 14 & 15 & 15 & 15 \\ + \hline + \ps{m} & 6 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 15 & 15 & 15 & 15 & 15 & 15 & 15 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Schichten der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} \label{tbl:ec-ps-speed} \end{table} -Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian -Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} -definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit -$\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man -ein Sortiernetzwerk, das die gleiche Anzahl Komparatoren und Schichten hat wie -$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser +% Beispiel Geschwindigkeit + +\begin{figure} + \begin{center} + \input{images/18-ec-from-ps24.tex} + \end{center} + \caption{Sortiernetzwerk mit 18~Leitungen und 89~Komparatoren in + 13~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk + $\operatorname{PS}(24)$ erzeugt.} + \label{fig:18-ec-from-ps24} +\end{figure} + +% 2-er Potenz + +Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene +Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war +(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise +ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich, +wie und warum es jede beliebige Eingabe sortiert. + +Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet +man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe, +16~Leitungen zu entfernen, kann der Algorithmus ein Sortiernetzwerk +zurückgeben, das die gleiche Anzahl Komparatoren und Schichten wie +$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$ hat. Eines dieser Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. +Dieses Ergebnis demonstriert, dass sich die Ergebnisse in den gezeigten +Tabellen oft durch zusätzliche Iterationen verbessern lassen. \begin{figure} \begin{center} @@ -2642,7 +2839,7 @@ Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. \label{fig:16-ec-from-ps32} \end{figure} -Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht +Obwohl das \emph{Pairwise-Sorting}-Netzwerk den \emph{Odd-Even}-Mischer nicht einsetzt und auch nicht auf einem Mischer basiert, ist das \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In @@ -2692,13 +2889,14 @@ Netzwerk in schwarz gut zu erkennen. \label{fig:16-pairwise} \end{figure} -Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf -$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein -8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für -größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise -kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} -konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} -untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. +Ein Spezialfall ergibt sich, wenn \textsc{SN-Evolution-Cut} auf +$\operatorname{PS}(16)$ angewendet wird: In diesem Fall kann ein +8-Schnittmuster ausgegeben werden, das \emph{Odd-Even-Mergesort}-Netzwerk +\oes{8} aus \ps{16} erzeugt.. Für größere Sortiernetzwerke ist dies hingegen +nicht mehr möglich, beispielsweise kann $\operatorname{PS}(32)$ nicht durch +ein 16-Schnittmuster in \oes{16} konvertiert werden. Die Verwandtschaft von +$\operatorname{PS}(n)$ und \oes{n} untersucht \textit{Moritz Mühlenthaler} +ausführlich in~\cite{M2009}. \newpage \section{Fazit und Ausblick}