An adaptive framework for large-scale state space search

Yanhua Sun, Gengbin Zheng, Pritish Jetley, Laxmikant V. Kalé

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2011 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum, IPDPSW 2011
Pages1798-1805
Number of pages8
DOIs
StatePublished - Dec 20 2011
Event25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011 - Anchorage, AK, United States
Duration: May 16 2011May 20 2011

Publication series

NameIEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum

Other

Other25th IEEE International Parallel and Distributed Processing Symposium, Workshops and Phd Forum, IPDPSW 2011
CountryUnited States
CityAnchorage, AK
Period5/16/115/20/11

Keywords

  • Adaptive grain size control
  • Dynamic load balancing
  • Parallel state space search
  • Prioritized execution

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'An adaptive framework for large-scale state space search'. Together they form a unique fingerprint.

Cite this