Analysis Of The Smp-based Parallel Game Tree Search Program Load

Game-tree search plays an important role in the field of artificial intelligence. In this paper we characterize and compare two parallel game-tree search Workloads in chess on two Intel Xeon? shared-memory multiprocessor systems. One is a recently-proposed Parallel Randomized Best-First Minimax search (PRBFM) algorithm in a Chess-playing program, and the other is the latest version of Crafty, a state-of-the-art alpha-beta-based chess-playing program whose older sequential version is known as a typical game program in SPEC2000.Our data discloses that the hash-table and dynamic tree splitting operations used in Crafty have caused huge L3 cache misses which at last bring in large scalability penalties. They consume 35%~50% of the running time on our 4-way system. By comparison, similar functions of PRBFM only cost about 20% running time. It is the fundamentally different search strategy that prevents those scalability penalties. Our performance characterization also indicates 20~25X fewer cache misses as well as 4~5X fewer cache coherence misses using PRBFM. So PRBFM is more memory-friendly than Crafty.As a result, although for a number of test positions PRBFM is on average 2.4~3 times slower than Crafty in sequential performance, it is much faster than Crafty on middle-scale multiprocessor systems due to its much better scalability. This makes PRBFM a promising emerging game-tree search algorithm in future Chip MultiProcessor platforms.This thesis discloses some key workload characteristics of tree search applications in some sense, while gives some data support to design Intel platform's Chip MultProcessor.