今回でラスト。

◯第10章 グラフアルゴリズム
深さ優先探索と幅優先探索の並行実装例を紹介している。どちらも逐次処理だと再帰実装がよく用いられるが、再帰と並行処理の相性が悪いためキュー・スタックをつかって探索位置を管理する必要がある。スタックを使えば深さ優先探索に、キューを使えば幅優先探索になる。

次が最短経路探索問題のアルゴリズム。Floyd-Warshall法やDijkstra法があるけど、本ではFloyd-Warshall法だけTBBを使って紹介。特筆事項は無し。

最後が最小スパニングツリーを見つけるアルゴリズム。KruskalとPrimがあるけど、本ではPrimをTBBとOpenMPを組み合わせて並列化する手法を紹介。これまでの総集編といった趣。

◯第11章 スレッド対応ツール
宣伝じゃないと言いながらもIntelの製品をパワープッシュ。
著者はIntelの社員さんなのは割り引いて聞く必要があるかも。

◯全部読んでの感想
会社のメンバで輪講したのですが、後半はアルゴリズムの解説が多く、ソースの実装もいまいちだったように感じました。さらに後半は元の文が悪いのか、訳が悪いのか読んでいてわからないところが頻出しました。並行処理の基礎知識を習得するのに5章までを読むのにはいいかもしれません。後半は並行処理実装のアイデアを色々もらえるけど、いくらか疑ってかかったほうがいいと思います。

間が開いたので2回分まとめて。

◯第8章 ソート
プロセッサ時間の80%以上はソートに費やされるとも言われる。ソートを高速化すれば処理全体の高速化につながりやすい。
この章では5つのアルゴリズムについて並行化を検討している。

バブルソートは左右で要素を比較して、小さい値(または大きい値)が泡のように上がっていくことからそう呼ばれる。スレッドの順番が入れ替わらない限り、頭から複数スレッドで配列を走査してもソートは保証される。このアルゴリズムは波の動きに似ているためwavefront法とも呼ばれる。単に前のスレッドを抜かさないようにするとオーバーヘッドが大きくなるため、配列をいくつかのゾーンに区切って制御すると良い。

奇偶転置ソートは「奇数インデックスの比較→偶数インデックスの比較→奇数インデックスの比較」を繰り返してソートを行う。隣接同士の比較・変更しか起こりえないので、データ分解による並列化が容易。

シェルソートは配列全体を適当なサイズで分割し、分割された範囲内でソートを行う。徐々に分割サイズを小さくすることでソートを行ない、要素が大きく動かせることからソートが早く行える特徴がある。逐次処理では有効だが、並行処理ではキャッシュが効きにくくなり並行処理では短所にもなりうる。

クイックソートは逐次処理では最も一般的なソートである。再帰を使って実装することもあるが、並行処理には不向きなのでキューを使うなりして再帰は避ける必要がある。スレッドをプールし、ソート対象のインデックス範囲をキュー/スタックに入れておくことでスレッド間の競合を抑え、処理を並行化することができる。処理が終わったかどうかを判断し、スレッドに処理を辞めるよう促す実装が若干面倒。

奇数ソートはソート対象を二進数と考え、上位ビット/下位ビットを使ってソートしていく。同じ値の順序が保たれる安定ソートであることが特徴。実装では複数ビットをまとめてソートすることになるが、ソート後の移動先の計算がかなり面倒。本でもトリッキーに思える例が紹介されていた。

◯第9章 サーチ
未ソートデータに対するサーチと、ソート済みデータに対するサーチの例を紹介。

未ソートデータの場合、全要素を見ないといけないので、配列をデータ分解してスレッドに処理させる。探索対象のデータが見つかったときに処理を打ち切る工夫を入れるぐらいでOK。素直な実装になる。

ソート済みデータの場合、逐次処理では2分探索が一般的。並行処理ではこの考え方を発展させてN分探索すると良い。配列をNつに分解し、探索対象がどちら側にあるか(右側、左側、見つかった)を調べる。探索対象のデータは向きが異なるブロックに含まれるため、このブロックを探し出し、内部をさらにNつに分解して再帰的に探索を続ける。