基于SMP的并行游戲樹搜索程序負載分析研究.pdf

1、游戲樹搜索(Game-treeSearch)一直以來在人工智能領(lǐng)域扮演著極其重要的角色，并行游戲樹搜索更是該領(lǐng)域的熱點研究問題。本文研究比較了兩個典型的并行游戲樹搜索算法在兩個基于IntelXeon共享內(nèi)存多處理器(SMP)平臺上的性能和負載特征。算法一是最近新出的ParallelRandomizedBest-FirstMinimaxSearch(PRBFM)，算法二是著名的開源棋類游戲Crafty采用的DynamicTreeSplit

2、ting算法，其早期的單線程版本是SPEC2000Benchmark測試CPU整數(shù)性能的程序之一。我們的試驗數(shù)據(jù)表明Crafty中哈希表操作和動態(tài)分裂樹操作導致的L3cachemiss成為其多線程程序下的性能瓶頸，導致了極大的擴展性問題，在我們4路和16路的并行系統(tǒng)上，這些操作的時間占到了程序運行總時間的35％～50％。相對的，類似的函數(shù)在PRBFM算法中僅消耗了大約20％的運行時間。同時，負載特征分析顯示，PRBFM相比Craay在C

3、achemiss率上要低20～25倍，CacheCoherencemiss率低4～5倍。我們認為這是搜索策略上的根本不同使得PRBFM更加Cache友善，擴展性也更好。 最終，在一系列的測試棋局里面，雖然單線程的PRBFM比單線程的Crafty平均慢2.4～3倍的時間，在中等規(guī)模SMP的多線程測試中，PRBFM超過了Crafty。這使得PRBFM成為將來多核處理器(CMP)多線程游戲樹搜索BenchMark的一個有力的備選算法。