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 Stunden 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 drei Stunden in Anspruch nimmt, sind für eine Million
287 Iterationen etwa 340~Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
288 auf 1000~Computern mit je 4~Prozessoren verteilt wird, wird etwa ein Monat für
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. Die Rolle, die
353 \textit{Exploitation} und \textit{Exploration} bei evolutionären
354 Optimierungsalgorithmen spielen, wird von \textit{Eiben} und
355 \textit{Schippers} in~\cite{ES1998} untersucht.
357 Die Parameter evolutionärer Algorithmen so einzustellen, dass sich ein guter
358 Mittelweg zwischen den beiden Extremen einstellt, ist eine Aufgabe, die sich
359 nur experimentell lösen lässt. Die genauen Parameter hängen nicht nur vom
360 eigentlichen Algorithmus, sondern auch vom konkreten Problem ab, so dass sich
361 beispielsweise bei der Optimierung von Sortiernetzwerken die Parameter
362 zwischen verschiedenen Leitungszahlen stark unterscheiden. Einen Überblick
363 geben \textit{Kalyanmoy Deb} und \textit{Samir Agrawal} in~\cite{DA1998}.
365 Die Erforschung (\textit{Exploration}) kann von einem weiteren Mechanismus
366 unterstützt werden, der ebenfalls der Evolutionslehre entliehen ist, der
367 \emph{Mutation}. Dabei werden Lösungen zufällig verändert, so dass auch andere
368 Lösungen „in der Nähe“ von direkten Nachfolgern erreicht werden können. Das
369 hilft insbesondere bei der intensiven Suche in der Nähe eines lokalen Optimums
370 aber auch beim „Ausbrechen“ aus lokalen Optima und finden noch besserer
373 Bei \emph{Sortiernetzwerken} ist eine \emph{Mutation} leider immer damit
374 verbunden, dass anschließend die Sortiereigenschaft des resultierenden
375 \emph{Komparatornetzwerks} wieder überprüft werden muss, da selbst das
376 Hinzufügen eines zufälligen Komparators diese Eigenschaft zer\-stö\-ren kann.
377 Beim Suchen möglichst effizienter Netzwerke ist das zufällige Entfernen von
378 Komparatoren interessanter, was die Sortiereigenschaft fast immer aufhebt.
380 Die im Folgenden beschriebenen Algorithmen mutieren (verändern) daher nicht
381 die \emph{Sortiernetzwerke} selbst, sondern verzichten entweder ganz auf
382 Mutation oder mutieren lediglich Transformationen von Sortiernetzwerken, die
383 die Sortiereigenschaft erhalten. Transformationen von Sortiernetzwerken werden
384 in Abschnitt~\ref{sect:tranformation} beschrieben, ein Algorithmus, der
385 Mutation einsetzt, wird in Abschnitt~\ref{sect:sn-evolution-cut} vorgestellt.
389 \input{images/16-hillis.tex}
391 \caption{Das 16-Sortiernetzwerk, das \textit{Hillis} in~\cite{H1990} angibt.
392 Es besteht aus 61~Komparatoren in 11~Schichten.}
393 \label{fig:16-hillis}
395 Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um
396 Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete
397 \emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“
398 zu optimieren~\cite{H1990}. Diese \emph{Parasiten} genannten Eingaben wurden
399 daran gemessen, bei wie vielen Komparatornetzwerken sie beweisen konnten, dass
400 sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen
401 (Komparatornetzwerken) nicht alle 0-1-Folgen, sondern nur erfolgreiche
402 Parasiten (schwierige Eingaben) überprüft werden. Auf diese Art und Weise
403 gelang es \textit{Hillis} ein 16-Sortiernetzwerk mit 61~Komparatoren
404 anzugeben, das in Abbildung~\ref{fig:16-hillis} zu sehen ist.
406 \textit{Michael~L. Harrison} und \textit{James~A. Foster} nutzten ebenfalls
407 \emph{Co-Evolution} in~\cite{HF2004}, um die Stabilität von Sortiernetzwerken
408 zu erhöhen. Die zweite Population bestand aus \emph{Fehlern} -- der
409 Information, welche Komparatoren defekt, beziehungsweise inaktiv sind. So
410 generierte Sortiernetzwerke können auch dann noch für viele Eingaben eine
411 korrekt sortierte Ausgabe erzeugen, wenn ein oder mehrere Komparatoren
412 (zufällig) entfernt werden.
416 \subfigure{\input{images/13-juille-0.tex}}
417 \subfigure{\input{images/13-juille-1.tex}}
418 \caption{13-Sortiernetzwerke, die von \textit{Hugues Juillé} mithilfe des
419 END-Algorithmus gefunden wurden. Sie bestehen jeweils aus 45~Komparatoren in
421 \label{fig:13-juille}
423 \textit{Hugues Juillé} entwickelte ein Verfahren, das er \emph{Evolving
424 Non-Determinism} (END) nannte~\cite{J1995}. Dabei handelt es sich nicht um
425 einen der \emph{Evolutionären Algorithmen}, wie sie hier vorgestellt wurden,
426 sondern um eine verteilte, probabilistische Breitensuche, die an die
427 \emph{Strahlsuche} (englisch: \textit{beam search}), ein Verfahren der
428 Künstlichen Intelligenz, angelehnt ist. Die aufwendigste Operation bei diesem
429 Ansatz ist die Bewertungsfunktion, die abschätzt, wie viele Komparatoren zu
430 einem Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu
431 erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke
432 anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin
433 bekannten (Abbildung~\ref{fig:13-juille}).
436 \section[Konstruktionsverfahren]{Konstruktionsverfahren für Sortiernetzwerke}
437 \label{sect:konstruktive_netzwerke}
439 Die bekannten Konstruktionsverfahren für Sortiernetzwerke, insbesondere ein
440 häufig verwendeter Baustein, sogenannte \emph{Mischer}\footnote{Eine
441 Fehlübersetzung aus dem Englischen, von \textit{to~merge} (Deutsch:
442 zusammenfügen). Da der Begriff des "`mischens"' beziehungsweise der
443 "`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
444 in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
445 beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
446 Eingabe. Im Folgenden werden daher drei Konstruktionsverfahren vorgestellt.
448 \subsection{Das Odd-Even-Transpositionsort-Netzwerk}
449 \label{sect:odd_even_transpositionsort}
451 Das Sortiernetzwerk {\em Odd-Even-Transpositionsort} (OET) ist eines der
452 einfachsten Sortiernetzwerke. Es besteht aus $n$~{\em Schichten}, die jede
453 "`Leitung"' abwechselnd mit den benachbarten Leitungen verbindet.
454 Abbildung~\ref{fig:odd-even-transposition-08} zeigt das OET-Netzwerk für
459 \input{images/oe-transposition-8.tex}
461 \caption{Das \emph{Odd-Even-Transpositionsort}-Netzwerk mit 8~Eingängen.}
462 \label{fig:odd-even-transposition-08}
465 Dass das \emph{Odd-Even-Transpositionsort}-Netzwerk tatsächlich jede beliebige
466 Eingabe sortiert, ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass
467 sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene
468 Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt.
470 Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen,
471 indem man $\operatorname{OET}(n)$ auf $\operatorname{OET}(n-1)$ durch
472 Herausschneiden einer Leitung reduziert. In
473 Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail
474 beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das
475 Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. Die Rekursion endet
476 beim \emph{Odd-Even-Transpositionsort}-Netzwerk mit drei Eingängen, bei dem
477 das Minimum auf der untersten, das Maximum auf der obersten und der mittlere
478 Wert auf der mittleren Leitung landet. Folglich ist die Ausgabe bei
479 $\operatorname{OET}(3)$ sortiert.
481 Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
482 Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
483 sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
484 (n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
485 Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
486 ($\Theta(n \log (n)^2)$), die in weniger Schichten,
487 ($\Theta(\log (n)^2)$), angeordnet sind.
489 Das Interessante am OET-Netzwerk ist seine einfache Konstruktion. Einige der
490 folgenden Algorithmen benötigen ein möglichst einfaches Sortiernetzwerk als
491 Starteingabe, auf dessen Basis sie versuchen optimierte Sortiernetzwerke zu
492 finden. Häufig dient $\operatorname{OET}(n)$ als Eingabe für diese
495 Außerdem bedienen sich die Algorithmen der Technik des Herausschneidens einer,
496 beziehungsweise mehrerer Leitungen, um die Anzahl der Leitungen eines
497 Sortiernetzwerks zu reduzieren. Die Technik wird in Detail im
498 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben.
500 \subsection{Das bitone Mergesort-Netzwerk}
502 Das \emph{bitone Mergesort}-Netzwerk ($\operatorname{BS}(n)$) ist ein
503 Sortiernetzwerk, das 1968 von \emph{Kenneth~E. Batcher} in~\cite{B1968}
504 veröffentlicht wurde. Es ist deutlich effizienter als das
505 Odd-Even-Transposi\-tionsort-Netzwerk -- sowohl in Bezug auf die Anzahl der
506 Komparatoren als auch der benötigten Zeit, also der Anzahl der Schichten.
508 Das Sortiernetzwerk basiert auf einem Komparatornetzwerk, welches zwei
509 sortierte Listen zusammenfügen (Englisch: \textit{to~merge}) kann. Dieser
510 \emph{„bitone Mischer“} (Englisch: \textit{bitonic merger}) genannte Baustein
511 verleiht dem Sortiernetzwerk seinen Namen.
513 Da das Sortiernetzwerk rekursiv definiert ist, betrachten wir hier nur die
514 Instanzen des Netzwerks, deren Leitungszahl $n = 2^d$ eine Zweierpotenz ist.
515 Es ist jedoch möglich, das Sortiernetzwerk für beliebige~$n$ zu erzeugen.
517 \subsubsection{Der bitone Mischer}\label{sect:der_bitone_mischer}
519 Das \emph{bitone Mergesort}-Netzwerk basiert auf dem sogenannten \emph{bitonen
520 Mischer} $\operatorname{BM}(n)$, einem Kom\-parator-Netzwerk, das eine
521 beliebige \emph{bitone Folge} in eine sortierte Liste umordnen kann. Eine
522 \emph{bitone Folge} ist eine monoton steigende Folge, gefolgt von einer
523 monoton absteigenden Folge, oder ein zyklischer Shift davon.
524 Abbildung~\ref{fig:beispiel-biton} zeigt die vier prinzipiellen Möglichkeiten,
525 die durch zyklische Shifts entstehen können. Die wichtigsten Varianten für das
526 \emph{bitone Mergesort}-Netzwerk zeigen die
527 Abbildungen~\ref{fig:beispiel-biton-0} und~\ref{fig:beispiel-biton-1}. Sie
528 erhält man, wenn man eine aufsteigend und eine absteigend sortierte Liste
529 aneinanderhängt. Bei den anderen beiden Formen ist wichtig zu beachten, dass
530 das letzte Element nicht größer (Abbildung~\ref{fig:beispiel-biton-2}) beziehungsweise
531 kleiner (Abbildung~\ref{fig:beispiel-biton-3}) als das erste Element der Folge
536 \subfigure[aufsteigend, absteigend]{\input{images/beispiel-biton-0.tex}\label{fig:beispiel-biton-0}}
537 \subfigure[absteigend, aufsteigend]{\input{images/beispiel-biton-1.tex}\label{fig:beispiel-biton-1}}
538 \subfigure[aufsteigend, absteigend, aufsteigend]{\input{images/beispiel-biton-2.tex}\label{fig:beispiel-biton-2}}
539 \subfigure[absteigend, aufsteigend, absteigend]{\input{images/beispiel-biton-3.tex}\label{fig:beispiel-biton-3}}
540 \caption{Beispiele bitoner Folgen.}
541 \label{fig:beispiel-biton}
546 \subfigure[normal]{\input{images/bitonic-merge.tex}\label{fig:bitonic-merge-normal}}
548 \subfigure[trichter]{\input{images/bitonic-merge-trichter.tex}\label{fig:bitonic-merge-tricheter}}
549 \caption{Schematischer Aufbau des bitonen Mischers: Jedes Element der
550 aufsteigenden Folge $u_0, u_1, \ldots$ wird mit dem entsprechenden Element
551 der absteigend sortierten Folge $v_0, v_1, \ldots$ verglichen. Die beiden
552 resultierenden Teilfolgen sind wiederum biton.}
553 \label{fig:bitonic-merge-schema}
556 Der Mischer funktioniert folgendermaßen: Gegeben sind zwei Folgen mit je
557 ${m = \frac{n}{2}}$ Elementen, $U = \left(u_0, u_1, \ldots, u_{m-1}\right)$ und
558 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die Folge $U$ sei aufsteigend
559 sortiert, die Folge $V$ sei absteigend sortiert:
561 u_0 \leqq u_1 \leqq &\ldots& \leqq u_{m-1} \\
562 v_0 \geqq v_1 \geqq &\ldots& \geqq v_{m-1}
564 Im ersten Schritt werden nun jeweils die Elemente an den gleichen relativen
565 Positionen verglichen und ggf. vertauscht:
567 u_i \longleftrightarrow v_i, \quad 0 \leqq i < m
569 Sei $j \in \{0 \ldots m\}$ der Index der ersten Elemente $u_j$ und $v_j$, die
570 durch den gemeinsamen Komparator vertauscht werden. Unter der Annahme, dass
571 Elemente nur vertauscht werden wenn, sie ungleich sind, muss ${u_j > v_j}$
572 gelten. Mit $u_j \leqq u_{j+1}$ und $v_j \geqq v_{j+1}$ folgt daraus $u_{j+1}
573 > v_{j+1}$. Es werden also alle Elemente $u_k$ und $v_k$ mit $k \geqq j$
574 vertauscht. $j = m$ bezeichnet den Fall, in dem das größte Element der
575 "`linken"' Folge $u_{m-1}$ kleiner ist als das kleinste Element der
576 "`rechten"' Folge $v_{m-1}$. Daraus folgt, dass sich das Resultat in zwei
577 bitone Folgen aufteilen lässt: Eine aufsteigende~/ absteigende Folge und eine
578 absteigende~/ aufsteigende Folge. Abbildung~\ref{fig:bitonic-merge-normal}
579 zeigt die Situationen vor und nach diesem Schritt des Mischers schematisch.
581 Um die Folge vollständig zu sortieren, müssen anschließend die beiden
582 resultierenden bitonen Folgen sortiert werden. Die geschieht ebenfalls
583 mithilfe des bitonen Mischers, mit zwei Instanzen von
584 $\operatorname{BM}(\frac{n}{2})$. Diese rekursive Definition endet mit dem
585 bitonen Mischer mit zwei Leitungen, $\operatorname{BM}(2)$, der als
586 Komparator-Netzwerk mit einem Komparator zwischen den beiden Leitungen
589 Der bitone Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist
590 lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt
591 notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine
592 „echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das
593 Schema des bitonen Mischers für zwei aufsteigend sortierte Folgen. Durch das
594 Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig:
595 Statt an eine Treppe erinnert das Muster nun an einen Trichter.
597 Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
598 die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
599 $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
600 $\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren
601 besteht, die in $\log(n)$~Schichten angeordnet werden können.
603 \subsubsection{Das bitone Mergesort-Netzwerk}
605 Ebenso wie der bitone Mischer $\operatorname{BM}(n)$ ist auch das \emph{bitone
606 Mergesort-Netzwerk} $\operatorname{BS}(n)$ rekursiv definiert. Es setzt sich
607 zusammen aus zwei Instanzen des bitonen Mergesort-Netzwerks halber Größe
608 $\bs{\frac{n}{2}}$ für je die Hälfte der Eingänge, sowie dem bitonen Mischer
609 für $n$~Leitungen $\operatorname{BM}(n)$. Das Rekursionsende ist das bitone
610 Mergesort-Netzwerk mit nur einer Leitung $\operatorname{BS}(1)$, welches als
611 leeres Komparatornetzwerk definiert ist. Entsprechend sind die
612 Komparatornetzwerke $\operatorname{BM}(2)$ und $\operatorname{BS}(2)$
615 Bei der Konstruktion kommt die trichterförmige Anordnung der Komparatoren
616 (Abbildung~\ref{fig:bitonic-merge-tricheter}) gelegen, weil so die beiden
617 rekursiven Sortiernetzwerke in die gleiche Richtung sortieren können und so
618 alle Komparatoren in die gleiche Richtung zeigen.
622 \input{images/batcher-8.tex}
624 \caption{\bs{8}, Batchers \emph{bitones Mergesort}-Netzwerk für 8~Eingänge.
625 Markiert sind die beiden Instanzen von \bs{4} (rot), die beiden bitonen
626 Mischer~\bm{4} (blau) und die Komparatoren, die im letzten rekursiven
627 Schritt hinzugefügt wurden (grün).}
628 \label{fig:bitonic-08}
631 Das Sortiernetzwerk~$\operatorname{BS}(8)$ ist in
632 Abbildung~\ref{fig:bitonic-08} zu sehen. Eingezeichnet sind ebenfalls die
633 beiden Instanzen des Netzwerks~$\operatorname{BS}(4)$ (rot) sowie der bitone
634 Mischer~$\operatorname{BM}(8)$ (blau). Die trichterförmige Komparator-Kaskade,
635 die die bitone Eingabefolge in zwei bitone Ausgabefolgen transformiert, ist
638 Das \emph{bitone Mergesort}-Netzwerk mit einer Leitungszahl $n = 2^d$, die
639 eine Zweierpotenz ist, besteht aus $\frac{1}{4} n \log(n) \log(n+1) =
640 \Theta\left(n (log (n))^2\right)$ Komparatoren, die in $\frac{1}{2}
641 \log(n) \log(n+1) = \Theta(\log(n)^2)$ Schichten angeordnet sind.
643 \subsection{Das Odd-Even-Mergesort-Netzwerk}
645 Obwohl der Name ähnlich klingt, haben das \emph{Odd-Even-Mergesort}-Netzwerk
646 (OES) und das \emph{Odd-Even-Transpositionsort}-Netzwerk (siehe
647 Abschnitt~\ref{sect:odd_even_transpositionsort}) wenig gemein. Vielmehr ist
648 OES dem \emph{bitonen Mergesort}-Netzwerk, das im vorherigen Abschnitt
649 vorgestellt wurde, ähnlich: Auch dieses Sortiernetzwerk ist von
650 \textit{Kenneth~E. Batcher} gefunden worden und ist ebenfalls in~\cite{B1968}
651 beschrieben und initial analysiert worden. Eine weitere Gemeinsamkeit besteht
652 darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist.
654 \subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer}
656 Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein
657 Komparatornetzwerk, das zwei sortierte Folgen mit $n$ beziehungsweise $m$
658 Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen
659 zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der
660 \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer}
661 vorgestellt wurde. Im allgemeinen Fall, wenn die Anzahl der Leitungen keine
662 Zweierpotenz ist, kann das \emph{bitonic-Merge}-Netzwerk schneller sein
663 als das \emph{Odd-Even-Merge}-Netzwerk.~\cite{KNUTH}
665 Der \emph{Odd-Even}-Mischer selbst ist ebenfalls rekursiv aufgebaut: Die
666 Eingabe für den Mischer mit $N = n + m$ Leitungen besteht aus den beiden
667 sortierten Folgen $U = \left(u_0, u_1, \ldots, u_{n-1}\right)$ und
668 $V = \left(v_0, v_1, \ldots, v_{m-1}\right)$. Die gesamte Eingabe sei
669 $W = \left(w_0, w_1, \ldots, w_{N-1}\right)$ mit:
671 w_i = \left\{ \begin{array}{ll}
680 \input{images/oe-merge.tex}
682 \caption{Schematischer Aufbau des \emph{Odd-Even-Merge}-Netzwerks. Die
683 beiden Dreiecke symbolisieren die beiden sortierten Folgen $U$ und $V$,
684 die Blöcke darunter die rekursiven Mischer mit etwa der Hälfte der
685 Leitungen. Im Vergleich zum \emph{bitonen Mischer} für 8~Leitungen kommt
686 dieses Schema mit einem Komparator weniger aus. Der Effekt wird durch den
687 rekursiven Aufbau verstärkt.}
691 Diese werden in insgesamt vier sortierte Folgen aufgeteilt, je eine Liste der
692 geraden Indizes und je eine Liste der ungeraden Indizes.
694 U_{\textrm{gerade}} &=& \left(u_0, u_2, u_4, \ldots\right) \\
695 U_{\textrm{ungerade}} &=& \left(u_1, u_3, u_5, \ldots\right) \\
696 V_{\textrm{gerade}} &=& \left(v_0, v_2, u_4, \ldots\right) \\
697 V_{\textrm{ungerade}} &=& \left(v_1, v_3, u_5, \ldots\right)
700 Die geraden Folgen $U_{\textrm{gerade}}$ und $V_{\textrm{gerade}}$,
701 beziehungsweise die ungeraden Folgen $U_{\textrm{ungerade}}$ und
702 $V_{\textrm{ungerade}}$ werden rekursiv von kleineren \emph{Odd-Even}-Mischern
703 zusammengefügt, so dass sich am Ausgang der Mischer die Folgen
705 W_{\textrm{gerade}} &=& \left(w_0, w_2, w_4, \ldots\right) \\
706 W_{\textrm{ungerade}} &=& \left(w_1, w_3, w_5, \ldots\right)
710 Anschließend werden die Komparatoren zwischen benachbarten Leitungen
713 w_{2i-1} \longleftrightarrow w_{2i}, \quad 1 \leqq i < \frac{N}{2}
715 die die Folge~$W$ sortieren. Den schematischen Aufbau des
716 \emph{Odd-Even}-Mischers zeigt Abbildung~\ref{fig:oe-merge}.
718 Leider bricht die Rekursion nicht so schön ab, wie das beim {\em bitonen
719 Mischer} der Fall gewesen ist. Insbesondere für ${n = m = 1}$ würde --
720 entsprechend der Konstruktionsvorschrift -- ein leeres Netzwerk entstehen, was
721 offensichtlich nicht korrekt wäre. Die Abbruchbedingungen für den rekursiven
724 \item Falls ${n = 0}$ oder ${m = 0}$: Das Netzwerk ist leer.
725 \item Falls ${n = 1}$ und ${m = 1}$: Das Netzwerk besteht aus einem
726 einzelnen Komparator.
729 Mit dem {\em 0-1-Prinzip} lässt sich zeigen, dass die resultierende Folge
730 sortiert ist. Da $U$ und $V$ sortiert sind, ist die Anzahl der Nullen in den
731 geraden Teilfolgen $U_{\textrm{gerade}}$, beziehungsweise
732 $V_{\textrm{gerade}}$ größer oder gleich der Anzahl der Nullen in den
733 ungeraden Teilfolgen $U_{\textrm{ungerade}}$ beziehungsweise
734 $V_{\textrm{ungerade}}$ --~die Einsen verhalten sich entsprechend umgekehrt.
735 Das trifft demnach auch auf die Folgen $W_{\textrm{gerade}}$ und
736 $W_{\textrm{ungerade}}$ entsprechend zu:
738 \left|W_{\textrm{gerade}}\right|_0
739 &=& \left|U_{\textrm{gerade}}\right|_0
740 + \left|V_{\textrm{gerade}}\right|_0
741 = \left\lceil \frac{1}{2} \left|U\right|_0 \right\rceil
742 + \left\lceil \frac{1}{2} \left|V\right|_0 \right\rceil \\
743 \left|W_{\textrm{ungerade}}\right|_0
744 &=& \left|U_{\textrm{ungerade}}\right|_0
745 + \left|V_{\textrm{ungerade}}\right|_0
746 = \left\lfloor \frac{1}{2} \left|U\right|_0 \right\rfloor
747 + \left\lfloor \frac{1}{2} \left|V\right|_0 \right\rfloor
749 Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält
750 als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"'
751 Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall,
752 wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält als
753 $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die
754 Ausgabe zu sortieren. Diese wird von den Komparatoren ausgeführt, die
755 benachbarte Leitungen miteinander vergleichen. Die jeweiligen Situationen sind
756 in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
760 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 0$]{\input{images/oe-post-recursive-diff0.tex}}
762 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 1$]{\input{images/oe-post-recursive-diff1.tex}}
764 \subfigure[$\left|W_{\textrm{gerade}}\right|_0 - \left|W_{\textrm{ungerade}}\right|_0 = 2$]{\input{images/oe-post-recursive-diff2.tex}}
765 \caption{Die drei Situationen, die nach dem Verzahnen der Ausgaben der
766 kleineren \emph{Odd-Even}-Mischer entstehen können. Ist die Differenz der
767 Anzahl der Nullen gleich $0$ oder $1$, ist die Folge bereits sortiert. Im
768 letzten Fall stellt einer der Komparatoren sicher, dass das Ergebnis
770 \label{fig:oe-post-recursive}
773 Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
774 bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$
775 Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
776 Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
777 Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
779 Die Anzahl der Komparatoren $K(n,m)$, die $\operatorname{OEM}(n,m)$ im
780 allgemeinen Fall verwendet, hängt gemäß der rekursiven Definition von der
781 Länge der Eingabefolgen, $n$ und $m$ ab:
783 K(n,m) = \left\{ \begin{array}{ll}
784 nm, & \mathrm{falls} \quad nm \leqq 1 \\
785 K\left(\left\lceil \frac{n}{2} \right\rceil, \left\lceil \frac{m}{2} \right\rceil\right)
786 + K\left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor\right)
787 + \left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor & \mathrm{falls} \quad nm > 1
790 Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
791 anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
792 dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist.
794 Für den wichtigen Spezialfall, dass $n = m = 2^{d-1}$ beträgt, lässt sich die
795 Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
796 erste Rekursionsschritt der OEM-Konstruktion fügt
797 $\left\lfloor \frac{1}{2} (m + n - 1) \right\rfloor = \frac{N}{2} - 1$
798 Komparatoren ein -- einen Komparator weniger als der \emph{bitone Mischer} in
799 diesem Schritt. Das selbe gilt für die rekursiv verwendeten kleineren Mischer
800 $\operatorname{OEM}(\frac{n}{2}, \frac{n}{2})$ und so weiter bis
801 einschließlich $\operatorname{OEM}(2, 2)$, von denen es $2, 4, \dots,
802 \frac{N}{4} = 2^{\log(N)-2}$ Instanzen gibt. Insgesamt werden
804 \sum_{i=0}^{\log(N)-2} 2^i = 2^{\log(N) - 1} - 1 = \frac{N}{2} - 1 = n - 1
806 Komparatoren eingespart. Damit ergibt sich
808 K\left(n = 2^{d-1}, n = 2^{d-1}\right) = \frac{1}{2} N \log(N) - \frac{N}{2} + 1
810 für die Anzahl der Komparatoren, die von $\operatorname{OEM}(N = 2^d)$
813 \subsubsection{Das Odd-Even-Mergesort-Netzwerk}
815 Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ besteht, wie
816 das \emph{bitone Mergesort}-Netzwerk, rekursiv aus kleineren Varianten von
817 sich selbst und einem abschließenden \emph{Odd-Even}-Mischer. Die
818 effizientesten Sortiernetzwerke in Bezug auf Komparator- und Schichtzahl
819 entstehen, wenn die Anzahl der Leitungen jeweils halbiert wird. Somit besteht
820 \oes{n} aus $\oes{\left\lceil\frac{n}{2}\right\rceil}$,
821 $\oes{\left\lfloor\frac{n}{2}\right\rfloor}$ und
822 $\oem{\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor}$.
823 Die Rekursion endet mit $\operatorname{OES}(1)$ und $\operatorname{OES}(0)$,
824 die als leere Komparatornetzwerke definiert sind.
828 \input{images/oe-mergesort-8.tex}
830 \caption{Das {\em Odd-Even-Mergesort-Netzwerk} für 8~Eingänge. Markiert
831 sind die Instanzen von $\operatorname{OES}(4)$ (rot), die beiden
832 \emph{Odd-Even}-Mischer $\operatorname{OEM}(4)$ für gerade und ungerade
833 Leitungen (blau) und die im ersten Rekursionsschritt hinzugefügten
834 Komparatoren zwischen benachbarten Leitungen (grün).}
835 \label{fig:odd-even-mergesort-08}
838 In Abbildung~\ref{fig:odd-even-mergesort-08} ist das \oes{8}-Sortiernetzwerk
839 zu sehen. Rot markiert sind die beiden rekursiven Instanzen
840 $\operatorname{OES}(4)$. Die anderen Blöcke stellen den
841 \emph{Odd-Even}-Mischer für 8~Leitungen dar: die beiden blauen Blöcke sind
842 die rekursiven Instanzen von $\operatorname{OEM}(4)$, der grüne Block markiert
843 die Komparatoren, die im ersten Rekursionsschritt hinzugefügt werden.
845 Im Allgemeinen ist die Anzahl der Komparatoren, die vom
846 \emph{Odd-Even-Mergesort-Netz\-werk} verwendet wird, $k(n)$, direkt aus der
847 Definition, beziehungsweise der Konstruktionsanleitung abzulesen:
849 k(n) = k\left(\left\lceil\frac{n}{2}\right\rceil\right)
850 + k\left(\left\lfloor\frac{n}{2}\right\rfloor\right)
851 + K\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right)
853 Da es schwierig ist für $K(n,m)$ eine geschlossene Form anzugeben, ist eine
854 geschlossene Darstellung von $k(n)$ ebenfalls nicht ohne weiteres möglich. Es
855 ist allerdings bekannt, dass $k(n)$ in $\Theta\left(n \left(\log
856 (n)\right)^2\right)$ enthalten ist.
858 Für den wichtigen Spezialfall, dass $n = 2^d$ eine Zweierpotenz ist, kann die
859 Anzahl der Komparatoren wieder explizit angegeben werden. \textit{Kenneth
860 Batcher} zeigt in~\cite{B1968}, dass in diesem Fall
862 k(n = 2^d) = \frac{1}{4} n \left(\log (n)\right)^2 - \frac{1}{4}n\log(n) + n - 1
866 %\subsection{Das Pairwise-Sorting-Netzwerk}
868 %Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
869 %für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
870 %Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
871 %Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
872 %\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
873 %das \emph{Odd-Even-Mergesort}-Netzwerk.
876 \section{Transformation von Sortiernetzwerken}
877 \label{sect:tranformation}
879 \subsection{Komprimieren}
881 Komparatoren, die unterschiedliche Leitungen miteinander vergleichen, können
882 gleichzeitig ausgewertet werden, wie bereits in
883 Abschnitt~\ref{sect:einleitung_sortiernetzwerke} beschrieben. Durch manche
884 Transformationen, insbesondere das Entfernen einer Leitung wie in
885 Abschnitt~\ref{sect:leitungen_entfernen} beschrieben, kann es vorkommen, dass
886 die Komparatoren eines Sortiernetzwerks nicht mehr in der kleinstmöglichen
887 Anzahl von \emph{Schichten} angeordnet sind. Unter \emph{Komprimierung} wird
888 eine (Neu-)Gruppierung der Komparatoren verstanden, die jeden Komparator so
889 früh wie möglich ausführt. So entsteht die kleinstmögliche Anzahl von
890 \emph{Schichten}, in die sich ein Sortiernetzwerk unterteilen lässt.
892 Diese Anzahl ist insbesondere beim automatisierten Bewerten von
893 Komparatornetzwerken interessant, wie in Abschnitt~\ref{sect:sn-evolution:bewertung}
894 beschrieben. Die Anzahl der Schichten kann künstlich vergrößert werden, indem
895 Komparatoren später angewendet werden. Deshalb sollte vor einer Bewertung, die
896 die Anzahl der Schichten als Bewertungskriterium verwendet, immer eine
897 Komprimierung durchgeführt werden.
899 \subsection{Normalisieren}
900 \label{sect:normalisieren}
904 \subfigure[$S(8)$ (nach Konstruktion)]{\input{images/batcher-8-nonstd.tex}\label{fig:bitonic-nonstd}}
905 \subfigure[$S(8)$ (normalisiert)]{\input{images/batcher-8-std.tex}\label{fig:bitonic-std}}
906 \caption{Jedes Sortiernetzwerk kann in ein Standard-Sortiernetzwerk
907 transformiert werden. Gezeigt ist das bitone Sortiernetzwerk nach der
908 intuitiven Konstruktion und die normalisierte Variante.}
909 \label{fig:beispiel_normalisieren}
912 Ein \emph{Standard-Sortiernetzwerk} oder \emph{normalisiertes Sortiernetzwerk}
913 ist ein Sortiernetzwerk, dessen Komparatoren alle in die selbe Richtung
914 zeigen.\footnote{Die Konvention in dieser Arbeit ist, dass in diesem Fall alle
915 Pfeile nach unten zeigen. Das Minimum wird auf der untersten, das Maximum auf
916 der obersten Leitung ausgegeben.} Jedes Sortiernetzwerk kann in eine
917 normaliesierte Variante transformiert werden. Dazu gibt beispielsweise
918 \emph{Donald~E. Knuth} in~\cite{KNUTH} einen Algorithmus an.
920 Abbildung~\ref{fig:beispiel_normalisieren} stellt das \emph{bitone
921 Mergesort}-Netzwerk in zwei Varianten dar. Abbildung~\ref{fig:bitonic-nonstd}
922 zeigt das Netzwerk nach der Konstruktionsvorschrift, siehe auch
923 Abbildung~\ref{fig:bitonic-merge-normal}: In den ersten drei Schichten werden
924 die untere und die obere Hälfte gegenläufig sortiert. Das heißt, dass nach
925 drei Schritten die eine Hälfte auf- und die andere Hälfte absteigend sortiert
926 ist. In den Schichten~4 bis~6 folgt der bitone Mischer entsprechend der
927 rekursiven Definition.
929 In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen
930 Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die selbe
931 Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen-
932 und das Trichtermuster zu sehen.
934 \subsection{Zwei Netzwerke kombinieren}
936 Um Sortiernetzwerke als \emph{Individuen} evolutionärer Algorithmen verwenden
937 zu können, muss es möglich sein, zwei Sortiernetzwerke zu einem neuen
938 Sortiernetzwerk zusammenzufassen.
940 Diese Technik wurde in den vorangegangen Abschnitten bereits verwendet,
941 beispielsweise um zwei \emph{bitone Mergesort}-Netzwerke mit jeweils der
942 halben Leitungszahl, $\operatorname{BS}\left(\frac{n}{2}\right)$, zu einem
943 einzigen Sortiernetzwerk $\operatorname{BS}(n)$ zu kombinieren. Auch das
944 \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(n)$ wurde auf diese Art
945 und Weise rekursiv aufgebaut.
947 Die vorgestellten \emph{Mischer} erwarten als Eingabe zwei bereits sortierte
948 Folgen. \emph{Wie} diese Folgen sortiert wurden ist unerheblich. Entsprechend
949 können wir beliebige Sortiernetzwerke einsetzen, um die beiden Eingabefolgen
950 zu sortieren und die Ausgaben mit einem der beschriebenen Mischer
953 Beispielsweise kann die Ausgabe von zwei \emph{bitonen Mergesort-Netzwerken}
954 $\operatorname{BS}(8)$ mit je 8~Leitungen mit dem
955 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM(8,8)}$ zu einer sortierten
956 Gesamtfolge zusammengefügt werden. Das resultierende Sortiernetzwerk besitzt
957 73~Komparatoren (zum Vergleich: $\operatorname{BS}(16)$ benötigt
958 80~Komparatoren, $\operatorname{OES}(16)$ nur 63).
960 Verbesserungen der Effizienz (die Anzahl der benötigten Komparatoren),
961 beziehungsweise der Geschwindigkeit (die Anzahl der Schichten) eines „kleinen“
962 Sortiernetzwerks, übertragen sich direkt auf das resultierende Gesamtnetzwerk.
963 Das \emph{Odd-Even-Mergesort}-Netzwerk $\operatorname{OES}(9)$ benötigt
964 beispielsweise 26~Komparatoren, die in 9~Schichten angeordnet sind. Es sind
965 allerdings Sortiernetzwerke mit 9~Eingängen bekannt, die lediglich
966 25~Komparatoren in 7~Schichten benötigen. Wenn zwei dieser Netzwerke mit dem
967 \emph{Odd-Even}-Mischer kombiniert werden, entsteht ein 18-Sortiernetzwerk,
968 das aus 80~Komparatoren in 11~Schichten besteht. Damit ist das resultierende
969 Netzwerk genauso schnell wie das Sortiernetzwerk mit 18~Eingängen, das
970 \textit{Sherenaz~W. Al-Haj Baddar} und \textit{Kenneth~E. Batcher} in ihrer
971 Arbeit „An 11-Step Sorting Network for 18~Elements“~\cite{BB2009} vorstellen,
972 benötigt aber 6~Komparatoren weniger. $\operatorname{OES}(18)$ benötigt
973 82~Komparatoren in 13~Schichten.
975 Das Zusammenfassen von zwei Sortiernetzwerken durch Hintereinanderausführung
976 ist nicht sinnvoll: Da die Ausgabe des ersten Sortiernetzwerks bereits
977 sortiert ist, ist das zweite Sortiernetzwerk überflüssig. Eine
978 Aneinanderreihung der Art „die ersten $x$~Schichten des einen, dann die
979 letzten $y$~Schichten des anderen Sortiernetzwerks“ zerstören im Allgemeinen
980 die Sortiereigenschaft. Die Sortiereigenschaft des resultierenden
981 Komparatornetzwerks müsste überprüft werden, was nach heutigem Wissensstand
982 nur mit exponentiellem Aufwand möglich ist.
984 \subsection{Leitungen entfernen}
985 \label{sect:leitungen_entfernen}
987 Im vorherigen Abschnitt wurde gezeigt, dass es mithilfe von \emph{Mischern}
988 möglich ist, aus zwei Sortiernetzwerken mit je $n$~Eingängen
989 ein neues Sortiernetzwerk mit $2n$~Eingängen zu erzeugen. Für einen
990 beabsichtigen \emph{evolutionären Algorithmus} ist es jedoch notwendig, dass
991 sich die Anzahl der Eingänge nicht verändert. Es soll wieder ein
992 Sortiernetzwerk mit $n$~Eingängen entstehen.
994 Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein
995 Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung
996 „eliminiert“. Dazu wird angenommen, dass das Minimum oder das Maximum an einem
997 bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das
998 Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an
999 einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten
1000 Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und
1001 welche dafür sorgen, dass der Wert die Leitung wechselt, da das Minimum jeden
1002 Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die
1003 Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch
1004 das \emph{Odd-Even-Transpositionsort}-Netzwerk.
1006 Im ersten Schritt wird eine Leitung ausgewählt und Maximum oder Minimum auf
1007 dieser Leitung angenommen. Dadurch ist der Weg durch das Sortiernetzwerk
1008 eindeutig festgelegt.
1012 \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad
1013 durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}}
1014 \subfigure[Komparatoren, die einen Wechsel der Leitungen bewirken, werden
1015 durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}}
1016 \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit
1017 7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}}
1018 \subfigure[Die Leitungen wurden wieder gerade eingezeichnet und die
1019 Komparatoren regelmäßig angeordnet. Blau eingezeichnet ist \oet{7}.]{\input{images/oe-transposition-cut3.tex}\label{fig:oe-transposition-cut3}}
1020 \caption{Eine Leitung wird aus dem
1021 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{8} entfernt: Auf der rot
1022 markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator
1023 nach unten weiter gegeben wird, ist der Pfad fest vorgegeben. Da die
1024 restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser
1025 Pfad heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.}
1026 \label{fig:oe-transposition-cut}
1029 Im nächsten Schritt werden alle beteiligten Komparatoren gelöscht,
1030 beziehungsweise ersetzt: Komparatoren, die {\em nicht} zu einem Wechsel der
1031 Leitung geführt haben, werden ersatzlos gelöscht. Diese Komparatoren sind in
1032 Abbildung~\ref{fig:oe-transposition-cut0} grün markiert. Die Komparatoren, die
1033 zum Wechsel der Leitung geführt haben, werden durch sich kreuzende Leitungen
1034 ersetzt. Das Resultat ist eine Leitung, auf der das Minimum beziehungsweise
1035 das Maximum angenommen wird, die an unterster oder oberster Stelle endet und
1036 die keine Komparatoren mehr berührt
1037 (Abbildung~\ref{fig:oe-transposition-cut1}).
1039 Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen
1040 Komparatornetzwerk immer noch sortiert werden: Es wurde lediglich die
1041 \emph{Position} des Minimums oder des Maximums in der Eingabe angenommen. Ein
1042 Sortiernetzwerk muss die Eingabe sortieren, unabhängig davon auf welcher
1043 Leitung das Minimum oder das Maximum liegt. Das Sortiernetzwerk unter diese
1044 Annahme auszuwerten -- über die verbleibenden Eingänge wurde keine Aussage
1045 getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste
1046 mit $(n-1)$~Elementen darstellen.
1048 Wird die Minimum- beziehungsweise Maximum-Leitung entfernt, wie in
1049 Abbildung~\ref{fig:oe-transposition-cut2} dargestellt, bleibt das
1050 Sortiernetzwerk für $(n-1)$~Leitungen übrig. Je nachdem, ob auf einer Leitung
1051 ein Minimum oder ein Maximum angenommen wird, wird das eliminieren einer
1052 Leitung auf diese Art und Weise als \emph{Minimum-Schnitt}, beziehungsweise
1053 \emph{Maximum-Schnitt} bezeichnet.
1055 Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das
1056 Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot
1057 markierten Komparatoren sind verschoben, so dass sich eine kompaktere
1058 Darstellung ergibt. Außerdem ist das
1059 \emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der
1060 zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und
1061 kann entfernt werden.
1063 Durch das Ersetzen von Komparatoren durch gekreuzte Leitungen werden häufig
1064 \emph{Nicht-Standard-Sortiernetzwerke} erzeugt. Im Anschluss an einen
1065 \emph{Schnitt} empfiehlt es sich deshalb, das Sortiernetzwerk zu
1066 \emph{normalisieren}, wie in Abschnitt~\ref{sect:normalisieren} beschrieben.
1068 \subsubsection{Anzahl möglicher und unterschiedlicher Schnittmuster}
1069 \label{sect:anzahl_schnittmuster}
1071 Der Eliminierungsschritt kann iterativ angewendet werden, um aus einem
1072 Sortiernetzwerk mit $n$~Ein\-gängen Sortiernetzwerke mit $n-1$, $n-2$,
1073 $n-3$,~\dots Eingängen zu erzeugen. Insbesondere können auf diese Art und
1074 Weise Sortiernetzwerke mit $2n$~Eingängen auf Sortiernetzwerke mit
1075 $n$~Eingängen reduziert werden. Als \emph{$k$-Schnittmuster} bezeichnet man
1076 die $k$~Minimum- und Maximum-Schnitte, die nacheinander angewendet ein
1077 $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetz\-werk reduzieren.
1079 Zwei Schnittmuster heißen \emph{äquivalent} bezüglich~$S$, wenn ihre Anwendung
1080 auf das Sortiernetzwerk~$S$ das selbe Ergebnis liefert. Ansonsten heißen die
1081 Schnittmuster \emph{unterschiedlich} bezüglich~$S$.
1083 Bei einem Sortiernetzwerk mit $n$~Eingängen gibt es $2n$~Möglichkeiten eine
1084 Leitung zu entfernen: Auf jeder der $n$~Leitungen kann sowohl das Minimum als
1085 auch das Maximum angenommen werden. Wendet man das Verfahren iterativ an, um
1086 ein $n$-Sortiernetzwerk auf ein ${(n-k)}$-Sortiernetzwerk zu reduzieren,
1087 ergeben sich insgesamt
1089 \prod_{i=n}^{1+n-k} 2i = 2^k \cdot \frac{n!}{(n-k)!}
1092 \emph{mögliche} Schnittmuster. Diese Schnittmuster sind nicht alle
1093 unterschiedlich. Wird beispielsweise das Minimum auf der untersten Leitung
1094 und das Maximum auf der obersten Leitung eines Standard-Sortiernetzwerks
1095 angenommen, führen beide möglichen Schnitt-Reihenfolgen zum selben Ergebnis.
1097 \textit{Moritz Mühlenthaler} zeigt in seiner Arbeit~\cite{M2009}, dass es
1098 möglich ist, mehrere Eingänge gleichzeitig mit Minimum beziehungsweise Maximum
1099 vorzubelegen, ohne die Menge der erreichbaren Sortiernetzwerke einzuschränken.
1100 Dadurch wird die Anzahl der möglichen Schnittmuster reduziert, die Menge der
1101 so erzeugbaren Sortiernetzwerke bleibt aber unverändert. Die Anzahl der
1102 möglichen Schnittmuster setzt sich zusammen aus der Anzahl von Möglichkeiten,
1103 $k$~Leitungen aus $n$~Leitungen auszuwählen, und die möglichen Minimum-~/
1104 Maximum-Muster. Damit ergibt sich folgende Formel für die Anzahl der möglichen
1106 \begin{equation}\label{eqn:anzahl_schnittmuster}
1107 2^k \cdot \left( \begin{array}{c} n \\ k \end{array} \right)
1108 = 2^{k} \cdot \frac{n!}{k! (n-k)!}
1109 = 2^{k} \cdot \frac{n!}{(n-k)!} \cdot \frac{1}{k!}
1110 \quad (1 \leqq k < n)
1113 Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden
1114 Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf
1115 ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schnittmuster mit
1116 16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$
1117 Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große
1118 Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich.
1120 Die Anzahl der \emph{unterschiedlichen} Schnittmuster ist allerdings kleiner
1121 als die Anzahl der \emph{möglichen} Schnittmuster. Für jeden Komparator auf
1122 der ersten Stufe gibt es neun verschiedene Eingangskonfigurationen: Für beide
1123 Eingänge gibt es drei mögliche Eingangswerte, Minimum, Maximum und
1124 unspezifiziert. Es gibt drei Konfigurationen, bei denen an beiden Eingängen
1125 der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die
1126 Werte unterscheiden.
1128 Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe
1129 Ausgangsmuster abgebildet, weil die Position des Minimums beziehungsweise des
1130 Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun
1131 unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster
1132 erzeugen. In der zweiten und allen folgenden Schichten kann man diesen
1133 Unterschied nicht mehr erkennen. In allen sechs Fällen, in denen sich die
1134 Eingänge unterscheiden, wird anschließend der Komparator entfernt, so dass
1135 sich die Resultate auch in der ersten Schicht nicht unterscheiden.
1139 \includegraphics[viewport=0 0 425 262,width=15cm]{images/count-cuts-16.pdf}
1141 \caption{Anzahl der \emph{unterschiedlichen} Sortiernetzwerke, die durch
1142 8-Schnittmuster aus $\operatorname{OES}(16)$, $\operatorname{BS}(16)$ und
1143 $\operatorname{PS}(16)$ hervorgegangen sind. Die Anzahl der
1144 unterschiedlichen Netzwerke nach $10^6$~Iterationen ist 3519 für das
1145 \emph{Odd-Even-Mergesort}-Netzwerk, 4973 für das \emph{bitone
1146 Mergesort}-Netzwerk und 18764 für das \emph{Pairwise-Sorting}-Netzwerk.}
1147 \label{fig:count-cuts-16}
1150 Alleine durch Betrachten der ersten Schicht von Komparatoren konnte die Anzahl
1151 der \emph{unterschiedlichen} Schnittmuster auf höchstens $\frac{2}{3}$ der
1152 \emph{möglichen} Schnittmuster reduziert werden. Um die Anzahl der
1153 \emph{unterschiedlichen} Schnittmuster experimentell zu ermitteln, wurden je
1154 eine Million zufällige 8-Schnittmuster auf die 16-Sortiernetzwerke \oes{16},
1155 \bs{16} und \ps{16} angewandt. Anschließend wurde mithilfe einer Hashtabelle
1156 überprüft, ob das resultierende Sortiernetzwerk schon von einem
1157 \emph{äquivalenten} Schnittmuster erzeugt wurde. Falls das Sortiernetzwerk
1158 noch nicht in der Hashtabelle enthalten war, wurde der Zähler für
1159 unterschiedliche Schnittmuster erhöht und das Sortiernetzwerk eingefügt.
1161 Abbildung~\ref{fig:count-cuts-16} trägt die Anzahl der
1162 \emph{unterschiedlichen} Schnittmuster gegen die Anzahl der zufälligen
1163 Schnittmuster auf. Klar zu sehen ist, dass sich die Anzahl der erzeugten
1164 Sortiernetzwerke nach $500.000$~Iterationen nur noch gering verändert und der
1165 Wert nach $1.000.000$~Iterationen allem Anschein nach dem Endwert schon sehr
1168 Die Anzahl der möglichen 8-Schnittmuster ist entsprechend der
1169 Formel~\eqref{eqn:anzahl_schnittmuster} 3.294.720. Diese möglichen
1170 Schnittmuster führen aber nur zu wenigen \emph{unterschiedlichen}
1171 Sortiernetzwerken: 3519 ($\approx 0,1\%$) im Fall des
1172 \emph{Odd-Even-Mergesort}-Netzwerks, 4973 ($\approx 0,15\%$) beim
1173 \emph{bitonen Mergesort}-Netzwerk und 18764 ($\approx 0,57\%$) beim
1174 \emph{Pairwise-Sorting}-Netzwerk. Zwar ist es möglich, dass mehr Iterationen
1175 die Anzahl der unterschiedlichen Schnittmuster noch wachsen lässt. Die Graphen
1176 in Abbildung~\ref{fig:count-cuts-16} geben jedoch Grund zu der Annahme, dass
1177 die Anzahl dieser zusätzlichen, unterschiedlichen Schnittmuster
1178 vernachlässigbar klein ist.
1180 Bedingt durch die sehr große Anzahl möglicher Schnittmuster ist dieses
1181 Experiment für größere Sortiernetzwerke nicht sinnvoll durchführbar. Die
1182 Hashtabelle würde mehr Arbeitsspeicher benötigen als in derzeitigen Rechnern
1183 vorhanden ist, bevor ein entsprechender Graph den linearen Bereich für
1184 „kleine“ x-Werte verlässt.
1186 Um die Anzahl der unterschiedlichen Schnittmuster trotzdem abschätzen zu
1187 können, kann man sich einer stochastischen Methode bedienen, der sogenannten
1188 \emph{Monte-Carlo-Methode}, die \textit{Rolf Wanka} in~\cite{W2006} für
1189 schwierige Zählprobleme vorstellt. Zunächst generiert man eine Menge~$S$ von
1190 $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster
1191 zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter
1192 der Annahme, dass auf diese Art und Weise Sortiernetzwerke zufällig und
1193 gleichverteilt erzeugt werden, entspricht das Verhältnis der zufälligen
1194 Schnittmuster, die in $S$ enthalten sind, und $n$ gleich dem Verhältnis von
1195 $k$ und der Anzahl der unterschiedlichen Schnittmuster insgesamt. Damit kann
1196 die Anzahl der unterschiedlichen Schnittmuster abgeschätzt werden.
1200 \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf}
1202 \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
1203 \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und
1204 $\operatorname{BS}(32)$.}
1205 \label{fig:collisions-10000-1000000-32}
1208 In Abbildung~\ref{fig:collisions-10000-1000000-32} ist das Ergebnis des
1209 Monte-Carlo-Algorithmus für 16-Schnittmuster zu sehen, die auf
1210 $\operatorname{OES}(32)$ und $\operatorname{BS}(32)$ angewandt wurden: Von
1211 jedem Sortiernetzwerk wurden zunächst eine Menge~$S$ von 10.000
1212 \emph{unterschiedlichen} Schnittmustern erzeugt. Anschließend wurden 1.000.000
1213 zufällige Schnittmuster erzeugt und der Anteil der zufälligen Schnittmuster,
1214 die \emph{äquivalent} zu einem in~$S$ enthalten Schnittmuster sind, berechnet.
1215 Für $\operatorname{OES}(32)$ war dieser Anteil etwa $0,19 \%$, für
1216 $\operatorname{BS}(32)$ etwa $0,29 \%$. Das ergibt eine Abschätzung von $5,2
1217 \cdot 10^6$ unterschiedlichen 16-Schnittmustern für $\operatorname{OES}(32)$
1218 und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$.
1222 \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf}
1224 \caption{Abschätzung der unterschiedlichen Schnittmuster mit der
1225 \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000
1226 zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer
1227 Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$
1228 unterschiedlichen Schnittmustern.}
1229 \label{fig:collisions-100000-1000000-32-ps}
1232 Im vorherigen Abschnitt wurde das \emph{Pairwise-Sorting}-Netzwerk
1233 $\operatorname{PS}(32)$ nicht betrachtet, da es für dieses Netzwerk viel mehr
1234 unterschiedliche 16-Schnittmuster gibt als für $\operatorname{OES}(32)$ und
1235 $\operatorname{BS}(32)$. In Anbetracht der Tatsache, dass die Anzahl der
1236 unterschiedlichen 8-Schnittmuster für $\operatorname{PS}(16)$ in
1237 Abbildung~\ref{fig:count-cuts-16} bereits mehr als dreimal größer war als die
1238 Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$,
1239 ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem
1240 kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen
1241 Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit
1242 $\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedlichen
1243 Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385
1244 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent
1245 waren. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$
1246 unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den
1247 vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als
1248 die Anzahl der \emph{möglichen} Schnittmuster.
1251 \section{Der \textsc{SN-Evolution}-Algorithmus}
1252 \label{sect:sn-evolution}
1254 Der \textsc{SN-Evolution}-Algorithmus ist ein \emph{evolutionärer
1255 Algorithmus}, der die in den vorherigen Abschnitten beschriebenen Mischer
1256 (Abschnitt~\ref{sect:konstruktive_netzwerke}) und Schnittmuster
1257 (Abschnitt~\ref{sect:leitungen_entfernen}) verwendet, um „möglichst gute“
1258 Sortiernetzwerke zu erzeugen. Was ein „gutes“ Sortiernetzwerk ausmacht, wird
1259 in Abschnitt~\ref{sect:sn-evolution:bewertung} behandelt. Informationen zur Implementierung
1260 von \textsc{SN-Evolution} befinden sich in
1261 Abschnitt~\ref{sect:implementierung}.
1263 \subsection{Bewertungsfunktion}\label{sect:sn-evolution:bewertung}
1265 Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die
1266 {\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele,
1267 die bei Sortiernetzwerken verfolgt werden können:
1269 \item Möglichst wenige Komparatoren („effizient“)
1270 \item Möglichst wenige Schichten („schnell“)
1275 \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das
1276 Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in~\cite{G1972}
1277 veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
1278 \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das
1279 Netzwerk wurde von \textit{D. Van~Voorhis} 1974 in~\cite{V1974}
1280 veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
1281 \caption{Das effizienteste und das schnellste Sortiernetzwerk für
1282 16~Leitungen, das derzeit bekannt ist.}
1283 \label{fig:16-best-known}
1285 Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken.
1286 Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für
1287 16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in
1288 Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte
1289 16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in
1290 Abbildung~\ref{fig:16-voorhis} zu sehen.
1292 \textsc{SN-Evolution} verwendet eine Gütefunktion, die die beiden Ziele
1293 "`effizient"' und "`schnell"' berücksichtigen kann. Sie hat die folgende
1296 \operatorname{Guete}(S) = w_{\mathrm{Basis}}
1297 + w_{\mathrm{Komparatoren}} \cdot \left|S\right|_\mathrm{Komparatoren}
1298 + w_{\mathrm{Schichten}} \cdot \left|S\right|_\mathrm{Schichten}
1300 Die Parameter $w_{\mathrm{Komparatoren}}$ und $w_{\mathrm{Schichten}}$ dienen
1301 dabei der Festlegung des Optimierungsziels. Wenn einer der beiden Parameter
1302 gleich Null ist, wird nur das jeweils andere Ziel verfolgt. Sind beide
1303 Parameter gleich Null, werden alle Netzwerke mit der gleich Güte bewertet --
1304 jegliche Ergebnisse sind dann rein zufälliger Natur.\footnote{Dass dies nicht
1305 so schlecht ist wie man intuitiv vermuten könnte, zeigt der
1306 \textsc{SN-Markov}-Algorithmus in Abschnitt~\ref{sect:markov}.}
1308 Da möglichst effiziente und schnelle Sortiernetzwerke gefunden werden sollen,
1309 ist ein kleiner Wert von $\operatorname{Guete}(S)$ besser als ein großer Wert.
1310 Das heißt, dass das Ziel von \textsc{SN-Evolution} ist,
1311 $\operatorname{Guete}(S)$ zu \emph{minimieren}.
1313 Mit dem Parameter $w_{\mathrm{Basis}}$ kann auf die Selektion Einfluss
1314 genommen werden. Ist er groß, wird der relative Unterschied der Güten
1315 verschiedener Netzwerke kleiner, was die {\em Exploration}, das Absuchen des
1316 gesamten Lösungsraums, begünstigt. Wählt man $w_{\mathrm{Basis}}$ hingegen
1317 klein -- in Abhängigkeit von den anderen beiden Parametern sind auch negative
1318 Werte möglich -- werden die relativen Unterschiede groß. Dadurch wird die {\em
1319 Exploitation}, das Streben zu (lokalen) Optima, verstärkt. In~\cite{WW2002}
1320 geben \textit{Karsten und Nicole Weicker} einen Überblick über
1321 Selektionsmethoden und Rekombinationsmöglichkeiten.
1323 Diese Parameter haben einen großen Einfluss auf die Geschwindigkeit, mit der
1324 der \textsc{SN-Evolution}-Algorithmus konvergiert und ob er tatsächlich gute
1325 Lösungen findet oder sich in \emph{lokalen} Optima "`verfängt"'. Leider gibt
1326 es kein Patentrezept für die Wahl der Parameter, so dass für verschiedene
1327 Leitungszahlen und Mischer-Typen experimentiert werden muss.
1329 Als guter Standardansatz für \textsc{SN-Evolution} haben sich die folgenden
1330 Werte herausgestellt:
1332 w_{\mathrm{Basis}} &=& 0 \\
1333 w_{\mathrm{Komparatoren}} &=& 1 \\
1334 w_{\mathrm{Schichten}} &=& \left|S\right|_\mathrm{Leitungen}
1336 Sofern nicht anders angegeben, werden diese Werte im Folgenden zur Bewertung
1337 von Sortiernetzwerken verwendet. Die Bewertungsfunktion bevorzugt mit diesen
1338 Konstanten \emph{schnelle} Sortiernetzwerke, da das Einsparen einer Schicht
1339 ein höheres Gewicht als das Einsparen von Komparatoren hat.
1341 Wenn der \textsc{SN-Evolution}-Algorithmus nach \emph{effizienten}
1342 Sortiernetzwerken suchen soll, werden alternative Werte für die Konstanten der
1343 Bewertungsfunktion verwendet. Die Werte
1345 w_{\mathrm{Basis}} &=& 0 \\
1346 w_{\mathrm{Komparatoren}} &=& 2 \\
1347 w_{\mathrm{Schichten}} &=& 1
1349 geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
1352 \subsection{Selektion}
1354 Als \emph{Selektion} wird der Vorgang bezeichnet, der zwei Individuen zufällig
1355 aus der Population auswählt. Sie werden im folgenden Schritt miteinander
1356 rekombiniert. Die Auswahl der Individuen erfolgt zufällig, aber nicht
1357 gleichverteilt. So sorgt die \emph{Selektion} dafür, dass bessere Individuen
1358 eine größere Wahrscheinlichkeit haben zur nächsten Generation beizutragen.
1359 Diese Ungleichbehandlung von Individuen verschiedener Güte ist der Grund für
1360 das Streben des Algorithmus nach besseren Lösungen.
1362 Obwohl dieser Vorteil für gute Individuen intuitiv als sehr gering erscheint,
1363 passiert es häufig, dass die Ausnutzung \emph{(Exploitation)} überhand gewinnt
1364 und der Algorithmus vorschnell in Richtung eines lokalen Optimums optimiert.
1366 Die in \textsc{SN-Evolution} implementierte Selektion eines Individuums lässt
1367 sich mit Pseudocode wie folgt beschreiben:
1372 für jedes Individuum in Population
1374 reziproke Güte := 1.0 / Guete(Individuum)
1375 Wahrscheinlichkeit P := reziproke Güte / (Gütesumme + reziproke Güte)
1376 Gütesumme := Gütesumme + reziproke Güte
1378 mit Wahrscheinlichkeit P
1380 Auswahl := Individuum
1386 Diese Auswahl wird zweimal ausgeführt, um zwei Individuen für die
1387 Rekombination zu erhalten. Das heißt, dass die Individuen bei
1388 \textsc{SN-Evolution} stochastisch unabhängig voneinander ausgewählt werden.
1390 \subsection{Rekombination}
1391 \label{sect:sn-evolution:rekombination}
1393 Bei der Rekombination werden zwei Individuen --~hier Sortiernetzwerke~-- zu
1394 einer neuen Lösung kombiniert. Geeignete Mischer, um die beiden Netzwerke zu
1395 einem Netzwerk mit $2n$~Leitungen zusammenzufügen, sind zum Beispiel der {\em
1396 bitonen Mischer} (Abschnitt~\ref{sect:der_bitone_mischer}) und der
1397 \emph{Odd-Even}-Mischer (Abschnitt~\ref{sect:der_odd_even_mischer}),
1398 Anschließend werden $n$~Leitungen mit einem zufälligen $n$-Schnittmuster wie
1399 in Abschnitt~\ref{sect:leitungen_entfernen} beschrieben entfernt.
1401 Dieses Verfahren hat den großen Vorteil, dass es die Sortiereigenschaft
1402 erhält. Entsprechend muss nicht aufwendig überprüft werden, ob das
1403 Komparatornetzwerk die Sortiereigenschaft besitzt. Der Nachteil ist, dass
1404 nicht alle Sortiernetzwerke auf diese Art und Weise erzeugt werden können.
1406 \subsection{Mutation}
1408 Zu einem vollständigen evolutionären Algorithmus gehört außerdem die Mutation
1409 --~eine zufällige Veränderung einer Lösung. Leider ist es nicht möglich ein
1410 Sortiernetzwerk zufällig zu verändern und dabei die Sortiereigenschaft zu
1411 erhalten. Selbst das \emph{Hinzufügen} eines zufälligen Komparators kann diese
1412 Eigenschaft zerstören.
1414 Nach einer Mutation müsste man überprüfen, ob das neue Komparatornetzwerk die
1415 Sortiereigenschaft noch besitzt. Nach heutigem Wissenstand ist diese
1416 Überprüfung nur mit exponentiellem Aufwand möglich, etwa durch das
1417 Ausprobieren aller $2^n$~Bitmuster, wie in Abschnitt~\ref{sect:0-1-prinzip}
1420 Um das Potenzial einer Mutation abzuschätzen wurde in \textsc{SN-Evolution}
1421 eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population
1422 überprüft eine Funktion die Notwendigkeit jedes einzelnen Komparators. Dazu
1423 wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende
1424 Netzwerk die Sortiereigenschaft noch besitzt. Trotz des hohen Rechenaufwands
1425 -- bei 16-Sortiernetzwerken sind gut 4~Millionen Tests notwendig, um alle
1426 Komparatoren zu überprüfen -- waren die Ergebnisse ernüchternd: Nach circa
1427 1~Million Iterationen mit 16-Sortiernetzwerken fand der so modifizierte
1428 Algorithmus keinen einzigen Komparator, den er hätte entfernen können. Daher
1429 wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet.
1431 \subsection[Bitoner Mischer]{Versuche mit dem bitonen Mischer}
1433 Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk
1434 als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen
1435 Mischer} verwendet, gibt der Algorithmus \emph{effiziente} und in einigen
1436 Fällen \emph{schnelle} Sortiernetzwerke aus. Die Ergebnisse des
1437 \textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
1438 sind in Tabelle~\ref{tbl:sn-ev-bm-fast} zusammengefasst.
1440 \begin{table}\label{tbl:sn-ev-bm-fast}
1442 \rowcolors{4}{black!5}{}
1443 \begin{tabular}{|r|r|r|r|r|}
1445 Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\
1447 ($n$) & Komp. & Schichten & Komp. & Schichten \\
1449 8 & \gcell 20 & 6 & 24 & 6 \\
1450 9 & \Gcell 26 & 8 & 28 & 8 \\
1451 10 & \gcell 31 & \gcell 8 & 33 & 9 \\
1452 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\
1453 12 & \gcell 42 & \gcell 9 & 46 & 10 \\
1454 13 & \Gcell 48 & 10 & 53 & 10 \\
1455 14 & \gcell 54 & 10 & 61 & 10 \\
1456 15 & \Gcell 61 & 10 & 70 & 10 \\
1457 16 & \gcell 67 & 10 & 80 & 10 \\
1458 17 & \Gcell 76 & 12 & 85 & 12 \\
1459 18 & \gcell 87 & \gcell 12 & 91 & 13 \\
1460 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\
1461 20 & \gcell 104 & \gcell 13 & 106 & 14 \\
1462 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\
1463 22 & \gcell 118 & \gcell 14 & 123 & 15 \\
1464 23 & \Gcell 129 & \Gcell 14 & 133 & 15 \\
1465 24 & \gcell 133 & 15 & 144 & 15 \\
1468 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
1469 unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus
1470 wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet
1471 und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die
1472 Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$,
1473 $w_{\mathrm{Schichten}} = n$.}
1477 Alle Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser Konfiguration
1478 gefunden wurden, waren \emph{effizienter} als das \emph{bitone
1479 Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen
1480 Merge}-Netzwerk \bm{n} beruht. Zum Beispiel benötigt das in
1481 Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk
1482 67~Komparatoren, 13~Komparatoren weniger als \bs{n}.
1486 \input{images/16-e1-bitonic-1296542566.tex}
1488 \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
1489 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1490 \textsc{SN-Evolution} unter Verwendung des \emph{bitonen Mischers}
1492 \label{fig:16-e1-bitonic-1296542566}
1495 Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke
1496 bevorzugt, werden in einigen Fällen Netzwerke zurückgegeben, die
1497 \emph{schneller} und \emph{effizienter} als \bs{n} sind. Das
1498 19-Sortiernetzwerk in Abbildung~\ref{fig:19-e1-bm-fast} besitzt beispielsweise
1499 nur 13~Schichten und benötigt damit einen parallelen Schritt weniger als
1504 \input{images/19-e1-bm-fast.tex}
1506 \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in
1507 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
1508 unter Verwendung des \emph{bitonen Mischers} erzeugt.}
1509 \label{fig:19-e1-bm-fast}
1512 \subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer}
1514 Die folgenden Ergebnisse wurden erzielt, indem \textsc{SN-Evolution} mit dem
1515 \emph{Odd-Even-Transpositionsort}-Netzwerk als Eingabe gestartet wurde und in
1516 der Rekombinationsphase das \emph{Odd-Even-Merge}-Netzwerk verwendete. So
1517 erzeugt der Algorithmus entweder Sortiernetzwerke, die genauso schnell und
1518 effizient wie das \oes{n}-Netzwerk, oder Sortiernetzwerke, die schneller aber
1519 weniger effizient als das \oes{n}-Netzwerk sind. Die Ergebnisse von
1520 \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer sind in
1521 Tabelle~\ref{tbl:sn-ev-oem-fast} zusammengefasst.
1523 \begin{table}\label{tbl:sn-ev-oem-fast}
1525 \rowcolors{4}{black!5}{}
1526 \begin{tabular}{|r|r|r|r|r|}
1528 Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\
1530 & Komp. & Schichten & Komp. & Schichten \\
1532 8 & 19 & 6 & 19 & 6 \\
1533 9 & 26 & 8 & 26 & 8 \\
1534 10 & 31 & 9 & 31 & 9 \\
1535 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\
1536 12 & 43 & \gcell 9 & \gcell 41 & 10 \\
1537 13 & 48 & 10 & 48 & 10 \\
1538 14 & 53 & 10 & 53 & 10 \\
1539 15 & 59 & 10 & 59 & 10 \\
1540 16 & 63 & 10 & 63 & 10 \\
1541 17 & 74 & 12 & 74 & 12 \\
1542 18 & 82 & 13 & 82 & 13 \\
1543 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\
1544 20 & 97 & 14 & 97 & 14 \\
1545 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\
1546 22 & 117 & \gcell 14 & \gcell 114 & 15 \\
1547 23 & 127 & \Gcell 14 & \Gcell 122 & 15 \\
1548 24 & 128 & 15 & \gcell 127 & 15 \\
1551 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
1552 unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der
1553 Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n}
1554 gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion
1555 nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} =
1556 1$, $w_{\mathrm{Schichten}} = n$.}
1560 Im vorherigen Abschnitt wurde gezeigt, dass der
1561 \textsc{SN-Evolution}-Algorithmus unter Verwendung des \emph{bitonen Mischers}
1562 Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem
1563 \emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind.
1564 Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht
1565 erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des
1566 \emph{Odd-Even-Merge}-Netzwerks findet, erreichen das
1567 \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber
1568 nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in
1569 Abbildung~\ref{fig:16-e1-oem-fast} dargestellt.
1573 \input{images/16-e1-oem-fast.tex}
1575 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
1576 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1577 \textsc{SN-Evolution} unter Verwendung des \emph{Odd-Even}-Mischers
1579 \label{fig:16-e1-oem-fast}
1582 Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch
1583 mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution}
1584 Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Beispielsweise
1585 benötigt das 19-Sortiernetzwerk, das in Abbildung~\ref{fig:19-e1-oem-fast}
1586 dargestellt ist, nur 13~Schichten, während \oes{19} 14~Schichten benötigt.
1590 \input{images/19-e1-oem-fast.tex}
1592 \caption{Sortiernetzwerk mit 19~Leitungen und 93~Komparatoren in
1593 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
1594 unter Verwendung des \emph{Odd-Even}-Mischers erzeugt.}
1595 \label{fig:19-e1-oem-fast}
1600 %\input{images/08-e2-1237993371.tex}
1602 %\caption{{\tt images/08-e2-1237993371.tex}: 19~Komparatoren in 6~Schichten}
1603 %\label{fig:08-e2-1237993371}
1608 %\input{images/09-e2-1237997073.tex}
1610 %\caption{{\tt images/09-e2-1237997073.tex}: 25~Komparatoren in 8~Schichten}
1611 %\label{fig:09-e2-1237997073}
1616 %\input{images/09-e2-1237999719.tex}
1618 %\caption{{\tt images/09-e2-1237999719.tex}: 25~Komparatoren in 7~Schichten}
1619 %\label{fig:09-e2-1237999719}
1624 %\input{images/10-e2-1239014566.tex}
1626 %\caption{{\tt images/10-e2-1239014566.tex}: 29~Komparatoren in 8~Schichten}
1627 %\label{fig:10-e2-1239014566}
1630 \subsection{Zufälliger Mischer}
1632 Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige
1633 Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der
1634 \emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das
1635 Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur
1636 12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur
1637 82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen,
1638 um das beste Ergebnis beider Konstruktionen zu erreichen.
1639 \textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier
1640 Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem
1641 \emph{Odd-Even}-Mischer wählen. Die Ergebnisse von \textsc{SN-Evolution} bei
1642 einer zufälligen Wahl des Mischers in der Rekombinationsphase sind in
1643 Tabelle~\ref{tbl:sn-ev-rnd-fast} zusammengefasst.
1645 \begin{table}\label{tbl:sn-ev-rnd-fast}
1647 \rowcolors{4}{black!5}{}
1648 \begin{tabular}{|r|r|r|r|r|r|r|}
1650 Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}}
1651 & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}}
1652 & \multicolumn{2}{l|}{\textsc{SN-EV} mit Zufall} \\
1654 ($n$) & Komp. & Schichten & Komp. & Schichten & Komp. & Schichten \\
1656 8 & 20 & 6 & \gcell 19 & 6 & \gcell 19 & 6 \\
1657 9 & 26 & 8 & 26 & 8 & 26 & 8 \\
1658 10 & 31 & \gcell 8 & 31 & 9 & 31 & \gcell 8 \\
1659 11 & \Gcell 37 & 9 & 38 & 9 & \Gcell 37 & 9 \\
1660 12 & 42 & 9 & 43 & 9 & \gcell 41 & 9 \\
1661 13 & 48 & 10 & 48 & 10 & 48 & 10 \\
1662 14 & 54 & 10 & \gcell 53 & 10 & \gcell 53 & 10 \\
1663 15 & 61 & 10 & \Gcell 59 & 10 & \Gcell 59 & 10 \\
1664 16 & 67 & 10 & \gcell 63 & 10 & 64 & 10 \\
1665 17 & 76 & 12 & \Gcell 74 & 12 & \Gcell 74 & 12 \\
1666 18 & 87 & \gcell 12 & \gcell 82 & 13 & 83 & \gcell 12 \\
1667 19 & 93 & 13 & 93 & 13 & \Gcell 92 & 13 \\
1668 20 & 104 & \gcell 13 & \gcell 97 & 14 & 101 & \gcell 13 \\
1669 21 & 109 & 14 & 108 & 14 & \Gcell 107 & 14 \\
1670 22 & 118 & 14 & 117 & 14 & \gcell 116 & 14 \\
1671 23 & 129 & 14 & \Gcell 127 & 14 & 128 & 14 \\
1672 24 & 133 & 15 & \gcell 128 & 15 & 130 & 15 \\
1675 \caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus
1676 unter Verwendung der beiden Mischer-Netzwerke. Der Algorithmus wurde mit dem
1677 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet und nach
1678 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die Konstanten
1679 $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$ und
1680 $w_{\mathrm{Schichten}} = n$.}
1684 Bei einigen Leitungszahlen kann der Algorithmus durch die Verfügbarkeit beider
1685 Mi\-scher-Netzwerke Sortiernetzwerke zurückgeben, die effizienter als die
1686 vorherigen Ergebnisse sind. Beispielsweise ist das 19-Sortiernetzwerk in
1687 Abbildung~\ref{fig:19-e1-rnd-fast} mit 92~Komparatoren effizienter als die
1688 19-Sortiernetzwerke, die mit nur einem der beiden Mischer-Netzwerke erreicht
1689 wurden (Abbildungen~\ref{fig:19-e1-bm-fast} und~\ref{fig:19-e1-oem-fast}).
1693 \input{images/19-e1-rnd-fast.tex}
1695 \caption{Sortiernetzwerk mit 19~Leitungen und 92~Komparatoren in
1696 13~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
1697 unter Verwendung des \emph{bitonen Mischers} und des
1698 \emph{Odd-Even}-Mischers erzeugt.}
1699 \label{fig:19-e1-rnd-fast}
1702 Die Ergebnisse anderer Leitungszahlen erreichen die Geschwindigkeit der
1703 Ergebnisse, die mit dem \emph{bitonen Mischer} erzielt wurden. Die Effizienz
1704 liegt zwischen den Ergebnissen, die mit dem \emph{bitonen Mischer} erzielt
1705 wurden, und den Ergebnissen, die mit dem \emph{Odd-Even}-Mischer erzielt
1706 wurden. Beispielsweise ist das 18-Sortiernetzwerk in
1707 Abbildung~\ref{fig:18-e1-rnd-fast} so schnell wie das Ergebnis, das mit dem
1708 \emph{bitonen Mischer} ausgegeben wurde. Mit 83~Komparatoren liegt die
1709 Effizienz des Sortiernetzwerks zwischen den Ergebnissen, die mit dem
1710 \emph{bitonen Mischer} (87~Komparatoren), beziehungsweise dem
1711 \emph{Odd-Even}-Mischer (82~Komparatoren) erreicht werden konnten.
1715 \input{images/18-e1-rnd-fast.tex}
1717 \caption{Sortiernetzwerk mit 18~Leitungen und 83~Komparatoren in
1718 12~Schichten. Das Netzwerk wurde von dem Algorithmus \textsc{SN-Evolution}
1719 unter Verwendung des \emph{bitonen Mischers} und des
1720 \emph{Odd-Even}-Mischers erzeugt.}
1721 \label{fig:18-e1-rnd-fast}
1724 In einigen Fällen hat \textsc{SN-Evolution} in dieser Konfiguration
1725 Sortiernetzwerke ausgegeben, die weniger effizient und genauso schnell wie die
1726 bisherigen Ergebnisse unter Verwendung des \emph{Odd-Even}-Mischers sind.
1727 Prinzipiell könnte der Algorithmus in jeder Iteration zufällig den
1728 \emph{Odd-Even}-Mischers auswählen, um die selektierten Individuen zu
1729 rekombinieren. Das heißt, das die Ergebnisse auch bei einer zufälligen Wahl
1730 des Mischer-Netzwerks theoretisch erreicht werden können. Allerdings sind
1731 unter Umständen mehr Iterationen notwendig, bis die gleiche Effizienz erreicht
1734 %\input{shmoo-aequivalenz.tex}
1737 \section{Der \textsc{SN-Markov}-Algorithmus}
1740 Der evolutionäre \textsc{SN-Evolution}-Algorithmus aus dem vorherigen
1741 Abschnitt verwendet immer zwei zufällige Sortiernetzwerke („Individuen“) aus
1742 einer Population. Da die beiden „Eltern“ zufällig und unabhängig voneinander
1743 ausgewählt werden, kann es vorkommen, dass das selbe Sortiernetzwerk zweimal
1744 verwendet und mit sich selbst kombiniert wird.
1746 Macht man diesen Spezialfall zum Regelfall, kombiniert das aktuelle Netzwerk
1747 \emph{immer} mit sich selbst und eliminiert anschließend die Hälfte aller
1748 Leitungen, lassen sich einige interessante Beobachtungen anstellen. Netzwerke,
1749 die aus einem Netzwerk $S_0$ durch die beschriebene Kombination von $S_0$ mit
1750 sich selbst und anschließendem Eliminieren der Hälfte der Leitungen hervorgehen
1751 können, heißen \emph{Nachfolger} von $S_0$.
1753 Beim beschriebenen Vorgehen kann man die Sortiernetzwerke als Knoten in einem
1754 (gerichteten) Graphen betrachten. Zwei Knoten $V_0$ und $V_1$, die zwei
1755 Sortiernetzwerke $S_0$ und $S_1$ repräsentieren, sind genau dann mit einer
1756 Kante ${E_{0,1} = (V_0, V_1)}$ verbunden, wenn $S_1$ ein \emph{Nachfolger} von
1757 $S_0$ ist, das heißt, dass $S_1$ durch die Rekombination von $S_0$ mit sich
1758 selbst erzeugt werden kann.
1760 Wie in Abschnitt~\ref{sect:anzahl_schnittmuster} beschrieben, ist die Anzahl
1761 der \emph{unterschiedlichen} Schnittmuster und damit die Anzahl der Nachfolger
1762 sehr groß. Bei den untersuchten 16-Sortiernetzwerken lag die Anzahl der
1763 Nachfolger zwar noch unter 20.000, bei den untersuchten
1764 32-Sortier\-netz\-werken wurden jedoch bereits bis zu $2,6 \cdot 10^8$
1765 unterschiedliche Schnittmuster geschätzt.
1767 Der Algorithmus {\sc SN-Markov} legt auf diesem Nachfolger-Graph einen
1768 zufälligen Weg (englisch: \textit{random walk}) zurück. Er startet auf einem
1769 gegebenen Sortiernetzwerk. Um von einem Sortiernetzwerk zum Nächsten zu
1770 gelangen, rekombiniert der Algorithmus das aktuelle Sortiernetzwerk mit sich
1771 selbst und erhält so einen zufälligen Nachfolger. In Pseudocode lässt sich der
1772 Algorithmus wie folgt beschreiben:
1779 Nachfolger := kombiniere (Netzwerk, Netzwerk)
1780 Netzwerk := Nachfolger
1786 Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der
1787 Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem
1788 zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der
1789 \textsc{SN-Markov}-Algorithmus auf einem entsprechenden
1790 \emph{Odd-Even-Transpositionsort}-Netzwerk gestartet und hat mindestens
1791 1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der
1792 Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler
1793 erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende
1794 prozentuale Verteilung zu sehen.
1796 Ebenfalls in die Graphen der Abbildung~\ref{fig:markov-comparators}
1797 eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen
1798 Daten gut annähert. Die Gamma-Verteilung verwendet einen Offset~$\delta$, der
1799 um Eins kleiner als die kleinste erreichte Komparatorzahl gewählt wurde.
1800 Beispielsweise war die kleinste erreichte Komparatorzahl bei
1801 16-Sortiernetzwerken~63, entsprechend wurde der Offset $\delta = 63 - 1$
1802 gesetzt und die Gamma-Verteilung $g(x - 62)$ eingezeichnet. Die Parameter $k$
1803 und $\theta$, die eine Gamma-Verteilung charakterisieren, wurden mit einem
1804 Fitting-Algorithmus bestimmt. Der konkrete Offset ist als Parameter~$\delta$
1805 unter den Graphen angegeben.
1809 \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}}
1810 \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}}
1811 \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}}
1812 \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}}
1813 \caption{Anzahl der Komparatoren von Sortiernetzwerken,
1814 die von {\sc SN-Markov} durchlaufen wurden (rot). Ebenfalls eingezeichnet
1815 ist jeweils eine \emph{Gamma-Verteilung} (grün), die eine gute Näherung der
1816 gemessenen Daten darstellt.}
1817 \label{fig:markov-comparators}
1822 \includegraphics[viewport=0 0 425 262,width=15cm]{images/comparison-comparators-16.pdf}
1824 \caption{Anzahl der Komparatoren, die 16-Sortiernetzwerke von
1825 \textsc{SN-Markov} und \textsc{SN-Evolution} (mit dem
1826 \emph{Odd-Even}-Mischer und dem \emph{bitonen Mischer}) besaßen.}
1827 \label{fig:comparison-comparators}
1830 Der Graph in Abbildung~\ref{fig:comparison-comparators} zeigt, dass der
1831 \textsc{SN-Markov}-Algorithmus nicht schlechter ist als der
1832 \textsc{SN-Evolution}-Algo\-rith\-mus. Analog zu dem Versuch mit
1833 \textsc{SN-Markov}, wurde beim \textsc{SN-Evolution}-Algorithmus die Anzahl
1834 der Komparatoren jedes neuen Individuums ermittelt und gespeichert. Als
1835 Startnetzwerk diente bei beiden Algorithmen das
1836 \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{16}. Der Graph zeigt auf der
1837 x-Achse die Anzahl der Komparatoren, auf der y-Achse die Häufigkeit, mit der
1838 ein Sortiernetzwerk mit dieser Komparatorzahl durch die Rekombination erzeugt
1839 wurde. Die Ergebnisse von \textsc{SN-Evolution} unterscheiden sich außerdem je
1840 nach verwendetem Mischer-Netzwerk -- \oem{32}, beziehungsweise \bm{32}.
1842 Sowohl der \textsc{SN-Markov}-Algorithmus, der das
1843 \emph{Odd-Even-Merge}-Netzwerk verwendet, als auch \textsc{SN-Evolution} mit
1844 \oem{32} erreichen eine Komparatorzahl von~63 und finden Sortiernetzwerke, die
1845 bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} sind.
1846 Interessanterweise erzeugt \textsc{SN-Markov} derartige Netzwerke häufiger:
1847 Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit
1848 63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335
1849 \%$ rund 20~mal höher.
1851 Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem
1852 \emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist
1853 jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die
1854 mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort}. \oet{16}
1855 ist aus 120~Komparatoren aufgebaut. Bei dem Lauf, der die Daten für
1856 Abbildung~\ref{fig:comparison-comparators} lieferte, trat auch jeweils ein
1857 Sortiernetzwerk mit 121 und 124~Komparatoren auf. Dass Sortiernetzwerke mit so
1858 vielen Komparatoren im Verlauf des Experiments selbst nach über 100~Millionen
1859 Iterationen nicht noch einmal erzeugt wurden, ist vermutlich ein Phänomen, das
1860 mit der Initialisierung durch das \emph{Odd-Even-Transpositionsort}-Netzwerk
1865 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-14-pct.pdf}
1867 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 14~Leitungen),
1868 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1869 % \emph{Gamma-Verteilung} $f(x - 52)$ mit $k = 9,522$ und $\theta = 0,867$.}
1870 % \label{fig:markov-comparators-14}
1875 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-16-pct.pdf}
1877 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 16~Leitungen),
1878 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1879 % \emph{Gamma-Verteilung} $f(x - 62)$ mit $k = 17,939$ und $\theta = 1,091$.}
1880 % \label{fig:markov-comparators-16}
1885 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-comparators-18-pct.pdf}
1887 % \caption{Anzahl der Komparatoren von Sortiernetzwerken (mit 18~Leitungen),
1888 % die von {\sc SN-Markov} durchlaufen wurden. Grün eingezeichnet ist die
1889 % \emph{Gamma-Verteilung} $f(x - 81)$ mit $k = 10,724$ und $\theta = 0,766$.}
1890 % \label{fig:markov-comparators-18}
1895 % \includegraphics[viewport=0 0 425 262,width=15cm]{images/markov-cycles-16.pdf}
1897 % \caption{Zyklen, die beim \textit{Random Walk} des
1898 % \textsc{SN-Markov}-Algorithmus detektiert wurden. Auf der x-Achse sind die
1899 % Anzahl der Schritte, die \textsc{SN-Markov} zurückgelegt hat, auf der
1900 % y-Achse die Längen der gefundenen Zyklen aufgetragen. Das initiale
1901 % Start-Sortiernetzwerk war $\operatorname{OET}(16)$.}
1902 % \label{fig:markov-cycles-16}
1906 \section[\textsc{SN-Evolution-Cut}]{Der \textsc{SN-Evolution-Cut}-Algorithmus}
1907 \label{sect:sn-evolution-cut}
1909 Das Programm \textsc{SN-Evolution-Cut} implementiert einen evolutionären
1910 Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten
1911 Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer
1912 möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung
1913 von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:sn-evolution:bewertung}.
1915 Der \textsc{SN-Evolution-Cut}-Algorithmus verwendet \emph{Schnittmuster}, die
1916 in Abschnitt~\ref{sect:anzahl_schnittmuster} definiert wurden, als Individuen.
1917 Ein Individuum besteht aus einer Liste von $n$~Zahlen, die entweder 1, $-1$
1918 oder 0 sind. Dieser Werte entsprechen Maximum, Minimum und unbelegt. Bei einem
1919 $k$-Schnittmuster sind genau $k$ Zahlen ungleich Null.
1921 Um zwei Individuen zu rekombinieren werden die ersten $r$~Werte des einen
1922 Schnittmusters und die letzten ${n-r}$~Schnitte des zweiten Schnittmusters
1923 verwendet. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq n$. Anschließend
1924 werden zufällig Werte auf Null beziehungsweise 1 oder $-1$ gesetzt, um die
1925 Anzahl der Schnitte zu korrigieren.
1927 Die Mutation vertauscht entweder die Werte von zwei zufälligen Positionen oder
1928 multipliziert den Wert einer Leitung mit $-1$, um die Schnittrichtung zu
1931 Die Eingabe für \textsc{SN-Evolution-Cut} ist ein $n$-Sortiernetzwerk und eine
1932 Zahl $k$, $1 \leqq k < n$, die angibt wie viele Leitungen entfernt werden
1933 sollen. Der Rückgabewert des \textsc{SN-Evolution-Cut}-Algorithmus ist ein
1934 \emph{$k$-Schnittmuster}. Wird das Schnittmuster auf das Sortiernetzwerk, mit
1935 dem der Algorithmus gestartet wurde, angewendet, entsteht ein möglichst
1936 schnelles und effizientes Sortiernetzwerk mit $m = n - k$ Leitungen. Da mit
1937 dem Eingabe-Netzwerk und dem zurückgegebenen $k$-Schnittmuster das
1938 $m$-Sortiernetzwerk eindeutig bestimmt ist, werden im Folgenden sowohl das
1939 $k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von
1940 \textsc{SN-Evolution-Cut} bezeichnet.
1942 \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk}
1943 \label{sect:sn-evolution-cut:bs}
1947 Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen
1948 Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll,
1949 ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke
1950 als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k
1951 = 6$ gestartet, resultiert das gefundene Schnittmuster in einem
1952 Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16}
1953 benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert
1954 wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen.
1956 % Beispiel Effizienz
1960 \input{images/16-ec-from-bs22.tex}
1962 \caption{Sortiernetzwerk mit 16~Leitungen und 67~Komparatoren in
1963 10~Schichten. Das Netzwerk wurde von dem Algorithmus
1964 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk
1965 $\operatorname{BS}(22)$ durch das 6-Schnittmuster $\operatorname{MIN}(4,
1966 10, 17)$, $\operatorname{MAX}(7, 15, 20)$ erzeugt.}
1967 \label{fig:16-ec-from-bs22}
1970 Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen
1971 Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden,
1972 gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde
1973 mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten
1974 der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$,
1975 $w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder
1976 Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten
1977 befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des
1978 Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des
1979 resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der
1980 Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu
1985 \rowcolors{2}{black!5}{}
1986 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
1988 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
1990 9 & 21 & & & & & & & & & & & & & & & \\
1991 10 & 20 & 27 & & & & & & & & & & & & & & \\
1992 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\
1993 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\
1994 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\
1995 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\
1996 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\
1997 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\
1998 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\
1999 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\
2000 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\
2001 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\
2002 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\
2003 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\
2004 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\
2005 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\
2007 \bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\
2011 \caption{Anzahl der Komparatoren der Ergebnisse von
2012 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
2013 Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
2014 die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
2015 Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
2016 \label{tbl:ec-bs-efficiency}
2019 Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut}
2020 mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der
2021 gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von
2022 $m=23$) ein Ergebnis, das effizienter als \bs{m} ist.
2024 In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein
2025 effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut}
2026 gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren
2027 3~weniger als \bs{19}.
2029 Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke,
2030 beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein
2031 Sortiernetzwerk mit 31~Komparatoren gefunden.
2035 Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der
2036 \textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als
2037 das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In
2038 Tabelle~\ref{tbl:ec-bs-speed} ist die Anzahl der Schichten, die die Ergebnisse
2039 von \textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren,
2040 aufgelistet. Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n},
2041 jede Spalte enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die
2042 Zellen enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks.
2046 \rowcolors{2}{black!5}{}
2047 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2049 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2051 9 & 6 & & & & & & & & & & & & & & & \\
2052 10 & 6 & 8 & & & & & & & & & & & & & & \\
2053 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
2054 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
2055 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
2056 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
2057 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
2058 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
2059 17 & 6 & 8 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
2060 18 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
2061 19 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
2062 20 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
2063 21 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
2064 22 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
2065 23 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
2066 24 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
2068 \bs{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
2072 \caption{Anzahl der Schichten der Ergebnisse von
2073 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen
2074 Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt
2075 die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die
2076 Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.}
2077 \label{tbl:ec-bs-speed}
2080 Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die
2081 schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke,
2082 die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt
2083 werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt.
2085 % Beispiel Geschwindigkeit
2089 \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das
2090 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}}
2091 \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das
2092 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}}
2093 \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das
2094 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}}
2095 \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das
2096 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}}
2097 \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11,
2098 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
2099 erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.}
2100 \label{fig:ec-bs-fast_networks}
2103 Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das
2104 Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m}
2105 führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt
2106 werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht
2107 einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m
2108 = 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu
2109 reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise
2110 noch größer gewählt werden.
2112 % Detaillierte Betrachtung fuer m = 19
2114 Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von
2115 \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten
2116 werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in
2117 Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im
2118 Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n =
2119 37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19}
2120 und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein
2121 Beispiel für ein solches Netzwerk ist in
2122 Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen.
2126 \rowcolors{2}{black!5}{}
2127 \begin{tabular}{|r|r|r|}
2129 $n$ & Komp. & Schichten \\
2149 \rowcolor{green!10!white!95!black}
2153 \bs{19} & 98 & 14 \\
2154 \oes{19} & 91 & 14 \\
2158 \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
2159 von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt
2160 wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als
2161 \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit
2162 13~Schichten die Effizienz der vorherigen
2163 Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese
2164 Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37}
2165 auf diese Art erzeugt wurde, ist in
2166 Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.}
2167 \label{tbl:ec-bs-19}
2172 \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010},
2173 wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode
2174 konstruiert wurde, durch systematisches Entfernen von Leitungen in einen
2175 ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert werden
2176 kann, so dass dieser alternative Mischer im Vergleich zu $\bm{\frac{n}{2} =
2177 2^{d-1}}$ Komparatoren einspart.
2179 Basierend auf diesen alternativen Mischern geben \textit{Mühlenthaler} und
2180 \textit{Wanka} eine Konstruktionsvorschrift für Sortiernetzwerke an, die
2181 gegenüber \bs{n} ${\frac{1}{4}n(\log n - 1)}$ Komparatoren einspart.
2182 Beispielsweise wird ein 16-Sortiernetzwerk angegeben, das nur 68~Komparatoren
2183 benötigt. Dieses Netzwerk ist in Abbildung~\ref{fig:16-muehlenthaler}
2188 \input{images/16-muehlenthaler.tex}
2190 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
2191 10~Schichten. Das Netzwerk wurde 2010 von \textit{Mühlenthaler} und
2192 \textit{Wanka} aus optimierten bitonen Mischern konstruiert und
2193 in~\cite{MW2010} veröffentlicht.}
2194 \label{fig:16-muehlenthaler}
2199 \input{images/16-ec-from-bs32.tex}
2201 \caption{Visualisierung eines 16-Schnittmusters, das von
2202 \textsc{SN-Evolution-Cut} für das \emph{bitone Mergesort}-Netzwerk \bs{32}
2203 berechnet wurde. Das resultierende Sortiernetzwerk besteht aus
2204 68~Komparatoren in 10~Schichten und ist in
2205 Abbildung~\ref{fig:16-ec-from-bs32-normalized} als
2206 Standard-Sortiernetzwerk dargestellt.}
2207 \label{fig:16-ec-from-bs32}
2212 \input{images/16-ec-from-bs32-normalized.tex}
2214 \caption{Sortiernetzwerk mit 16~Leitungen und 68~Komparatoren in
2215 10~Schichten. Das Netzwerk wurde mit einem 16-Schnittmuster, das von
2216 \textsc{SN-Evolution-Cut} berechnet wurde, aus dem \emph{bitone
2217 Mergesort}-Netzwerk \bs{32} erzeugt. Das Schnittmuster ist in
2218 Abbildung~\ref{fig:16-ec-from-bs32} dargestellt.}
2219 \label{fig:16-ec-from-bs32-normalized}
2222 Startet man {\sc SN-Evolution-Cut} mit dem \emph{bitonen Mergesort}-Netzwerk
2223 $\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der
2224 Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein
2225 16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in den
2226 Abbildungen~\ref{fig:16-ec-from-bs32} und~\ref{fig:16-ec-from-bs32-normalized}
2227 zu sehen. Abbildung~\ref{fig:16-ec-from-bs32} zeigt $\operatorname{BS}(32)$
2228 und das Schnittmuster ${\operatorname{MIN}(0, 5, 9, 11, 15, 17, 20, 22, 26,
2229 29, 30)}$, ${\operatorname{MAX}(2, 4, 13, 19, 24)}$, das durch
2230 \textsc{SN-Evolution-Cut} gefunden wurde.
2231 Abbildung~\ref{fig:16-ec-from-bs32-normalized} zeigt das 16-Sortiernetzwerk
2232 nachdem das Schnittmuster angewendet und das Netzwerk normalisiert wurde.
2233 % Eine Ähnlichkeit zu $\operatorname{BS}(32)$ oder $\operatorname{BS}(16)$ ist
2234 % in diesem Netzwerk nicht mehr erkennbar -- insbesondere die ersten Schichten
2235 % des Netzwerks scheinen rein zufällig zu sein.
2238 % 0:MAX 1:MAX 4:MIN 6:MAX 9:MAX 11:MAX 14:MIN 15:MAX 18:MAX 19:MAX 21:MAX
2239 % 23:MIN 24:MAX 25:MAX 30:MIN 31:MIN 32:MAX 34:MAX 36:MIN 37:MAX 40:MAX
2240 % 43:MAX 46:MIN 47:MAX 48:MAX 49:MAX 54:MIN 55:MAX 56:MAX 58:MIN 60:MAX
2243 \input{images/32-ec-from-bs64.tex}
2245 \caption{Sortiernetzwerk mit 32~Leitungen und 206~Komparatoren in
2246 15~Schichten. Das Netzwerk wurde von dem Algorithmus
2247 \textsc{SN-Evolution-Cut} aus dem bitonen Mergesort-Netzwerk
2248 $\operatorname{BS}(64)$ durch 32~Schnitte erzeugt. Das zugehörige
2250 $\operatorname{MIN}(4, 14, 23, 30, 31, 36, 46, 54, 58)$,
2251 $\operatorname{MAX}(0, 1, 6, 9, 11, 15, 18, 19, 21, 24, 25, 32, 34, 37,
2252 40, 43, 47, 48, 49, 55, 56, 60, 63)$.}
2253 \label{fig:32-ec-from-bs64}
2256 Wenn \textsc{SN-Evolution-Cut} mit dem \bs{64}-Netzwerk und $k = 32$ gestartet
2257 wird, findet der Algorithmus 32-Sortiernetzwerke, die effizienter sind als
2258 32-Sortiernetzwerke, die nach \textit{Mühlenthalers} und \textit{Wankas}
2259 Methode konstruiert werden. Ein von \textsc{SN-Evolution-Cut} aus \bs{64}
2260 generiertes 32-Sortiernetzwerk ist in Abbildung~\ref{fig:32-ec-from-bs64}
2261 dargestellt. Das \emph{bitone Mergesort}-Netzwerk \bs{32} benötigt
2262 240~Komparatoren, ein aus den optimierten Mischern aufgebautes Netzwerk
2263 verbessert die Effizienz auf 208~Komparatoren. Das Ergebnis von
2264 \textsc{SN-Evolution-Cut} kommt mit nur 206~Komparatoren aus. Die
2265 Geschwindigkeit aller genannten Sortiernetzwerke ist mit 15 parallelen
2266 Schritten identisch.
2268 Wenn die Leitungszahl des Eingabenetzwerks keine Zweierpotenz ist, kann
2269 \textsc{SN-Evo\-lu\-tion-Cut} auch 16-Sortiernetzwerke erzeugen, die diese
2270 Effizienz unterbieten. Das geht aus den Daten in
2271 Tabelle~\ref{tbl:ec-bs-efficiency} hervor. Ein 16-Sortiernetzwerk mit
2272 67~Komparatoren, das von \textsc{SN-Evolution-Cut} generiert wurde, ist in
2273 Abbildung~\ref{fig:16-ec-from-bs22} dargestellt.
2275 Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr
2276 unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für
2277 gute Schnittmuster anzugeben.
2279 Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen
2280 Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein.
2281 Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in
2282 Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73
2283 ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten
2284 ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich
2285 die Schnittmuster aufgrund der Symmetrie des \emph{bitonen
2286 Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung --
2287 mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig.
2289 Dass die Sortiernetzwerke, die mit den Schnittmustern von
2290 \textsc{SN-Evolution-Cut} entstehen, keine erkennbare Struktur haben, ist
2291 jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere von der
2292 Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem
2293 \emph{Odd-Even-Transpositionsort}-Netzwerk $\operatorname{OET}(n)$ und
2294 $k$~Schnitten gestartet, so ist das beste Ergebnis immer das
2295 $\operatorname{OET}(n-k)$-Netzwerk.
2297 \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk}
2298 \label{sect:sn-evolution-cut:oes}
2300 Wird \textsc{SN-Evolution-Cut} mit dem \emph{Odd-Even-Mergesort}-Netzwerk
2301 \oes{n} gestartet, gibt der Algorithmus meist Sortiernetzwerke zurück, die
2302 genauso effizient und schnell wie das entsprechende
2303 \emph{Odd-Even-Mergesort}-Netzwerk \oes{m} sind. Die Effizienz der
2304 Sortiernetzwerke, die mit Schnittmustern von \textsc{SN-Evolution-Cut} aus
2305 \oes{n} entstehen können, zeigt Tabelle~\ref{tbl:ec-oes-efficiency}
2310 \rowcolors{2}{black!5}{}
2311 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2313 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2315 9 & 19 & & & & & & & & & & & & & & & \\
2316 10 & 19 & 26 & & & & & & & & & & & & & & \\
2317 11 & 19 & 26 & 31 & & & & & & & & & & & & & \\
2318 12 & 19 & 26 & 31 & 37 & & & & & & & & & & & & \\
2319 13 & 19 & 26 & 31 & 37 & 41 & & & & & & & & & & & \\
2320 14 & 19 & 26 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
2321 15 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
2322 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
2323 17 & 19 & 26 & 31 & 38 & 41 & 48 & 53 & 59 & 63 & & & & & & & \\
2324 18 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & & & & & & \\
2325 19 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & & & & & \\
2326 20 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & & & & \\
2327 21 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & & & \\
2328 22 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & & \\
2329 23 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & \\
2330 24 & 19 & 26 & 31 & 38 & 43 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
2332 \oes{m}&19& 26 & 31 & 37 & 41 & 48 & 53 & 59 & 63 & 74 & 82 & 91 & 97 & 107 & 114 & 122 \\
2336 \caption{Anzahl der Komparatoren der Ergebnisse von
2337 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2338 \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
2339 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
2340 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2342 \label{tbl:ec-oes-efficiency}
2347 \subfigure[11-Sortiernetzwerk aus 38~Komparatoren in 9~Schichten. Das
2348 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}}
2349 \subfigure[12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten. Das
2350 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}}
2351 \caption{Für einige Ziel-Leitungszahlen, unter anderem $m = 10$ und $m =
2352 11$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke
2353 erzeugen, die \emph{schneller} aber weniger \emph{effizient} als \oes{m}
2355 \label{fig:ec-oes-fast_networks}
2358 Die Bewertungsfunktion, die \textsc{SN-Evolution-Cut} verwendet, bevorzugt
2359 schnelle Sortiernetzwerke. Dadurch kann es vorkommen, dass ein
2360 $m$-Sortiernetzwerk, das durch ein von \textsc{SN-Evolution-Cut} ausgegebenes
2361 Schnittmuster entsteht, schneller als \oes{m} ist. Diese Geschwindigkeit
2362 war allerdings in allen beobachteten Fällen nur dann möglich, wenn
2363 zusätzliche Komparatoren in Kauf genommen wurden. In den
2364 Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} ist dieser
2365 Fall für $m = 11$ und $k \geqq 6$, beziehungsweise $m = 12$ und $k \geqq 6$ zu
2366 beobachten. Die entsprechenden schnellen Sortiernetzwerke sind in
2367 Abbildung~\ref{fig:ec-oes-fast_networks} dargestellt.
2369 Wie beim \emph{bitonen Mergesort}-Netzwerk reicht auch beim
2370 \emph{Odd-Even-Mergesort}-Netzwerk ein einziger Schnitt nicht aus, um die
2371 Geschwindigkeit gegenüber \oes{m} zu verbessern. Bei $m = 11$ und $m = 12$ war
2372 jeweils mindestens ein 6-Schnittmuster notwendig, um eine höhere
2373 Geschwindigkeit zu erreichen.
2375 In Tabelle~\ref{tbl:ec-oes-19} sind die Ergebnisse von
2376 \textsc{SN-Evolution-Cut} für \oes{n}, $n = 20$ und $m = 19$ ($k = 1 \dots
2377 19$) aufgelistet. Mit $k = 10$ wird das erste mal ein schnelles
2378 19-Sortiernetzwerk mit 13~Schichten ausgegeben. Mit $k \geqq 11$ sind die
2379 resultierenden Netzwerke mit 93~Komparatoren effizienter als das Ergebnis mit
2380 $k = 10$, das 95~Komparatoren benötigt. Das Ergebnis, das auf Basis des
2381 \emph{bitonen Mergesort}-Netzwerks erreicht wurde (92~Komparatoren in
2382 13~Schichten, siehe Tabelle~\ref{tbl:ec-bs-19}), wird nicht erreicht.
2386 \rowcolors{2}{black!5}{}
2387 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2389 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2391 9 & 6 & & & & & & & & & & & & & & & \\
2392 10 & 6 & 8 & & & & & & & & & & & & & & \\
2393 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\
2394 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
2395 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
2396 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
2397 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
2398 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
2399 17 & 6 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\
2400 18 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\
2401 19 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\
2402 20 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\
2403 21 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\
2404 22 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\
2405 23 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\
2406 24 & 6 & 8 & 9 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
2408 \oes{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\
2412 \caption{Anzahl der Schichten der Ergebnisse von
2413 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2414 \emph{Odd-Even-Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$.
2415 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \oes{n} an, jede
2416 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2418 \label{tbl:ec-oes-speed}
2423 \rowcolors{2}{black!5}{}
2424 \begin{tabular}{|r|r|r|}
2426 $n$ & Komp. & Schichten \\
2440 \rowcolor{green!10!white!95!black}
2444 \rowcolor{green!10!white!95!black}
2448 \rowcolor{green!10!white!95!black}
2452 \rowcolor{green!10!white!95!black}
2457 \bs{19} & 98 & 14 \\
2458 \oes{19} & 91 & 14 \\
2462 \caption{Komparatoren und Schichten von Sortiernetzwerken, die von
2463 \textsc{SN-Evolution-Cut} mit \oes{n} und $k = n - 19$ ermittelt wurden. Erst mit $k = 10$
2464 ist es möglich gegenüber \oes{19} eine Schicht einzusparen. Dafür ist die
2465 Effizienz von 91~Komparatoren nicht mehr erreichbar.}
2466 \label{tbl:ec-oes-19}
2471 In Abschnitt~\ref{sect:anzahl_schnittmuster} wurde bereits untersucht, wie
2472 viele \emph{unterschiedliche} 16-Schnittmuster die konstruierten
2473 Sortiernetzwerke $\operatorname{OES}(32)$, $\operatorname{BS}(32)$ und
2474 $\operatorname{PS}(32)$ besitzen. Eines der Ergebnisse war, dass von diesen
2475 Sortiernetzwerken das \emph{Odd-Even-Mergesort}-Netzwerk die wenigsten
2476 unterschiedlichen 16-Schnittmuster besitzt -- nur etwa $5,2$~Millionen.
2477 Entsprechend ist es wenig verwunderlich, dass \textsc{SN-Evolution-Cut}
2478 gestartet mit $\operatorname{OES}(32)$ sehr schnell\footnote{Ein
2479 entsprechendes Ergebnis wird meist nach 20.000 bis 100.000 Iterationen
2480 geliefert. Bei dieser Problemgröße erreicht die Implementierung (siehe
2481 Abschnitt~\ref{sect:implementierung}) etwa 20.000 Iterationen pro Sekunde auf
2482 derzeitigen Computern.} ein gutes 16-Schnittmuster findet.
2484 Eines der 16-Schnittmuster für \oes{32}, die ein Sortiernetzwerk erzeugen, das
2485 bezüglich Effizienz und Geschwindigkeit identisch zu \oes{16} ist, ist
2486 $\operatorname{MIN}(1, 6, 11, 14, 17, 23, 26, 29)$, $\operatorname{MAX}(2, 7,
2487 8,$ $13, 18, 21, 27, 31)$. Das Schnittmuster ist in
2488 Abbildung~\ref{fig:16-ec-from-oes32-cut} veranschaulicht, das resultierende
2489 Netzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32} zu sehen.
2493 \input{images/16-ec-from-oes32-cut.tex}
2495 \caption{Visualisierung eines 16-Schnittmusters, das auf
2496 $\operatorname{OES}(32)$ angewendet ein Sortiernetzwerk ergibt, das
2497 bezüglich Geschwindigkeit und Effizienz identisch zu \oes{16} ist. Das
2498 resultierende Sortiernetzwerk ist in Abbildung~\ref{fig:16-ec-from-oes32}
2500 \label{fig:16-ec-from-oes32-cut}
2505 \input{images/16-ec-from-oes32.tex}
2507 \caption{16-Sortiernetzwerk mit 63~Komparatoren in 10~Schichten.
2508 Das Netzwerk wurde aus dem \emph{Odd-Even-Mergesort}-Netzwerk \oes{32} mit
2509 einem 16-Schnittmuster erzeugt, das von \textsc{SN-Evolution-Cut}
2510 berechnet wurde. Das Schnittmuster ist in
2511 Abbildung~\ref{fig:16-ec-from-oes32-cut} dargestellt.}
2512 \label{fig:16-ec-from-oes32}
2515 % Regelmaessiges Schnittmuster fuer n = 2^d
2517 Bei diesem Schnittmuster fällt auf, dass es für jeweils vier Eingänge (0--3,
2518 4--7, \dots, 28--31) einen Minimum- und einen Maximumschnitt gibt. Aus dieser
2519 Beobachtung kann das regelmäßige Schnittmuster
2521 \textit{Eingang}_i = \left\{ \begin{array}{rl}
2522 \infty & \quad \textrm{falls } i \bmod 4 = 0 \\
2523 -\infty & \quad \textrm{falls } i \bmod 4 = 3 \\
2524 ? & \quad \mathrm{sonst}
2527 abgeleitet werden. Es entfernt die Hälfte der Leitungen, vorausgesetzt die
2528 Anzahl der Leitungen ist durch Vier teilbar. Das Schnittmuster erzeugt
2529 effiziente Netzwerke, wenn die Anzahl der Leitungen $n = 2^d$ eine
2530 Zweierpotenz ist. Ein 32-Sortiernetzwerk, das mit diesem Schnittmuster aus
2531 \oes{64} erzeugt wurde, ist in Abbildung~\ref{fig:32-ec-from-oes64} zu sehen.
2535 \input{images/32-ec-from-oes64.tex}
2537 \caption{32-Sortiernetzwerk mit 191~Komparatoren in 15~Schichten.
2538 Das Netzwerk wurde mit einem regelmäßigen Schnittmuster aus dem
2539 \emph{Odd-Even-Mergesort}-Netzwerk \oes{64} erzeugt.}
2540 \label{fig:32-ec-from-oes64}
2543 Wenn die Anzahl der Leitungen keine Zweierpotenz ist, erreichen die durch
2544 dieses regelmäßige Schnittmuster erzeugten Sortiernetzwerke die Effizienz des
2545 \emph{Odd-Even-Mergesort}-Netzwerks nicht. Wendet man das Schnittmuster
2546 beispielsweise auf \oes{24} an, so erhält man ein Sortiernetzwerk mit
2547 43~Komparatoren -- \oes{12} kommt mit 41~Komparatoren aus. Die Geschwindigkeit
2548 beider Sortiernetzwerke ist mit 10~Schichten identisch.
2550 % SN-Evolution-Cut vs. regelmaessiges Schnittmuster
2552 Wird der \textsc{SN-Evolution-Cut}-Algorithmus mit \oes{n}, $n = 22, 23, 24$
2553 und $k = 10, 11, 12$ gestartet, hängt die Ausgabe von der verwendeten
2554 Gütefunktion ab. Werden effiziente Netzwerke bevorzugt, findet der Algorithmus
2555 Schnittmuster wie das 12-Schnittmus\-ter $\operatorname{MIN}(6, 7, 8, 9, 16, 17,
2556 20, 22)$, $\operatorname{MAX}(2, 4, 12, 14)$ für \oes{24}, dessen Ergebnis in
2557 Abbildung~\ref{fig:12-ec-from-oes24-efficient} zu sehen ist. Das resultierende
2558 Sortiernetzwerk besteht aus 41~Komparatoren, die in 10~Schichten angeordnet
2559 werden können. Damit ist das Netzwerk bezüglich Effizienz und Geschwindigkeit
2560 gleichauf mit \oes{12}. Werden hingegen schnelle Sortiernetzwerke bevorzugt,
2561 werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15,
2562 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis
2563 dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu
2564 sehen, weitere Ergebnisse für diese Gütefunktion sind in den
2565 Tabellen~\ref{tbl:ec-oes-efficiency} und~\ref{tbl:ec-oes-speed} zusammengefasst.
2566 Das resultierende 12-Sortiernetzwerk besteht aus 43~Komparatoren, die
2567 in 9~Schichten angeordnet sind. Das resultierende Netzwerk zwar nicht so
2568 effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12}.
2572 \subfigure[Effizientes 12-Sortiernetzwerk aus 41~Komparatoren in
2573 10~Schichten, das von \textsc{SN-Evolution-Cut} aus dem
2574 \emph{Odd-Even-Mergesort}-Netzwerk generiert
2575 wurde.]{\input{images/12-ec-from-oes24-efficient.tex}\label{fig:12-ec-from-oes24-efficient}}
2576 \subfigure[Schnelles 12-Sortiernetzwerk aus 43~Komparatoren in 9~Schichten,
2577 das von \textsc{SN-Evolution-Cut} aus dem \emph{Odd-Even-Mergesort}-Netzwerk
2579 wurde.]{\input{images/12-ec-from-oes24-fast.tex}\label{fig:12-ec-from-oes24-fast}}
2580 \caption{Startet man \textsc{SN-Evolution-Cut} mit \oes{24}, hängt das
2581 Ergebnis von der Bewertungsfunktion ab.}
2582 \label{fig:12-ec-from-oes24}
2585 \subsection[Pairwise-Sorting-Netzwerk]{Versuche mit dem Pairwise-Sorting-Netzwerk}
2587 Eine weitere interessante Eingabe für \textsc{SN-Evolution-Cut} ist das
2588 \emph{Pairwise-Sorting}-Netzwerk \ps{n}, das \textit{Ian
2589 Parberry} in seiner Arbeit „The Pairwise Sorting Network“ \cite{P1992}
2590 definiert. Einerseits wurde in Abschnitt~\ref{sect:anzahl_schnittmuster}
2591 gezeigt, dass es für \ps{n} sehr viele \emph{unterschiedliche} Schnittmuster
2592 gibt. Andererseits sind die Sortiernetzwerke, die nach \textit{Parberrys}
2593 Methode erzeugt werden, genauso schnell und effizient wie das
2594 \emph{Odd-Even-Mergesort}-Netzwerk, wenn die Leitungszahl $n = 2^d$ eine
2599 Für viele Kombinationen von \ps{n} und $k$ sind die Sortiernetzwerke, die
2600 \textsc{SN-Evolution-Cut} ausgibt, weniger effizient als das entsprechende
2601 \ps{m}-Netzwerk. Für einige Kombinationen werden jedoch auch effizientere
2602 Netzwerke generiert, beispielsweise für $m = 11$ und $m = 20$. Die Effizienz
2603 der Sortiernetzwerke, die \textsc{SN-Evolution-Cut} auf Basis des
2604 \emph{Pairwise-Sorting}-Netzwerks berechnet, ist tabellarisch in
2605 Tabelle~\ref{tbl:ec-ps-efficiency} dargestellt.
2609 \rowcolors{2}{black!5}{}
2610 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2612 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2614 9 & 20 & & & & & & & & & & & & & & & \\
2615 10 & 20 & 27 & & & & & & & & & & & & & & \\
2616 11 & 20 & 28 & 32 & & & & & & & & & & & & & \\
2617 12 & 20 & 28 & 32 & 38 & & & & & & & & & & & & \\
2618 13 & 19 & 27 & 31 & 37 & 41 & & & & & & & & & & & \\
2619 14 & 19 & 27 & 31 & 37 & 41 & 48 & & & & & & & & & & \\
2620 15 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & & & & & & & & & \\
2621 16 & 19 & 27 & 31 & 37 & 41 & 48 & 53 & 59 & & & & & & & & \\
2622 17 & 21 & 29 & 32 & 39 & 43 & 51 & 57 & 64 & 68 & & & & & & & \\
2623 18 & 22 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & & & & & & \\
2624 19 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & & & & & \\
2625 20 & 23 & 29 & 32 & 39 & 43 & 52 & 58 & 65 & 69 & 80 & 88 & 97 & & & & \\
2626 21 & 20 & 30 & 34 & 38 & 44 & 51 & 57 & 64 & 74 & 82 & 87 & 96 & 102 & & & \\
2627 22 & 20 & 30 & 34 & 38 & 46 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & & \\
2628 23 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 66 & 72 & 83 & 89 & 97 & 102 & 112 & 119 & \\
2629 24 & 20 & 27 & 34 & 38 & 42 & 51 & 57 & 64 & 72 & 82 & 89 & 96 & 102 & 112 & 119 & 127 \\
2631 \ps{m}&19 & 27 & 32 & 38 & 42 & 48 & 53 & 59 & 63 & 79 & 88 & 97 & 103 & 112 & 119 & 127 \\
2635 \caption{Anzahl der Komparatoren der Ergebnisse von
2636 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2637 \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
2638 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
2639 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2641 \label{tbl:ec-ps-efficiency}
2644 % Beispiel Effizienz
2646 Zwei Ergebnisse, die effizienter als die entsprechenden
2647 \emph{Pairwise-Sorting}-Netzwerke sind, zeigt
2648 Abbildung~\ref{fig:ec-ps-efficient_networks}. Sie erreichen die
2649 Geschwindigkeit und Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks mit der
2650 entsprechenden Leitungszahl. Bei größeren Netzwerken, beispielsweise $m = 19$,
2651 ist dies mit der in Tabelle~\ref{tbl:ec-ps-efficiency} dargestellten Größe der
2652 Schnittmuster noch nicht zu beobachten.
2656 \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 10~Schichten. Das
2657 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
2658 \emph{Pairwise-Sorting}-Netzwerk \ps{13}
2659 erzeugt.]{\input{images/11-ec-from-ps13.tex}}
2660 \subfigure[12-Sortiernetzwerk aus 41~Komparatoren in 10~Schichten. Das
2661 Netzwerk wurde von \textsc{SN-Evolution-Cut} aus dem
2662 \emph{Pairwise-Sorting}-Netzwerk \ps{16}
2663 erzeugt.]{\input{images/12-ec-from-ps16.tex}}
2664 \caption{Zwei effiziente Sortiernetzwerke, die durch Schnittmuster, die von
2665 \emph{SN-Evolution-Cut} berechnet wurden, aus dem
2666 \emph{Pairwise-Sorting}-Netzwerk \ps{n} erzeugt wurden.}
2667 \label{fig:ec-ps-efficient_networks}
2670 % Wie viele Schnitte man braucht.
2672 Bei welchen Parametern \textsc{SN-Evolution-Cut} effiziente
2673 19-Sortiernetzwerke findet, ist Tabelle~\ref{tbl:ec-ps-19} zu entnehmen. Für
2674 $n = 31$, $k = 12$ und $n = 32$, $k = 13$ werden 19-Sortiernetzwerke mit der
2675 selben Effizienz und Geschwindigkeit wie \oes{19} erzeugt. Das
2676 19-Sortiernetzwerk, das auf diese Art und Weise aus \ps{32} erzeugt wurde, ist
2677 in Abbildung~\ref{fig:19-ec-from-ps32} dargestellt.
2681 \rowcolors{2}{black!5}{}
2682 \begin{tabular}{|r|r|r|}
2684 $n$ & Komp. & Schichten \\
2697 \rowcolor{green!10!white!95!black}
2708 \ps{19} & 97 & 15 \\
2709 \oes{19} & 91 & 14 \\
2713 \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die
2714 von \textsc{SN-Evolution-Cut} aus \ps{n}, $n = 20, \dots, 38$ erzeugt
2716 \label{tbl:ec-ps-19}
2721 \input{images/19-ec-from-ps32.tex}
2723 \caption{Sortiernetzwerk mit 19~Leitungen und 91~Komparatoren in
2724 14~Schichten. Das Netzwerk wurde von dem Algorithmus
2725 \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
2726 $\operatorname{PS}(32)$ erzeugt.}
2727 \label{fig:19-ec-from-ps32}
2730 An den Daten in Tabelle~\ref{tbl:ec-ps-19} fällt auf, dass die Effizienz und
2731 Geschwindigkeit der Ergebnisse für $n > 32$ schlechter werden. Das
2732 \emph{Pairwise-Sorting}-Netzwerk ist Leitungszahlen, die Zweierpotenzen sind,
2733 besonders effizient und schnell. Um der Vermutung nachzugehen, dass der
2734 \textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente
2735 Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1
2736 \dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32}
2741 \rowcolors{2}{black!5}{}
2742 \begin{tabular}{|r|r|r|}
2744 $m$ & Komp. & Schichten \\
2765 \caption{Anzahl der Komparatoren und Schichten von $m$-Sortiernetzwerken,
2766 die von \textsc{SN-Evolution-Cut} nach 5.000.000 Iterationen aus \ps{32}
2768 \label{tbl:ec-ps-32}
2773 Die Schnittmuster, die \textsc{SN-Evolution-Cut} für das
2774 \emph{Pairwise-Sorting}-Netzwerk berechnet, können zu schnelleren
2775 Sortiernetzwerken als \ps{m} führen. Beispielsweise konnte aus \ps{24} ein
2776 18-Sortiernetzwerk erzeugt werden, das mit 13~Schichten zwei parallele
2777 Schritte im Vergleich zu \ps{18} einspart. Eine Darstellung dieses
2778 Sortiernetzwerks befindet sich in Abbildung~\ref{fig:18-ec-from-ps24}. Für
2779 andere $m$ wurde die Geschwindigkeit des \emph{Pairwise-Sorting}-Netzwerks
2780 nicht übertroffen und im Fall von $m = 16$ wurde die Geschwindigkeit nicht
2785 \rowcolors{2}{black!5}{}
2786 \begin{tabular}{|r|rrrrrrrrrrrrrrrr|}
2788 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\
2790 9 & 6 & & & & & & & & & & & & & & & \\
2791 10 & 6 & 10 & & & & & & & & & & & & & & \\
2792 11 & 6 & 9 & 10 & & & & & & & & & & & & & \\
2793 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\
2794 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\
2795 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\
2796 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\
2797 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\
2798 17 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & & & & & & & \\
2799 18 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & & & & & & \\
2800 19 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & & & & & \\
2801 20 & 7 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 11 & 15 & 15 & 15 & & & & \\
2802 21 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 15 & 15 & 15 & & & \\
2803 22 & 6 & 8 & 9 & 10 & 10 & 11 & 11 & 11 & 12 & 14 & 14 & 15 & 15 & 15 & & \\
2804 23 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 14 & 14 & 15 & 15 & 15 & \\
2805 24 & 6 & 9 & 9 & 10 & 10 & 10 & 11 & 11 & 11 & 13 & 13 & 14 & 14 & 15 & 15 & 15 \\
2807 \ps{m} & 6 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 15 & 15 & 15 & 15 & 15 & 15 & 15 \\
2811 \caption{Anzahl der Schichten der Ergebnisse von
2812 \textsc{SN-Evolution-Cut} mit verschiedenen Größen des
2813 \emph{Pairwise-Sorting}-Netzwerks und unterschiedlichen Werten für~$k$.
2814 Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede
2815 Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des
2817 \label{tbl:ec-ps-speed}
2820 % Beispiel Geschwindigkeit
2824 \input{images/18-ec-from-ps24.tex}
2826 \caption{Sortiernetzwerk mit 18~Leitungen und 89~Komparatoren in
2827 13~Schichten. Das Netzwerk wurde von dem Algorithmus
2828 \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting}-Netzwerk
2829 $\operatorname{PS}(24)$ erzeugt.}
2830 \label{fig:18-ec-from-ps24}
2835 Die Ergebnisse, die \textsc{SN-Evolution-Cut} erzielte, wenn das gegebene
2836 Sortiernetzwerk das \emph{bitone Mergesort}-Netzwerk war
2837 (Abschnitt~\ref{sect:sn-evolution-cut:bs}), waren sehr wirr. Beispielsweise
2838 ist bei dem Netzwerk in Abbildung~\ref{fig:32-ec-from-bs64} nicht ersichtlich,
2839 wie und warum es jede beliebige Eingabe sortiert.
2841 Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet
2842 man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
2843 16~Leitungen zu entfernen, kann der Algorithmus ein Sortiernetzwerk
2844 zurückgeben, das die gleiche Anzahl Komparatoren und Schichten wie
2845 $\operatorname{PS}(16)$ und $\operatorname{OES}(16)$ hat. Eines dieser
2846 Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
2847 Dieses Ergebnis demonstriert, dass sich die Ergebnisse in den gezeigten
2848 Tabellen oft durch zusätzliche Iterationen verbessern lassen.
2852 \input{images/16-ec-from-ps32.tex}
2854 \caption{Sortiernetzwerk mit 16~Leitungen und 63~Komparatoren in
2855 10~Schichten. Das Netzwerk wurde von dem Algorithmus
2856 \textsc{SN-Evolution-Cut} aus dem \emph{Pairwise-Sorting-Netzwerk}
2857 $\operatorname{PS}(32)$ durch 16~Schnitte erzeugt.}
2858 \label{fig:16-ec-from-ps32}
2861 Obwohl das \emph{Pairwise-Sorting}-Netzwerk den \emph{Odd-Even}-Mischer nicht
2862 einsetzt und auch nicht auf einem Mischer basiert, ist das
2863 \emph{Odd-Even-Merge}-Netzwerk $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in
2864 Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In
2865 den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die
2866 strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die
2867 Schichten~1 und~2 sowie 4~und~5 sind vertauscht.
2871 \input{images/32-pairwise-cut-16-pairwise.tex}
2873 \caption{Das \ps{32}-Netzwerk mit 8~Maximum- und 8~Minimumschnitten. Gut zu
2874 sehen sind die verbleibenden Komparatoren, die das \ps{16}-Netzwerk
2876 \label{fig:ps16-from-ps32}
2879 Für das \emph{Pairwise-Sorting-Netzwerk} ist es vergleichsweise einfach
2880 regelmäßige Schnittmuster anzugeben, die aus dem Netzwerk ein kleineres
2881 schnelles und effizientes Sortiernetzwerk erzeugen. Beispielsweise führt das
2882 einfache Schnittmuster
2884 \textit{Eingang}_i = \left\{ \begin{array}{rl}
2885 -\infty & \quad \textrm{falls } i < \frac{1}{4} n \\
2886 \infty & \quad \textrm{falls } i \geqq \frac{3}{4} n \\
2887 ? & \quad \mathrm{sonst}
2890 für $\operatorname{PS}\left(n = 2^d\right)$ zum Sortiernetzwerk
2891 $\operatorname{PS}\left(\frac{1}{2}n\right)$. Die Art und Weise, mit der
2892 dieses Schnittmuster Komparatoren eliminiert und welche Komparatoren das
2893 verbleibende Netzwerk ausmachen, ist in Abbildung~\ref{fig:ps16-from-ps32}
2894 dargestellt. Die matt blauen und roten Leitungen und Komparatoren sind
2895 diejenigen, die Aufgrund eines Minimums oder eines Maximums im resultierenden
2896 Netzwerk nicht mehr enthalten sind. Da die Minima und Maxima bereits auf den
2897 „richtigen“ Leitungen angelegt werden, müssen keine Leitungen vertauscht
2898 werden und das Ergebnis ist bereits normalisiert. Daher ist das resultierende
2899 Netzwerk in schwarz gut zu erkennen.
2903 \input{images/16-pairwise.tex}
2905 \caption{Das $\operatorname{PS}(16)$-Sortiernetzwerk mit 8~Schnitten
2906 ($\operatorname{MIN}(0, 2, 4, 6), \operatorname{MAX}(9, 11, 13, 15)$). Das
2907 resultierende 8-Sortiernetzwerk ist $\operatorname{OES}(8)$.}
2908 \label{fig:16-pairwise}
2911 Ein Spezialfall ergibt sich, wenn \textsc{SN-Evolution-Cut} auf
2912 $\operatorname{PS}(16)$ angewendet wird: In diesem Fall kann ein
2913 8-Schnittmuster ausgegeben werden, das \emph{Odd-Even-Mergesort}-Netzwerk
2914 \oes{8} aus \ps{16} erzeugt.. Für größere Sortiernetzwerke ist dies hingegen
2915 nicht mehr möglich, beispielsweise kann $\operatorname{PS}(32)$ nicht durch
2916 ein 16-Schnittmuster in \oes{16} konvertiert werden. Die Verwandtschaft von
2917 $\operatorname{PS}(n)$ und \oes{n} untersucht \textit{Moritz Mühlenthaler}
2918 ausführlich in~\cite{M2009}.
2921 \section{Fazit und Ausblick}
2923 Mit dem Entfernen von Leitungen aus bekannten Sortiernetzwerken lassen sich
2924 interessante Ergebnisse erzielen. Dies zeigte \textit{Moritz Mühlenthaler}
2925 bereits in~\cite{M2009}. Die in dieser Arbeit vorgestellten Methoden und
2926 Resultate machen deutlich, dass sich mit diesem Verfahren noch weitere
2927 interessante Beobachtungen machen lassen.
2929 Das \emph{Odd-Even-Mergesort}-Netzwerk wird sowohl von \textsc{SN-Evolution},
2930 \textsc{SN-Evolution-Cut} und \textsc{SN-Markov} erreicht. Wenn die Anzahl der
2931 Leitungen keine Zweierpotenz ist, kann gegebenenfalls ein schnelleres
2932 Sortiernetzwerk erzeugt werden. Einige Beispiele hierfür wurden in
2933 Abschnitt~\ref{sect:sn-evolution-cut:oes} aufgezeigt.
2935 Das \emph{bitone Mergesort}-Netzwerk kann in Bezug auf Effizienz von den
2936 vorgestellten Algorithmen übertroffen werden. Der Algorithmus
2937 \textsc{SN-Evolution-Cut} kann das Ergebnis von \textit{Mühlenthaler} und
2938 \textit{Wanka} (\cite{MW2010}) für ein 16-Sortiernetzwerk reproduzieren und
2939 für ein 32-Sortiernetzwerk sogar noch übertreffen. Der
2940 \textsc{SN-Evolution}-Algorithmus fand 16-Sortiernetzwerke, die gegenüber dem
2941 Ergebnis von \textsc{SN-Evolution-Cut} beziehungsweise~\cite{MW2010} einen
2942 weiteren Komparator einsparen.
2944 Leider weisen die Sortiernetzwerke, die von den angegebenen Algorithmen
2945 zurückgegeben werden, keine Struktur auf, die sich zur Angabe einer
2946 Konstruktionsanweisung eigenen würde. Für das \emph{Pairwise-Sorting}- und das
2947 \emph{Odd-Even-Mergesort}-Netzwerk mit Zweierpotenzen als Leitungszahl wurden
2948 regelmäßige Schnittmuster angegeben. Diese ergeben Sortiernetzwerke, die so
2949 schnell und effizient sind wie die vergleichbaren \oes{n} und \ps{n}
2952 Die Anzahl der \emph{unterschiedlichen} Schnitte von verschiedenen
2953 Sortiernetzwerken wurde experimentell bestimmt und gezeigt, dass es deutlich
2954 weniger \emph{unterschiedliche} als \emph{mögliche} Schnittmuster gibt. Das
2955 bedeutet im Umkehrschluss, dass die gewonnenen Sortiernetzwerke mit mehreren
2956 Schnittmustern erreicht werden können.
2958 Die Möglichkeiten der Optimierung von Sortiernetzwerken mit
2959 \emph{Evolutionären Algorithmen} sind durch die in dieser Arbeit vorgestellten
2960 Herangehensweisen bei weitem nicht erschöpft. Im Folgenden werden Ansätze
2961 umrissen, mit denen an die Untersuchungen in dieser Arbeit nahtlos angeknüpft
2964 \subsection{Ausblick: Das \textit{Pairwise-Sorting}-Netzwerk und \textsc{SN-Evolution}}
2966 Die aktuelle Implementierung von \textsc{SN-Evolution}
2967 (Abschnitte~\ref{sect:sn-evolution}
2968 beziehungsweise~\ref{sect:implementierung}) kann sowohl den \emph{bitonen
2969 Mischer} als auch den \emph{Odd-Even}-Mischer verwenden, um zwei Individuen zu
2970 rekombinieren. Das \emph{Pairwise-Sorting}-Netzwerk verwendet zwar keinen
2971 Mischer, es ist aber ebenfalls rekursiv über kleinere Versionen von sich
2972 selbst definiert. Das heißt, dass \ps{n} aus zwei Instanzen von
2973 $\ps{\frac{n}{2}}$ und zusätzlichen Komparatoren besteht, die die Eingabe für
2974 die kleineren Sortiernetzwerke vorbereiten und anschließend für eine sortierte
2975 Ausgabe sorgen. Anstelle von $\ps{\frac{n}{2}}$ können beliebige
2976 Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwendet werden.
2978 Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu
2979 rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele
2980 \emph{unterschiedliche} Schnittmuster gibt
2981 (Abschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die
2982 Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider
2983 wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine
2984 $n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren
2985 $n$-Sortiernetzwerken als \ps{n} führen.
2987 \subsection{Ausblick: Kooperation von \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut}}
2989 Ähnlich zu der parasitären \emph{Co-Evolution}, die \textit{W.~Daniel Hillis}
2990 in~\cite{H1990} beschreibt, könnte man versuchen, die Algorithmen
2991 \textsc{SN-Evolution} und \textsc{SN-Evolution-Cut} zu kombinieren. Nach dem
2992 Zusammenfügen von zwei $n$-Sortiernetzwerken könnte der Algorithmus
2993 \textsc{SN-Evolution-Cut} beispielsweise einen möglichst guten Schnitt für
2994 \emph{dieses} Netzwerk ermitteln. Da sich die Lösungen, die Evolutionäre
2995 Algorithmen in ihre Population aufnehmen, in den ersten Schritten rasch
2996 verbessern, könnten selbst weniger Iterationen von \textsc{SN-Evolution-Cut}
2997 die Zwischenlösungen von \textsc{SN-Evolution} deutlich verbessern.
2999 Alternativ könnte man -- analog zur Herangehensweise von \textit{Hillis} --
3000 eine zweite Population von Schnittmustern evolvieren, die für die
3001 Sortiernetzwerke in der Population von \textsc{SN-Evolution} besonders gut
3002 funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge
3003 Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten
3004 Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster
3005 eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses}
3006 Schnittmuster zur nächsten Generation beiträgt. Im Gegensatz zum Ansatz der
3007 parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die
3008 das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern
3012 \section{Implementierung}
3013 \label{sect:implementierung}
3015 Alle in dieser Arbeit beschriebenen Versuche wurden mit einer eigens
3016 entwickelten C-Bibliothek, \textit{libsortnetwork}, und zugehörigen
3017 Kommandozeilen-Programmen durchgeführt. Die Bibliothek wurde unter der
3018 \textit{GNU Lesser General Public License} (LGPL) in der Version~2.1
3019 veröffentlicht; die Kommandozeilen-Programme, die in vielen Fällen lediglich
3020 Funktionalität der Bibliothek auf der Kommandozeile zur Verfügung stellen,
3021 stehen unter der \textit{GNU General Public License}, Version~2. Diese
3022 Lizenzen räumen einem Benutzer weitreichende Rechte ein, unter anderem das
3023 Programm beliebig zu verwenden, zu studieren, zu verändern sowie veränderte
3024 und unveränderte Kopien zu veröffentlichen.
3026 Die Programmierschnittstelle (API) der Bibliothek orientiert sich an
3027 Paradigmen der \textit{objektorientierten Programmierung}. Beispielsweise kann
3028 mit der Funktion \texttt{sn\_network\_ create()} ein neues Zustands-Objekt
3029 erzeugt werden, für das mehrere Manipulations-Methoden, zum Beispiel
3030 \texttt{sn\_network\_comparator\_add()}, zur Verfügung stehen. Auf diese Art
3031 und Weise kann die Bibliothek leicht erweitert werden, ohne dass bestehende
3032 Programme angepasst werden müssen.
3034 Die meisten Kommandozeilen-Programmen lesen ein Komparatornetzwerk von der
3035 Standard-Eingabe und schreiben ihr Ergebnis auf die Standard-Ausgabe. Um
3036 Beispielsweise eine \emph{normalisierte} Variante des \emph{bitonen
3037 Mergesort}-Netzwerks \bs{42} zu erzeugen, kann folgendes Kommando verwendet
3040 $ sn-bitonicsort 42 | sn-normalize >sn-42
3042 Dieses Prinzip, kleine Programme \emph{eine} Aufgabe erledigen zu lassen und
3043 es einfach zu ermöglichen, Programme zu verketten, ist eines der
3044 Grundprinzipien des UNIX-Be\-triebs\-sys\-tems. Es hat sich in den letzten
3045 Jahrzehnten und beim Verfassen dieser Arbeit als sehr flexibel und mächtig
3048 Funktionen, die von Kommandozeilen-Programmen zur Verfügung gestellt werden,
3049 sind unter anderem das Erzeugen des \emph{Odd-Even-Mergesort}-, \emph{bitonen
3050 Mergesort}- und \emph{Pairwise-Sorting}-Netzwerks, das Normalisieren von
3051 Sortiernetzwerken, Anwendung von Schnittmustern auf Sortiernetzwerke und
3052 Anwendung eines Komparatornetzwerks auf eine Eingabepermutation. Das
3053 Darstellen von Sortiernetzwerken wird ebenfalls angeboten, beispielsweise
3054 wurden die Sortiernetzwerke in dieser Arbeit mit dem Kommando \texttt{sn-tex}
3057 \textit{libsortnetwork} kann unter der Web-Adresse
3058 \url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden.
3061 \bibliography{references}
3062 \bibliographystyle{plain}
3068 % vim: set shiftwidth=2 softtabstop=2 tabstop=8 fdm=marker tw=78 spelllang=de :