?? 解剖大象的眼睛——中國象棋程序設計探索(六)：并行搜索技術探索.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0056)http://www.elephantbase.net/computer/eleeye_parallel.htm -->
<HTML><HEAD><TITLE>解剖大象的眼睛——中國象棋程序設計探索(六)：并行搜索技術探索</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.536" name=GENERATOR></HEAD>
<BODY background=解剖大象的眼睛——中國象棋程序設計探索(六)：并行搜索技術探索_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT face=隸書 size=6>解剖大象的眼睛</FONT><FONT
size=6><STRONG>——</STRONG></FONT><FONT face=隸書 size=6>中國象棋程序設計探索</FONT>
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT>黃晨 <FONT face="Times New Roman">*</FONT> <FONT
face="Times New Roman">2005</FONT>年<FONT
face="Times New Roman">6</FONT>月初稿，<FONT
face="Times New Roman">2005</FONT>年<FONT face="Times New Roman">11</FONT>月修訂
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">( * </FONT>聯系地址：復旦大學化學系表面化學實驗室，<FONT
face="Times New Roman">eMail</FONT>：<A
href="mailto:webmaster@elephantbase.net"><FONT
face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT
face="Times New Roman">)</FONT> </CENTER></DT></DIV>
<DT>
<DT><FONT face=Arial size=5><STRONG>(</STRONG></FONT><FONT face=楷體_GB2312
size=5><STRONG>六</STRONG></FONT><FONT face=Arial size=5><STRONG>)
</STRONG></FONT><FONT face=楷體_GB2312 size=5><STRONG>并行搜索技術探索</STRONG></FONT>
<DT> </DT></DL>
<DL>
<DT> 在閱讀本章前，建議讀者先閱讀《<A href="http://www.elephantbase.net/"
target=_blank>象棋百科全書</A>》網站中《<A
href="http://www.elephantbase.net/computer/outline.htm"
target=_blank>對弈程序基本技術</A>》專題的以下幾篇譯文：
<DT> <FONT face="Times New Roman">(1) </FONT><A
href="http://www.elephantbase.net/computer/advanced_aspiration.htm"
target=_blank>高級搜索方法——期望窗口</A><FONT face="Times New Roman">(Bruce
Moreland)</FONT>；
<DT> <FONT face="Times New Roman">(2) </FONT><A
href="http://www.elephantbase.net/computer/advanced_pvs.htm"
target=_blank>高級搜索方法——主要變例搜索</A><FONT face="Times New Roman">(Bruce
Moreland)</FONT>。 </DT></DL>
<DL>
<DT> 并行搜索是博弈搜索技術中最復雜的組成部分，這就是<FONT
face="Times New Roman">ElephantEye</FONT>沒有采用并行技術的原因。盡管如此，筆者還是在這里簡單地談一下對并行搜索的認識。
<DT>
<DT><FONT face=Arial size=4><STRONG>6.1 </STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>并行計算的基本操作</STRONG></FONT>
<DT>
<DT> 并行計算有兩種體系，一是單機體系，即一個程序在單機的多個處理器上運行，簡稱<FONT
face="Times New Roman">SMP(</FONT>對稱多處理器<FONT
face="Times New Roman">)</FONT>，二是分布式體系，即一個程序在多個計算機聯成的網絡上運行，簡稱<FONT
face="Times New Roman">Cluster(</FONT>計算機集群<FONT
face="Times New Roman">)</FONT>。兩者最大的區別是，單機體系的多個處理器可以共享存儲器<FONT
face="Times New Roman">(</FONT>并且共享同一地址的存儲單元<FONT
face="Times New Roman">)</FONT>，而分布式體系則必須通過網絡來交換信息<FONT
face="Times New Roman">(</FONT>盡管傳輸速度非常高，通常在<FONT
face="Times New Roman">1000MBPS</FONT>以上<FONT face="Times New Roman">)</FONT>。
<DT> 由于博弈搜索需要用到置換表，所以特別適合以<FONT
face="Times New Roman">SMP</FONT>的方式作并行計算。<FONT
face="Times New Roman">Windows</FONT>、<FONT
face="Times New Roman">UNIX</FONT>等多任務操作系統都有線程<FONT
face="Times New Roman">(Thread)</FONT>這個概念，線程是處理器任務的最小單位，一個線程是不可能同時在兩個處理器上運行的，建立線程后，操作系統就會自動把新建的線程分配到空閑的處理器上。<FONT
face="Times New Roman">Windows</FONT>下建立線程的方法是：
<DD>
<DD>#include <windows.h>
<DD>……
<DD>DWORD ThreadId;
<DD>CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) ThreadEntry, (LPVOID)
&ArgList, 0, &ThreadId);
<DT>
<DT> <FONT face="Times New Roman">UNIX</FONT>下建立線程的方式是：
<DD>
<DD>#include <pthread.h>
<DD>……
<DD>pthread_t pthread;
<DD>pthread_attr_t pthread_attr;
<DD>pthread_attr_init(&pthread_attr);
<DD>pthread_attr_setscope(&pthread_attr, PTHREAD_SCOPE_SYSTEM);
<DD>pthread_create(&pthread, &pthread_attr, (void *(*)(void *))
ThreadEntry, (void *) &ArgList);
<DT>
<DT> 這里<FONT face="Times New Roman">ThreadEntry</FONT>僅僅是某個線程的入口，以便整理參數<FONT
face="Times New Roman">ArgList</FONT>并且在線程中調用其他函數。例如，一個用遞歸函數來計算斐波那契數列的并行程序<FONT
face="Times New Roman">(Windows</FONT>版本<FONT face="Times New Roman">)</FONT>：
<DD>
<DD>static volatile int IdleThreads;
<DD>
<DD>struct ArgListStruct {
<DD> volatile bool Active;
<DD> volatile int Value;
<DD>};
<DD>
<DD>static void *ThreadEntry(ArgListStruct *ArgListPtr);
<DD>
<DD>static int Fibonacci(int Arg) {
<DD> if (Arg < 2) {
<DD> return 1;
<DD> } else {
<DD> return Fibonacci(Arg - 2) + Fibonacci(Arg - 1);
<DD> }
<DD>}
<DD>
<DD>static int FibonacciSMP(int Arg) {
<DD> DWORD ThreadId;
<DD> int Result;
<DD> ArgListStruct ArgList;
<DD> if (Arg < 2) {
<DD> return 1;
<DD> } else {
<DD> if (Arg > 30) {
<DD> if (Decrement(&IdleThreads) < 0) {
<DD> Increment(&IdleThreads);
<DD> return FibonacciSMP(Arg - 2) + FibonacciSMP(Arg - 1);
<DD> } else {
<DD> ArgList.Value = Arg - 2;
<DD> ArgList.Active = true;
<DD> CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) ThreadEntry, (LPVOID)
&ArgList, 0, &ThreadId);
<DD> Result = FibonacciSMP(Arg - 1);
<DD> while (ArgList.Active) {
<DD> Idle();
<DD> }
<DD> return Result + ArgList.Value;
<DD> }
<DD> } else {
<DD> return Fibonacci(Arg - 2) + Fibonacci(Arg - 1);
<DD> }
<DD> }
<DD>}
<DD>
<DD>static void *ThreadEntry(ArgListStruct *ArgListPtr) {
<DD> ArgListPtr->Value = FibonacciSMP(ArgListPtr->Value);
<DD> ArgListPtr->Active = false;
<DD> Increment(&IdleThreads);
<DD> return NULL;
<DD>}
<DT>
<DT> 由于<FONT
face="Times New Roman">Fibonacci()</FONT>函數的遞歸形式如同二叉樹一樣擴展開來，所以當處理器有空閑時，就可以把其中一個分枝交給另一個線程，這個操作稱為遞歸樹的分割<FONT
face="Times New Roman">(Split)</FONT>。為此程序需要維護變量<FONT
face="Times New Roman">IdleThreads</FONT>來判斷是否還有空閑的處理器，對該變量的操作必須用<FONT
face="Times New Roman">Increment()</FONT>和<FONT
face="Times New Roman">Decrement()</FONT>函數<FONT
face="Times New Roman">(</FONT>即<FONT
face="Times New Roman">Intel</FONT>處理器的<FONT
face="Times New Roman">INC</FONT>和<FONT
face="Times New Roman">DEC</FONT>原子指令，參閱<FONT
face="Times New Roman"><x86asm.h>)</FONT>，以保證不會因為有兩個線程同時對該變量操作而發生錯誤，這樣的共享變量都應該標記為<FONT
face="Times New Roman">volatile</FONT>屬性，以避免編譯器對這些變量作優化。
<DT> 由于線程的維護需要消耗額外的處理器資源，所以并非每個遞歸結點要作分割的嘗試，以上這段程序的核心問題盡管是<FONT
face="Times New Roman">FibonacciSMP()</FONT>的遞歸，但當遞歸樹不太大<FONT
face="Times New Roman">(</FONT>參數不超過<FONT
face="Times New Roman">30)</FONT>時，調用單純的遞歸函數<FONT
face="Times New Roman">Fibonacci()</FONT>會得到更高的效率。
<DT>
<DT><FONT face=Arial size=4><STRONG>6.2 </STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>加鎖技術和非加鎖技術</STRONG></FONT>
<DT>
<DT> 如果兩個線程同時存取同一存儲單元，就有可能產生錯誤，為此必須建立預防錯誤的機制，通常的措施是加鎖<FONT
face="Times New Roman">(Lock)</FONT>。一個比較簡單的加鎖方法是調用函數<FONT
face="Times New Roman">Exchange()(</FONT>即<FONT
face="Times New Roman">Intel</FONT>處理器的<FONT
face="Times New Roman">XCHG</FONT>原子指令，參閱<FONT
face="Times New Roman"><x86asm.h>)</FONT>，因為兩個線程的原子語句是不可能同時存取同一存儲單元的<FONT
face="Times New Roman">(</FONT>正因為如此，處理器對存儲單元作<FONT
face="Times New Roman">INC</FONT>、<FONT
face="Times New Roman">DEC</FONT>、<FONT
face="Times New Roman">XCHG</FONT>等操作就需要考慮沖突，所以比較耗時<FONT
face="Times New Roman">)</FONT>。在某塊共享的存儲單元中，第一個變量就是加鎖標志，<FONT
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -