X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=5130f0ca61eec1b258a283c59d406fa85f80b82c;hb=cddd0282fa78e5b560e46c230f4ee80ed75d21f3;hp=eb0255234802ee87da18311994b3504262bbbb3c;hpb=3028e656c71a13d67a5114094f1a36ef0ba23c5a;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index eb02552..5130f0c 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1532,7 +1532,7 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l 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 \\ + 23 & 127 & \Gcell 14 & \Gcell 122 & 15 \\ 24 & 128 & 15 & \gcell 127 & 15 \\ \hline \end{tabular} @@ -1554,26 +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} dargestellt. +Abbildung~\ref{fig:16-e1-oem-fast} dargestellt. \begin{figure} \begin{center} - \input{images/16-e1-oddeven-1296543330.tex} + \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-oddeven-1296543330} + \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~Schichten benötigen. -\oes{11} und \oes{12} benötigen jeweils 10~Schichten. +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} @@ -1618,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} @@ -1654,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 & 129 & 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 @@ -2122,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} @@ -2134,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} @@ -2354,14 +2409,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 \\