Design and Evaluation of a Distributed Shared-Hashing Mechanism for Searching Game-Trees in Parallel

在游戏树搜索中，换位表用于消除重复出现（相同或相似）位置的相同计算。换位表也被认为是有效的高效并行搜索。在一个分布式并行计算机集群上，设计、实现、应用并评估了一种组件处理器之间共享全局转置表的新方法。设计、实现并改进了网络连接处理器间通信的基本并行软件系统。全局转置表由分布在处理器上的共享哈希表组成。实验比较了两种类型的共享哈希表。使用两个游戏来评估我们的分布式共享哈希方法。它们是迷你奥赛罗和并行选择。得到了关于这些对策性质的一些理论结果。通过执行一些并行算法，计算了几种开销和计算时间。基于这些实验结果，对我们的方法的各个方面进行了评估。通过比较我们的方法（包括本地哈希表）和本地哈希方法（不包括全局共享哈希表），可以看出加速因子。在处理器数量方面实现了出色的加速。该方法解决了迄今为止尚未在单台计算机上解决的若干并行选择问题。实验证明，在处理器间通信缓慢的分布式并行环境下，我们的分布式共享哈希方法具有足够的效率，可以显示出接近最大值的良好性能

In game-tree searching, transposition tables are used for eliminating repetitions of the identical computation for reappeared (identical or similar) positions. Transposition tables are also expected to be effective for efficient parallel searching. On a distributed parallel computer-cluster, a new method for sharing the global transposition table among component processors is designed, implemented, applied and evaluated.The basic parallel software system for communicating among network-connected processors is designed, implemented and improved. The global transposition table consists of shared-hashing tables which are distributed on processors. Two types of the shared-hashing tables are experimentally compared.Two games are used for evaluating our distributed shared-hashing method. They are mini-othello and parallel selection. Some theoretical results concerning properties of those games are obtained.By executing some parallel algorithms, several kinds of overheads as well as the computation time are counted. Based on these experimental results, various aspects of our method are evaluated. The speedup factor is shown by comparing our method (together with local hashing tables) with the local-hashing method (without the global shared-hashing table). The excellent speedups in terms of the number of processors are achieved. By our method, several instances of the parallel selection problem are solved, which have not been solved so far on a single computer.The experiments prove that our distributed shared-hashing method is efficient enough to show a good performance near the maximum on a distributed parallel environment with slow interprocessor communication