GPGPUでソート

TopSorter

説明しよう! TopSorterとはGPGPUでソート速度を競いながら遊ぶ知的遊戯である! 様々なサイズのランダム数字列をソートせよ!

参加したい人は/home/tanakh/chunjp/gpusorter/gpusorter.tar.gz を展開し、yoursort.cuを自分の好きなように書き換えて挑戦だ! 17:14に更新したぞ!

整数部門

N=2^20 (1M int = 4M mem)
N=2^24 (16M int = 64M mem)
N=2^26 (64M int = 256M mem)

一様分布と偏った分布を用意する予定

tanakh (bitonic sort)

gpusorter.tar.gz

N = 1048576, dist = even, time = 0.039
N = 1048576, dist = skew, time = 0.039
N = 16777216, dist = even, time = 0.804
N = 16777216, dist = skew, time = 0.804
N = 67108864, dist = even, time = 3.736
N = 67108864, dist = skew, time = 3.737

参考記録(std::sort() -O2)

N = 1048576, dist = even, time = 0.148
N = 1048576, dist = skew, time = 0.099
N = 16777216, dist = even, time = 2.783
N = 16777216, dist = skew, time = 1.850
N = 67108864, dist = even, time = 11.909
N = 67108864, dist = skew, time = 7.821

実数部門

N=2^20 (1M int = 4M mem)
N=2^24 (16M int = 64M mem)
N=2^26 (64M int = 256M mem)

一様分布と偏った分布を用意する予定

tanakh (bitonic sort)

N = 1048576, dist = even, time = 0.039
N = 1048576, dist = skew, time = 0.039
N = 16777216, dist = even, time = 0.804
N = 16777216, dist = skew, time = 0.804
N = 67108864, dist = even, time = 3.737
N = 67108864, dist = skew, time = 3.736

参考記録(std::sort() -O2)

N = 1048576, dist = even, time = 0.163
N = 1048576, dist = skew, time = 0.104
N = 16777216, dist = even, time = 3.026
N = 16777216, dist = skew, time = 1.936
N = 67108864, dist = even, time = 12.745
N = 67108864, dist = skew, time = 8.173

参考記録(thrust::sort() on device)

N = 1048576, dist = even, time = 0.019
N = 1048576, dist = skew, time = 0.015
N = 16777216, dist = even, time = 0.297
N = 16777216, dist = skew, time = 0.292
N = 67108864, dist = even, time = 1.224
N = 67108864, dist = skew, time = 1.243