X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=6a41d91e6045cd6897de754c9147bf4a58828404;hb=bf0bcc6509eb1c677b419cb8fdf655145950ec93;hp=03be0ac8394252c14d38a6cd25a5887078f1cd66;hpb=73495b061c2fa75855a6a068178f93c1d9948fa4;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 03be0ac..6a41d91 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1825,6 +1825,15 @@ invertieren. \subsection[Bitones Mergesort-Netzwerk]{Versuche mit dem bitonen Mergesort-Netzwerk} \label{sect:sn-evolution-cut:bs} +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 +als \bs{n-k}. Wird \textsc{SN-Evolution-Cut} beispielsweise mit \bs{22} und $k += 6$ gestartet, resultiert das gefundene Schnittmuster in einem +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. + \begin{figure} \begin{center} \input{images/16-ec-from-bs22.tex} @@ -1837,6 +1846,200 @@ invertieren. \label{fig:16-ec-from-bs22} \end{figure} +Eine Übersicht über die Effizienz der Ergebnisse, die mit dem \emph{bitonen +Mergesort}-Netzwerk als Eingabe für \textsc{SN-Evolution-Cut} erzielt wurden, +gibt Tabelle~\ref{tbl:ec-bs-efficiency}. \textsc{SN-E\-vo\-lu\-tion-Cut} wurde +mit \bs{n}, $n = 9 \dots 24$ und $k = 1 \dots (n-8)$ gestartet. Die Konstanten +der Bewertungsfunktion waren $w_{\mathrm{Basis}} = 0$, +$w_{\mathrm{Komparatoren}} = 1$ und $w_{\mathrm{Schichten}} = n$. In jeder +Zeile befinden sich die Ergebnisse für ein Eingabenetzwerk, in den Spalten +befinden sich die Ergebnisse für eine Leitungszahl $m=n-k$ des +Ausgabenetzwerks. In den Zellen stehen jeweils die Anzahl der Komparatoren des +resultierenden Netzwerks. Die letzte Zeile enthält die Anzahl der +Komparatoren, die \bs{m} benötigt, um die Ergebnisse besser einordnen zu +können. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|rrrrrrrrrrrrrrrr|} + \hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ + \hline + 9 & 21 & & & & & & & & & & & & & & & \\ + 10 & 20 & 27 & & & & & & & & & & & & & & \\ + 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\ + 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\ + 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\ + 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\ + 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\ + 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\ + 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\ + 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\ + 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\ + 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\ + 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\ + 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\ + 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\ + 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\ + \hline +\bs{m} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen + Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt + die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die + Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.} + \label{tbl:ec-bs-efficiency} +\end{table} + +Zu sehen ist, dass jedes einzelne Ergebnis von \textsc{SN-Evolution-Cut} +mindestens so effizient wie das \emph{bitone Mergesort}-Netzwerk mit der +gleichen Leitungszahl ist. Außerdem enthält jede Spalte (mit Ausnahme von +$m=23$) ein Ergebnis, das effizienter als \bs{m} ist. + +In zahlreichen Fällen reicht das Entfernen einer einzigen Leitung aus, um ein +effizientes Ergebnis zu erzielen. Das Ergebnis, das \textsc{SN-Evolution-Cut} +gestartet mit \bs{20} und $k = 1$ erreicht, benötigt mit 95~Komparatoren +3~weniger als \bs{19}. + +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} + +Bei einigen Werten für die Ziel-Leitungsanzahl $m$ kann der +\textsc{SN-Evolution-Cut}-Algorithmus Ergebnisse erzielen, die schneller als +das entsprechende \emph{bitone Mergesort}-Netzwerk \bs{m} sind. In +Tabelle~\ref{tbl:ec-bs-speed} sind die Schichten, die die Ergebnisse von +\textsc{SN-Evolution-Cut} benötigen, um die Eingabe zu sortieren, aufgelistet. +Jede Zeile enthält die Ergebnisse für ein Eingabenetzwerk \bs{n}, jede Spalte +enthält die Ergebnisse für eine Ziel-Leitungszahl $m = n-k$. Die Zellen +enthalten die Anzahl der Schichten des jeweiligen Ergebnis-Netzwerks. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} +\begin{tabular}{|r|rrrrrrrrrrrrrrrr|} +\hline + & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ +\hline + 9 & 6 & & & & & & & & & & & & & & & \\ + 10 & 6 & 8 & & & & & & & & & & & & & & \\ + 11 & 6 & 8 & 9 & & & & & & & & & & & & & \\ + 12 & 6 & 8 & 9 & 10 & & & & & & & & & & & & \\ + 13 & 6 & 8 & 9 & 10 & 10 & & & & & & & & & & & \\ + 14 & 6 & 8 & 9 & 10 & 10 & 10 & & & & & & & & & & \\ + 15 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & & & & & & & & & \\ + 16 & 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & & \\ + 17 & 6 & 8 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & & & & & & & \\ + 18 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & & & & & & \\ + 19 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & & & & & \\ + 20 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & & & & \\ + 21 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & & & \\ + 22 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & & \\ + 23 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & \\ + 24 & 6 & 8 & 8 & 9 & 9 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\ +\hline +\bs{m}& 6 & 8 & 9 & 10 & 10 & 10 & 10 & 10 & 10 & 12 & 13 & 14 & 14 & 15 & 15 & 15 \\ +\hline +\end{tabular} + \end{center} + \caption{Anzahl der Schichten der Ergebnisse von + \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen + Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt + die Ergebnisse für ein Eingabenetzwerk \bs{n} an, jede Spalte enthält die + Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.} + \label{tbl:ec-bs-speed} +\end{table} + +Für die Ziel-Leitungszahlen 9, 10 und 11 wurden Schnittmuster gefunden, die +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. + +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 +werden müssen, um schnellere Netzwerke zu erzielen, größer. Um eine Schicht +einzusparen waren bei $m = 10$ und $m = 11$ $k = 6$ Schnitte notwendig. Bei $m += 9$ war sogar ein 7-Schnittmuster notwendig, um die Anzahl der Schichten zu +reduzieren. Für schnelle \emph{und} effiziente Netzwerke musste $k$ teilweise +noch größer gewählt werden. + +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 +Tabelle~\ref{tbl:ec-bs-19} aufgelistet. Erst, wenn $k \geqq 6$ ist, wird im +Vergleich zu \bs{19} eine Schicht eingespart. Für $n = 36$ ($k = 17$) und $n = +37$ ($k = 18$) werden Sortiernetzwerke ausgegeben, die schneller als \bs{19} +und \oes{19} sind und nur einen Komparator mehr als \oes{19} benötigen. Ein +Beispiel für ein solches Netzwerk ist in +Abbildung~\ref{fig:19-ec-from-bs37-fast} zu sehen. + +\begin{table} + \begin{center} + \rowcolors{2}{black!5}{} + \begin{tabular}{|r|r|r|} + \hline + $n$ & Komp. & Schichten \\ + \hline + 20 & 95 & 14 \\ + 21 & 94 & 14 \\ + 22 & 93 & 14 \\ + 23 & 93 & 14 \\ + 24 & 93 & 14 \\ + 25 & 96 & 13 \\ + 26 & 96 & 13 \\ + 27 & 96 & 13 \\ + 28 & 96 & 13 \\ + 29 & 95 & 13 \\ + 30 & 96 & 13 \\ + 31 & 95 & 13 \\ + 32 & 96 & 13 \\ + 33 & 93 & 13 \\ + 34 & 94 & 13 \\ + 35 & 93 & 13 \\ + \rowcolor{green!10} + 36 & 92 & 13 \\ + \rowcolor{green!10!white!95!black} + 37 & 92 & 13 \\ + 38 & 93 & 13 \\ + \hline + \bs{19} & 98 & 14 \\ + \oes{19} & 91 & 14 \\ + \hline + \end{tabular} + \end{center} + \caption{Anzahl der Komparatoren und Schichten von 19-Sortiernetzwerken, die + von \textsc{SN-Evolution-Cut} aus \bs{n}, $n = 20, \dots, 38$ erzeugt + wurden. Für $k \geqq 6$ ergeben sich Sortiernetzwerke, die schneller als + \bs{19} sind. Mit $k \in \{14, 16, 19\}$ erreichen die Ergebnisse mit + 13~Schichten die Effizienz der vorherigen + Ergebnisse mit 14~Schichten, mit $k = 17$ und $k = 18$ wird diese + Effizienz noch übertroffen. Ein 19-Sortiernetzwerk, das aus \bs{37} + auf diese Art erzeugt wurde, ist in + Abbildung~\ref{fig:19-ec-from-bs37-fast} dargestellt.} + \label{tbl:ec-bs-19} +\end{table} + \textit{Moritz Mühlenthaler} und \textit{Rolf Wanka} zeigen in~\cite{MW2010}, wie man einen bitonen Mischer, der nach Batchers Methode konstruiert wurde, durch systematisches Entfernen von Leitungen in einen ebenfalls bitonen @@ -1921,41 +2124,6 @@ Sortiernetzwerk benötigt lediglich 206~Komparatoren. Die Komparatoren aller dieser Netzwerke können in 15~Schichten angeordnet werden, so dass die Geschwindigkeit dieser Sortiernetzwerke gleich ist. -Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr -unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für -gute Schnittmuster anzugeben. - -Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen -Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein. -Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in -Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 -ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten -ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich -die Schnittmuster aufgrund der Symmetrie des \emph{bitonen -Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung -- -mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig. - -\begin{figure} - \centering - \subfigure[11-Sortiernetzwerk aus 37~Komparatoren in 9~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{22} erzeugt.]{\input{images/11-ec-from-bs22-fast.tex}\label{fig:11-ec-from-bs22-fast}} - \subfigure[12-Sortiernetzwerk aus 42~Komparatoren in 9~Schichten. Das - Netzwerk wurde von \textsc{SN-Evolution-Cut} aus \bs{24} erzeugt.]{\input{images/12-ec-from-bs24-fast.tex}\label{fig:12-ec-from-bs24-fast}} - \caption{Startet man \textsc{SN-Evolution-Cut} mit \bs{22} und \bs{24}, kann - der Algorithmus schnelle Sortiernetzwerke ausgeben.} - \label{fig:11-12-ec-from-bs22-bs24} -\end{figure} - -Verwendet man als Eingabe für \textsc{SN-Evolution-Cut} Instanzen des -\emph{bitonen Mergesort}-Netzwerks, deren Leitungszahl keine Zweierpotenz ist, -können Sortiernetzwerke zurückgegeben werden, die sowohl schneller als auch -effizienter als das entsprechende \emph{bitone Mergesort}-Netzwerk sind. Die -folgende Tabelle listet einige interessante Fälle auf. Die Eingabe für -\textsc{SN-Evolution-Cut} war jeweils das \emph{bitone Mergesort}-Netzwerk mit -der doppelten Leitungszahl. Die Abbildungen~\ref{fig:11-12-ec-from-bs22-bs24} -und~\ref{fig:23-ec-from-bs46} zeigen beispielhaft ein 11-, 12- und -23-Sortiernetzwerk, die aus \bs{22}, \bs{24} und \bs{46} generiert wurden. - \begin{center} \begin{tabular}{|r|r|r|r|r|} \hline @@ -1987,6 +2155,20 @@ Leitungen & Komparatoren & Schichten & Komparatoren & Schichten \\ \label{fig:23-ec-from-bs46} \end{figure} +Leider sind die Schnittmuster, die \textsc{SN-Evolution-Cut} ausgibt, sehr +unregelmäßig. Bisher ist es nicht gelungen eine Konstruktionsanweisung für +gute Schnittmuster anzugeben. + +Entscheidend für das Ergebnis eines Schnittmusters scheint beim \emph{bitonen +Mergesort}-Netzwerk die Aufteilung der Minimum- und Maximumschnitte zu sein. +Von Hundert 16-Schnittmustern für $\operatorname{BS}(32)$, die in +Sortiernetzwerken mit 68~Komparatoren in 10~Schichten resultieren, hatten 73 +ein Verhältnis von $5/11$, 13 hatten ein Verhältnis von $4/12$ und 14 hatten +ein Verhältnis von $3/13$ Minimum- beziehungsweise Maximumschnitten. Da sich +die Schnittmuster aufgrund der Symmetrie des \emph{bitonen +Mergesort}-Netzwerks leicht invertieren lassen, ist eine Fallunterscheidung -- +mehr Minimum- oder mehr Maximumschnitte -- nicht notwendig. + Dass die Ergebnisse von \textsc{SN-Evolution-Cut} keine erkennbare Struktur haben, ist jedoch kein Eigenschaft des Algorithmus, sondern hängt insbesondere von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem @@ -1994,42 +2176,6 @@ von der Eingabe ab. Wird \textsc{SN-Evolution-Cut} beispielsweise mit dem $k$~Schnitten gestartet, so ist das beste Ergebnis immer das $\operatorname{OET}(n-k)$-Netzwerk. -\begin{table} - \begin{center} - \rowcolors{2}{black!5}{} - \begin{tabular}{|r|rrrrrrrrrrrrrrrr|} - \hline - & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ - \hline - 9 & 21 & & & & & & & & & & & & & & & \\ - 10 & 20 & 27 & & & & & & & & & & & & & & \\ - 11 & 20 & 27 & 32 & & & & & & & & & & & & & \\ - 12 & 20 & 26 & 32 & 39 & & & & & & & & & & & & \\ - 13 & 20 & 26 & 32 & 39 & 45 & & & & & & & & & & & \\ - 14 & 20 & 26 & 32 & 39 & 45 & 53 & & & & & & & & & & \\ - 15 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & & & & & & & & & \\ - 16 & 20 & 26 & 32 & 39 & 45 & 53 & 61 & 70 & & & & & & & & \\ - 17 & 20 & 26 & 32 & 37 & 43 & 50 & 57 & 65 & 74 & & & & & & & \\ - 18 & 20 & 26 & 31 & 37 & 43 & 49 & 56 & 63 & 71 & 82 & & & & & & \\ - 19 & 20 & 26 & 31 & 37 & 43 & 48 & 55 & 62 & 70 & 79 & 88 & & & & & \\ - 20 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 86 & 95 & & & & \\ - 21 & 20 & 26 & 32 & 37 & 44 & 48 & 55 & 61 & 68 & 77 & 85 & 94 & 103 & & & \\ - 22 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 67 & 77 & 84 & 93 & 102 & 112 & & \\ - 23 & 20 & 26 & 31 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & \\ - 24 & 20 & 26 & 32 & 37 & 42 & 48 & 54 & 61 & 68 & 76 & 84 & 93 & 102 & 112 & 122 & 133 \\ - \hline -\bs{n} & 24 & 28 & 33 & 39 & 46 & 53 & 61 & 70 & 80 & 85 & 91 & 98 & 106 & 114 & 123 & 133 \\ - \hline - \end{tabular} - \end{center} - \caption{Anzahl der Komparatoren der Ergebnisse des - \textsc{SN-Evolution-Cut} mit verschiedenen Größen des \emph{bitonen - Mergesort}-Netzwerks und unterschiedlichen Werten für~$k$. Jede Zeile gibt - die Ergebnisse für ein Eingabenetzwerk \bs{n} an, die Spalten - repräsentieren die Anzahl der Leitungen des Ausgabenetzwerks.} - \label{tbl:ec-bs-fast} -\end{table} - \subsection[Odd-Even-Mergesort-Netzwerk]{Versuche mit dem Odd-Even-Mergesort-Netzwerk} \label{sect:sn-evolution-cut:oes} @@ -2223,7 +2369,7 @@ wie und warum es jede beliebige Eingabe sortiert. Jede Zeile gibt die Ergebnisse für ein Eingabenetzwerk \ps{n} an, jede Spalte enthält die Ergebnisse für $m=n-k$, die Anzahl der Leitungen des Ausgabenetzwerks.} - \label{tbl:ec-bs-fast} + \label{tbl:ec-ps-fast} \end{table} Das \emph{Pairwise-Sorting-Netzwerk} $\operatorname{PS}(n)$, das \textit{Ian