X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=6809fffb59b60685f314301e72bb0cdc0bf977a1;hb=f9401849ff887c2d920650a71801b64a04d38b70;hp=591aa4e6e696453ae5d6cd6f73a19c8d0ebe6700;hpb=6ad09e4aabf63f4ebfbe36cf940615132691bb71;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 591aa4e..6809fff 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -155,12 +155,12 @@ Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind, 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 @@ -205,9 +205,9 @@ zerstört. \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 @@ -232,8 +232,8 @@ Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1, 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} @@ -260,47 +260,55 @@ Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine 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 -$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, -ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(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 @@ -420,7 +428,7 @@ in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die 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} @@ -435,7 +443,7 @@ ${n = 8}$ Leitungen. \begin{center} \input{images/oe-transposition-8.tex} \end{center} - \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.} + \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.} \label{fig:odd-even-transposition-08} \end{figure} @@ -458,7 +466,7 @@ $\operatorname{OET}(3)$ sortiert. Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n -(n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind. +(n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind. Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren, ($\Theta(n \log (n)^2)$), die in weniger Schichten, ($\Theta(\log (n)^2)$), angeordnet sind. @@ -488,7 +496,7 @@ sortierte Listen zusammenfügen (Englisch: \textit{to~merge}) kann. Dieser 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} @@ -574,7 +582,7 @@ Statt an eine Treppe erinnert das Muster nun an einen Trichter. Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus -$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren +$\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren besteht, die in $\log(n)$~Schichten angeordnet werden können. \subsubsection{Das bitone Mergesort-Netzwerk} @@ -598,10 +606,10 @@ alle Komparatoren in die gleiche Richtung zeigen. \begin{center} \input{images/batcher-8.tex} \end{center} - \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht - Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden - bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten - rekursiven Schritt hinzugefügt wurden (grün).} + \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~Eingänge. + Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden bitonen + Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven + Schritt hinzugefügt wurden (grün).} \label{fig:bitonic-08} \end{figure} @@ -656,10 +664,12 @@ w_i = \left\{ \begin{array}{ll} \begin{center} \input{images/oe-merge.tex} \end{center} - \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Im - Vergleich zum bitonen Mischer für acht Leitungen kommt dieses Schema mit - einem Komparator weniger aus. Der Effekt wird durch den rekursiven Aufbau - verstärkt.} + \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die + beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$, + die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der + Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt + dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den + rekursiven Aufbau verstärkt.} \label{fig:oe-merge} \end{figure} @@ -701,7 +711,7 @@ Aufbau lauten: einzelnen Komparator. \end{itemize} -Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass die resultierende Folge +Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise $V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den @@ -746,7 +756,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \end{figure} Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden, -bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$ +bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$ Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit Schichten im Mischer-Netzwerk), hängt von der längeren der beiden Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$. @@ -764,9 +774,9 @@ Länge der Eingabefolgen, $n$ und $m$ ab: \end{displaymath} Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar, -dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist. +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$ @@ -780,9 +790,9 @@ einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots, \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} @@ -802,7 +812,7 @@ die als leere Komparatornetzwerke definiert sind. \begin{center} \input{images/oe-mergesort-8.tex} \end{center} - \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert + \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~Eingänge. Markiert sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten @@ -813,7 +823,7 @@ die als leere Komparatornetzwerke definiert sind. In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk zu sehen. Rot markiert sind die beiden rekursiven Instanzen $\operatorname{OES}(4)$. Die anderen Blöcke stellen den -\emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind +\emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden. @@ -830,11 +840,11 @@ geschlossene Darstellung von $k(n)$ ebenfalls nicht ohne weiteres möglich. Es 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. @@ -874,7 +884,7 @@ früh wie möglich ausführt. So entsteht die kleinstmögliche Anzahl von \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 @@ -935,7 +945,7 @@ zu sortieren und die Ausgaben mit einem der beschriebenen Mischer zusammenfügen. Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken} -$\operatorname{BS}(8)$ mit je acht Leitungen mit dem +$\operatorname{BS}(8)$ mit je 8~Leitungen mit dem \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt @@ -945,16 +955,16 @@ Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren), 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 @@ -1240,9 +1250,11 @@ Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer (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, @@ -1252,13 +1264,24 @@ die bei Sortiernetzwerken verfolgt werden können: \item Möglichst wenige Schichten („schnell“) \end{itemize} -Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das -effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus -60~Komparatoren in 10~Schichten. Das schnellste bekannte 16-Sortiernetzwerk -besteht aus 61~Komparatoren in nur 9~Schichten. - -Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"' -berücksichtigen kann, hat die folgende allgemeine Form: +\begin{figure} + \centering + \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}} + \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}} + \caption{Das effizienteste und das schnellste Sortiernetzwerk für + 16~Leitungen, das derzeit bekannt ist.} + \label{fig:16-best-known} +\end{figure} +Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. +Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für +16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in +Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte +16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in +Abbildung~\ref{fig:16-voorhis} zu sehen. + +\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} @@ -1283,7 +1306,7 @@ verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des 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 @@ -1294,24 +1317,42 @@ Leitungszahlen und Mischer-Typen experimentiert werden muss. 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} -Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere -Wahrscheinlichkeit haben zur nächsten Generation beizutragen. Diese -Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das -Streben des Algorithmus nach besseren Lösungen. +Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig +aus der Population auswählt. Sie werden im folgenden Schritt miteinander +rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht +gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen +eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen. +Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für +das Streben des Algorithmus nach besseren Lösungen. Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint, -ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der -Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. +passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt +und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert. -Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von -Pseudocode wie folgt beschreiben: +Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt +sich mit Pseudocode wie folgt beschreiben: \begin{verbatim} Gütesumme := 0 Auswahl := (leer) @@ -1330,6 +1371,10 @@ Pseudocode wie folgt beschreiben: gib Auswahl zurück \end{verbatim} +Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die +Rekombination zu erhalten. Das heißt, dass die Individuen bei +\textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden. + \subsection{Rekombination} \label{sect:sn-evolution:rekombination} @@ -1373,37 +1418,12 @@ wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet. \subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer} -\begin{figure} - \begin{center} - \input{images/16-e1-bitonic-1296542566.tex} - \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in - 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers} - erzeugt.} - \label{fig:16-e1-bitonic-1296542566} -\end{figure} - Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen -Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in -Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück. - -Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser -Konfiguration gefunden werden, sind effizienter als das \emph{bitone -Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen -Merge}-Netzwerk \bm{n} beruht. Das in -Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk -benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}. - -Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke -bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n} -sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als -\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit -134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von -schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen -Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast} -aufgelistet. +Mischer} verwendet, gibt der Algorithmus \emph{effiziente} und in einigen +Fällen \emph{schnelle} Sortiernetzwerke aus. Die Ergebnisse des +\textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers} +sind in Tabelle~\ref{tbl:sn-ev-bm-fast} zusammengefasst. \begin{table}\label{tbl:sn-ev-bm-fast} \begin{center} @@ -1414,23 +1434,23 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l| \cline{2-5} ($n$) & Komp. & Schichten & Komp. & Schichten \\ \hline - 8 & \gcell 20 & 6 & 24 & 6 \\ - 9 & \Gcell 26 & 8 & 28 & 8 \\ - 10 & \gcell 31 & \gcell 8 & 33 & 9 \\ - 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\ - 12 & \gcell 42 & \gcell 9 & 46 & 10 \\ - 13 & \Gcell 48 & 10 & 53 & 10 \\ - 14 & \gcell 54 & 10 & 61 & 10 \\ - 15 & \Gcell 61 & 10 & 70 & 10 \\ - 16 & \gcell 67 & 10 & 80 & 10 \\ - 17 & \Gcell 76 & 12 & 85 & 12 \\ - 18 & \gcell 87 & \gcell 12 & 91 & 13 \\ - 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\ - 20 & \gcell 104 & \gcell 13 & 106 & 14 \\ - 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\ - 22 & \gcell 118 & \gcell 14 & 123 & 15 \\ - 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\ - 24 & \gcell 133 & 15 & 144 & 15 \\ + 8 & \gcell 20 & 6 & 24 & 6 \\ + 9 & \Gcell 26 & 8 & 28 & 8 \\ + 10 & \gcell 31 & \gcell 8 & 33 & 9 \\ + 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\ + 12 & \gcell 42 & \gcell 9 & 46 & 10 \\ + 13 & \Gcell 48 & 10 & 53 & 10 \\ + 14 & \gcell 54 & 10 & 61 & 10 \\ + 15 & \Gcell 61 & 10 & 70 & 10 \\ + 16 & \gcell 67 & 10 & 80 & 10 \\ + 17 & \Gcell 76 & 12 & 85 & 12 \\ + 18 & \gcell 87 & \gcell 12 & 91 & 13 \\ + 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\ + 20 & \gcell 104 & \gcell 13 & 106 & 14 \\ + 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\ + 22 & \gcell 118 & \gcell 14 & 123 & 15 \\ + 23 & \Gcell 129 & \Gcell 14 & 133 & 15 \\ + 24 & \gcell 133 & 15 & 144 & 15 \\ \hline \end{tabular} \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus @@ -1442,19 +1462,89 @@ Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l| \end{center} \end{table} -\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} +Alle Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser Konfiguration +gefunden wurden, waren \emph{effizienter} als das \emph{bitone +Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen +Merge}-Netzwerk \bm{n} beruht. Zum Beispiel benötigt das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk +67~Komparatoren, 13~Komparatoren weniger als \bs{n}. \begin{figure} \begin{center} - \input{images/16-e1-oddeven-1296543330.tex} + \input{images/16-e1-bitonic-1296542566.tex} \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers + \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers} erzeugt.} - \label{fig:16-e1-oddeven-1296543330} + \label{fig:16-e1-bitonic-1296542566} +\end{figure} + +Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke +bevorzugt, werden in einigen Fällen Netzwerke zurückgegeben, die +\emph{schneller} und \emph{effizienter} als \bs{n} sind. Das +19-Sortiernetzwerk in Abbildung~\ref{fig:19-e1-bm-fast} besitzt beispielsweise +nur 13~Schichten und benötigt damit einen parallelen Schritt weniger als +\bs{19}. + +\begin{figure} + \begin{center} + \input{images/19-e1-bm-fast.tex} + \end{center} + \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in + 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution} + unter Verwendung des \emph{bitonen Mischers} erzeugt.} + \label{fig:19-e1-bm-fast} \end{figure} +\subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} + +Die folgenden Ergebnisse wurden erzielt, indem \textsc{SN-Evolution} mit dem +\emph{Odd-Even-Transpositionsort}-Netzwerk als Eingabe gestartet wurde und in +der Rekombinationsphase das \emph{Odd-Even-Merge}-Netzwerk verwendete. So +erzeugt der Algorithmus entweder Sortiernetzwerke, die genauso schnell und +effizient wie das \oes{n}-Netzwerk, oder Sortiernetzwerke, die schneller aber +weniger effizient als das \oes{n}-Netzwerk sind. Die Ergebnisse von +\textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer sind in +Tabelle~\ref{tbl:sn-ev-oem-fast} zusammengefasst. + +\begin{table}\label{tbl:sn-ev-oem-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\ +\cline{2-5} + & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & 19 & 6 & 19 & 6 \\ + 9 & 26 & 8 & 26 & 8 \\ + 10 & 31 & 9 & 31 & 9 \\ + 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\ + 12 & 43 & \gcell 9 & \gcell 41 & 10 \\ + 13 & 48 & 10 & 48 & 10 \\ + 14 & 53 & 10 & 53 & 10 \\ + 15 & 59 & 10 & 59 & 10 \\ + 16 & 63 & 10 & 63 & 10 \\ + 17 & 74 & 12 & 74 & 12 \\ + 18 & 82 & 13 & 82 & 13 \\ + 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\ + 20 & 97 & 14 & 97 & 14 \\ + 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\ + 22 & 117 & \gcell 14 & \gcell 114 & 15 \\ + 23 & 127 & \Gcell 14 & \Gcell 122 & 15 \\ + 24 & 128 & 15 & \gcell 127 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der + Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} + gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion + nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = + 1$, $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} + Im vorherigen Abschnitt wurde gezeigt, dass der \textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers} Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem @@ -1464,16 +1554,34 @@ erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks findet, erreichen das \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in -Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. +Abbildung~\ref{fig:16-e1-oem-fast} dargestellt. + +\begin{figure} + \begin{center} + \input{images/16-e1-oem-fast.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers + erzeugt.} + \label{fig:16-e1-oem-fast} +\end{figure} Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution} -Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht -beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt -\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen. -\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der -Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet -sich in Tabelle~\ref{tbl:sn-ev-oem-fast}. +Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Beispielsweise +benötigt das 19-Sortiernetzwerk, das in Abbildung~\ref{fig:19-e1-oem-fast} +dargestellt ist, nur 13~Schichten, während \oes{19} 14~Schichten benötigt. + +\begin{figure} + \begin{center} + \input{images/19-e1-oem-fast.tex} + \end{center} + \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in + 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution} + unter Verwendung des \emph{Odd-Even}-Mischers erzeugt.} + \label{fig:19-e1-oem-fast} +\end{figure} %\begin{figure} %\begin{center} @@ -1507,43 +1615,6 @@ sich in Tabelle~\ref{tbl:sn-ev-oem-fast}. %\label{fig:10-e2-1239014566} %\end{figure} -\begin{table}\label{tbl:sn-ev-oem-fast} -\begin{center} -\rowcolors{4}{black!5}{} -\begin{tabular}{|r|r|r|r|r|} -\hline -Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\ -\cline{2-5} - & Komp. & Schichten & Komp. & Schichten \\ -\hline - 8 & 19 & 6 & 19 & 6 \\ - 9 & 26 & 8 & 26 & 8 \\ - 10 & 31 & 9 & 31 & 9 \\ - 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\ - 12 & 43 & \gcell 9 & \gcell 41 & 10 \\ - 13 & 48 & 10 & 48 & 10 \\ - 14 & 53 & 10 & 53 & 10 \\ - 15 & 59 & 10 & 59 & 10 \\ - 16 & 63 & 10 & 63 & 10 \\ - 17 & 74 & 12 & 74 & 12 \\ - 18 & 82 & 13 & 82 & 13 \\ - 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\ - 20 & 97 & 14 & 97 & 14 \\ - 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\ - 22 & 117 & \gcell 14 & \gcell 114 & 15 \\ - 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\ - 24 & 128 & 15 & \gcell 127 & 15 \\ -\hline -\end{tabular} -\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus - unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der - Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} - gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion - nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = - 1$, $w_{\mathrm{Schichten}} = n$.} -\end{center} -\end{table} - \subsection{Zufälliger Mischer} Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige @@ -1555,427 +1626,100 @@ Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur um das beste Ergebnis beider Konstruktionen zu erreichen. \textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem -\emph{Odd-Even}-Mischer wählen. \todo{Daten noch in eine Tabelle einfügen.} - -%\input{shmoo-aequivalenz.tex} - -\newpage -\section{Der \textsc{SN-Evolution-Cut}-Algorithmus} -\label{sect:sn-evolution-cut} - -Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären -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}. Mit diesem -Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst -gute Schnittmuster gesucht. - -Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die -in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen. -Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$ -oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem -$k$-Schnittmuster sind genau $k$ Zahlen nicht Null. - -Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen -Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters -verwendet. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq n$. Anschließend -werden zufällig Werte auf Null beziehungsweise 1 oder $-1$ gesetzt, um die -Anzahl der Schnitte zu korrigieren. - -Die Mutation vertauscht entweder die Werte von zwei zufälligen Positionen oder -multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu -invertieren. - -\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk} - -\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, -wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde, -durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen -Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer -sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert -werden, Komparatoren ein. - -Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein -Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer -konstruiert wurde. Dieses Sortiernetzwerk be\-nö\-tigt 68~Komparatoren, -12~weniger als das \emph{bitone Mergesort}-Netzwerk nach Batchers Methode. -Gegenüber Batchers Methode sparen so konstruierte Sortiernetzwerke -${\frac{1}{4}n(\log n - 1)}$ Komparatoren ein. - -\begin{figure} - \begin{center} - \input{images/16-ec-from-bs32.tex} - \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in - 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk} - $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.} - \label{fig:16-ec-from-bs32} -\end{figure} - -\begin{figure} - \begin{center} - \input{images/16-ec-from-bs32-normalized.tex} - \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in - 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk - $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.} - \label{fig:16-ec-from-bs32-normalized} -\end{figure} - -Startet man {\sc SN-Evolution-Cut} mit dem \emph{bitonen Mergesort}-Netzwerk -$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der -Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein -16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den -Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized} -zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$ -und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26, -29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch -\textsc{SN-Evolution-Cut} gefunden wurde. -Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk -nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine -Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in -diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des -Netzwerks scheinen rein zufällig zu sein. - -\begin{figure} - % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX - % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX - % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX - % 63:MAX - \begin{center} - \input{images/32-ec-from-bs64.tex} - \end{center} - \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in - 15~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk - $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige - Schnittmuster ist - $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$, - $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37, - 40, 43, 47, 48, 49, 55, 56, 60, 63)$.} - \label{fig:32-ec-from-bs64} -\end{figure} - -Das Ergebnis von \textit{Mühlenthaler} und \textit{Wanka}, die den bitonen -Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk -konstruiert haben, kann demnach auch erreicht werden, wenn -$\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen -Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein -32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden, -wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode -konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den -optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf -208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte -Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller -dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die -Geschwindigkeit dieser Sortiernetzwerke gleich ist. - -Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr -unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für -gute Schnittmuster anzugeben. - -Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen -Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein. -Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in -Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 -ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten -ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich -die Schnittmuster aufgrund der Symmetrie des \emph{bitonen -Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung -- -mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig. - -\begin{figure} - \centering - \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}} - \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}} - \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann - der Algorithmus schnelle Sortiernetzwerke ausgeben.} - \label{fig:11-12-ec-from-bs22-bs24} -\end{figure} - -Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des -\emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist, -können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch -effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die -folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für -\textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit -der doppelten Leitungszahl. Die Abbildungen~\ref{fig:11-12-ec-from-bs22-bs24} -und~\ref{fig:23-ec-from-bs46} zeigen beispielhaft ein 11-, 12- und -23-Sortiernetzwerk, die aus \bs{22}, \bs{24} und \bs{46} generiert wurden. +\emph{Odd-Even}-Mischer wählen. Die Ergebnisse von \textsc{SN-Evolution} bei +einer zufälligen Wahl des Mischers in der Rekombinationsphase sind in +Tabelle~\ref{tbl:sn-ev-rnd-fast} zusammengefasst. +\begin{table}\label{tbl:sn-ev-rnd-fast} \begin{center} -\begin{tabular}{|r|r|r|r|r|} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|r|r|} \hline -Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\ - & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} & - \bs{n} \\ +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} + & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} + & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\ +\cline{2-7} + ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\ \hline -11 & 37 & 9 & 39 & 10 \\ -12 & 42 & 9 & 46 & 10 \\ -19 & 93 & 13 & 98 & 14 \\ -20 & 102 & 13 & 106 & 14 \\ -% 20: # sn-cut 2:MAX 3:MIN 4:MIN 9:MIN 10:MIN 13:MIN 14:MIN 15:MIN 19:MIN 20:MAX 24:MAX 26:MIN 27:MAX 29:MIN 31:MAX 33:MIN 34:MAX 35:MIN 37:MIN 39:MAX -21 & 109 & 14 & 114 & 15 \\ -22 & 116 & 14 & 123 & 15 \\ -23 & 124 & 14 & 133 & 15 \\ + 8 & 20 & 6 & \gcell 19 & 6 & \gcell 19 & 6 \\ + 9 & 26 & 8 & 26 & 8 & 26 & 8 \\ + 10 & 31 & \gcell 8 & 31 & 9 & 31 & \gcell 8 \\ + 11 & \Gcell 37 & 9 & 38 & 9 & \Gcell 37 & 9 \\ + 12 & 42 & 9 & 43 & 9 & \gcell 41 & 9 \\ + 13 & 48 & 10 & 48 & 10 & 48 & 10 \\ + 14 & 54 & 10 & \gcell 53 & 10 & \gcell 53 & 10 \\ + 15 & 61 & 10 & \Gcell 59 & 10 & \Gcell 59 & 10 \\ + 16 & 67 & 10 & \gcell 63 & 10 & 64 & 10 \\ + 17 & 76 & 12 & \Gcell 74 & 12 & \Gcell 74 & 12 \\ + 18 & 87 & \gcell 12 & \gcell 82 & 13 & 83 & \gcell 12 \\ + 19 & 93 & 13 & 93 & 13 & \Gcell 92 & 13 \\ + 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\ + 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\ + 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\ + 23 & 129 & 14 & \Gcell 127 & 14 & 128 & 14 \\ + 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\ \hline \end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung der beiden Mischer-Netzwerke. Der Algorithmus wurde mit dem + \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach + 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten + $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$ und + $w_{\mathrm{Schichten}} = n$.} \end{center} +\end{table} + +Bei einigen Leitungszahlen kann der Algorithmus durch die Verfügbarkeit beider +Mi\-scher-Netzwerke Sortiernetzwerke zurückgeben, die effizienter als die +vorherigen Ergebnisse sind. Beispielsweise ist das 19-Sortiernetzwerk in +Abbildung~\ref{fig:19-e1-rnd-fast} mit 92~Komparatoren effizienter als die +19-Sortiernetzwerke, die mit nur einem der beiden Mischer-Netzwerke erreicht +wurden (Abbildungen~\ref{fig:19-e1-bm-fast} und~\ref{fig:19-e1-oem-fast}). \begin{figure} \begin{center} - \input{images/23-ec-from-bs46-fast.tex} + \input{images/19-e1-rnd-fast.tex} \end{center} - \caption{23-Sortiernetzwerk mit 124~Komparatoren in 14~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{46} mit dem - Schnittmuster $\operatorname{MIN}(2, 4, 9, 12, 20, 22, 28, 30, 32, 33, 37, - 38, 41)$, $\operatorname{MAX}(1, 5, 16, 19, 21, 24, 25, 35, 36, 43)$ - erzeugt.} - \label{fig:23-ec-from-bs46} + \caption{Sortiernetzwerk mit 19~Leitungen und 92~Komparatoren in + 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution} + unter Verwendung des \emph{bitonen Mischers} und des + \emph{Odd-Even}-Mischers erzeugt.} + \label{fig:19-e1-rnd-fast} \end{figure} -Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur -haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere -von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem -\emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und -$m$~Schnitten gestartet, so ist das beste Ergebnis immer das -$\operatorname{OET}(n-m)$-Netzwerk. - -\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk} - -Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk} -$\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The -Pairwise Sorting Network“ \cite{P1992} definiert. 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. +Die Ergebnisse anderer Leitungszahlen erreichen die Geschwindigkeit der +Ergebnisse, die mit dem \emph{bitonen Mischer} erzielt wurden. Die Effizienz +liegt zwischen den Ergebnissen, die mit dem \emph{bitonen Mischer} erzielt +wurden, und den Ergebnissen, die mit dem \emph{Odd-Even}-Mischer erzielt +wurden. Beispielsweise ist das 18-Sortiernetzwerk in +Abbildung~\ref{fig:18-e1-rnd-fast} so schnell wie das Ergebnis, das mit dem +\emph{bitonen Mischer} ausgegeben wurde. Mit 83~Komparatoren liegt die +Effizienz des Sortiernetzwerks zwischen den Ergebnissen, die mit dem +\emph{bitonen Mischer} (87~Komparatoren), beziehungsweise dem +\emph{Odd-Even}-Mischer (82~Komparatoren) erreicht werden konnten. \begin{figure} \begin{center} - \input{images/16-ec-from-ps32.tex} + \input{images/18-e1-rnd-fast.tex} \end{center} - \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in - 10~Schichten. Das Netzwerk wurde von dem Algorithmus - \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} - $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} - \label{fig:16-ec-from-ps32} + \caption{Sortiernetzwerk mit 18~Leitungen und 83~Komparatoren in + 12~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution} + unter Verwendung des \emph{bitonen Mischers} und des + \emph{Odd-Even}-Mischers erzeugt.} + \label{fig:18-e1-rnd-fast} \end{figure} -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 -den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die -strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die -Schichten~1 und~2 sowie 4~und~5 sind vertauscht. +In einigen Fällen hat \textsc{SN-Evolution} in dieser Konfiguration +Sortiernetzwerke ausgegeben, die weniger effizient und genauso schnell wie die +bisherigen Ergebnisse unter Verwendung des \emph{Odd-Even}-Mischers sind. +Prinzipiell könnte der Algorithmus in jeder Iteration zufällig den +\emph{Odd-Even}-Mischers auswählen, um die selektierten Individuen zu +rekombinieren. Das heißt, das die Ergebnisse auch bei einer zufälligen Wahl +des Mischer-Netzwerks theoretisch erreicht werden können. Allerdings sind +unter Umständen mehr Iterationen notwendig, bis die gleiche Effizienz erreicht +wird. -\begin{figure} - \begin{center} - \input{images/32-pairwise-cut-16-pairwise.tex} - \end{center} - \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu - sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk - bilden.} - \label{fig:ps16-from-ps32} -\end{figure} - -Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach -regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres -schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das -einfache Schnittmuster -\begin{displaymath} -\textit{Eingang}_i = \left\{ \begin{array}{rl} - -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\ - \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\ - ? & \quad \mathrm{sonst} - \end{array} \right. -\end{displaymath} -für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk -$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der -dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das -verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32} -dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind -diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden -Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den -„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht -werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende -Netzwerk in schwarz gut zu erkennen. - -\begin{figure} - \begin{center} - \input{images/16-pairwise.tex} - \end{center} - \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten - ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das - resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.} - \label{fig:16-pairwise} -\end{figure} - -Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf -$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein -8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für -größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise -kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} -konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} -untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. - -\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk} -\label{sect:sn-evolution-cut:oes} - -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. - -Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das -bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, 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 -Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen. - -\begin{figure} - \begin{center} - \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.} - \label{fig:16-ec-from-oes32-cut} -\end{figure} - -\begin{figure} - \begin{center} - \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.} - \label{fig:16-ec-from-oes32} -\end{figure} - -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 -\begin{displaymath} -\textit{Eingang}_i = \left\{ \begin{array}{rl} - \infty & \quad \textrm{falls } i \bmod 4 = 0 \\ - -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\ - ? & \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. - -\begin{figure} - \begin{center} - \input{images/32-ec-from-oes64.tex} - \end{center} - \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten. - Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem - \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.} - \label{fig:32-ec-from-oes64} -\end{figure} - -Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so -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 -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 -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}. - -\begin{figure} - \centering - \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in - 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem - \emph{Odd-Even-Mergesort}-Netzwerk generiert - wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}} - \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten, - das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk - generiert - wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}} - \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das - Ergebnis von der Bewertungsfunktion ab.} - \label{fig:12-ec-from-oes24} -\end{figure} - -Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut} -findet Sortiernetzwerke, die schneller sind als das entsprechende -\emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit -22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige -schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können, -charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das -\emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl. -\begin{center} -\begin{tabular}{|r|r|r|r|r|} -\hline -Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\ - & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\ -\hline -11 & 38 & 9 & 37 & 10 \\ -12 & 43 & 9 & 41 & 10 \\ -19 & 93 & 13 & 91 & 14 \\ -20 & 101 & 13 & 97 & 14 \\ -21 & 108 & 14 & 107 & 15 \\ -22 & 116 & 14 & 114 & 15 \\ -23 & 125 & 14 & 122 & 15 \\ -\hline -\end{tabular} -\end{center} -Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein -23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem -Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der -Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In -beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu -\bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das -Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46}) -effizienter, da es nur 124~Komparatoren benötigt. - -\begin{figure} - \begin{center} - \input{images/23-ec-from-oes46-fast.tex} - \end{center} - \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten. - Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem - Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38, - 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$ - erzeugt.} - \label{fig:23-ec-from-oes46} -\end{figure} +%\input{shmoo-aequivalenz.tex} \newpage \section{Der \textsc{SN-Markov}-Algorithmus} @@ -2147,6 +1891,786 @@ zusammenhängt. %\end{figure} \newpage +\section[\textsc{SN-Evolution-Cut}]{Der \textsc{SN-Evolution-Cut}-Algorithmus} +\label{sect:sn-evolution-cut} + +Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären +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:sn-evolution:bewertung}. + +Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die +in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen. +Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$ +oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem +$k$-Schnittmuster sind genau $k$ Zahlen ungleich Null. + +Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen +Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters +verwendet. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq n$. Anschließend +werden zufällig Werte auf Null beziehungsweise 1 oder $-1$ gesetzt, um die +Anzahl der Schnitte zu korrigieren. + +Die Mutation vertauscht entweder die Werte von zwei zufälligen Positionen oder +multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu +invertieren. + +Die Eingabe für \textsc{SN-Evolution-Cut} ist ein $n$-Sortiernetzwerk und eine +Zahl $k$, $1 \leqq k < n$, die angibt wie viele Leitungen entfernt werden +sollen. Der Rückgabewert des \textsc{SN-Evolution-Cut}-Algorithmus ist ein +\emph{$k$-Schnittmuster}. Wird das Schnittmuster auf das Sortiernetzwerk, mit +dem der Algorithmus gestartet wurde, angewendet, entsteht ein möglichst +schnelles und effizientes Sortiernetzwerk mit $m = n - k$ Leitungen. Da mit +dem Eingabe-Netzwerk und dem zurückgegebenen $k$-Schnittmuster das +$m$-Sortiernetzwerk eindeutig bestimmt ist, werden im Folgenden sowohl das +$k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von +\textsc{SN-Evolution-Cut} bezeichnet. + +\subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk} +\label{sect:sn-evolution-cut:bs} + +Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen +Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll, +ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke +als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k += 6$ gestartet, resultiert das gefundene Schnittmuster in einem +Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16} +benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert +wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen. + +\begin{figure} + \begin{center} + \input{images/16-ec-from-bs22.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk + $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4, + 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.} + \label{fig:16-ec-from-bs22} +\end{figure} + +Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen +Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden, +gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde +mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten +der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$, +$w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder +Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten +befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des +Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des +resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der +Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu +können. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|rrrrrrrrrrrrrrrr|} + \hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ + \hline + 9 & 21 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\ + 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\ + 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\ + 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\ + 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\ + 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\ + 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\ + 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\ + 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\ + 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\ + 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\ + 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\ + 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\ + \hline +\bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen + Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt + die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die + Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.} + \label{tbl:ec-bs-efficiency} +\end{table} + +Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut} +mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der +gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von +$m=23$) ein Ergebnis, das effizienter als \bs{m} ist. + +In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein +effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut} +gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren +3~weniger als \bs{19}. + +Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke, +beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein +Sortiernetzwerk mit 31~Komparatoren gefunden. + +\begin{figure} + \centering + \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}} + \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}} + \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}} + \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}} + \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11, + 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke + erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.} + \label{fig:ec-bs-fast_networks} +\end{figure} + +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} 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} + \rowcolors{2}{black!5}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 6 & & & & & & & & & & & & & & & \\ + 10 & 6 & 8 & & & & & & & & & & & & & & \\ + 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\ + 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\ + 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\ + 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\ + 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\ + 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\ + 17 & 6 & 8 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\ + 18 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\ + 19 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\ + 20 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\ + 21 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\ + 22 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\ + 23 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\ + 24 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\ +\hline +\bs{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\ +\hline +\end{tabular} + \end{center} + \caption{Anzahl der Schichten der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen + Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt + die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die + Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.} + \label{tbl:ec-bs-speed} +\end{table} + +Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die +schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke, +die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt +werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt. + +Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das +Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m} +führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt +werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht +einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m += 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu +reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise +noch größer gewählt werden. + +Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von +\textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten +werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in +Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im +Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n = +37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19} +und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein +Beispiel für ein solches Netzwerk ist in +Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|r|r|} + \hline + $n$ & Komp. & Schichten \\ + \hline + 20 & 95 & 14 \\ + 21 & 94 & 14 \\ + 22 & 93 & 14 \\ + 23 & 93 & 14 \\ + 24 & 93 & 14 \\ + 25 & 96 & 13 \\ + 26 & 96 & 13 \\ + 27 & 96 & 13 \\ + 28 & 96 & 13 \\ + 29 & 95 & 13 \\ + 30 & 96 & 13 \\ + 31 & 95 & 13 \\ + 32 & 96 & 13 \\ + 33 & 93 & 13 \\ + 34 & 94 & 13 \\ + 35 & 93 & 13 \\ + \rowcolor{green!10} + 36 & 92 & 13 \\ + \rowcolor{green!10!white!95!black} + 37 & 92 & 13 \\ + 38 & 93 & 13 \\ + \hline + \bs{19} & 98 & 14 \\ + \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 \bs{n}, $n = 20, \dots, 38$ erzeugt + wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als + \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit + 13~Schichten die Effizienz der vorherigen + Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese + Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37} + auf diese Art erzeugt wurde, ist in + Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.} + \label{tbl:ec-bs-19} +\end{table} + +\textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, +wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode +konstruiert wurde, durch systematisches Entfernen von Leitungen in einen +ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert werden +kann, so dass dieser alternative Mischer im Vergleich zu $\bm{\frac{n}{2} = +2^{d-1}}$ Komparatoren einspart. + +Basierend auf diesen alternativen Mischern geben \textit{Mühlenthaler} und +\textit{Wanka} eine Konstruktionsvorschrift für Sortiernetzwerke an, die +gegenüber \bs{n} ${\frac{1}{4}n(\log n - 1)}$ Komparatoren einspart. +Beispielsweise wird ein 16-Sortiernetzwerk angegeben, das nur 68~Komparatoren +benötigt. Dieses Netzwerk ist in Abbildung~\ref{fig:16-muehlenthaler} +dargestellt. + +\begin{figure} + \begin{center} + \input{images/16-muehlenthaler.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in + 10~Schichten. Das Netzwerk wurde 2010 von \textit{Mühlenthaler} und + \textit{Wanka} aus optimierten bitonen Mischern konstruiert und + in~\cite{MW2010} veröffentlicht.} + \label{fig:16-muehlenthaler} +\end{figure} + +\begin{figure} + \begin{center} + \input{images/16-ec-from-bs32.tex} + \end{center} + \caption{Visualisierung eines 16-Schnittmusters, das von + \textsc{SN-Evolution-Cut} für das \emph{bitone Mergesort}-Netzwerk \bs{32} + berechnet wurde. Das resultierende Sortiernetzwerk besteht aus + 68~Komparatoren in 10~Schichten und ist in + Abbildung~\ref{fig:16-ec-from-bs32-normalized} als + Standard-Sortiernetzwerk dargestellt.} + \label{fig:16-ec-from-bs32} +\end{figure} + +\begin{figure} + \begin{center} + \input{images/16-ec-from-bs32-normalized.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in + 10~Schichten. Das Netzwerk wurde mit einem 16-Schnittmuster, das von + \textsc{SN-Evolution-Cut} berechnet wurde, aus dem \emph{bitone + Mergesort}-Netzwerk \bs{32} erzeugt. Das Schnittmuster ist in + Abbildung~\ref{fig:16-ec-from-bs32} dargestellt.} + \label{fig:16-ec-from-bs32-normalized} +\end{figure} + +Startet man {\sc SN-Evolution-Cut} mit dem \emph{bitonen Mergesort}-Netzwerk +$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der +Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein +16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den +Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized} +zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$ +und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26, +29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch +\textsc{SN-Evolution-Cut} gefunden wurde. +Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk +nachdem das Schnittmuster angewendet und das Netzwerk normalisiert wurde. +% Eine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist +% in diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten +% des Netzwerks scheinen rein zufällig zu sein. + +\begin{figure} + % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX + % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX + % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX + % 63:MAX + \begin{center} + \input{images/32-ec-from-bs64.tex} + \end{center} + \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in + 15~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk + $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige + Schnittmuster ist + $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$, + $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37, + 40, 43, 47, 48, 49, 55, 56, 60, 63)$.} + \label{fig:32-ec-from-bs64} +\end{figure} + +Wenn \textsc{SN-Evolution-Cut} mit dem \bs{64}-Netzwerk und $k = 32$ gestartet +wird, findet der Algorithmus 32-Sortiernetzwerke, die effizienter sind als +32-Sortiernetzwerke, die nach \textit{Mühlenthalers} und \textit{Wankas} +Methode konstruiert werden. Ein von \textsc{SN-Evolution-Cut} aus \bs{64} +generiertes 32-Sortiernetzwerk ist in Abbildung~\ref{fig:32-ec-from-bs64} +dargestellt. Das \emph{bitone Mergesort}-Netzwerk \bs{32} benötigt +240~Komparatoren, ein aus den optimierten Mischern aufgebautes Netzwerk +verbessert die Effizienz auf 208~Komparatoren. Das Ergebnis von +\textsc{SN-Evolution-Cut} kommt mit nur 206~Komparatoren aus. Die +Geschwindigkeit aller genannten Sortiernetzwerke ist mit 15 parallelen +Schritten identisch. + +Wenn die Leitungszahl des Eingabenetzwerks keine Zweierpotenz ist, kann +\textsc{SN-Evo\-lu\-tion-Cut} auch 16-Sortiernetzwerke erzeugen, die diese +Effizienz unterbieten. Das geht aus den Daten in +Tabelle~\ref{tbl:ec-bs-efficiency} hervor. Ein 16-Sortiernetzwerk mit +67~Komparatoren, das von \textsc{SN-Evolution-Cut} generiert wurde, ist in +Abbildung~\ref{fig:16-ec-from-bs22} dargestellt. + +Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr +unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für +gute Schnittmuster anzugeben. + +Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen +Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein. +Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in +Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 +ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten +ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich +die Schnittmuster aufgrund der Symmetrie des \emph{bitonen +Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung -- +mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig. + +Dass die Sortiernetzwerke, die mit den Schnittmustern von +\textsc{SN-Evolution-Cut} entstehen, keine erkennbare Struktur haben, ist +jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere von der +Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem +\emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(n)$ und +$k$~Schnitten gestartet, so ist das beste Ergebnis immer das +$\operatorname{OET}(n-k)$-Netzwerk. + +\subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk} +\label{sect:sn-evolution-cut:oes} + +Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk +\oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die +genauso effizient und schnell wie das entsprechende +\emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der +Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus +\oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency} +tabellarisch. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 19 & & & & & & & & & & & & & & & \\ + 10 & 19 & 26 & & & & & & & & & & & & & & \\ + 11 & 19 & 26 & 31 & & & & & & & & & & & & & \\ + 12 & 19 & 26 & 31 & 37 & & & & & & & & & & & & \\ + 13 & 19 & 26 & 31 & 37 & 41 & & & & & & & & & & & \\ + 14 & 19 & 26 & 31 & 37 & 41 & 48 & & & & & & & & & & \\ + 15 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\ + 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\ + 17 & 19 & 26 & 31 & 38 & 41 & 48 & 53 & 59 & 63 & & & & & & & \\ + 18 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & & & & & & \\ + 19 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & & & & & \\ + 20 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & & & & \\ + 21 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & & & \\ + 22 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & & \\ + 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 +\end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} + \label{tbl:ec-oes-efficiency} +\end{table} + +\begin{figure} + \centering + \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{17} erzeugt.]{\input{images/11-ec-from-oes17-fast.tex}\label{fig:11-ec-from-oes17-fast}} + \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das + Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{18} erzeugt.]{\input{images/12-ec-from-oes18-fast.tex}\label{fig:12-ec-from-oes18-fast}} + \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m = + 11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke + erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m} + sind.} + \label{fig:ec-oes-fast_networks} +\end{figure} + +Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt +schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein +$m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes +Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit +war allerdings in allen beobachteten Fällen nur dann möglich, wenn +zusätzliche Komparatoren in Kauf genommen wurden. In den +Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser +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}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 6 & & & & & & & & & & & & & & & \\ + 10 & 6 & 8 & & & & & & & & & & & & & & \\ + 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\ + 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\ + 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\ + 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\ + 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\ + 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\ + 17 & 6 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\ + 18 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\ + 19 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\ + 20 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\ + 21 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\ + 22 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\ + 23 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\ + 24 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\ +\hline +\oes{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\ +\hline +\end{tabular} + \end{center} + \caption{Anzahl der Schichten der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} + \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 \\ + \rowcolor{green!10} + 30 & 93 & 13 \\ + \rowcolor{green!10!white!95!black} + 31 & 93 & 13 \\ + \rowcolor{green!10} + 32 & 93 & 13 \\ + \rowcolor{green!10!white!95!black} + 33 & 93 & 13 \\ + \rowcolor{green!10} + 34 & 93 & 13 \\ + \rowcolor{green!10!white!95!black} + 35 & 93 & 13 \\ + \rowcolor{green!10} + 36 & 93 & 13 \\ + \rowcolor{green!10!white!95!black} + 37 & 93 & 13 \\ + \rowcolor{green!10} + 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} 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 +$\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 +Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen. + +\begin{figure} + \begin{center} + \input{images/16-ec-from-oes32-cut.tex} + \end{center} + \caption{Visualisierung eines 16-Schnittmusters, das auf + $\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} + +\begin{figure} + \begin{center} + \input{images/16-ec-from-oes32.tex} + \end{center} + \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten. + 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} + +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 +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + \infty & \quad \textrm{falls } i \bmod 4 = 0 \\ + -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\ + ? & \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. + +\begin{figure} + \begin{center} + \input{images/32-ec-from-oes64.tex} + \end{center} + \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten. + Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem + \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.} + \label{fig:32-ec-from-oes64} +\end{figure} + +Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so +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 +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 +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}. + +\begin{figure} + \centering + \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in + 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem + \emph{Odd-Even-Mergesort}-Netzwerk generiert + wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}} + \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten, + das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk + generiert + wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}} + \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das + Ergebnis von der Bewertungsfunktion ab.} + \label{fig:12-ec-from-oes24} +\end{figure} + +\subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk} + +Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene +Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war +(Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise +ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich, +wie und warum es jede beliebige Eingabe sortiert. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 20 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\ + 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\ + 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\ + 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\ + 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\ + 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\ + 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\ + 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\ + 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\ + 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\ + 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\ + 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\ + 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\ +\hline +\ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\ +\hline +\end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des + \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$. + Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede + Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des + Ausgabenetzwerks.} + \label{tbl:ec-ps-speed} +\end{table} + +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. + +\begin{figure} + \begin{center} + \input{images/16-ec-from-ps32.tex} + \end{center} + \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in + 10~Schichten. Das Netzwerk wurde von dem Algorithmus + \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk} + $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.} + \label{fig:16-ec-from-ps32} +\end{figure} + +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 +den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die +strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die +Schichten~1 und~2 sowie 4~und~5 sind vertauscht. + +\begin{figure} + \begin{center} + \input{images/32-pairwise-cut-16-pairwise.tex} + \end{center} + \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu + sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk + bilden.} + \label{fig:ps16-from-ps32} +\end{figure} + +Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach +regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres +schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das +einfache Schnittmuster +\begin{displaymath} +\textit{Eingang}_i = \left\{ \begin{array}{rl} + -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\ + \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\ + ? & \quad \mathrm{sonst} + \end{array} \right. +\end{displaymath} +für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk +$\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der +dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das +verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32} +dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind +diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden +Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den +„richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht +werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende +Netzwerk in schwarz gut zu erkennen. + +\begin{figure} + \begin{center} + \input{images/16-pairwise.tex} + \end{center} + \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten + ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das + resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.} + \label{fig:16-pairwise} +\end{figure} + +Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf +$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein +8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für +größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise +kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} +konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} +untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. + +\newpage \section{Fazit und Ausblick} Mit dem Entfernen von Leitungen aus bekannten Sortiernetzwerken lassen sich