Abstract
Constraint propagation algorithms present inherent parallelism. Each constraint behaves as a concurrent process triggered by changes in the store of variables, updating the store in its turn. There is an inherent sequentiality, as well, since a constraint must be executed only as the consequence of a previous execution of another constraint. We have developed different parallel execution models of constraint propagation for MIMD distributed memory machines. We have adopted the indexical scheme, an adequate approach to achieve consistency for n-ary constraints. The proposed models arise from two techniques, dynamic and static, for scheduling constraint executions (assignment of constraint executions to processing elements). In the static scheduling models the constraint graph is divided into N partitions, which are executed in parallel on N processors. We have investigated an important issue affecting performance, the criterion to establish the graph partition in order to balance the run-time workload. In the dynamic scheduling models, any processor can execute any constraint, improving the workload balance. However, a coordination mechanism is required to ensure a sound order in the execution of constraints. We have designed coordination mechanisms for both centralised and distributed control schemes. Several parallel processing methods for solving Constraint Satisfaction Problems have been proposed. [1] and [3] must be remarked in relation with our work.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Baudot, B., Deville, Y.: Analysis of Distributed Arc-Consistency Algorithms. Technical Report 97-07. University of Louvain. Belgium (1997).
Ruiz-Andino, A., Araujo, L., Ruz, J.: Parallel constraint satisfaction and optimisation. The PCSO system. Technical Report 71.98. Department of Computer Science. Universidad Complutense de Madrid, Spain. (1998).
Zhang, Y., Mackworth, K.: Parallel and Distributed Finite Constraint Satisfaction: Complexity, Algorithms and Experiments. Parallel Processing for Artificial Intelligence. Elsevier (1993).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ruiz-Andino, A., Araujo, L., Sàenz, F., Ruz, J. (1998). Parallel Execution Models for Constraint Propagation. In: Maher, M., Puget, JF. (eds) Principles and Practice of Constraint Programming — CP98. CP 1998. Lecture Notes in Computer Science, vol 1520. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49481-2_44
Download citation
DOI: https://doi.org/10.1007/3-540-49481-2_44
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65224-3
Online ISBN: 978-3-540-49481-2
eBook Packages: Springer Book Archive