Frameworks:
Parallel State Space Search Engine
AI Search, especially Branch-and-Bound type searches:
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]
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]
People
Papers/Talks
13-29
2013
[Paper]
[Paper]
Parallel Branch-and-Bound for Two-Stage Stochastic Integer Optimization (Best Paper Award) [HiPC 2013]
11-25
2011
[Paper]
[Paper]
ParSSSE: An Adaptive Parallel State Space Search Engine [PPL 2011]
11-05
2011
[Paper]
[Paper]
An Adaptive Framework for Large-scale State Space Search [LSPP 2011]
03-09
2003
[MS Thesis]
[MS Thesis]
Balancing Priorities and Load for State Space Search On Large Parallel Machines [Thesis 2003]
95-05
1995
[Paper]
[Paper]
Efficient Parallel Graph Coloring with Prioritization [LNCS 1995]
93-16
1992
[Paper]
[Paper]
Prioritization in Parallel Computing (extended abstract) [Parallel Symbolic Computing Workshop 1992]
93-06
1993
[Paper]
[Paper]
Prioritization in Parallel Symbolic Computing [LNCS 1993]
93-05
1993
[MS Thesis]
[MS Thesis]
Bidirectional Search in Parallel [Thesis 1993]
92-05
1992
[Paper]
[Paper]
A Load Balancing Strategy For Prioritized Execution of Tasks [Workshop on Dynamic Object Placement and Load Balancing at ECOOP 1992]
91-06
1994
[Paper]
[Paper]
Machine Independent AND and OR Parallel Execution of Logic Programs: Part II - Compiled Execution [IEEE Transactions on Parallel and Distributed Systems 1994]
91-05
1994
[Paper]
[Paper]
Machine Independent AND and OR Parallel Execution of Logic Programs: Part I - the Binding Environment [IEEE Transactions on Parallel and Distributed Systems 1994]
90-10
1990
[PhD Thesis]
[PhD Thesis]
Machine Independent Parallel Execution of Speculative Computations [Thesis 1990]
90-02
1990
[Paper]
[Paper]
Consistent Linear Speedups for a First Solution in Parallel State-Space Search [AAAI 1990]