-- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt.
Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch
bereits etwa 4,3~Milliarden Tests notwendig, die einen Rechner durchaus
-mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im
+mehrere Stunden beschäftigen. Das ist deshalb problematisch, weil die im
Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende
Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines
-Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million
-Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
-auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden
-für einen Lauf benötigt.
+Zwischenergebnisses drei Stunden in Anspruch nimmt, sind für eine Million
+Iterationen etwa 340~Jahre Rechenzeit notwendig. Selbst wenn die Berechnung
+auf 1000~Computern mit je 4~Prozessoren verteilt wird, wird etwa ein Monat für
+einen Lauf benötigt.
\subsubsection{Evolutionäre Algorithmen}
"`Mischer"' in der Literatur sehr weit verbreitet ist, werden diese Begriffe
in dieser Arbeit trotzdem verwendet.}, bilden die Grundlage für die
beschriebenen evolutionären Algorithmen beziehungsweise dienen als initiale
-Eingabe. Im Folgenden werden daher vier Konstruktionsverfahren vorgestellt.
-
-\todo{Drei oder vier Verfahren? Sprich: Mit oder ohne Pairwise Sorting.}
+Eingabe. Im Folgenden werden daher drei Konstruktionsverfahren vorgestellt.
\subsection{Das Odd-Even-Transpositionsort-Netzwerk}
\label{sect:odd_even_transpositionsort}
\end{displaymath}
gilt.
-% gnuplot:
-% oem(n,m) = ((n*m) <= 1) ? (n*m) : oem(ceil(.5*n), ceil(.5*m)) + oem(floor(.5*n), floor(.5*m)) + floor(.5*(n+m-1.0))
-% oem1(n) = oem(ceil(.5*n),floor(.5*n))
-% oes(n) = (n <= 1.0) ? 0 : oes(ceil(0.5*n)) + oes(floor(0.5*n)) + oem1(n)
-
-%\begin{itemize}
-%\item Pairwise sorting-network
-%\end{itemize}
-
-\subsection{Das Pairwise-Sorting-Netzwerk}
-
-Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
-für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
-Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
-Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
-\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
-das \emph{Odd-Even-Mergesort}-Netzwerk.
+%\subsection{Das Pairwise-Sorting-Netzwerk}
+%
+%Das \emph{Pairwise-Sorting}-Netzwerk \ps{n} ist eine Konstruktionsvorschrift
+%für Sortiernetzwerke, die 1992 von \textit{Ian Parberry} in seiner Arbeit „The
+%Pairwise Sorting Network“ \cite{P1992} definiert wurde. Wenn die Anzahl der
+%Leitungen $n = 2^d$ eine Zweierpotenz ist, hat das
+%\emph{Pairwise-Sorting}-Netzwerk die selbe Effizienz und Geschwindigkeit wie
+%das \emph{Odd-Even-Mergesort}-Netzwerk.
\newpage
\section{Transformation von Sortiernetzwerken}
\begin{figure}
\centering
- \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
- \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
+ \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das
+ Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in~\cite{G1972}
+ veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}}
+ \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das
+ Netzwerk wurde von \textit{D. Van~Voorhis} 1974 in~\cite{V1974}
+ veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}}
\caption{Das effizienteste und das schnellste Sortiernetzwerk für
16~Leitungen, das derzeit bekannt ist.}
\label{fig:16-best-known}
w_{\mathrm{Schichten}} &=& 1
\end{eqnarray*}
geben dem Einsparen eines Komparators ein höheres Gewicht als dem Einsparen
-einer Schicht. \todo{Fehler hier noch was?}
+einer Schicht.
\subsection{Selektion}
\textsc{SN-Evolution-Cut}-Algorithmus für $\ps{n = 2^d}$ besonders effiziente
Schnittmuster findet, wurde \textsc{SN-Evolution-Cut} mit \ps{32} und $k = 1
\dots 16$ gestartet. Die Ergebnisse sind in Tabelle~\ref{tbl:ec-ps-32}
-zusammengefasst. \todo{Tabelle einfügen.}
+zusammengefasst.
+
+\begin{table}
+ \begin{center}
+ \rowcolors{2}{black!5}{}
+ \begin{tabular}{|r|r|r|}
+ \hline
+ $m$ & Komp. & Schichten \\
+ \hline
+ 16 & 69 & 11 \\
+ 17 & 77 & 13 \\
+ 18 & 89 & 13 \\
+ 19 & 91 & 14 \\
+ 20 & 97 & 14 \\
+ 21 & 107 & 15 \\
+ 22 & 114 & 15 \\
+ 23 & 122 & 15 \\
+ 24 & 127 & 15 \\
+ 25 & 138 & 15 \\
+ 26 & 146 & 15 \\
+ 27 & 155 & 15 \\
+ 28 & 161 & 15 \\
+ 29 & 171 & 15 \\
+ 30 & 178 & 15 \\
+ 31 & 186 & 15 \\
+ \hline
+ \end{tabular}
+ \end{center}
+ \caption{Anzahl der Komparatoren und Schichten von $m$-Sortiernetzwerken,
+ die von \textsc{SN-Evolution-Cut} nach 5.000.000 Iterationen aus \ps{32}
+ erzeugt wurden.}
+ \label{tbl:ec-ps-32}
+\end{table}
% Geschwindigkeit
Bei dem \emph{Pairwise-Sorting}-Netzwerk $\ps{n=2^d}$ ist das anders. Startet
man \textsc{SN-Evolution-Cut} mit $\operatorname{PS}(32)$ und der Vorgabe,
-16~Leitungen zu entfernen, erhält man ein Sortiernetzwerk, das die gleiche
-Anzahl Komparatoren und Schichten hat wie $\operatorname{PS}(16)$ und
-$\operatorname{OES}(16)$. Eines dieser Sortiernetzwerke ist in
-Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+16~Leitungen zu entfernen, kann der Algorithmus ein Sortiernetzwerk
+zurückgeben, das die gleiche Anzahl Komparatoren und Schichten wie
+$\operatorname{PS}(16)$ und $\operatorname{OES}(16)$ hat. Eines dieser
+Sortiernetzwerke ist in Abbildung~\ref{fig:16-ec-from-ps32} dargestellt.
+Dieses Ergebnis demonstriert, dass sich die Ergebnisse in den gezeigten
+Tabellen oft durch zusätzliche Iterationen verbessern lassen.
\begin{figure}
\begin{center}
\label{fig:16-pairwise}
\end{figure}
-Ein Spezialfall ergibt sich, wenn man \textsc{SN-Evolution-Cut} auf
-$\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein
-8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für
-größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise
-kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16}
-konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n}
-untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}.
+Ein Spezialfall ergibt sich, wenn \textsc{SN-Evolution-Cut} auf
+$\operatorname{PS}(16)$ angewendet wird: In diesem Fall kann ein
+8-Schnittmuster ausgegeben werden, das \emph{Odd-Even-Mergesort}-Netzwerk
+\oes{8} aus \ps{16} erzeugt.. Für größere Sortiernetzwerke ist dies hingegen
+nicht mehr möglich, beispielsweise kann $\operatorname{PS}(32)$ nicht durch
+ein 16-Schnittmuster in \oes{16} konvertiert werden. Die Verwandtschaft von
+$\operatorname{PS}(n)$ und \oes{n} untersucht \textit{Moritz Mühlenthaler}
+ausführlich in~\cite{M2009}.
\newpage
\section{Fazit und Ausblick}
projects / diplomarbeit.git / blobdiff