\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}
\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
\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
\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}
%\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
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}
projects / diplomarbeit.git / blobdiff