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
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:
https://lup.lub.lu.se/record/620172
- author
- Rolf, Carl Christian
LU
and Kuchcinski, Krzysztof
LU
- organization
- publishing date
- 2007
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Distribution, Constraint Programming, Parallelism
- host publication
- 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
- conference location
- Toulouse, France
- conference dates
- 2008-02-13
- 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
- 2016-04-04 10:34:36
- date last changed
- 2022-01-29 20:31:33
@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}},
keywords = {{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}},
doi = {{10.1109/PDP.2008.48}},
year = {{2007}},
}