Advanced

State-copying and Recomputation in Parallel Constraint Programming with Global Constraints

Rolf, Carl Christian LU and Kuchcinski, Krzysztof LU (2007) 16th Euromicro International Conference on Parallel, Distributed and network-based Processing In Proceedings of the 16th Euromicro International Conference on Parallel, Distributed and network-based Processing p.311-317
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Distribution, Constraint Programming, Parallelism
in
Proceedings of the 16th Euromicro International Conference on Parallel, Distributed and network-based Processing
pages
7 pages
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
16th Euromicro International Conference on Parallel, Distributed and network-based Processing
external identifiers
  • WOS:000254266500041
  • Scopus:47349111939
DOI
10.1109/PDP.2008.48
language
English
LU publication?
yes
id
91ec9c3f-d31d-46d2-8b93-1405629e40aa (old id 620172)
date added to LUP
2007-12-12 11:14:04
date last changed
2017-01-01 07:58:36
@inproceedings{91ec9c3f-d31d-46d2-8b93-1405629e40aa,
  abstract     = {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. <br/><br>
<br/><br>
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.},
  author       = {Rolf, Carl Christian and Kuchcinski, Krzysztof},
  booktitle    = {Proceedings of the 16th Euromicro International Conference on Parallel, Distributed and network-based Processing},
  keyword      = {Distribution,Constraint Programming,Parallelism},
  language     = {eng},
  pages        = {311--317},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {State-copying and Recomputation in Parallel Constraint Programming with Global Constraints},
  url          = {http://dx.doi.org/10.1109/PDP.2008.48},
  year         = {2007},
}