State-copying and Recomputation in Parallel Constraint Programming with Global Constraints
Författare
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.
Avdelning/ar
Publiceringsår
2007
Språk
Engelska
Sidor
311-317
Publikation/Tidskrift/Serie
Proceedings of the 16th Euromicro International Conference on Parallel, Distributed and network-based Processing
Dokumenttyp
Konferensbidrag
Förlag
IEEE - Institute of Electrical and Electronics Engineers Inc.
Ämne
- Computer Science
Nyckelord
- 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
Forskningsgrupp
- ESDLAB