Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Time Efficient Parallel Lookahead Search Technique

IP.com Disclosure Number: IPCOM000101034D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 8 page(s) / 297K

Publishing Venue

IBM

Related People

Natarajan, KS: AUTHOR

Abstract

A technique is described for efficient use of multiple processors for generating solutions to a large class of Constraint Satisfaction Problems in a manner that tends to minimize completion time and maximize processor utilization simultaneously.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 23% of the total text.

Time Efficient Parallel Lookahead Search Technique

       A technique is described for efficient use of multiple
processors for generating solutions to a large class of Constraint
Satisfaction Problems in a manner that tends to minimize completion
time and maximize processor utilization simultaneously.

      Many combinatorial search problems are formulated as Constraint
Satisfaction Problems.  A Constraint Satisfaction Problem typically
requires finding values for a set of variables that are subject to an
arbitrary set of constraints.  A Constraint Satisfaction Problem has
the following generic form:
   G (S) = P1(S1) & P2(S2) & ... & PM(SM)
where G(S) is the Constraint Satisfaction Problem to be solved and
S={X1, X2, ..., XN} is a set of N variables. Each variable Xi takes
on values from its domain Di .  For 1 & i & M, the ith
constraint is a predicate Pi defined over a set of variables Si,
where Si & S.  A solution to problem G is a binding of values to
each of the variables in S such that  a) each predicate Pi is
satisfied and  b) each variable that is common to two or more
predicates must be consistently bound to the same element.  Two
solutions are distinct if the bindings are different, i.e., at least
one variable is bound to two different values in the two bindings.
In an instance of the Constraint Satisfaction Problem, one is given
the bindings of a subset of S and the search procedure is required to
enumerate all the consistent bindings for the remainder of S.

      A large number of applications can be posed as the problem of
simultaneous satisfaction of several constraints. Applications
include database retrieval, scene analysis (segmentation of a scene
into regions), graph coloring, route selection in networks, etc.

      A search procedure is required to enumerate all solutions that
simultaneously satisfy all constraints on the problem.  Prior art on
the solution of this class of problems have considered the use of
backtrack search algorithms [1] to enumerate all the solutions to a
problem. A number of improved variants of backtrack search have been
de- veloped [2,3,4,5,6,7,8] to overcome limitations of the backtrack
search algorithm.  Specifically, it was shown that the Forward
Checker Algorithm [5], an efficient sequential algorithm for solving
Constraint Satisfaction Problems, can be executed in parallel.

      The amount of search effort is predominantly determined by the
total number of consistency test.  For a prototypical
Constraint-Satis- faction Problem, namely, the N-Queens problem
(place N-queens on an NxN checkerboard so that no queen can take
another), the speedup behavior is shown in Fig. 1.  The computational
effort is distributed in the different nodes of the search tree.

      Next, two basic observations are made about the parallel search
techniques that provide the basis for the current discussion.  It has
been observed that in many Constraint Satisfaction Problem s...