In principal variation splitting, all processors recursively analyze the first move, with the remaining moves being examined using a null window by individual processors using a local refutation table that is updated after each iteration of the ID search. The transposition table can be accessed either on a global (stored in the supervisor processor increasing communication overhead) or local basis.
Performance
The program was tested performing 5- and 6-ply searches on 24 positions of the Bratko-Kopec Test with various transposition table implementations. Despite huge savings in nodes visited using the global table, the increased communication overhead by far decreased the net result, and only a depth limited shared table (depth < 3) came close to the performance of a local, depth limited transposition table, which turned out best for this hardware configuration - speedup with standard deviation (σ) as given in the 1983 paper [7] .
Tony Marsland, Tim Breitkreutz, Steve Sutphen (1991). A Network Multiprocessor for Experiments in Parallelism. Concurrency: Practice and Experience, Vol. 3, No. 3, pp. 203-219. pdf
^Tony Marsland, Tim Breitkreutz, Steve Sutphen (1991). A Network Multiprocessor for Experiments in Parallelism. Concurrency: Practice and Experience, Vol. 3, No. 3, pp. 203-219. pdf
an experimenatal chess program of the early 1980s developed by Fred Popowich and Tony Marsland at University of Alberta, written in C, to research on parallel search. In partcicular addressing search overhead and communication overhead, the speedup of principal variation splitting with various setups was investigated, later revised by Tim Breitkreutz et al. to run Parabelle under network multiprocessor package (NMP), a PVM-like message passing library [1]. Parabelle was initially based on Ken Thompson's program TinkerBelle [2] [3] , and was itself base for further projects such as the program Abyss, which was subject of research on selective search extensions in the domain of Chinese Chess, and also played tournaments [4] .
Table of Contents
Description
The basis of both the sequential and parallel chess programs was an iterative deepening (ID) framework with transposition table and refulation table performing a principal variation search. The test framework was a 68000 based MIMD system [6] with under today's standards extremely slow interprocess communication through serial lines at 4800 or 9600 baud.In principal variation splitting, all processors recursively analyze the first move, with the remaining moves being examined using a null window by individual processors using a local refutation table that is updated after each iteration of the ID search. The transposition table can be accessed either on a global (stored in the supervisor processor increasing communication overhead) or local basis.
Performance
The program was tested performing 5- and 6-ply searches on 24 positions of the Bratko-Kopec Test with various transposition table implementations. Despite huge savings in nodes visited using the global table, the increased communication overhead by far decreased the net result, and only a depth limited shared table (depth < 3) came close to the performance of a local, depth limited transposition table, which turned out best for this hardware configuration - speedup with standard deviation (σ) as given in the 1983 paper [7] .See also
Publications
External Links
References
What links here?
Up one Level