From 5d396423e160e7ba2259c409f36a4a6dedefa56e Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Sat, 26 Feb 2011 19:01:05 +0100 Subject: [PATCH] SN-Evolution-Cut: Mehr zu schnellen Netzwerken auf Basis von OES(n). --- diplomarbeit.tex | 75 ++++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 65 insertions(+), 10 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 3e575d5..d910dbb 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -2241,6 +2241,21 @@ Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt. +Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim +\emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die +Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war +jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere +Geschwindigkeit zu erreichen. + +In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von +\textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots +19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles +19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die +resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit +$k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des +\emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in +13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht. + \begin{table} \begin{center} \rowcolors{2}{black!5}{} @@ -2278,17 +2293,57 @@ Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt. \label{tbl:ec-oes-speed} \end{table} +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|r|r|} + \hline + $n$ & Komp. & Schichten \\ + \hline + 20 & 91 & 14 \\ + 21 & 91 & 14 \\ + 22 & 91 & 14 \\ + 23 & 91 & 14 \\ + 24 & 91 & 14 \\ + 25 & 91 & 14 \\ + 26 & 91 & 14 \\ + 27 & 91 & 14 \\ + 28 & 91 & 14 \\ + 29 & 95 & 13 \\ + 30 & 93 & 13 \\ + 31 & 93 & 13 \\ + 32 & 93 & 13 \\ + 33 & 93 & 13 \\ + 34 & 93 & 13 \\ + 35 & 93 & 13 \\ + 36 & 93 & 13 \\ + 37 & 93 & 13 \\ + 38 & 93 & 13 \\ + \hline + \bs{19} & 98 & 14 \\ + \oes{19} & 91 & 14 \\ + \hline + \end{tabular} + \end{center} + \caption{Komparatoren und Schichten von Sortiernetzwerken, die von + \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$ + ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die + Effizienz von 91~Komparatoren nicht mehr erreichbar.} + \label{tbl:ec-oes-19} +\end{table} + In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie -viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke -$\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$ -besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das -\emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen -16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es -wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit -$\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese -Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine -Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes -16-Schnittmuster findet. +viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten +Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und +$\operatorname{PS}(32)$ besitzen. Eines der Ergebnisse war, dass von diesen +Sortiernetzwerken das \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten +unterschiedlichen 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. +Entsprechend ist es wenig verwunderlich, dass \textsc{SN-Evolution-Cut} +gestartet mit $\operatorname{OES}(32)$ sehr schnell\footnote{Ein +entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen +geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe +Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf +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 -- 2.11.0