ネタ元：並列処理が向かないかもしれない例
ネタ。。。いただきました。バブルソートの並列化。。。チョー難問。
とりあえずは、επιστημηさんのアプローチ(一般にソースコードとも呼ぶｗ)で、８コア(4コアHT)で試してみました。結果はネタ元のコメントを参照のことｗ
さて。。。バブルソートはなぜ並列化に向かないのでしょう？
そのためには、まずバブルソートというアルゴリズムを知る必要があります。
バブルソートとは隣接するデータ同士を比較し、より大きい(あるいは小さい)値を右(あるいは左)に寄せながら隣の要素と比較して、要素の最後まで作業する。という処理を、入れ替えが発生しなくなるまで行い続けるというソートアルゴリズムです。
が…文字で書くとさっぱりわかりませんｗｗｗ
図で書いてみましょう。
元データは、えぴさんところのをもらって「1 7 6 5 8 2 4 3 」です。
下記の図は、<>でくくった二つの数字を比較し、大きいほうを右に寄せます。それを一つずつずらして処理します。
<1 7> 6 5 8 2 4 3
1<7 6>5 8 2 4 3
1 6<7 5>8 2 4 3
1 6 5<7 8>2 4 3
1 6 5 7<8 2>4 3
1 6 5 7 2<8 4>3
1 6 5 7 2 4<8 3>
1 6 5 7 2 4 3 8
と、こんな感じで１回目の処理が終わります。あとは、入れ替えが発生しなくなるまでずーっと繰り返すだけ(紙面の都合でカットアウトですｗ)。比較部分がまるで泡が上って行くように少しずつずれていく様子がわかるでしょうか？このような動きをすることからバブルソートと呼ばれています。
さて。。。ここでポイントになるのが、データにアクセスするタイミングと箇所。バブルソートは非常に単純であるがゆえに、ソートの瞬間処理(<>の部分)で必要とするデータアクセス量が少ないという特性を持っています。
この特性は並列処理においてはかなり高いアドバンテージがあるといえます。要素が1000あったとした場合、ある瞬間にソート処理している要素は２個しかない。全体から見れば同時アクセスを回避する必要がある部分がわずかに0.2%しか存在しないということになります。残りの99.8%はそれこそ何をやっていても困らない。
<>でくくっている瞬間はその２要素だけ他からアクセスされないようにロックしておけばよさそうです。
が。。。数が全部で１０個程度ならまだしも現実のソートとなるとふつうに３ケタ、４ケタあるいは５ケタ、６ケタという数で処理されるのが大半です。そうなるとその部分を排他制御していたのではコストが合わなそうです。
ここで考えるべきは、明確に同時アクセスを制御することなく、バブルソートの持つ局所アクセス性を犠牲にすることなくなるべく同時に処理する方法というのが一番良いといえるでしょう。
アプローチにはいくつかありますが、バブルソートのアルゴリズム「だけ」を使ってなんとか並列する方法を考えてみることにしましょう。
上の図の下半分に着目してみます。要素の後半だけをアクセスしていますね。逆に前半分はどうでしょう？前半だけをアクセスしています。
では、要素の前半分だけ、後ろ半分だけでそれぞれバブルソートさせてみたらどうなるのでしょう？
1 7 6 5 | 8 2 4 3
<1 7>6 5 |<8 2>4 3
1<7 6>5 | 2<8 4>3
1 6<7 5>| 2 4<8 3>
1 6 5 7 | 2 4 3 8
…省略…
1 5 6 7 | 2 3 4 8
半分に割ったままでは、どこまで行っても全体はソートされません(当たり前ですが)。しかもこれだと、2個しか同時に処理しません。デスクトップだとエントリーモデルですら3コア、4コアあるいは論理8コアとかという時代なのに。。。
じゃぁ追いかけていったらどうでしょう？
<1 7> 6 5 8 2 4 3
1<7 6>5 8 2 4 3
[1 6]<7 5>8 2 4 3
1 [6 5]<7 8>2 4 3
(1 5) [6 7]<8 2>4 3
1 (5 6)[7 2]<8 4>3
1 5 (6 2)[7 4]<8 3>
1 5 2 (6 4)[7 3] 8
1 5 2 4 (6 3) [7 8]
1 5 2 4 3 (6 7) 8
1 5 2 4 3 6 7 8
お。これならいい感じで進めそうです。ここでは3個で書いてますが、ソートが終わってなければ。。。でいくらでも行けそうです。しかも図で見てる限りにおいては重複もありません。
となると、問題はこれをどうやってコードにするか？ある瞬間はdata[i] と data[i+1] へのアクセスですが、それを維持しつつあとから来るやつが追い越さない(入れ替えが発生しない場合と発生する場合では進む速度が変わる)アプローチが取れるのか？
これ、現実的な処理モデルに非常に近い形を持っているので、ぜひとも自分なりのアプローチで設計してみるとよいのではないでしょうか？
その手助けになるかどうかはわかりませんが、わんくま同盟東京勉強会 #49 でVS2010の並列アルゴリズム、ほとんど全部紹介しますのでｗ