?? 解剖大象的眼睛——中國象棋程序設計探索(六)：并行搜索技術探索.htm

?? 象棋程序設計全資料集(介紹編寫象棋程序的方法思路）
?? HTM
?? 第 1 頁 / 共 2 頁
字號:
12 下一頁
<!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 &lt;windows.h&gt; 
  <DD>…… 
  <DD>DWORD ThreadId; 
  <DD>CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) ThreadEntry, (LPVOID) 
  &amp;ArgList, 0, &amp;ThreadId); 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">UNIX</FONT>下建立線程的方式是： 
  <DD>　 
  <DD>#include &lt;pthread.h&gt; 
  <DD>…… 
  <DD>pthread_t pthread; 
  <DD>pthread_attr_t pthread_attr; 
  <DD>pthread_attr_init(&amp;pthread_attr); 
  <DD>pthread_attr_setscope(&amp;pthread_attr, PTHREAD_SCOPE_SYSTEM); 
  <DD>pthread_create(&amp;pthread, &amp;pthread_attr, (void *(*)(void *)) 
  ThreadEntry, (void *) &amp;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 &lt; 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 &lt; 2) { 
  <DD>　　return 1; 
  <DD>　} else { 
  <DD>　　if (Arg &gt; 30) { 
  <DD>　　　if (Decrement(&amp;IdleThreads) &lt; 0) { 
  <DD>　　　　Increment(&amp;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) 
  &amp;ArgList, 0, &amp;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-&gt;Value = FibonacciSMP(ArgListPtr-&gt;Value); 
  <DD>　ArgListPtr-&gt;Active = false; 
  <DD>　Increment(&amp;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">&lt;x86asm.h&gt;)</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">&lt;x86asm.h&gt;)</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
12 下一頁
?? 文件大小 859 K
?? 上傳用戶 Emouse
?? 所屬分類文件格式
??? 相關標簽

#程序設計 #程序 #編寫
?? 快捷鍵說明

復制代碼 Ctrl + C
搜索代碼 Ctrl + F
全屏模式 F11
切換主題 Ctrl + Shift + D
顯示快捷鍵 ?
增大字號 Ctrl + =
減小字號 Ctrl + -
亚洲欧美第一页_禁久久精品乱码_粉嫩av一区二区三区免费野_久草精品视频

?? 解剖大象的眼睛——中國象棋程序設計探索(六)：并行搜索技術探索.htm

?? 快捷鍵說明
