From 8cb536c55ae5c681bfe6bf297da5c5aaae4337fe Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Mon, 13 Dec 2010 16:09:19 +0100 Subject: [PATCH] Abschnitt "Leitungen entfernen": Verweis auf Moritz und Rolfs Arbeit. --- diplomarbeit.tex | 23 ++++++++++++++++++++++- 1 file changed, 22 insertions(+), 1 deletion(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 023c710..2ed7e38 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -654,12 +654,33 @@ Das Programm {\sc SN-Evolution-Cut} implementiert einen evolutionären Algorithmus, der zu einem gegebenen Sortiernetzwerk und einer gewünschten Leitungszahl ein Schnittmuster sucht, dass ein Sortiernetzwerk mit einer möglichst geringen Anzahl von Komparatoren und Schichten ergibt. Zur Bewertung -von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. +von Sortiernetzwerken siehe auch Abschnitt~\ref{sect:bewertung}. Mit diesem +Algorithmus wurden zu einer Reihe von „interessanten“ Netzwerken möglichst +gute Schnittmuster gesucht. + +In ihrer Arbeit “Improving Bitonic Sorting by Wire Elimination” zeigen Moritz +Mühlenthaler und Rolf Wanka, wie man einen bitonen Mischer, der nach Batchers +Methode konstruiert wurde, durch systematisches Entfernen von Leitungen in +einen ebenfalls bitonen Mischer mit der Hälfte der Leitungen transformiert. +Diese alternativen Mischer sparen im Vergleich zu den Mischern, die nach +Batchers Methode konstruiert werden, Komparatoren ein. + +Beispeilsweise geben Mühlenthaler und Wanka ein Sortiernetzwerk mit +16~Eingängen an, das mithilfe der alternativen Mischer konstruiert wurde. +Dieses Sortiernetzwerk benötigt 68~Komparatoren, 12~weniger als das +bitone Mergesort-Netzwerk nach Batchers Methode. + +Startet man {\sc SN-Evolution-Cut} mit dem bitonen Mergesort-Netzwerk +$\operatorname{BS}(32)$ und der Vorgabe 16~Leitungen zu entfernen, liefert der +Algorithmus Sortiernetzwerke, die ebenfalls aus 68~Komparatoren bestehen. Ein +16-Sortiernetzwerk, das auf diese Weise generiert wurde, ist in +Abbildung~\ref{fig:16-ec-1277186619} zu sehen. \begin{itemize} \item Beispiel: Moritz und Rolfs Optimierung für Bitonic-Sort. \item Wie gut kann man durch wegschneiden werden? \item Wieviele Schnitte ergeben das selbe Netzwerk? + \item Abschnitt „Optimierung der Schnitte“ hier einbauen. \end{itemize} \section{Der evolutionäre Ansatz} -- 2.11.0