推 jackytsai:看不懂 163.25.118.44 04/26
恩不是當你們找 25 個皇后當女朋友啦,
http://queen0.csie.ntu.edu.tw/
這是我們實驗室在做的研究，我們有很快的演算法，但是在挑戰 Q(24) 的時候，
因為有幾台機器發生硬體錯誤，率先算出來的數據是錯的，因此 credit 稍後被
日本人 Kenji Kise 用 64 CPU 的電腦算出來拿去了。
這是 Kenji Kise 的 paper，用大量的電腦來將答案算出：
http://www.yuba.is.uec.ac.jp/~kis/doc/paper/uec-is-2004-06.pdf
如今我們想挑戰 Q(25) ，而 Kenji Kise 這組人馬卻有了更強大的運算資源，
我們雖然有較快較聰明的演算法，但是我們實驗室沒有足夠的電腦可以彌補之
間的運算差距。因此我來網路上尋求協助善心人士的協助。若您的電腦長時間
開機，願意貢獻您閒置的計算資源，請點最上面的網頁下載軟體！謝謝。
台灣大學資訊工程系 自動推論與數位典藏實驗室
----------------------------------------------------------------------------
台灣大學 25皇后計畫 謝育平 黃光璿 項潔 許德標
2005.04.12
著名的8皇后問題，是：給定一個 8 乘 8 的棋盤，有多少種方法可以將 8 個皇后放進
棋盤中，使得每一行、 每一列、 每一個(左上右下)斜線和(右上左下)斜線中， 至多
一個皇后。而所謂的N皇后問題則是：給定一個 N 乘 N 的棋盤，有多少種方法可以將
N 個皇后放進棋盤中，使得每一行、 每一列、 每一個(左上右下)斜線和(右上左下)斜
線中， 至多一個皇后。我們使用 Q(N) 來表示N皇后問題的解答。下圖表示了 8皇后問
題的一個 排法，而下圖右方則是列出目前已知的Q(N)。 (請參照 Integer Sequence 網
站上所列資料)。
_|Q|_|_|_|_|_|_| N Q(N) N Q(N) N Q(N)
_|_|_|_|_|_|_|Q| 8 92 15 2279184 22 2691008701644
_|_|_|_|_|Q|_|_| 9 352 16 14772512 23 24233937684440
Q|_|_|_|_|_|_|_| 10 724 17 95815104 24 227514171973736
_|_|Q|_|_|_|_|_| 11 2680 18 666090624 25 ？？？？？？
_|_|_|_|Q|_|_|_| 12 14200 19 4968057848
_|_|_|_|_|_|Q|_| 13 73712 20 39029188884
_|_|_|Q|_|_|_|_| 14 365596 21 314666222712
這一兩年，國際間對此一問題產生了極大的興趣，主要是因為N皇后問題本身非常出名
，很適合拿來當成測試和挑戰問題。法國國家電腦和自動化研究院(INRIA) 發展了一套
由Java寫成的網格計算中間軟體，名為ProActive。INRIA 和 歐洲國家電信標準組織
(ETSI)舉辦了 ProAcitve第一屆使用者會議並且選定24-Queen問題作為挑戰的目標，邀
集世界各國NQueen問題的專家齊聚ETSI來解決24Queen問題並且測試ProActive這套軟體
。Philippe Cousin(ETSI)，Partick Rene Guillemin(ETSI)，和Denis Caromel(INRIA)
對此貢獻良多。
這一兩年共有三個團體嘗試計算Q(24)，一個是Kenji Kise，一個是Denis Caromel，一
個是我們(NTU)。Kenji Kise使用64CPU(2.8Ghz)花了21天完成計算。Denis Caromel花了
300台電腦花了17天完成計算。而我們則是花了57天完成計算。但是論快來說，Kenji
Kise花了約 1949 個2GHz PC工作天率先算出，Denis Caromel 花了約 2053 個工作天，
而我們的演算法卻只花 1294 個工作天。
因此我們決定往25-Queen問題出發，根據估計，25皇后問題約需13000~18000個工作天
(PC 2.0Ghz)，是一個相當大的計算，所以希望借重大家的平時沒有使用的CPU計算能力
來幫忙完成。另外希望加入計劃的善心人士能寫封Email給我
(arping@turing.csie.ntu.edu.tw)告知姓名，以便日後在論文中答謝各位。
我們將25皇后問題分成十萬個(100,000)jobs，交由各個 client 程式來完成。各位可以
依據你的機器下載以下不同種類的 client來執行。
FAQ:
1.我可不可以關機? 關機後會有什麼影響?重新開機後會如何?
可以，關機只會損失最後一個正在計算的工作，平均來說約 6 小時，不過一切以您的
方便為第一。
重新開機後，程式會起來到 Server 拿取下一個工作回來做，而損失掉的工作，將在
10萬份工作都指定完後才會回頭指定尚未算完的工作。
Windows Setup:
1.安裝 (為了避免影響公用電腦其他人員使用權利 請勿在公用電腦上放程式 )
1.自動安裝 : 下載 NQueen25.msi 並安裝之(需要已安裝dotNet Framework)。
2.手動安裝 : 直接下載 NTU-NQueen.exe 和 upcc_queen.exe 放在同一個
目錄下，並執行NTU_NQueen.exe 來設定之。
2.安裝後請使用桌面上(或程式集中) 的捷徑 NTU_NQueen來設定控管執行。
NTU_NQueen 僅為管理介面，無關計算 設定執行後 可關閉，
真正的計算是由upcc_queen.exe來完成，須開啟工作管理員來監視。
3.開啟 [工作管理員](Ctrl-Alt-Del T)
在[檢視][選擇欄位](Alt-V S) 加選
[PID] [CPU使用率] [CPU 時間] [記憶體使用量] [基本優先順序] 後按 [確定]
翻開 [處理程序] 確定 upcc_queen.exe 在執行中
4.預設開機後執行一個執行緒(前往 queen0.csie.ntu.edu.tw 63214 提取工作)。
5.可以設定前往 queen0.csie.ntu.edu.tw 63214 或是 23 來提取工作，這主要是要
避開 firewall 設定。
6.可設定執行緒個數，請依CPU及HyperThreading個數來設定(如果不清楚，請設 1 )。
7.可以設定執行時間，其他時間將不執行。
例如 10 - 20 表示每日早上10:00到晚上8:00將幫忙運算，
而 20 - 10 則表示每日晚上8:00到次日早上10:00將幫忙運算。
8.可以設定當電腦正在使用時，不幫忙計算 25-Queen。
Linux Setup:
1.請下載 upcc.ex 至工作目錄
2.為了避免影響公用電腦其他人員使用權利 請勿在公用電腦上放程式
3.請執行 nice -n19 ./upcc.ex 0 &
4.upcc 的參數如右 ./upcc.ex Id Saver TimeBegin TimeEnd Server Port
1.Id: 同一個機器上跑數個 thread 其個別 thread 需有不同的 Id 為一個
數字 0 , 1, 2 ,3,...
2.Saver: 1 (表示機器有在用時(老鼠鍵盤) 不計算25-Queen)
0 (表示進全力幫忙計算)
3.TimeBegin: 每日開始時間
4.TimeEnd: 每日結束時間
5.Server: 拿取工作的機器 請設 queen0.csie.ntu.edu.tw
6.Port: 63214 or 23 (如果有Firewall 問題請設 23 不然請用 63214)
7.所以下面是一個例子
nice -n19 ./upcc 0 0 0 24 queen0.csie.ntu.edu.tw 63214 &
5.詳細指令如下
1.$> wget http://queen0.csie.ntu.edu.tw/upcc.ex
2.$> nice -n19 ./upcc.ex 0 &
3.$> nice -n19 ./upcc.ex 1 & (如果機器是自己的 且有多餘的計算能力)
4.$> top (觀察是否已經在跑)
5.q (離開top)
6.$> logout
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.73.172.178
※ 編輯: growup 來自: 203.73.172.178 (04/26 21:36)