From db8369a636c6c7d31c4772b09a34ce01aaaae8ea Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Mon, 28 Feb 2011 08:46:09 +0100 Subject: [PATCH] SN-Evolution-Cut: OES: Kleine Verbesserungen. --- diplomarbeit.tex | 44 +++++++++++++++++++++++++++----------------- 1 file changed, 27 insertions(+), 17 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 6809fff..9eb0467 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -2305,6 +2305,8 @@ tabellarisch. 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 @@ -2440,6 +2442,8 @@ $k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des \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 @@ -2454,7 +2458,7 @@ 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 +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 @@ -2484,9 +2488,11 @@ Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen. \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 \\ @@ -2494,11 +2500,11 @@ Beobachtung kann man das regelmäßige Schnittmuster ? & \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} @@ -2510,18 +2516,20 @@ ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen. \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 @@ -2529,9 +2537,11 @@ gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt, 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 -- 2.11.0