はやみずの「は」

Go遊会 10日目

今日のテーマ:parallel-for loopの比較

並列クイックソートアルゴリズムhttp://www3.cs.stonybrook.edu/~rezaul/Spring-2013/CSE638/CSE638-lectures-8-9.pdf を参考に実装することにした。 並列クイックソートの実装には並列パーティションの実装が必要で、並列パーティションの実装には並列プレフィックスサムの実装が必要。並列プレフィックスサムの実装にはparallel-forパターンの実装が必要不可欠なので、まず今日はparallel-for をGo言語で実現するアプローチを模索した。

Cilkなどの並列プログラミング言語が持っている parallel-for のような抽象度の高い並列処理機能は、Go言語自身では提供されていない。そのため、goroutineを使って自前でそれらしいものを作り上げる必要がある。

例えば次のようなfor ループの並列化を考える。

for i := 0; i < N; i++ {
  doSomething(i)
}

for ループの並列化には大きく次のパターンが考えうる

  • パターン1: 各イテレーションの実行を goroutine 生成して行う
  • パターン2: 幾つかのイテレーションをバッチにまとめ、バッチ毎に goroutine を生成して処理する

パターン1のほうは実装がシンプルになる一方で、イテレーションの処理が軽い場合にはgoroutine生成コストがかなり大きくなるので効率が悪い。パターン2は、処理の並列性が満たされる程度の範囲でgoroutine生成コストを削減することができるため、効率はかなりよいであろうと思われる。

実際に次のような入力値の二乗を出力値とする doSomething を逐次実行、パターン1、パターン2で実行して時間を測定してみる。

func doSomething(i int) {
  output[i] = intput[i] * input[i]
}

結果

入力データは32ビット整数の配列、配列長 N = 100,000,000

  • 逐次実行:0.7186 秒
  • パターン1:71.2431 秒
  • パターン2:0.1873 秒

逐次に対してパターン1のparallel-for はかなり遅いことがわかる。パターン2は逐次よりも若干速くなっている。 この結果から、goroutineの生成はできるだけ抑えてやったほうがよいことが確認できる。 それぞれの実装は次のようになっている。

所感

Goではgoroutineがあってかなりカジュアルにスレッドプログラミング的なことはできるが、並列プログラミング言語のように並列アルゴリズムが書きやすいかというと全くそんなことはない。parallel-for や spawn & sync のような並列処理パターンを言語として取り込むことにはあまり興味がないように思われ、それらを自前で作る程度の能力がないと、Go言語ではまともな並列処理はできない。 Goのgoroutineはあくまでconcurrencyのものであって、並列処理のためのものではないのだろう。

実装

次のテーマ: 並列プレフィックスサムの実装

parallel-for を使って並列プレフィックスサムの実装をする。 その後、並列プレフィックスサムを使った並列パーティショニングを実装する。 その後、並列パーティショニングを使って並列クイックソートを実装する。