Abstract | ||
---|---|---|
Parallel constraint solving is a promising way to enhance the performance of constraint programming. Yet, current solutions for parallel constraint solving ignore the importance of hypergraph decomposition when mapping constraints onto cores. This paper explains why and how the hypergraph decomposition can be employed to relatively evenly distribute workload in parallel constraint solving. We present our dedicated hypergraph decomposition method det-k-CP for parallel constraint solving. The result of det-k-CP, which conforms with four conditions of hypertree decomposition, can be used to allocate constraints of a given constraint network to cores for parallel constraint solving. Our benchmark evaluations have shown that det-k-CP can relatively evenly decompose a hypergraph for specific scale of constraint networks. Besides, we obtained competitive execution time as long as the hypergraphs are sufficiently simple. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/978-3-030-00801-7_6 | DECLARATIVE PROGRAMMING AND KNOWLEDGE MANAGEMENT, DECLARE 2017 |
Keywords | DocType | Volume |
Parallel constraint solving, Hypertree decomposition | Conference | 10997 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ke Liu | 1 | 20 | 16.97 |
Sven Löffler | 2 | 0 | 1.01 |
Petra Hofstedt | 3 | 50 | 18.83 |