📄 解剖大象的眼睛——中国象棋程序设计探索(六)：并行搜索技术探索.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 + -