いよいよアルゴリズムの並行化に着手する。今回は並列和、プリフィックススキャン、セレクションの3種類。
◯並列和
配列の和を全部求めるよくある処理。楽なのはOpenMPやTBBを使ってリダクション処理をそのまま利用すること。
自前で実装するなら配列をスレッド数で分割して個別に小計を計算。全スレッドが計算終わったら小計を全部足して合計をもとめるというやり方がおすすめ。
◯プリフィックススキャン
[3, 5, 2, 5, 7, 9, 4, 6]という配列を与えたときに[3, 8, 10 15, 22, 31, 35, 41]という配列を求める。配列のN番目に元の配列の0〜N番目までの和を入れておく処理に当たる。包含的プリフィックススキャンとも言うらしい。
先頭を覗いて[0, 3, 8, 10, 15, 22, 31, 35]の配列を求める排他的プリフィックススキャンの方法もある。
並列化の手法として、スレッド数で配列を分割し、個別にプリフィックススキャンを行う。次に末尾の要素を使って前後のチャンクに伝搬させる値を計算する。計算が終わったそれぞれのスレッドが担当するチャンクに値を加算してプリフィックススキャンを完了する。
さっきの例を3スレッドでやるとこんな感じになる。2と4のステップが並列化可能になる。
2から3、3から4に移るときに毎回スレッドを生成/破棄するとオーバーヘッドになるので、スレッドのイベント通知機能を上手く使って使いまわすのが吉。
1. 入力をスレッド数で分割
[3, 5, 2, 5, 7, 9, 4, 6] -> [3, 5, 2], [5, 7, 9], [4, 6]
2. 個別にプリフィックススキャン
[3, 5, 2], [5, 7, 9], [4, 6] -> [3, 8, 10], [5, 12, 21], [4, 10]
3. 配列の末尾の値で排他的プリフィックススキャンを行い、伝搬させる値を計算する
[3, 8, 10], [5, 12, 21], [4, 10] -> [10, 21, 10] -> [0, 10, 31]
4. 3で求めた値を2の処理結果にそれぞれ加算
[3, 8, 10]+0, [5, 12, 21]+10, [4, 10]+31 -> [3, 8, 10, 15, 22, 31, 35, 41]
◯セレクション
配列をソートしてN番目の値を取ってくるという処理。
ソートしてもいいけど、1回しか呼ばれないとか、適宜順番が変わるような配列だとセレクションがおすすめ。
公知のセレクションアルゴリズムがあって、その中でいくつかを並列化する。
1. 配列数がQ(本では5を勧めている)より小さければデータをソートして、k番目の要素を返す。Qより多ければ次のステップへ
2. チャンクから中央値を選ぶ(本では配列を分割して中央値を求め、その中からさらに中央値を求めるやり方をしているけど、配列の中身が適度にバラバラなら適当に選んでもいいかも)
3. データを A.中央値より小さい値を持つ B.中央値と同じ値である C.中央値より大きい値を持つ の3種類に分け、A,B,Cの数を数える。
4. 求めるk番目の要素がどこに入るかを調べる。Bに入るなら値を返して終了、AかCなら再帰的に1から処理を続ける。
本で高速化しているのはこのうちの2の処理、3の処理、4の処理の一部である。ポイントは4の処理で、再帰的に呼び出す際の配列の部分集合を使うのにプリフィックススキャンを使って詰め直し先のインデックス値を求めている。逐次処理に慣れきっていると重そうだけど、実際実行してみたら早いのかな? 要検証。
Clay Breshears
オライリージャパン
売り上げランキング: 8422
IBM東京基礎研究所のようす
企業研究者を目指す学生は勿論のこと、企業研究者にも参考になる。
