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

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

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

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