対称解の特性を用いた N-Queens 問題の求解とGPU による高速化

萩野谷 一二田中 慶悟 *1
藤本 典幸 *1

*1 大阪府立大学

大学院理学系研究科~1~

情報数理科学専攻

1. はじめに
1.1 N-Queens 問題とは
1.2 Somers のアルゴリズム
1.3 解の区分
1.4 Seed~2~

1.1 N-Queens 問題とは
Q
Q
Q
QQ
Q
Q
Q

・ N x N のチェス版に N 個のクイーンを配置。互いに攻撃し合わない配置の総数を求める問題
・N=26 までの解の総数は既知
・N=27 以降の解の総数は未解決
・解法：Somers アルゴリズムが有名
・高速化：対称解の取り扱いがポイント（上下／左右反転・回転操作などの対称変換による別解)【最近の取り組み】
 田中らの GPU を用いた高速化の提案
 新アルゴリズム「部分解合成法」の提案~3~

1.2 Somers のアルゴリズム
 左右反転解を考慮して探索量を半減 スタックを利用したループ制御（GPU では関数の再帰呼び出し不可）
スタック情報：クイーンの効き筋の管理(u, r, l, bitmap の 4words が標準)
l [x ]：左下方向の効き筋

r[x ]：真下方向の効き筋Q

u[x ]：右下方向の効き筋

Q

QQ

Q
Q

l[x]
l[x+1]l [x +1] = ( l [x ] | bi t) >> 1

Q
Q

r[x]
r[x+1]

r[x +1] = r[x ] | bi t

bi tma p[x ]：ク イー ンの配置可能な位置Qu[x]u[x+1]

u[x +1] = ( u[x ] | bi t) >> 1

bi tma p[x +1] = ma s k & ~ ( u[x +1] | r[x +1] | l [x +1])

スタックの深さ：GPU 側でクイーンを探索するとき必要な行数
ス タ ッ ク 域：スタック情報 ×スタックの深さの配列（高速な共有メモリに配置）
共有メモリは小容量のためスレッドの多重度を制約する要因~4~

1.3 解の区分
対称解による区分(上下反転、左右反転、回転操作による解分類)
type-a：非回転対称解（8 つの対称解が存在するもの）
type-b：180°回転対称解（4 つの対称解が存在するもの）
type-c：90°回転対称解（2 つの対称解が存在するもの）
代表解：対称解を生成する元となった解
type-atype-ｂQ

type-ｃ
Q

Q

Q

Q
Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q

Q
Q

Q

Q

Q

Q

Q
Q
Q
Q

Q

Q
Q

Q

Q
Q

Q

N-Queens 問題の解は殆どが type-a~5~

1.4 Seed
Seed：CPU から GPU へ探索を引き継ぐための情報Seeds 全体として、生成される解の重複・欠落がないこと
ex.

u,r,l,bitmap の 4words が標準的な情報（bitmap は必須情報ではない）
Seeds 削減の施策では 4word 目を別の情報に使用【Seed の区分】
Seed-A：type-a の代表解を生成する Seed
解の総数を求める際、探索で得られた解の数を 8 倍して集計
Seed-B： 左右反転、斜軸反転(上下反転＋90°回転)により生成される解を代表する Seed
解の総数を求める際、探索で得られた解の数を 4 倍して集計
type-b の代表解を生成する Seed ／ 2 つの Seeds で Seed-A を代用するケース
Seed-C： 左右反転により生成される解を代表する Seed
解の総数を求める際、探索で得られた解の数を 2 倍して集計
type-c の代表解を生成する Seed／4 つの Seeds で Seed-A を代用するケース／
2 つの Seeds で Seed-B を代用するケース~6~２．関連研究と提案手法の概要
2.1 田中らの提案手法の概要
2.2 新アルゴリズム「部分解合成法」の概要
2.3 本提案手法の基本構想
2.4 本提案手法の概要
2.5 本提案手法の主な取り組み
2.6 本提案手法と田中らの提案手法との比較~7~

2.1 田中らの提案手法の概要
Q① m行までのクイーンの配置を決定② 求めたクイーンの配置を4バイトに符号化して格納

Q
Q(対象解を考慮し、探索量を半減)CPU

