State-copying and Recomputation in Parallel Constraint Programming with Global Constraints
Author
Summary, in English
In this paper we discuss parallelization and distribution of problems modeled in a constraint programming (CP) framework. We focus on parallelization of depth-first search methods, since search is the most time-consuming task in CP. The current hardware development is moving towards multi-core processors and the cost of building distributed systems is shrinking. Hence, parallelization and distribution of constraint solvers is of increasing interest when trying to improve performance.
One of the most important issues that arises in parallel computing is load-balancing, which requires a trade-off between processor load and communication. In this paper we present how reduced communication, at the cost of increased computation, can improve performance. Our experiments include global constraints, which are more powerful than binary constraints, but significantly more expensive to recompute in the average case. Our results show that recomputing data, rather than copying it, is sometimes faster even for problems that use global constraints. Given that copying is sometimes the better choice, we also present a method for combining copying and recomputation to create an even more powerful model of communication.
One of the most important issues that arises in parallel computing is load-balancing, which requires a trade-off between processor load and communication. In this paper we present how reduced communication, at the cost of increased computation, can improve performance. Our experiments include global constraints, which are more powerful than binary constraints, but significantly more expensive to recompute in the average case. Our results show that recomputing data, rather than copying it, is sometimes faster even for problems that use global constraints. Given that copying is sometimes the better choice, we also present a method for combining copying and recomputation to create an even more powerful model of communication.
Department/s
Publishing year
2007
Language
English
Pages
311-317
Publication/Series
Proceedings of the 16th Euromicro International Conference on Parallel, Distributed and network-based Processing
Document type
Conference paper
Publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
Topic
- Computer Science
Keywords
- Distribution
- Constraint Programming
- Parallelism
Conference name
16th Euromicro International Conference on Parallel, Distributed and network-based Processing
Conference date
2008-02-13
Conference place
Toulouse, France
Status
Published
Research group
- ESDLAB