Parallelism and Domain Dependence in Constraint Satisfaction

This paper discusses how better arc consistency algorithms for constraint satisfaction can be developed by exploiting parallelism and domain specific problem characteristics. A massively parallel algorithm for arc consistency is given, expressed as a digital circuit. For a constraint satisfaction problem with n variables and a labels, this algorithm has a worst case time complexity of O(l1a)~ significantly better than that of the optimal uniprocessor algorithm. An algorithm of intermediate parallelism suitable for implementation on a SIl\lD machine is also given. Analyses and implementation experiments are shown for both algorithrus. A method for exploiting characteristics of a problem domain to achieve arc consistency algorithms with better time and space complexity is also discussed. A detailed example is developed, and a general technique for expressing domain knowledge and using it to develop optimized arc consistency algorithms is described. The domain specific optimizations can be applied analogously to any of the arc consistency .algorithms along the sequential/parallel spectrum