WEKO3
-
RootNode
アイテム
GPUを用いたN-Queens問題の求解
https://ipsj.ixsq.nii.ac.jp/records/78257
https://ipsj.ixsq.nii.ac.jp/records/782575da0971e-88e5-4abd-99e9-ded93fd4ad17
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-GPWS2011011.pdf (268.8 kB)
|
Copyright (c) 2011 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Symposium(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2011-11-04 | |||||||
| タイトル | ||||||||
| タイトル | GPUを用いたN-Queens問題の求解 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Solving the N-Queens Problem on a GPU | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||
| 資源タイプ | conference paper | |||||||
| 著者所属 | ||||||||
| 大阪府立大学大学院理学系研究科 | ||||||||
| 著者所属 | ||||||||
| 大阪府立大学大学院理学系研究科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Prefecture University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Prefecture University | ||||||||
| 著者名 |
田中, 慶悟
藤本, 典幸
× 田中, 慶悟 藤本, 典幸
|
|||||||
| 著者名(英) |
Keigo, Tanaka
Noriyuki, Fujimoto
× Keigo, Tanaka Noriyuki, Fujimoto
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 近年，汎用計算ができるようになった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倍高速であった． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In recent years, GPUs have acquired the ability to perform general purpose computation. In this paper, for CUDA GPUs, we propose a method to parallelize Somers' fast sequential algorithm to solve the N-Queens problem. The proposed method partitions a given instance of the N-Queens problem into sub-problems which can be computed in parallel. Then, the sub-problems are sent to VRAM on a GPU so that each sub-problem is dynamically allocated to a thread. Experimental results on an NVIDIA GeForce GTX480 and a 2.93 GHz Intel Core i3 CPU show that the proposed method solves the 19-Queens problem 24.5 times faster than Somers' sequential algorithm and that the proposed method is twice faster than Feinbube et al.'s existing method for CUDA GPUs. | |||||||
| 書誌情報 |
ゲームプログラミングワークショップ2011論文集 巻 2011, 号 6, p. 76-83, 発行日 2011-10-28 |
|||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
