GPU(グラフィックアクセラレータ：要はゲームPC）を使って、NQueens問題のSolverを高速化する試みです。
GPUを使ってNQueens問題を高速化する試みは幾つかあります。
その中で、大阪府立大学(大学院生Keiさん）の研究が最新かつ最良の成果のようです。
以下の成果はその大阪府立大学(大学院生Keiさん）との共同研究です。
deepgreenは初めてGPUのプログラムを組みましたが、CUDA環境は意外と簡単です。
しかし、GPUにも弱点があります。その弱点を如何に補うかが高速化の重要なポイントです。
今回はSomersのアルゴリズムをベースにQJH(oｄｄ）の代表解の選択条件を取り込みを図りました。(QJHについてはこちらを参照）
そのため、ク
イーンの数（N）は奇数のみに限定しています。（プログラム名はnq_symGとしました）
| 【PC】 | 【GPU】NVIDIA GeForce GTX580 | ||
| キャッ シュ容量: 8MB | コア 数 512 | ||
| メモ リ容量：4GB | MPclock数 1.54GHｚ | ||
| グラ フィックスドライバ：270.81 | グ ローバルメモリ容量 : 1.5GB | ||
| OS
:Windows7 Home premium (32ビット版） |
共有 メモリ容量：48KB | ||
| 【開 発環境】 | |||
| コンパイラ：Visual C++ 2008 Express Edition | |||
| CUDA : NVIDIA GPU Computing SDK 3.2 | |||
| クイーン数 | 解 の数 | 求 解時間 | 備 考 |
| 15 | 2,279,184 | 0.22 | |
| 17 | 95,815,104 | 0.50 | |
| 19 | 4,968,057,848 | 9.72 | |
| 21 | 314,666,222,712 | 566.70 | |
| 23 | 24,233,937,684,440 | 43,782.58 | （12H 09M 43S ) |
| 25 | 2,207,893,435,808,350 | 約50 日 | (予 測値） |
| 27 | 未 解決 | 約55 日 x 100台 | (予 測値） |
| Ｎ | 単 一CPUのプログラム | GPU を用いたプログラム | |||||
| Somers版 | 部 分解合成法 | 田 中らの提案手法 | 本 提案手法 | ||||
| 実測値 | 実 測値 | 相対比１ | 実測値 | 実 測値 | 相 対比2 | 相対比3 | |
| 17 | 28.00 | 3.71 | 0.5 | 1.90 | 0.50 | 3.8 | 56.0 |
| 19 | 1,617.00 | 107.00 | 1.0 | 102.40 | 9.72 | 10.5 | 166.4 |
| 21 | 111,425.00 | 5,919.82 | 1.2 | 7,103.24 | 566.70 | 12.5 | 196.6 |
| Home
|