Help us understand the problem. What is going on with this article?

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であることがわかる。

prime.png

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

jun6231jp
京都大学大学院情報学研究科卒 スーパーコンピュータハード開発チーム所属 電気主任技術者第3種 ネットワークスペシャリスト データベーススペシャリスト 情報安全確保支援士 統計検定準1級
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away