Not Logged In

A Performance Analysis of Transposition-Table-Driven Work Scheduling in Distributed Search

Full Text: tds.ps PS

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

University of Alberta Logo AICML Logo