CUDAによる素数リスト生成プログラム

#環境
CUDA　9.0
NVIDIA GeForce GTX960
core i7 5820K
DDR4 32Gbyte

#総当り計算法
##CUDAで総当り計算法を実装
まずは1から引数指定の数まで、順に除算して素数判定する方法で実装する。
https://github.com/jun6231jp/math/blob/master/prime_cuda.cu

ビルド

nvcc -m64 prime_cuda.cu -o prime_cuda.exe -O3

###説明
一度の計算で、unsigned long long int型で1024x1024x16x8個分の領域をグラフィックボード側のメモリ空間に用意。
スレッドごとに自スレッドの番号が素数かどうかを判定する。
1サイクルで各スレッドは1つの数の素数判定をすることになる。
引数で指定した数に達するまで1サイクル1024x1024x16x8個の計算を繰り返す。

###実行例
500000000までの範囲で素数判定を行う。
1024x1024x16x8の倍数で500000000を超える最小数まで計算される。
この場合は0から536870911までとなる。
素数リストはprime_num.txtに書き込まれる。

./prime_cuda.exe 500000000

Range : 0 - 134217727
Processing time: 21444.285156 (msec)
Memory copy time: 175.316101 (msec)
Now Writing...
Range : 134217728 - 268435455
Processing time: 38330.570312 (msec)
Memory copy time: 174.686310 (msec)
Now Writing...
Range : 268435456 - 402653183
Processing time: 48694.289062 (msec)
Memory copy time: 174.285660 (msec)
Now Writing...
Range : 402653184 - 536870911
Processing time: 58622.562500 (msec)
Memory copy time: 174.144485 (msec)
Now Writing...

素数リスト

2
3
5
7
...
(略)
...
536870849
536870869
536870879
536870909

###実行時間

下図のように4200000000を超えたあたりで計算時間が増加している。
これはint(32bit)とlong long int(64bit)の境界と考えられる。
64bitでビルドしているが、アーキテクチャは32bitであることがわかる。

##Cで総当り計算法を実装
prime_cuda.cuと同じ方法で素数リストを作成する。
openMPを用いて、マルチスレッド処理を行う。
https://github.com/jun6231jp/math/blob/master/prime_openmp.c

ビルド

gcc -fopenmp prime_openmp.c -o prime_openmp.out -std=c99 -O3 -lm

##CUDAとCの実行時間を比較
1から134217728(CUDAでの計算の1サイクル)までの範囲の計算時間を比較する。
CUDA(GPU)：21秒
C(CPU)：10分程度

CUDAでの演算の方が速い。
openMPとCUDAとの並列度の差が表れている。

#エラトステネスの篩
##CUDAでエラトステネスの篩を実装
https://github.com/jun6231jp/math/blob/master/prime_cuda_eratosthenes.cu

実行結果

Range : 0 - 134217728
Processing time: 2741.332764 (msec)
Memory copy time: 41.863617 (msec)

計算時間は2.7秒程度。

##Cでエラトステネスの篩を実装
Cでエラトステネスの篩を実装する。
ここでもopenMPを使う。
https://github.com/jun6231jp/math/blob/master/prime_eratosthenes.c

同じく134217728までの範囲で実行時間は1秒程度。

##CUDAとCの実行時間を比較
1から134217728までの範囲での計算時間を比較する。
CUDA(GPU)：2.7秒
C(CPU)：1秒

Cでの演算の方が速い。
エラトステネスの篩は並列度の効果が薄くなる。
そのためコア単体の性能が大きく影響していると考えられる。