X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=9eb046705336160009182f9d85ee4ec68242911a;hb=db8369a636c6c7d31c4772b09a34ce01aaaae8ea;hp=27be82aa48b66267a423cd9e89dee0b261b2439e;hpb=32ef3b0158d0b4e1f7da64a10ad5110622805ca1;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 27be82a..9eb0467 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1279,8 +1279,9 @@ Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte 16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in Abbildung~\ref{fig:16-voorhis} zu sehen. -Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"' -berücksichtigen kann, hat die folgende allgemeine Form: +\textsc{SN-Evolution} verwendet eine Gütefunktion, die die beiden Ziele +"`effizient"' und "`schnell"' berücksichtigen kann. Sie hat die folgende +generelle Form: \begin{equation} \operatorname{Guete}(S) = w_{\mathrm{Basis}} + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren} @@ -1305,7 +1306,7 @@ verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em -Exploitation}, das Finden (lokaler) Optima, bevorzugt. +Exploitation}, das Streben zu (lokalen) Optima, verstärkt. Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute @@ -1316,10 +1317,25 @@ Leitungszahlen und Mischer-Typen experimentiert werden muss. Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden Werte herausgestellt: \begin{eqnarray*} -w_{\mathrm{Basis}} &=& 0 \\ -w_{\mathrm{Komparatoren}} &=& 1 \\ -w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen} + w_{\mathrm{Basis}} &=& 0 \\ + w_{\mathrm{Komparatoren}} &=& 1 \\ + w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen} \end{eqnarray*} +Sofern nicht anders angegeben, werden diese Werte im Folgenden zur Bewertung +von Sortiernetzwerken verwendet. Die Bewertungsfunktion bevorzugt mit diesen +Konstanten \emph{schnelle} Sortiernetzwerke, da das Einsparen einer Schicht +ein höheres Gewicht als das Einsparen von Komparatoren hat. + +Wenn der \textsc{SN-Evolution}-Algorithmus nach \emph{effizienten} +Sortiernetzwerken suchen soll, werden alternative Werte für die Konstanten der +Bewertungsfunktion verwendet. Die Werte +\begin{eqnarray*} + w_{\mathrm{Basis}} &=& 0 \\ + w_{\mathrm{Komparatoren}} &=& 2 \\ + 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?} \subsection{Selektion} @@ -1402,37 +1418,12 @@ wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet. \subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer} -\begin{figure} - \begin{center} - \input{images/16-e1-bitonic-1296542566.tex} - \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in - 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers} - erzeugt.} - \label{fig:16-e1-bitonic-1296542566} -\end{figure} - Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen -Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in -Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück. - -Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser -Konfiguration gefunden werden, sind effizienter als das \emph{bitone -Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen -Merge}-Netzwerk \bm{n} beruht. Das in -Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk -benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}. - -Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke -bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n} -sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als -\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit -134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von -schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen -Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast} -aufgelistet. +Mischer} verwendet, gibt der Algorithmus \emph{effiziente} und in einigen +Fällen \emph{schnelle} Sortiernetzwerke aus. Die Ergebnisse des +\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers} +sind in Tabelle~\ref{tbl:sn-ev-bm-fast} zusammengefasst. \begin{table}\label{tbl:sn-ev-bm-fast} \begin{center} @@ -1443,23 +1434,23 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l| \cline{2-5} ($n$) & Komp. & Schichten & Komp. & Schichten \\ \hline - 8 & \gcell 20 & 6 & 24 & 6 \\ - 9 & \Gcell 26 & 8 & 28 & 8 \\ - 10 & \gcell 31 & \gcell 8 & 33 & 9 \\ - 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\ - 12 & \gcell 42 & \gcell 9 & 46 & 10 \\ - 13 & \Gcell 48 & 10 & 53 & 10 \\ - 14 & \gcell 54 & 10 & 61 & 10 \\ - 15 & \Gcell 61 & 10 & 70 & 10 \\ - 16 & \gcell 67 & 10 & 80 & 10 \\ - 17 & \Gcell 76 & 12 & 85 & 12 \\ - 18 & \gcell 87 & \gcell 12 & 91 & 13 \\ - 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\ - 20 & \gcell 104 & \gcell 13 & 106 & 14 \\ - 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\ - 22 & \gcell 118 & \gcell 14 & 123 & 15 \\ - 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\ - 24 & \gcell 133 & 15 & 144 & 15 \\ + 8 & \gcell 20 & 6 & 24 & 6 \\ + 9 & \Gcell 26 & 8 & 28 & 8 \\ + 10 & \gcell 31 & \gcell 8 & 33 & 9 \\ + 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\ + 12 & \gcell 42 & \gcell 9 & 46 & 10 \\ + 13 & \Gcell 48 & 10 & 53 & 10 \\ + 14 & \gcell 54 & 10 & 61 & 10 \\ + 15 & \Gcell 61 & 10 & 70 & 10 \\ + 16 & \gcell 67 & 10 & 80 & 10 \\ + 17 & \Gcell 76 & 12 & 85 & 12 \\ + 18 & \gcell 87 & \gcell 12 & 91 & 13 \\ + 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\ + 20 & \gcell 104 & \gcell 13 & 106 & 14 \\ + 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\ + 22 & \gcell 118 & \gcell 14 & 123 & 15 \\ + 23 & \Gcell 129 & \Gcell 14 & 133 & 15 \\ + 24 & \gcell 133 & 15 & 144 & 15 \\ \hline \end{tabular} \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus @@ -1471,19 +1462,89 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l| \end{center} \end{table} -\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} +Alle Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser Konfiguration +gefunden wurden, waren \emph{effizienter} als das \emph{bitone +Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen +Merge}-Netzwerk \bm{n} beruht. Zum Beispiel benötigt das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk +67~Komparatoren, 13~Komparatoren weniger als \bs{n}. \begin{figure} \begin{center} - \input{images/16-e1-oddeven-1296543330.tex} + \input{images/16-e1-bitonic-1296542566.tex} \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers + \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers} erzeugt.} - \label{fig:16-e1-oddeven-1296543330} + \label{fig:16-e1-bitonic-1296542566} +\end{figure} + +Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke +bevorzugt, werden in einigen Fällen Netzwerke zurückgegeben, die +\emph{schneller} und \emph{effizienter} als \bs{n} sind. Das +19-Sortiernetzwerk in Abbildung~\ref{fig:19-e1-bm-fast} besitzt beispielsweise +nur 13~Schichten und benötigt damit einen parallelen Schritt weniger als +\bs{19}. + +\begin{figure} + \begin{center} + \input{images/19-e1-bm-fast.tex} + \end{center} + \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in + 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution} + unter Verwendung des \emph{bitonen Mischers} erzeugt.} + \label{fig:19-e1-bm-fast} \end{figure} +\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} + +Die folgenden Ergebnisse wurden erzielt, indem \textsc{SN-Evolution} mit dem +\emph{Odd-Even-Transpositionsort}-Netzwerk als Eingabe gestartet wurde und in +der Rekombinationsphase das \emph{Odd-Even-Merge}-Netzwerk verwendete. So +erzeugt der Algorithmus entweder Sortiernetzwerke, die genauso schnell und +effizient wie das \oes{n}-Netzwerk, oder Sortiernetzwerke, die schneller aber +weniger effizient als das \oes{n}-Netzwerk sind. Die Ergebnisse von +\textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer sind in +Tabelle~\ref{tbl:sn-ev-oem-fast} zusammengefasst. + +\begin{table}\label{tbl:sn-ev-oem-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\ +\cline{2-5} + & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & 19 & 6 & 19 & 6 \\ + 9 & 26 & 8 & 26 & 8 \\ + 10 & 31 & 9 & 31 & 9 \\ + 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\ + 12 & 43 & \gcell 9 & \gcell 41 & 10 \\ + 13 & 48 & 10 & 48 & 10 \\ + 14 & 53 & 10 & 53 & 10 \\ + 15 & 59 & 10 & 59 & 10 \\ + 16 & 63 & 10 & 63 & 10 \\ + 17 & 74 & 12 & 74 & 12 \\ + 18 & 82 & 13 & 82 & 13 \\ + 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\ + 20 & 97 & 14 & 97 & 14 \\ + 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\ + 22 & 117 & \gcell 14 & \gcell 114 & 15 \\ + 23 & 127 & \Gcell 14 & \Gcell 122 & 15 \\ + 24 & 128 & 15 & \gcell 127 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der + Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} + gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion + nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = + 1$, $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} + Im vorherigen Abschnitt wurde gezeigt, dass der \textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers} Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem @@ -1493,16 +1554,34 @@ erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks findet, erreichen das \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in -Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. +Abbildung~\ref{fig:16-e1-oem-fast} dargestellt. + +\begin{figure} + \begin{center} + \input{images/16-e1-oem-fast.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers + erzeugt.} + \label{fig:16-e1-oem-fast} +\end{figure} Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution} -Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht -beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt -\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen. -\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der -Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet -sich in Tabelle~\ref{tbl:sn-ev-oem-fast}. +Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Beispielsweise +benötigt das 19-Sortiernetzwerk, das in Abbildung~\ref{fig:19-e1-oem-fast} +dargestellt ist, nur 13~Schichten, während \oes{19} 14~Schichten benötigt. + +\begin{figure} + \begin{center} + \input{images/19-e1-oem-fast.tex} + \end{center} + \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in + 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution} + unter Verwendung des \emph{Odd-Even}-Mischers erzeugt.} + \label{fig:19-e1-oem-fast} +\end{figure} %\begin{figure} %\begin{center} @@ -1536,43 +1615,6 @@ sich in Tabelle~\ref{tbl:sn-ev-oem-fast}. %\label{fig:10-e2-1239014566} %\end{figure} -\begin{table}\label{tbl:sn-ev-oem-fast} -\begin{center} -\rowcolors{4}{black!5}{} -\begin{tabular}{|r|r|r|r|r|} -\hline -Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\ -\cline{2-5} - & Komp. & Schichten & Komp. & Schichten \\ -\hline - 8 & 19 & 6 & 19 & 6 \\ - 9 & 26 & 8 & 26 & 8 \\ - 10 & 31 & 9 & 31 & 9 \\ - 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\ - 12 & 43 & \gcell 9 & \gcell 41 & 10 \\ - 13 & 48 & 10 & 48 & 10 \\ - 14 & 53 & 10 & 53 & 10 \\ - 15 & 59 & 10 & 59 & 10 \\ - 16 & 63 & 10 & 63 & 10 \\ - 17 & 74 & 12 & 74 & 12 \\ - 18 & 82 & 13 & 82 & 13 \\ - 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\ - 20 & 97 & 14 & 97 & 14 \\ - 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\ - 22 & 117 & \gcell 14 & \gcell 114 & 15 \\ - 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\ - 24 & 128 & 15 & \gcell 127 & 15 \\ -\hline -\end{tabular} -\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus - unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der - Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} - gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion - nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = - 1$, $w_{\mathrm{Schichten}} = n$.} -\end{center} -\end{table} - \subsection{Zufälliger Mischer} Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige @@ -1584,15 +1626,9 @@ Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur um das beste Ergebnis beider Konstruktionen zu erreichen. \textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem -\emph{Odd-Even}-Mischer wählen. - -Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des -Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast} -zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der -Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem -Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und -20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen -Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz. +\emph{Odd-Even}-Mischer wählen. Die Ergebnisse von \textsc{SN-Evolution} bei +einer zufälligen Wahl des Mischers in der Rekombinationsphase sind in +Tabelle~\ref{tbl:sn-ev-rnd-fast} zusammengefasst. \begin{table}\label{tbl:sn-ev-rnd-fast} \begin{center} @@ -1620,19 +1656,69 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\ 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\ 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\ - 23 & 134 & 14 & 129 & 14 & \Gcell 128 & 14 \\ + 23 & 129 & 14 & \Gcell 127 & 14 & 128 & 14 \\ 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\ \hline \end{tabular} \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus - unter Verwendung der verschiedenen Mischer. Der Algorithmus wurde mit dem + unter Verwendung der beiden Mischer-Netzwerke. Der Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten - $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$, + $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$.} \end{center} \end{table} +Bei einigen Leitungszahlen kann der Algorithmus durch die Verfügbarkeit beider +Mi\-scher-Netzwerke Sortiernetzwerke zurückgeben, die effizienter als die +vorherigen Ergebnisse sind. Beispielsweise ist das 19-Sortiernetzwerk in +Abbildung~\ref{fig:19-e1-rnd-fast} mit 92~Komparatoren effizienter als die +19-Sortiernetzwerke, die mit nur einem der beiden Mischer-Netzwerke erreicht +wurden (Abbildungen~\ref{fig:19-e1-bm-fast} und~\ref{fig:19-e1-oem-fast}). + +\begin{figure} + \begin{center} + \input{images/19-e1-rnd-fast.tex} + \end{center} + \caption{Sortiernetzwerk mit 19~Leitungen und 92~Komparatoren in + 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution} + unter Verwendung des \emph{bitonen Mischers} und des + \emph{Odd-Even}-Mischers erzeugt.} + \label{fig:19-e1-rnd-fast} +\end{figure} + +Die Ergebnisse anderer Leitungszahlen erreichen die Geschwindigkeit der +Ergebnisse, die mit dem \emph{bitonen Mischer} erzielt wurden. Die Effizienz +liegt zwischen den Ergebnissen, die mit dem \emph{bitonen Mischer} erzielt +wurden, und den Ergebnissen, die mit dem \emph{Odd-Even}-Mischer erzielt +wurden. Beispielsweise ist das 18-Sortiernetzwerk in +Abbildung~\ref{fig:18-e1-rnd-fast} so schnell wie das Ergebnis, das mit dem +\emph{bitonen Mischer} ausgegeben wurde. Mit 83~Komparatoren liegt die +Effizienz des Sortiernetzwerks zwischen den Ergebnissen, die mit dem +\emph{bitonen Mischer} (87~Komparatoren), beziehungsweise dem +\emph{Odd-Even}-Mischer (82~Komparatoren) erreicht werden konnten. + +\begin{figure} + \begin{center} + \input{images/18-e1-rnd-fast.tex} + \end{center} + \caption{Sortiernetzwerk mit 18~Leitungen und 83~Komparatoren in + 12~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution} + unter Verwendung des \emph{bitonen Mischers} und des + \emph{Odd-Even}-Mischers erzeugt.} + \label{fig:18-e1-rnd-fast} +\end{figure} + +In einigen Fällen hat \textsc{SN-Evolution} in dieser Konfiguration +Sortiernetzwerke ausgegeben, die weniger effizient und genauso schnell wie die +bisherigen Ergebnisse unter Verwendung des \emph{Odd-Even}-Mischers sind. +Prinzipiell könnte der Algorithmus in jeder Iteration zufällig den +\emph{Odd-Even}-Mischers auswählen, um die selektierten Individuen zu +rekombinieren. Das heißt, das die Ergebnisse auch bei einer zufälligen Wahl +des Mischer-Netzwerks theoretisch erreicht werden können. Allerdings sind +unter Umständen mehr Iterationen notwendig, bis die gleiche Effizienz erreicht +wird. + %\input{shmoo-aequivalenz.tex} \newpage @@ -2088,10 +2174,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} @@ -2100,9 +2188,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} @@ -2216,6 +2305,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 @@ -2320,14 +2411,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 \\ @@ -2342,6 +2442,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 @@ -2356,7 +2458,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 @@ -2386,9 +2488,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 \\ @@ -2396,11 +2500,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} @@ -2412,18 +2516,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 @@ -2431,9 +2537,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 @@ -2450,48 +2558,6 @@ 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