基于SMP的并行游戏树搜索程序负载分析研究

摘要

游戏树搜索(Game-treeSearch)一直以来在人工智能领域扮演着极其重要的角色，并行游戏树搜索更是该领域的热点研究问题。本文研究比较了两个典型的并行游戏树搜索算法在两个基于IntelXeon共享内存多处理器(SMP)平台上的性能和负载特征。算法一是最近新出的ParallelRandomizedBest-FirstMinimaxSearch(PRBFM)，算法二是著名的开源棋类游戏Crafty采用的DynamicTreeSplitting算法，其早期的单线程版本是SPEC2000Benchmark测试CPU整数性能的程序之一。我们的试验数据表明Crafty中哈希表操作和动态分裂树操作导致的L3cachemiss成为其多线程程序下的性能瓶颈，导致了极大的扩展性问题，在我们4路和16路的并行系统上，这些操作的时间占到了程序运行总时间的35％～50％。相对的，类似的函数在PRBFM算法中仅消耗了大约20％的运行时间。同时，负载特征分析显示，PRBFM相比Craay在Cachemiss率上要低20～25倍，CacheCoherencemiss率低4～5倍。我们认为这是搜索策略上的根本不同使得PRBFM更加Cache友善，扩展性也更好。 最终，在一系列的测试棋局里面，虽然单线程的PRBFM比单线程的Crafty平均慢2.4～3倍的时间，在中等规模SMP的多线程测试中，PRBFM超过了Crafty。这使得PRBFM成为将来多核处理器(CMP)多线程游戏树搜索BenchMark的一个有力的备选算法。 本文在一定程度上揭示了并行树搜索程序在SMP平台上的关键负载特征，为Intel平台设计多核处理器提供了一些数据支持。

目录

文摘

英文文摘

独创性声明及关于论文使用授权的说明

第一章引言

1.1研究动机与意义

1.2作者的主要工作

1.3本文的贡献

1.4章节安排

第二章负载分析及游戏树搜索综述

2.1负载分析综述

2.1.1负载的种类

2.1.2负载分析步骤

2.2游戏树搜索技术综述

2.2.1串行游戏树搜索算法

2.2.2并行游戏树搜索算法

第三章Crafty及PRBFM算法程序介绍

3.1 Crafty程序及算法介绍

3.1.1 Craffy算法描述及程序框架

3.1.2 Crafty函数调用关系图

3.2 PRBFM程序及算法介绍

3.2.1 PRBFM算法描述及程序框架

3.2.2 PRBFM函数调用关系图

第四章游戏树搜索负载构建

4.1软硬件环境及配置

4.2对原PRBFM修改

4.3测试集选择和基线的确定

第五章性能分析和负载特征比较

5.1性能分析方法

5.2扩展性分析

5.2.1 Crafty扩展性分析

5.2.2 PRBFM扩展性分析

5.3存储体系结构分析

5.3.1指令类型分布

5.3.2 Cache利用情况

5.3.3 Cache一致性情况

5.3.4系统带宽利用率

5.4对PRBFM算法进一步分析

第六章PRBFM Xboad Demo

6.1 Xboard简介

6.2 PRBFM Xboard Demo具体实现

6.3配置Xboard，PRBFM和Crafty

6.3.1配置Xboard

6.3.2配置PRBFM

6.3.3配置Crafty

6.4 PRBFM和Crafty实际对弈

6.4.1 Unisys平台上对弈结果

6.4.2 QP平台上对弈结果

第七章总结与展望

7.1总结

7.2展望

致谢

参考文献

在学期间的研究成果