SN-Evolution-Cut: OES: Kleine Verbesserungen.

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index 6809fff..9eb0467 100644 (file)
--- 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