@drken さんの『「ソート」を極める! 〜 なぜソートを学ぶのか 〜』とゆう記事を読んで、「並列処理でバブルソートをしたらどうなるんだろぉ?」って素朴に思ったもんで、ちょっと考えてみた。意外に速くなるんじゃないかって…。((o(´∀`)o))ワクワク

二相式・同期並列処理のバブルソート

並列処理のイメージとして考えたのは生体内の細胞の作用みたいな感じ。(分かんないけど)もしかしたら分子コンピューティングとかDNAコンピューティングとかなら実現できるかも?棚の前に人がズラッと並んだ人海戦術の場合でもできる手法。とにもかくにもプロセッサーの個数が多くてそれらが同時に作用する、そんな場合を考えてみたんだ。

考えたのは、一次元に並んだメモリー・セル $\left[C_1,\ C_2,\ \dots,\ C_n\right]$ に対してプロセッサー群 $\left[P_1,\ P_2,\ \dots,\ P_{n-1}\right]$ が同期的並列に動作するもので、二相ある状態を交互に繰り返す。

第一相
隣り合う $C_i$ と $C_{i+1}$ の間に跨るように $P_i$ が内容を比較して $C_i>C_{i+1}$ の場合は値を交換して、さもなくばそのままにする。
第ニ相
隣り合う $C_{i+1}$ と $C_{i+2}$ の間に跨るように $P_i$ が内容を比較して $C_{i+1}>C_{i+2}$ の場合は値を交換して、さもなくばそのままにする。

1s.png

二相が一回終わるごとにメモリーの内容は最大2個分移動する。$n=8$ の場合だと最大離れたメモリー距離は $n-1=7$ だから二相一式の動作を $\displaystyle\left\lceil 7\div 2\right\rceil=4$ 回すればソートは完了する。処理回数としては $2\times 4=8$ ねっ。

プロセッサーの個数が少ない場合

データが大量にあってプロセッサーの個数が足りない場合はどうなるか?プロセッサーを移動させて一つの相を何回を分けて実現すれば良いんだ。

データ数が8でプロセッサー数が2の場合

2s.png

データ数が8でプロセッサー数が1の場合

3s.png

ソートに必要な処理回数

プロセッサーの個数が無限にある場合でも必要なプロセッサー数 $P_\mathrm{max}$ は…。

$$P_\mathrm{max} = \left\lceil\frac{n-1}{2}\right\rceil$$

この時、一つの相ではメモリー距離 $2$ だけ値が移動するけど、これに必要な処理回数 $T_2$ は…

$$T_2 = \left\lceil\frac{n-1}{\min\left(P,\ P_\mathrm{max}\right)}\right\rceil$$

メモリー距離 $n-1$ の移動に必要な処理回数 $T_{n-1}$ は…

$$T_{n-1} = \left\lfloor\frac{n-1}{2}\right\rfloor T_2$$

数式全部を一つにするとぉ…

$$T_{n-1} = \left\lfloor\frac{n-1}{2}\right\rfloor \left\lceil\frac{n-1}{\min\left(P,\ \left\lceil\frac{n-1}{2}\right\rceil\right)}\right\rceil$$

こんな感じ。

プロセッサーが十分にある場合のオーダー

プロセッサーが十分にある場合、つまり、$P\ge P_\mathrm{max}$ の場合のオーダー $O\left(\cdots\right)$ を考えてみた。オーダーって確か $n\rightarrow\infty$ の場合の数式のことだから…

$$
\begin{array}\newline
\displaystyle\lim_{n\to\infty}T_{n-1}
&=\displaystyle\lim_{n\to\infty}\left\lfloor\frac{n-1}{2}\right\rfloor \left\lceil\frac{n-1}{\min\left(P,\ \left\lceil\frac{n-1}{2}\right\rceil\right)}\right\rceil\newline
&=\displaystyle\lim_{n\to\infty}\left\lfloor\frac{n-1}{2}\right\rfloor \left\lceil\frac{n-1}{\left\lceil\frac{n-1}{2}\right\rceil}\right\rceil\newline
&=\displaystyle\lim_{n\to\infty}\left\lfloor\frac{n-1}{2}\right\rfloor\cdot 2\newline
&=\displaystyle\lim_{n\to\infty}\left(n-1\right)\newline
&=\displaystyle\lim_{n\to\infty}n\newline
\end{array}
$$

とゆうわけで、

$$O\left(n\right)$$

になる、はず。数式、間違いないかなぁ…?二相式・同期並列処理のバブルソート、速いねっ。イイネッ。(・∀・)

追記

このアルゴリズムの利用法としてイメージしてるのは細胞みたいに大量の低機能の小さなプロセッサーが寄ってたかって処理するような場合であって、共有バスラインを使ってメモリーにアクセスする方式の現存する電子計算機ではないんだ。

現存する電子計算機で実装するのはかなり無理があるともう。実際、データ数 $n$ に対してプロセッサー数 $P\ \left(\lt P_\mathrm{max}\right)$ での実装を想定して処理時間 $T_{n-1}$ を考えてみると、(天井関数・床関数を省いて近似した)概算値としては、

$$T_{n-1}\sim\displaystyle\frac{\left(n-1\right)^2}{2P}$$

こんな感じだから、現存する電子計算機だと $P\ll n$ だから、やっぱり向かない方式だねっ。電子回路を使う方式としてしは、あり得るとすればプラスチック・セル・アーキテクチャー1かもねっ。(;´∀`)


  1. plastic cell architecture、PCA 

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.