1 \documentclass[a4paper,11pt]{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=30mm}
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 \newcommand{\oes}[1]{\ensuremath{\operatorname{OES}\left(#1\right)}}
40 \newcommand{\bs}[1]{\ensuremath{\operatorname{BS}\left(#1\right)}}
41 \newcommand{\ps}[1]{\ensuremath{\operatorname{PS}\left(#1\right)}}
42 \newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}\left(#1\right)}}
43 \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
44 \newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}
46 \newtheorem{definition}{Definition}
47 \newtheorem{satz}{Satz}
49 % Zeige Nummern nur bei referenzierten Gleichungen an.
50 \mathtoolsset{showonlyrefs=true}
54 \tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt]
55 \tikzstyle{comp} = [draw,thick,-]
56 \tikzstyle{compup} = [draw,thick,->]
57 \tikzstyle{compdown} = [draw,thick,<-]
58 \tikzstyle{edge} = [draw,thick,-]
59 \tikzstyle{diredge} = [draw,thick,->]
60 \tikzstyle{prob} = [font=\tiny]
62 \tikzstyle{edge minimum} = [edge,color=blue!20]
63 \tikzstyle{edge maximum} = [edge,color=red!20]
64 \tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50]
65 \tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50]
66 \tikzstyle{vertex active minimum maximum} = [vertex,color=violet!50, fill=violet!50]
67 \tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20]
68 \tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20]
69 \tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20]
70 \tikzstyle{comp active minimum} = [comp]
71 \tikzstyle{comp active maximum} = [comp]
72 \tikzstyle{comp active minimum maximum} = [comp,color=black!20]
73 \tikzstyle{comp inactive minimum} = [comp,color=blue!20]
74 \tikzstyle{comp inactive maximum} = [comp,color=red!20]
75 \tikzstyle{comp inactive minimum maximum} = [comp,color=black!20]
77 \tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
78 \tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
79 \tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
80 \tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
84 Sortiernetzwerke erweisen sich als sehr schwieriges Optimierungsproblem. Zwar
85 ist das Konzept leicht verständlich und schnell erklärt, effiziente und
86 schnelle Sortiernetzwerke zu finden oder zu konstruieren bleibt aber eine
89 Diese Arbeit verwendet „Schnitte“ oder „Leitungselimination“ und
90 Mischer-Netz\-werke, um evolutionäre Algorithmen anzugeben, deren Individuen
91 die Menge der gültigen Sortiernetzwerke nie verlassen. Bisherige Ansätze
92 bewegten sich in der Regel in der Menge aller Komparatornetzwerke und suchten
93 dort nach Sortiernetzwerken. Nach dem Vorstellen der zwei Algorithmen
94 \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} sowie einiger Ergebnisse,
95 die mit diesen Algorithmen erzielt werden konnten, wird -- basierend auf dem
96 evolutionären Algorithmus \textsc{SN-Evolution} -- eine Markov-Kette für
97 Sortiernetzwerke angegeben.
104 \section{Motivation und Einleitung}
106 \subsection{Motivation}\label{sect:motivation}
108 \emph{Sortiernetzwerke} sind ein theoretisches Konstrukt, dass auch von
109 Personen ohne Zugang zum Thema, beziehungsweise der theoretischen Informatik,
110 schnell verstanden werden kann. Eine Einführung wird in
111 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} gegeben. Nichtsdestotrotz ist
112 das Finden von Sortiernetzwerken sowie das Beweisen, dass ein
113 Komparatornetzwerk jede beliebige Eingabe sortiert, im Allgemeinen sehr
114 schwierig und nach heutigem Kenntnisstand nur mit exponentiellem Aufwand zu
117 Einfacher ist der Korrektheitsbeweis bei konstruktiven Verfahren, da hier die
118 Konstruktionsvorschrift genutzt werden kann, um die Korrektheit für beliebige
119 Eingabegrößen zu beweisen. Im Abschnitt~\ref{sect:konstruktive_netzwerke}
120 geschieht dies beispielsweise für zwei von \emph{Kenneth~E. Batcher} 1968
121 gefundene Konstruktionsvorschriften.
123 Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon wiederholt
124 Computer und automatische Suchverfahren eingesetzt. Bisherige Ansätze
125 versuchen meist in der Menge aller Komparatornetzwerke jene zu finden, die
126 die Sortiereigenschaft besitzen und aus wenigen Komparatoren bestehen. Die
127 Eigenschaft, jede Eingabepermutation zu sortieren, ist also ein
128 Optimierungsziel und nicht durch das Vorgehen gewährleistet. Dafür können
129 theoretisch alle Sortiernetzwerke durch diese Algorithmen gefunden werden --
130 genügend Laufzeit vorausgesetzt.
132 In dieser Arbeit werden Methoden verwendet, die die Menge der Sortiernetzwerke
133 nie verlassen, dafür aber auch nicht alle existierenden Sortiernetzwerke
134 erzeugen können. So muss für ein gefundenes Komparatornetzwerk nicht mehr
135 nachgewiesen werden, dass es jede beliebige Eingabe sortiert, weil diese
136 Eigenschaft durch das Verfahren sichergestellt ist.
138 \subsection{Einleitung}\label{sect:einleitung}
140 \subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
142 \emph{Komparatoren} sind die Bausteine, die \emph{Komparatornetzwerken}
143 zugrunde liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten
144 können und zwei Ausgänge, auf denen die Zahlen wieder ausgegeben werden. Dabei
145 sind die Ausgänge im Gegensatz zu den Eingängen unterscheidbar, da die größere
146 der beiden Zahlen immer auf dem einen, die kleinere der beiden Zahlen
147 immer auf dem anderen Ausgang ausgegeben wird.
149 Kombiniert man mehrere \emph{Komparatoren} in der Form miteinander, dass die
150 Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind,
151 erhält man ein {\em Komparatornetzwerk}.
155 \input{images/einfaches_komparatornetzwerk.tex}
157 \caption{Einfaches Komparatornetzwerk mit vier Ein- beziehungsweise Ausgängen, bestehend
159 \label{fig:einfaches_komparatornetzwerk}
162 Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
163 \emph{Komparatornetzwerk} aus fünf Komparatoren. Insgesamt gibt es vier
164 verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch
165 eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die
166 \emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je
167 zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von
168 \emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichtlichkeit
169 durch schwarze Punkte symbolisiert.
171 Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in
172 das Netzwerk hinein gegeben. Jeder Komparator vergleicht die Zahlen „auf“ den
173 beiden Leitungen, die er verbindet. Nach einem Komparator befindet sich die
174 kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
175 befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat. Wenn in
176 einem Komparatornetzwerk alle Komparatoren in die gleiche Richtung zeigen --
177 die Konvention in dieser Arbeit ist, dass das Minimum auf der unteren Leitung
178 ausgegeben wird -- werden die Pfeile durch einfache Linien ersetzt. Zu diesen
179 sogenannten \emph{Standard-Netzwerken} siehe auch
180 Abschnitt~\ref{sect:normalisieren}.
182 Komparatoren, die \emph{unterschiedliche} Leitungen miteinander vergleichen,
183 können gleichzeitig angewendet werden. Das Beispiel in
184 Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
185 vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine
186 Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man
187 eine \emph{Schicht} des Komparatornetzwerks. Die \emph{Geschwindigkeit} eines
188 Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die
189 sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der
190 benötigten parallelen Schritte darstellt.
192 \emph{Komparatornetzwerke}, die für \emph{jede} Eingabefolge eine Ausgabe
193 erzeugen, die der Sortierung der Eingabe entspricht, heißen
194 \emph{Sortiernetzwerke}. Das in
195 Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
196 ist \emph{kein} Sortiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur
197 Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar
202 \input{images/09-e2-c24-allbut1.tex}
204 \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
205 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
206 alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
207 \label{fig:09-e2-c24-allbut1}
209 Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
210 nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich. Das
211 Komparatornetzwerk wird auf das Gegenbeispiel angewendet und anschließend wird
212 überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht, heißt das, dass es
213 mindestens eine Eingabefolge gibt, die nicht sortiert wird. Entsprechend der
214 Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich
215 \emph{nicht} um ein \emph{Sortiernetzwerk}. Ein solches Gegenbeispiel für ein
216 gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
217 nicht \emph{effizient}\footnote{In diesem Zusammenhang heißt \emph{effizient},
218 dass keine Algorithmen bekannt sind, die eine polynomielle Laufzeit (in
219 Abhängigkeit von der Eingabelänge) haben.} möglich.
221 Beispielsweise sortiert das im Rahmen dieser Arbeit entdeckte
222 Komparatornetzwerk in Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880
223 möglichen Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4,
224 8, 6)$ lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die
225 Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1,
226 0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt.
228 Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
229 Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
230 Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
231 über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
232 Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
233 ist.\footnote{1.307.674.368.000 Permutationen}
235 \label{sect:0-1-prinzip}
236 Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie
237 \textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende:
238 Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine
239 Permutation $E = (e_0, \dots, e_{n-1})$ beliebiger Zahlen, die nicht sortiert
240 wird. Die Ausgabefolge sei $A = (a_0, \dots, a_{n-1})$. Sei $i$ eine Position
241 in der Ausgabe, die die Sortierbedingung verletzt:
243 a_0 \leqq a_1 \leqq \dots \leqq a_{i-1} > a_i \dots
245 Die Eingabe kann mittels
253 auf eine 0-1-Folge abgebildet werden, die entsprechend der Annahme vom
254 Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
255 Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine
256 Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
257 wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
258 vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
259 zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$
260 oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei
261 gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich
262 der Komparator so verhält, wie er sich bei der Permutation verhalten hat --
263 ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$
264 und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im
265 Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.
267 Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
269 $\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
270 ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$
271 verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
272 schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
273 ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
274 sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
275 aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
276 eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
277 4,3~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
280 \subsubsection{Evolutionäre Algorithmen}
282 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
283 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
284 $\mathcal{NP}$. Das heißt, dass keine Verfahren bekannt sind, die diese
285 Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese Probleme
286 außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine Konsequenz,
287 dass es effiziente exakte Algorithmen für diese Probleme nicht gibt. Falls
288 sich hingegen herausstellt, dass diese Probleme neben $\mathcal{NP}$ auch in
289 der Komplexitätsklasse~\textit{P} liegen, gibt es effiziente Algorithmen. Es
290 ist jedoch wahrscheinlich, dass die Zeitkonstanten solcher Algorithmen sehr
291 groß sein würden, so dass der praktische Nutzen fraglich bleibt.
293 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
294 die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen
295 Lösungen}, als einzige Ausgabe des Algorithmus zuzulassen, wird eine
296 "`möglichst gute"' Lösung ausgegeben. Viele dieser Optimierungsalgorithmen
297 orientieren sich an Vorgängen in der Natur. Beispielsweise imitieren die
298 „Ameisenalgorithmen“ das Verhalten von Ameisen auf der Futtersuche, um kurze
299 Rundreisen auf Graphen zu berechnen.
301 Bei {\em Evolutionären Algorithmen} stand die Evolution Pate. Die Grundidee
302 ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
303 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
304 Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em
305 Individuen} bezeichnet.
307 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben: Aus einer
308 bestehenden Lösungsmenge, der {\em Population}, werden zufällig Lösungen
309 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
310 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
311 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
312 eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der
313 {\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
314 werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
317 Nicht alle Probleme eignen sich für diese Strategie. Zum einen muss es möglich
318 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
319 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
320 es oft einfach ist, {\em irgendeine} Lösung anzugeben. Die angegebenen
321 Algorithmen verwenden als einfache initiale Lösung häufig das
322 \emph{Odd-Even-Transpositionsort}-Netzwerk, das in
323 Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
324 muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
325 problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen. Die in
326 dieser Arbeit verwendeten Rekombinationsmethoden sind so gewählt, dass die
327 Nebenbedingungen nicht verletzt werden.
329 Beim Aussuchen von zufälligen Lösungen aus der Population, der
330 \emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
331 bevorzugt werden, hat einen starken Einfluss auf das Verhalten des
332 Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus
333 schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch
334 für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus
335 schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale
336 Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
337 erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
338 \textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
339 zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
340 findet er aber in der Regel bessere Lösungen.
342 Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
343 Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
344 nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
345 eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
346 beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
347 zwischen verschiedenen Leitungszahlen stark unterscheiden.
349 Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
350 unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
351 \emph{Mutation}. Dabei werden Lösungen zufällig verändert, so dass auch andere
352 Lösungen „in der Nähe“ von direkten Nachfolgern erreicht werden können. Das
353 hilft insbesondere bei der intensiven Suche in der Nähe eines lokalen Optimums
354 aber auch beim „Ausbrechen“ aus lokalen Optima und finden noch besserer
357 Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
358 verbunden, dass anschließend die Sortiereigenschaft des resultierenden
359 \emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
360 Hinzufügen eines zufälligen Komparators diese Eigenschaft zer\-stö\-ren kann.
361 Beim Suchen möglichst effizienter Netzwerke ist das zufällige Entfernen von
362 Komparatoren interessanter, was die Sortiereigenschaft fast immer aufhebt.
364 Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
365 die \emph{Sortiernetzwerke} selbst, sondern verzichten entweder ganz auf
366 Mutation oder mutieren lediglich Transformationen von Sortiernetzwerken, die
367 die Sortiereigenschaft erhalten. Transformationen von Sortiernetzwerken werden
368 in Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der
369 Mutation einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
371 \begin{figure} \begin{center} \input{images/16-hillis.tex} \end{center}
372 \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
373 Es besteht aus 61~Komparatoren in 11~Schichten.} \label{fig:16-hillis}
374 \end{figure} Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
375 Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
376 \emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
377 zu optimieren~\cite{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
378 daran gemessen, bei wie vielen Komparatornetzwerken sie beweisen konnten, dass
379 sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen
380 (Komparatornetzwerken) nicht alle 0-1-Folgen, sondern nur erfolgreiche
381 Parasiten (schwierige Eingaben) überprüft werden. Auf diese Art und Weise
382 gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
383 anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
387 \subfigure{\input{images/13-juille-0.tex}}
388 \subfigure{\input{images/13-juille-1.tex}}
389 \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des
390 END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in
392 \label{fig:13-juille}
394 \textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
395 Non-Determinism} (END) nannte~\cite{J1995}. Dabei handelt es sich nicht um
396 einen der \emph{Evolutionären Algorithmen}, wie sie hier vorgestellt wurden,
397 sondern um eine verteilte, probabilistische Breitensuche, die an die
398 \emph{Strahlsuche} (englisch: \textit{beam search}), ein Verfahren der
399 Künstlichen Intelligenz, angelehnt ist. Die aufwendigste Operation bei diesem
400 Ansatz ist die Bewertungsfunktion, die abschätzt, wie viele Komparatoren zu
401 einem Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
402 erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
403 anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
404 bekannten (Abbildung~\ref{fig:13-juille}).
407 \section[Konstruktionsverfahren]{Konstruktionsverfahren für Sortiernetzwerke}
408 \label{sect:konstruktive_netzwerke}
410 Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere ein
411 häufig verwendeter Baustein, sogenannte \emph{Mischer}\footnote{Eine
412 Fehlübersetzung aus dem Englischen, von \textit{to~merge} (Deutsch:
413 zusammenfügen). Da der Begriff des "`mischens"' beziehungsweise der
414 "`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
415 in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
416 beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
417 Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
419 % \todo{Drei oder vier Verfahren?}
421 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
422 \label{sect:odd_even_transpositionsort}
424 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
425 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
426 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
427 Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für
432 \input{images/oe-transposition-8.tex}
434 \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit acht Eingängen.}
435 \label{fig:odd-even-transposition-08}
438 Dass das \emph{Odd-Even-Transpositionsort}-Netzwerk tatsächlich jede beliebige
439 Eingabe sortiert, ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
440 sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
441 Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt.
443 Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
444 indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
445 Herausschneiden einer Leitung reduziert. In
446 Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
447 beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
448 Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. Die Rekursion endet
449 beim \emph{Odd-Even-Transpositionsort}-Netzwerk mit drei Eingängen, bei dem
450 das Minimum auf der untersten, das Maximum auf der obersten und der mittlere
451 Wert auf der mittleren Leitung landet. Folglich ist die Ausgabe bei
452 $\operatorname{OET}(3)$ sortiert.
454 Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
455 Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
456 sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
457 (n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
458 Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
459 ($\Theta(n \log (n)^2)$), die in weniger Schichten,
460 ($\Theta(\log (n)^2)$), angeordnet sind.
462 Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
463 folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
464 Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
465 finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
468 Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer,
469 beziehungsweise mehrerer Leitungen, um die Anzahl der Leitungen eines
470 Sortiernetzwerks zu reduzieren. Die Technik wird in Detail im
471 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
473 \subsection{Das bitone Mergesort-Netzwerk}
475 Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
476 Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
477 veröffentlicht wurde. Es ist deutlich effizienter als das
478 Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
479 Komparatoren als auch der benötigten Zeit, also der Anzahl der Schichten.
481 Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
482 sortierte Listen zusammenfügen (Englisch: \textit{to~merge}) kann. Dieser
483 \emph{„bitone Mischer“} (Englisch: \textit{bitonic merger}) genannte Baustein
484 verleiht dem Sortiernetzwerk seinen Namen.
486 Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
487 Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
488 Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
490 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
492 Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen
493 Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine
494 beliebige \emph{bitone Folge} in eine sortierte Liste umordnen kann. Eine
495 \emph{bitone Folge} ist eine monoton steigende Folge, gefolgt von einer
496 monoton absteigenden Folge, oder ein zyklischer Shift davon.
497 Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten,
498 die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das
499 \emph{bitone Mergesort}-Netzwerk zeigen die
500 Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie
501 erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste
502 aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass
503 das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) beziehungsweise
504 kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge
509 \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
510 \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
511 \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
512 \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
513 \caption{Beispiele bitoner Folgen.}
514 \label{fig:beispiel-biton}
519 \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
521 \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
522 \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
523 aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
524 der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
525 resultierenden Teilfolgen sind wiederum biton.}
526 \label{fig:bitonic-merge-schema}
529 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
530 ${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
531 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
532 sortiert, die Folge $V$ sei absteigend sortiert:
534 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
535 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
537 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
538 Positionen verglichen und ggf. vertauscht:
540 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
542 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
543 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
544 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
545 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
546 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
547 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
548 "`linken"' Folge $u_{m-1}$ kleiner ist als das kleinste Element der
549 "`rechten"' Folge $v_{m-1}$. Daraus folgt, dass sich das Resultat in zwei
550 bitone Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
551 absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
552 zeigt die Situationen vor und nach diesem Schritt des Mischers schematisch.
554 Um die Folge vollständig zu sortieren, müssen anschließend die beiden
555 resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
556 mithilfe des bitonen Mischers, mit zwei Instanzen von
557 $\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem
558 bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als
559 Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
562 Der bitone Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
563 lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
564 notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
565 „echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
566 Schema des bitonen Mischers für zwei aufsteigend sortierte Folgen. Durch das
567 Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
568 Statt an eine Treppe erinnert das Muster nun an einen Trichter.
570 Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
571 die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
572 $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
573 $\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren
574 besteht, die in $\log(n)$~Schichten angeordnet werden können.
576 \subsubsection{Das bitone Mergesort-Netzwerk}
578 Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
579 Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
580 zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe
581 $\bs{\frac{n}{2}}$ für je die Hälfte der Eingänge, sowie dem bitonen Mischer
582 für $n$~Leitungen $\operatorname{BM}(n)$. Das Rekursionsende ist das bitone
583 Mergesort-Netzwerk mit nur einer Leitung $\operatorname{BS}(1)$, welches als
584 leeres Komparatornetzwerk definiert ist. Entsprechend sind die
585 Komparatornetzwerke $\operatorname{BM}(2)$ und $\operatorname{BS}(2)$
588 Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
589 (Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
590 rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so
591 alle Komparatoren in die gleiche Richtung zeigen.
595 \input{images/batcher-8.tex}
597 \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für acht
598 Eingänge. Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden
599 bitonen Mischer~\bm{4} (blau) und die Komparatoren, die im letzten
600 rekursiven Schritt hinzugefügt wurden (grün).}
601 \label{fig:bitonic-08}
604 Das Sortiernetzwerk~$\operatorname{BS}(8)$ ist in
605 Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
606 beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
607 Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
608 die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
611 Das \emph{bitone Mergesort}-Netzwerk mit einer Leitungszahl $n = 2^d$, die
612 eine Zweierpotenz ist, besteht aus $\frac{1}{4} n \log(n) \log(n+1) =
613 \Theta\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2}
614 \log(n) \log(n+1) = \Theta(\log(n)^2)$ Schichten angeordnet sind.
616 \subsection{Das Odd-Even-Mergesort-Netzwerk}
618 Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort}-Netzwerk
619 (OES) und das \emph{Odd-Even-Transpositionsort}-Netzwerk (siehe
620 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
621 OES dem \emph{bitonen Mergesort}-Netzwerk, das im vorherigen Abschnitt
622 vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
623 \textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
624 beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
625 darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
627 \subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer}
629 Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein
630 Komparatornetzwerk, das zwei sortierte Folgen mit $n$ beziehungsweise $m$
631 Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
632 zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
633 \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
634 vorgestellt wurde. Im allgemeinen Fall, wenn die Anzahl der Leitungen keine
635 Zweierpotenz ist, kann das \emph{bitonic-Merge}-Netzwerk schneller sein
636 als das \emph{Odd-Even-Merge}-Netzwerk.~\cite{KNUTH}
638 Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die
639 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
640 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
641 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
642 $W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
644 w_i = \left\{ \begin{array}{ll}
653 \input{images/oe-merge.tex}
655 \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Im
656 Vergleich zum bitonen Mischer für acht Leitungen kommt dieses Schema mit
657 einem Komparator weniger aus. Der Effekt wird durch den rekursiven Aufbau
662 Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der
663 geraden Indizes und je eine Liste der ungeraden Indizes.
665 U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
666 U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
667 V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
668 V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
671 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$,
672 beziehungsweise die ungeraden Folgen $U_{\textrm{ungerade}}$ und
673 $V_{\textrm{ungerade}}$ werden rekursiv von kleineren \emph{Odd-Even}-Mischern
674 zusammengefügt, so dass sich am Ausgang der Mischer die Folgen
676 W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
677 W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
681 Anschließend werden die Komparatoren zwischen benachbarten Leitungen
684 w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
686 die die Folge~$W$ sortieren. Den schematischen Aufbau des
687 \emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}.
689 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
690 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
691 entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
692 offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
695 \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
696 \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
697 einzelnen Komparator.
700 Mit dem {\em 0-1-Prinzip} lässt sich zeigen, sass die resultierende Folge
701 sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den
702 geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise
703 $V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den
704 ungeraden Teilfolgen $U_{\textrm{ungerade}}$ beziehungsweise
705 $V_{\textrm{ungerade}}$ --~die Einsen verhalten sich entsprechend umgekehrt.
706 Das trifft demnach auch auf die Folgen $W_{\textrm{gerade}}$ und
707 $W_{\textrm{ungerade}}$ entsprechend zu:
709 \left|W_{\textrm{gerade}}\right|_0
710 &=& \left|U_{\textrm{gerade}}\right|_0
711 + \left|V_{\textrm{gerade}}\right|_0
712 = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
713 + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
714 \left|W_{\textrm{ungerade}}\right|_0
715 &=& \left|U_{\textrm{ungerade}}\right|_0
716 + \left|V_{\textrm{ungerade}}\right|_0
717 = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
718 + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
720 Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
721 als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
722 Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
723 wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält als
724 $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
725 Ausgabe zu sortieren. Diese wird von den Komparatoren ausgeführt, die
726 benachbarte Leitungen miteinander vergleichen. Die jeweiligen Situationen sind
727 in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
731 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
733 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
735 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
736 \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
737 kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der
738 Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
739 letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
741 \label{fig:oe-post-recursive}
744 Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
745 bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$
746 Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
747 Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
748 Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
750 Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
751 allgemeinen Fall verwendet, hängt gemäß der rekursiven Definition von der
752 Länge der Eingabefolgen, $n$ und $m$ ab:
754 K(n,m) = \left\{ \begin{array}{ll}
755 nm, & \mathrm{falls} \quad nm \leqq 1 \\
756 K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right)
757 + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right)
758 + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1
761 Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
762 anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
763 dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist.
765 Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
766 Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
767 erste Rekursionsschritt der OEM-Konstruktion fügt
768 $\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
769 Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
770 diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer
771 $\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
772 einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
773 \frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
775 \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1
777 Komparatoren eingespart. Damit ergibt sich
779 K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
781 für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
784 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
786 Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ besteht, wie
787 das \emph{bitone Mergesort}-Netzwerk, rekursiv aus kleineren Varianten von
788 sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die
789 effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
790 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
791 \oes{n} aus $\oes{\left\lceil\frac{n}{2}\right\rceil}$,
792 $\oes{\left\lfloor\frac{n}{2}\right\rfloor}$ und
793 $\oem{\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor}$.
794 Die Rekursion endet mit $\operatorname{OES}(1)$ und $\operatorname{OES}(0)$,
795 die als leere Komparatornetzwerke definiert sind.
799 \input{images/oe-mergesort-8.tex}
801 \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für acht Eingänge. Markiert
802 sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
803 \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade
804 Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
805 Komparatoren zwischen benachbarten Leitungen (grün).}
806 \label{fig:odd-even-mergesort-08}
809 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
810 zu sehen. Rot markiert sind die beiden rekursiven Instanzen
811 $\operatorname{OES}(4)$. Die anderen Blöcke stellen den
812 \emph{Odd-Even}-Mischer für acht Leitungen dar: die beiden blauen Blöcke sind
813 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
814 die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.
816 Im Allgemeinen ist die Anzahl der Komparatoren, die vom
817 \emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der
818 Definition, beziehungsweise der Konstruktionsanleitung abzulesen:
820 k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
821 + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
822 + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
824 Da es schwierig ist für $K(n,m)$ eine geschlossene Form anzugeben, ist eine
825 geschlossene Darstellung von $k(n)$ ebenfalls nicht ohne weiteres möglich. Es
826 ist allerdings bekannt, dass $k(n)$ in $\Theta\left(n \left(\log
827 (n)\right)^2\right)$ enthalten ist.
829 Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
830 Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
831 Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
833 k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
838 % oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
839 % oem1(n) = oem(ceil(.5*n),floor(.5*n))
840 % oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
843 %\item Pairwise sorting-network
846 \subsection{Das Pairwise-Sorting-Netzwerk}
848 Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
849 für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
850 Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
851 Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
852 \emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
853 das \emph{Odd-Even-Mergesort}-Netzwerk.
856 \section{Transformation von Sortiernetzwerken}
857 \label{sect:tranformation}
859 \subsection{Komprimieren}
861 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
862 gleichzeitig ausgewertet werden, wie bereits in
863 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
864 Transformationen, insbesondere das Entfernen einer Leitung wie in
865 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben, kann es vorkommen, dass
866 die Komparatoren eines Sortiernetzwerks nicht mehr in der kleinstmöglichen
867 Anzahl von \emph{Schichten} angeordnet sind. Unter \emph{Komprimierung} wird
868 eine (Neu-)Gruppierung der Komparatoren verstanden, die jeden Komparator so
869 früh wie möglich ausführt. So entsteht die kleinstmögliche Anzahl von
870 \emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
872 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
873 Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
874 beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
875 Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
876 die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
877 Komprimierung durchgeführt werden.
879 \subsection{Normalisieren}
880 \label{sect:normalisieren}
884 \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
885 \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
886 \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
887 transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
888 intuitiven Konstruktion und die normalisierte Variante.}
889 \label{fig:beispiel_normalisieren}
892 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
893 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
894 zeigen.\footnote{Die Konvention in dieser Arbeit ist, dass in diesem Fall alle
895 Pfeile nach unten zeigen. Das Minimum wird auf der untersten, das Maximum auf
896 der obersten Leitung ausgegeben.} Jedes Sortiernetzwerk kann in eine
897 normaliesierte Variante transformiert werden. Dazu gibt beispielsweise
898 \emph{Donald~E. Knuth} in~\cite{KNUTH} einen Algorithmus an.
900 Abbildung~\ref{fig:beispiel_normalisieren} stellt das \emph{bitone
901 Mergesort}-Netzwerk in zwei Varianten dar. Abbildung~\ref{fig:bitonic-nonstd}
902 zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
903 Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
904 die untere und die obere Hälfte gegenläufig sortiert. Das heißt, dass nach
905 drei Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert
906 ist. In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der
907 rekursiven Definition.
909 In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
910 Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die selbe
911 Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen-
912 und das Trichtermuster zu sehen.
914 \subsection{Zwei Netzwerke kombinieren}
916 Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden
917 zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
918 Sortiernetzwerk zusammenzufassen.
920 Diese Technik wurde in den vorangegangen Abschnitten bereits verwendet,
921 beispielsweise um zwei \emph{bitone Mergesort}-Netzwerke mit jeweils der
922 halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
923 einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
924 \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ wurde auf diese Art
925 und Weise rekursiv aufgebaut.
927 Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
928 Folgen. \emph{Wie} diese Folgen sortiert wurden ist unerheblich. Entsprechend
929 können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
930 zu sortieren und die Ausgaben mit einem der beschriebenen Mischer
933 Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
934 $\operatorname{BS}(8)$ mit je acht Leitungen mit dem
935 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
936 Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
937 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
938 80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
940 Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren),
941 beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“
942 Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk.
943 Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt
944 beispielsweise 26~Komparatoren, die in neun Schichten angeordnet sind. Es sind
945 allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich
946 25~Komparatoren in sieben Schichten benötigen. Kombiniert man zwei dieser
947 Netzwerke mit dem \emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit
948 18~Eingängen, das 80~Komparatoren in 11~Schichten benötigt.
949 $\operatorname{OES}(18)$ benötigt 82~Komparatoren in 13~Schichten. Damit ist
950 das resultierende Netzwerk genauso schnell wie das Sortiernetzwerk mit
951 18~Eingängen, das \textit{Sherenaz~W. Al-Haj Baddar} und \textit{Kenneth~E.
952 Batcher} in ihrer Arbeit „An 11-Step Sorting Network for
953 18~Elements“~\cite{BB2009} vorstellen, benötigt aber 6~Komparatoren weniger.
955 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
956 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
957 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
958 Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die
959 letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen
960 die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
961 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
962 nur mit exponentiellem Aufwand möglich ist.
964 \subsection{Leitungen entfernen}
965 \label{sect:leitungen_entfernen}
967 Im vorherigen Abschnitt wurde gezeigt, dass es mithilfe von \emph{Mischern}
968 möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
969 ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
970 beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
971 sich die Anzahl der Eingänge nicht verändert. Es soll wieder ein
972 Sortiernetzwerk mit $n$~Eingängen entstehen.
974 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
975 Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
976 „eliminiert“. Dazu wird angenommen, dass das Minimum oder das Maximum an einem
977 bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das
978 Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an
979 einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten
980 Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und
981 welche dafür sorgen, dass der Wert die Leitung wechselt, da das Minimum jeden
982 Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
983 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
984 das \emph{Odd-Even-Transpositionsort}-Netzwerk.
986 Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf
987 dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk
988 eindeutig festgelegt.
992 \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
993 durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
994 \subfigure[Komparatoren, die einen Wechsel der Leitungen bewirken, werden
995 durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
996 \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit
997 7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
998 \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die
999 Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
1000 \caption{Eine Leitung wird aus dem
1001 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
1002 markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
1003 nach unten weiter gegeben wird, ist der Pfad fest vorgegeben. Da die
1004 restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
1005 Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
1006 \label{fig:oe-transposition-cut}
1009 Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht,
1010 beziehungsweise ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der
1011 Leitung geführt haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
1012 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
1013 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
1014 ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
1015 das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
1016 die keine Komparatoren mehr berührt
1017 (Abbildung~\ref{fig:oe-transposition-cut1}).
1019 Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
1020 Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die
1021 \emph{Position} des Minimums oder des Maximums in der Eingabe angenommen. Ein
1022 Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher
1023 Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese
1024 Annahme auszuwerten -- über die verbleibenden Eingänge wurde keine Aussage
1025 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
1026 mit $(n-1)$~Elementen darstellen.
1028 Wird die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
1029 Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das
1030 Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung
1031 ein Minimum oder ein Maximum angenommen wird, wird das eliminieren einer
1032 Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise
1033 \emph{Maximum-Schnitt} bezeichnet.
1035 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
1036 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
1037 markierten Komparatoren sind verschoben, so dass sich eine kompaktere
1038 Darstellung ergibt. Außerdem ist das
1039 \emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
1040 zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
1041 kann entfernt werden.
1043 Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig
1044 \emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen
1045 \emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu
1046 \emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben.
1048 \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
1049 \label{sect:anzahl_schnittmuster}
1051 Der Eliminierungsschritt kann iterativ angewendet werden, um aus einem
1052 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
1053 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und
1054 Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
1055 $n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man
1056 die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein
1057 $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren.
1059 Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
1060 auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
1061 Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
1063 Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
1064 Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
1065 auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
1066 ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
1067 ergeben sich insgesamt
1069 \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!}
1072 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
1073 unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung
1074 und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks
1075 angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis.
1077 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
1078 möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
1079 vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken.
1080 Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der
1081 so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der
1082 möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten,
1083 $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/
1084 Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen
1086 \begin{equation}\label{eqn:anzahl_schnittmuster}
1087 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
1088 = 2^{k} \cdot \frac{n!}{k! (n-k)!}
1089 = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
1090 \quad (1 \leqq k < n)
1093 Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
1094 Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
1095 ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schnittmuster mit
1096 16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$
1097 Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große
1098 Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich.
1100 Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
1101 als die Anzahl der \emph{möglichen} Schnittmuster. Für jeden Komparator auf
1102 der ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
1103 Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
1104 unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
1105 der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
1106 Werte unterscheiden.
1108 Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
1109 Ausgangsmuster abgebildet, weil die Position des Minimums beziehungsweise des
1110 Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
1111 unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
1112 erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
1113 Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
1114 Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
1115 sich die Resultate auch in der ersten Schicht nicht unterscheiden.
1119 \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf}
1121 \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
1122 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
1123 $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
1124 unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
1125 \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone
1126 Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.}
1127 \label{fig:count-cuts-16}
1130 Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl
1131 der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
1132 \emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
1133 \emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je
1134 eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke \oes{16},
1135 \bs{16} und \ps{16} angewandt. Anschließend wurde mithilfe einer Hashtabelle
1136 überprüft, ob das resultierende Sortiernetzwerk schon von einem
1137 \emph{äquivalenten} Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk
1138 noch nicht in der Hashtabelle enthalten war, wurde der Zähler für
1139 unterschiedliche Schnittmuster erhöht und das Sortiernetzwerk eingefügt.
1141 Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
1142 \emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
1143 Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
1144 Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
1145 Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
1148 Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
1149 Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen
1150 Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen}
1151 Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des
1152 \emph{Odd-Even-Mergesort}-Netzwerks, 4973 ($\approx 0,15\%$) beim
1153 \emph{bitonen Mergesort}-Netzwerk und 18764 ($\approx 0,57\%$) beim
1154 \emph{Pairwise-Sorting}-Netzwerk. Zwar ist es möglich, dass mehr Iterationen
1155 die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen
1156 in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass
1157 die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
1158 vernachlässigbar klein ist.
1160 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
1161 Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
1162 Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern
1163 vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
1164 „kleine“ x-Werte verlässt.
1166 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
1167 können, kann man sich einer stochastischen Methode bedienen, der sogenannten
1168 \emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für
1169 schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von
1170 $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
1171 zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
1172 der Annahme, dass auf diese Art und Weise Sortiernetzwerke zufällig und
1173 gleichverteilt erzeugt werden, entspricht das Verhältnis der zufälligen
1174 Schnittmuster, die in $S$ enthalten sind, und $n$ gleich dem Verhältnis von
1175 $k$ und der Anzahl der unterschiedlichen Schnittmuster insgesamt. Damit kann
1176 die Anzahl der unterschiedlichen Schnittmuster abgeschätzt werden.
1180 \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
1182 \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
1183 \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
1184 $\operatorname{BS}(32)$.}
1185 \label{fig:collisions-10000-1000000-32}
1188 In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
1189 Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
1190 $\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
1191 jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
1192 \emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
1193 zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
1194 die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
1195 Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
1196 $\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2
1197 \cdot 10^6$ unterschiedlichen 16-Schnittmustern für $\operatorname{OES}(32)$
1198 und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
1202 \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
1204 \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
1205 \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
1206 zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
1207 Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
1208 unterschiedlichen Schnittmustern.}
1209 \label{fig:collisions-100000-1000000-32-ps}
1212 Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting}-Netzwerk
1213 $\operatorname{PS}(32)$ nicht betrachtet, da es für dieses Netzwerk viel mehr
1214 unterschiedliche 16-Schnittmuster gibt als für $\operatorname{OES}(32)$ und
1215 $\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der
1216 unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
1217 Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
1218 Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,
1219 ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem
1220 kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen
1221 Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
1222 $\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedlichen
1223 Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
1224 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
1225 waren. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
1226 unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
1227 vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als
1228 die Anzahl der \emph{möglichen} Schnittmuster.
1231 \section{Der \textsc{SN-Evolution}-Algorithmus}
1232 \label{sect:sn-evolution}
1234 Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
1235 Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
1236 (Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
1237 (Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
1238 Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
1239 in Abschnitt~\ref{sect:bewertung} behandelt.
1241 \subsection{Bewertungsfunktion}\label{sect:bewertung}
1243 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
1244 {\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
1245 die bei Sortiernetzwerken verfolgt werden können:
1247 \item Möglichst wenige Komparatoren („effizient“)
1248 \item Möglichst wenige Schichten („schnell“)
1251 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das
1252 effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus
1253 60~Komparatoren in 10~Schichten. Das schnellste bekannte 16-Sortiernetzwerk
1254 besteht aus 61~Komparatoren in nur 9~Schichten.
1256 Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
1257 berücksichtigen kann, hat die folgende allgemeine Form:
1259 \operatorname{Guete}(S) = w_{\mathrm{Basis}}
1260 + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
1261 + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
1263 Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
1264 dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
1265 gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
1266 Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
1267 jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
1268 so schlecht ist wie man intuitiv vermuten könnte, zeigt der
1269 \textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
1271 Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen,
1272 ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert.
1273 Das heißt, dass das Ziel von \textsc{SN-Evolution} ist,
1274 $\operatorname{Guete}(S)$ zu \emph{minimieren}.
1276 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
1277 genommen werden. Ist er groß, wird der relative Unterschied der Güten
1278 verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
1279 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
1280 klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
1281 Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
1282 Exploitation}, das Finden (lokaler) Optima, bevorzugt.
1284 Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
1285 der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
1286 Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
1287 es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
1288 Leitungszahlen und Mischer-Typen experimentiert werden muss.
1290 Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
1291 Werte herausgestellt:
1293 w_{\mathrm{Basis}} &=& 0 \\
1294 w_{\mathrm{Komparatoren}} &=& 1 \\
1295 w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
1298 \subsection{Selektion}
1300 Die \emph{Selektion} sorgt dafür, dass bessere Individuen eine größere
1301 Wahrscheinlichkeit haben zur nächsten Generation beizutragen. Diese
1302 Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für das
1303 Streben des Algorithmus nach besseren Lösungen.
1305 Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
1306 ist es sehr häufig, dass die \emph{Exploitation} überhand gewinnt und der
1307 Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
1309 Die in \textsc{SN-Evolution} implementierte Selektion lässt sich mithilfe von
1310 Pseudocode wie folgt beschreiben:
1315 für jedes Individuum in Population
1317 reziproke Güte := 1.0 / Guete(Individuum)
1318 Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
1319 Gütesumme := Gütesumme + reziproke Güte
1321 mit Wahrscheinlichkeit P
1323 Auswahl := Individuum
1329 \subsection{Rekombination}
1330 \label{sect:sn-evolution:rekombination}
1332 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
1333 einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
1334 einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
1335 bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
1336 \emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
1337 Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
1338 in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
1340 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
1341 erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
1342 Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass
1343 nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können.
1345 \subsection{Mutation}
1347 Zu einem vollständigen evolutionären Algorithmus gehört außerdem die Mutation
1348 --~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
1349 Sortiernetzwerk zufällig zu verändern und dabei die Sortiereigenschaft zu
1350 erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
1351 Eigenschaft zerstören.
1353 Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
1354 Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
1355 Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
1356 Ausprobieren aller $2^n$~Bitmuster, wie in Abschnitt~\ref{sect:0-1-prinzip}
1359 Um das Potenzial einer Mutation abzuschätzen wurde in \textsc{SN-Evolution}
1360 eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population
1361 überprüft eine Funktion die Notwendigkeit jedes einzelnen Komparators. Dazu
1362 wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende
1363 Netzwerk die Sortiereigenschaft noch besitzt. Trotz des hohen Rechenaufwands
1364 -- bei 16-Sortiernetzwerken sind gut 4~Millionen Tests notwendig, um alle
1365 Komparatoren zu überprüfen -- waren die Ergebnisse ernüchternd: Nach circa
1366 1~Million Iterationen mit 16-Sortiernetzwerken fand der so modifizierte
1367 Algorithmus keinen einzigen Komparator, den er hätte entfernen können. Daher
1368 wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet.
1370 \subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer}
1374 \input{images/16-e1-bitonic-1296542566.tex}
1376 \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
1377 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1378 \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers}
1380 \label{fig:16-e1-bitonic-1296542566}
1383 Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von
1384 \textsc{SN-Evolution}, so erhält man Netzwerke wie das in
1385 Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus
1386 wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale
1387 Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist
1388 als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren,
1389 das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt
1390 lediglich~67. Die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks wurde
1391 leider mit keiner Leitungszahl erreicht.
1393 \subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
1397 \input{images/16-e1-oddeven-1296543330.tex}
1399 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
1400 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1401 \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers
1403 \label{fig:16-e1-oddeven-1296543330}
1406 Im vorherigen Abschnitt wurde gezeigt, dass der
1407 \textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
1408 Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
1409 \emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
1410 Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
1411 wiederholen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung
1412 des \emph{Odd-Even}-Mischers findet, erreichen das
1413 \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
1414 nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
1415 Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Wenn $n$ keine
1416 Zweierpotenz ist, kann \textsc{SN-Evolution} unter Umständen Sortiernetzwerke
1417 ausgeben, die schneller als \oes{n} sind.
1421 %\input{images/08-e2-1237993371.tex}
1423 %\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
1424 %\label{fig:08-e2-1237993371}
1429 %\input{images/09-e2-1237997073.tex}
1431 %\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
1432 %\label{fig:09-e2-1237997073}
1437 %\input{images/09-e2-1237999719.tex}
1439 %\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
1440 %\label{fig:09-e2-1237999719}
1445 %\input{images/10-e2-1239014566.tex}
1447 %\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
1448 %\label{fig:10-e2-1239014566}
1451 %\input{shmoo-aequivalenz.tex}
1454 \section{Der \textsc{SN-Evolution-Cut}-Algorithmus}
1455 \label{sect:sn-evolution-cut}
1457 Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
1458 Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
1459 Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
1460 möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
1461 von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem
1462 Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst
1463 gute Schnittmuster gesucht.
1465 Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
1466 in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
1467 Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$
1468 oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem
1469 $k$-Schnittmuster sind genau $k$ Zahlen nicht Null.
1471 Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
1472 Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
1473 verwendet. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq n$. Anschließend
1474 werden zufällig Werte auf Null beziehungsweise 1 oder $-1$ gesetzt, um die
1475 Anzahl der Schnitte zu korrigieren.
1477 Die Mutation vertauscht entweder die Werte von zwei zufälligen Positionen oder
1478 multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu
1481 \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
1483 \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
1484 wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde,
1485 durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen
1486 Mischer mit der Hälfte der Leitungen transformiert. Diese alternativen Mischer
1487 sparen im Vergleich zu den Mischern, die nach Batchers Methode konstruiert
1488 werden, Komparatoren ein.
1490 Beispielsweise geben \textit{Mühlenthaler} und \textit{Wanka} ein
1491 Sortiernetzwerk mit 16~Eingängen an, das mithilfe der alternativen Mischer
1492 konstruiert wurde. Dieses Sortiernetzwerk be\-nö\-tigt 68~Komparatoren,
1493 12~weniger als das \emph{bitone Mergesort}-Netzwerk nach Batchers Methode.
1494 Gegenüber Batchers Methode sparen so konstruierte Sortiernetzwerke
1495 ${\frac{1}{4}n(\log n - 1)}$ Komparatoren ein.
1499 \input{images/16-ec-from-bs32.tex}
1501 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
1502 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1503 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk}
1504 $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
1505 \label{fig:16-ec-from-bs32}
1510 \input{images/16-ec-from-bs32-normalized.tex}
1512 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
1513 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1514 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
1515 $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
1516 \label{fig:16-ec-from-bs32-normalized}
1519 Startet man {\sc SN-Evolution-Cut} mit dem \emph{bitonen Mergesort}-Netzwerk
1520 $\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
1521 Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
1522 16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den
1523 Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
1524 zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
1525 und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26,
1526 29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch
1527 \textsc{SN-Evolution-Cut} gefunden wurde.
1528 Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
1529 nachdem das Schnittmuster angewandt und das Netzwerk normalisiert wurde. Eine
1530 Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist in
1531 diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten des
1532 Netzwerks scheinen rein zufällig zu sein.
1535 % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
1536 % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
1537 % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
1540 \input{images/32-ec-from-bs64.tex}
1542 \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
1543 15~Schichten. Das Netzwerk wurde von dem Algorithmus
1544 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
1545 $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
1547 $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
1548 $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
1549 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
1550 \label{fig:32-ec-from-bs64}
1553 Das Ergebnis von \textit{Mühlenthaler} und \textit{Wanka}, die den bitonen
1554 Mischer optimiert und anschließend aus diesen Mischern ein Sortiernetzwerk
1555 konstruiert haben, kann demnach auch erreicht werden, wenn
1556 $\operatorname{BS}(32)$ auf ein 16-Sortiernetzwerk reduziert wird. Bei anderen
1557 Größen, beispielsweise wenn man $\operatorname{BS}(64)$ auf ein
1558 32-Sortiernetzwerk reduziert, kann das Ergebnis sogar noch übertroffen werden,
1559 wie in Abbildung~\ref{fig:32-ec-from-bs64} zu sehen: Ein nach Batchers Methode
1560 konstruiertes Sortiernetzwerk benötigt 240~Komparatoren, ein aus den
1561 optimierten Mischern aufgebautes Netzwerk verbessert die Kosten auf
1562 208~Komparatoren. Das in Abbildung~\ref{fig:32-ec-from-bs64} dargestellte
1563 Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller
1564 dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die
1565 Geschwindigkeit dieser Sortiernetzwerke gleich ist.
1567 Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
1568 unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
1569 gute Schnittmuster anzugeben.
1571 Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
1572 Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
1573 Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
1574 Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
1575 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
1576 ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
1577 die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
1578 Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
1579 mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
1583 \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
1584 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}}
1585 \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
1586 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}}
1587 \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann
1588 der Algorithmus schnelle Sortiernetzwerke ausgeben.}
1589 \label{fig:11-12-ec-from-bs22-bs24}
1592 Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des
1593 \emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist,
1594 können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch
1595 effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die
1596 folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für
1597 \textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit
1598 der doppelten Leitungszahl. Die Abbildungen~\ref{fig:11-12-ec-from-bs22-bs24}
1599 und~\ref{fig:23-ec-from-bs46} zeigen beispielhaft ein 11-, 12- und
1600 23-Sortiernetzwerk, die aus \bs{22}, \bs{24} und \bs{46} generiert wurden.
1603 \begin{tabular}{|r|r|r|r|r|}
1605 Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
1606 & \textsc{SN-EC} & \textsc{SN-EC} & \bs{n} &
1609 11 & 37 & 9 & 39 & 10 \\
1610 12 & 42 & 9 & 46 & 10 \\
1611 19 & 93 & 13 & 98 & 14 \\
1612 20 & 102 & 13 & 106 & 14 \\
1613 % 20: # sn-cut 2:MAX 3:MIN 4:MIN 9:MIN 10:MIN 13:MIN 14:MIN 15:MIN 19:MIN 20:MAX 24:MAX 26:MIN 27:MAX 29:MIN 31:MAX 33:MIN 34:MAX 35:MIN 37:MIN 39:MAX
1614 21 & 109 & 14 & 114 & 15 \\
1615 22 & 116 & 14 & 123 & 15 \\
1616 23 & 124 & 14 & 133 & 15 \\
1623 \input{images/23-ec-from-bs46-fast.tex}
1625 \caption{23-Sortiernetzwerk mit 124~Komparatoren in 14~Schichten. Das
1626 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{46} mit dem
1627 Schnittmuster $\operatorname{MIN}(2, 4, 9, 12, 20, 22, 28, 30, 32, 33, 37,
1628 38, 41)$, $\operatorname{MAX}(1, 5, 16, 19, 21, 24, 25, 35, 36, 43)$
1630 \label{fig:23-ec-from-bs46}
1633 Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur
1634 haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere
1635 von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
1636 \emph{Odd-Even-Transpositionsort-Netzwerk} $\operatorname{OET}(n)$ und
1637 $m$~Schnitten gestartet, so ist das beste Ergebnis immer das
1638 $\operatorname{OET}(n-m)$-Netzwerk.
1640 \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
1642 Anders verhält sich das \emph{Pairwise-Sorting-Netzwerk}
1643 $\operatorname{PS}(n)$, das \textit{Ian Parberry} in seiner Arbeit „The
1644 Pairwise Sorting Network“ \cite{P1992} definiert. Startet man
1645 \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
1646 16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, das die gleiche
1647 Anzahl Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
1648 $\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
1649 Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
1653 \input{images/16-ec-from-ps32.tex}
1655 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
1656 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1657 \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
1658 $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
1659 \label{fig:16-ec-from-ps32}
1662 Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
1663 einsetzt und auch nicht auf einem Mischer basiert, ist das
1664 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
1665 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
1666 den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die
1667 strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die
1668 Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
1672 \input{images/32-pairwise-cut-16-pairwise.tex}
1674 \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu
1675 sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk
1677 \label{fig:ps16-from-ps32}
1680 Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
1681 regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
1682 schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
1683 einfache Schnittmuster
1685 \textit{Eingang}_i = \left\{ \begin{array}{rl}
1686 -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\
1687 \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\
1688 ? & \quad \mathrm{sonst}
1691 für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk
1692 $\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der
1693 dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das
1694 verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32}
1695 dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind
1696 diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden
1697 Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den
1698 „richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht
1699 werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende
1700 Netzwerk in schwarz gut zu erkennen.
1704 \input{images/16-pairwise.tex}
1706 \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
1707 ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das
1708 resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
1709 \label{fig:16-pairwise}
1712 Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf
1713 $\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein
1714 8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für
1715 größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise
1716 kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16}
1717 konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
1718 untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
1720 \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
1721 \label{sect:sn-evolution-cut:oes}
1723 In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
1724 viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
1725 $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$
1726 besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das
1727 \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen
1728 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es
1729 wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
1730 $\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese
1731 Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine
1732 Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes
1733 16-Schnittmuster findet.
1735 Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
1736 bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
1737 $\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
1738 8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
1739 Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
1740 Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
1744 \input{images/16-ec-from-oes32-cut.tex}
1746 \caption{Visualisierung eines 16-Schnittmusters, das auf
1747 $\operatorname{OES}(32)$ angewendet wieder ein schnelles und effizientes
1748 Sortiernetzwerk ergibt.}
1749 \label{fig:16-ec-from-oes32-cut}
1754 \input{images/16-ec-from-oes32.tex}
1756 \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
1757 Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution-Cut} aus dem
1758 \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(32)$ durch
1759 16~Schnitte erzeugt.}
1760 \label{fig:16-ec-from-oes32}
1763 Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
1764 4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
1765 Beobachtung kann man das regelmäßige Schnittmuster
1767 \textit{Eingang}_i = \left\{ \begin{array}{rl}
1768 \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
1769 -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
1770 ? & \quad \mathrm{sonst}
1773 ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
1774 Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
1775 Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
1776 32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
1777 ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
1781 \input{images/32-ec-from-oes64.tex}
1783 \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten.
1784 Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
1785 \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
1786 \label{fig:32-ec-from-oes64}
1789 Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
1790 erzeugten Sortiernetzwerke die Effizienz des
1791 \emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
1792 beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
1793 43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
1794 beider Sortiernetzwerke ist mit 10~Schichten identisch.
1796 Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
1797 und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
1798 verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
1799 Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
1800 22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
1801 Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
1802 Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
1803 werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
1804 gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
1805 werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
1806 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
1807 dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
1808 sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
1809 angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
1810 \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
1814 \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
1815 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
1816 \emph{Odd-Even-Mergesort}-Netzwerk generiert
1817 wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
1818 \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
1819 das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
1821 wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
1822 \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
1823 Ergebnis von der Bewertungsfunktion ab.}
1824 \label{fig:12-ec-from-oes24}
1827 Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
1828 findet Sortiernetzwerke, die schneller sind als das entsprechende
1829 \emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit
1830 22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige
1831 schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können,
1832 charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
1833 \emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
1835 \begin{tabular}{|r|r|r|r|r|}
1837 Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
1838 & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
1840 11 & 38 & 9 & 37 & 10 \\
1841 12 & 43 & 9 & 41 & 10 \\
1842 19 & 93 & 13 & 91 & 14 \\
1843 20 & 101 & 13 & 97 & 14 \\
1844 21 & 108 & 14 & 107 & 15 \\
1845 22 & 116 & 14 & 114 & 15 \\
1846 23 & 125 & 14 & 122 & 15 \\
1850 Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
1851 23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
1852 Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
1853 Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
1854 beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
1855 \bs{23} beziehungsweise \oes{23} eine Schicht einspart. Allerdings ist das
1856 Sortiernetzwerk auf Basis von \bs{46} (Abbildung~\ref{fig:23-ec-from-bs46})
1857 effizienter, da es nur 124~Komparatoren benötigt.
1861 \input{images/23-ec-from-oes46-fast.tex}
1863 \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten.
1864 Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
1865 Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
1866 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
1868 \label{fig:23-ec-from-oes46}
1872 \section{Der \textsc{SN-Markov}-Algorithmus}
1875 Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
1876 Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus
1877 einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
1878 ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
1879 verwendet und mit sich selbst kombiniert wird.
1881 Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk
1882 \emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
1883 Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke,
1884 die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit
1885 sich selbst und anschließendem Eliminieren der Hälfte der Leitungen hervorgehen
1886 können, heißen \emph{Nachfolger} von $S_0$.
1888 Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
1889 (gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
1890 Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
1891 Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von
1892 $S_0$ ist, das heißt, dass $S_1$ durch die Rekombination von $S_0$ mit sich
1893 selbst erzeugt werden kann.
1895 Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
1896 der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
1897 sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
1898 Nachfolger zwar noch unter 20.000, bei den untersuchten
1899 32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$
1900 unterschiedliche Schnittmuster geschätzt.
1902 Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
1903 zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
1904 gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
1905 gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
1906 selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der
1907 Algorithmus wie folgt beschreiben:
1914 Nachfolger := kombiniere (Netzwerk, Netzwerk)
1915 Netzwerk := Nachfolger
1921 Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der
1922 Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem
1923 zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der
1924 \textsc{SN-Markov}-Algorithmus auf einem entsprechenden
1925 \emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens
1926 1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der
1927 Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler
1928 erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende
1929 prozentuale Verteilung zu sehen.
1931 Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators}
1932 eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
1933 Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
1934 um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
1935 Beispielsweise war die kleinste erreichte Komparatorzahl bei
1936 16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$
1937 gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$
1938 und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem
1939 Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
1940 unter den Graphen angegeben.
1944 \subfigure[12 Leitungen, $k = 8,267$, $\theta = 0,962$, $\delta = 40$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-12-pct.pdf}}
1945 \subfigure[14 Leitungen, $k = 9,522$, $\theta = 0,867$, $\delta = 52$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-14-pct.pdf}}
1946 \subfigure[16 Leitungen, $k = 17,939$, $\theta = 1,091$, $\delta = 62$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-16-pct.pdf}}
1947 \subfigure[18 Leitungen, $k = 10,724$, $\theta = 0,766$, $\delta = 81$]{\includegraphics[viewport=0 0 425 262,width=7cm]{images/markov-comparators-18-pct.pdf}}
1948 \caption{Anzahl der Komparatoren von Sortiernetzwerken,
1949 die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet
1950 ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der
1951 gemessenen Daten darstellt.}
1952 \label{fig:markov-comparators}
1957 \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf}
1959 \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von
1960 \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem
1961 \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.}
1962 \label{fig:comparison-comparators}
1965 Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der
1966 \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
1967 \textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit
1968 \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl
1969 der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
1970 Startnetzwerk diente bei beiden Algorithmen das
1971 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
1972 x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
1973 ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
1974 wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je
1975 nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}.
1977 Sowohl der \textsc{SN-Markov}-Algorithmus, der das
1978 \emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
1979 \oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die
1980 bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind.
1981 Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger:
1982 Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit
1983 63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335
1984 \%$ rund 20~mal höher.
1986 Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem
1987 \emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist
1988 jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
1989 mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16}
1990 ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für
1991 Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein
1992 Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so
1993 vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
1994 Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das
1995 mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk
2000 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf}
2002 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
2003 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
2004 % \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.}
2005 % \label{fig:markov-comparators-14}
2010 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf}
2012 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
2013 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
2014 % \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.}
2015 % \label{fig:markov-comparators-16}
2020 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf}
2022 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen),
2023 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
2024 % \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.}
2025 % \label{fig:markov-comparators-18}
2030 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
2032 % \caption{Zyklen, die beim \textit{Random Walk} des
2033 % \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
2034 % Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
2035 % y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
2036 % Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
2037 % \label{fig:markov-cycles-16}
2041 \section{Fazit und Ausblick}
2043 Mit dem Entfernen von Leitungen aus bekannten Sortiernetzwerken lassen sich
2044 interessante Ergebnisse erzielen. Dies zeigte \textit{Moritz Mühlenthaler}
2045 bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und
2046 Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere
2047 interessante Beobachtungen machen lassen.
2049 Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution},
2050 \textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der
2051 Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres
2052 Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in
2053 Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt.
2055 Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den
2056 vorgestellten Algorithmen übertroffen werden. Der Algorithmus
2057 \textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und
2058 \textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und
2059 für ein 32-Sortiernetzwerk sogar noch übertreffen. Der
2060 \textsc{SN-Evolution}-Algorithmus fand 16-Sortiernetzwerke, die gegenüber dem
2061 Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen
2062 weiteren Komparator einsparen.
2064 Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen
2065 zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer
2066 Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das
2067 \emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden
2068 regelmäßige Schnittmuster angegeben. Diese ergeben Sortiernetzwerke, die so
2069 schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
2072 Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen
2073 Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich
2074 weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das
2075 bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
2076 Schnittmustern erreicht werden können.
2078 Die Möglichkeiten der Optimierung von Sortiernetzwerken mit
2079 \emph{Evolutionären Algorithmen} sind durch die in dieser Arbeit vorgestellten
2080 Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze
2081 umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknüpft
2084 \subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}
2086 Die aktuelle Implementierung von \textsc{SN-Evolution}
2087 (Abschnitte~\ref{sect:sn-evolution}
2088 beziehungsweise~\ref{sect:implementierung}) kann sowohl den \emph{bitonen
2089 Mischer} als auch den \emph{Odd-Even}-Mischer verwenden, um zwei Individuen zu
2090 rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen
2091 Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich
2092 selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von
2093 $\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
2094 die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
2095 Ausgabe sorgen. Anstelle von $\ps{\frac{n}{2}}$ können beliebige
2096 Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwendet werden.
2098 Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
2099 rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
2100 \emph{unterschiedliche} Schnittmuster gibt
2101 (Abschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
2102 Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider
2103 wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine
2104 $n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren
2105 $n$-Sortiernetzwerken als \ps{n} führen.
2107 \subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}}
2109 Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
2110 in~\cite{H1990} beschreibt, könnte man versuchen, die Algorithmen
2111 \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} zu kombinieren. Nach dem
2112 Zusammenfügen von zwei $n$-Sortiernetzwerken könnte der Algorithmus
2113 \textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
2114 \emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
2115 Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
2116 verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut}
2117 die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern.
2119 Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} --
2120 eine zweite Population von Schnittmustern evolvieren, die für die
2121 Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut
2122 funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge
2123 Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten
2124 Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster
2125 eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses}
2126 Schnittmuster zur nächsten Generation beiträgt. Im Gegensatz zum Ansatz der
2127 parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die
2128 das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern
2132 \section{Implementierung}
2133 \label{sect:implementierung}
2135 Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens
2136 entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen
2137 Kommandozeilen-Programmen durchgeführt. Die Bibliothek wurde unter der
2138 \textit{GNU Lesser General Public License} (LGPL) in der Version~2.1
2139 veröffentlicht; die Kommandozeilen-Programme, die in vielen Fällen lediglich
2140 Funktionalität der Bibliothek auf der Kommandozeile zur Verfügung stellen,
2141 stehen unter der \textit{GNU General Public License}, Version~2. Diese
2142 Lizenzen räumen einem Benutzer weitreichende Rechte ein, unter anderem das
2143 Programm beliebig zu verwenden, zu studieren, zu verändern sowie veränderte
2144 und unveränderte Kopien zu veröffentlichen.
2146 Die Programmierschnittstelle (API) der Bibliothek orientiert sich an
2147 Paradigmen der \textit{objektorientierten Programmierung}. Beispielsweise kann
2148 mit der Funktion \texttt{sn\_network\_ create()} ein neues Zustands-Objekt
2149 erzeugt werden, für das mehrere Manipulations-Methoden, zum Beispiel
2150 \texttt{sn\_network\_comparator\_add()}, zur Verfügung stehen. Auf diese Art
2151 und Weise kann die Bibliothek leicht erweitert werden, ohne dass bestehende
2152 Programme angepasst werden müssen.
2154 Die meisten Kommandozeilen-Programmen lesen ein Komparatornetzwerk von der
2155 Standard-Eingabe und schreiben ihr Ergebnis auf die Standard-Ausgabe. Um
2156 Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen
2157 Mergesort}-Netzwerks \bs{42} zu erzeugen, kann folgendes Kommando verwendet
2160 $ sn-bitonicsort 42 | sn-normalize >sn-42
2162 Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
2163 es einfach zu ermöglichen, Programme zu verketten, ist eines der
2164 Grundprinzipien des UNIX-Be\-triebs\-sys\-tems. Es hat sich in den letzten
2165 Jahrzehnten und beim Verfassen dieser Arbeit als sehr flexibel und mächtig
2168 Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden,
2169 sind unter anderem das Erzeugen des \emph{Odd-Even-Mergesort}-, \emph{bitonen
2170 Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von
2171 Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und
2172 Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das
2173 Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise
2174 wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex}
2177 \textit{libsortnetwork} kann unter der Web-Adresse
2178 \url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden.
2181 \bibliography{references}
2182 \bibliographystyle{plain}
2188 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 spelllang=de :