X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=0e86f73cf73a412635109265a1ce57013732c1d7;hb=0d8ad84d3a94cc18581337be5177f4319b7502b8;hp=3e575d5edf858fbe3d0a3d47c7c7136354e991f8;hpb=3eeccd372c2ac49d843e25614caed88fa870e74e;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 3e575d5..0e86f73 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,26 +260,33 @@ 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 -$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, -ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$ -verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein -schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen, -ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt, -sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für -aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung -eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa -4,3~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten -beschäftigen. +zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als +$a_i$, beziehungsweise zwei Zahlen größer oder gleich $a_i$. Da im Fall der +0-1-Folge zwei gleiche Zahlen am Komparator anliegen, dürfen wir davon +ausgehen, dass sich der Komparator so verhält, wie er sich bei der Permutation +verhalten hat -- ohne das Ergebnis zu beeinflussen. Entsprechend müssen an den +Ausgängen $i-1$ und $i$ eine Null und eine Eins in der falschen Reihenfolge +ankommen. Das steht im Widerspruch zu der Annahme, dass alle 0-1-Folgen +sortiert werden. + +Im Gegensatz zum Überprüfen aller möglichen Permutationen, was mit dem Aufwand +$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ verbunden ist, besitzt +das Überprüfen aller 0-1-Folgen „nur“ den Aufwand $\Theta(2^n)$. Entsprechend +ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist +bisher allerdings nicht bekannt. + +Um zu überprüfen, ob ein Komparatornetzwerk mit 16~Leitungen die +Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig +-- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt. +Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch +bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus +mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im +Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende +Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines +Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million +Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung +auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden +für einen Lauf benötigt. \subsubsection{Evolutionäre Algorithmen} @@ -947,16 +954,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 @@ -2241,6 +2248,21 @@ Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt. +Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim +\emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die +Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war +jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere +Geschwindigkeit zu erreichen. + +In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von +\textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots +19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles +19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die +resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit +$k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des +\emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in +13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht. + \begin{table} \begin{center} \rowcolors{2}{black!5}{} @@ -2278,17 +2300,57 @@ Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt. \label{tbl:ec-oes-speed} \end{table} +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|r|r|} + \hline + $n$ & Komp. & Schichten \\ + \hline + 20 & 91 & 14 \\ + 21 & 91 & 14 \\ + 22 & 91 & 14 \\ + 23 & 91 & 14 \\ + 24 & 91 & 14 \\ + 25 & 91 & 14 \\ + 26 & 91 & 14 \\ + 27 & 91 & 14 \\ + 28 & 91 & 14 \\ + 29 & 95 & 13 \\ + 30 & 93 & 13 \\ + 31 & 93 & 13 \\ + 32 & 93 & 13 \\ + 33 & 93 & 13 \\ + 34 & 93 & 13 \\ + 35 & 93 & 13 \\ + 36 & 93 & 13 \\ + 37 & 93 & 13 \\ + 38 & 93 & 13 \\ + \hline + \bs{19} & 98 & 14 \\ + \oes{19} & 91 & 14 \\ + \hline + \end{tabular} + \end{center} + \caption{Komparatoren und Schichten von Sortiernetzwerken, die von + \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$ + ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die + Effizienz von 91~Komparatoren nicht mehr erreichbar.} + \label{tbl:ec-oes-19} +\end{table} + In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie -viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke -$\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$ -besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das -\emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen -16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es -wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit -$\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese -Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine -Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes -16-Schnittmuster findet. +viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten +Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und +$\operatorname{PS}(32)$ besitzen. Eines der Ergebnisse war, dass von diesen +Sortiernetzwerken das \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten +unterschiedlichen 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. +Entsprechend ist es wenig verwunderlich, dass \textsc{SN-Evolution-Cut} +gestartet mit $\operatorname{OES}(32)$ sehr schnell\footnote{Ein +entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen +geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe +Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf +derzeitigen Computern.} ein gutes 16-Schnittmuster findet. Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist