日曜研究室 LLVMによるプログラミング言語の実装 xv6ソースコードリーディング 技術 日記
日曜研究室

日曜研究室

まだ庭の小石の数を数え終わっていない

技術

バイトニックソート リベンジ

投稿日
2013/7/2 火曜日
カテゴリー
技術
タグ
著者
Take it easy!

リベンジといっても最適化したんじゃなくてただ実行するマシンを変えてみただけ。

マシンは
CPU: Xeon L3406
GPU: Geforce GTX 460
OS: Ubuntu 13.04
メモリ: 4GB

ちなみに前回は
CPU: Core 2 Duo 2GHz
GPU: Geforce 9400M
OS: Mac OS X 10.8.4
メモリ: 8GB

処理内容は前回と同じく約100万（1024 * 1024）要素のunsigned intのソート。
ソースは前回載せたので今回はなし。

  1. std::sort　約0.10秒
  2. 自分で書いたバイトニックソート（特に最適化無し） 約0.033秒（うちCPU-GPU間メモリコピー約0.003秒）
  3. thrust::sort 約0.033秒（うちCPU-GPU間メモリコピー約0.005秒）

ヤバイ！自分で適当に書いたバイトニックソートがthrust::sortと同じ速さ！
というかGTX 460の懐の深さすごい。

std::sortも全コア（2コア）使い切るようにしたらもう少し速くなると思う。
ただ、std::sort（クイックソート）を普通に使ってるだけでは完全並列に実行するのは不可能だと思うので2倍とかにはならないと思うけど、
CPUにおける並列処理に適したソート方法（並列クイックソートとか？マージソートと組み合わせるとか？）を使えば結構速くなりそうな気はする。

自分のバイトニックソートの書き方は最近のGPU向けとしては間違ってなかったんや！と思ったけど、特に深く考えて実装したワケじゃないのでアレです。

今回thrust::sortは、てきとーバイトニックソートに追いつかれてしまったけど、前回もGeforce 9400Mで同じぐらいの速度（約0.05秒）が出てた事を考えるとやはりすごい。

ちなみに、バイトニックソートの方は値の交換範囲がブロックごとのスレッド数以下のときに共有メモリ上で値を交換するように実装してみたけど、逆に微妙に遅くなってしまったので元に戻した。
これは、Geforce 9400MでもGTX 460でも同じだった。
コアレッシング能力が高いGTX 460で変わらないのは分かるけど、9400Mでもそうなのが解せない。
自分で書いたカーネルなのに、まだグローバルメモリへのアクセスパターンが良くわかってないぽい。

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。