1 \documentclass[a4paper,10pt]{article}
2 \usepackage[utf8]{inputenc}
6 \usepackage{amsmath, bbm}
12 %\usepackage{longtable}
13 \usepackage{subfigure}
17 \usetikzlibrary{arrows,shapes}
20 \usepackage{mathtools}
22 \geometry{paper=a4paper,margin=25mm}
26 %\fancyhead[LO,LE]{"Ubung zu Computational Intelligence}
27 %\fancyhead[CO,CE]{2006-05-15}
28 %\fancyhead[RO,RE]{Florian Forster (2099894)}
30 \title{Evolutionäre Optimierung von Sortiernetzwerken}
31 \author{Florian Forster}
34 \newcommand{\false}{\textsc{False}}
35 \newcommand{\true}{\textsc{True}}
36 \newcommand{\todo}[1]{{\bf TODO:} #1}
37 \newcommand{\qed}{\hfill $\Box$ \par \bigskip}
39 \newtheorem{definition}{Definition}
40 \newtheorem{satz}{Satz}
42 % Zeige Nummern nur bei referenzierten Gleichungen an.
43 \mathtoolsset{showonlyrefs=true}
47 \tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt]
48 \tikzstyle{comp} = [draw,thick,-]
49 \tikzstyle{compup} = [draw,thick,->]
50 \tikzstyle{compdown} = [draw,thick,<-]
51 \tikzstyle{edge} = [draw,thick,-]
52 \tikzstyle{diredge} = [draw,thick,->]
53 \tikzstyle{prob} = [font=\tiny]
55 \tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
56 \tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
57 \tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
58 \tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
62 Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
63 vorgestellt (Off-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
64 Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
65 Evolutionäre Algorithmen werden beschrieben und ein evolutionärer
66 Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben.
67 Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die
68 Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich
69 das hinbekomme bzw. Recht behalte.}
76 \section{Motivation und Einleitung}
78 \subsection{Motivation}\label{sect:motivation}
81 \item Sortiernetzwerke sind toll, weil $\ldots$
82 \item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
83 \item Bisher noch kein evolutionärer Algorithmus zur automatischen
84 Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
87 \subsection{Einleitung}\label{sect:einleitung}
89 \subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
91 {\em Komparatoren} sind die Bausteine, die {\em Sortiernetzwerken} zugrunde
92 liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten können.
93 Ausserdem besitzt ein {\em Komparator} zwei Ausgänge, die im Gegensatz zu den
94 Eingängen unterscheidbar sind: Die grö"sere der beiden Zahlen wird immer auf
95 dem einen, die kleinere der beiden Zahlen immer auf dem anderen Ausgang
98 Wenn man nun mehrere {\em Komparatoren} miteinander kombiniert, also die
99 Ausgänge von {\em Komparatoren} mit dem Eingängen anderer {\em Komparatoren}
100 verbindet, erhält man ein {\em Komparatornetzwerk}.
104 \input{images/einfaches_komparatornetzwerk.tex}
106 \caption{Einfaches Komparatornetzwerk mit vier Ein- bzw. Ausgängen, bestehend
108 \label{fig:einfaches_komparatornetzwerk}
111 Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
112 Komparatornetzwerk aus fünf Komparatoren in der üblichen Darstellungsweise:
113 Die horizontalen Linien stellen Leitungen von den Eingängen auf der linken
114 Seite zu den Ausgängen auf er rechten Seite dar. Die vertikalen Pfeile
115 symbolisieren die Komparatoren, die die Werte "`auf den Leitungen"'
116 vergleichen und ggf. vertauschen. Nach einem Komparator befindet sich die
117 kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
118 befindet sich auf der Leitung auf der der Pfeil seinen Ursprung hat.
120 Komparatornetzwerke, die für jede beliebige Eingabepermutation eine
121 Ausgabe erzeugen, die der Sortierung der Eingabe entspricht, heißen
122 {\em Sortiernetzwerke}. Das in
123 Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
124 ist kein Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ würde zur Ausgabe
125 ${(2, 1, 3, 4)}$ führen -- die bestehenden Sortierung wird also sogar
128 Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft
129 {\em nicht} hat, ist mit einem gegebenen Gegenbeispiel also einfach möglich.
130 Dieses Gegenbeispiel zu finden ist allerdings aufwendig.
132 \todo{Wie findet man die Gegenbeispiele? Die {\em Entscheidung}, ob ein
133 Netzwerk sortiert, ist doch NP-vollständig, also müsste doch das Finden eines
134 Gegenbeispiels im Allgemeinen auch exponentialle Laufzeit haben..?}
135 \todo{Wenn die {\em Entscheidung}, ob ein Netzwerk sortiert, NP-vollständig
136 ist, müsse man dann nicht einen Zeugen für die Sortiereigenschaft angeben
141 Um zu überprüfen, ob ein gegebenes Komparatornetzwerk die Sortiereigenschaft
142 besetzt, müssen nicht alle $n!$ Permutationen von $n$~unterschiedlichen Zahlen
143 ausprobieren. Stattdessen reicht es zu überprüfen, dass das Netzwerk alle
144 $2^n$~${0-1}$-Folgen sortiert.
148 \item Ein Komparator-Netzwerk ist $\ldots$
149 \item Ein Komparator-Netzwerk ist ein Sortiernetzwerk, wenn $\ldots$
150 \item Die Frage nach der Sortiereigenschaft ist NP-vollständig.
153 \subsubsection{Evolutionäre Algorithmen}
155 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
156 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
157 $NP$, sind also mit bekannten Verfahren nicht effizient exakt lösbar. Sollte
158 sich herausstellen, dass diese Probleme nicht in der Komplexitätsklasse $P$
159 liegen, wäre eine Konsequenz, dass es effiziente exakte Algorithmen für diese
160 Probleme nicht geben kann. Falls sich hingegen herausstellt, dass diese
161 Probleme in der Komplexitätsklasse~$P$ liegen, wird es mit großer
162 Wahrscheinlichkeit noch einige Zeit dauern bis auch Algorithmen mit
163 praktikablen Zeitkonstanten gefunden werden.
165 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
166 die bzw. eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus
167 zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele dieser
168 Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur,
169 beispielsweise immitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen
170 auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen.
172 Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee
173 ist es, bestehende Lösungen zu neuen, unter Umständen besseren Lösungen zu
174 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
175 Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem häufig
176 als {\em Individuum} bezeichnet.
178 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben. Aus einer
179 bestehenden Lösungsmenge, der {\em Population} werden zufällig Lösungen
180 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
181 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
182 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
183 integriert wird. Die Wahrscheinlichkeiten, beispielsweise bei der {\em
184 Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
185 werden bessere Lösungen bevorzugt. Zur Bewertung die die sogenannte {\em
188 Nicht alle Probleme eignen sich für diese Strategie: Zum einen muss es möglich
189 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
190 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
191 es oft einfach ist {\em irgendeine} Lösung anzugeben. Zum anderen muss eine
192 Methode für die Rekombination existieren. Das insbesondere dann problematisch
193 wenn {\em Nebenbedingungen} eingehalten werden müssen.
196 \item Unter einem "`Evolutionären Algorithmus"' versteht man $\ldots$
197 \item Da die Sortiereigenschaft zu überprüfen NP-schwer ist, ist die
198 Mutation \textit{(vermutlich)} nicht (effizient) möglich.
201 \section{Bekannte konstruktive Sortiernetzwerke}
203 Übersicht über bekannte konstruktive Sortiernetzwerke.
205 \subsection{Odd-Even-Transpositionsort}
206 \label{sect:odd_even_transpositionsort}
208 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
209 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
210 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
211 Abbildung~\ref{fig:odd_even_transposition_08} zeigt das OET-Netzwerk für
216 \input{images/oe-transposition-8.tex}
218 \caption{Das {\em Odd-Even-Transpositionsort} Netzwerk für acht Eingänge.}
219 \label{fig:odd_even_transposition_08}
222 \subsection{Batcher's Mergesort}
224 Ein Netzwerk von K.~E.~Batcher. Siehe:
225 K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring
226 Joint Comput. Conf., Vol. 32, 307-314 (1968)
229 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
231 Das Netzwerk basiert auf dem {\em bitonen Mischer}, einem Komparator-Netzwerk,
232 das eine beliebige bitone Folge in eine sortierte Listen umordnen kann. Eine
233 {\em bitone Folge} ist eine monoton steigende Folge gefolgt von einer monoton
234 fallenden Folge, oder ein zyklischer Shift davon.
235 Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinipiellen Möglichkeiten
236 die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für
237 Batcher's Mergesort-Netzwerk zeigen die Abbildungen~\ref{fig:beispiel-biton-0}
238 und~\ref{fig:beispiel-biton-1}. Sie erhält man, wenn man eine aufsteigend und
239 eine absteigend sortierte Liste aneinanderhängt. Bei den
240 anderen beiden Formen ist wichtig zu beachten, dass das letzte Element nicht
241 größer (Abbildung~\ref{fig:beispiel-biton-2}) bzw. kleiner
242 (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge sein
247 \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
248 \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
249 \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
250 \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
251 \caption{Beispiele bitoner Folgen.}
252 \label{fig:beispiel-biton}
257 \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
259 \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
260 \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
261 aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
262 der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
263 resultierenden Teilfolgen sind wiederum biton.}
264 \label{fig:bitonic-merge-schema}
267 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
268 ${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
269 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
270 sortiert, die Folge $V$ sei absteigend sortiert:
272 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
273 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
275 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
276 Positionen verglichen und ggf. vertauscht:
278 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
280 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
281 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
282 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
283 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
284 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
285 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
286 "`linken"' Folge, $u_{m-1}$, kleiner ist als das kleinste Element der
287 "`rechten"' Folge, $v_{m-1}$. Daraus folgt, dass die entstehende Folge aus
288 zwei bitonen Folgen besteht, die rekursiv zusammengeführt werden können.
289 Abbildung~\ref{fig:bitonic-merge-normal} zeigt die Situationen vor und nach
290 diesem Schritt des Mischers.
292 Mit dem bitonen Mischer auch zwei aufsteigend sortierte Folgen sortiert
293 werden. Dazu ist lediglich das "`Umbenennen"' der Leitungen notwendig.
294 Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das Schema des bitonen
295 Mischers für zwei aufsteigend sortierte Foglen. Durch das Umbenennen verändert
296 sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das
297 Muster nun an einen Trichter.
299 \subsubsection{Batcher's Bitonic-Mergesort-Netzwerk}
301 Das Sortiernetzwerk $S(n)$ mit $n$~Eingängen besteht aus zwei Instanzen von
302 $S(\frac{n}{2})$, dem Netzwerk mit $\frac{n}{2}$~Eingängen und dem bitonen
303 Mischer~$M(n)$. Die Rekursion bricht bei ${n = 1}$~ab --~eine einelementige
304 Liste ist immer sortiert.
305 Das konkrete Netzwerk~$S(8)$ ist in Abbildung~\ref{fig:batcher_08} zu sehen.
306 Eingezeichnet sind ebenfalls die beiden Instanzen des Netzwerks~$S(4)$ (rot)
307 sowie der bitone Mischer~$M(8)$ (blau).
313 %\includegraphics[viewport=115 491 372 782,width=7.5cm]{images/sn-rekursiver-aufbau.pdf}
315 %\caption{Rekursiver Aufbau von $S(n)$: Es besteht aus zwei Instanzen von
316 %$S(n/2)$ und dem Mischer $M(n)$.}
317 %\label{fig:bms_rekursiver_aufbau}
322 \input{images/batcher-8.tex}
324 \caption{$S(8)$, Batcher's {\em bitone Mergesort-Netzwerk} für acht
325 Eingänge. Markiert sind die beiden Instanzen von $S(4)$ (rot), die beiden
326 bitonen Mischer~$M(4)$ (blau) und die Komparatoren, die im letzten rekursiven
327 Schritt hinzugefügt wurden (grün).}
328 \label{fig:batcher_08}
331 \subsection{Odd-Even-Mergesort}
333 Obwohl der Name ähnlich klingt, haben {\em Odd-Even-Mergesort} (OEM) und
334 {\em Odd-Even-Transpositionsort} (OET, siehe
335 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Auch dieses
336 Netzwerk ist von K.~Batcher gefunden worden und wird rekursiv durch einen
337 "`Mischer"' definiert.
339 \subsubsection{Der Odd-Even-Mischer}\label{sect:der_odd_even_mischer}
341 Der {\em Odd-Even-Mischer} ist ein Komperatornetzwerk, dass zwei sortierte
342 Folgen zu einer sortierten Ausgabe zusammenfügen kann. Dabei kommt es mit
343 weniger Vergleichen aus als der {\em bitone Mischer}, der im
344 Abschnitt~\ref{sect:der_bitone_mischer} vorgestellt wurde.
346 Der {\em Odd-Even-Mischer} selbst ist ebenfalls rekursiv aufgebaut: Die
347 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
348 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
349 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
350 $W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
352 w_i = \left\{ \begin{array}{ll}
361 \input{images/oe-merge.tex}
363 \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum
364 bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger
365 aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.}
369 Diese werden jetzt in insgesamt vier sortierte Folgen aufgeteilt, je eine
370 Liste der geraden Indizes und je eine Liste der ungeraden Indizes.
372 U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
373 U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
374 V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
375 V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
378 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$ bzw. die
379 ungeraden Folgen $U_{\textrm{ungerade}}$ und $V_{\textrm{ungerade}}$ werden
380 rekursiv von kleineren {\em Odd-Even-Mischern} zusammengefügt, so dass sich am
381 Ausgang der Mischer die Folgen
383 W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
384 W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
388 Anschließend werden die Komparatoren zwischen benachbarten Leitungen
391 w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
393 die die Folge~$W$ sortieren. Den schematischen Aufbau des {\em
394 Odd-Even-Mischers} zeigt Abbildung~\ref{fig:oe-merge}.
396 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
397 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
398 entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
399 offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
402 \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
403 \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
404 einzelnen Komparator.
407 Dass die resultierende Folge sortiert ist, lässt sich mit dem
408 {\em 0-1-Prinzip} leicht zeigen:
409 Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den geraden
410 Teilfolgen, $U_{\textrm{gerade}}$ bzw. $V_{\textrm{gerade}}$, größer oder
411 gleich der Anzahl der Nullen in den ungeraden Teilfolgen
412 $U_{\textrm{ungerade}}$ bzw. $V_{\textrm{ungerade}}$ --~die Einsen verhalten
413 sich entsprechend umgekehrt. Das trifft demnach auch auf die Folgen
414 $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu:
416 \left|W_{\textrm{gerade}}\right|_0
417 &=& \left|U_{\textrm{gerade}}\right|_0
418 + \left|V_{\textrm{gerade}}\right|_0
419 = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
420 + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
421 \left|W_{\textrm{ungerade}}\right|_0
422 &=& \left|U_{\textrm{ungerade}}\right|_0
423 + \left|V_{\textrm{ungerade}}\right|_0
424 = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
425 + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
427 Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
428 als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
429 Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
430 wenn $W_{\textrm{gerade}}$ $2$~Nullen mehr enthählt als
431 $W_{\textrm{ungerade}}$, muss eine Vertauschung stattfinden, um die Ausgabe zu
432 sortieren. Die jeweiligen Situationen sind in
433 Abbildung~\ref{fig:oe-post-recursive} dargestellt.
437 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
439 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
441 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
442 \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
443 kleineren {\em Odd-Even-Mischer} entstehen können. Ist die Differenz der
444 Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
445 letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
447 \label{fig:oe-post-recursive}
450 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
452 Auch beim \emph{Odd-Even-Mergesort-Netzwerk} --~wie beim \emph{bitonen
453 Mergesort-Netzwerk}~-- entsteht das Sortiernetzwerk aus dem {\em
454 Odd-Even-Mischer} durch rekursives Anwenden auf einen Teil der Eingabe
455 (üblicherweise die Hälfte der Leitungen) und anschließendes zusammenfügen.
456 Abbildung~\ref{fig:odd_even_mergesort_08} zeigt das Netzwerk für $8$~Eingänge.
460 \input{images/oe-mergesort-8.tex}
462 \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge.}
463 \label{fig:odd_even_mergesort_08}
467 \item Odd-Even-Transpositionsort
468 \item Bitonic-Mergesort
469 \item Odd-Even-Mergesort
470 \item Pairwise sorting-network
473 \section{Transformation von Sortiernetzwerken}
475 \subsection{Komprimieren}
477 \todo{Aus theoretischer Sicht eigentlich eine Trivialität. Rausschmeißen?}
479 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
480 gleichzeitig ausgewertet werden, wie bereits in
481 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Unter
482 \emph{Komprimieren} wird eine (Neu-)Gruppierung in die kleinstmögliche Anzahl
483 von \emph{Schichten} verstanden.
485 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
486 Komparatornetzwerken interessant. \dots
488 \subsection{Normalisieren}
492 \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
493 \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
494 \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
495 transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
496 intuitiven Konstruktion und die normalisierte Variante.}
497 \label{fig:beispiel_normalisieren}
500 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
501 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
502 zeigen. Jedes Sortiernetzwerk kann in eine normaliesierte Variante
503 transformiert werden. Dazu gibt beispielsweise \emph{Knuth} (\todo{Verweis})
504 einen Algorithmus an.
506 Abbildung~\ref{fig:beispiel_normalisieren} zeigt das das
507 bitone Sortiernetzwerk in zwei Varianten. Abbildung~\ref{fig:bitonic-nonstd}
508 zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
509 Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
510 die unter und die obere Hälfte gegenläufig sortiert. Das heißt dass nach drei
511 Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert ist.
512 In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der rekursiven
515 In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
516 Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche
519 \subsection{Zwei Netzwerke kombinieren}
522 \item Mit dem Bitonic-Merge
523 \item Mit dem Odd-Even-Merge
524 \item Nach dem Pairwise sorting-network Schema.
527 \subsection{Leitungen entfernen}\label{sect:leitungen_entfernen}
529 Im vorherigen Abschnitt haben wir gesehen, dass es mithilfe von
530 \emph{Mischern} möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
531 ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
532 beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
533 sich die Anzahl der Eingänge nicht verändert. Das heißt, dass wir wieder ein
534 Sortiernetzwerk mit $n$~Eingängen erhalten müssen.
536 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
537 Sortiernetzwerk mit $(n-1)$~Leitungen verkleinern, indem man eine Leitung
538 „eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem
539 bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim
540 durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der
541 „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index.
542 Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche
543 dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden
544 Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
545 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
546 das {\em Odd-Even-Transpositionsort-Netzwerk}.
550 \subfigure[foo]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
551 \subfigure[bar]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
552 \subfigure[baz]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
553 \subfigure[qux]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
554 \caption{Eine Leitung wird aus dem {\em Odd-Even-Transpositionsort} Netzwerk
555 $\textrm{OET}(8)$ entfernt: Auf der rot markierten Leitung wird $\infty$
556 angelegt. Da der Wert bei jedem Komparator am unteren Ende herauskommt, ist
557 der Pfad fest vorgegeben. Da die restlichen Werte trotzdem noch richtig
558 sortiert werden müssen, kann dieser Pfad herausgetrennt werden. In der
559 letzten Abbildung ist $\textrm{OET}(7)$ markiert.}
562 Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht bzw.
563 ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der Leitung geführt
564 haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
565 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
566 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
567 ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
568 das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
569 auf die keine Komparatoren mehr berührt
570 (Abbildung~\ref{fig:oe-transposition-cut1}).
572 Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
573 Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position
574 des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die
575 Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt.
576 Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme
577 auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage
578 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
579 mit $(n-1)$~Elementen darstellen.
581 Wenn wir die Minimum- beziehungsweise Maximum-Leitung entfernen
582 (Abbildung~\ref{fig:oe-transposition-cut2}), bleibt das Sortiernetzwerk für
583 $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung ein Minimum oder ein
584 Maximum angenommen wird, bezeichnen wir das eliminieren einer Leitung als
585 \emph{Minimum-Schnitt} beziehungsweise \emph{Maximum-Schnitt}.
587 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
588 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
589 markierten Komparatoren wurden verschoben, so dass sich eine kompaktere
590 Darstellung ergibt. Ausserdem ist das
591 {\em Odd-Even-Transpositionsort-Netzwerk} für sieben Werte markiert. Der
592 zusätzliche Komparator vor dem $\textrm{OET}(7)$ hat keinen Einfluss auf die
593 Ausgabe und kann entfernt werden.
595 Der Eliminierungsschritt kann iterativ angewandt werden, um aus einem
596 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
597 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können wir auf diese Art und
598 Weise einen Sortiernetzwerk mit $2n$~Eingängen wieder auf ein Sortiernetzwerk
599 mit $n$~Eingängen reduzieren.
601 Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
602 Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
603 auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
604 ein $n$-Sortiernetzwerk auf ein $m$-Sortiernetzwerk zu reduzieren, ergeben
607 \prod_{i=n}^{m+1} 2i = 2^{n-m} \frac{n!}{m!}
610 Möglichkeiten. Diese Möglichkeiten sind nicht alle unterschiedlich. Legt man
611 beispielsweise das Minimum auf die unterste Leitung und das Maximum auf die
612 oberste Leitung eines Standard-Sortiernetzwerks, führen beide Reihenfolgen zum
615 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit (\todo{Referenz}), dass
616 es möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise
617 Maximum vorzubelegen. Dadurch wird die Anzahl der möglichen Schnitte
618 reduziert, die Menge der erreichbaren Sortiernetzwerke bleibt aber
619 unverändert. Die Anzahl der möglichen „Schnittmuster“ setzt sich zusammen aus
620 der Anzahl von Möglichkeiten, $n-m$~Leitungen aus $n$ Leitungen auszuwählen,
621 und die möglichen Minimum-~/ Maximum-Muster. Damit ergibt sich folgende
624 2^{n-m} \cdot \left( \begin{array}{c} n \\ n-m \end{array} \right)
625 = 2^{n-m} \cdot \frac{n!}{(n-m)! m!}
626 = 2^{n-m} \cdot \frac{n!}{m!} \cdot \frac{1}{(n-m)!}
630 Die Anzahl der möglichen Schnitte wird mit der Anzahl der zu entfernenden
631 Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
632 ein Sortiernetzwerk mit 16~Eingängen zu reduzieren sind 16~Schnitte notwendig,
633 für die es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein
634 Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter
635 erheblichem Ressourcenaufwand möglich.
637 Das Programm {\sc SN-Evolution-Cut} implementiert einen evolutionären
638 Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
639 Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
640 möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
641 von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
644 \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort.
645 \item Wie gut kann man durch wegschneiden werden?
646 \item Wieviele Schnitte ergeben das selbe Netzwerk?
649 \section{Der evolutionäre Ansatz}
651 Um einen evolutionären Algorithmus für Sortiernetzwerke zu entwickeln, werden
652 die vorgestellten Methoden kombiniert.
654 \subsection{Bewertungsfunktion}\label{sect:bewertung}
656 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
657 {\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele,
658 die interessant sind:
660 \item Möglichst wenige Komparatoren ("`klein"')
661 \item Möglichst wenige Schichten ("`schnell"')
664 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
665 kleinste bekannte Sortiernetzwerk für 16~Eingänge besteht aus 60~Komparatoren
666 in 10~Schichten. Das schnellste Netzwerk besteht aus 61~Komparatoren in nur
669 Eine Gütefunktion, die die beiden Ziele "`klein"' und "`schnell"'
670 berücksichtigen kann, hat die folgende allgemeine Form:
672 \mathit{Guete}(S) = w_{\mathrm{Basis}}
673 + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
674 + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
676 Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
677 dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
678 gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
679 Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
680 jegliche Ergebnisse sind dann rein zufälliger Natur.
682 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
683 genommen werden. Ist er groß, wird der relative Unterschied der Güten
684 verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
685 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
686 klein, in Abhängigkeit von den anderen beiden Parametern sind auch negative
687 Werte möglich, werden die relativen Unterschiede groß. Dadurch wird die {\em
688 Exploitation}, das Finden lokaler Optima, bevorzugt.
690 \subsection{Selektion}
694 \subsection{Rekombination}
696 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
697 einer neuen Lösung kombiniert. Dazu verwenden wir einen Mischer, zum Beispiel
698 den {\em bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) oder den
699 {\em Odd-Even-Mischer} (Abschnitt~\ref{sect:der_odd_even_mischer}), um die
700 beiden Netzwerke zu einem Netzwerk mit $2n$~Leitungen zusammenzufügen.
701 Anschließend entfernen wir zufällig $n$~Leitungen wie in
702 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
704 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
707 \subsection{Mutation}
709 Zu einem vollständigen evolutionären Algorithmus gehört außerdem eine Mutation
710 --~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
711 Sortiernetzwerk zufällig zu verändern aber trotzdem die Sortiereigenschaft zu
712 erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
713 Eigenschaft zerstören.
715 Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
716 Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
717 Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
718 Ausprobieren aller $2^n$~Bitmuster.
720 Um das Potenzial einer Mutation abzuschätzen habe ich in den evolutionären
721 Algorithmus eine Überprüfung eingebaut. Unmittelbar vor dem Einfügen in die
722 Population überprüft das Programm die Notwendigkeit jedes einzelnen
723 Komparators. Dazu wurde nacheinander jeder Komparator entfernt und überprüft,
724 ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt.
727 \item Güte von Sortiernetzwerken (Anzahl der Komparatoren, Anzahl der
728 Schichten, kobiniert)
729 \item Rekombination: Merge Anhängen und Leitungen entfernen.
732 Ein Beispielnetzwerk, das von dem Algorithmus gefunden wird, zeigt
733 Abbildung~\ref{fig:evolutionary_08}.
737 \input{images/evolutionary-08.tex}
739 \caption{Ein mit dem evolutionären Algorithmus erzeugtes Sortiernetzwerk mit
740 acht Eingängen. Es besteht aus 19~Komparatoren in 6~Schichten.}
741 \label{fig:evolutionary_08}
746 \input{images/08-e2-1237993371.tex}
748 \caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
749 \label{fig:08-e2-1237993371}
754 \input{images/09-e2-1237997073.tex}
756 \caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
757 \label{fig:09-e2-1237997073}
762 \input{images/09-e2-1237999719.tex}
764 \caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
765 \label{fig:09-e2-1237999719}
770 \input{images/10-e2-1239014566.tex}
772 \caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
773 \label{fig:10-e2-1239014566}
779 \item So gut kann man mindestens werden {\em ($\rightarrow$ Bitonic-Mergesort, vermute ich)}.
780 \item Wie gut die Netzwerke werden, hängt stark vom verwendeten \em{Mischer} ab.
783 \section{Markov-Kette}
785 Der evolutionäre Algorithmus aus dem vorherigen Abschnitt verwendete immer
786 zwei zufällige Sortiernetzwerke („Individuen“) aus einer Population. Da die
787 beiden „Eltern“ zufällig und unabhängig voneinander ausgewählt werden, kann es
788 vorkommen, dass das selbe Sortiernetzwerk zweimal verwendet und mit sich
789 selbst kombiniert wird.
791 Macht man diesen Spezialfall zum Regelfall, indem man \emph{immer} das
792 aktuelle Netzwerk mit sich selbst kombiniert und anschließend die Hälfte aller
793 Leitungen eliminiert, lassen sich einige interessante Beobachtungen anstellen.
794 Netzwerke, die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von
795 $S_0$ mit sich selbst und anschließendem Eliminieren der Hälfte der Leitungen
796 hervorgehen können, heißen \emph{Nachfolger} von $S_0$.
798 Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
799 gerichteten Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
800 Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
801 Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von $S_0$
802 ist, das heißt dass man $S_1$ durch die Rekombination von $S_0$ mit sich
803 selbst erzeugen kann.
805 Der Algorithmus {\sc SN-Markov} legt auf diesem Graph einen zufälligen Weg
806 (englisch: \textit{random walk}) zurück. Er startet auf einem gegebenen
807 Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu gelangen
808 rekombiniert er das aktuelle Sortiernetzwerk mit sich selbst und erhält so
809 einen zufälligen Nachfolger.
812 \item $n \leftarrow \mathrm{Input}$
813 \item \texttt{while} \textit{true}
815 \item $n \leftarrow \operatorname{recombine} (n, n)$
820 \item Beste erreichte Netzwerke (gleich zu \emph{OE-Mergesort}).
821 \item Anzahl der erreichbaren Sortiernetzwerke.
822 \item Anzahl der Komparatoren und Anzahl der Schichten der durchlaufenen
823 Netzwerke. (Abbildung~\ref{fig:markov-comparators-16})
828 \includegraphics[viewport=0 0 360 216,width=15cm]{images/markov-comparators-16.pdf}
830 \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen), die von {\sc SN-Markov} durchlaufen wurden.}
831 \label{fig:markov-comparators-16}
834 %\input{shmoo-aequivalenz.tex}
836 \section{Optimierung der Schnitte}
838 Der \emph{evolution-cut}-Algorithmus nimmt ein gegebenes Sortiernetzwerk mit
839 $n$~Leitungen und sucht die beste Sequenz von $c$~Min- und Max-Schnitten um
840 ein ${(n-c)}$-Sortiernetzwerk zu erhalten.
842 Bei diesem Algorithmus werden die \emph{Schnitt-Sequenzen} als Individuen
843 verwendet. Eine \emph{Schnitt-Sequenz} ist eine Liste mit $c$~Schnitten, die
844 jeweils durch die Start-Leitung und die Richtung \textit{Min} beziehungsweise
845 \textit{Max} gegeben ist. Der Algorithmus wendet jeden Schnitt einzeln an, so
846 dass eine Leitungsnummer mehrfach in einer Schnittsequenz vorkommen kann. Die
847 höchste zulässige Leitungsnummer ist abhängig von der Position des Schnitts in
848 der Sequenz. Der Schnitt an Position~$i$ darf höchstens die
849 Leitungsnummer~${n-i-1}$ enthalten.\footnote{Die niedrigste Leitungsnummer ist
850 $0$, die höchste Leitungsnummer eines $n$-Sortiernetzwerks ist $n-1$.}
852 Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte der einen
853 Schnitt-Sequenz verwendet und die letzten ${c-r}$~Schnitte der zweiten
854 Sequenz. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$.
856 Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig
857 auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die
862 \input{images/16-ec-1277186619.tex}
864 \caption{{\tt images/16-ec-1277186619.tex}: Sortiernetzwerk mit 16~Leitungen
865 und 68~Komparatoren in 10~Schichten. Das Netzwerk wurde von dem Algorithmus
866 \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(32)$ durch
867 16~Schnitte erzeugt.}
868 \label{fig:16-ec-1277186619}
871 Wendet man den \emph{evolution-cut}-Algorithmus auf das
872 Bitonic-Mergesort-Netzwerk $M(n)$ an und setzt die Anzahl der Schnitte~$c$ auf
873 $\frac{n}{2}$, so erhält man Sortiernetzwerke, die weniger Komparatoren
874 benötigen als $M(\frac{n}{2})$.
876 Das Sortiernetzwerk in Abbildung~\ref{fig:16-ec-1277186619} ist entstanden,
877 indem der Algorithmus \emph{evolution-cut} auf das $M(32)$-Sortiernetzwerk
878 angewendet wurde. Der Algorithmus fand eine Schnitt-Sequenz aus 16~Schnitten,
879 die ein Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in 10~Schichten
880 erzeugt. Das $M(16)$-Sortiernetzwerk besteht aus 80~Komparatoren in
883 Dieses Ergebnis deckt sich mit dem Sortiernetzwerk, dass
884 \emph{Moritz Mühlenthaler} und \emph{Rolf Wanka} in ihrer Veröffentlichung
885 „Improving Bitonic Sorting by Wire Elimination“ vorstellen. Sie verwenden
886 Schnitte, um Komparatoren beim bitonen $(n,n)$-Mischer enizusparen. Ein
887 sukzessive aus optimieren Mischern aufgebautes Sortiernetzwerk spart
888 --~verglichen mit dem Bitonic-Mergesort-Netzwerk~-- $\frac{1}{4}n(\log n - 1)$
889 Komparatoren ein. Bei einem Sortiernetzwerk mit 16~Leitungen also
890 12~Komparatoren -- 68 statt 80.
894 \input{images/32-ec-1277190372.tex}
896 \caption{{\tt images/32-ec-1277190372.tex}: Sortiernetzwerk mit 32~Leitungen
897 und 206~Komparatoren in 15~Schichten. Das Netzwerk wurde von dem Algorithmus
898 \emph{evolution-cut} aus dem Bitonic-Mergesort-Netzwerk $M(64)$ durch
899 32~Schnitte erzeugt.}
900 \label{fig:32-ec-1277190372}
903 Abbildung~\ref{fig:32-ec-1277190372} zeigt ein 32-Sortiernetzwerk, dass vom
904 \emph{evolution-cut}-Algorithmus aus dem $M(64)$-Netzwerk erzeugt wurde. Es
905 besteht aus 206~Komparatoren in 15~Schichten -- 34~Komparatoren weniger als
906 $M(32)$ und zwei Komparatoren weniger als das Netzwerk, das nach Mühlenthaler
907 und Wankas Methode konstruiert wird. Die Anzahl der Schichten ist bei allen
910 \textbf{TODO:} $M(128) \rightarrow n=64$: 584~Komparatoren in 21~Schichten
911 möglich (nach ca. 600k Iterationen). Moritz und Rolf: $672-80=592$
912 Komparatoren; $M(64)$: 672~Komparatoren.
980 % images/32-ec-1277190372.tex
982 \section{Empirische Beobachtungen}
985 \item So schnell konvergiert der Algorithmus.
991 Das würde mir noch einfallen$\ldots$
993 %\bibliography{references}
994 %\bibliographystyle{plain}
1000 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 :