X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=blobdiff_plain;f=diplomarbeit.tex;h=eb0255234802ee87da18311994b3504262bbbb3c;hp=d5c84bc5fbac15d9f0fb4b439af3aef6e4716034;hb=3028e656c71a13d67a5114094f1a36ef0ba23c5a;hpb=c63d86b41a8f1d63bdad0dfdc79d3bdf4d790dfd diff --git a/diplomarbeit.tex b/diplomarbeit.tex index d5c84bc..eb02552 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1418,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} @@ -1459,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 @@ -1487,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 & 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} + 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 @@ -1509,16 +1554,26 @@ 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-oddeven-1296543330} dargestellt. + +\begin{figure} + \begin{center} + \input{images/16-e1-oddeven-1296543330.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-oddeven-1296543330} +\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}. +\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schichten benötigen. +\oes{11} und \oes{12} benötigen jeweils 10~Schichten. + %\begin{figure} %\begin{center} @@ -1552,43 +1607,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 @@ -1636,7 +1654,7 @@ 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 & 129 & 14 & \Gcell 128 & 14 \\ 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\ \hline \end{tabular}