1 \documentclass[a4paper,11pt]{article}
2 \usepackage[utf8]{inputenc}
6 \usepackage{amsmath, bbm}
12 \usepackage[table]{xcolor}
13 %\usepackage{longtable}
14 \usepackage{subfigure}
18 \usetikzlibrary{arrows,shapes}
21 \usepackage{mathtools}
23 \geometry{paper=a4paper,margin=30mm}
27 %\fancyhead[LO,LE]{"Ubung zu Computational Intelligence}
28 %\fancyhead[CO,CE]{2006-05-15}
29 %\fancyhead[RO,RE]{Florian Forster (2099894)}
31 \title{Evolutionäre Optimierung von Sortiernetzwerken}
32 \author{Florian Forster}
35 \newcommand{\false}{\textsc{False}}
36 \newcommand{\true}{\textsc{True}}
37 \newcommand{\todo}[1]{{\bf TODO:} #1}
38 \newcommand{\qed}{\hfill $\Box$ \par \bigskip}
40 \newcommand{\oes}[1]{\ensuremath{\operatorname{OES}\left(#1\right)}}
41 \newcommand{\bs}[1]{\ensuremath{\operatorname{BS}\left(#1\right)}}
42 \newcommand{\ps}[1]{\ensuremath{\operatorname{PS}\left(#1\right)}}
43 \newcommand{\oem}[1]{\ensuremath{\operatorname{OEM}\left(#1\right)}}
44 \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}}
45 \newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}}
47 \newcommand{\gcell}{\cellcolor{green!10}}
48 \newcommand{\Gcell}{\cellcolor{green!10!white!95!black}}
50 \newtheorem{definition}{Definition}
51 \newtheorem{satz}{Satz}
53 % Zeige Nummern nur bei referenzierten Gleichungen an.
54 \mathtoolsset{showonlyrefs=true}
58 \tikzstyle{vertex} = [circle,draw,thick,fill=black,minimum size=5,inner sep=0pt]
59 \tikzstyle{comp} = [draw,thick,-]
60 \tikzstyle{compup} = [draw,thick,->]
61 \tikzstyle{compdown} = [draw,thick,<-]
62 \tikzstyle{edge} = [draw,thick,-]
63 \tikzstyle{diredge} = [draw,thick,->]
64 \tikzstyle{prob} = [font=\tiny]
66 \tikzstyle{edge minimum} = [edge,color=blue!20]
67 \tikzstyle{edge maximum} = [edge,color=red!20]
68 \tikzstyle{vertex active minimum} = [vertex,color=blue!50, fill=blue!50]
69 \tikzstyle{vertex active maximum} = [vertex,color=red!50, fill=red!50]
70 \tikzstyle{vertex active minimum maximum} = [vertex,color=violet!50, fill=violet!50]
71 \tikzstyle{vertex inactive minimum} = [vertex,color=blue!20, fill=blue!20]
72 \tikzstyle{vertex inactive maximum} = [vertex,color=red!20, fill=red!20]
73 \tikzstyle{vertex inactive minimum maximum} = [vertex,color=black!20, fill=black!20]
74 \tikzstyle{comp active minimum} = [comp]
75 \tikzstyle{comp active maximum} = [comp]
76 \tikzstyle{comp active minimum maximum} = [comp,color=black!20]
77 \tikzstyle{comp inactive minimum} = [comp,color=blue!20]
78 \tikzstyle{comp inactive maximum} = [comp,color=red!20]
79 \tikzstyle{comp inactive minimum maximum} = [comp,color=black!20]
81 \tikzstyle{red box} = [draw,-,color=red, top color=red!2,bottom color=red!10]
82 \tikzstyle{blue box} = [draw,-,color=blue,top color=blue!2,bottom color=blue!10]
83 \tikzstyle{green box} = [draw,-,color=teal,top color=teal!2,bottom color=teal!10]
84 \tikzstyle{gray box} = [draw,-,color=black, top color=black!2,bottom color=black!10]
88 Sortiernetzwerke erweisen sich als sehr schwieriges Optimierungsproblem. Zwar
89 ist das Konzept leicht verständlich und schnell erklärt, effiziente und
90 schnelle Sortiernetzwerke zu finden oder zu konstruieren bleibt aber eine
93 Diese Arbeit verwendet „Schnitte“ oder „Leitungselimination“ und
94 Mischer-Netz\-werke, um evolutionäre Algorithmen anzugeben, deren Individuen
95 die Menge der gültigen Sortiernetzwerke nie verlassen. Bisherige Ansätze
96 bewegten sich in der Regel in der Menge aller Komparatornetzwerke und suchten
97 dort nach Sortiernetzwerken. Nach dem Vorstellen der zwei Algorithmen
98 \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} sowie einiger Ergebnisse,
99 die mit diesen Algorithmen erzielt werden konnten, wird -- basierend auf dem
100 evolutionären Algorithmus \textsc{SN-Evolution} -- eine Markov-Kette für
101 Sortiernetzwerke angegeben.
108 \section{Motivation und Einleitung}
110 \subsection{Motivation}\label{sect:motivation}
112 \emph{Sortiernetzwerke} sind ein theoretisches Konstrukt, dass auch von
113 Personen ohne Zugang zum Thema, beziehungsweise der theoretischen Informatik,
114 schnell verstanden werden kann. Eine Einführung wird in
115 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} gegeben. Nichtsdestotrotz ist
116 das Finden von Sortiernetzwerken sowie das Beweisen, dass ein
117 Komparatornetzwerk jede beliebige Eingabe sortiert, im Allgemeinen sehr
118 schwierig und nach heutigem Kenntnisstand nur mit exponentiellem Aufwand zu
121 Einfacher ist der Korrektheitsbeweis bei konstruktiven Verfahren, da hier die
122 Konstruktionsvorschrift genutzt werden kann, um die Korrektheit für beliebige
123 Eingabegrößen zu beweisen. Im Abschnitt~\ref{sect:konstruktive_netzwerke}
124 geschieht dies beispielsweise für zwei von \emph{Kenneth~E. Batcher} 1968
125 gefundene Konstruktionsvorschriften.
127 Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon wiederholt
128 Computer und automatische Suchverfahren eingesetzt. Bisherige Ansätze
129 versuchen meist in der Menge aller Komparatornetzwerke jene zu finden, die
130 die Sortiereigenschaft besitzen und aus wenigen Komparatoren bestehen. Die
131 Eigenschaft, jede Eingabepermutation zu sortieren, ist also ein
132 Optimierungsziel und nicht durch das Vorgehen gewährleistet. Dafür können
133 theoretisch alle Sortiernetzwerke durch diese Algorithmen gefunden werden --
134 genügend Laufzeit vorausgesetzt.
136 In dieser Arbeit werden Methoden verwendet, die die Menge der Sortiernetzwerke
137 nie verlassen, dafür aber auch nicht alle existierenden Sortiernetzwerke
138 erzeugen können. So muss für ein gefundenes Komparatornetzwerk nicht mehr
139 nachgewiesen werden, dass es jede beliebige Eingabe sortiert, weil diese
140 Eigenschaft durch das Verfahren sichergestellt ist.
142 \subsection{Einleitung}\label{sect:einleitung}
144 \subsubsection{Sortiernetzwerke}\label{sect:einleitung_sortiernetzwerke}
146 \emph{Komparatoren} sind die Bausteine, die \emph{Komparatornetzwerken}
147 zugrunde liegen. Sie haben zwei Eingänge über die sie zwei Zahlen erhalten
148 können und zwei Ausgänge, auf denen die Zahlen wieder ausgegeben werden. Dabei
149 sind die Ausgänge im Gegensatz zu den Eingängen unterscheidbar, da die größere
150 der beiden Zahlen immer auf dem einen, die kleinere der beiden Zahlen
151 immer auf dem anderen Ausgang ausgegeben wird.
153 Kombiniert man mehrere \emph{Komparatoren} in der Form miteinander, dass die
154 Ausgänge eines Komparators mit Eingängen weiterer Komparatoren verbunden sind,
155 erhält man ein {\em Komparatornetzwerk}.
159 \input{images/einfaches_komparatornetzwerk.tex}
161 \caption{Einfaches Komparatornetzwerk mit vier Ein- beziehungsweise Ausgängen, bestehend
163 \label{fig:einfaches_komparatornetzwerk}
166 Abbildung~\ref{fig:einfaches_komparatornetzwerk} zeigt ein einfaches
167 \emph{Komparatornetzwerk} aus fünf Komparatoren. Insgesamt gibt es vier
168 verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch
169 eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die
170 \emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je
171 zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von
172 \emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichtlichkeit
173 durch schwarze Punkte symbolisiert.
175 Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in
176 das Netzwerk hinein gegeben. Jeder Komparator vergleicht die Zahlen „auf“ den
177 beiden Leitungen, die er verbindet. Nach einem Komparator befindet sich die
178 kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl
179 befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat. Wenn in
180 einem Komparatornetzwerk alle Komparatoren in die gleiche Richtung zeigen --
181 die Konvention in dieser Arbeit ist, dass das Minimum auf der unteren Leitung
182 ausgegeben wird -- werden die Pfeile durch einfache Linien ersetzt. Zu diesen
183 sogenannten \emph{Standard-Netzwerken} siehe auch
184 Abschnitt~\ref{sect:normalisieren}.
186 Komparatoren, die \emph{unterschiedliche} Leitungen miteinander vergleichen,
187 können gleichzeitig angewendet werden. Das Beispiel in
188 Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und
189 vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine
190 Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man
191 eine \emph{Schicht} des Komparatornetzwerks. Die \emph{Geschwindigkeit} eines
192 Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die
193 sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der
194 benötigten parallelen Schritte darstellt.
196 \emph{Komparatornetzwerke}, die für \emph{jede} Eingabefolge eine Ausgabe
197 erzeugen, die der Sortierung der Eingabe entspricht, heißen
198 \emph{Sortiernetzwerke}. Das in
199 Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk
200 ist \emph{kein} Sortiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur
201 Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar
206 \input{images/09-e2-c24-allbut1.tex}
208 \caption{Ein \emph{Komparatornetzwerk} mit neun Eingängen und
209 24~Komparatoren, die in 8~Schichten angeordnet sind. Das Netzwerk sortiert
210 alle Eingaben, bei denen das Minimum nicht auf dem mittleren Eingang liegt.}
211 \label{fig:09-e2-c24-allbut1}
213 Zu beweisen, dass ein gegebenes Komparatornetzwerk die Sortiereigenschaft {\em
214 nicht} hat, ist mit einem gegebenen Gegenbeispiel einfach möglich. Das
215 Komparatornetzwerk wird auf das Gegenbeispiel angewendet und anschließend wird
216 überprüft, ob die Ausgabe sortiert ist. Ist sie es nicht, heißt das, dass es
217 mindestens eine Eingabefolge gibt, die nicht sortiert wird. Entsprechend der
218 Definition handelt es sich bei dem \emph{Komparatornetzwerk} folglich
219 \emph{nicht} um ein \emph{Sortiernetzwerk}. Ein solches Gegenbeispiel für ein
220 gegebenes Komparatornetzwerk zu finden ist nach heutigem Kenntnisstand jedoch
221 nicht \emph{effizient}\footnote{In diesem Zusammenhang heißt \emph{effizient},
222 dass keine Algorithmen bekannt sind, die eine polynomielle Laufzeit (in
223 Abhängigkeit von der Eingabelänge) haben.} möglich.
225 Beispielsweise sortiert das im Rahmen dieser Arbeit entdeckte
226 Komparatornetzwerk in Abbildung~\ref{fig:09-e2-c24-allbut1} viele der 362.880
227 möglichen Eingabepermutationen. Mit dem Gegenbeispiel $(3, 5, 2, 1, 0, 7, 4,
228 8, 6)$ lässt sich jedoch leicht beweisen, dass das Komparatornetzwerk die
229 Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1,
230 0, 2, 3, 4, 5, 6, 7, 8)$ ausgibt.
232 Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein
233 Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese
234 Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$
235 über-exponentiell schnell, so dass ein Ausprobieren aller möglichen
236 Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen
237 ist.\footnote{1.307.674.368.000 Permutationen}
239 \label{sect:0-1-prinzip}
240 Glücklicherweise reicht es aus, alle möglichen 0-1-Folgen zu überprüfen, wie
241 \textit{Donald~E. Knuth} in \cite{KNUTH} zeigt. Die Beweisidee ist folgende:
242 Angenommen ein Komparatornetzwerk sortiert alle 0-1-Folgen und es gibt eine
243 Permutation $E = (e_0, \dots, e_{n-1})$ beliebiger Zahlen, die nicht sortiert
244 wird. Die Ausgabefolge sei $A = (a_0, \dots, a_{n-1})$. Sei $i$ eine Position
245 in der Ausgabe, die die Sortierbedingung verletzt:
247 a_0 \leqq a_1 \leqq \dots \leqq a_{i-1} > a_i \dots
249 Die Eingabe kann mittels
257 auf eine 0-1-Folge abgebildet werden, die entsprechend der Annahme vom
258 Komparatornetzwerk sortiert wird. Allerdings verändert diese Abbildung das
259 Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine
260 Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen
261 wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso
262 vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen
263 zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$
264 oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei
265 gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich
266 der Komparator so verhält, wie er sich bei der Permutation verhalten hat --
267 ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$
268 und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im
269 Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.
271 Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
273 $\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
274 ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$
275 verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
276 schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
277 ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
278 sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für
279 aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung
280 eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa
281 4,3~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten
284 \subsubsection{Evolutionäre Algorithmen}
286 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
287 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
288 $\mathcal{NP}$. Das heißt, dass keine Verfahren bekannt sind, die diese
289 Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese Probleme
290 außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine Konsequenz,
291 dass es effiziente exakte Algorithmen für diese Probleme nicht gibt. Falls
292 sich hingegen herausstellt, dass diese Probleme neben $\mathcal{NP}$ auch in
293 der Komplexitätsklasse~\textit{P} liegen, gibt es effiziente Algorithmen. Es
294 ist jedoch wahrscheinlich, dass die Zeitkonstanten solcher Algorithmen sehr
295 groß sein würden, so dass der praktische Nutzen fraglich bleibt.
297 Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt
298 die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen
299 Lösungen}, als einzige Ausgabe des Algorithmus zuzulassen, wird eine
300 "`möglichst gute"' Lösung ausgegeben. Viele dieser Optimierungsalgorithmen
301 orientieren sich an Vorgängen in der Natur. Beispielsweise imitieren die
302 „Ameisenalgorithmen“ das Verhalten von Ameisen auf der Futtersuche, um kurze
303 Rundreisen auf Graphen zu berechnen.
305 Bei {\em Evolutionären Algorithmen} stand die Evolution Pate. Die Grundidee
306 ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
307 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
308 Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em
309 Individuen} bezeichnet.
311 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben: Aus einer
312 bestehenden Lösungsmenge, der {\em Population}, werden zufällig Lösungen
313 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
314 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
315 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
316 eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der
317 {\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
318 werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
321 Nicht alle Probleme eignen sich für diese Strategie. Zum einen muss es möglich
322 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
323 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
324 es oft einfach ist, {\em irgendeine} Lösung anzugeben. Die angegebenen
325 Algorithmen verwenden als einfache initiale Lösung häufig das
326 \emph{Odd-Even-Transpositionsort}-Netzwerk, das in
327 Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
328 muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
329 problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen. Die in
330 dieser Arbeit verwendeten Rekombinationsmethoden sind so gewählt, dass die
331 Nebenbedingungen nicht verletzt werden.
333 Beim Aussuchen von zufälligen Lösungen aus der Population, der
334 \emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
335 bevorzugt werden, hat einen starken Einfluss auf das Verhalten des
336 Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus
337 schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch
338 für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus
339 schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale
340 Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
341 erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
342 \textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
343 zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
344 findet er aber in der Regel bessere Lösungen.
346 Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
347 Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
348 nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
349 eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
350 beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
351 zwischen verschiedenen Leitungszahlen stark unterscheiden.
353 Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
354 unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
355 \emph{Mutation}. Dabei werden Lösungen zufällig verändert, so dass auch andere
356 Lösungen „in der Nähe“ von direkten Nachfolgern erreicht werden können. Das
357 hilft insbesondere bei der intensiven Suche in der Nähe eines lokalen Optimums
358 aber auch beim „Ausbrechen“ aus lokalen Optima und finden noch besserer
361 Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
362 verbunden, dass anschließend die Sortiereigenschaft des resultierenden
363 \emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
364 Hinzufügen eines zufälligen Komparators diese Eigenschaft zer\-stö\-ren kann.
365 Beim Suchen möglichst effizienter Netzwerke ist das zufällige Entfernen von
366 Komparatoren interessanter, was die Sortiereigenschaft fast immer aufhebt.
368 Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
369 die \emph{Sortiernetzwerke} selbst, sondern verzichten entweder ganz auf
370 Mutation oder mutieren lediglich Transformationen von Sortiernetzwerken, die
371 die Sortiereigenschaft erhalten. Transformationen von Sortiernetzwerken werden
372 in Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der
373 Mutation einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
375 \begin{figure} \begin{center} \input{images/16-hillis.tex} \end{center}
376 \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
377 Es besteht aus 61~Komparatoren in 11~Schichten.} \label{fig:16-hillis}
378 \end{figure} Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
379 Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
380 \emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
381 zu optimieren~\cite{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
382 daran gemessen, bei wie vielen Komparatornetzwerken sie beweisen konnten, dass
383 sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen
384 (Komparatornetzwerken) nicht alle 0-1-Folgen, sondern nur erfolgreiche
385 Parasiten (schwierige Eingaben) überprüft werden. Auf diese Art und Weise
386 gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
387 anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
391 \subfigure{\input{images/13-juille-0.tex}}
392 \subfigure{\input{images/13-juille-1.tex}}
393 \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des
394 END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in
396 \label{fig:13-juille}
398 \textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
399 Non-Determinism} (END) nannte~\cite{J1995}. Dabei handelt es sich nicht um
400 einen der \emph{Evolutionären Algorithmen}, wie sie hier vorgestellt wurden,
401 sondern um eine verteilte, probabilistische Breitensuche, die an die
402 \emph{Strahlsuche} (englisch: \textit{beam search}), ein Verfahren der
403 Künstlichen Intelligenz, angelehnt ist. Die aufwendigste Operation bei diesem
404 Ansatz ist die Bewertungsfunktion, die abschätzt, wie viele Komparatoren zu
405 einem Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
406 erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
407 anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
408 bekannten (Abbildung~\ref{fig:13-juille}).
411 \section[Konstruktionsverfahren]{Konstruktionsverfahren für Sortiernetzwerke}
412 \label{sect:konstruktive_netzwerke}
414 Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere ein
415 häufig verwendeter Baustein, sogenannte \emph{Mischer}\footnote{Eine
416 Fehlübersetzung aus dem Englischen, von \textit{to~merge} (Deutsch:
417 zusammenfügen). Da der Begriff des "`mischens"' beziehungsweise der
418 "`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
419 in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
420 beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
421 Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
423 % \todo{Drei oder vier Verfahren?}
425 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
426 \label{sect:odd_even_transpositionsort}
428 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
429 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
430 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
431 Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für
436 \input{images/oe-transposition-8.tex}
438 \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.}
439 \label{fig:odd-even-transposition-08}
442 Dass das \emph{Odd-Even-Transpositionsort}-Netzwerk tatsächlich jede beliebige
443 Eingabe sortiert, ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
444 sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
445 Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt.
447 Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
448 indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
449 Herausschneiden einer Leitung reduziert. In
450 Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
451 beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
452 Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. Die Rekursion endet
453 beim \emph{Odd-Even-Transpositionsort}-Netzwerk mit drei Eingängen, bei dem
454 das Minimum auf der untersten, das Maximum auf der obersten und der mittlere
455 Wert auf der mittleren Leitung landet. Folglich ist die Ausgabe bei
456 $\operatorname{OET}(3)$ sortiert.
458 Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
459 Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
460 sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
461 (n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
462 Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
463 ($\Theta(n \log (n)^2)$), die in weniger Schichten,
464 ($\Theta(\log (n)^2)$), angeordnet sind.
466 Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
467 folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
468 Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
469 finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
472 Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer,
473 beziehungsweise mehrerer Leitungen, um die Anzahl der Leitungen eines
474 Sortiernetzwerks zu reduzieren. Die Technik wird in Detail im
475 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
477 \subsection{Das bitone Mergesort-Netzwerk}
479 Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
480 Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
481 veröffentlicht wurde. Es ist deutlich effizienter als das
482 Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
483 Komparatoren als auch der benötigten Zeit, also der Anzahl der Schichten.
485 Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
486 sortierte Listen zusammenfügen (Englisch: \textit{to~merge}) kann. Dieser
487 \emph{„bitone Mischer“} (Englisch: \textit{bitonic merger}) genannte Baustein
488 verleiht dem Sortiernetzwerk seinen Namen.
490 Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
491 Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
492 Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
494 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
496 Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen
497 Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine
498 beliebige \emph{bitone Folge} in eine sortierte Liste umordnen kann. Eine
499 \emph{bitone Folge} ist eine monoton steigende Folge, gefolgt von einer
500 monoton absteigenden Folge, oder ein zyklischer Shift davon.
501 Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten,
502 die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das
503 \emph{bitone Mergesort}-Netzwerk zeigen die
504 Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie
505 erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste
506 aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass
507 das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) beziehungsweise
508 kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge
513 \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
514 \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
515 \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
516 \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
517 \caption{Beispiele bitoner Folgen.}
518 \label{fig:beispiel-biton}
523 \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
525 \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
526 \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
527 aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
528 der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
529 resultierenden Teilfolgen sind wiederum biton.}
530 \label{fig:bitonic-merge-schema}
533 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
534 ${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
535 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
536 sortiert, die Folge $V$ sei absteigend sortiert:
538 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
539 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
541 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
542 Positionen verglichen und ggf. vertauscht:
544 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
546 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
547 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
548 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
549 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
550 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
551 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
552 "`linken"' Folge $u_{m-1}$ kleiner ist als das kleinste Element der
553 "`rechten"' Folge $v_{m-1}$. Daraus folgt, dass sich das Resultat in zwei
554 bitone Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
555 absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
556 zeigt die Situationen vor und nach diesem Schritt des Mischers schematisch.
558 Um die Folge vollständig zu sortieren, müssen anschließend die beiden
559 resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
560 mithilfe des bitonen Mischers, mit zwei Instanzen von
561 $\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem
562 bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als
563 Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
566 Der bitone Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
567 lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
568 notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
569 „echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
570 Schema des bitonen Mischers für zwei aufsteigend sortierte Folgen. Durch das
571 Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
572 Statt an eine Treppe erinnert das Muster nun an einen Trichter.
574 Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
575 die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
576 $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
577 $\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren
578 besteht, die in $\log(n)$~Schichten angeordnet werden können.
580 \subsubsection{Das bitone Mergesort-Netzwerk}
582 Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
583 Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
584 zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe
585 $\bs{\frac{n}{2}}$ für je die Hälfte der Eingänge, sowie dem bitonen Mischer
586 für $n$~Leitungen $\operatorname{BM}(n)$. Das Rekursionsende ist das bitone
587 Mergesort-Netzwerk mit nur einer Leitung $\operatorname{BS}(1)$, welches als
588 leeres Komparatornetzwerk definiert ist. Entsprechend sind die
589 Komparatornetzwerke $\operatorname{BM}(2)$ und $\operatorname{BS}(2)$
592 Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
593 (Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
594 rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so
595 alle Komparatoren in die gleiche Richtung zeigen.
599 \input{images/batcher-8.tex}
601 \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~Eingänge.
602 Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden bitonen
603 Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven
604 Schritt hinzugefügt wurden (grün).}
605 \label{fig:bitonic-08}
608 Das Sortiernetzwerk~$\operatorname{BS}(8)$ ist in
609 Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
610 beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
611 Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
612 die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
615 Das \emph{bitone Mergesort}-Netzwerk mit einer Leitungszahl $n = 2^d$, die
616 eine Zweierpotenz ist, besteht aus $\frac{1}{4} n \log(n) \log(n+1) =
617 \Theta\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2}
618 \log(n) \log(n+1) = \Theta(\log(n)^2)$ Schichten angeordnet sind.
620 \subsection{Das Odd-Even-Mergesort-Netzwerk}
622 Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort}-Netzwerk
623 (OES) und das \emph{Odd-Even-Transpositionsort}-Netzwerk (siehe
624 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
625 OES dem \emph{bitonen Mergesort}-Netzwerk, das im vorherigen Abschnitt
626 vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
627 \textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
628 beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
629 darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
631 \subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer}
633 Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein
634 Komparatornetzwerk, das zwei sortierte Folgen mit $n$ beziehungsweise $m$
635 Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
636 zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
637 \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
638 vorgestellt wurde. Im allgemeinen Fall, wenn die Anzahl der Leitungen keine
639 Zweierpotenz ist, kann das \emph{bitonic-Merge}-Netzwerk schneller sein
640 als das \emph{Odd-Even-Merge}-Netzwerk.~\cite{KNUTH}
642 Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die
643 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
644 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
645 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
646 $W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
648 w_i = \left\{ \begin{array}{ll}
657 \input{images/oe-merge.tex}
659 \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die
660 beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$,
661 die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der
662 Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt
663 dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den
664 rekursiven Aufbau verstärkt.}
668 Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der
669 geraden Indizes und je eine Liste der ungeraden Indizes.
671 U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
672 U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
673 V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
674 V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
677 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$,
678 beziehungsweise die ungeraden Folgen $U_{\textrm{ungerade}}$ und
679 $V_{\textrm{ungerade}}$ werden rekursiv von kleineren \emph{Odd-Even}-Mischern
680 zusammengefügt, so dass sich am Ausgang der Mischer die Folgen
682 W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
683 W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
687 Anschließend werden die Komparatoren zwischen benachbarten Leitungen
690 w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
692 die die Folge~$W$ sortieren. Den schematischen Aufbau des
693 \emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}.
695 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
696 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
697 entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
698 offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
701 \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
702 \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
703 einzelnen Komparator.
706 Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge
707 sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den
708 geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise
709 $V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den
710 ungeraden Teilfolgen $U_{\textrm{ungerade}}$ beziehungsweise
711 $V_{\textrm{ungerade}}$ --~die Einsen verhalten sich entsprechend umgekehrt.
712 Das trifft demnach auch auf die Folgen $W_{\textrm{gerade}}$ und
713 $W_{\textrm{ungerade}}$ entsprechend zu:
715 \left|W_{\textrm{gerade}}\right|_0
716 &=& \left|U_{\textrm{gerade}}\right|_0
717 + \left|V_{\textrm{gerade}}\right|_0
718 = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
719 + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
720 \left|W_{\textrm{ungerade}}\right|_0
721 &=& \left|U_{\textrm{ungerade}}\right|_0
722 + \left|V_{\textrm{ungerade}}\right|_0
723 = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
724 + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
726 Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
727 als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
728 Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
729 wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält als
730 $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
731 Ausgabe zu sortieren. Diese wird von den Komparatoren ausgeführt, die
732 benachbarte Leitungen miteinander vergleichen. Die jeweiligen Situationen sind
733 in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
737 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
739 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
741 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
742 \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
743 kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der
744 Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
745 letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
747 \label{fig:oe-post-recursive}
750 Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
751 bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$
752 Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
753 Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
754 Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
756 Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
757 allgemeinen Fall verwendet, hängt gemäß der rekursiven Definition von der
758 Länge der Eingabefolgen, $n$ und $m$ ab:
760 K(n,m) = \left\{ \begin{array}{ll}
761 nm, & \mathrm{falls} \quad nm \leqq 1 \\
762 K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right)
763 + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right)
764 + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1
767 Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
768 anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
769 dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.
771 Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
772 Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
773 erste Rekursionsschritt der OEM-Konstruktion fügt
774 $\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
775 Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
776 diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer
777 $\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
778 einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
779 \frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
781 \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1
783 Komparatoren eingespart. Damit ergibt sich
785 K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
787 für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
790 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
792 Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ besteht, wie
793 das \emph{bitone Mergesort}-Netzwerk, rekursiv aus kleineren Varianten von
794 sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die
795 effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
796 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
797 \oes{n} aus $\oes{\left\lceil\frac{n}{2}\right\rceil}$,
798 $\oes{\left\lfloor\frac{n}{2}\right\rfloor}$ und
799 $\oem{\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor}$.
800 Die Rekursion endet mit $\operatorname{OES}(1)$ und $\operatorname{OES}(0)$,
801 die als leere Komparatornetzwerke definiert sind.
805 \input{images/oe-mergesort-8.tex}
807 \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~Eingänge. Markiert
808 sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
809 \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade
810 Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
811 Komparatoren zwischen benachbarten Leitungen (grün).}
812 \label{fig:odd-even-mergesort-08}
815 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
816 zu sehen. Rot markiert sind die beiden rekursiven Instanzen
817 $\operatorname{OES}(4)$. Die anderen Blöcke stellen den
818 \emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind
819 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
820 die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.
822 Im Allgemeinen ist die Anzahl der Komparatoren, die vom
823 \emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der
824 Definition, beziehungsweise der Konstruktionsanleitung abzulesen:
826 k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
827 + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
828 + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
830 Da es schwierig ist für $K(n,m)$ eine geschlossene Form anzugeben, ist eine
831 geschlossene Darstellung von $k(n)$ ebenfalls nicht ohne weiteres möglich. Es
832 ist allerdings bekannt, dass $k(n)$ in $\Theta\left(n \left(\log
833 (n)\right)^2\right)$ enthalten ist.
835 Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
836 Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
837 Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
839 k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
844 % 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))
845 % oem1(n) = oem(ceil(.5*n),floor(.5*n))
846 % oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
849 %\item Pairwise sorting-network
852 \subsection{Das Pairwise-Sorting-Netzwerk}
854 Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
855 für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
856 Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
857 Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
858 \emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
859 das \emph{Odd-Even-Mergesort}-Netzwerk.
862 \section{Transformation von Sortiernetzwerken}
863 \label{sect:tranformation}
865 \subsection{Komprimieren}
867 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
868 gleichzeitig ausgewertet werden, wie bereits in
869 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
870 Transformationen, insbesondere das Entfernen einer Leitung wie in
871 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben, kann es vorkommen, dass
872 die Komparatoren eines Sortiernetzwerks nicht mehr in der kleinstmöglichen
873 Anzahl von \emph{Schichten} angeordnet sind. Unter \emph{Komprimierung} wird
874 eine (Neu-)Gruppierung der Komparatoren verstanden, die jeden Komparator so
875 früh wie möglich ausführt. So entsteht die kleinstmögliche Anzahl von
876 \emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
878 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
879 Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
880 beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
881 Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
882 die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
883 Komprimierung durchgeführt werden.
885 \subsection{Normalisieren}
886 \label{sect:normalisieren}
890 \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
891 \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
892 \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
893 transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
894 intuitiven Konstruktion und die normalisierte Variante.}
895 \label{fig:beispiel_normalisieren}
898 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
899 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
900 zeigen.\footnote{Die Konvention in dieser Arbeit ist, dass in diesem Fall alle
901 Pfeile nach unten zeigen. Das Minimum wird auf der untersten, das Maximum auf
902 der obersten Leitung ausgegeben.} Jedes Sortiernetzwerk kann in eine
903 normaliesierte Variante transformiert werden. Dazu gibt beispielsweise
904 \emph{Donald~E. Knuth} in~\cite{KNUTH} einen Algorithmus an.
906 Abbildung~\ref{fig:beispiel_normalisieren} stellt das \emph{bitone
907 Mergesort}-Netzwerk in zwei Varianten dar. Abbildung~\ref{fig:bitonic-nonstd}
908 zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
909 Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
910 die untere und die obere Hälfte gegenläufig sortiert. Das heißt, dass nach
911 drei Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert
912 ist. In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der
913 rekursiven Definition.
915 In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
916 Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die selbe
917 Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen-
918 und das Trichtermuster zu sehen.
920 \subsection{Zwei Netzwerke kombinieren}
922 Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden
923 zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
924 Sortiernetzwerk zusammenzufassen.
926 Diese Technik wurde in den vorangegangen Abschnitten bereits verwendet,
927 beispielsweise um zwei \emph{bitone Mergesort}-Netzwerke mit jeweils der
928 halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
929 einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
930 \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ wurde auf diese Art
931 und Weise rekursiv aufgebaut.
933 Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
934 Folgen. \emph{Wie} diese Folgen sortiert wurden ist unerheblich. Entsprechend
935 können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
936 zu sortieren und die Ausgaben mit einem der beschriebenen Mischer
939 Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
940 $\operatorname{BS}(8)$ mit je 8~Leitungen mit dem
941 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
942 Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
943 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
944 80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
946 Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren),
947 beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“
948 Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk.
949 Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt
950 beispielsweise 26~Komparatoren, die in neun Schichten angeordnet sind. Es sind
951 allerdings Sortiernetzwerke mit neun Eingängen bekannt, die lediglich
952 25~Komparatoren in sieben Schichten benötigen. Kombiniert man zwei dieser
953 Netzwerke mit dem \emph{Odd-Even}-Mischer erhält man ein Sortiernetzwerk mit
954 18~Eingängen, das 80~Komparatoren in 11~Schichten benötigt.
955 $\operatorname{OES}(18)$ benötigt 82~Komparatoren in 13~Schichten. Damit ist
956 das resultierende Netzwerk genauso schnell wie das Sortiernetzwerk mit
957 18~Eingängen, das \textit{Sherenaz~W. Al-Haj Baddar} und \textit{Kenneth~E.
958 Batcher} in ihrer Arbeit „An 11-Step Sorting Network for
959 18~Elements“~\cite{BB2009} vorstellen, benötigt aber 6~Komparatoren weniger.
961 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
962 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
963 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
964 Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die
965 letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen
966 die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
967 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
968 nur mit exponentiellem Aufwand möglich ist.
970 \subsection{Leitungen entfernen}
971 \label{sect:leitungen_entfernen}
973 Im vorherigen Abschnitt wurde gezeigt, dass es mithilfe von \emph{Mischern}
974 möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
975 ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
976 beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
977 sich die Anzahl der Eingänge nicht verändert. Es soll wieder ein
978 Sortiernetzwerk mit $n$~Eingängen entstehen.
980 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
981 Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
982 „eliminiert“. Dazu wird angenommen, dass das Minimum oder das Maximum an einem
983 bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das
984 Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an
985 einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten
986 Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und
987 welche dafür sorgen, dass der Wert die Leitung wechselt, da das Minimum jeden
988 Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
989 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
990 das \emph{Odd-Even-Transpositionsort}-Netzwerk.
992 Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf
993 dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk
994 eindeutig festgelegt.
998 \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
999 durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
1000 \subfigure[Komparatoren, die einen Wechsel der Leitungen bewirken, werden
1001 durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
1002 \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit
1003 7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
1004 \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die
1005 Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
1006 \caption{Eine Leitung wird aus dem
1007 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
1008 markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
1009 nach unten weiter gegeben wird, ist der Pfad fest vorgegeben. Da die
1010 restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
1011 Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
1012 \label{fig:oe-transposition-cut}
1015 Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht,
1016 beziehungsweise ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der
1017 Leitung geführt haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
1018 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
1019 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
1020 ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
1021 das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
1022 die keine Komparatoren mehr berührt
1023 (Abbildung~\ref{fig:oe-transposition-cut1}).
1025 Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
1026 Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die
1027 \emph{Position} des Minimums oder des Maximums in der Eingabe angenommen. Ein
1028 Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher
1029 Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese
1030 Annahme auszuwerten -- über die verbleibenden Eingänge wurde keine Aussage
1031 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
1032 mit $(n-1)$~Elementen darstellen.
1034 Wird die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
1035 Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das
1036 Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung
1037 ein Minimum oder ein Maximum angenommen wird, wird das eliminieren einer
1038 Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise
1039 \emph{Maximum-Schnitt} bezeichnet.
1041 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
1042 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
1043 markierten Komparatoren sind verschoben, so dass sich eine kompaktere
1044 Darstellung ergibt. Außerdem ist das
1045 \emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
1046 zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
1047 kann entfernt werden.
1049 Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig
1050 \emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen
1051 \emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu
1052 \emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben.
1054 \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
1055 \label{sect:anzahl_schnittmuster}
1057 Der Eliminierungsschritt kann iterativ angewendet werden, um aus einem
1058 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
1059 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und
1060 Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
1061 $n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man
1062 die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein
1063 $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren.
1065 Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
1066 auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
1067 Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
1069 Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
1070 Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
1071 auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
1072 ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
1073 ergeben sich insgesamt
1075 \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!}
1078 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
1079 unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung
1080 und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks
1081 angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis.
1083 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
1084 möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
1085 vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken.
1086 Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der
1087 so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der
1088 möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten,
1089 $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/
1090 Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen
1092 \begin{equation}\label{eqn:anzahl_schnittmuster}
1093 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
1094 = 2^{k} \cdot \frac{n!}{k! (n-k)!}
1095 = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
1096 \quad (1 \leqq k < n)
1099 Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
1100 Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
1101 ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schnittmuster mit
1102 16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$
1103 Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große
1104 Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich.
1106 Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
1107 als die Anzahl der \emph{möglichen} Schnittmuster. Für jeden Komparator auf
1108 der ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
1109 Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
1110 unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
1111 der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
1112 Werte unterscheiden.
1114 Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
1115 Ausgangsmuster abgebildet, weil die Position des Minimums beziehungsweise des
1116 Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
1117 unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
1118 erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
1119 Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
1120 Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
1121 sich die Resultate auch in der ersten Schicht nicht unterscheiden.
1125 \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf}
1127 \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
1128 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
1129 $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
1130 unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
1131 \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone
1132 Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.}
1133 \label{fig:count-cuts-16}
1136 Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl
1137 der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
1138 \emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
1139 \emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je
1140 eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke \oes{16},
1141 \bs{16} und \ps{16} angewandt. Anschließend wurde mithilfe einer Hashtabelle
1142 überprüft, ob das resultierende Sortiernetzwerk schon von einem
1143 \emph{äquivalenten} Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk
1144 noch nicht in der Hashtabelle enthalten war, wurde der Zähler für
1145 unterschiedliche Schnittmuster erhöht und das Sortiernetzwerk eingefügt.
1147 Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
1148 \emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
1149 Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
1150 Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
1151 Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
1154 Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
1155 Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen
1156 Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen}
1157 Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des
1158 \emph{Odd-Even-Mergesort}-Netzwerks, 4973 ($\approx 0,15\%$) beim
1159 \emph{bitonen Mergesort}-Netzwerk und 18764 ($\approx 0,57\%$) beim
1160 \emph{Pairwise-Sorting}-Netzwerk. Zwar ist es möglich, dass mehr Iterationen
1161 die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen
1162 in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass
1163 die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
1164 vernachlässigbar klein ist.
1166 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
1167 Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
1168 Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern
1169 vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
1170 „kleine“ x-Werte verlässt.
1172 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
1173 können, kann man sich einer stochastischen Methode bedienen, der sogenannten
1174 \emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für
1175 schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von
1176 $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
1177 zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
1178 der Annahme, dass auf diese Art und Weise Sortiernetzwerke zufällig und
1179 gleichverteilt erzeugt werden, entspricht das Verhältnis der zufälligen
1180 Schnittmuster, die in $S$ enthalten sind, und $n$ gleich dem Verhältnis von
1181 $k$ und der Anzahl der unterschiedlichen Schnittmuster insgesamt. Damit kann
1182 die Anzahl der unterschiedlichen Schnittmuster abgeschätzt werden.
1186 \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
1188 \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
1189 \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
1190 $\operatorname{BS}(32)$.}
1191 \label{fig:collisions-10000-1000000-32}
1194 In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
1195 Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
1196 $\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
1197 jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
1198 \emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
1199 zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
1200 die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
1201 Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
1202 $\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2
1203 \cdot 10^6$ unterschiedlichen 16-Schnittmustern für $\operatorname{OES}(32)$
1204 und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
1208 \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
1210 \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
1211 \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
1212 zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
1213 Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
1214 unterschiedlichen Schnittmustern.}
1215 \label{fig:collisions-100000-1000000-32-ps}
1218 Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting}-Netzwerk
1219 $\operatorname{PS}(32)$ nicht betrachtet, da es für dieses Netzwerk viel mehr
1220 unterschiedliche 16-Schnittmuster gibt als für $\operatorname{OES}(32)$ und
1221 $\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der
1222 unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
1223 Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
1224 Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,
1225 ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem
1226 kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen
1227 Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
1228 $\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedlichen
1229 Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
1230 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
1231 waren. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
1232 unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
1233 vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als
1234 die Anzahl der \emph{möglichen} Schnittmuster.
1237 \section{Der \textsc{SN-Evolution}-Algorithmus}
1238 \label{sect:sn-evolution}
1240 Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
1241 Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
1242 (Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
1243 (Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
1244 Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
1245 in Abschnitt~\ref{sect:bewertung} behandelt.
1247 \subsection{Bewertungsfunktion}\label{sect:bewertung}
1249 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
1250 {\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
1251 die bei Sortiernetzwerken verfolgt werden können:
1253 \item Möglichst wenige Komparatoren („effizient“)
1254 \item Möglichst wenige Schichten („schnell“)
1259 \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
1260 \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
1261 \caption{Das effizienteste und das schnellste Sortiernetzwerk für
1262 16~Leitungen, das derzeit bekannt ist.}
1263 \label{fig:16-best-known}
1265 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken.
1266 Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für
1267 16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in
1268 Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte
1269 16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
1270 Abbildung~\ref{fig:16-voorhis} zu sehen.
1272 Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
1273 berücksichtigen kann, hat die folgende allgemeine Form:
1275 \operatorname{Guete}(S) = w_{\mathrm{Basis}}
1276 + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
1277 + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
1279 Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
1280 dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
1281 gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
1282 Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
1283 jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
1284 so schlecht ist wie man intuitiv vermuten könnte, zeigt der
1285 \textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
1287 Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen,
1288 ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert.
1289 Das heißt, dass das Ziel von \textsc{SN-Evolution} ist,
1290 $\operatorname{Guete}(S)$ zu \emph{minimieren}.
1292 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
1293 genommen werden. Ist er groß, wird der relative Unterschied der Güten
1294 verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
1295 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
1296 klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
1297 Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
1298 Exploitation}, das Finden (lokaler) Optima, bevorzugt.
1300 Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
1301 der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
1302 Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
1303 es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
1304 Leitungszahlen und Mischer-Typen experimentiert werden muss.
1306 Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
1307 Werte herausgestellt:
1309 w_{\mathrm{Basis}} &=& 0 \\
1310 w_{\mathrm{Komparatoren}} &=& 1 \\
1311 w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
1314 \subsection{Selektion}
1316 Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig
1317 aus der Population auswählt. Sie werden im folgenden Schritt miteinander
1318 rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht
1319 gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen
1320 eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen.
1321 Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für
1322 das Streben des Algorithmus nach besseren Lösungen.
1324 Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
1325 passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt
1326 und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
1328 Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt
1329 sich mit Pseudocode wie folgt beschreiben:
1334 für jedes Individuum in Population
1336 reziproke Güte := 1.0 / Guete(Individuum)
1337 Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
1338 Gütesumme := Gütesumme + reziproke Güte
1340 mit Wahrscheinlichkeit P
1342 Auswahl := Individuum
1348 Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die
1349 Rekombination zu erhalten. Das heißt, dass die Individuen bei
1350 \textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden.
1352 \subsection{Rekombination}
1353 \label{sect:sn-evolution:rekombination}
1355 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
1356 einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
1357 einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
1358 bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
1359 \emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
1360 Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
1361 in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
1363 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
1364 erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
1365 Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass
1366 nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können.
1368 \subsection{Mutation}
1370 Zu einem vollständigen evolutionären Algorithmus gehört außerdem die Mutation
1371 --~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
1372 Sortiernetzwerk zufällig zu verändern und dabei die Sortiereigenschaft zu
1373 erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
1374 Eigenschaft zerstören.
1376 Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
1377 Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
1378 Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
1379 Ausprobieren aller $2^n$~Bitmuster, wie in Abschnitt~\ref{sect:0-1-prinzip}
1382 Um das Potenzial einer Mutation abzuschätzen wurde in \textsc{SN-Evolution}
1383 eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population
1384 überprüft eine Funktion die Notwendigkeit jedes einzelnen Komparators. Dazu
1385 wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende
1386 Netzwerk die Sortiereigenschaft noch besitzt. Trotz des hohen Rechenaufwands
1387 -- bei 16-Sortiernetzwerken sind gut 4~Millionen Tests notwendig, um alle
1388 Komparatoren zu überprüfen -- waren die Ergebnisse ernüchternd: Nach circa
1389 1~Million Iterationen mit 16-Sortiernetzwerken fand der so modifizierte
1390 Algorithmus keinen einzigen Komparator, den er hätte entfernen können. Daher
1391 wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet.
1393 \subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer}
1397 \input{images/16-e1-bitonic-1296542566.tex}
1399 \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
1400 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1401 \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers}
1403 \label{fig:16-e1-bitonic-1296542566}
1406 Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
1407 als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
1408 Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in
1409 Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück.
1411 Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser
1412 Konfiguration gefunden werden, sind effizienter als das \emph{bitone
1413 Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
1414 Merge}-Netzwerk \bm{n} beruht. Das in
1415 Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
1416 benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
1418 Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
1419 bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n}
1420 sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als
1421 \bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit
1422 134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von
1423 schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen
1424 Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast}
1427 \begin{table}\label{tbl:sn-ev-bm-fast}
1429 \rowcolors{4}{black!5}{}
1430 \begin{tabular}{|r|r|r|r|r|}
1432 Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\
1434 ($n$) & Komp. & Schichten & Komp. & Schichten \\
1436 8 & \gcell 20 & 6 & 24 & 6 \\
1437 9 & \Gcell 26 & 8 & 28 & 8 \\
1438 10 & \gcell 31 & \gcell 8 & 33 & 9 \\
1439 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\
1440 12 & \gcell 42 & \gcell 9 & 46 & 10 \\
1441 13 & \Gcell 48 & 10 & 53 & 10 \\
1442 14 & \gcell 54 & 10 & 61 & 10 \\
1443 15 & \Gcell 61 & 10 & 70 & 10 \\
1444 16 & \gcell 67 & 10 & 80 & 10 \\
1445 17 & \Gcell 76 & 12 & 85 & 12 \\
1446 18 & \gcell 87 & \gcell 12 & 91 & 13 \\
1447 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\
1448 20 & \gcell 104 & \gcell 13 & 106 & 14 \\
1449 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
1450 22 & \gcell 118 & \gcell 14 & 123 & 15 \\
1451 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\
1452 24 & \gcell 133 & 15 & 144 & 15 \\
1455 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
1456 unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus
1457 wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet
1458 und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die
1459 Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
1460 $w_{\mathrm{Schichten}} = n$.}
1464 \subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
1468 \input{images/16-e1-oddeven-1296543330.tex}
1470 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
1471 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1472 \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers
1474 \label{fig:16-e1-oddeven-1296543330}
1477 Im vorherigen Abschnitt wurde gezeigt, dass der
1478 \textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
1479 Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
1480 \emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
1481 Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
1482 erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
1483 \emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
1484 \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
1485 nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
1486 Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen.
1488 Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
1489 mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
1490 Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht
1491 beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt
1492 \textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen.
1493 \oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der
1494 Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet
1495 sich in Tabelle~\ref{tbl:sn-ev-oem-fast}.
1499 %\input{images/08-e2-1237993371.tex}
1501 %\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
1502 %\label{fig:08-e2-1237993371}
1507 %\input{images/09-e2-1237997073.tex}
1509 %\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
1510 %\label{fig:09-e2-1237997073}
1515 %\input{images/09-e2-1237999719.tex}
1517 %\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
1518 %\label{fig:09-e2-1237999719}
1523 %\input{images/10-e2-1239014566.tex}
1525 %\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
1526 %\label{fig:10-e2-1239014566}
1529 \begin{table}\label{tbl:sn-ev-oem-fast}
1531 \rowcolors{4}{black!5}{}
1532 \begin{tabular}{|r|r|r|r|r|}
1534 Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
1536 & Komp. & Schichten & Komp. & Schichten \\
1538 8 & 19 & 6 & 19 & 6 \\
1539 9 & 26 & 8 & 26 & 8 \\
1540 10 & 31 & 9 & 31 & 9 \\
1541 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
1542 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
1543 13 & 48 & 10 & 48 & 10 \\
1544 14 & 53 & 10 & 53 & 10 \\
1545 15 & 59 & 10 & 59 & 10 \\
1546 16 & 63 & 10 & 63 & 10 \\
1547 17 & 74 & 12 & 74 & 12 \\
1548 18 & 82 & 13 & 82 & 13 \\
1549 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
1550 20 & 97 & 14 & 97 & 14 \\
1551 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
1552 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
1553 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\
1554 24 & 128 & 15 & \gcell 127 & 15 \\
1557 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
1558 unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
1559 Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
1560 gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
1561 nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
1562 1$, $w_{\mathrm{Schichten}} = n$.}
1566 \subsection{Zufälliger Mischer}
1568 Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
1569 Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
1570 \emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
1571 Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
1572 12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
1573 82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
1574 um das beste Ergebnis beider Konstruktionen zu erreichen.
1575 \textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
1576 Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
1577 \emph{Odd-Even}-Mischer wählen.
1579 Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des
1580 Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast}
1581 zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der
1582 Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem
1583 Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und
1584 20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen
1585 Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz.
1587 \begin{table}\label{tbl:sn-ev-rnd-fast}
1589 \rowcolors{4}{black!5}{}
1590 \begin{tabular}{|r|r|r|r|r|r|r|}
1592 Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}}
1593 & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}}
1594 & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\
1596 ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\
1598 8 & 20 & 6 & \gcell 19 & 6 & \gcell 19 & 6 \\
1599 9 & 26 & 8 & 26 & 8 & 26 & 8 \\
1600 10 & 31 & \gcell 8 & 31 & 9 & 31 & \gcell 8 \\
1601 11 & \Gcell 37 & 9 & 38 & 9 & \Gcell 37 & 9 \\
1602 12 & 42 & 9 & 43 & 9 & \gcell 41 & 9 \\
1603 13 & 48 & 10 & 48 & 10 & 48 & 10 \\
1604 14 & 54 & 10 & \gcell 53 & 10 & \gcell 53 & 10 \\
1605 15 & 61 & 10 & \Gcell 59 & 10 & \Gcell 59 & 10 \\
1606 16 & 67 & 10 & \gcell 63 & 10 & 64 & 10 \\
1607 17 & 76 & 12 & \Gcell 74 & 12 & \Gcell 74 & 12 \\
1608 18 & 87 & \gcell 12 & \gcell 82 & 13 & 83 & \gcell 12 \\
1609 19 & 93 & 13 & 93 & 13 & \Gcell 92 & 13 \\
1610 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\
1611 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\
1612 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\
1613 23 & 134 & 14 & 129 & 14 & \Gcell 128 & 14 \\
1614 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\
1617 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
1618 unter Verwendung der verschiedenen Mischer. Der Algorithmus wurde mit dem
1619 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach
1620 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten
1621 $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
1622 $w_{\mathrm{Schichten}} = n$.}
1626 %\input{shmoo-aequivalenz.tex}
1629 \section{Der \textsc{SN-Markov}-Algorithmus}
1632 Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
1633 Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus
1634 einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
1635 ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
1636 verwendet und mit sich selbst kombiniert wird.
1638 Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk
1639 \emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
1640 Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke,
1641 die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit
1642 sich selbst und anschließendem Eliminieren der Hälfte der Leitungen hervorgehen
1643 können, heißen \emph{Nachfolger} von $S_0$.
1645 Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
1646 (gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
1647 Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
1648 Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von
1649 $S_0$ ist, das heißt, dass $S_1$ durch die Rekombination von $S_0$ mit sich
1650 selbst erzeugt werden kann.
1652 Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
1653 der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
1654 sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
1655 Nachfolger zwar noch unter 20.000, bei den untersuchten
1656 32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$
1657 unterschiedliche Schnittmuster geschätzt.
1659 Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
1660 zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
1661 gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
1662 gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
1663 selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der
1664 Algorithmus wie folgt beschreiben:
1671 Nachfolger := kombiniere (Netzwerk, Netzwerk)
1672 Netzwerk := Nachfolger
1678 Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der
1679 Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem
1680 zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der
1681 \textsc{SN-Markov}-Algorithmus auf einem entsprechenden
1682 \emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens
1683 1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der
1684 Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler
1685 erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende
1686 prozentuale Verteilung zu sehen.
1688 Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators}
1689 eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
1690 Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
1691 um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
1692 Beispielsweise war die kleinste erreichte Komparatorzahl bei
1693 16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$
1694 gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$
1695 und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem
1696 Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
1697 unter den Graphen angegeben.
1701 \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}}
1702 \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}}
1703 \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}}
1704 \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}}
1705 \caption{Anzahl der Komparatoren von Sortiernetzwerken,
1706 die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet
1707 ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der
1708 gemessenen Daten darstellt.}
1709 \label{fig:markov-comparators}
1714 \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf}
1716 \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von
1717 \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem
1718 \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.}
1719 \label{fig:comparison-comparators}
1722 Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der
1723 \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
1724 \textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit
1725 \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl
1726 der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
1727 Startnetzwerk diente bei beiden Algorithmen das
1728 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
1729 x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
1730 ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
1731 wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je
1732 nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}.
1734 Sowohl der \textsc{SN-Markov}-Algorithmus, der das
1735 \emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
1736 \oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die
1737 bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind.
1738 Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger:
1739 Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit
1740 63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335
1741 \%$ rund 20~mal höher.
1743 Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem
1744 \emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist
1745 jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
1746 mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16}
1747 ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für
1748 Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein
1749 Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so
1750 vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
1751 Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das
1752 mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk
1757 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf}
1759 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
1760 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1761 % \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.}
1762 % \label{fig:markov-comparators-14}
1767 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf}
1769 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
1770 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1771 % \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.}
1772 % \label{fig:markov-comparators-16}
1777 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf}
1779 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen),
1780 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1781 % \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.}
1782 % \label{fig:markov-comparators-18}
1787 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
1789 % \caption{Zyklen, die beim \textit{Random Walk} des
1790 % \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
1791 % Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
1792 % y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
1793 % Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
1794 % \label{fig:markov-cycles-16}
1798 \section[\textsc{SN-Evolution-Cut}]{Der \textsc{SN-Evolution-Cut}-Algorithmus}
1799 \label{sect:sn-evolution-cut}
1801 Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
1802 Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
1803 Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
1804 möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
1805 von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
1807 Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
1808 in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
1809 Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$
1810 oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem
1811 $k$-Schnittmuster sind genau $k$ Zahlen ungleich Null.
1813 Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
1814 Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
1815 verwendet. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq n$. Anschließend
1816 werden zufällig Werte auf Null beziehungsweise 1 oder $-1$ gesetzt, um die
1817 Anzahl der Schnitte zu korrigieren.
1819 Die Mutation vertauscht entweder die Werte von zwei zufälligen Positionen oder
1820 multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu
1823 Die Eingabe für \textsc{SN-Evolution-Cut} ist ein $n$-Sortiernetzwerk und eine
1824 Zahl $k$, $1 \leqq k < n$, die angibt wie viele Leitungen entfernt werden
1825 sollen. Der Rückgabewert des \textsc{SN-Evolution-Cut}-Algorithmus ist ein
1826 \emph{$k$-Schnittmuster}. Wird das Schnittmuster auf das Sortiernetzwerk, mit
1827 dem der Algorithmus gestartet wurde, angewendet, entsteht ein möglichst
1828 schnelles und effizientes Sortiernetzwerk mit $m = n - k$ Leitungen. Da mit
1829 dem Eingabe-Netzwerk und dem zurückgegebenen $k$-Schnittmuster das
1830 $m$-Sortiernetzwerk eindeutig bestimmt ist, werden im Folgenden sowohl das
1831 $k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von
1832 \textsc{SN-Evolution-Cut} bezeichnet.
1834 \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
1835 \label{sect:sn-evolution-cut:bs}
1837 Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen
1838 Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll,
1839 ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke
1840 als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k
1841 = 6$ gestartet, resultiert das gefundene Schnittmuster in einem
1842 Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16}
1843 benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
1844 wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
1848 \input{images/16-ec-from-bs22.tex}
1850 \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
1851 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1852 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk
1853 $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4,
1854 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.}
1855 \label{fig:16-ec-from-bs22}
1858 Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen
1859 Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden,
1860 gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde
1861 mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten
1862 der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$,
1863 $w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder
1864 Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten
1865 befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des
1866 Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des
1867 resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der
1868 Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu
1873 \rowcolors{2}{black!5}{}
1874 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
1876 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
1878 9 & 21 & & & & & & & & & & & & & & & \\
1879 10 & 20 & 27 & & & & & & & & & & & & & & \\
1880 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\
1881 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\
1882 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\
1883 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\
1884 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\
1885 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\
1886 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\
1887 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\
1888 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\
1889 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\
1890 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\
1891 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\
1892 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\
1893 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
1895 \bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
1899 \caption{Anzahl der Komparatoren der Ergebnisse von
1900 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
1901 Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
1902 die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
1903 Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
1904 \label{tbl:ec-bs-efficiency}
1907 Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut}
1908 mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der
1909 gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von
1910 $m=23$) ein Ergebnis, das effizienter als \bs{m} ist.
1912 In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein
1913 effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut}
1914 gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren
1915 3~weniger als \bs{19}.
1917 Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke,
1918 beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein
1919 Sortiernetzwerk mit 31~Komparatoren gefunden.
1923 \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
1924 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{19} erzeugt.]{\input{images/10-ec-from-bs19-fast.tex}\label{fig:10-ec-from-bs19-fast}}
1925 \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
1926 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{18} erzeugt.]{\input{images/11-ec-from-bs18-fast.tex}\label{fig:11-ec-from-bs18-fast}}
1927 \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
1928 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/12-ec-from-bs22-fast.tex}\label{fig:12-ec-from-bs22-fast}}
1929 \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
1930 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{37} erzeugt.]{\input{images/19-ec-from-bs37-fast.tex}\label{fig:19-ec-from-bs37-fast}}
1931 \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
1932 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
1933 erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
1934 \label{fig:ec-bs-fast_networks}
1937 Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
1938 \textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
1939 das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
1940 Tabelle~\ref{tbl:ec-bs-speed} ist die Anzahl der Schichten, die die Ergebnisse
1941 von \textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren,
1942 aufgelistet. Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n},
1943 jede Spalte enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die
1944 Zellen enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
1948 \rowcolors{2}{black!5}{}
1949 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
1951 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
1953 9 & 6 & & & & & & & & & & & & & & & \\
1954 10 & 6 & 8 & & & & & & & & & & & & & & \\
1955 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
1956 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
1957 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
1958 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
1959 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
1960 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
1961 17 & 6 & 8 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
1962 18 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
1963 19 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
1964 20 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
1965 21 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
1966 22 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
1967 23 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
1968 24 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
1970 \bs{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
1974 \caption{Anzahl der Schichten der Ergebnisse von
1975 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
1976 Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
1977 die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
1978 Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
1979 \label{tbl:ec-bs-speed}
1982 Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die
1983 schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke,
1984 die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
1985 werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.
1987 Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das
1988 Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m}
1989 führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt
1990 werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht
1991 einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m
1992 = 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu
1993 reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
1994 noch größer gewählt werden.
1996 Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von
1997 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten
1998 werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in
1999 Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im
2000 Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n =
2001 37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19}
2002 und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein
2003 Beispiel für ein solches Netzwerk ist in
2004 Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen.
2008 \rowcolors{2}{black!5}{}
2009 \begin{tabular}{|r|r|r|}
2011 $n$ & Komp. & Schichten \\
2031 \rowcolor{green!10!white!95!black}
2035 \bs{19} & 98 & 14 \\
2036 \oes{19} & 91 & 14 \\
2040 \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
2041 von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt
2042 wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als
2043 \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit
2044 13~Schichten die Effizienz der vorherigen
2045 Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese
2046 Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37}
2047 auf diese Art erzeugt wurde, ist in
2048 Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.}
2049 \label{tbl:ec-bs-19}
2052 \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
2053 wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode
2054 konstruiert wurde, durch systematisches Entfernen von Leitungen in einen
2055 ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert werden
2056 kann, so dass dieser alternative Mischer im Vergleich zu $\bm{\frac{n}{2} =
2057 2^{d-1}}$ Komparatoren einspart.
2059 Basierend auf diesen alternativen Mischern geben \textit{Mühlenthaler} und
2060 \textit{Wanka} eine Konstruktionsvorschrift für Sortiernetzwerke an, die
2061 gegenüber \bs{n} ${\frac{1}{4}n(\log n - 1)}$ Komparatoren einspart.
2062 Beispielsweise wird ein 16-Sortiernetzwerk angegeben, das nur 68~Komparatoren
2063 benötigt. Dieses Netzwerk ist in Abbildung~\ref{fig:16-muehlenthaler}
2068 \input{images/16-muehlenthaler.tex}
2070 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
2071 10~Schichten. Das Netzwerk wurde 2010 von \textit{Mühlenthaler} und
2072 \textit{Wanka} aus optimierten bitonen Mischern konstruiert und
2073 in~\cite{MW2010} veröffentlicht.}
2074 \label{fig:16-muehlenthaler}
2079 \input{images/16-ec-from-bs32.tex}
2081 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
2082 10~Schichten. Das Netzwerk wurde von dem Algorithmus
2083 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk}
2084 $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
2085 \label{fig:16-ec-from-bs32}
2090 \input{images/16-ec-from-bs32-normalized.tex}
2092 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
2093 10~Schichten. Das Netzwerk wurde von dem Algorithmus
2094 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
2095 $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
2096 \label{fig:16-ec-from-bs32-normalized}
2099 Startet man {\sc SN-Evolution-Cut} mit dem \emph{bitonen Mergesort}-Netzwerk
2100 $\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
2101 Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
2102 16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den
2103 Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
2104 zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
2105 und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26,
2106 29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch
2107 \textsc{SN-Evolution-Cut} gefunden wurde.
2108 Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
2109 nachdem das Schnittmuster angewendet und das Netzwerk normalisiert wurde.
2110 % Eine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist
2111 % in diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten
2112 % des Netzwerks scheinen rein zufällig zu sein.
2115 % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
2116 % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
2117 % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
2120 \input{images/32-ec-from-bs64.tex}
2122 \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
2123 15~Schichten. Das Netzwerk wurde von dem Algorithmus
2124 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
2125 $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
2127 $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
2128 $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
2129 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
2130 \label{fig:32-ec-from-bs64}
2133 Wenn \textsc{SN-Evolution-Cut} mit dem \bs{64}-Netzwerk und $k = 32$ gestartet
2134 wird, findet der Algorithmus 32-Sortiernetzwerke, die effizienter sind als
2135 32-Sortiernetzwerke, die nach \textit{Mühlenthalers} und \textit{Wankas}
2136 Methode konstruiert werden. Ein von \textsc{SN-Evolution-Cut} aus \bs{64}
2137 generiertes 32-Sortiernetzwerk ist in Abbildung~\ref{fig:32-ec-from-bs64}
2138 dargestellt. Das \emph{bitone Mergesort}-Netzwerk \bs{32} benötigt
2139 240~Komparatoren, ein aus den optimierten Mischern aufgebautes Netzwerk
2140 verbessert die Effizienz auf 208~Komparatoren. Das Ergebnis von
2141 \textsc{SN-Evolution-Cut} kommt mit nur 206~Komparatoren aus. Die
2142 Geschwindigkeit aller genannten Sortiernetzwerke ist mit 15 parallelen
2143 Schritten identisch.
2145 Wenn die Leitungszahl des Eingabenetzwerks keine Zweierpotenz ist, kann
2146 \textsc{SN-Evo\-lu\-tion-Cut} auch 16-Sortiernetzwerke erzeugen, die diese
2147 Effizienz unterbieten. Das geht aus den Daten in
2148 Tabelle~\ref{tbl:ec-bs-efficiency} hervor. Ein 16-Sortiernetzwerk mit
2149 67~Komparatoren, das von \textsc{SN-Evolution-Cut} generiert wurde, ist in
2150 Abbildung~\ref{fig:16-ec-from-bs22} dargestellt.
2152 Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
2153 unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
2154 gute Schnittmuster anzugeben.
2156 Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
2157 Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
2158 Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
2159 Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
2160 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
2161 ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
2162 die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
2163 Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
2164 mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
2166 Dass die Sortiernetzwerke, die mit den Schnittmustern von
2167 \textsc{SN-Evolution-Cut} entstehen, keine erkennbare Struktur haben, ist
2168 jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere von der
2169 Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
2170 \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(n)$ und
2171 $k$~Schnitten gestartet, so ist das beste Ergebnis immer das
2172 $\operatorname{OET}(n-k)$-Netzwerk.
2174 \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
2175 \label{sect:sn-evolution-cut:oes}
2177 Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk
2178 \oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die
2179 genauso effizient und schnell wie das entsprechende
2180 \emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der
2181 Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus
2182 \oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency}
2187 \rowcolors{2}{black!5}{}
2188 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2190 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2192 9 & 19 & & & & & & & & & & & & & & & \\
2193 10 & 19 & 26 & & & & & & & & & & & & & & \\
2194 11 & 19 & 26 & 31 & & & & & & & & & & & & & \\
2195 12 & 19 & 26 & 31 & 37 & & & & & & & & & & & & \\
2196 13 & 19 & 26 & 31 & 37 & 41 & & & & & & & & & & & \\
2197 14 & 19 & 26 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
2198 15 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
2199 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
2200 17 & 19 & 26 & 31 & 38 & 41 & 48 & 53 & 59 & 63 & & & & & & & \\
2201 18 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & & & & & & \\
2202 19 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & & & & & \\
2203 20 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & & & & \\
2204 21 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & & & \\
2205 22 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & & \\
2206 23 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & \\
2207 24 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
2211 \caption{Anzahl der Komparatoren der Ergebnisse von
2212 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2213 \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
2214 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
2215 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2217 \label{tbl:ec-oes-efficiency}
2222 \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das
2223 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{17} erzeugt.]{\input{images/11-ec-from-oes17-fast.tex}\label{fig:11-ec-from-oes17-fast}}
2224 \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das
2225 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{18} erzeugt.]{\input{images/12-ec-from-oes18-fast.tex}\label{fig:12-ec-from-oes18-fast}}
2226 \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m =
2227 11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
2228 erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m}
2230 \label{fig:ec-oes-fast_networks}
2233 Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt
2234 schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein
2235 $m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes
2236 Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit
2237 war allerdings in allen beobachteten Fällen nur dann möglich, wenn
2238 zusätzliche Komparatoren in Kauf genommen wurden. In den
2239 Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser
2240 Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu
2241 beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
2242 Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.
2246 \rowcolors{2}{black!5}{}
2247 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2249 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2251 9 & 6 & & & & & & & & & & & & & & & \\
2252 10 & 6 & 8 & & & & & & & & & & & & & & \\
2253 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
2254 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
2255 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
2256 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
2257 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
2258 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
2259 17 & 6 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
2260 18 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
2261 19 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
2262 20 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
2263 21 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
2264 22 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
2265 23 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
2266 24 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
2268 \oes{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
2272 \caption{Anzahl der Schichten der Ergebnisse von
2273 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2274 \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
2275 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
2276 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2278 \label{tbl:ec-oes-speed}
2281 In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
2282 viele \emph{unterschiedliche} Schnittmuster die konstruktiven Sortiernetzwerke
2283 $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und $\operatorname{PS}(32)$
2284 besitzen. Eines der Ergebnisse war, dass von diesen Sortiernetzwerken das
2285 \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten unterschiedlichen
2286 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen. Entsprechend ist es
2287 wenig verwunderlich, dass \textsc{SN-Evolution-Cut} gestartet mit
2288 $\operatorname{OES}(32)$ sehr schnell\footnote{Auf dem Computer, auf dem diese
2289 Arbeit geschrieben wurde, dauerte es in den meisten Fällen weniger als eine
2290 Sekunde bis ein entsprechendes Schnittmuster gefunden wurde.} ein gutes
2291 16-Schnittmuster findet.
2293 Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
2294 bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
2295 $\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
2296 8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
2297 Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
2298 Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
2302 \input{images/16-ec-from-oes32-cut.tex}
2304 \caption{Visualisierung eines 16-Schnittmusters, das auf
2305 $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
2306 bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
2307 resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
2309 \label{fig:16-ec-from-oes32-cut}
2314 \input{images/16-ec-from-oes32.tex}
2316 \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
2317 Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
2318 einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
2319 berechnet wurde. Das Schnittmuster ist in
2320 Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
2321 \label{fig:16-ec-from-oes32}
2324 Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
2325 4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
2326 Beobachtung kann man das regelmäßige Schnittmuster
2328 \textit{Eingang}_i = \left\{ \begin{array}{rl}
2329 \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
2330 -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
2331 ? & \quad \mathrm{sonst}
2334 ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
2335 Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
2336 Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
2337 32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
2338 ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
2342 \input{images/32-ec-from-oes64.tex}
2344 \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten.
2345 Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
2346 \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
2347 \label{fig:32-ec-from-oes64}
2350 Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
2351 erzeugten Sortiernetzwerke die Effizienz des
2352 \emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
2353 beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
2354 43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
2355 beider Sortiernetzwerke ist mit 10~Schichten identisch.
2357 Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
2358 und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
2359 verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
2360 Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
2361 22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
2362 Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
2363 Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
2364 werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
2365 gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
2366 werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
2367 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
2368 dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
2369 sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
2370 angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
2371 \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
2375 \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
2376 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
2377 \emph{Odd-Even-Mergesort}-Netzwerk generiert
2378 wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
2379 \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
2380 das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
2382 wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
2383 \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
2384 Ergebnis von der Bewertungsfunktion ab.}
2385 \label{fig:12-ec-from-oes24}
2388 Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
2389 findet Sortiernetzwerke, die schneller sind als das entsprechende
2390 \emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit
2391 22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige
2392 schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können,
2393 charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
2394 \emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
2396 \begin{tabular}{|r|r|r|r|r|}
2398 Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
2399 & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
2401 11 & 38 & 9 & 37 & 10 \\
2402 12 & 43 & 9 & 41 & 10 \\
2403 19 & 93 & 13 & 91 & 14 \\
2404 20 & 101 & 13 & 97 & 14 \\
2405 21 & 108 & 14 & 107 & 15 \\
2406 22 & 116 & 14 & 114 & 15 \\
2407 23 & 125 & 14 & 122 & 15 \\
2411 Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
2412 23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
2413 Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
2414 Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
2415 beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
2416 \bs{23} beziehungsweise \oes{23} eine Schicht einspart.
2420 \input{images/23-ec-from-oes46-fast.tex}
2422 \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten.
2423 Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
2424 Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
2425 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
2427 \label{fig:23-ec-from-oes46}
2430 \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
2432 Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
2433 Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
2434 (Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
2435 ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
2436 wie und warum es jede beliebige Eingabe sortiert.
2440 \rowcolors{2}{black!5}{}
2441 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2443 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2445 9 & 20 & & & & & & & & & & & & & & & \\
2446 10 & 20 & 27 & & & & & & & & & & & & & & \\
2447 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\
2448 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\
2449 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\
2450 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
2451 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
2452 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
2453 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\
2454 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\
2455 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\
2456 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\
2457 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\
2458 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\
2459 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\
2460 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\
2462 \ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\
2466 \caption{Anzahl der Komparatoren der Ergebnisse von
2467 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2468 \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
2469 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
2470 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2472 \label{tbl:ec-ps-speed}
2475 Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
2476 Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
2477 definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
2478 $\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
2479 ein Sortiernetzwerk, das die gleiche Anzahl Komparatoren und Schichten hat wie
2480 $\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser
2481 Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
2485 \input{images/16-ec-from-ps32.tex}
2487 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
2488 10~Schichten. Das Netzwerk wurde von dem Algorithmus
2489 \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
2490 $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
2491 \label{fig:16-ec-from-ps32}
2494 Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
2495 einsetzt und auch nicht auf einem Mischer basiert, ist das
2496 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
2497 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
2498 den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die
2499 strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die
2500 Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
2504 \input{images/32-pairwise-cut-16-pairwise.tex}
2506 \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu
2507 sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk
2509 \label{fig:ps16-from-ps32}
2512 Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
2513 regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
2514 schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
2515 einfache Schnittmuster
2517 \textit{Eingang}_i = \left\{ \begin{array}{rl}
2518 -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\
2519 \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\
2520 ? & \quad \mathrm{sonst}
2523 für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk
2524 $\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der
2525 dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das
2526 verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32}
2527 dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind
2528 diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden
2529 Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den
2530 „richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht
2531 werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende
2532 Netzwerk in schwarz gut zu erkennen.
2536 \input{images/16-pairwise.tex}
2538 \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
2539 ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das
2540 resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
2541 \label{fig:16-pairwise}
2544 Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf
2545 $\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein
2546 8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für
2547 größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise
2548 kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16}
2549 konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
2550 untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
2553 \section{Fazit und Ausblick}
2555 Mit dem Entfernen von Leitungen aus bekannten Sortiernetzwerken lassen sich
2556 interessante Ergebnisse erzielen. Dies zeigte \textit{Moritz Mühlenthaler}
2557 bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und
2558 Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere
2559 interessante Beobachtungen machen lassen.
2561 Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution},
2562 \textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der
2563 Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres
2564 Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in
2565 Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt.
2567 Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den
2568 vorgestellten Algorithmen übertroffen werden. Der Algorithmus
2569 \textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und
2570 \textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und
2571 für ein 32-Sortiernetzwerk sogar noch übertreffen. Der
2572 \textsc{SN-Evolution}-Algorithmus fand 16-Sortiernetzwerke, die gegenüber dem
2573 Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen
2574 weiteren Komparator einsparen.
2576 Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen
2577 zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer
2578 Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das
2579 \emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden
2580 regelmäßige Schnittmuster angegeben. Diese ergeben Sortiernetzwerke, die so
2581 schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
2584 Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen
2585 Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich
2586 weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das
2587 bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
2588 Schnittmustern erreicht werden können.
2590 Die Möglichkeiten der Optimierung von Sortiernetzwerken mit
2591 \emph{Evolutionären Algorithmen} sind durch die in dieser Arbeit vorgestellten
2592 Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze
2593 umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknüpft
2596 \subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}
2598 Die aktuelle Implementierung von \textsc{SN-Evolution}
2599 (Abschnitte~\ref{sect:sn-evolution}
2600 beziehungsweise~\ref{sect:implementierung}) kann sowohl den \emph{bitonen
2601 Mischer} als auch den \emph{Odd-Even}-Mischer verwenden, um zwei Individuen zu
2602 rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen
2603 Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich
2604 selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von
2605 $\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
2606 die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
2607 Ausgabe sorgen. Anstelle von $\ps{\frac{n}{2}}$ können beliebige
2608 Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwendet werden.
2610 Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
2611 rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
2612 \emph{unterschiedliche} Schnittmuster gibt
2613 (Abschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
2614 Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider
2615 wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine
2616 $n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren
2617 $n$-Sortiernetzwerken als \ps{n} führen.
2619 \subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}}
2621 Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
2622 in~\cite{H1990} beschreibt, könnte man versuchen, die Algorithmen
2623 \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} zu kombinieren. Nach dem
2624 Zusammenfügen von zwei $n$-Sortiernetzwerken könnte der Algorithmus
2625 \textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
2626 \emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
2627 Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
2628 verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut}
2629 die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern.
2631 Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} --
2632 eine zweite Population von Schnittmustern evolvieren, die für die
2633 Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut
2634 funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge
2635 Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten
2636 Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster
2637 eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses}
2638 Schnittmuster zur nächsten Generation beiträgt. Im Gegensatz zum Ansatz der
2639 parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die
2640 das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern
2644 \section{Implementierung}
2645 \label{sect:implementierung}
2647 Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens
2648 entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen
2649 Kommandozeilen-Programmen durchgeführt. Die Bibliothek wurde unter der
2650 \textit{GNU Lesser General Public License} (LGPL) in der Version~2.1
2651 veröffentlicht; die Kommandozeilen-Programme, die in vielen Fällen lediglich
2652 Funktionalität der Bibliothek auf der Kommandozeile zur Verfügung stellen,
2653 stehen unter der \textit{GNU General Public License}, Version~2. Diese
2654 Lizenzen räumen einem Benutzer weitreichende Rechte ein, unter anderem das
2655 Programm beliebig zu verwenden, zu studieren, zu verändern sowie veränderte
2656 und unveränderte Kopien zu veröffentlichen.
2658 Die Programmierschnittstelle (API) der Bibliothek orientiert sich an
2659 Paradigmen der \textit{objektorientierten Programmierung}. Beispielsweise kann
2660 mit der Funktion \texttt{sn\_network\_ create()} ein neues Zustands-Objekt
2661 erzeugt werden, für das mehrere Manipulations-Methoden, zum Beispiel
2662 \texttt{sn\_network\_comparator\_add()}, zur Verfügung stehen. Auf diese Art
2663 und Weise kann die Bibliothek leicht erweitert werden, ohne dass bestehende
2664 Programme angepasst werden müssen.
2666 Die meisten Kommandozeilen-Programmen lesen ein Komparatornetzwerk von der
2667 Standard-Eingabe und schreiben ihr Ergebnis auf die Standard-Ausgabe. Um
2668 Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen
2669 Mergesort}-Netzwerks \bs{42} zu erzeugen, kann folgendes Kommando verwendet
2672 $ sn-bitonicsort 42 | sn-normalize >sn-42
2674 Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
2675 es einfach zu ermöglichen, Programme zu verketten, ist eines der
2676 Grundprinzipien des UNIX-Be\-triebs\-sys\-tems. Es hat sich in den letzten
2677 Jahrzehnten und beim Verfassen dieser Arbeit als sehr flexibel und mächtig
2680 Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden,
2681 sind unter anderem das Erzeugen des \emph{Odd-Even-Mergesort}-, \emph{bitonen
2682 Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von
2683 Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und
2684 Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das
2685 Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise
2686 wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex}
2689 \textit{libsortnetwork} kann unter der Web-Adresse
2690 \url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden.
2693 \bibliography{references}
2694 \bibliographystyle{plain}
2700 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 spelllang=de :