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 4~Ein- beziehungsweise Ausgängen,
162 bestehend aus 5~Komparatoren.}
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 9~Eingängen und 24~Komparatoren,
209 die in 8~Schichten angeordnet sind. Das Netzwerk sortiert alle Eingaben, bei
210 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 so schnell, dass ein Ausprobieren aller möglichen Permutationen schon bei
236 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
264 $a_i$, beziehungsweise zwei Zahlen größer oder gleich $a_i$. Da im Fall der
265 0-1-Folge zwei gleiche Zahlen am Komparator anliegen, dürfen wir davon
266 ausgehen, dass sich der Komparator so verhält, wie er sich bei der Permutation
267 verhalten hat -- ohne das Ergebnis zu beeinflussen. Entsprechend müssen an den
268 Ausgängen $i-1$ und $i$ eine Null und eine Eins in der falschen Reihenfolge
269 ankommen. Das steht im Widerspruch zu der Annahme, dass alle 0-1-Folgen
272 Im Gegensatz zum Überprüfen aller möglichen Permutationen, was mit dem Aufwand
273 $\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ verbunden ist, besitzt
274 das Überprüfen aller 0-1-Folgen „nur“ den Aufwand $\Theta(2^n)$. Entsprechend
275 ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist
276 bisher allerdings nicht bekannt.
278 Um zu überprüfen, ob ein Komparatornetzwerk mit 16~Leitungen die
279 Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig
280 -- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt.
281 Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch
282 bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus
283 mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
284 Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
285 Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
286 Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
287 Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
288 auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
289 für einen Lauf benötigt.
291 \subsubsection{Evolutionäre Algorithmen}
293 Viele {\em kombinatorische Optimierungsprobleme} sind schwer zu lösen -- die
294 entsprechenden Entscheidungsprobleme liegen oft in der Komplexitätsklasse
295 $\mathcal{NP}$-vollständig. Das heißt, dass keine Verfahren bekannt sind, die
296 diese Probleme effizient exakt lösen. Sollte sich herausstellen, dass diese
297 Probleme außerhalb der Komplexitätsklasse~$\mathcal{P}$ liegen, wäre eine
298 Konsequenz, dass es für diese Probleme keine effizienten exakten Algorithmen
299 gibt. Stellt sich hingegen heraus, dass diese Probleme neben
300 $\mathcal{NP}$-vollständig auch in der Komplexitätsklasse~\textit{P} liegen,
301 gibt es effiziente Algorithmen. Es ist jedoch wahrscheinlich, dass die
302 Zeitkonstanten solcher Algorithmen sehr groß wären, so dass der praktische
303 Nutzen fraglich bleibt.
305 Aus diesem Grund besteht die Notwendigkeit, einen Kompromiss einzugehen: Statt
306 die \emph{optimale Lösung}, beziehungsweise eine der \emph{optimalen Lösungen}
307 als einzige Ausgabe des Algorithmus zuzulassen, wird eine "`möglichst gute"'
308 Lösung ausgegeben. Dafür verringert sich die Laufzeit des Algorithmus. Viele
309 dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur.
310 Beispielsweise imitieren die „Ameisenalgorithmen“ das Verhalten von Ameisen
311 auf der Futtersuche, um kurze Rundreisen auf Graphen zu berechnen.
313 Bei {\em Evolutionären Algorithmen} stand die Evolution Pate. Die Grundidee
314 ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu
315 kombinieren. Dabei bedient man sich der in der Evolutionstheorie etablierten
316 Nomenklatur, beispielsweise werden konkrete Lösungen für ein Problem als {\em
317 Individuen} bezeichnet.
319 Die Vorgehensweise lässt sich abstrakt wie folgt beschreiben: Aus einer
320 bestehenden Lösungsmenge, der {\em Population}, werden zufällig Lösungen
321 ausgesucht {\em (Selektion)} und zu einer neuen Lösung kombiniert ({\em
322 Rekombination}). Unter Umständen wird die neue Lösung noch zufällig
323 verändert {\em (Mutation)}, bevor sie in die bestehende Lösungsmenge
324 eingefügt wird. Die verwendeten Wahrscheinlichkeiten, beispielsweise bei der
325 {\em Selektion}, sind dabei nicht zwangsläufig gleichverteilt -- üblicherweise
326 werden bessere Lösungen bevorzugt. Zur Bewertung dient die sogenannte {\em
329 Nicht alle Probleme eignen sich für diese Strategie. Zum einen muss es möglich
330 sein, eine initiale Population zur Verfügung zu stellen, da diese als Basis
331 aller weiteren Operationen dient. Das ist häufig keine große Einschränkung, da
332 es oft einfach ist, {\em irgendeine} Lösung anzugeben. Die angegebenen
333 Algorithmen verwenden als einfache initiale Lösung häufig das
334 \emph{Odd-Even-Transpositionsort}-Netzwerk, das in
335 Abschnitt~\ref{sect:odd_even_transpositionsort} beschrieben wird. Zum anderen
336 muss eine Methode für die Rekombination existieren. Das ist insbesondere dann
337 problematisch, wenn {\em Nebenbedingungen} eingehalten werden müssen. Die in
338 dieser Arbeit verwendeten Rekombinationsmethoden sind so gewählt, dass die
339 Nebenbedingungen nicht verletzt werden.
341 Beim Aussuchen von zufälligen Lösungen aus der Population, der
342 \emph{Selektion}, werden gute Lösungen bevorzugt. Wie sehr diese Lösungen
343 bevorzugt werden, hat einen starken Einfluss auf das Verhalten des
344 Algorithmus. Werden gute Lösungen stark bevorzugt, konvergiert der Algorithmus
345 schnell gegen ein (lokales) Optimum. Dieses \textit{Exploitation} (Englisch
346 für „Ausnutzung“) genannte Verhalten sorgt dafür, dass sich der Algorithmus
347 schnell auf eine Lösung festlegt und andere, möglicherweise bessere lokale
348 Optima nicht mehr findet. Werden gute Lösungen hingegen nur wenig bevorzugt,
349 erforscht der Algorithmus den Lösungsraum in viele Richtungen. Dieses
350 \textit{Exploration} (Englisch für „Erforschung“) genannte Verhalten sorgt
351 zwar dafür, dass der Algorithmus langsamer auf ein Optimum zusteuert, dafür
352 findet er aber in der Regel bessere Lösungen.
354 Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
355 Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
356 nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
357 eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
358 beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
359 zwischen verschiedenen Leitungszahlen stark unterscheiden.
361 Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
362 unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
363 \emph{Mutation}. Dabei werden Lösungen zufällig verändert, so dass auch andere
364 Lösungen „in der Nähe“ von direkten Nachfolgern erreicht werden können. Das
365 hilft insbesondere bei der intensiven Suche in der Nähe eines lokalen Optimums
366 aber auch beim „Ausbrechen“ aus lokalen Optima und finden noch besserer
369 Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
370 verbunden, dass anschließend die Sortiereigenschaft des resultierenden
371 \emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
372 Hinzufügen eines zufälligen Komparators diese Eigenschaft zer\-stö\-ren kann.
373 Beim Suchen möglichst effizienter Netzwerke ist das zufällige Entfernen von
374 Komparatoren interessanter, was die Sortiereigenschaft fast immer aufhebt.
376 Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
377 die \emph{Sortiernetzwerke} selbst, sondern verzichten entweder ganz auf
378 Mutation oder mutieren lediglich Transformationen von Sortiernetzwerken, die
379 die Sortiereigenschaft erhalten. Transformationen von Sortiernetzwerken werden
380 in Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der
381 Mutation einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
383 \begin{figure} \begin{center} \input{images/16-hillis.tex} \end{center}
384 \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
385 Es besteht aus 61~Komparatoren in 11~Schichten.} \label{fig:16-hillis}
386 \end{figure} Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
387 Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
388 \emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
389 zu optimieren~\cite{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
390 daran gemessen, bei wie vielen Komparatornetzwerken sie beweisen konnten, dass
391 sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen
392 (Komparatornetzwerken) nicht alle 0-1-Folgen, sondern nur erfolgreiche
393 Parasiten (schwierige Eingaben) überprüft werden. Auf diese Art und Weise
394 gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
395 anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
399 \subfigure{\input{images/13-juille-0.tex}}
400 \subfigure{\input{images/13-juille-1.tex}}
401 \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des
402 END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in
404 \label{fig:13-juille}
406 \textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
407 Non-Determinism} (END) nannte~\cite{J1995}. Dabei handelt es sich nicht um
408 einen der \emph{Evolutionären Algorithmen}, wie sie hier vorgestellt wurden,
409 sondern um eine verteilte, probabilistische Breitensuche, die an die
410 \emph{Strahlsuche} (englisch: \textit{beam search}), ein Verfahren der
411 Künstlichen Intelligenz, angelehnt ist. Die aufwendigste Operation bei diesem
412 Ansatz ist die Bewertungsfunktion, die abschätzt, wie viele Komparatoren zu
413 einem Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
414 erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
415 anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
416 bekannten (Abbildung~\ref{fig:13-juille}).
419 \section[Konstruktionsverfahren]{Konstruktionsverfahren für Sortiernetzwerke}
420 \label{sect:konstruktive_netzwerke}
422 Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere ein
423 häufig verwendeter Baustein, sogenannte \emph{Mischer}\footnote{Eine
424 Fehlübersetzung aus dem Englischen, von \textit{to~merge} (Deutsch:
425 zusammenfügen). Da der Begriff des "`mischens"' beziehungsweise der
426 "`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
427 in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
428 beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
429 Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
431 % \todo{Drei oder vier Verfahren?}
433 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
434 \label{sect:odd_even_transpositionsort}
436 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
437 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
438 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
439 Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für
444 \input{images/oe-transposition-8.tex}
446 \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.}
447 \label{fig:odd-even-transposition-08}
450 Dass das \emph{Odd-Even-Transpositionsort}-Netzwerk tatsächlich jede beliebige
451 Eingabe sortiert, ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
452 sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
453 Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt.
455 Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
456 indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
457 Herausschneiden einer Leitung reduziert. In
458 Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
459 beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
460 Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. Die Rekursion endet
461 beim \emph{Odd-Even-Transpositionsort}-Netzwerk mit drei Eingängen, bei dem
462 das Minimum auf der untersten, das Maximum auf der obersten und der mittlere
463 Wert auf der mittleren Leitung landet. Folglich ist die Ausgabe bei
464 $\operatorname{OET}(3)$ sortiert.
466 Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
467 Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
468 sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
469 (n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
470 Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
471 ($\Theta(n \log (n)^2)$), die in weniger Schichten,
472 ($\Theta(\log (n)^2)$), angeordnet sind.
474 Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
475 folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
476 Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
477 finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
480 Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer,
481 beziehungsweise mehrerer Leitungen, um die Anzahl der Leitungen eines
482 Sortiernetzwerks zu reduzieren. Die Technik wird in Detail im
483 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
485 \subsection{Das bitone Mergesort-Netzwerk}
487 Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
488 Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
489 veröffentlicht wurde. Es ist deutlich effizienter als das
490 Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
491 Komparatoren als auch der benötigten Zeit, also der Anzahl der Schichten.
493 Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
494 sortierte Listen zusammenfügen (Englisch: \textit{to~merge}) kann. Dieser
495 \emph{„bitone Mischer“} (Englisch: \textit{bitonic merger}) genannte Baustein
496 verleiht dem Sortiernetzwerk seinen Namen.
498 Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
499 Instanzen des Netzwerks, deren Leitungszahl $n = 2^t$ eine Zweierpotenz ist.
500 Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
502 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
504 Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen
505 Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine
506 beliebige \emph{bitone Folge} in eine sortierte Liste umordnen kann. Eine
507 \emph{bitone Folge} ist eine monoton steigende Folge, gefolgt von einer
508 monoton absteigenden Folge, oder ein zyklischer Shift davon.
509 Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten,
510 die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das
511 \emph{bitone Mergesort}-Netzwerk zeigen die
512 Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie
513 erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste
514 aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass
515 das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) beziehungsweise
516 kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge
521 \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
522 \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
523 \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
524 \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
525 \caption{Beispiele bitoner Folgen.}
526 \label{fig:beispiel-biton}
531 \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
533 \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
534 \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
535 aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
536 der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
537 resultierenden Teilfolgen sind wiederum biton.}
538 \label{fig:bitonic-merge-schema}
541 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
542 ${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
543 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
544 sortiert, die Folge $V$ sei absteigend sortiert:
546 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
547 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
549 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
550 Positionen verglichen und ggf. vertauscht:
552 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
554 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
555 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
556 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
557 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
558 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
559 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
560 "`linken"' Folge $u_{m-1}$ kleiner ist als das kleinste Element der
561 "`rechten"' Folge $v_{m-1}$. Daraus folgt, dass sich das Resultat in zwei
562 bitone Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
563 absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
564 zeigt die Situationen vor und nach diesem Schritt des Mischers schematisch.
566 Um die Folge vollständig zu sortieren, müssen anschließend die beiden
567 resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
568 mithilfe des bitonen Mischers, mit zwei Instanzen von
569 $\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem
570 bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als
571 Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
574 Der bitone Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
575 lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
576 notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
577 „echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
578 Schema des bitonen Mischers für zwei aufsteigend sortierte Folgen. Durch das
579 Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
580 Statt an eine Treppe erinnert das Muster nun an einen Trichter.
582 Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
583 die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
584 $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
585 $\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren
586 besteht, die in $\log(n)$~Schichten angeordnet werden können.
588 \subsubsection{Das bitone Mergesort-Netzwerk}
590 Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
591 Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
592 zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe
593 $\bs{\frac{n}{2}}$ für je die Hälfte der Eingänge, sowie dem bitonen Mischer
594 für $n$~Leitungen $\operatorname{BM}(n)$. Das Rekursionsende ist das bitone
595 Mergesort-Netzwerk mit nur einer Leitung $\operatorname{BS}(1)$, welches als
596 leeres Komparatornetzwerk definiert ist. Entsprechend sind die
597 Komparatornetzwerke $\operatorname{BM}(2)$ und $\operatorname{BS}(2)$
600 Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
601 (Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
602 rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so
603 alle Komparatoren in die gleiche Richtung zeigen.
607 \input{images/batcher-8.tex}
609 \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~Eingänge.
610 Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden bitonen
611 Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven
612 Schritt hinzugefügt wurden (grün).}
613 \label{fig:bitonic-08}
616 Das Sortiernetzwerk~$\operatorname{BS}(8)$ ist in
617 Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
618 beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
619 Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
620 die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
623 Das \emph{bitone Mergesort}-Netzwerk mit einer Leitungszahl $n = 2^d$, die
624 eine Zweierpotenz ist, besteht aus $\frac{1}{4} n \log(n) \log(n+1) =
625 \Theta\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2}
626 \log(n) \log(n+1) = \Theta(\log(n)^2)$ Schichten angeordnet sind.
628 \subsection{Das Odd-Even-Mergesort-Netzwerk}
630 Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort}-Netzwerk
631 (OES) und das \emph{Odd-Even-Transpositionsort}-Netzwerk (siehe
632 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
633 OES dem \emph{bitonen Mergesort}-Netzwerk, das im vorherigen Abschnitt
634 vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
635 \textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
636 beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
637 darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
639 \subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer}
641 Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein
642 Komparatornetzwerk, das zwei sortierte Folgen mit $n$ beziehungsweise $m$
643 Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
644 zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
645 \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
646 vorgestellt wurde. Im allgemeinen Fall, wenn die Anzahl der Leitungen keine
647 Zweierpotenz ist, kann das \emph{bitonic-Merge}-Netzwerk schneller sein
648 als das \emph{Odd-Even-Merge}-Netzwerk.~\cite{KNUTH}
650 Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die
651 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
652 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
653 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
654 $W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
656 w_i = \left\{ \begin{array}{ll}
665 \input{images/oe-merge.tex}
667 \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die
668 beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$,
669 die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der
670 Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt
671 dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den
672 rekursiven Aufbau verstärkt.}
676 Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der
677 geraden Indizes und je eine Liste der ungeraden Indizes.
679 U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
680 U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
681 V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
682 V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
685 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$,
686 beziehungsweise die ungeraden Folgen $U_{\textrm{ungerade}}$ und
687 $V_{\textrm{ungerade}}$ werden rekursiv von kleineren \emph{Odd-Even}-Mischern
688 zusammengefügt, so dass sich am Ausgang der Mischer die Folgen
690 W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
691 W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
695 Anschließend werden die Komparatoren zwischen benachbarten Leitungen
698 w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
700 die die Folge~$W$ sortieren. Den schematischen Aufbau des
701 \emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}.
703 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
704 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
705 entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
706 offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
709 \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
710 \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
711 einzelnen Komparator.
714 Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge
715 sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den
716 geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise
717 $V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den
718 ungeraden Teilfolgen $U_{\textrm{ungerade}}$ beziehungsweise
719 $V_{\textrm{ungerade}}$ --~die Einsen verhalten sich entsprechend umgekehrt.
720 Das trifft demnach auch auf die Folgen $W_{\textrm{gerade}}$ und
721 $W_{\textrm{ungerade}}$ entsprechend zu:
723 \left|W_{\textrm{gerade}}\right|_0
724 &=& \left|U_{\textrm{gerade}}\right|_0
725 + \left|V_{\textrm{gerade}}\right|_0
726 = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
727 + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
728 \left|W_{\textrm{ungerade}}\right|_0
729 &=& \left|U_{\textrm{ungerade}}\right|_0
730 + \left|V_{\textrm{ungerade}}\right|_0
731 = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
732 + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
734 Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
735 als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
736 Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
737 wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält als
738 $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
739 Ausgabe zu sortieren. Diese wird von den Komparatoren ausgeführt, die
740 benachbarte Leitungen miteinander vergleichen. Die jeweiligen Situationen sind
741 in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
745 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
747 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
749 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
750 \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
751 kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der
752 Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
753 letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
755 \label{fig:oe-post-recursive}
758 Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
759 bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$
760 Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
761 Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
762 Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
764 Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
765 allgemeinen Fall verwendet, hängt gemäß der rekursiven Definition von der
766 Länge der Eingabefolgen, $n$ und $m$ ab:
768 K(n,m) = \left\{ \begin{array}{ll}
769 nm, & \mathrm{falls} \quad nm \leqq 1 \\
770 K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right)
771 + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right)
772 + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1
775 Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
776 anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
777 dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.
779 Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
780 Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
781 erste Rekursionsschritt der OEM-Konstruktion fügt
782 $\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
783 Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
784 diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer
785 $\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
786 einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
787 \frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
789 \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1
791 Komparatoren eingespart. Damit ergibt sich
793 K\left(n = 2^{t-1}, n = 2^{t-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
795 für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^t)$
798 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
800 Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ besteht, wie
801 das \emph{bitone Mergesort}-Netzwerk, rekursiv aus kleineren Varianten von
802 sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die
803 effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
804 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
805 \oes{n} aus $\oes{\left\lceil\frac{n}{2}\right\rceil}$,
806 $\oes{\left\lfloor\frac{n}{2}\right\rfloor}$ und
807 $\oem{\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor}$.
808 Die Rekursion endet mit $\operatorname{OES}(1)$ und $\operatorname{OES}(0)$,
809 die als leere Komparatornetzwerke definiert sind.
813 \input{images/oe-mergesort-8.tex}
815 \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~Eingänge. Markiert
816 sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
817 \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade
818 Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
819 Komparatoren zwischen benachbarten Leitungen (grün).}
820 \label{fig:odd-even-mergesort-08}
823 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
824 zu sehen. Rot markiert sind die beiden rekursiven Instanzen
825 $\operatorname{OES}(4)$. Die anderen Blöcke stellen den
826 \emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind
827 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
828 die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.
830 Im Allgemeinen ist die Anzahl der Komparatoren, die vom
831 \emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der
832 Definition, beziehungsweise der Konstruktionsanleitung abzulesen:
834 k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
835 + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
836 + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
838 Da es schwierig ist für $K(n,m)$ eine geschlossene Form anzugeben, ist eine
839 geschlossene Darstellung von $k(n)$ ebenfalls nicht ohne weiteres möglich. Es
840 ist allerdings bekannt, dass $k(n)$ in $\Theta\left(n \left(\log
841 (n)\right)^2\right)$ enthalten ist.
843 Für den wichtigen Spezialfall, dass $n = 2^t$ eine Zweierpotenz ist, kann die
844 Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
845 Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
847 k(n = 2^t) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
852 % 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))
853 % oem1(n) = oem(ceil(.5*n),floor(.5*n))
854 % oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
857 %\item Pairwise sorting-network
860 \subsection{Das Pairwise-Sorting-Netzwerk}
862 Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
863 für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
864 Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
865 Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
866 \emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
867 das \emph{Odd-Even-Mergesort}-Netzwerk.
870 \section{Transformation von Sortiernetzwerken}
871 \label{sect:tranformation}
873 \subsection{Komprimieren}
875 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
876 gleichzeitig ausgewertet werden, wie bereits in
877 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
878 Transformationen, insbesondere das Entfernen einer Leitung wie in
879 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben, kann es vorkommen, dass
880 die Komparatoren eines Sortiernetzwerks nicht mehr in der kleinstmöglichen
881 Anzahl von \emph{Schichten} angeordnet sind. Unter \emph{Komprimierung} wird
882 eine (Neu-)Gruppierung der Komparatoren verstanden, die jeden Komparator so
883 früh wie möglich ausführt. So entsteht die kleinstmögliche Anzahl von
884 \emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
886 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
887 Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:bewertung}
888 beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
889 Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
890 die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
891 Komprimierung durchgeführt werden.
893 \subsection{Normalisieren}
894 \label{sect:normalisieren}
898 \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
899 \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
900 \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
901 transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
902 intuitiven Konstruktion und die normalisierte Variante.}
903 \label{fig:beispiel_normalisieren}
906 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
907 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
908 zeigen.\footnote{Die Konvention in dieser Arbeit ist, dass in diesem Fall alle
909 Pfeile nach unten zeigen. Das Minimum wird auf der untersten, das Maximum auf
910 der obersten Leitung ausgegeben.} Jedes Sortiernetzwerk kann in eine
911 normaliesierte Variante transformiert werden. Dazu gibt beispielsweise
912 \emph{Donald~E. Knuth} in~\cite{KNUTH} einen Algorithmus an.
914 Abbildung~\ref{fig:beispiel_normalisieren} stellt das \emph{bitone
915 Mergesort}-Netzwerk in zwei Varianten dar. Abbildung~\ref{fig:bitonic-nonstd}
916 zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
917 Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
918 die untere und die obere Hälfte gegenläufig sortiert. Das heißt, dass nach
919 drei Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert
920 ist. In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der
921 rekursiven Definition.
923 In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
924 Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die selbe
925 Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen-
926 und das Trichtermuster zu sehen.
928 \subsection{Zwei Netzwerke kombinieren}
930 Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden
931 zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
932 Sortiernetzwerk zusammenzufassen.
934 Diese Technik wurde in den vorangegangen Abschnitten bereits verwendet,
935 beispielsweise um zwei \emph{bitone Mergesort}-Netzwerke mit jeweils der
936 halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
937 einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
938 \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ wurde auf diese Art
939 und Weise rekursiv aufgebaut.
941 Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
942 Folgen. \emph{Wie} diese Folgen sortiert wurden ist unerheblich. Entsprechend
943 können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
944 zu sortieren und die Ausgaben mit einem der beschriebenen Mischer
947 Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
948 $\operatorname{BS}(8)$ mit je 8~Leitungen mit dem
949 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
950 Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
951 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
952 80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
954 Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren),
955 beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“
956 Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk.
957 Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt
958 beispielsweise 26~Komparatoren, die in 9~Schichten angeordnet sind. Es sind
959 allerdings Sortiernetzwerke mit 9~Eingängen bekannt, die lediglich
960 25~Komparatoren in 7~Schichten benötigen. Wenn zwei dieser Netzwerke mit dem
961 \emph{Odd-Even}-Mischer kombiniert werden, entsteht ein 18-Sortiernetzwerk,
962 das aus 80~Komparatoren in 11~Schichten besteht. Damit ist das resultierende
963 Netzwerk genauso schnell wie das Sortiernetzwerk mit 18~Eingängen, das
964 \textit{Sherenaz~W. Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer
965 Arbeit „An 11-Step Sorting Network for 18~Elements“~\cite{BB2009} vorstellen,
966 benötigt aber 6~Komparatoren weniger. $\operatorname{OES}(18)$ benötigt
967 82~Komparatoren in 13~Schichten.
969 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
970 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
971 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
972 Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die
973 letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen
974 die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
975 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
976 nur mit exponentiellem Aufwand möglich ist.
978 \subsection{Leitungen entfernen}
979 \label{sect:leitungen_entfernen}
981 Im vorherigen Abschnitt wurde gezeigt, dass es mithilfe von \emph{Mischern}
982 möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
983 ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
984 beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
985 sich die Anzahl der Eingänge nicht verändert. Es soll wieder ein
986 Sortiernetzwerk mit $n$~Eingängen entstehen.
988 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
989 Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
990 „eliminiert“. Dazu wird angenommen, dass das Minimum oder das Maximum an einem
991 bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das
992 Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an
993 einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten
994 Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und
995 welche dafür sorgen, dass der Wert die Leitung wechselt, da das Minimum jeden
996 Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
997 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
998 das \emph{Odd-Even-Transpositionsort}-Netzwerk.
1000 Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf
1001 dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk
1002 eindeutig festgelegt.
1006 \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
1007 durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
1008 \subfigure[Komparatoren, die einen Wechsel der Leitungen bewirken, werden
1009 durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
1010 \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit
1011 7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
1012 \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die
1013 Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
1014 \caption{Eine Leitung wird aus dem
1015 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
1016 markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
1017 nach unten weiter gegeben wird, ist der Pfad fest vorgegeben. Da die
1018 restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
1019 Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
1020 \label{fig:oe-transposition-cut}
1023 Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht,
1024 beziehungsweise ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der
1025 Leitung geführt haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
1026 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
1027 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
1028 ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
1029 das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
1030 die keine Komparatoren mehr berührt
1031 (Abbildung~\ref{fig:oe-transposition-cut1}).
1033 Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
1034 Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die
1035 \emph{Position} des Minimums oder des Maximums in der Eingabe angenommen. Ein
1036 Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher
1037 Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese
1038 Annahme auszuwerten -- über die verbleibenden Eingänge wurde keine Aussage
1039 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
1040 mit $(n-1)$~Elementen darstellen.
1042 Wird die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
1043 Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das
1044 Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung
1045 ein Minimum oder ein Maximum angenommen wird, wird das eliminieren einer
1046 Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise
1047 \emph{Maximum-Schnitt} bezeichnet.
1049 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
1050 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
1051 markierten Komparatoren sind verschoben, so dass sich eine kompaktere
1052 Darstellung ergibt. Außerdem ist das
1053 \emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
1054 zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
1055 kann entfernt werden.
1057 Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig
1058 \emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen
1059 \emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu
1060 \emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben.
1062 \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
1063 \label{sect:anzahl_schnittmuster}
1065 Der Eliminierungsschritt kann iterativ angewendet werden, um aus einem
1066 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
1067 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und
1068 Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
1069 $n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man
1070 die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein
1071 $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren.
1073 Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
1074 auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
1075 Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
1077 Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
1078 Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
1079 auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
1080 ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
1081 ergeben sich insgesamt
1083 \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!}
1086 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
1087 unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung
1088 und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks
1089 angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis.
1091 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
1092 möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
1093 vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken.
1094 Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der
1095 so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der
1096 möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten,
1097 $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/
1098 Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen
1100 \begin{equation}\label{eqn:anzahl_schnittmuster}
1101 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
1102 = 2^{k} \cdot \frac{n!}{k! (n-k)!}
1103 = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
1104 \quad (1 \leqq k < n)
1107 Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
1108 Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
1109 ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schnittmuster mit
1110 16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$
1111 Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große
1112 Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich.
1114 Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
1115 als die Anzahl der \emph{möglichen} Schnittmuster. Für jeden Komparator auf
1116 der ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
1117 Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
1118 unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
1119 der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
1120 Werte unterscheiden.
1122 Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
1123 Ausgangsmuster abgebildet, weil die Position des Minimums beziehungsweise des
1124 Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
1125 unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
1126 erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
1127 Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
1128 Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
1129 sich die Resultate auch in der ersten Schicht nicht unterscheiden.
1133 \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf}
1135 \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
1136 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
1137 $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
1138 unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
1139 \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone
1140 Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.}
1141 \label{fig:count-cuts-16}
1144 Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl
1145 der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
1146 \emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
1147 \emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je
1148 eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke \oes{16},
1149 \bs{16} und \ps{16} angewandt. Anschließend wurde mithilfe einer Hashtabelle
1150 überprüft, ob das resultierende Sortiernetzwerk schon von einem
1151 \emph{äquivalenten} Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk
1152 noch nicht in der Hashtabelle enthalten war, wurde der Zähler für
1153 unterschiedliche Schnittmuster erhöht und das Sortiernetzwerk eingefügt.
1155 Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
1156 \emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
1157 Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
1158 Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
1159 Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
1162 Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
1163 Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen
1164 Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen}
1165 Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des
1166 \emph{Odd-Even-Mergesort}-Netzwerks, 4973 ($\approx 0,15\%$) beim
1167 \emph{bitonen Mergesort}-Netzwerk und 18764 ($\approx 0,57\%$) beim
1168 \emph{Pairwise-Sorting}-Netzwerk. Zwar ist es möglich, dass mehr Iterationen
1169 die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen
1170 in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass
1171 die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
1172 vernachlässigbar klein ist.
1174 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
1175 Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
1176 Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern
1177 vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
1178 „kleine“ x-Werte verlässt.
1180 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
1181 können, kann man sich einer stochastischen Methode bedienen, der sogenannten
1182 \emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für
1183 schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von
1184 $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
1185 zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
1186 der Annahme, dass auf diese Art und Weise Sortiernetzwerke zufällig und
1187 gleichverteilt erzeugt werden, entspricht das Verhältnis der zufälligen
1188 Schnittmuster, die in $S$ enthalten sind, und $n$ gleich dem Verhältnis von
1189 $k$ und der Anzahl der unterschiedlichen Schnittmuster insgesamt. Damit kann
1190 die Anzahl der unterschiedlichen Schnittmuster abgeschätzt werden.
1194 \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
1196 \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
1197 \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
1198 $\operatorname{BS}(32)$.}
1199 \label{fig:collisions-10000-1000000-32}
1202 In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
1203 Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
1204 $\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
1205 jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
1206 \emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
1207 zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
1208 die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
1209 Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
1210 $\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2
1211 \cdot 10^6$ unterschiedlichen 16-Schnittmustern für $\operatorname{OES}(32)$
1212 und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
1216 \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
1218 \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
1219 \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
1220 zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
1221 Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
1222 unterschiedlichen Schnittmustern.}
1223 \label{fig:collisions-100000-1000000-32-ps}
1226 Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting}-Netzwerk
1227 $\operatorname{PS}(32)$ nicht betrachtet, da es für dieses Netzwerk viel mehr
1228 unterschiedliche 16-Schnittmuster gibt als für $\operatorname{OES}(32)$ und
1229 $\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der
1230 unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
1231 Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
1232 Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,
1233 ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem
1234 kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen
1235 Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
1236 $\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedlichen
1237 Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
1238 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
1239 waren. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
1240 unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
1241 vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als
1242 die Anzahl der \emph{möglichen} Schnittmuster.
1245 \section{Der \textsc{SN-Evolution}-Algorithmus}
1246 \label{sect:sn-evolution}
1248 Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
1249 Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
1250 (Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
1251 (Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
1252 Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
1253 in Abschnitt~\ref{sect:bewertung} behandelt.
1255 \subsection{Bewertungsfunktion}\label{sect:bewertung}
1257 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
1258 {\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
1259 die bei Sortiernetzwerken verfolgt werden können:
1261 \item Möglichst wenige Komparatoren („effizient“)
1262 \item Möglichst wenige Schichten („schnell“)
1267 \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}}
1268 \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}}
1269 \caption{Das effizienteste und das schnellste Sortiernetzwerk für
1270 16~Leitungen, das derzeit bekannt ist.}
1271 \label{fig:16-best-known}
1273 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken.
1274 Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für
1275 16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in
1276 Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte
1277 16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
1278 Abbildung~\ref{fig:16-voorhis} zu sehen.
1280 Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"'
1281 berücksichtigen kann, hat die folgende allgemeine Form:
1283 \operatorname{Guete}(S) = w_{\mathrm{Basis}}
1284 + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
1285 + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
1287 Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
1288 dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
1289 gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
1290 Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
1291 jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
1292 so schlecht ist wie man intuitiv vermuten könnte, zeigt der
1293 \textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
1295 Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen,
1296 ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert.
1297 Das heißt, dass das Ziel von \textsc{SN-Evolution} ist,
1298 $\operatorname{Guete}(S)$ zu \emph{minimieren}.
1300 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
1301 genommen werden. Ist er groß, wird der relative Unterschied der Güten
1302 verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
1303 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
1304 klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
1305 Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
1306 Exploitation}, das Finden (lokaler) Optima, bevorzugt.
1308 Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
1309 der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
1310 Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
1311 es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
1312 Leitungszahlen und Mischer-Typen experimentiert werden muss.
1314 Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
1315 Werte herausgestellt:
1317 w_{\mathrm{Basis}} &=& 0 \\
1318 w_{\mathrm{Komparatoren}} &=& 1 \\
1319 w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
1322 \subsection{Selektion}
1324 Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig
1325 aus der Population auswählt. Sie werden im folgenden Schritt miteinander
1326 rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht
1327 gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen
1328 eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen.
1329 Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für
1330 das Streben des Algorithmus nach besseren Lösungen.
1332 Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
1333 passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt
1334 und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
1336 Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt
1337 sich mit Pseudocode wie folgt beschreiben:
1342 für jedes Individuum in Population
1344 reziproke Güte := 1.0 / Guete(Individuum)
1345 Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
1346 Gütesumme := Gütesumme + reziproke Güte
1348 mit Wahrscheinlichkeit P
1350 Auswahl := Individuum
1356 Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die
1357 Rekombination zu erhalten. Das heißt, dass die Individuen bei
1358 \textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden.
1360 \subsection{Rekombination}
1361 \label{sect:sn-evolution:rekombination}
1363 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
1364 einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
1365 einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
1366 bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
1367 \emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
1368 Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
1369 in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
1371 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
1372 erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
1373 Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass
1374 nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können.
1376 \subsection{Mutation}
1378 Zu einem vollständigen evolutionären Algorithmus gehört außerdem die Mutation
1379 --~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
1380 Sortiernetzwerk zufällig zu verändern und dabei die Sortiereigenschaft zu
1381 erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
1382 Eigenschaft zerstören.
1384 Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
1385 Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
1386 Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
1387 Ausprobieren aller $2^n$~Bitmuster, wie in Abschnitt~\ref{sect:0-1-prinzip}
1390 Um das Potenzial einer Mutation abzuschätzen wurde in \textsc{SN-Evolution}
1391 eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population
1392 überprüft eine Funktion die Notwendigkeit jedes einzelnen Komparators. Dazu
1393 wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende
1394 Netzwerk die Sortiereigenschaft noch besitzt. Trotz des hohen Rechenaufwands
1395 -- bei 16-Sortiernetzwerken sind gut 4~Millionen Tests notwendig, um alle
1396 Komparatoren zu überprüfen -- waren die Ergebnisse ernüchternd: Nach circa
1397 1~Million Iterationen mit 16-Sortiernetzwerken fand der so modifizierte
1398 Algorithmus keinen einzigen Komparator, den er hätte entfernen können. Daher
1399 wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet.
1401 \subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer}
1405 \input{images/16-e1-bitonic-1296542566.tex}
1407 \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
1408 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1409 \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers}
1411 \label{fig:16-e1-bitonic-1296542566}
1414 Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
1415 als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
1416 Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in
1417 Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück.
1419 Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser
1420 Konfiguration gefunden werden, sind effizienter als das \emph{bitone
1421 Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
1422 Merge}-Netzwerk \bm{n} beruht. Das in
1423 Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
1424 benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
1426 Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
1427 bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n}
1428 sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als
1429 \bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit
1430 134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von
1431 schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen
1432 Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast}
1435 \begin{table}\label{tbl:sn-ev-bm-fast}
1437 \rowcolors{4}{black!5}{}
1438 \begin{tabular}{|r|r|r|r|r|}
1440 Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\
1442 ($n$) & Komp. & Schichten & Komp. & Schichten \\
1444 8 & \gcell 20 & 6 & 24 & 6 \\
1445 9 & \Gcell 26 & 8 & 28 & 8 \\
1446 10 & \gcell 31 & \gcell 8 & 33 & 9 \\
1447 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\
1448 12 & \gcell 42 & \gcell 9 & 46 & 10 \\
1449 13 & \Gcell 48 & 10 & 53 & 10 \\
1450 14 & \gcell 54 & 10 & 61 & 10 \\
1451 15 & \Gcell 61 & 10 & 70 & 10 \\
1452 16 & \gcell 67 & 10 & 80 & 10 \\
1453 17 & \Gcell 76 & 12 & 85 & 12 \\
1454 18 & \gcell 87 & \gcell 12 & 91 & 13 \\
1455 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\
1456 20 & \gcell 104 & \gcell 13 & 106 & 14 \\
1457 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
1458 22 & \gcell 118 & \gcell 14 & 123 & 15 \\
1459 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\
1460 24 & \gcell 133 & 15 & 144 & 15 \\
1463 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
1464 unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus
1465 wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet
1466 und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die
1467 Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
1468 $w_{\mathrm{Schichten}} = n$.}
1472 \subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
1476 \input{images/16-e1-oddeven-1296543330.tex}
1478 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
1479 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1480 \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers
1482 \label{fig:16-e1-oddeven-1296543330}
1485 Im vorherigen Abschnitt wurde gezeigt, dass der
1486 \textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
1487 Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
1488 \emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
1489 Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
1490 erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
1491 \emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
1492 \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
1493 nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
1494 Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen.
1496 Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
1497 mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
1498 Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht
1499 beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt
1500 \textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen.
1501 \oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der
1502 Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet
1503 sich in Tabelle~\ref{tbl:sn-ev-oem-fast}.
1507 %\input{images/08-e2-1237993371.tex}
1509 %\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
1510 %\label{fig:08-e2-1237993371}
1515 %\input{images/09-e2-1237997073.tex}
1517 %\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
1518 %\label{fig:09-e2-1237997073}
1523 %\input{images/09-e2-1237999719.tex}
1525 %\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
1526 %\label{fig:09-e2-1237999719}
1531 %\input{images/10-e2-1239014566.tex}
1533 %\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
1534 %\label{fig:10-e2-1239014566}
1537 \begin{table}\label{tbl:sn-ev-oem-fast}
1539 \rowcolors{4}{black!5}{}
1540 \begin{tabular}{|r|r|r|r|r|}
1542 Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
1544 & Komp. & Schichten & Komp. & Schichten \\
1546 8 & 19 & 6 & 19 & 6 \\
1547 9 & 26 & 8 & 26 & 8 \\
1548 10 & 31 & 9 & 31 & 9 \\
1549 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
1550 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
1551 13 & 48 & 10 & 48 & 10 \\
1552 14 & 53 & 10 & 53 & 10 \\
1553 15 & 59 & 10 & 59 & 10 \\
1554 16 & 63 & 10 & 63 & 10 \\
1555 17 & 74 & 12 & 74 & 12 \\
1556 18 & 82 & 13 & 82 & 13 \\
1557 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
1558 20 & 97 & 14 & 97 & 14 \\
1559 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
1560 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
1561 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\
1562 24 & 128 & 15 & \gcell 127 & 15 \\
1565 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
1566 unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
1567 Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
1568 gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
1569 nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
1570 1$, $w_{\mathrm{Schichten}} = n$.}
1574 \subsection{Zufälliger Mischer}
1576 Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
1577 Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
1578 \emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
1579 Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
1580 12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
1581 82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
1582 um das beste Ergebnis beider Konstruktionen zu erreichen.
1583 \textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
1584 Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
1585 \emph{Odd-Even}-Mischer wählen.
1587 Die Ergebnisse von \textsc{SN-Evolution} bei einer zufälligen Wahl des
1588 Mischers in der Rekombinationsphase sind in Tabelle~\ref{tbl:sn-ev-rnd-fast}
1589 zusammengefasst. Bei den Leitungszahlen 12, 19, 21, 22 und 23 hat der
1590 Algorithmus Netzwerke mit einer Effizienz erzeugt, die mit nur einem
1591 Mischertyp nicht erreicht wurde. Die Ergebnisse mit den Leitungszahlen 18 und
1592 20 erreichen die Geschwindigkeit der Netzwerke, die mit dem \emph{bitonen
1593 Mischer} generiert wurden, und verbessern gleichzeitig die Effizienz.
1595 \begin{table}\label{tbl:sn-ev-rnd-fast}
1597 \rowcolors{4}{black!5}{}
1598 \begin{tabular}{|r|r|r|r|r|r|r|}
1600 Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}}
1601 & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}}
1602 & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\
1604 ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\
1606 8 & 20 & 6 & \gcell 19 & 6 & \gcell 19 & 6 \\
1607 9 & 26 & 8 & 26 & 8 & 26 & 8 \\
1608 10 & 31 & \gcell 8 & 31 & 9 & 31 & \gcell 8 \\
1609 11 & \Gcell 37 & 9 & 38 & 9 & \Gcell 37 & 9 \\
1610 12 & 42 & 9 & 43 & 9 & \gcell 41 & 9 \\
1611 13 & 48 & 10 & 48 & 10 & 48 & 10 \\
1612 14 & 54 & 10 & \gcell 53 & 10 & \gcell 53 & 10 \\
1613 15 & 61 & 10 & \Gcell 59 & 10 & \Gcell 59 & 10 \\
1614 16 & 67 & 10 & \gcell 63 & 10 & 64 & 10 \\
1615 17 & 76 & 12 & \Gcell 74 & 12 & \Gcell 74 & 12 \\
1616 18 & 87 & \gcell 12 & \gcell 82 & 13 & 83 & \gcell 12 \\
1617 19 & 93 & 13 & 93 & 13 & \Gcell 92 & 13 \\
1618 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\
1619 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\
1620 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\
1621 23 & 134 & 14 & 129 & 14 & \Gcell 128 & 14 \\
1622 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\
1625 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
1626 unter Verwendung der verschiedenen Mischer. Der Algorithmus wurde mit dem
1627 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach
1628 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten
1629 $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
1630 $w_{\mathrm{Schichten}} = n$.}
1634 %\input{shmoo-aequivalenz.tex}
1637 \section{Der \textsc{SN-Markov}-Algorithmus}
1640 Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
1641 Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus
1642 einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
1643 ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
1644 verwendet und mit sich selbst kombiniert wird.
1646 Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk
1647 \emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
1648 Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke,
1649 die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit
1650 sich selbst und anschließendem Eliminieren der Hälfte der Leitungen hervorgehen
1651 können, heißen \emph{Nachfolger} von $S_0$.
1653 Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
1654 (gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
1655 Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
1656 Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von
1657 $S_0$ ist, das heißt, dass $S_1$ durch die Rekombination von $S_0$ mit sich
1658 selbst erzeugt werden kann.
1660 Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
1661 der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
1662 sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
1663 Nachfolger zwar noch unter 20.000, bei den untersuchten
1664 32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$
1665 unterschiedliche Schnittmuster geschätzt.
1667 Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
1668 zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
1669 gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
1670 gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
1671 selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der
1672 Algorithmus wie folgt beschreiben:
1679 Nachfolger := kombiniere (Netzwerk, Netzwerk)
1680 Netzwerk := Nachfolger
1686 Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der
1687 Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem
1688 zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der
1689 \textsc{SN-Markov}-Algorithmus auf einem entsprechenden
1690 \emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens
1691 1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der
1692 Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler
1693 erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende
1694 prozentuale Verteilung zu sehen.
1696 Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators}
1697 eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
1698 Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
1699 um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
1700 Beispielsweise war die kleinste erreichte Komparatorzahl bei
1701 16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$
1702 gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$
1703 und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem
1704 Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
1705 unter den Graphen angegeben.
1709 \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}}
1710 \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}}
1711 \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}}
1712 \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}}
1713 \caption{Anzahl der Komparatoren von Sortiernetzwerken,
1714 die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet
1715 ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der
1716 gemessenen Daten darstellt.}
1717 \label{fig:markov-comparators}
1722 \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf}
1724 \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von
1725 \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem
1726 \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.}
1727 \label{fig:comparison-comparators}
1730 Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der
1731 \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
1732 \textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit
1733 \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl
1734 der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
1735 Startnetzwerk diente bei beiden Algorithmen das
1736 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
1737 x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
1738 ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
1739 wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je
1740 nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}.
1742 Sowohl der \textsc{SN-Markov}-Algorithmus, der das
1743 \emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
1744 \oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die
1745 bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind.
1746 Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger:
1747 Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit
1748 63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335
1749 \%$ rund 20~mal höher.
1751 Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem
1752 \emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist
1753 jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
1754 mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16}
1755 ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für
1756 Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein
1757 Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so
1758 vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
1759 Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das
1760 mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk
1765 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf}
1767 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
1768 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1769 % \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.}
1770 % \label{fig:markov-comparators-14}
1775 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf}
1777 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
1778 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1779 % \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.}
1780 % \label{fig:markov-comparators-16}
1785 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf}
1787 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen),
1788 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1789 % \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.}
1790 % \label{fig:markov-comparators-18}
1795 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
1797 % \caption{Zyklen, die beim \textit{Random Walk} des
1798 % \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
1799 % Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
1800 % y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
1801 % Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
1802 % \label{fig:markov-cycles-16}
1806 \section[\textsc{SN-Evolution-Cut}]{Der \textsc{SN-Evolution-Cut}-Algorithmus}
1807 \label{sect:sn-evolution-cut}
1809 Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
1810 Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
1811 Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
1812 möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
1813 von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}.
1815 Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
1816 in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
1817 Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$
1818 oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem
1819 $k$-Schnittmuster sind genau $k$ Zahlen ungleich Null.
1821 Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
1822 Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
1823 verwendet. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq n$. Anschließend
1824 werden zufällig Werte auf Null beziehungsweise 1 oder $-1$ gesetzt, um die
1825 Anzahl der Schnitte zu korrigieren.
1827 Die Mutation vertauscht entweder die Werte von zwei zufälligen Positionen oder
1828 multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu
1831 Die Eingabe für \textsc{SN-Evolution-Cut} ist ein $n$-Sortiernetzwerk und eine
1832 Zahl $k$, $1 \leqq k < n$, die angibt wie viele Leitungen entfernt werden
1833 sollen. Der Rückgabewert des \textsc{SN-Evolution-Cut}-Algorithmus ist ein
1834 \emph{$k$-Schnittmuster}. Wird das Schnittmuster auf das Sortiernetzwerk, mit
1835 dem der Algorithmus gestartet wurde, angewendet, entsteht ein möglichst
1836 schnelles und effizientes Sortiernetzwerk mit $m = n - k$ Leitungen. Da mit
1837 dem Eingabe-Netzwerk und dem zurückgegebenen $k$-Schnittmuster das
1838 $m$-Sortiernetzwerk eindeutig bestimmt ist, werden im Folgenden sowohl das
1839 $k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von
1840 \textsc{SN-Evolution-Cut} bezeichnet.
1842 \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
1843 \label{sect:sn-evolution-cut:bs}
1845 Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen
1846 Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll,
1847 ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke
1848 als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k
1849 = 6$ gestartet, resultiert das gefundene Schnittmuster in einem
1850 Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16}
1851 benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
1852 wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
1856 \input{images/16-ec-from-bs22.tex}
1858 \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
1859 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1860 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk
1861 $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4,
1862 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.}
1863 \label{fig:16-ec-from-bs22}
1866 Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen
1867 Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden,
1868 gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde
1869 mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten
1870 der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$,
1871 $w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder
1872 Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten
1873 befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des
1874 Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des
1875 resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der
1876 Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu
1881 \rowcolors{2}{black!5}{}
1882 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
1884 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
1886 9 & 21 & & & & & & & & & & & & & & & \\
1887 10 & 20 & 27 & & & & & & & & & & & & & & \\
1888 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\
1889 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\
1890 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\
1891 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\
1892 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\
1893 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\
1894 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\
1895 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\
1896 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\
1897 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\
1898 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\
1899 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\
1900 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\
1901 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
1903 \bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
1907 \caption{Anzahl der Komparatoren der Ergebnisse von
1908 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
1909 Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
1910 die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
1911 Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
1912 \label{tbl:ec-bs-efficiency}
1915 Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut}
1916 mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der
1917 gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von
1918 $m=23$) ein Ergebnis, das effizienter als \bs{m} ist.
1920 In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein
1921 effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut}
1922 gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren
1923 3~weniger als \bs{19}.
1925 Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke,
1926 beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein
1927 Sortiernetzwerk mit 31~Komparatoren gefunden.
1931 \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
1932 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}}
1933 \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
1934 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}}
1935 \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
1936 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}}
1937 \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
1938 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}}
1939 \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
1940 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
1941 erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
1942 \label{fig:ec-bs-fast_networks}
1945 Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
1946 \textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
1947 das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
1948 Tabelle~\ref{tbl:ec-bs-speed} ist die Anzahl der Schichten, die die Ergebnisse
1949 von \textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren,
1950 aufgelistet. Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n},
1951 jede Spalte enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die
1952 Zellen enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
1956 \rowcolors{2}{black!5}{}
1957 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
1959 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
1961 9 & 6 & & & & & & & & & & & & & & & \\
1962 10 & 6 & 8 & & & & & & & & & & & & & & \\
1963 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
1964 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
1965 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
1966 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
1967 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
1968 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
1969 17 & 6 & 8 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
1970 18 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
1971 19 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
1972 20 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
1973 21 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
1974 22 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
1975 23 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
1976 24 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
1978 \bs{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
1982 \caption{Anzahl der Schichten der Ergebnisse von
1983 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
1984 Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
1985 die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
1986 Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
1987 \label{tbl:ec-bs-speed}
1990 Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die
1991 schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke,
1992 die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
1993 werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.
1995 Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das
1996 Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m}
1997 führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt
1998 werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht
1999 einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m
2000 = 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu
2001 reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
2002 noch größer gewählt werden.
2004 Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von
2005 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten
2006 werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in
2007 Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im
2008 Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n =
2009 37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19}
2010 und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein
2011 Beispiel für ein solches Netzwerk ist in
2012 Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen.
2016 \rowcolors{2}{black!5}{}
2017 \begin{tabular}{|r|r|r|}
2019 $n$ & Komp. & Schichten \\
2039 \rowcolor{green!10!white!95!black}
2043 \bs{19} & 98 & 14 \\
2044 \oes{19} & 91 & 14 \\
2048 \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
2049 von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt
2050 wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als
2051 \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit
2052 13~Schichten die Effizienz der vorherigen
2053 Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese
2054 Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37}
2055 auf diese Art erzeugt wurde, ist in
2056 Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.}
2057 \label{tbl:ec-bs-19}
2060 \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
2061 wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode
2062 konstruiert wurde, durch systematisches Entfernen von Leitungen in einen
2063 ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert werden
2064 kann, so dass dieser alternative Mischer im Vergleich zu $\bm{\frac{n}{2} =
2065 2^{d-1}}$ Komparatoren einspart.
2067 Basierend auf diesen alternativen Mischern geben \textit{Mühlenthaler} und
2068 \textit{Wanka} eine Konstruktionsvorschrift für Sortiernetzwerke an, die
2069 gegenüber \bs{n} ${\frac{1}{4}n(\log n - 1)}$ Komparatoren einspart.
2070 Beispielsweise wird ein 16-Sortiernetzwerk angegeben, das nur 68~Komparatoren
2071 benötigt. Dieses Netzwerk ist in Abbildung~\ref{fig:16-muehlenthaler}
2076 \input{images/16-muehlenthaler.tex}
2078 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
2079 10~Schichten. Das Netzwerk wurde 2010 von \textit{Mühlenthaler} und
2080 \textit{Wanka} aus optimierten bitonen Mischern konstruiert und
2081 in~\cite{MW2010} veröffentlicht.}
2082 \label{fig:16-muehlenthaler}
2087 \input{images/16-ec-from-bs32.tex}
2089 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
2090 10~Schichten. Das Netzwerk wurde von dem Algorithmus
2091 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort-Netzwerk}
2092 $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
2093 \label{fig:16-ec-from-bs32}
2098 \input{images/16-ec-from-bs32-normalized.tex}
2100 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
2101 10~Schichten. Das Netzwerk wurde von dem Algorithmus
2102 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
2103 $\operatorname{BS}(32)$ durch 16~Schnitte erzeugt.}
2104 \label{fig:16-ec-from-bs32-normalized}
2107 Startet man {\sc SN-Evolution-Cut} mit dem \emph{bitonen Mergesort}-Netzwerk
2108 $\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
2109 Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
2110 16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den
2111 Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
2112 zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
2113 und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26,
2114 29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch
2115 \textsc{SN-Evolution-Cut} gefunden wurde.
2116 Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
2117 nachdem das Schnittmuster angewendet und das Netzwerk normalisiert wurde.
2118 % Eine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist
2119 % in diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten
2120 % des Netzwerks scheinen rein zufällig zu sein.
2123 % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
2124 % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
2125 % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
2128 \input{images/32-ec-from-bs64.tex}
2130 \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
2131 15~Schichten. Das Netzwerk wurde von dem Algorithmus
2132 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
2133 $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
2135 $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
2136 $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
2137 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
2138 \label{fig:32-ec-from-bs64}
2141 Wenn \textsc{SN-Evolution-Cut} mit dem \bs{64}-Netzwerk und $k = 32$ gestartet
2142 wird, findet der Algorithmus 32-Sortiernetzwerke, die effizienter sind als
2143 32-Sortiernetzwerke, die nach \textit{Mühlenthalers} und \textit{Wankas}
2144 Methode konstruiert werden. Ein von \textsc{SN-Evolution-Cut} aus \bs{64}
2145 generiertes 32-Sortiernetzwerk ist in Abbildung~\ref{fig:32-ec-from-bs64}
2146 dargestellt. Das \emph{bitone Mergesort}-Netzwerk \bs{32} benötigt
2147 240~Komparatoren, ein aus den optimierten Mischern aufgebautes Netzwerk
2148 verbessert die Effizienz auf 208~Komparatoren. Das Ergebnis von
2149 \textsc{SN-Evolution-Cut} kommt mit nur 206~Komparatoren aus. Die
2150 Geschwindigkeit aller genannten Sortiernetzwerke ist mit 15 parallelen
2151 Schritten identisch.
2153 Wenn die Leitungszahl des Eingabenetzwerks keine Zweierpotenz ist, kann
2154 \textsc{SN-Evo\-lu\-tion-Cut} auch 16-Sortiernetzwerke erzeugen, die diese
2155 Effizienz unterbieten. Das geht aus den Daten in
2156 Tabelle~\ref{tbl:ec-bs-efficiency} hervor. Ein 16-Sortiernetzwerk mit
2157 67~Komparatoren, das von \textsc{SN-Evolution-Cut} generiert wurde, ist in
2158 Abbildung~\ref{fig:16-ec-from-bs22} dargestellt.
2160 Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
2161 unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
2162 gute Schnittmuster anzugeben.
2164 Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
2165 Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
2166 Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
2167 Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
2168 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
2169 ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
2170 die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
2171 Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
2172 mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
2174 Dass die Sortiernetzwerke, die mit den Schnittmustern von
2175 \textsc{SN-Evolution-Cut} entstehen, keine erkennbare Struktur haben, ist
2176 jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere von der
2177 Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
2178 \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(n)$ und
2179 $k$~Schnitten gestartet, so ist das beste Ergebnis immer das
2180 $\operatorname{OET}(n-k)$-Netzwerk.
2182 \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
2183 \label{sect:sn-evolution-cut:oes}
2185 Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk
2186 \oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die
2187 genauso effizient und schnell wie das entsprechende
2188 \emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der
2189 Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus
2190 \oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency}
2195 \rowcolors{2}{black!5}{}
2196 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2198 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2200 9 & 19 & & & & & & & & & & & & & & & \\
2201 10 & 19 & 26 & & & & & & & & & & & & & & \\
2202 11 & 19 & 26 & 31 & & & & & & & & & & & & & \\
2203 12 & 19 & 26 & 31 & 37 & & & & & & & & & & & & \\
2204 13 & 19 & 26 & 31 & 37 & 41 & & & & & & & & & & & \\
2205 14 & 19 & 26 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
2206 15 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
2207 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
2208 17 & 19 & 26 & 31 & 38 & 41 & 48 & 53 & 59 & 63 & & & & & & & \\
2209 18 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & & & & & & \\
2210 19 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & & & & & \\
2211 20 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & & & & \\
2212 21 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & & & \\
2213 22 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & & \\
2214 23 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & \\
2215 24 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
2219 \caption{Anzahl der Komparatoren der Ergebnisse von
2220 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2221 \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
2222 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
2223 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2225 \label{tbl:ec-oes-efficiency}
2230 \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das
2231 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}}
2232 \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das
2233 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}}
2234 \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m =
2235 11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
2236 erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m}
2238 \label{fig:ec-oes-fast_networks}
2241 Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt
2242 schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein
2243 $m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes
2244 Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit
2245 war allerdings in allen beobachteten Fällen nur dann möglich, wenn
2246 zusätzliche Komparatoren in Kauf genommen wurden. In den
2247 Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser
2248 Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu
2249 beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
2250 Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.
2252 Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim
2253 \emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die
2254 Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war
2255 jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere
2256 Geschwindigkeit zu erreichen.
2258 In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von
2259 \textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots
2260 19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles
2261 19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die
2262 resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit
2263 $k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des
2264 \emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in
2265 13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht.
2269 \rowcolors{2}{black!5}{}
2270 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2272 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2274 9 & 6 & & & & & & & & & & & & & & & \\
2275 10 & 6 & 8 & & & & & & & & & & & & & & \\
2276 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
2277 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
2278 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
2279 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
2280 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
2281 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
2282 17 & 6 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
2283 18 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
2284 19 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
2285 20 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
2286 21 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
2287 22 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
2288 23 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
2289 24 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
2291 \oes{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
2295 \caption{Anzahl der Schichten der Ergebnisse von
2296 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2297 \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
2298 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
2299 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2301 \label{tbl:ec-oes-speed}
2306 \rowcolors{2}{black!5}{}
2307 \begin{tabular}{|r|r|r|}
2309 $n$ & Komp. & Schichten \\
2331 \bs{19} & 98 & 14 \\
2332 \oes{19} & 91 & 14 \\
2336 \caption{Komparatoren und Schichten von Sortiernetzwerken, die von
2337 \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$
2338 ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die
2339 Effizienz von 91~Komparatoren nicht mehr erreichbar.}
2340 \label{tbl:ec-oes-19}
2343 In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
2344 viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
2345 Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und
2346 $\operatorname{PS}(32)$ besitzen. Eines der Ergebnisse war, dass von diesen
2347 Sortiernetzwerken das \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten
2348 unterschiedlichen 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen.
2349 Entsprechend ist es wenig verwunderlich, dass \textsc{SN-Evolution-Cut}
2350 gestartet mit $\operatorname{OES}(32)$ sehr schnell\footnote{Ein
2351 entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen
2352 geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe
2353 Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf
2354 derzeitigen Computern.} ein gutes 16-Schnittmuster findet.
2356 Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
2357 bezüglich Effizienz und Geschwindigkeit identisch ist zu \oes{16}, ist
2358 $\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
2359 8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
2360 Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
2361 Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
2365 \input{images/16-ec-from-oes32-cut.tex}
2367 \caption{Visualisierung eines 16-Schnittmusters, das auf
2368 $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
2369 bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
2370 resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
2372 \label{fig:16-ec-from-oes32-cut}
2377 \input{images/16-ec-from-oes32.tex}
2379 \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
2380 Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
2381 einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
2382 berechnet wurde. Das Schnittmuster ist in
2383 Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
2384 \label{fig:16-ec-from-oes32}
2387 Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
2388 4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
2389 Beobachtung kann man das regelmäßige Schnittmuster
2391 \textit{Eingang}_i = \left\{ \begin{array}{rl}
2392 \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
2393 -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
2394 ? & \quad \mathrm{sonst}
2397 ableiten. Es entfernt die Hälfte der Leitungen, vorausgesetzt die Anzahl der
2398 Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt effiziente
2399 Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine Zweierpotenz ist. Ein
2400 32-Sortiernetzwerk, das mit diesem Schnittmuster aus \oes{64} erzeugt wurde,
2401 ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
2405 \input{images/32-ec-from-oes64.tex}
2407 \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten.
2408 Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
2409 \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
2410 \label{fig:32-ec-from-oes64}
2413 Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die so
2414 erzeugten Sortiernetzwerke die Effizienz des
2415 \emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
2416 beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
2417 43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
2418 beider Sortiernetzwerke ist mit 10~Schichten identisch.
2420 Startet man hingegen den \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{24}
2421 und dem Ziel, ein gutes 12-Schnittmuster zu finden, hängt die Ausgabe von der
2422 verwendeten Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der
2423 Algorithmus Schnittmuster wie $\operatorname{MIN}(6, 7, 8, 9, 16, 17, 20,
2424 22)$, $\operatorname{MAX}(2, 4, 12, 14)$, dessen Ergebnis in
2425 Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
2426 Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
2427 werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
2428 gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
2429 werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
2430 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
2431 dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
2432 sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten
2433 angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie
2434 \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
2438 \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
2439 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
2440 \emph{Odd-Even-Mergesort}-Netzwerk generiert
2441 wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
2442 \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
2443 das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
2445 wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
2446 \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
2447 Ergebnis von der Bewertungsfunktion ab.}
2448 \label{fig:12-ec-from-oes24}
2451 Das \oes{24}-Sortiernetzwerk ist kein Einzelfall: \textsc{SN-Evolution-Cut}
2452 findet Sortiernetzwerke, die schneller sind als das entsprechende
2453 \emph{Odd-Even-Mergesort}-Netzwerk, unter anderem für das Sortiernetzwerke mit
2454 22, 24, 38, 40, 42, 44 und 46 Leitungen. In der folgenden Tabelle sind einige
2455 schnelle Netzwerke, die von \textsc{SN-Evolution-Cut} generiert werden können,
2456 charakterisiert. Die Eingabe für \textsc{SN-Evolution-Cut} war jeweils das
2457 \emph{Odd-Even-Mergesort}-Netzwerk mit der doppelten Leitungszahl.
2459 \begin{tabular}{|r|r|r|r|r|}
2461 Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\
2462 & \textsc{SN-EC} & \textsc{SN-EC} & \oes{n} & \oes{n} \\
2464 11 & 38 & 9 & 37 & 10 \\
2465 12 & 43 & 9 & 41 & 10 \\
2466 19 & 93 & 13 & 91 & 14 \\
2467 20 & 101 & 13 & 97 & 14 \\
2468 21 & 108 & 14 & 107 & 15 \\
2469 22 & 116 & 14 & 114 & 15 \\
2470 23 & 125 & 14 & 122 & 15 \\
2474 Abbildung~\ref{fig:23-ec-from-oes46} zeigt beispielhaft ein
2475 23-Sortiernetzwerk, das aus \oes{46} generiert wurde. Bemerkenswert an diesem
2476 Sortiernetzwerk ist insbesondere, dass \textsc{SN-Evolution-Cut} mit der
2477 Eingabe \bs{46} ein besseres Ergebnis liefert als mit der Eingabe \oes{46}. In
2478 beiden Fällen wird ein Sortiernetzwerk zurückgegeben, das im Vergleich zu
2479 \bs{23} beziehungsweise \oes{23} eine Schicht einspart.
2483 \input{images/23-ec-from-oes46-fast.tex}
2485 \caption{23-Sortiernetzwerk mit 125~Komparatoren in 14~Schichten.
2486 Das Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \oes{46} mit dem
2487 Schnittmuster $\operatorname{MIN}(6, 7, 9, 17, 19, 22, 29, 30, 32, 34, 38,
2488 44)$, $\operatorname{MAX}(4, 5, 11, 16, 18, 25, 31, 36, 39, 42, 45)$
2490 \label{fig:23-ec-from-oes46}
2493 \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
2495 Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
2496 Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
2497 (Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
2498 ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
2499 wie und warum es jede beliebige Eingabe sortiert.
2503 \rowcolors{2}{black!5}{}
2504 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2506 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2508 9 & 20 & & & & & & & & & & & & & & & \\
2509 10 & 20 & 27 & & & & & & & & & & & & & & \\
2510 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\
2511 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\
2512 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\
2513 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
2514 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
2515 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
2516 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\
2517 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\
2518 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\
2519 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\
2520 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\
2521 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\
2522 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\
2523 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\
2525 \ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\
2529 \caption{Anzahl der Komparatoren der Ergebnisse von
2530 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2531 \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
2532 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
2533 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2535 \label{tbl:ec-ps-speed}
2538 Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian
2539 Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
2540 definiert, verhält sich anders. Startet man \textsc{SN-Evolution-Cut} mit
2541 $\operatorname{PS}(32)$ und der Vorgabe, 16~Leitungen zu entfernen, erhält man
2542 ein Sortiernetzwerk, das die gleiche Anzahl Komparatoren und Schichten hat wie
2543 $\operatorname{PS}(16)$ und $\operatorname{OES}(16)$. Eines dieser
2544 Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
2548 \input{images/16-ec-from-ps32.tex}
2550 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
2551 10~Schichten. Das Netzwerk wurde von dem Algorithmus
2552 \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
2553 $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
2554 \label{fig:16-ec-from-ps32}
2557 Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht
2558 einsetzt und auch nicht auf einem Mischer basiert, ist das
2559 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
2560 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
2561 den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die
2562 strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die
2563 Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
2567 \input{images/32-pairwise-cut-16-pairwise.tex}
2569 \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu
2570 sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk
2572 \label{fig:ps16-from-ps32}
2575 Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
2576 regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
2577 schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
2578 einfache Schnittmuster
2580 \textit{Eingang}_i = \left\{ \begin{array}{rl}
2581 -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\
2582 \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\
2583 ? & \quad \mathrm{sonst}
2586 für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk
2587 $\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der
2588 dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das
2589 verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32}
2590 dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind
2591 diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden
2592 Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den
2593 „richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht
2594 werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende
2595 Netzwerk in schwarz gut zu erkennen.
2599 \input{images/16-pairwise.tex}
2601 \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
2602 ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das
2603 resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
2604 \label{fig:16-pairwise}
2607 Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf
2608 $\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein
2609 8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für
2610 größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise
2611 kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16}
2612 konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
2613 untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
2616 \section{Fazit und Ausblick}
2618 Mit dem Entfernen von Leitungen aus bekannten Sortiernetzwerken lassen sich
2619 interessante Ergebnisse erzielen. Dies zeigte \textit{Moritz Mühlenthaler}
2620 bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und
2621 Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere
2622 interessante Beobachtungen machen lassen.
2624 Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution},
2625 \textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der
2626 Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres
2627 Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in
2628 Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt.
2630 Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den
2631 vorgestellten Algorithmen übertroffen werden. Der Algorithmus
2632 \textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und
2633 \textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und
2634 für ein 32-Sortiernetzwerk sogar noch übertreffen. Der
2635 \textsc{SN-Evolution}-Algorithmus fand 16-Sortiernetzwerke, die gegenüber dem
2636 Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen
2637 weiteren Komparator einsparen.
2639 Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen
2640 zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer
2641 Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das
2642 \emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden
2643 regelmäßige Schnittmuster angegeben. Diese ergeben Sortiernetzwerke, die so
2644 schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
2647 Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen
2648 Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich
2649 weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das
2650 bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
2651 Schnittmustern erreicht werden können.
2653 Die Möglichkeiten der Optimierung von Sortiernetzwerken mit
2654 \emph{Evolutionären Algorithmen} sind durch die in dieser Arbeit vorgestellten
2655 Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze
2656 umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknüpft
2659 \subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}
2661 Die aktuelle Implementierung von \textsc{SN-Evolution}
2662 (Abschnitte~\ref{sect:sn-evolution}
2663 beziehungsweise~\ref{sect:implementierung}) kann sowohl den \emph{bitonen
2664 Mischer} als auch den \emph{Odd-Even}-Mischer verwenden, um zwei Individuen zu
2665 rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen
2666 Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich
2667 selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von
2668 $\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
2669 die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
2670 Ausgabe sorgen. Anstelle von $\ps{\frac{n}{2}}$ können beliebige
2671 Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwendet werden.
2673 Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
2674 rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
2675 \emph{unterschiedliche} Schnittmuster gibt
2676 (Abschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
2677 Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider
2678 wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine
2679 $n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren
2680 $n$-Sortiernetzwerken als \ps{n} führen.
2682 \subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}}
2684 Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
2685 in~\cite{H1990} beschreibt, könnte man versuchen, die Algorithmen
2686 \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} zu kombinieren. Nach dem
2687 Zusammenfügen von zwei $n$-Sortiernetzwerken könnte der Algorithmus
2688 \textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
2689 \emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
2690 Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
2691 verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut}
2692 die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern.
2694 Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} --
2695 eine zweite Population von Schnittmustern evolvieren, die für die
2696 Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut
2697 funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge
2698 Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten
2699 Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster
2700 eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses}
2701 Schnittmuster zur nächsten Generation beiträgt. Im Gegensatz zum Ansatz der
2702 parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die
2703 das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern
2707 \section{Implementierung}
2708 \label{sect:implementierung}
2710 Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens
2711 entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen
2712 Kommandozeilen-Programmen durchgeführt. Die Bibliothek wurde unter der
2713 \textit{GNU Lesser General Public License} (LGPL) in der Version~2.1
2714 veröffentlicht; die Kommandozeilen-Programme, die in vielen Fällen lediglich
2715 Funktionalität der Bibliothek auf der Kommandozeile zur Verfügung stellen,
2716 stehen unter der \textit{GNU General Public License}, Version~2. Diese
2717 Lizenzen räumen einem Benutzer weitreichende Rechte ein, unter anderem das
2718 Programm beliebig zu verwenden, zu studieren, zu verändern sowie veränderte
2719 und unveränderte Kopien zu veröffentlichen.
2721 Die Programmierschnittstelle (API) der Bibliothek orientiert sich an
2722 Paradigmen der \textit{objektorientierten Programmierung}. Beispielsweise kann
2723 mit der Funktion \texttt{sn\_network\_ create()} ein neues Zustands-Objekt
2724 erzeugt werden, für das mehrere Manipulations-Methoden, zum Beispiel
2725 \texttt{sn\_network\_comparator\_add()}, zur Verfügung stehen. Auf diese Art
2726 und Weise kann die Bibliothek leicht erweitert werden, ohne dass bestehende
2727 Programme angepasst werden müssen.
2729 Die meisten Kommandozeilen-Programmen lesen ein Komparatornetzwerk von der
2730 Standard-Eingabe und schreiben ihr Ergebnis auf die Standard-Ausgabe. Um
2731 Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen
2732 Mergesort}-Netzwerks \bs{42} zu erzeugen, kann folgendes Kommando verwendet
2735 $ sn-bitonicsort 42 | sn-normalize >sn-42
2737 Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
2738 es einfach zu ermöglichen, Programme zu verketten, ist eines der
2739 Grundprinzipien des UNIX-Be\-triebs\-sys\-tems. Es hat sich in den letzten
2740 Jahrzehnten und beim Verfassen dieser Arbeit als sehr flexibel und mächtig
2743 Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden,
2744 sind unter anderem das Erzeugen des \emph{Odd-Even-Mergesort}-, \emph{bitonen
2745 Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von
2746 Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und
2747 Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das
2748 Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise
2749 wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex}
2752 \textit{libsortnetwork} kann unter der Web-Adresse
2753 \url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden.
2756 \bibliography{references}
2757 \bibliographystyle{plain}
2763 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 spelllang=de :