Transposition Table Driven Work Scheduling in Distributed Search

Abstract

This paper introduces a new scheduling algorithm for parallel single-agent search, transposition table driven work scheduling, that places the transposition 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. Measurements on a 128-processor parallel machine show that the scheme achieves nearly-optimal performance and scales well. The algorithm performs a factor of 2.0 to 13.7 times better than traditional work-stealing-based schemes. Introduction Heuristic search is one of the cornerstones of AI. Its applications range from logic programming to pattern recognition, from theorem proving to chess playing. For many applications, such as real-time search and any-time algorithms, achieving high performance is of great importance, both for solution quality and execution speed. Many search algorithms recursively decompose a state into successor states. If the successor states are ...