From 3968b300fe8f2ed000d177f6783b5adec6072bad Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Mon, 28 Feb 2011 08:51:30 +0100 Subject: [PATCH] SN-Evolution-Cut: BS: Beispiel-Netzwerke verschoben. --- diplomarbeit.tex | 42 +++++++++++++++++++++++++++--------------- 1 file changed, 27 insertions(+), 15 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 9eb0467..7f9cb23 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1930,6 +1930,8 @@ $k$-Schnittmuster als auch das $m$-Sortiernetzwerk als Ausgabe von \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk} \label{sect:sn-evolution-cut:bs} +% Effizienz + Wenn der \textsc{SN-Evolution-Cut}-Algorithmus mit dem \emph{bitonen Mergesort}-Netzwerk \bs{n} gestartet wird und $k$~Leitungen entfernen soll, ergeben die gefundenen Schnittmuster in vielen Fällen effizientere Netzwerke @@ -1939,6 +1941,8 @@ Sortiernetzwerk mit 67~Komparatoren, 13~Komparatoren weniger als \bs{16} benötigt. Eines der Sortiernetzwerke, die auf diese Art und Weise generiert wurde, ist in Abbildung~\ref{fig:16-ec-from-bs22} zu sehen. +% Beispiel Effizienz + \begin{figure} \begin{center} \input{images/16-ec-from-bs22.tex} @@ -2014,21 +2018,7 @@ Bei anderen Größen ergeben erst größere~$k$ effiziente Sortiernetzwerke, beispielsweise bei $m = 10$: erst für $n = 18$, $k = 8$ wird ein Sortiernetzwerk mit 31~Komparatoren gefunden. -\begin{figure} - \centering - \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das - 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}} - \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das - 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}} - \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das - 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}} - \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das - 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}} - \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11, - 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke - erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.} - \label{fig:ec-bs-fast_networks} -\end{figure} +% Geschwindigkeit Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der \textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als @@ -2080,6 +2070,24 @@ schnelle Sortiernetzwerke erzeugen. Beispiele für schnelle Sortiernetzwerke, die mit den von \textsc{SN-Evolution-Cut} ausgegebenen Schnittmustern erzeugt werden können, sind in Abbildung~\ref{fig:ec-bs-fast_networks} dargestellt. +% Beispiel Geschwindigkeit + +\begin{figure} + \centering + \subfigure[10-Sortiernetzwerk aus 31~Komparatoren in 8~Schichten. Das + 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}} + \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das + 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}} + \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das + 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}} + \subfigure[19-Sortiernetzwerk aus 92~Komparatoren in 13~Schichten. Das + 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}} + \caption{Für einige Ziel-Leitungszahlen, unter anderem $m \in \{10, 11, + 12, 19\}$, kann der \textsc{SN-Evolution-Cut}-Algorithmus Sortiernetzwerke + erzeugen, die \emph{schneller} und \emph{effizienter} als \bs{m} sind.} + \label{fig:ec-bs-fast_networks} +\end{figure} + Bei der Betrachtung der Effizienz wurde festgestellt, dass oft schon das Entfernen einer einzigen Leitung zu eines effizienteren Ergebnis als \bs{m} führt. Bei der Geschwindigkeit ist die Anzahl der Leitungen, die entfernt @@ -2089,6 +2097,8 @@ einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise noch größer gewählt werden. +% Detaillierte Betrachtung fuer m = 19 + Die Effizienz und Geschwindigkeit der Sortiernetzwerke, die von \textsc{SN-Evolution-Cut} aus dem \emph{bitonen Mergesort}-Netzwerk erzeugten werden, ist für $m = 19$ und $n = 20 \dots 38$ ($k = 1 \dots 19$) in @@ -2145,6 +2155,8 @@ Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen. \label{tbl:ec-bs-19} \end{table} +% 2-er Potenz + \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, wie ein \emph{bitoner Mischer} $\bm{n = 2^d}$, der nach Batchers Methode konstruiert wurde, durch systematisches Entfernen von Leitungen in einen -- 2.11.0