間が開いたので2回分まとめて。
◯第8章 ソート
プロセッサ時間の80%以上はソートに費やされるとも言われる。ソートを高速化すれば処理全体の高速化につながりやすい。
この章では5つのアルゴリズムについて並行化を検討している。
バブルソートは左右で要素を比較して、小さい値(または大きい値)が泡のように上がっていくことからそう呼ばれる。スレッドの順番が入れ替わらない限り、頭から複数スレッドで配列を走査してもソートは保証される。このアルゴリズムは波の動きに似ているためwavefront法とも呼ばれる。単に前のスレッドを抜かさないようにするとオーバーヘッドが大きくなるため、配列をいくつかのゾーンに区切って制御すると良い。
奇偶転置ソートは「奇数インデックスの比較→偶数インデックスの比較→奇数インデックスの比較」を繰り返してソートを行う。隣接同士の比較・変更しか起こりえないので、データ分解による並列化が容易。
シェルソートは配列全体を適当なサイズで分割し、分割された範囲内でソートを行う。徐々に分割サイズを小さくすることでソートを行ない、要素が大きく動かせることからソートが早く行える特徴がある。逐次処理では有効だが、並行処理ではキャッシュが効きにくくなり並行処理では短所にもなりうる。
クイックソートは逐次処理では最も一般的なソートである。再帰を使って実装することもあるが、並行処理には不向きなのでキューを使うなりして再帰は避ける必要がある。スレッドをプールし、ソート対象のインデックス範囲をキュー/スタックに入れておくことでスレッド間の競合を抑え、処理を並行化することができる。処理が終わったかどうかを判断し、スレッドに処理を辞めるよう促す実装が若干面倒。
奇数ソートはソート対象を二進数と考え、上位ビット/下位ビットを使ってソートしていく。同じ値の順序が保たれる安定ソートであることが特徴。実装では複数ビットをまとめてソートすることになるが、ソート後の移動先の計算がかなり面倒。本でもトリッキーに思える例が紹介されていた。
◯第9章 サーチ
未ソートデータに対するサーチと、ソート済みデータに対するサーチの例を紹介。
未ソートデータの場合、全要素を見ないといけないので、配列をデータ分解してスレッドに処理させる。探索対象のデータが見つかったときに処理を打ち切る工夫を入れるぐらいでOK。素直な実装になる。
ソート済みデータの場合、逐次処理では2分探索が一般的。並行処理ではこの考え方を発展させてN分探索すると良い。配列をNつに分解し、探索対象がどちら側にあるか(右側、左側、見つかった)を調べる。探索対象のデータは向きが異なるブロックに含まれるため、このブロックを探し出し、内部をさらにNつに分解して再帰的に探索を続ける。
