\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
\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
-Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
-Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
-(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
-ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
-wie und warum es jede beliebige Eingabe sortiert.
+% Effizienz
\begin{table}
\begin{center}
Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
Ausgabenetzwerks.}
+ \label{tbl:ec-ps-efficiency}
+\end{table}
+
+% Beispiel Effizienz
+
+\begin{figure}
+ \centering
+ \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Pairwise-Sorting}-Netzwerk \ps{13}
+ erzeugt.]{\input{images/11-ec-from-ps13.tex}}
+ \subfigure[12-Sortiernetzwerk aus 41~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
+ \emph{Pairwise-Sorting}-Netzwerk \ps{16}
+ erzeugt.]{\input{images/12-ec-from-ps16.tex}}
+ \caption{Zwei effiziente Sortiernetzwerke, die durch Schnittmuster, die von
+ \emph{SN-Evolution-Cut} berechnet wurden, aus dem
+ \emph{Pairwise-Sorting}-Netzwerk \ps{n} erzeugt wurden.}
+ \label{fig:ec-ps-efficient_networks}
+\end{figure}
+
+% Geschwindigkeit
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
+ \hline
+ & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
+ \hline
+ 9 & 6 & & & & & & & & & & & & & & & \\
+ 10 & 6 & 10 & & & & & & & & & & & & & & \\
+ 11 & 6 & 9 & 10 & & & & & & & & & & & & & \\
+ 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
+ 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
+ 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
+ 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
+ 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
+ 17 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & & & & & & & \\
+ 18 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & & & & & & \\
+ 19 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & & & & & \\
+ 20 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & 15 & & & & \\
+ 21 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 15 & 15 & 15 & & & \\
+ 22 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 14 & 15 & 15 & 15 & & \\
+ 23 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 14 & 14 & 15 & 15 & 15 & \\
+ 24 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 13 & 14 & 14 & 15 & 15 & 15 \\
+ \hline
+ \ps{m} & 6 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 15 & 15 & 15 & 15 & 15 & 15 & 15 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Schichten der Ergebnisse von
+ \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
+ \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
+ Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
+ Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
+ Ausgabenetzwerks.}
\label{tbl:ec-ps-speed}
\end{table}
+% Beispiel Geschwindigkeit
+
+\begin{figure}
+ \begin{center}
+ \input{images/18-ec-from-ps24.tex}
+ \end{center}
+ \caption{Sortiernetzwerk mit 18~Leitungen und 89~Komparatoren in
+ 13~Schichten. Das Netzwerk wurde von dem Algorithmus
+ \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
+ $\operatorname{PS}(24)$ erzeugt.}
+ \label{fig:18-ec-from-ps24}
+\end{figure}
+
+% 2-er Potenz
+
+Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
+Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
+(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
+ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
+wie und warum es jede beliebige Eingabe sortiert.
+
Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
projects / diplomarbeit.git / blobdiff