X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=98dd41ec91e6ef9373246da181adc4deb26df8f4;hb=36e6060c43037ba34eb96b809e6a0349fa545cf1;hp=6cd40785ebfa38f7dd1031d40839d8cbc2222b37;hpb=8fc2876c1eb49652c1e1a897b4cd4617fae96094;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 6cd4078..98dd41e 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -9,6 +9,7 @@ \usepackage{listings} \usepackage{graphicx} \usepackage{url} +\usepackage[table]{xcolor} %\usepackage{longtable} \usepackage{subfigure} \usepackage{icomma} @@ -43,6 +44,9 @@ \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}} \newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}} +\newcommand{\gcell}{\cellcolor{green!10}} +\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}} + \newtheorem{definition}{Definition} \newtheorem{satz}{Satz} @@ -1158,10 +1162,10 @@ die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster vernachlässigbar klein ist. Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses -Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar. -Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen -Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich -für „kleine“ x-Werte verlässt. +Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die +Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern +vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für +„kleine“ x-Werte verlässt. Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können, kann man sich einer stochastischen Methode bedienen, der sogenannten @@ -1283,8 +1287,8 @@ Exploitation}, das Finden (lokaler) Optima, bevorzugt. Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute -Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es -kein Patentrezept für die Wahl der Parameter, so dass für verschiedene +Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt +es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene Leitungszahlen und Mischer-Typen experimentiert werden muss. Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden @@ -1330,12 +1334,12 @@ Pseudocode wie folgt beschreiben: \label{sect:sn-evolution:rekombination} Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu -einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel -den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den -\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die -beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen. -Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in -Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt. +einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu +einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em +bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der +\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), +Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie +in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt. Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das @@ -1380,15 +1384,63 @@ wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet. \label{fig:16-e1-bitonic-1296542566} \end{figure} -Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von -\textsc{SN-Evolution}, so erhält man Netzwerke wie das in -Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus -wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale -Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist -als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren, -das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt -lediglich~67. Die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks wurde -leider mit keiner Leitungszahl erreicht. +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. + +\begin{table}\label{tbl:sn-ev-bm-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\ +\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 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{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[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} @@ -1403,17 +1455,25 @@ leider mit keiner Leitungszahl erreicht. \label{fig:16-e1-oddeven-1296543330} \end{figure} -Leider lies sich das Ergebnis des bitonen Mischers -- die von -\textsc{SN-Evolution} ausgegebenen Netzwerke waren effizienter als das -rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem -\emph{Odd-Even-Merge}-Netzwerk nicht wiederholen. Zwar erreichen die -Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des -\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk -bezüglich Geschwindigkeit und Effizienz, ein Beispiel hierfür ist in -Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Sortiernetzwerkde, die -effizienter als $\operatorname{OES}(n)$ sind, konnten leider nicht beobachtet -werden. Wenn $n$ keine Zweietpotenz ist, kann \textsc{SN-Evolution} unter -Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind. +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 +\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind. +Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht +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. + +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}. %\begin{figure} %\begin{center} @@ -1447,6 +1507,43 @@ Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind. %\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} + %\input{shmoo-aequivalenz.tex} \newpage @@ -1573,9 +1670,9 @@ Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich -die Schnittmuster aufgrund der Symmetrie des bitonen Mergesort-Netzwerks -leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und -der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden. +die Schnittmuster aufgrund der Symmetrie des \emph{bitonen +Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung -- +mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig. \begin{figure} \centering @@ -1642,7 +1739,7 @@ Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} definiert. Startet man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe, -16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, dass die gleiche +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 Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. @@ -1677,7 +1774,7 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \end{figure} Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach -regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen kleineres +regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das einfache Schnittmuster \begin{displaymath} @@ -1805,8 +1902,8 @@ 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 heißt, dass das resultierende Netzwerk zwar nicht so -effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12} ist. +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