From 204f0ead4d1ccbd87c678cf8c35a4c781781d594 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Sat, 19 Mar 2011 09:48:48 +0100 Subject: [PATCH] Weitere ToDos abgearbeitet. --- diplomarbeit.tex | 45 ++++++++++++++++++++------------------------- references.bib | 28 ++++++++++++++++++++++++++-- 2 files changed, 46 insertions(+), 27 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index e9203fb..a58d629 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -280,13 +280,13 @@ Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig -- 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} @@ -846,23 +846,14 @@ Batcher} zeigt in~\cite{B1968}, dass in diesem Fall \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} @@ -1264,8 +1255,12 @@ die bei Sortiernetzwerken verfolgt werden können: \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} @@ -1333,7 +1328,7 @@ Bewertungsfunktion verwendet. Die Werte 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} diff --git a/references.bib b/references.bib index 20a37c5..0c36103 100644 --- a/references.bib +++ b/references.bib @@ -1,7 +1,7 @@ @inproceedings{MW2010, Author = {Moritz Mühlenthaler and Rolf Wanka}, Title = {Improving Bitonic Sorting by Wire Elimination}, - Booktitle = {Proc. 23rd PARS-Workshop on Parallel Systems and Architectures of the 23rd Int. Conf. on Architecture of Computing Systems (ARCS)}, + Booktitle = {Proc. 23rd PARS-Workshop on Parallel Systems and Architectures of the 23rd International Conference on Architecture of Computing Systems (ARCS)}, Year = 2010, ISBN = {978-3-8007-3222-7}, Pages = {15--22}, @@ -81,7 +81,7 @@ @InProceedings{J1995, author = {Hugues Juillé}, title = {Evolution of Non-Deterministic Incremental Algorithms as a New Approach for Search in State Space}, - booktitle = {Proc. 6th Int. Conf. on Genetic Algorithms (ICGA)}, + booktitle = {Proc. 6th International Conference on Genetic Algorithms (ICGA)}, pages = {351--358}, year = 1995 } @@ -113,3 +113,27 @@ Publisher = {Teubner Verlag}, Address = {Wiesbaden} } + +@InProceedings{G1972, + author = {M.~W. Green}, + title = {Some improvements in non-adaptive sorting algorithms}, + booktitle = {Proc. 6th Princeton Conference on Information Sciences and Systems (CISS)}, + pages = {387--391}, + year = 1972 +} + +@inproceedings{V1974, + author = {David C. Van Voorhis}, + title = {An economical construction for sorting networks}, + booktitle = {Proceedings of the May 6--10, 1974, national computer conference and exposition}, + series = {AFIPS '74}, + year = {1974}, + location = {Chicago, Illinois}, + pages = {921--927}, + numpages = {7}, + url = {http://doi.acm.org/10.1145/1500175.1500347}, + doi = {http://doi.acm.org/10.1145/1500175.1500347}, + acmid = {1500347}, + publisher = {ACM}, + address = {New York, NY, USA} +} -- 2.11.0