A NOVEL DISCRETE RELAXATION ARCHITECTURE

The discrete relaxation algorithm (DRA) is a computational technique that enforces arc consistency (AC) in a constraint satisfaction problem (CSP). It has been widely used in artificial intelligence, operations research, pattern recognition and computer vision, and many related areas. The original sequential AC-1 algorithm suffers from O(n3m3) time complexity, and even the optimal sequential AC-4 algorithm is O(n2m2) for an n-object and m-label DRA problem. Sample problem runs show that these algorithms are all too slow to meet the need for any useful, real-time CSP applications. In this paper, we give a parallel DRA5 algorithm that reaches a lower bound of O(nm) (where the number of processors is polynomial in the problem size). A fine-grained, massively parallel hardware computer architecture has been designed for the DRA5 algorithm. For practical problems, many orders of magnitude of efficiency improvement can be reached on such a hardware architecture.