\emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
Diese Anzahl ist insbesondere beim automatisierten Bewerten von
-Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
+Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:sn-evolution:bewertung}
beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
-in Abschnitt~\ref{sect:bewertung} behandelt.
+in Abschnitt~\ref{sect:sn-evolution:bewertung} behandelt. Informationen zur Implementierung
+von \textsc{SN-Evolution} befinden sich in
+Abschnitt~\ref{sect:implementierung}.
-\subsection{Bewertungsfunktion}\label{sect:bewertung}
+\subsection{Bewertungsfunktion}\label{sect:sn-evolution:bewertung}
Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
{\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
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}
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
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}
\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-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}
%\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}
Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
-von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:sn-evolution:bewertung}.
Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
projects / diplomarbeit.git / blobdiff