The Grainger College of Engineering
Parallel Programming Laboratory

Parallel State Space Search Engine

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 our research, we analyze the parallel performance of several classes of state space search applications. To facility state space search programming, we developed a general framework based on Charm++. In the framework, the issues of of grain size, the prioritized execution of tasks and the balancing of processor load are carefully analyzed and handled. On three examples of NQueens, Unbalanced Tree Search and Traveling Salesman Problem, We demonstrate the efficiency and scalability of our design using three example applications, and present scaling results up to 32,768 processors.
Details can be found in the paper
11-25 ParSSSE: An Adaptive Parallel State Space Search Engine [Parallel Processing Letters 2011]

Papers / Talks