Parallel Hardware for Constraint Satisfaction

Michael J. Swain, Paul R. Cooper

A parallel implementation of constraint satisfaction by arc consistency is presented. The implementation is constructed of standard digital hardware elements, used in a very fine-grained, massively parallel style. As an example of how to specialize the design, a parallel implementation for solving graph isomorphism with arc consistency is also given. Complexity analyses are given for both circuits. Worst case running time for the algorithms turns out to be linear in the number of variables n and labels a, O(an), and if the I/O must be serial, it will dominate the computation time. Fine-grained parallelism trades off time complexity for space complexity, but the number of gates required is only O(a2n2).

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.