【硕士论文】基于SMP的并行游戏树搜索程序负载分析研究.pdf

《【硕士论文】基于SMP的并行游戏树搜索程序负载分析研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、摘要摘要游戏树搜索(Game—treeSearch)一直以来在人工智能领域扮演着极其重要的角色，并行游戏树搜索更是该领域的热点研究问题。本文研究比较了两个典型的并行游戏树搜索算法在两个基于IntelXeon共享内存多处理器(sMP)平台上的性能和负载特征。算法一是最近新出的ParallelRandomizedBest—FirstMinimaxSearch(PRBFM)，算法二是著名的开源棋类游戏Crafty采用的DynamicTreeSplitting算法，其早期的单线程版本是SPEC2000Benchmark测试CPU整数性能的程序之一。我们的试验

2、数据表明Crafty中哈希表操作和动态分裂树操作导致的L3cachemiss成为其多线程程序下的性能瓶颈，导致了极大的扩展性问题，在我们4路和16路的并行系统上，这些操作的时间占到了程序运行总时间的35％50％。相对的，类似的函数在PRBFM算法中仅消耗了大约20％的运行时间。同时，负载特征分析显示，PRBFM相比Crafty在Cachemiss率上要低20--25倍，CacheCoherencemiss率低4～5倍。我们认为这是搜索策略上的根本不同使得PRBFM更加Cache友善，扩展性也更好。晟终，在一系列的测试棋局里面，虽然单线程的PRBFM比

3、单线程的Crafty平均慢2．4～3倍的时间，在中等规模SMP的多线程测试中，PRBFM超过了Crafty。这使得PRBFM成为将来多核处理器(cMP)多线程游戏树搜索BenchMark的一个有力的备选算法。本文在一定程度上揭示了并行树搜索程序在SMP平台上的关键负载特征，为Intel平台设计多核处理器提供了一些数据支持。关键词：负载特征化，性能分析，并行游戏树搜索，SMP，Crafty，PRBFM，电脑国际象棋jjd1.76斗地主极品火龙http://www.doudizhugame.com/http://www.40ok.com/ABSTRACT

4、AbstractGame-treesearchplaysanimportantroleinthefieldofartificialintelligence．Inthispaperwecharacterizeandcomparetwoparallelgame-treesearchWorkloadsinchessOntWOIntelXeon⑧shared-memorymultiprocessorsystems．Oneisarecently-proposedParallelRandomizedBest-FirstMinimaxsearch(PRBFM)al

5、gorithminaChess-playingprogram，andtheotheristhelatestversionofCrafty,astate-of-the-artalpha-beta-basedwhoseolderasachess—playingprogramsequentialversionisknowntypicalgameprograminSPEC2000．Ourdatadisclosesthatthehash—tableanddynamictreespliaingoperationsusedinhavecausedcachemiss

6、eswhichatlastinCraftyhugeL3bringlargescalabilitypenalties．Theyconsume35％--。。50％oftherunningtimeonOur4-waysystem．ByfunctionsofPRBFMonlycostabouttime．Itisthecomparison，similar20％runnillgfundamentallydifferentsearchstrategythatpreventsthosescalabilitypenalties．Ourperformancecharac

7、terizationalsoindicates20～2SXfewercachemissesaswellas4-5XfewercachecoherencemissesusingPRBFM．SoPRBFMismorememory—friendlythanCrafty．Asaresult．althoughforanumberoftestpositionsPRBFMisonaverage2．4—3timesslowerthanCraftyinsequentialperformance，itismuchfasterthanCraftyOilmiddle—sca

8、lemulfi!c}rocessorsystemsduetoitsmuchbetterscalability