PARSSSE: AN ADAPTIVE PARALLEL STATE SPACE SEARCH ENGINE

Autor:	Pritish Jetley, Gengbin Zheng, Laxmikant V. Kale, Yanhua Sun
Rok vydání:	2011
Předmět:	Search engine Incremental heuristic search Hardware and Architecture Computer science State space search Distributed computing Scalability Combinatorial search Beam search Programmer Iterative deepening depth-first search Software Theoretical Computer Science
Zdroj:	Parallel Processing Letters. 21:319-338
ISSN:	1793-642X 0129-6264
Popis:	State space search problems abound in the artificial intelligence, planning and optimization literature. Solving such problems is generally NP-hard, so that a brute-force approach to state space search must be employed. Given the exponential amount of work that state space search problems entail, it is desirable to solve them on large parallel machines with significant computational power. In this paper, we analyze the parallel performance of several classes of 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 corresponding techniques that are used to scale such applications to large scale. Moreover, we tackle the problem of programmer productivity by incorporating these techniques into a general search engine framework 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 32,768 processors.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::cb1d629a7d9ff0886d3ec6c0674e1d35 https://doi.org/10.1142/s0129626411000242 Zobrazit plný text záznamu