DEPTH-1ST HEURISTIC-SEARCH ON A SIMD MACHINE

被引:16
作者
POWLEY, C
FERGUSON, C
KORF, RE
机构
[1] Computer Science Department, University of California, Los Angeles, CA 90024, Boelter Hall
基金
美国国家科学基金会;
关键词
D O I
10.1016/0004-3702(93)90002-S
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We present a parallel implementation of Iterative-Deepening-A*, a depth-first heuristic search, on the single-instruction, multiple-data (SIMD) Connection Machine*. 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.
引用
收藏
页码:199 / 242
页数:44
相关论文
共 57 条
[1]  
ARVINDAM S, 1990, 3RD P IEEE S FRONT M
[2]  
BAUDET GM, 1978, THESIS CARNEGIE MELL
[3]   HEURISTIC-SEARCH IN RESTRICTED MEMORY [J].
CHAKRABARTI, PP ;
GHOSE, S ;
ACHARYA, A ;
DESARKAR, SC .
ARTIFICIAL INTELLIGENCE, 1989, 41 (02) :197-221
[4]  
CHRISTMAN DP, 1983, THESIS MIT CAMBRIDGE
[5]   GENERALIZED BEST-1ST SEARCH STRATEGIES AND THE OPTIMALITY OF A [J].
DECHTER, R ;
PEARL, J .
JOURNAL OF THE ACM, 1985, 32 (03) :505-536
[6]  
EBELING C, 1987, ALL RIGHT MOVES
[7]  
EVETT M, 1990, 3RD SYMPOSIUM ON THE FRONTIERS OF MASSIVELY PARALLEL COMPUTATION, P145, DOI 10.1109/FMPC.1990.89450
[8]  
EVETT M, 1992, COMMUNICATION
[9]  
Feldmann R., 1990, PARALLEL ALGORITHMS, P66, DOI [10.1007/978-1-4612-3390-9_3, DOI 10.1007/978-1-4612-3390-9_3]
[10]  
FELTEN E, 1988, P INT C 5TH GENERATI