TY - GEN
T1 - An adaptive framework for large-scale state space search
AU - Sun, Yanhua
AU - Zheng, Gengbin
AU - Jetley, Pritish
AU - Kalé, Laxmikant V.
PY - 2011/12/20
Y1 - 2011/12/20
N2 - State space search problems abound in the artificial intelligence, planning and optimization literature. Solving such problems is generally NP-hard. Therefore, a brute-force approach to state space search must be employed. It is instructive to solve them on large parallel machines with significant computational power. However, writing efficient and scalable parallel programs has traditionally been a challenging undertaking. In this paper, we analyze several performance characteristics common to all parallel state space search applications. In particular, we focus on the issues of grain size, the prioritized execution of tasks and the balancing of load among processors in the system. We demonstrate the techniques that are used to scale such applications to large scale. We have incorporated these techniques into a general search engine framework that is designed to solve a broad class of state space search problems. We demonstrate the efficiency and scalability of our design using three example applications, and present scaling results up to 16,384 processors.
AB - State space search problems abound in the artificial intelligence, planning and optimization literature. Solving such problems is generally NP-hard. Therefore, a brute-force approach to state space search must be employed. It is instructive to solve them on large parallel machines with significant computational power. However, writing efficient and scalable parallel programs has traditionally been a challenging undertaking. In this paper, we analyze several performance characteristics common to all parallel state space search applications. In particular, we focus on the issues of grain size, the prioritized execution of tasks and the balancing of load among processors in the system. We demonstrate the techniques that are used to scale such applications to large scale. We have incorporated these techniques into a general search engine framework that is designed to solve a broad class of state space search problems. We demonstrate the efficiency and scalability of our design using three example applications, and present scaling results up to 16,384 processors.
KW - Adaptive grain size control
KW - Dynamic load balancing
KW - Parallel state space search
KW - Prioritized execution
UR - http://www.scopus.com/inward/record.url?scp=83455220533&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=83455220533&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2011.338
DO - 10.1109/IPDPS.2011.338
M3 - Conference contribution
AN - SCOPUS:83455220533
SN - 9780769543857
T3 - IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum
SP - 1798
EP - 1805
BT - 2011 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum, IPDPSW 2011
T2 - 25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011
Y2 - 16 May 2011 through 20 May 2011
ER -