最終結果 (解の総数）

通信量の最小化Q③ VRAMへ一括転送④ GPUを起動⑪ 探索結果をVRAMから取り出し結果を２倍して総数を得る

VRAM

Q
Q

GP
U

⑤ 符号化データを取り出し各スレッドのQ⑩ 探索結果を集計

負荷の均等化QQ

GPUの探索範囲(N-m）行

Q

スタック域(共有メモリ)⑥ クイーンの配置を復元し⑦ スタック情報（u,r,l,bitmap)を再生⑧ Somersアルゴリズムで解の探索⑨ ⑤～⑧を繰り返し、すべての符号化データを処理する

QQ

共有メモリのバンク衝突の防止

各スレッド毎に１つ~8~2.2 新アルゴリズム「部分解合成法」の概要①解の類別とその判定方法(代表解の選択条件)②部分解から全体解を合成する手順の提示【解の類別と代表解の選択条件】（クイーンの数(N)が奇数の場合）
type Ⅰ

type Ⅱ

ＡＢ
Ｑ

Ｄ

Ａ

Q

Ｂ

ＱＣＤ

Ｃ

typeⅠ：クイーンが中央に１つ配置された形（type-a~type-c の解の可能性がある）
typeⅡ：2 つのクイーンが配置された形（type-a の解のみ）

typeⅡの解の代表解の選択条件：I＜J＜n を満たす解 (type-a の代表解)
ただし、n=(N-1)/2、 中央の行・列のクイーンの位置を (n,I), (J,n)
 探索量を約 1/8 に削減（解の殆どは type-a）(Somers アルゴリズムの約４倍の削減効果)~9~

2.3 本提案手法の基本構想
田中らの提案手法をベース（GPU 版 Somers アルゴリズム）＋（クイーンの数を奇数に限定）
部分解合成法の「代表解の選択条件」の取込み

狙い：探索量の大幅な削減（Somers：1/2  部分解合成法：約 1/8）

~ 10 ~

2.4 本提案手法の概要
代表解の選択条件Q① ｎ行までのクイーンの配置を決定(n=(N-1)/2② 求めたクイーンの配置を
スタック情報からSeedを生成し、各Seedの区分別に格納

Q
Q

CP
Uの適用
Seed-A 用

Q
Seed-B 用
Seed-C用

突き放し制御③ Seedsが一杯のバッファをVRAMへ転送④ GPUを起動(非同期処理)CPU と GPU の適切な最終結果 (解の総数）⑩ 探索結果をVRAMから取り出し結果をSeedの区分の応じて集計⑪ すべてのSeed生成がおわるまで、②～⑪を繰り返す(分割処理）

役割分担

Q

VRAM

QQGPU⑤ Seedを取り出し

各スレッドのQ⑨ 探索結果を集計

負荷の均等化QQ

GPUの探索範囲((n＋２)～ｎ)行

Q

スタック域(共有メモリ)

Q
Q

共有メモリの使用量削減
・スタックの深さ

共有メモリの・スタック情報

バンク衝突の防止

各スレッド毎に１つ~ 11 ~( 各スレッドの処理）⑥ スタック情報と探索範囲を設定⑦ Somersアルゴリズムで解の探索⑧ ⑤～⑦を繰り返し、すべてのSeedsを処理する

2.5 本提案手法の主な取り組み
主な取り組み①（I,J）フィルタ（「代表解の選択条件」を取込み）
中央行までの探索を行い、代表解の選択条件を適用
以降の探索量を約 1/8 に削減② CPU/GPU の役割分担の最適化
前半の複雑な探索処理(代表解の選択条件の適用)は CPU 側
後半の単純・大量の探索処理を GPU 側③ CPU/GPU の並行処理
CPU 側の処理と GPU 側の処理を並行して実行④ 共有メモリ使用量の削減（64 ビットレジスタの活用）
スタック情報を 4words から 2words に削減
田中らの提案手法からの継承⑤ 多数スレッドに対する負荷の動的配分（負荷の均等化）⑥ 共有メモリのバンク衝突の防止~ 12 ~

2.6 本提案手法と田中らの提案手法との比較
項番 比較項目
1 クイーンの数の制限
2 探索量の削減
3 CPU側の探索行数(m)4 GPUの起動回数
5 負荷（Seed)の動的割り当て
6 共有メモリのバンク衝突防止

田中らの提案手法なし
m=5 (最適値に設定）
一括処理
あり
あり

本提案手法
奇数に限定
1月2日 約1 / 8
m=n～n-2 但し、n=(N-1)/2分割処理あり(田中らの提案手法を踏襲)あり(田中らの提案手法を踏襲)

78

Seedsの総数(N=19の場合）
Seedの情報量

232,1744バイト(符号化)約100M個
4バイト x 4910

スタック情報スタックの深さ

4バイト x 4
N-5

4バイト x 2
n+2～ｎ 但し、n=(N-1)/2

11

スレッドの多重度

64 x 32

96 x 64

1213

CPU/GPUの負荷バランス
CPU/GPUの並行処理

CPUは無視できるレベルなし(不要)

負荷バランスが重要あり（補足）Seeds に対する考え方
 多数のスレッドに均等な負荷を提供（既存手法)
 CPU と GPU との協調作業の媒介(トータルな負荷バランス)~ 13 ~

3. 提案手法の詳細
3.1 施策１: (I,J)フィルタ(代表解の選択条件の取込み)

3.2 施策 2：K-line 設定による Seeds の削減
3.3 K-line 設定時の Seed 生成論理
3.4 施策 3：簡易フレームチェック
3.5 Seed 情報とその扱い
3.6 CPU/GPU の適切な役割分担
3.7 施策 4 : CPU/GPU の並行処理
3.8 施策 5 : 64 ビットレジスタの活用
3.9 int4 データ型の利用~ 14 ~

3.1 施策１: (I,J)フィルタ(代表解の選択条件の取込み)

Seeds 生成処理
CPU 側で深さ 0～ｎ(= (N - 1) / 2 ) 行まで探索し、中央の行、列に配置されたクイーンの位置 (n,I), (J,n) を決定 I=J=n の場合：Seed-C を生成 (左右対称解を考慮し生成は半分とする)
typeⅠの解である（type-a～type-c の解の可能性がある）
 I<J<n の場合：Seed-A の生成
typeⅡの代表解である
 上記以外の場合：Seed の生成は不要
typeⅡの解であるが、代表解ではない（補足）大量の Seeds 生成に対応するため分割処理方式を採用
Seed-A, Seed-C の生成およびその扱いは後述~ 15 ~

3.2 施策 2：K-line 設定による Seeds の削減
K-line：Seed 生成を開始する行（中央行までの探索を待たずに Seed 生成を開始）
case1: K-lineより先に中央列のクイーンが決まる場合

case3: 中央行の中心に中央列のクイーンが決まる場合

0101
QKlineｎKlineｎQGPU 側の対処
①探索の深さを可変②中央行のクイーンの配置を制限

case2: K-lineと中央行の間に中央列のクイーンが決まる場合
01

Seeds生成の開始ライン
Kline

GPUの探索範囲

Qｎ

中央列のクイーンの制約により、中央行のクイーンの配置が可能な範囲~ 16 ~

3.3 K-line 設定時の Seed 生成論理記号の定義
K：Seed 生成を開始する行
n = (N-1) / 2
I：中央行のクイーンの位置
J：中央列のクイーンの位置
n e s t ：CPU 側の探索処理中の深さ(0~(n-1))
 nest < K の場合： 探索を継続 K ≦ nest & nest < n-1 の場合 ：J が確定：(case1)、Seed-A の生成
J が未確定：探索を継続 nest = n-1 の場合
J が確定：(case2)、Seed-A の生成
J が未確定：中央にクイーンを配置したものとして Seed-C の生成（ただし、左右対称解を考慮し生成は半分のみとする）【Seed-A の生成】（K-line 設定用）
u, r, l に続けて 4word 目には bitmap の代わりに J と d=max(J,K)を設定
J：GPU 側の探索で中央行のクイーンの位置を制限する情報
d：GPU 側の探索の深さを規定する情報~ 17 ~

3.4 施策 3：簡易フレームチェック（typeⅠの解の Seeds 削減策）
A

B

Ｐ

Ｑ
★

Ｓ

★：中央に配置されたクイーン

c

P,Q,R,S:b

中央の行・列により分割された各領域#(P),#(Q)：P,Q それぞれに配置されたクイーンの数
フレーム A,B の定義

Ｒ

A:P に配置されたクイーンの列方向のビットマップ
B:P に配置されたクイーンの行方向のビットマップ

 #(P) = #(Q)：Seed-C の生成（ただし、左右対称解を考慮し生成は半分のみとする）

 #(P) < #(Q)：A < B のとき、Seed-B の生成
A = B のとき、Seed-C の生成
A > B のとき、Seed の生成は不要
 #(P) > #(Q)：Seed の生成は不要~ 18 ~

3.5 Seed 情報とその扱い
記号の定義
K Seed 生成を開始する行
J 中央列のクイーンの位置
N クイーンの数

Seed情報GPUの探索の深さ
CPU側の処理
その他

ｎ＝（N – 1） / 2
d = max(J,K)

Seed-A
Seed-Bu, r, l, (J,d)
u, r, l, bitmap
N-dｎ
8 倍して集計4 倍して集計
中央行のクイーンの位置を J 未満に制限~ 19 ~

Seed-Cu, r, l, bitmapｎ
2 倍して集計

3.6 CPU/GPU の適切な役割分担
GPU の特性 単純で大量処理に向いている if 文などが多用される複雑な処理は苦手（スレッド分散）
 CPU/GPU それぞれの得意分野を分担
CPU：前半の複雑な処理(Seeds 生成処理)
GPU：後半の単純・大量の探索に専念
メリット：GPU 側の探索が浅くなる(スタック域(=共有メモリ)の削減スレッド多重度の向上)
懸念事項：CPU 側の処理が重すぎないか ？

~ 20 ~

3.7 施策 4 : CPU/GPU の並行処理
求解時間の内訳（N=19 の場合）
各処理部
Seeds生成部
GPU制御部
カーネル関数部
求解時間

処理時間(s)
5.12
0.59
17.4
23.11

CPU 側
GPU 側

Seeds 生成部の処理時間（5.12 秒）は、全体の 22%（無視できないレベル）
Seeds 生成部を別スレッド化し、GPU 側の探索処理と非同期に動作
凡例

Seeds生成部
GPU制御部

カーネル関数部

CPU・・・

GPU・・・~ 21 ~

3.8 施策 5 : 64 ビットレジスタの活用
スタック情報の変更： 4 words 構成（u,r,l,bitmap）  2words 構成
 b(クイーンの位置情報), bitmap の 2words
 u,l の代わりに 64 ビットレジスタ(uu,ll)を使用
 r の代わりに 32 ビットレジスタ(rr)を使用
push 操作
bit = －bitmap[x] & bitmap[x]bitmap[x] ^= bitb[x+1] = bit
uu = (uu | bit) << 1
rr = rr | bitll = (ll | (bit<<32)) >> 1
bitmap = mask & ~(uu | rr |( ll>>32))x++

pop 操作
x-bit = b[x]uu = (uu >> 1) ^ bit
rr = rr ^ bitll = (ll <<1) ^ (bit<<32)

共有メモリの使用量が半減 共有メモリへのアクセス回数の削減
 スレッド多重度の倍増~ 22 ~

3.9 int4 データ型の利用
Seed は 4 words 構成（田中らの提案手法では 1 word） 性能劣化の懸念（GPU のグローバルメモリアクセスは数百クロックと非常に遅い）

int4 データ型の利用（4words を 1 回のメモリアクセスで可能）
int4 に変更しても性能差はなし(効果なし)
Fermi アーキで追加された L2 キャッシュの効果？



Seed を 4words 構成にしても性能面での問題はない~ 23 ~

4. GPU のチューニング
4.1 CPU/GPU 間の負荷の最適化
4.2 CPU/GPU 間の通信オーバヘッド
4.3 MPSZ（スレッドブロック数）と求解時間の関係~ 24 ~

4.1 CPU/GPU 間の負荷の最適化
K-line 設定値と求解時間の変化(N=19 の場合)
K-line設定値
Seeds総数
スタックの深さ
スレッドブロック数
求解時間（ｓ）
Seeds生成部（ｓ）
GPU制御部（ｓ）
カーネル関数部（ｓ）

ｎ約383M個
1311246.4422.881.51
22.05

n-1
約255M個
1496
29.53
7.25
1.03
21.24

n-2
約131M個
159623.62
5.400.51
17.72

n-3約104M個
169622.91
4.93
0.25
17.72

n-4約100M個
1780
27.86
4.88
0.2222.78

ただし、n = ( N – 1 ) / 2

K-line の値の減少  Seeds 総数が減少
 CPU 側(Seeds 生成部)の負荷は減少
GPU 側(カーネル関数部)の負荷も減少（GPU 側の負荷減少の理由は、Seeds 取り込み回数の減少）
その後、GPU の探索が深くなるとスレッドの多重度が下がり、性能低下

K-line の最適値は、n-2, n-3~ 25 ~

4.2 CPU/GPU 間の通信オーバヘッド(GPU 制御部の処理時間)
 GPU の起動・終了時間

 36μs 程度 / 1 回（問題なし）

 Seeds を GPU（VRAM）に転送する時間
N が小：問題なし（N=19 の場合、求解時間 9.98 秒の約 5%）
N が大：PoolSize を大きくすると若干の改善あり(非同期処理の待ち合わせ時間の減少)

PoolSize と求解時間の関係(N=21 の場合)

PoolSize
Seeds総数
求解時間(s)

1.0M
604.5

2.5M
5M
2608M個 ( 41.7GB)
591.6
586.3

10M
584.1

N が 21 以上では、PoolSize＝10M 程度がよい~ 26 ~

4.3 MPSZ（スレッドブロック数）と求解時間の関係
BLKSZ=32 に固定し MPSZ を 16 の倍数で変化（N=19 の場合）
MPSZ
6480
96112128144160192

求解時間(s) 求解時間２(s)（2words）（2words）
17.73
10.87
14.78
12.8311.71
10.8210.82
10.85
10.85

10.159.98

参考値(s)（4words）
23.00
18.92
16.19

参考値は、スタック情報に4words を使用した時の測定値。
この時、MPSZ の最大値は 96。

再測定
BLKSZ=64
１MP 当たりの常駐ブロック数の最大値

最新版の MPSZ の最大値は 192(12x16)だが、
 MPSZ=128 以降はほぼ横ばい(アーキの制限：8 x 16 = 128 が上限)
 BLKSZ=64 で再測定し、若干の改善あり(求解時間２)~ 27 ~

5. 評価実験
5.1 評価環境
5.2 最新版の求解時間
5.3 他のプログラムとの比較
5.4 各施策の効果（N=19 の求解時間の推移）
5.5 各施策の効果(改善率)~ 28 ~

5.1 評価環境【GPU】NVIDIA GeForce GTX580【PC】
CPU:Intel Core i7 2600 3.4GHz CPU

MP数 : 16キャッシュ容量: 8MB

コア数 : 512

メモリ容量：4GBMPclock数 : 1.54GHｚ

グラフィックスドライバ：270.81

グローバルメモリ容量 : 1.5GB

OS :Windows7 Home premium

共有メモリ容量：48KB / MP(32ビット版）【開発環境】
コンパイラ：Visual C++ 2008 Express Edition
CUDA : NVIDIA GPU Computing SDK 3.2【GPU パラメタの定義】（共有メモリの必要量などは“N=27 まで測定可能な範囲”に設定）
 MPSZ：スレッドブロック数

 BLKSZ：スレッドブロック当たりのスレッド数

 Queens：GPU 側の探索の深さ(N=27 探索時のスタックの深さ) PoolSize ：Seeds の分割単位(GPU への 1 回の転送の最大数)~ 29 ~

5.2 最新版の求解時間
1517192123

解の数
2,279,184
95,815,104
4,968,057,848
314,666,222,71224,233,937,684,440

25
272,207,893,435,808,350
未解決

クイーン数

求解時間(s)
備考
0.20
0.51
9.98
591.5645818.24 (12H 43M 39S)
約50日 (予測値）
約60日 x 100台 (予測値）

GPU のパラメタ：MPSZ=96, BLKSZ=64, Queens=16, PoolSize=2500000
N=23 までは実測値 (ただし、N=23 は PoolSize=10M で測定)

 N=23 の求解時間：電通大の PC クラスタ(Intel Pentium4 Xeon 2.8GHz
CPU x 68）の求解時間(56.9H)に較べて、約 4.5 倍高速
 N=27 の求解時間の予測値：100 台ｘ約 60 日
N=19～23 の求解時間の伸び率は、解の総数の伸び率に比例
N=25,27 の求解時間は、この関係を利用して求めた予測値~ 30 ~

5.3 他のプログラムとの比較
Ｎ171921

単一CPUのプログラム
GPUを用いたプログラム
部分解合成法
本提案手法
Somers版[3]田中らの提案手法
実測値(s)
実測値(s) 相対比１
実測値(s)
実測値(s)
相対比228.00
3.71
0.5
1.90
0.51
3.7
1,617.00
107.001.0
102.409.98
10.3
111,425.00
5,919.82
1.2
7,103.24
591.5612.0

相対比354.9
162.0
188.4

田中らの提案手法：MPSZ=64,BLKSZ=32,Queens=22
本提案手法：MPSZ=96,BLKSZ=64,Queens=16,PoolSize=2500000
相対比 1 : 田中らの提案手法 / 部分解合成法
相対比 2 : 田中らの提案手法 / 本提案手法
相対比 3 : Somers / 本提案手法

 田中らの提案手法との比較：10.3～12.0 倍高速
また、クイーン数の増加に伴い改善効果も向上
 単一 CPU との比較：Somers 版の 162～188 倍高速 部分解合成法は GPU を使った田中らの提案手法と同等以上の性能~ 31 ~

5.4 各施策の効果（N=19 の求解時間の推移）
田中らの提案手法

120.00（秒）
102.40100.00施策１80.00

部分解合成法の効果（I,J）フィルタ他
約5倍

60.00
46.50

46.43

施策４

40.00

施策５29.33
23.11

22.24
17.12

20.00

16.15
9.98

施策２
施策３

0.00

~ 32 ~

最新版

5.5 各施策の効果(改善率)
田中らの提案手法
初版
施策１
第0.1版
第0.2版 施策2
第0.3版 施策2
第0.4版 施策3
第0.5版 施策4
第0.6版
最新版 施策5求解時間(s)102.40
46.50
46.43
29.33
23.11
22.24
17.12
16.159.98

改善率
0.55
0.00
0.37
0.50
0.04
0.23
0.06
0.38

備考
参考値
(I,J)フィルタ Seeds=383M個
int4データ型の利用
K-line(n-1) Seeds=255M個
K-line(n-2) Seeds=130M個
簡易フレームチェック Seeds=100M個
CPU/GPUの並行処理
電通大アルゴリズムの採用
64ビットレジスタの活用

改善率：1 －改善後 / 改善前①施策１の効果：55%

探索量の差は約 4 倍弱なので、改善率 55%ではまだ不十分②施策 2 の効果：50%

Seeds 生成処理の軽減とカーネル関数部の Seeds 取込み処理の削減③施策 3 の効果： 4%

１つの Seed の重さ(必要となる計算量)が軽いため効果小④施策 4 の効果：23%

CPU 側の Seeds 生成処理時間の削減⑤施策 5 の効果：38%

共有メモリへのアクセス回数の減少および多重度の向上の相乗効果~ 33 ~

6. まとめ本提案手法
 田中らの提案手法をベース
 クイーンの数（N）を奇数に限定
 Somers アルゴリズムと部分解合成法の「代表解の選択条件」との融合
 CPU と GPU の協調作業（適切な役割分担、並行処理）成果 田中らの提案手法に較べて 10.3～12.0 倍
 Somers アルゴリズム(単一 CPU)との比較では 162～188 倍
 N=23 の求解時間は、電通大の PC クラスタ（Intel Pentium4 Xeon 2.8GHz
CPU x 68）の約 4.5 倍高速

今後の課題 N=27 への挑戦（環境が整えば)： GPU 付き PC 100 台 x 60 日程度~ 34 ~

補遺 最新版(論文提出後)の求解時間
スタック情報 b, bitmap を int2 データ型に変更約４％の改善（実行ステッ数の削減効果がバンク衝突のペナルティをカバー）

15171921
23

解の数
2,279,18495,815,104
4,968,057,848314,666,222,712
24,233,937,684,440

25
272,207,893,435,808,350
未解決

クイーン数求解時間(s)備考
0.22 <--0.20
0.50 <--0.51
9.72 <--9.98
566.70 <--591.56
43782.58 <--45818.24(12H 09M 43S)
約50日 (予測値）
約55日 x 100台 (予測値）

GPU のパラメタ：MPSZ=96, BLKSZ=64, Queens=16, PoolSize=2500000
N=23 までは実測値 (ただし、N=23 は PoolSize=10M で測定)
 N=23 の求解時間：電通大の PC クラスタの約 4.7 倍高速
 N=27 の求解時間の予測値：100 台ｘ約 55 日

 単一 CPU との比較 166～196 倍高速
 田中らの手法との比較 10.5～12.5 倍高速~ 35 ~ご清聴ありがとうございました

本論文で実験に使用したプログラム(nq_symG)のソースを下記の Web サイトにて公開予定

http://deepgreen.game.cocon.jp/nqueens_index.html~ 36 ~