erhält man ein {\em Komparatornetzwerk}.
\begin{figure}
-\begin{center}
-\input{images/einfaches_komparatornetzwerk.tex}
-\end{center}
-\caption{Einfaches Komparatornetzwerk mit vier Ein- beziehungsweise Ausgängen, bestehend
-aus 5~Komparatoren.}
-\label{fig:einfaches_komparatornetzwerk}
+ \begin{center}
+ \input{images/einfaches_komparatornetzwerk.tex}
+ \end{center}
+ \caption{Einfaches Komparatornetzwerk mit 4~Ein- beziehungsweise Ausgängen,
+ bestehend aus 5~Komparatoren.}
+ \label{fig:einfaches_komparatornetzwerk}
\end{figure}
Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
\begin{center}
\input{images/09-e2-c24-allbut1.tex}
\end{center}
- \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
- 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
- alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
+ \caption{Ein \emph{Komparatornetzwerk} mit 9~Eingängen und 24~Komparatoren,
+ die in 8~Schichten angeordnet sind. Das Netzwerk sortiert alle Eingaben, bei
+ denen das Minimum nicht auf dem mittleren Eingang liegt.}
\label{fig:09-e2-c24-allbut1}
\end{figure}
Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
-über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
-Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
+so schnell, dass ein Ausprobieren aller möglichen Permutationen schon bei
+16~Leitungen praktisch nicht mehr zu bewerkstelligen
ist.\footnote{1.307.674.368.000 Permutationen}
\label{sect:0-1-prinzip}
Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
-zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$
-oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei
-gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich
-der Komparator so verhält, wie er sich bei der Permutation verhalten hat --
-ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$
-und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im
-Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.
-
-Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
-Komplexitätsklasse
-$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
-ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$
-verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
-schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
-ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
-sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
-aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
-eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
-4,3~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
-beschäftigen.
+zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als
+$a_i$, beziehungsweise zwei Zahlen größer oder gleich $a_i$. Da im Fall der
+0-1-Folge zwei gleiche Zahlen am Komparator anliegen, dürfen wir davon
+ausgehen, dass sich der Komparator so verhält, wie er sich bei der Permutation
+verhalten hat -- ohne das Ergebnis zu beeinflussen. Entsprechend müssen an den
+Ausgängen $i-1$ und $i$ eine Null und eine Eins in der falschen Reihenfolge
+ankommen. Das steht im Widerspruch zu der Annahme, dass alle 0-1-Folgen
+sortiert werden.
+
+Im Gegensatz zum Überprüfen aller möglichen Permutationen, was mit dem Aufwand
+$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ verbunden ist, besitzt
+das Überprüfen aller 0-1-Folgen „nur“ den Aufwand $\Theta(2^n)$. Entsprechend
+ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist
+bisher allerdings nicht bekannt.
+
+Um zu überprüfen, ob ein Komparatornetzwerk mit 16~Leitungen die
+Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig
+-- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt.
+Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch
+bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus
+mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
+Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
+Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
+Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
+Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
+für einen Lauf benötigt.
\subsubsection{Evolutionäre Algorithmen}
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
%\end{figure}
\newpage
-\section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
+\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:bewertung}. Mit diesem
-Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
-gute Schnittmuster gesucht.
+von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
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}
Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
-Tabelle~\ref{tbl:ec-bs-speed} sind die Schichten, die die Ergebnisse von
-\textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren, aufgelistet.
-Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n}, jede Spalte
-enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die Zellen
-enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
+Tabelle~\ref{tbl:ec-bs-speed} ist die Anzahl der Schichten, die die Ergebnisse
+von \textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren,
+aufgelistet. Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n},
+jede Spalte enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die
+Zellen enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
\begin{table}
\begin{center}
beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.
+Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim
+\emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die
+Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war
+jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere
+Geschwindigkeit zu erreichen.
+
+In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von
+\textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots
+19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles
+19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die
+resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit
+$k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des
+\emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in
+13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht.
+
\begin{table}
\begin{center}
\rowcolors{2}{black!5}{}
\label{tbl:ec-oes-speed}
\end{table}
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $n$ & Komp. & Schichten \\
+ \hline
+ 20 & 91 & 14 \\
+ 21 & 91 & 14 \\
+ 22 & 91 & 14 \\
+ 23 & 91 & 14 \\
+ 24 & 91 & 14 \\
+ 25 & 91 & 14 \\
+ 26 & 91 & 14 \\
+ 27 & 91 & 14 \\
+ 28 & 91 & 14 \\
+ 29 & 95 & 13 \\
+ 30 & 93 & 13 \\
+ 31 & 93 & 13 \\
+ 32 & 93 & 13 \\
+ 33 & 93 & 13 \\
+ 34 & 93 & 13 \\
+ 35 & 93 & 13 \\
+ 36 & 93 & 13 \\
+ 37 & 93 & 13 \\
+ 38 & 93 & 13 \\
+ \hline
+ \bs{19} & 98 & 14 \\
+ \oes{19} & 91 & 14 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Komparatoren und Schichten von Sortiernetzwerken, die von
+ \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$
+ ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die
+ Effizienz von 91~Komparatoren nicht mehr erreichbar.}
+ \label{tbl:ec-oes-19}
+\end{table}
+
In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
-viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
-$\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$
-besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das
-\emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen
-16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es
-wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
-$\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese
-Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine
-Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes
-16-Schnittmuster findet.
+viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
+Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und
+$\operatorname{PS}(32)$ besitzen. Eines der Ergebnisse war, dass von diesen
+Sortiernetzwerken das \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten
+unterschiedlichen 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen.
+Entsprechend ist es wenig verwunderlich, dass \textsc{SN-Evolution-Cut}
+gestartet mit $\operatorname{OES}(32)$ sehr schnell\footnote{Ein
+entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen
+geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe
+Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf
+derzeitigen Computern.} ein gutes 16-Schnittmuster findet.
Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
\input{images/16-ec-from-oes32-cut.tex}
\end{center}
\caption{Visualisierung eines 16-Schnittmusters, das auf
- $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes
- Sortiernetzwerk ergibt.}
+ $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
+ bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
+ resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
+ dargestellt.}
\label{fig:16-ec-from-oes32-cut}
\end{figure}
\input{images/16-ec-from-oes32.tex}
\end{center}
\caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
- Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem
- \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(32)$ durch
- 16~Schnitte erzeugt.}
+ Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
+ einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
+ berechnet wurde. Das Schnittmuster ist in
+ Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
\label{fig:16-ec-from-oes32}
\end{figure}
projects / diplomarbeit.git / blobdiff