A Performance Analysis of Transposition-Table-Driven Work Scheduling in Distributed Search
- John Romein
- Henri Bal
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
- Aske Plaat
This paper discusses a new work-scheduling algorithum for parallel search of single agent state spaces, called Trasposition-Table-Driven Work Scheduling, that places the transpostion table at the heart of the parallel work scheduling. The scheme results in less synchronization overhead, less processor idle time, and less redundant search effort. Measeurements on a 128-processor parallel machine show that he scheme achieves close to linear speedups; for large problems the speedups are even super linear due to better memory usage. On the same machine the algorithm is 1.6 to 12.9 time sfaster tahn traditional work-stealing-based schemes.
Citation
J. Romein, H. Bal, J. Schaeffer, A. Plaat. "A Performance Analysis of Transposition-Table-Driven Work Scheduling in Distributed Search". IEEE, 13(5), pp 447-459, January 2002.Keywords: | distributed search, work pushing, Traspostion-Table- Driven Work Scheduling |
Category: | In Journal |
BibTeX
@article{Romein+al:IEEE02, author = {John Romein and Henri Bal and Jonathan Schaeffer and Aske Plaat}, title = {A Performance Analysis of Transposition-Table-Driven Work Scheduling in Distributed Search}, Volume = "13", Number = "5", Pages = {447-459}, journal = {}, year = 2002, }Last Updated: December 04, 2006
Submitted by Valerie Dacyk