読者です 読者をやめる 読者になる 読者になる

東方算程譚

επιστημηがヨタをこく、弾幕とは無縁のCUDAなタワゴト

モンテカルロ法で円周率を求める

二次元平面上、0 < x <= 1, 0 < y <= 1 の領域に、デタラメに点を打ちます。その点と原点(0,0)との距離が1以下であるなら、点は1/4円の内部にあります。

f:id:Episteme:20161016000036g:plain

大量の点 (x[i],y[i]) : i = 0, 1...N-1 をデタラメに打ち、1/4円の中に入った点の数をPとすると、P/N はだいたい π/4 になるハズね。CUDAでやってみましょうね。

// CUDA Runtime
#include <cuda_runtime.h>
#include <device_launch_parameters.h>

// cuRAND
#include <curand.h>

// Thrust
#include <thrust/device_ptr.h>
#include <thrust/reduce.h>

#include <iostream>
using namespace std;

__global__ void kernel_is_in_circle(const float* x, const float* y, 
                                    float* count, unsigned int size) {
  unsigned int i = blockDim.x * blockIdx.x + threadIdx.x;
  if ( i < size ) {
    count[i] = ( x[i]*x[i] + y[i]*y[i] < 1.0f ) ? 1.0f : 0.0f; 
  }
}

int main() {
  const unsigned int N = 1000 * 1000;

  float* x = nullptr;
  float* y = nullptr;
  float* count = nullptr;

  cudaMalloc(&x,     N*sizeof(float));
  cudaMalloc(&y,     N*sizeof(float));
  cudaMalloc(&count, N*sizeof(float));

  curandGenerator_t gen;
  // メルセンヌ・ツイスタ
  curandCreateGenerator(&gen, CURAND_RNG_PSEUDO_MTGP32);
  curandSetPseudoRandomGeneratorSeed(gen, 1234ULL); // seedはテキトーな値

  // 0~1の一様乱数列を生成する
  cout << "--- generating uniform random numbers ---" << endl;
  curandGenerateUniform(gen, x, N);
  curandGenerateUniform(gen, y, N);

  // i番目の点(x[i],y[i])が1/4円の中に入っていれば count[i] = 1
  cout << "--- is the point in the circle? ---" < endl;
  unsigned int block = 256;
  unsigned int grid = (N + block -1) / block;
  kernel_is_in_circle<<<grid,block>>>(x, y, count, N);

  // count[N]の総計をNで割って4倍すれば π になるハズ
  cout << "--- accumulating the result(pi) ---" << endl;
  thrust::device_ptr<float> dev(count);
  float pi = thrust::reduce(dev, dev+N) * 4.0f / N;
  cout << pi << endl;

  curandDestroyGenerator(gen);

  cudaFree(x);
  cudaFree(y);
  cudaFree(count);

}

百万個の点を打って勘定したら 3.14116、まぁいいセンいってんじゃないでしょか。

(original: 2015-04-06)