X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=d98d914d73f37a16a0890b632fd5e37a397694b8;hb=d6d4f620236bc7b6ea9fdb368ae83d23b8692d7c;hp=65c583e05e65bf256248b724c7d561ad8a86f099;hpb=d8398b82efd25687be807b29a3c78315d3e31882;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 65c583e..d98d914 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -154,7 +154,7 @@ erhält man ein {\em Komparatornetzwerk}. \begin{center} \input{images/einfaches_komparatornetzwerk.tex} \end{center} -\caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend +\caption{Einfaches Komparatornetzwerk mit vier Ein- beziehungsweise Ausgängen, bestehend aus 5~Komparatoren.} \label{fig:einfaches_komparatornetzwerk} \end{figure} @@ -456,8 +456,8 @@ 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. Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren, -($\mathcal{\Theta}(n \log (n)^2)$), die in weniger Schichten, -($\mathcal{\Theta}(\log (n)^2)$), angeordnet sind. +($\Theta(n \log (n)^2)$), die in weniger Schichten, +($\Theta(\log (n)^2)$), angeordnet sind. Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als @@ -500,7 +500,7 @@ die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass -das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. +das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) beziehungsweise kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein darf. @@ -610,8 +610,8 @@ grün hinterlegt. Das \emph{bitone Mergesort}-Netzwerk mit einer Leitungszahl $n = 2^d$, die eine Zweierpotenz ist, besteht aus $\frac{1}{4} n \log(n) \log(n+1) = -\mathcal{\Theta}\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2} -\log(n) \log(n+1) = \mathcal{\Theta}(\log(n)^2)$ Schichten angeordnet sind. +\Theta\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2} +\log(n) \log(n+1) = \Theta(\log(n)^2)$ Schichten angeordnet sind. \subsection{Das Odd-Even-Mergesort-Netzwerk} @@ -627,7 +627,7 @@ darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist. \subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer} Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein -Komparatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ +Komparatornetzwerk, das zwei sortierte Folgen mit $n$ beziehungsweise $m$ Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer} @@ -668,7 +668,7 @@ geraden Indizes und je eine Liste der ungeraden Indizes. V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right) \end{eqnarray} -Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ +Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$, beziehungsweise die ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden rekursiv von kleineren \emph{Odd-Even}-Mischern zusammengefügt, so dass sich am Ausgang der Mischer die Folgen @@ -697,14 +697,14 @@ Aufbau lauten: einzelnen Komparator. \end{itemize} -Dass die resultierende Folge sortiert ist, lässt sich mit dem -{\em 0-1-Prinzip} zeigen: -Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden -Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder -gleich der Anzahl der Nullen in den ungeraden Teilfolgen -$U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten -sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen -$W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu: +Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass 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 +ungeraden Teilfolgen $U_{\textrm{ungerade}}$ beziehungsweise +$V_{\textrm{ungerade}}$ --~die Einsen verhalten sich entsprechend umgekehrt. +Das trifft demnach auch auf die Folgen $W_{\textrm{gerade}}$ und +$W_{\textrm{ungerade}}$ entsprechend zu: \begin{eqnarray} \left|W_{\textrm{gerade}}\right|_0 &=& \left|U_{\textrm{gerade}}\right|_0 @@ -722,8 +722,8 @@ als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"' Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall, wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält als $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die -Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte -Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind +Ausgabe zu sortieren. Diese wird von den Komparatoren ausgeführt, die +benachbarte Leitungen miteinander vergleichen. Die jeweiligen Situationen sind in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \begin{figure} @@ -744,12 +744,12 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden, bricht die Rekursion nach $\mathcal{O}\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 +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$. Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im -allgemeinen Fall verwendet, ist Gemäß der rekursiven Definition in -Abhängigkeit der Länge der Eingabefolgen, $n$ und $m$: +allgemeinen Fall verwendet, hängt gemäß der rekursiven Definition von der +Länge der Eingabefolgen, $n$ und $m$ ab: \begin{displaymath} K(n,m) = \left\{ \begin{array}{ll} nm, & \mathrm{falls} \quad nm \leqq 1 \\ @@ -762,12 +762,12 @@ 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. -Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$, lässt sich die Anzahl -der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der erste -Rekursionsschritt der OEM-Konstruktion fügt +Für den wichtigen Spezialfall, dass $n = m = 2^{t-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$ Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in -diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer, +diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer $\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots, \frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden @@ -783,8 +783,8 @@ benötigt werden. \subsubsection{Das Odd-Even-Mergesort-Netzwerk} -Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ besteht --~wie -das \emph{bitone Mergesort}-Netzwerk~-- rekursiv aus kleineren Varianten von +Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ besteht, wie +das \emph{bitone Mergesort}-Netzwerk, rekursiv aus kleineren Varianten von sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht @@ -806,24 +806,25 @@ die als leere Komparatornetzwerke definiert sind. \label{fig:odd-even-mergesort-08} \end{figure} -In Abbildung~\ref{fig:odd-even-mergesort-08} ist das konkrete Sortiernetzwerk -$\operatorname{OES}(8)$ zu sehen. Rot markiert sind die beiden rekursiven -Instanzen $\operatorname{OES}(4)$. Die blauen und der grüne Block stellen den -\emph{Odd-Even}-Mischer für acht Leitungen dar: Die beiden blauen Blöcke 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 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden. Im Allgemeinen ist die Anzahl der Komparatoren, die vom \emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der -Definition beziehungsweise der Konstruktionsanleitung abzulesen: +Definition, beziehungsweise der Konstruktionsanleitung abzulesen: \begin{displaymath} k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right) + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right) \end{displaymath} -Eine geschlossene Form dieser Formel ist schon alleine deshalb schwierig, weil -sie für $K(n,m)$ schwierig anzugeben ist. Es ist allerdings bekannt, dass -$k(n)$ in $\mathcal{O}\left(n \left(\log (n)\right)^2\right)$ enthalten ist. +Da es schwierig ist für $K(n,m)$ eine geschlossene Form anzugeben, ist eine +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 Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth @@ -860,14 +861,13 @@ das \emph{Odd-Even-Mergesort}-Netzwerk. Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können gleichzeitig ausgewertet werden, wie bereits in Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche -Transformationen, insbesondere das Entfernen einer Leitung, das in -Abschnitt~\ref{sect:leitungen_entfernen} beschrieben wird, kann es vorkommen, -dass die Komparatoren eines Sortiernetzwerks nicht mehr in der -kleinstmöglichen Anzahl von \emph{Schichten} angeordnet sind. Unter -\emph{Komprimierung} wird eine (Neu-)Gruppierung der Komparatoren verstanden, -die jeden Komparator so früh wie möglich ausführt. So entsteht die -kleinstmögliche Anzahl von \emph{Schichten}, in die sich ein Sortiernetzwerk -unterteilen lässt. +Transformationen, insbesondere das Entfernen einer Leitung wie in +Abschnitt~\ref{sect:leitungen_entfernen} beschrieben, kann es vorkommen, dass +die Komparatoren eines Sortiernetzwerks nicht mehr in der kleinstmöglichen +Anzahl von \emph{Schichten} angeordnet sind. Unter \emph{Komprimierung} wird +eine (Neu-)Gruppierung der Komparatoren verstanden, die jeden Komparator so +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} @@ -897,17 +897,17 @@ der obersten Leitung ausgegeben.} Jedes Sortiernetzwerk kann in eine normaliesierte Variante transformiert werden. Dazu gibt beispielsweise \emph{Donald~E. Knuth} in~\cite{KNUTH} einen Algorithmus an. -Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das \emph{bitone -Mergesort}-Netzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd} +Abbildung~\ref{fig:beispiel_normalisieren} stellt das \emph{bitone +Mergesort}-Netzwerk in zwei Varianten dar. Abbildung~\ref{fig:bitonic-nonstd} zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden -die untere und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei -Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist. -In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven -Definition. +die untere und die obere Hälfte gegenläufig sortiert. Das heißt, dass nach +drei Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert +ist. In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der +rekursiven Definition. In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen -Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche +Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die selbe Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen- und das Trichtermuster zu sehen. @@ -917,7 +917,7 @@ Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen Sortiernetzwerk zusammenzufassen. -Wir haben diese Technik in den vorangegangen Abschnitten bereits verwendet, +Diese Technik wurde in den vorangegangen Abschnitten bereits verwendet, beispielsweise um zwei \emph{bitone Mergesort}-Netzwerke mit jeweils der halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das @@ -925,29 +925,29 @@ einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das und Weise rekursiv aufgebaut. Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte -Folgen. \emph{Wie} diese Folgen sortiert wurden, ist unerheblich. Entsprechend +Folgen. \emph{Wie} diese Folgen sortiert wurden ist unerheblich. Entsprechend können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen -zu sortieren, und die Ausgaben mit einem der beschriebenen Mischer +zu sortieren und die Ausgaben mit einem der beschriebenen Mischer zusammenfügen. -Beispielsweise kann man die Ausgabe von zwei \emph{bitonen -Mergesort-Netzwerken} $\operatorname{BS}(8)$ mit je acht Leitungen mit dem +Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken} +$\operatorname{BS}(8)$ mit je acht Leitungen mit dem \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten -Gesamtfolge zusammenfügen. Das resultierende Sortiernetzwerk besitzt +Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt 80~Komparatoren, $\operatorname{OES}(16)$ nur 63). -Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren) +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. +Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk. Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt -beispielsweise 26~Komparatoren, die in in neun Schichten angeordnet sind. Es -sind allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich +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 -- +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 so schnell wie das Sortiernetzwerk mit +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. @@ -964,25 +964,29 @@ nur mit exponentiellem Aufwand möglich ist. \subsection{Leitungen entfernen} \label{sect:leitungen_entfernen} -Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von -\emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen +Im vorherigen Abschnitt wurde gezeigt, dass es mithilfe von \emph{Mischern} +möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass -sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein -Sortiernetzwerk mit $n$~Eingängen erhalten müssen. +sich die Anzahl der Eingänge nicht verändert. Es soll wieder ein +Sortiernetzwerk mit $n$~Eingängen entstehen. Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung -„eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem +„eliminiert“. Dazu wird angenommen, dass das Minimum oder das Maximum an einem bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und -welche dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum -jeden Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die +welche dafür sorgen, dass der Wert die Leitung wechselt, da das Minimum jeden +Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch das \emph{Odd-Even-Transpositionsort}-Netzwerk. +Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf +dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk +eindeutig festgelegt. + \begin{figure} \centering \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad @@ -996,41 +1000,41 @@ das \emph{Odd-Even-Transpositionsort}-Netzwerk. \caption{Eine Leitung wird aus dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator - am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die restlichen - Werte trotzdem noch richtig sortiert werden müssen, kann dieser Pfad - heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.} + nach unten weiter gegeben wird, ist der Pfad fest vorgegeben. Da die + restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser + Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.} \label{fig:oe-transposition-cut} \end{figure} -Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht +Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht, beziehungsweise ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt haben, werden ersatzlos gelöscht. Diese Komparatoren sind in Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise das Maximum angenommen wird, die an unterster oder oberster Stelle endet und -auf die keine Komparatoren mehr berührt +die keine Komparatoren mehr berührt (Abbildung~\ref{fig:oe-transposition-cut1}). Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen -Komparatornetzwerk immer noch sortiert werden: Wir haben lediglich die -Position des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss -die Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum -liegt. Wir haben nur angefangen, das Sortiernetzwerk unter diese Annahme -auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage +Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die +\emph{Position} des Minimums oder des Maximums in der Eingabe angenommen. Ein +Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher +Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese +Annahme auszuwerten -- über die verbleibenden Eingänge wurde keine Aussage getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste mit $(n-1)$~Elementen darstellen. -Wenn man die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in +Wird die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung -ein Minimum oder ein Maximum angenommen wird, bezeichnen wir das eliminieren -einer Leitung auf diese Art und Weise als \emph{Minimum-Schnitt} -beziehungsweise \emph{Maximum-Schnitt}. +ein Minimum oder ein Maximum angenommen wird, wird das eliminieren einer +Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise +\emph{Maximum-Schnitt} bezeichnet. Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot -markierten Komparatoren wurden verschoben, so dass sich eine kompaktere +markierten Komparatoren sind verschoben, so dass sich eine kompaktere Darstellung ergibt. Außerdem ist das \emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und @@ -1048,10 +1052,9 @@ Der Eliminierungsschritt kann iterativ angewendet werden, um aus einem Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$, $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit -$n$~Eingängen reduziert werden. $k$~Minimum- und Maximum-Schnitte, die -nacheinander angewendet ein $n$-Sortiernetzwerk auf ein -${(n-k)}$-Sortiernetz\-werk reduzieren, bezeichnen wir als -\emph{$k$-Schnittmuster}. +$n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man +die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein +$n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren. Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die @@ -1067,9 +1070,9 @@ ergeben sich insgesamt \quad (n > m) \end{displaymath} \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle -unterschiedlich. Legt man beispielsweise das Minimum auf die unterste Leitung -und das Maximum auf die oberste Leitung eines Standard-Sortiernetzwerks, -führen beide Reihenfolgen zum selben Ergebnis. +unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung +und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks +angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis. \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum @@ -1095,8 +1098,8 @@ Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich. Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner -als die Anzahl der möglichen Schnittmuster. Für jeden Komparator auf der -ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide +als die Anzahl der \emph{möglichen} Schnittmuster. Für jeden Komparator auf +der ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die @@ -1155,10 +1158,10 @@ die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster vernachlässigbar klein ist. Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses -Experiment für größere Sortiernetzwerke leider nicht sinnvoll durchführbar. -Die Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen -Rechnern vorhanden ist, bevor ein entsprechender Graph den linearen Bereich -für „kleine“ x-Werte verlässt. +Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die +Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern +vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für +„kleine“ x-Werte verlässt. Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu können, kann man sich einer stochastischen Methode bedienen, der sogenannten @@ -1280,8 +1283,8 @@ Exploitation}, das Finden (lokaler) Optima, bevorzugt. Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute -Lösungen findet oder sich in \emph{lokalen} Optima verrennt. Leider gibt es -kein Patentrezept für die Wahl der Parameter, so dass für verschiedene +Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt +es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene Leitungszahlen und Mischer-Typen experimentiert werden muss. Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden @@ -1327,12 +1330,12 @@ Pseudocode wie folgt beschreiben: \label{sect:sn-evolution:rekombination} Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu -einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel -den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den -\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), um die -beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen. -Anschließend werden zufällig $n$~Leitungen mit einem $n$-Schnittmuster wie in -Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt. +einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu +einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em +bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der +\emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}), +Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie +in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt. Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das @@ -1400,17 +1403,18 @@ leider mit keiner Leitungszahl erreicht. \label{fig:16-e1-oddeven-1296543330} \end{figure} -Leider lies sich das Ergebnis des bitonen Mischers -- die von -\textsc{SN-Evolution} ausgegebenen Netzwerke waren effizienter als das -rekursiv aus dem verwendeten Mischer aufgebaute Sortiernetzwerk -- mit dem -\emph{Odd-Even-Merge}-Netzwerk nicht wiederholen. Zwar erreichen die -Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des -\emph{Odd-Even}-Mischers findet, das \emph{Odd-Even-Mergesort}-Netzwerk -bezüglich Geschwindigkeit und Effizienz, ein Beispiel hierfür ist in -Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Sortiernetzwerkde, die -effizienter als $\operatorname{OES}(n)$ sind, konnten leider nicht beobachtet -werden. Wenn $n$ keine Zweietpotenz ist, kann \textsc{SN-Evolution} unter -Umständen Sortiernetzwerke ausgeben, die schneller als \oes{n} sind. +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 +\emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind. +Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht +wiederholen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung +des \emph{Odd-Even}-Mischers 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. Wenn $n$ keine +Zweierpotenz ist, kann \textsc{SN-Evolution} unter Umständen Sortiernetzwerke +ausgeben, die schneller als \oes{n} sind. %\begin{figure} %\begin{center} @@ -1570,9 +1574,9 @@ 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 bitonen Mergesort-Netzwerks -leicht invertieren lassen, werden der Fall, dass es mehr Minimumschnitte, und -der Fall, dass es mehr Maximumschnitte gibt, nicht unterschieden. +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 @@ -1639,7 +1643,7 @@ 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, dass die gleiche +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. @@ -1674,7 +1678,7 @@ Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \end{figure} Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach -regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk einen kleineres +regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das einfache Schnittmuster \begin{displaymath} @@ -1802,8 +1806,8 @@ 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 heißt, dass das resultierende Netzwerk zwar nicht so -effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12} ist. +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