X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=2a8eff5c4372438982b6e898e423b9cd5b36c6f0;hb=1e600fc1cfba4d57ab551f630fbbd355a5e600d9;hp=70a7c42ade5af5f96d328c58a68429ef1927e7f9;hpb=da8bbbc5dc446a98cced33ddae4a1cc5f47a35ca;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 70a7c42..2a8eff5 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -2134,7 +2134,7 @@ Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen. 35 & 93 & 13 \\ \rowcolor{green!10} 36 & 92 & 13 \\ - \rowcolor{green!10!white!95!black} + \rowcolor{green!10!white!95!black} 37 & 92 & 13 \\ 38 & 93 & 13 \\ \hline @@ -2572,8 +2572,26 @@ effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}. \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk} +Eine weitere interessante Eingabe für \textsc{SN-Evolution-Cut} ist das +\emph{Pairwise-Sorting}-Netzwerk \ps{n}, das \textit{Ian +Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992} +definiert. Einerseits wurde in Abschnitt~\ref{sect:anzahl_schnittmuster} +gezeigt, dass es für \ps{n} sehr viele \emph{unterschiedliche} Schnittmuster +gibt. Andererseits sind die Sortiernetzwerke, die nach \textit{Parberrys} +Methode erzeugt werden, genauso schnell und effizient wie das +\emph{Odd-Even-Mergesort}-Netzwerk, wenn die Leitungszahl $n = 2^d$ eine +Zweierpotenz ist. + % Effizienz +Für viele Kombinationen von \ps{n} und $k$ sind die Sortiernetzwerke, die +\textsc{SN-Evolution-Cut} ausgibt, weniger effizient als das entsprechende +\ps{m}-Netzwerk. Für einige Kombinationen werden jedoch auch effizientere +Netzwerke generiert, beispielsweise für $m = 11$ und $m = 20$. Die Effizienz +der Sortiernetzwerke, die \textsc{SN-Evolution-Cut} auf Basis des +\emph{Pairwise-Sorting}-Netzwerks berechnet, ist tabellarisch in +Tabelle~\ref{tbl:ec-ps-efficiency} dargestellt. + \begin{table} \begin{center} \rowcolors{2}{black!5}{} @@ -2613,6 +2631,14 @@ effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}. % Beispiel Effizienz +Zwei Ergebnisse, die effizienter als die entsprechenden +\emph{Pairwise-Sorting}-Netzwerke sind, zeigt +Abbildung~\ref{fig:ec-ps-efficient_networks}. Sie erreichen die +Geschwindigkeit und Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks mit der +entsprechenden Leitungszahl. Bei größeren Netzwerken, beispielsweise $m = 19$, +ist dies mit der in Tabelle~\ref{tbl:ec-ps-efficiency} dargestellten Größe der +Schnittmuster noch nicht zu beobachten. + \begin{figure} \centering \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das @@ -2629,8 +2655,87 @@ effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}. \label{fig:ec-ps-efficient_networks} \end{figure} +% Wie viele Schnitte man braucht. + +Bei welchen Parametern \textsc{SN-Evolution-Cut} effiziente +19-Sortiernetzwerke findet, ist Tabelle~\ref{tbl:ec-ps-19} zu entnehmen. Für +$n = 31$, $k = 12$ und $n = 32$, $k = 13$ werden 19-Sortiernetzwerke mit der +selben Effizienz und Geschwindigkeit wie \oes{19} erzeugt. Das +19-Sortiernetzwerk, das auf diese Art und Weise aus \ps{32} erzeugt wurde, ist +in Abbildung~\ref{fig:19-ec-from-ps32} dargestellt. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|r|r|} + \hline + $n$ & Komp. & Schichten \\ + \hline + 20 & 97 & 15 \\ + 21 & 96 & 15 \\ + 22 & 96 & 15 \\ + 23 & 97 & 14 \\ + 24 & 96 & 14 \\ + 25 & 93 & 14 \\ + 26 & 92 & 14 \\ + 27 & 94 & 14 \\ + 28 & 94 & 14 \\ + 29 & 92 & 14 \\ + 30 & 92 & 14 \\ + \rowcolor{green!10!white!95!black} + 31 & 91 & 14 \\ + \rowcolor{green!10} + 32 & 91 & 14 \\ + 33 & 101 & 15 \\ + 34 & 104 & 15 \\ + 35 & 106 & 15 \\ + 36 & 107 & 15 \\ + 37 & 106 & 15 \\ + 38 & 102 & 15 \\ + \hline + \ps{19} & 97 & 15 \\ + \oes{19} & 91 & 14 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die + von \textsc{SN-Evolution-Cut} aus \ps{n}, $n = 20, \dots, 38$ erzeugt + wurden.} + \label{tbl:ec-ps-19} +\end{table} + +\begin{figure} + \begin{center} + \input{images/19-ec-from-ps32.tex} + \end{center} + \caption{Sortiernetzwerk mit 19~Leitungen und 91~Komparatoren in + 14~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk + $\operatorname{PS}(32)$ erzeugt.} + \label{fig:19-ec-from-ps32} +\end{figure} + +An den Daten in Tabelle~\ref{tbl:ec-ps-19} fällt auf, dass die Effizienz und +Geschwindigkeit der Ergebnisse für $n > 32$ schlechter werden. Das +\emph{Pairwise-Sorting}-Netzwerk ist Leitungszahlen, die Zweierpotenzen sind, +besonders effizient und schnell. Um der Vermutung nachzugehen, dass der +\textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente +Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1 +\dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32} +zusammengefasst. \todo{Tabelle einfügen.} + % Geschwindigkeit +Die Schnittmuster, die \textsc{SN-Evolution-Cut} für das +\emph{Pairwise-Sorting}-Netzwerk berechnet, können zu schnelleren +Sortiernetzwerken als \ps{m} führen. Beispielsweise konnte aus \ps{24} ein +18-Sortiernetzwerk erzeugt werden, das mit 13~Schichten zwei parallele +Schritte im Vergleich zu \ps{18} einspart. Eine Darstellung dieses +Sortiernetzwerks befindet sich in Abbildung~\ref{fig:18-ec-from-ps24}. Für +andere $m$ wurde die Geschwindigkeit des \emph{Pairwise-Sorting}-Netzwerks +nicht übertroffen und im Fall von $m = 16$ wurde die Geschwindigkeit nicht +einmal erreicht. + \begin{table} \begin{center} \rowcolors{2}{black!5}{} @@ -2689,13 +2794,12 @@ Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war 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 -$\operatorname{PS}(32)$ und der Vorgabe, 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. +Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet +man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe, +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. \begin{figure} \begin{center} @@ -2708,7 +2812,7 @@ Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt. \label{fig:16-ec-from-ps32} \end{figure} -Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht +Obwohl das \emph{Pairwise-Sorting}-Netzwerk den \emph{Odd-Even}-Mischer nicht einsetzt und auch nicht auf einem Mischer basiert, ist das \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In