はやみずの「は」

Go遊会 11日目

今日のテーマ:並列プレフィックスサム

10日目に引き続き、並列クイックソート実装のためのプリミティブ作り。 配列 a に対して、次のような配列 s を a のプレフィックスサムという。

  • s[0] = a[0]
  • s[1] = a[0] + a[1]
  • s[2] = a[0] + a[1] + a[2]
  • ...
  • s[n] = a[0] + a[1] + ... + a[n]

プレフィックスサムは、単純には s[k] = s[k - 1] + a[k] の計算を逐次回すことで計算することができるが、この方法はそのまま並列化するのは難しい。 並列クイックソートの資料にあるように、配列 a の値をツリー上にマージするように足しあわせていくことで、並列にプレフィックスサムを計算することができる。そのかわり、逐次計算に比べて加算演算の実行総量は増すし、スレッド駆動等々の並列化オーバヘッドもあるため、あんまりいい加減に作ると速くならない。 実際、今回の実装では parallel_for の1イテレーションにおける演算をある程度バッチでまとめて流すようにしないと、逐次実行に比べて常に5倍程度遅くなってしまった。

結果

f:id:hayamiz:20141103140520p:plain

入力データ長N とプレフィックスサム計算に要する時間の比較。

f:id:hayamiz:20141103140626p:plain

入力データ長Nと、プレフィックスサム並列化による性能向上率。

Nが小さい時には並列プレフィックスサムが明らかに遅い。Nが2,000,000くらいのところでようやく性能がほぼ同じになり、それ以上では2倍弱の性能向上率だった。 おそらく並列化によるキャッシュへの擾乱等があるので、この処理に関してはあまり頑張っても性能向上に限りがありそうなので、とりあえずこんなもので一旦次に進むことにする。

実装コード

goyukai/par-prefixsum.go at master · hayamiz/goyukai · GitHub

次回のテーマ:並列パーティション

(並列)プレフィックスサムを使って、クイックソートにおけるパーティション操作を並列化する。