erhält man ein {\em Komparatornetzwerk}.
\begin{figure}
-\begin{center}
-\input{images/einfaches_komparatornetzwerk.tex}
-\end{center}
-\caption{Einfaches Komparatornetzwerk mit vier Ein- beziehungsweise Ausgängen, bestehend
-aus 5~Komparatoren.}
-\label{fig:einfaches_komparatornetzwerk}
+ \begin{center}
+ \input{images/einfaches_komparatornetzwerk.tex}
+ \end{center}
+ \caption{Einfaches Komparatornetzwerk mit 4~Ein- beziehungsweise Ausgängen,
+ bestehend aus 5~Komparatoren.}
+ \label{fig:einfaches_komparatornetzwerk}
\end{figure}
Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
\begin{center}
\input{images/09-e2-c24-allbut1.tex}
\end{center}
- \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
- 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
- alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
+ \caption{Ein \emph{Komparatornetzwerk} mit 9~Eingängen und 24~Komparatoren,
+ die in 8~Schichten angeordnet sind. Das Netzwerk sortiert alle Eingaben, bei
+ denen das Minimum nicht auf dem mittleren Eingang liegt.}
\label{fig:09-e2-c24-allbut1}
\end{figure}
Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
-über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
-Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
+so schnell, dass ein Ausprobieren aller möglichen Permutationen schon bei
+16~Leitungen praktisch nicht mehr zu bewerkstelligen
ist.\footnote{1.307.674.368.000 Permutationen}
\label{sect:0-1-prinzip}
Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
-zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$
-oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei
-gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich
-der Komparator so verhält, wie er sich bei der Permutation verhalten hat --
-ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$
-und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im
-Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.
-
-Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
-Komplexitätsklasse
-$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
-ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$
-verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
-schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
-ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
-sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
-aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
-eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
-4,3~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
-beschäftigen.
+zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als
+$a_i$, beziehungsweise zwei Zahlen größer oder gleich $a_i$. Da im Fall der
+0-1-Folge zwei gleiche Zahlen am Komparator anliegen, dürfen wir davon
+ausgehen, dass sich der Komparator so verhält, wie er sich bei der Permutation
+verhalten hat -- ohne das Ergebnis zu beeinflussen. Entsprechend müssen an den
+Ausgängen $i-1$ und $i$ eine Null und eine Eins in der falschen Reihenfolge
+ankommen. Das steht im Widerspruch zu der Annahme, dass alle 0-1-Folgen
+sortiert werden.
+
+Im Gegensatz zum Überprüfen aller möglichen Permutationen, was mit dem Aufwand
+$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ verbunden ist, besitzt
+das Überprüfen aller 0-1-Folgen „nur“ den Aufwand $\Theta(2^n)$. Entsprechend
+ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist
+bisher allerdings nicht bekannt.
+
+Um zu überprüfen, ob ein Komparatornetzwerk mit 16~Leitungen die
+Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig
+-- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt.
+Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch
+bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus
+mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
+Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
+Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
+Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
+Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
+für einen Lauf benötigt.
\subsubsection{Evolutionäre Algorithmen}
Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
-$\mathcal{NP}$. Das heißt, dass keine Verfahren bekannt sind, die diese
-Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese Probleme
-außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine Konsequenz,
-dass es effiziente exakte Algorithmen für diese Probleme nicht gibt. Falls
-sich hingegen herausstellt, dass diese Probleme neben $\mathcal{NP}$ auch in
-der Komplexitätsklasse~\textit{P} liegen, gibt es effiziente Algorithmen. Es
-ist jedoch wahrscheinlich, dass die Zeitkonstanten solcher Algorithmen sehr
-groß sein würden, so dass der praktische Nutzen fraglich bleibt.
-
-Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
-die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen
-Lösungen}, als einzige Ausgabe des Algorithmus zuzulassen, wird eine
-"`möglichst gute"' Lösung ausgegeben. Viele dieser Optimierungsalgorithmen
-orientieren sich an Vorgängen in der Natur. Beispielsweise imitieren die
-„Ameisenalgorithmen“ das Verhalten von Ameisen auf der Futtersuche, um kurze
-Rundreisen auf Graphen zu berechnen.
+$\mathcal{NP}$-vollständig. Das heißt, dass keine Verfahren bekannt sind, die
+diese Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese
+Probleme außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine
+Konsequenz, dass es für diese Probleme keine effizienten exakten Algorithmen
+gibt. Stellt sich hingegen heraus, dass diese Probleme neben
+$\mathcal{NP}$-vollständig auch in der Komplexitätsklasse~\textit{P} liegen,
+gibt es effiziente Algorithmen. Es ist jedoch wahrscheinlich, dass die
+Zeitkonstanten solcher Algorithmen sehr groß wären, so dass der praktische
+Nutzen fraglich bleibt.
+
+Aus diesem Grund besteht die Notwendigkeit, einen Kompromiss einzugehen: Statt
+die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen Lösungen}
+als einzige Ausgabe des Algorithmus zuzulassen, wird eine "`möglichst gute"'
+Lösung ausgegeben. Dafür verringert sich die Laufzeit des Algorithmus. Viele
+dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur.
+Beispielsweise imitieren die „Ameisenalgorithmen“ das Verhalten von Ameisen
+auf der Futtersuche, um kurze Rundreisen auf Graphen zu berechnen.
Bei {\em Evolutionären Algorithmen} stand die Evolution Pate. Die Grundidee
ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
-% \todo{Drei oder vier Verfahren?}
+\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.}
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
verleiht dem Sortiernetzwerk seinen Namen.
Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
-Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
+Instanzen des Netzwerks, deren Leitungszahl $n = 2^d$ eine Zweierpotenz ist.
Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
\subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.
-Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
+Für den wichtigen Spezialfall, dass $n = m = 2^{d-1}$ beträgt, lässt sich die
Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
erste Rekursionsschritt der OEM-Konstruktion fügt
$\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
\end{displaymath}
Komparatoren eingespart. Damit ergibt sich
\begin{displaymath}
- K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
+ K\left(n = 2^{d-1}, n = 2^{d-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
\end{displaymath}
-für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
+für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^d)$
benötigt werden.
\subsubsection{Das Odd-Even-Mergesort-Netzwerk}
ist allerdings bekannt, dass $k(n)$ in $\Theta\left(n \left(\log
(n)\right)^2\right)$ enthalten ist.
-Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
+Für den wichtigen Spezialfall, dass $n = 2^d$ eine Zweierpotenz ist, kann die
Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
\begin{displaymath}
- k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
+ k(n = 2^d) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
\end{displaymath}
gilt.
\emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
Diese Anzahl ist insbesondere beim automatisierten Bewerten von
-Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
+Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:sn-evolution:bewertung}
beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“
Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk.
Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt
-beispielsweise 26~Komparatoren, die in neun Schichten angeordnet sind. Es sind
-allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich
-25~Komparatoren in sieben Schichten benötigen. Kombiniert man zwei dieser
-Netzwerke mit dem \emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit
-18~Eingängen, das 80~Komparatoren in 11~Schichten benötigt.
-$\operatorname{OES}(18)$ benötigt 82~Komparatoren in 13~Schichten. Damit ist
-das resultierende Netzwerk genauso schnell wie das Sortiernetzwerk mit
-18~Eingängen, das \textit{Sherenaz~W. Al-Haj Baddar} und \textit{Kenneth~E.
-Batcher} in ihrer Arbeit „An 11-Step Sorting Network for
-18~Elements“~\cite{BB2009} vorstellen, benötigt aber 6~Komparatoren weniger.
+beispielsweise 26~Komparatoren, die in 9~Schichten angeordnet sind. Es sind
+allerdings Sortiernetzwerke mit 9~Eingängen bekannt, die lediglich
+25~Komparatoren in 7~Schichten benötigen. Wenn zwei dieser Netzwerke mit dem
+\emph{Odd-Even}-Mischer kombiniert werden, entsteht ein 18-Sortiernetzwerk,
+das aus 80~Komparatoren in 11~Schichten besteht. Damit ist das resultierende
+Netzwerk genauso schnell wie das Sortiernetzwerk mit 18~Eingängen, das
+\textit{Sherenaz~W. Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer
+Arbeit „An 11-Step Sorting Network for 18~Elements“~\cite{BB2009} vorstellen,
+benötigt aber 6~Komparatoren weniger. $\operatorname{OES}(18)$ benötigt
+82~Komparatoren in 13~Schichten.
Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
(Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
(Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
-in Abschnitt~\ref{sect:bewertung} behandelt.
+in Abschnitt~\ref{sect:sn-evolution:bewertung} behandelt. Informationen zur Implementierung
+von \textsc{SN-Evolution} befinden sich in
+Abschnitt~\ref{sect:implementierung}.
-\subsection{Bewertungsfunktion}\label{sect:bewertung}
+\subsection{Bewertungsfunktion}\label{sect:sn-evolution:bewertung}
Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
{\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
Abbildung~\ref{fig:16-voorhis} zu sehen.
-Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
-berücksichtigen kann, hat die folgende allgemeine Form:
+\textsc{SN-Evolution} verwendet eine Gütefunktion, die die beiden Ziele
+"`effizient"' und "`schnell"' berücksichtigen kann. Sie hat die folgende
+generelle Form:
\begin{equation}
\operatorname{Guete}(S) = w_{\mathrm{Basis}}
+ w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
-Exploitation}, das Finden (lokaler) Optima, bevorzugt.
+Exploitation}, das Streben zu (lokalen) Optima, verstärkt.
Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
Werte herausgestellt:
\begin{eqnarray*}
-w_{\mathrm{Basis}} &=& 0 \\
-w_{\mathrm{Komparatoren}} &=& 1 \\
-w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
+ w_{\mathrm{Basis}} &=& 0 \\
+ w_{\mathrm{Komparatoren}} &=& 1 \\
+ w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
\end{eqnarray*}
+Sofern nicht anders angegeben, werden diese Werte im Folgenden zur Bewertung
+von Sortiernetzwerken verwendet. Die Bewertungsfunktion bevorzugt mit diesen
+Konstanten \emph{schnelle} Sortiernetzwerke, da das Einsparen einer Schicht
+ein höheres Gewicht als das Einsparen von Komparatoren hat.
+
+Wenn der \textsc{SN-Evolution}-Algorithmus nach \emph{effizienten}
+Sortiernetzwerken suchen soll, werden alternative Werte für die Konstanten der
+Bewertungsfunktion verwendet. Die Werte
+\begin{eqnarray*}
+ w_{\mathrm{Basis}} &=& 0 \\
+ w_{\mathrm{Komparatoren}} &=& 2 \\
+ w_{\mathrm{Schichten}} &=& 1
+\end{eqnarray*}
+geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
+einer Schicht. \todo{Fehler hier noch was?}
\subsection{Selektion}
Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
-von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:sn-evolution:bewertung}.
Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
-Tabelle~\ref{tbl:ec-bs-speed} sind die Schichten, die die Ergebnisse von
-\textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren, aufgelistet.
-Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n}, jede Spalte
-enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die Zellen
-enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
+Tabelle~\ref{tbl:ec-bs-speed} ist die Anzahl der Schichten, die die Ergebnisse
+von \textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren,
+aufgelistet. Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n},
+jede Spalte enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die
+Zellen enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
\begin{table}
\begin{center}
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}{}
\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
\input{images/16-ec-from-oes32-cut.tex}
\end{center}
\caption{Visualisierung eines 16-Schnittmusters, das auf
- $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes
- Sortiernetzwerk ergibt.}
+ $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
+ bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
+ resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
+ dargestellt.}
\label{fig:16-ec-from-oes32-cut}
\end{figure}
\input{images/16-ec-from-oes32.tex}
\end{center}
\caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
- Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem
- \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(32)$ durch
- 16~Schnitte erzeugt.}
+ Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
+ einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
+ berechnet wurde. Das Schnittmuster ist in
+ Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
\label{fig:16-ec-from-oes32}
\end{figure}
projects / diplomarbeit.git / blobdiff