Go遊会 9日目
今日のテーマ：クイックソートの並列化
Go遊会 4日目 （追記あり） - はで実装したクイックソートを並列化して性能を比較してみる。 並列化のアプローチとしては、分割後の部分配列に対するquick_sortの再帰呼び出しを goroutine で並列に実行するというお手軽アプローチをトライしてみた。 このアプローチでは、配列の分割処理の部分は並列に走らないので、複数コアの演算性能を活用するという意味ではあまり効率はよくない。 また、あまりに小さい部分配列のソート実行にgoroutineを生成しているとgoroutineの生成・管理コストが入力長Nに比例して増えてしまうので、適当なところでgoroutine生成は打ち切って通常のクイックソートに動作を切り替える。
このパターンの単純な分割統治を並列展開するアプローチは、例えば Cilk では spawn と sync によって同期できるが、Go言語には現在実行中のスレッドが生成した子スレッドの終了待ち合わせを行う機能（ Cilk の sync 相当）が直接は提供されていないため、チャネルを使うなりWaitGroupを使うなりして同期を行う必要がある。
あと、Go言語のgoroutineが複数コアで並列に実行されるためには下記のおまじないを書く必要がある。
runtime.GOMAXPROCS(runtime.NumCPU())
測定
quick_sortとparallel_quick_sortの実行時間。横軸は入力データ長。データ長が短いときにはgoroutine生成コストが相対的に大きく、parallel_quick_sortのほうが遅いが、データ長が大きくなると逆転する。
quick_sortに対するparallel_quick_sortの性能向上率。16コアで6.5倍程度なのでやはり効率はいまいち。
N=100,000,000 の入力で parallel_quick_sort を実行した際のCPU利用率を見ると、開始から5.4秒は1コアしか使えていないことがわかる。この部分が、最初に配列を分割するところなので、ここを効果的に並列化することで更なる性能向上が見込まれる。
次のテーマ：クイックソートの並列化続き
もうちょっと真面目に並列化してみる。
