AIJ Journal 1993 Journal Article
Depth-first heuristic search on a SIMD machine
- Curt Powley
- Chris Ferguson
- Richard E. Korf
We present a parallel implementation of Iterative-Deepening-A∗, a depth-first heuristic search, on the single-instruction, multiple-data (SIMD) Connection Machine ★ ★ Connection Machine is a trademark of Thinking Machines Corporation. . Heuristic search of an irregular tree represents a new application of SIMD machines. The main technical challenge is load balancing, and we explore three different techniques in combination. We also use a simple method for dynamically determining when to stop searching and start load balancing. We achieve an efficiency of 69%, for a speedup of 5685 on 8K processors, an efficiency of 64%, for a speedup of 10, 435 on 16K processors, and an efficiency of 53%, for a speedup of 17, 300 on 32K processors on the Fifteen Puzzle. On hard problem instances, we achieved efficiencies as high as 80%, for a speedup of 26, 215 on 32K processors. Our analysis indicates that work only needs to increase as P log P to maintain constant efficiency, where P is the number of processors. This high degree of scalability was confirmed empirically for the range of 16 to 32, 768 (32K) processors.