電通大がN-Queens問題の最高記録を更新 59
ストーリー by Oliver
女王バトル 部門より
女王バトル 部門より
teltel曰く、"電気通信大学のニュースリリース によれば、同大並列処理学講座は古典的な数学問題のN-Queens 問題の世界最高記録を更新した。
N-Queens 問題は、NxN のチェス板にN個のQueenをお互いに攻撃できないように配置するならば配置のしかたがいくつあるか、という問題で、よくプログラミングの課題になったりする。この問題はN が増えると配置方法も急激に増え、N=23 の解までしか計算されていなかった。電通大のグループはN=24 の解を世界で初めて解いた。
同グループのN-Queens 問題のページ によれば、計算に用いたのはXeon 2.4GHz を搭載した68 ノードのクラスタ。N=24 の解を解くのに22 日かかったという。また上記ページでは、N-Queens 問題を解くプログラムも公開されている。MPI を用いた並列版と1 CPU版が同時にダウンロードできる。タレコみ人が試しに1CPU 版をVine Linux 2.6 上でコンパイルしたところ問題無かった。簡単なベンチマークとしても使えて、N=18 を解くのに1697.538sec かかった。この分だと、N=24 を解くには2000000000sec = 60 年位はかかりそうだ。"
約1年半 (スコア:2, 参考になる)
・メイル読んだりネットサーフィンしながら実行
・コンパイル・オプションで -static をはずす必要があった
ことが注意点。時間はelapsed timeだそうです。
N=13 → 約0.1秒
(N=13..17: 0.57, 3.04, 18.0, 150.0秒)
N=18 → 約974秒
(logとって直線回帰で予想)
N=24 → 約1.59年 (5.01×10^7秒)
こんな感じ。約580日なので、CPUパワーは68CPUの電通大クラスタの1/26? 並列化効率があまり良くないのか?と思いましたが、論文斜め読みでは非常に効率よさそうですね。
N=18の時で比べるとXeon 2.4GHz×68台の1/18。むむ。PowerPC G4 867MHzはXeon 2.4GHzの3倍も早いのだろうか。うーん。なんか計算まちがってるんかな?
Re:約1年半 (スコア:1)
N-Queens実行してみました。
Cygwin上のgcc 3.3.1でmake(gcc -O2と-O3)してみた。
-O3: N=18で 494.742秒
-O2: N=18で 581.913秒
うーん、PowerPCって速いのね。
GUST NOTCH な気分でいこう!
日記にも書いたけど仲間がいたから (スコア:1)
gcc 3.4.2 -O3 -march=opteron
n=18
32bit:551.424s
64bit:489.868s
↓次どうぞ
うすっぺらいコメントがあらわれた! ▼
Re:日記にも書いたけど仲間がいたから (スコア:1)
-O2 -mcpu=750
problem size n : 18
total solutions : 666090624
correct solutions : 666090624
million solutions/sec : 0.556
elapsed time (sec) : 1198.249
x86系と比較すると、クロックの割には早いのかな?
Re:日記にも書いたけど仲間がいたから (スコア:1)
gcc 3.3 -fast
problem size n : 18
total solutions : 666090624
correct solutions : 666090624
million solutions/sec : 1.178
elapsed time (sec) : 565.580
#カミさんのiMacが我が家では最速でした
Re:日記にも書いたけど仲間がいたから (スコア:1)
Linux 2.6.8 (debian sid box)
LAM/MPI 7.1.1
gcc 3.3.4
mpirun options: -ssi rpi sysv -np 3
gcc options: -O3 -march=athlon-mp -fomit-frame-pointer
qn24b MPI version 1.0.0 2004-06-16
problem size n : 18
total solutions : 666090624
correct solutions : 666090624
million solutions/sec : 2.576
elapsed time (sec) : 258.569
Re:日記にも書いたけど仲間がいたから (スコア:0)
qn24b base version 1.0.1 2004-09-02
problem size n : 18
total solutions : 666090624
correct solutions : 666090624
million solutions/sec : 2.072
elapsed time (sec) : 321.523
ベンチマークやってるみたい。
QuadOpteronとかならn=24でもそこそこ現実的な時間でできるんじゃなかろーか。
出遅れ(Re:日記にも書いたけど仲間がいたから) (スコア:1)
qn24b base version 1.0.1 2004-09-02
problem size n : 18
total solutions : 666090624
correct solutions : 666090624
million solutions/sec : 0.773
elapsed time (sec) : 861.848
可もなく不可もなく・・。
Re:日記にも書いたけど仲間がいたから (スコア:0)
gcc -static -O3 -march=pentium-m -fprefetch-loop-arrays -fomit-frame-pointer
1017.8s (n=18)
Re:日記にも書いたけど仲間がいたから (スコア:0)
gcc -static -fbranch-target-load-optimize2 -O3 -march=pentium-m -fprefetch-loop-arrays queens.c -o
elapsed time (sec) : 995.751
Re:日記にも書いたけど仲間がいたから (スコア:0)
-O2 -mcpu=750
elapsed time (sec) : 843.607
Re:日記にも書いたけど仲間がいたから (スコア:0)
n=18: 359
速いのか遅いのか分かりません。
Re:日記にも書いたけど仲間がいたから (スコア:0)
Pen4 1.7GHz FreeBSD5.2.1R gcc 3.3.3のマシンでN=20をやってみました。baseをmakeしたのみ。
qn24b base version 1.0.1 2004-09-02
problem size n : 20
total solutions : 39029188884
correct solutions : 39029188884
million solutions/sec : 0.930
elapsed time (sec) : 41983.733
クラスタでも走らせてみたいなぁ。
Re:日記にも書いたけど仲間がいたから (スコア:0)
適当に作ったMPI環境で、Athlon 650MHz追加時。
MPIはmpich2 0.971, ネットワークは100Base-TX。
クロック数が (1467+650)/1467 = 1.44倍で
速度が 519.590/367.642 = 1.41倍。
きれいにクロッ
Re:約1年半 (スコア:0)
Re:約1年半 (スコア:1)
14002.947 sec でした。N=13 から直線で近似して、予想するとN=24 で約5.4 年(1.7e8 sec) になります。N が増えると、傾きも大きくなる傾向にあるので、これ以上かかりそうです。
# 適当な計算の60 年は嘘でした。
ちなみに、PC はPentium iii 550 MHz で、コンソールのみです。
Re:約1年半 (スコア:1)
↑N-Queenって指数オーダーなの?てかむしろ計算量算出した人まだいないような。
Re:約1年半 (スコア:1)
自分の計算機で実行した時はなにも思いませんでしたが、いま同志社クラスタのデータで見てみると、対数空間での直線よりも上昇が(少しだけど)早いように見えますね(直線と交点が二点あって、下に凸に見える)。アルゴリズムが分かれば計算量は分かるんだけど、やっぱ論文(とソース)読めってことか。
Re:約1年半 (スコア:1)
Re:約1年半 (スコア:0)
Re:約1年半 (スコア:1)
PowerPCバンザイな結論に飛びつくのを我慢して普通に考えればやっぱり、並列化のコストが結構大きいんでしょうかね。論文よく読めってことか...。
タレコミ文 (スコア:1)
> 配置のしかたがいくつあるか、
「互いに攻撃をおこなわないような」N個のQueenと
条件をつければならないのでは?
#タレコミ文を読んだとき、えらく簡単な問題に思えたので
女王様 (スコア:1, 参考になる)
Re:女王様 (スコア:2, 参考になる)
いえいえ、四方八方に攻撃できるのですよ。怖いですねぇ
# 将棋でいう飛車と角行をあわせたようなものなので、その強力さ加減といったら(あぅ
マジレスですが (スコア:1)
王様なら近接している場所でないと喧嘩しないのに、女はやはり難しいです(違
/.configure;oddmake;oddmake install
Re:女王様 (スコア:1)
ですね。
盤上の端から端まで駆け回れますので
Re:女王様 (スコア:0)
王様は360度...と言えるのか?うーん。
Re:タレコミ文 (スコア:0)
# 今は直ってるけど、直したならそう書いてくれりゃいいのに
N-Queensの女王様達は (スコア:1, オフトピック)
#盤上でSMチックな女王様が一触即発の睨み合いを
#繰り広げるひどく殺伐とした状況を思い浮かべた・・・。
答え合わせ (スコア:1)
| printf(" ### Wrong answer?n");
(^^; ちょっぴりウケてしまった
PowerBook G4 1.3GHz で n=18 の時CPU時間 558秒ですた.
みんつ
そういえば…… (スコア:1)
# N Queen の解から N+1 Queen の解は 簡単には作れなさそうね。
-- 哀れな日本人専用(sorry Japanese only) --
Re:そういえば…… (スコア:0)
Re:そういえば…… (スコア:0)
門外漢ならなおさら、示されているリンクくらい読んでから
コメントしましょうね。
Re:そういえば…… (スコア:0)
Re:そういえば…… (スコア:1)
(「お互い」ってなんだ?)
なんとなくですけど (スコア:1)
使えない電通大OBの同僚にイライラしてる人とかはいても出てこなくて結構です。
つらくなるだけですから。僕が。
128cpu (スコア:1, 参考になる)
problem size n : 18
total solutions : 666090624
correct solutions : 666090624
million solutions/sec : 133.044
elapsed time (sec) : 5.007
はやっ!
意外 (スコア:0)
N-Queenには熱心な人が少ないのかな?
# ↓誰かが素数計算なんかとオーダー比べてくれるはず
Re:意外 (スコア:2, 興味深い)
Re:意外 (スコア:0)
9個あたりから、解いた!と思ったら鏡像/回転解で
いつまでたっても増えなかった記憶が…
時間かかりすぎだよね? (スコア:0)
Re:時間かかりすぎだよね? (スコア:0)
プログラムを改造して1つ見付かればすぐ終了するようにしてみたところ、
24の場合1-2分どころか0.01秒未満で発見されました
それはそうでしょう(Re:時間かかりすぎだよね?) (スコア:0)
他の枝でも指摘されている「自明な解」なら人間でも即座に解けますが、、
#もしかして釣られただけ?
Re:それはそうでしょう(Re:時間かかりすぎだよね?) (スコア:0)
本人です
親記事を別の枝と取り違えていました
ごめんなさい
#非常に簡単な解(騎士の並び)はありますが何を間違っても自明じゃないです
Re:それはそうでしょう(Re:時間かかりすぎだよね?) (スコア:0)
地球シミュレータでやって欲しい (スコア:0)
Re:地球シミュレータでやって欲しい (スコア:1)
Re:地球シミュレータでやって欲しい (スコア:0)
Re:地球シミュレータでやって欲しい (スコア:0)
是非ともBlueGeneで(ぇ
Re:地球シミュレータでやって欲しい (スコア:0)