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}
\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}
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}
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
\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
\label{sect:sn-evolution-cut:bs}
+% Effizienz
+
Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen
Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll,
ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke
benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
+% Beispiel Effizienz
+
\begin{figure}
\begin{center}
\input{images/16-ec-from-bs22.tex}
beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein
Sortiernetzwerk mit 31~Komparatoren gefunden.
-\begin{figure}
- \centering
- \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}}
- \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}}
- \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}}
- \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
- Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}}
- \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
- 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
- erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
- \label{fig:ec-bs-fast_networks}
-\end{figure}
+% Geschwindigkeit
Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.
+% Beispiel Geschwindigkeit
+
+\begin{figure}
+ \centering
+ \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}}
+ \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}}
+ \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}}
+ \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}}
+ \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
+ 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
+ erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
+ \label{fig:ec-bs-fast_networks}
+\end{figure}
+
Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das
Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m}
führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt
reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
noch größer gewählt werden.
+% Detaillierte Betrachtung fuer m = 19
+
Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von
\textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten
werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in
\label{tbl:ec-bs-19}
\end{table}
+% 2-er Potenz
+
\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode
konstruiert wurde, durch systematisches Entfernen von Leitungen in einen
\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}
\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}
23 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & \\
24 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
\hline
+\oes{m}&19& 26 & 31 & 37 & 41 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
+\hline
\end{tabular}
\end{center}
\caption{Anzahl der Komparatoren der Ergebnisse von
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 \\
\label{tbl:ec-oes-19}
\end{table}
+% 2-er Potenzen
+
In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und
derzeitigen Computern.} ein gutes 16-Schnittmuster findet.
Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
-bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
+bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} ist, ist
$\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
\label{fig:16-ec-from-oes32}
\end{figure}
+% Regelmaessiges Schnittmuster fuer n = 2^d
+
Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
-Beobachtung kann man das regelmäßige Schnittmuster
+Beobachtung kann das regelmäßige Schnittmuster
\begin{displaymath}
\textit{Eingang}_i = \left\{ \begin{array}{rl}
\infty & \quad \textrm{falls } i \bmod 4 = 0 \\
? & \quad \mathrm{sonst}
\end{array} \right.
\end{displaymath}
-ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
-Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
-Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
-32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
-ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
+abgeleitet werden. Es entfernt die Hälfte der Leitungen, vorausgesetzt die
+Anzahl der Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt
+effiziente Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine
+Zweierpotenz ist. Ein 32-Sortiernetzwerk, das mit diesem Schnittmuster aus
+\oes{64} erzeugt wurde, ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
\begin{figure}
\begin{center}
\label{fig:32-ec-from-oes64}
\end{figure}
-Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
-erzeugten Sortiernetzwerke die Effizienz des
+Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die durch
+dieses regelmäßige Schnittmuster erzeugten Sortiernetzwerke die Effizienz des
\emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
beider Sortiernetzwerke ist mit 10~Schichten identisch.
-Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
-und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
-verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
-Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
-22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
+% SN-Evolution-Cut vs. regelmaessiges Schnittmuster
+
+Wird der \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{n}, $n = 22, 23, 24$
+und $k = 10, 11, 12$ gestartet, hängt die Ausgabe von der verwendeten
+Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der Algorithmus
+Schnittmuster wie das 12-Schnittmus\-ter $\operatorname{MIN}(6, 7, 8, 9, 16, 17,
+20, 22)$, $\operatorname{MAX}(2, 4, 12, 14)$ für \oes{24}, dessen Ergebnis in
Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
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 resultierende Netzwerk zwar nicht so effizient wie
-\oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
+sehen, weitere Ergebnisse für diese Gütefunktion sind in den
+Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} zusammengefasst.
+Das resultierende 12-Sortiernetzwerk besteht aus 43~Komparatoren, die
+in 9~Schichten 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
\label{fig:12-ec-from-oes24}
\end{figure}
-Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
-findet Sortiernetzwerke, die schneller sind als das entsprechende
-\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit
-22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige
-schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können,
-charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
-\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
-\begin{center}
-\begin{tabular}{|r|r|r|r|r|}
-\hline
-Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
- & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
-\hline
-11 & 38 & 9 & 37 & 10 \\
-12 & 43 & 9 & 41 & 10 \\
-19 & 93 & 13 & 91 & 14 \\
-20 & 101 & 13 & 97 & 14 \\
-21 & 108 & 14 & 107 & 15 \\
-22 & 116 & 14 & 114 & 15 \\
-23 & 125 & 14 & 122 & 15 \\
-\hline
-\end{tabular}
-\end{center}
-Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
-23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
-Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
-Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
-beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
-\bs{23} beziehungsweise \oes{23} eine Schicht einspart.
-
-\begin{figure}
- \begin{center}
- \input{images/23-ec-from-oes46-fast.tex}
- \end{center}
- \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten.
- Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
- Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
- 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
- erzeugt.}
- \label{fig:23-ec-from-oes46}
-\end{figure}
-
\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
projects / diplomarbeit.git / blobdiff