著者

田中 慶悟 藤本 典幸

雑誌

ゲームプログラミングワークショップ2011論文集

巻号頁・発行日

vol.2011, no.6, pp.76-83, 2011-10-28

---

近年,汎用計算ができるようになったGPU上でCUDAを用いて,Somersの高速なN-Queens問題求解アルゴリズムをさらに高速化する手法を提案する.提案手法はN-Queens問題をSomersのアルゴリズムで計算可能かつ独立な部分問題の集合にCPU上で分割し,生成した部分問題をGPUのVRAM上へと転送し,各スレッドへ動的に割り当て,効率よく並列計算を行う.評価実験を行ったところ,NVIDIA GeForce GTX480と2.93 GHz Intel Core i3 CPUを用いた場合,提案手法はSomersのアルゴリズムと比べN=19で24.5倍高速であった.また,GPUを用いたFeinbubeらの既存手法に比べ,提案手法は2倍高速であった.