this paper presents a model and implementation techniques for speeding up constraint propagation. Two fundamental approaches to improving constraint propagation are explored: keeping track of which propagators are at ...
详细信息
Many global constraints can be described by a regular expression or a DFA. Originally, the regular constraint, uses a DFA to describe the constraint, however, it can also be used to express a table constraint. thus, t...
详细信息
Conflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with general linear inequalities, the conflict...
详细信息
We consider the impact of value ordering heuristics on the search effort required to find all solutions, or proving none exist, to a constraint satisfaction problem in k-way branching search. We show that when the var...
详细信息
An important extension of constraint technology involves problems that undergo changes that may invalidate the current solution. Previous work on dynamic problems sought methods for efficiently finding new solutions. ...
详细信息
Satellite imagery solutions are widely used to study and monitor different regions of the Earth. However, a single satellite image can cover only a limited area. In cases where a larger area of interest is studied, se...
详细信息
Most of complete search algorithms over constraint Satisfaction Problems (csp) are based on Standard Backtracking. Two main enhancements of this basic scheme have been studied: first, to integrate constraint propagati...
详细信息
In the last twenty years, many algorithms and heuristics were developed to find solutions in constraint networks. their number increased to such an extent that it quickly became necessary to compare their perfor...
详细信息
this paper presents an alternative method to parallelize programs, better suited to manycore processors than actual operating system-/API-based approaches like OpenMP and MPI. the method relies on a parallelizing hard...
详细信息
this paper presents an alternative method to parallelize programs, better suited to manycore processors than actual operating system-/API-based approaches like OpenMP and MPI. the method relies on a parallelizing hardware and an adapted programming style. It frees and captures the instruction-level parallelism (ILP). A many-core design is presented in which cores are multithreaded and able to fork new threads. the programming style is based on functions. the hardware creates a concurrent thread at each function call. the programming style and the hardware create the conditions to free the ILP, by eliminating the architectural dependences between a call and its continuation after return. We illustrate the method on a sum reduction, a matrix multiplication and a sort. We measure the ILP of the parallel runs and show that it is high enough to feed thousands of cores because it increases with data size. We compare our method to pthread parallelization, showing that (1) our parallel execution is deterministic, (2) our thread management is cheap, (3) our parallelism is implicit, and (4) our method parallelizes functions and loops. Implicit parallelism makes parallel code easy to write and read. Deterministic parallel execution makes parallel code easy to debug.
Most CSP algorithms are based on refinements arid extensions of backtracking, and employ one of two simple "branching schemes": 2-way branching or d-way branching, for domain size d. the schemes are not equi...
详细信息
暂无评论