# «Abstract. As a case study that illustrates our view on coordination and component-based software engineering, we present the design and ...»

A Component-Based Parallel Constraint Solver

Peter Zoeteweij and Farhad Arbab

CWI, P.O. Box 94079, 1090 GB Amsterdam, the Netherlands

{P.Zoeteweij,Farhad.Arbab}@cwi.nl

Abstract. As a case study that illustrates our view on coordination and

component-based software engineering, we present the design and implementation of a parallel constraint solver. The parallel solver coordinates

autonomous instances of a sequential constraint solver, which is used as

a software component. The component solvers achieve load balancing of tree search through a time-out mechanism. Experiments show that the purely exogenous mode of coordination employed here yields a viable parallel solver that eﬀectively reduces turn-around time for constraint solving on a broad range of hardware platforms.

Keywords: component-based software engineering, coordination, parallelization, constraint solving.

1 Introduction Over the past years, constraint solving has been a useful test case for coordination techniques. [3, 8, 9, 14]. One of the reasons is that because of the general nature of the constraint programming paradigm, any constraint solver inevitably supports only a speciﬁc class of constraint satisfaction problems (CSP’s). By having diﬀerent solvers, supporting diﬀerent classes of specialized problems cooperate to solve a more general problem, a broader range of problems can be addressed. The goal of having stand-alone constraint solvers cooperate in a uniform and structured way brings solver cooperation into the area of coordination programming and component-based software engineering.

Constraint solving is an NP-complete problem. Eﬃcient algorithms exist for some classes of CSP’s, and when completeness is not important we may be able to ﬁnd a solution to a CSP quickly by using local search techniques. Nevertheless, generally constraint solving comes down to tree search. In this paper, we deal with a speciﬁc mode of solver cooperation that aims at reducing the turn-around time of constraint solving through parallelization of tree search. Contrary to other modes of solver cooperation, parallel constraint solving has received little attention from a coordination point of view.

The primary aspect of our approach is to equip a tree search based constraint solver with a time-out mechanism. When a CSP can be solved before the elapse of a given time-out, such a solver simply produces all solutions that it has found Supported by NWO, the Netherlands Organization for Scientiﬁc Research, under project number 612.069.003.

(or the solution that it has found, if we are not interested in all solutions).

Otherwise it also produces some representation of the work that still needs to be done. For tree search, this is a collection of (disjunct) subproblems that must still be explored: the search frontier. These subproblems are then re-distributed among a set of identical solvers that run in parallel. The initial solver is part of this set, and each solver in the set may split its input into further subproblems, when its time-out elapses. The aim of the time-out mechanism is to provide an implicit load balancing: when a solver is idle, and there are currently no subproblems available for it to work on, another solver is likely to produce new subproblems when its time-out elapses. We expect to be able to tune the time-out value such that it is both suﬃciently small to ensure that enough subproblems are available to keep all solvers busy, and suﬃciently large to ensure that the overhead of communicating the subproblems is negligible. The idea of using timeouts is quite intuitive, but to our knowledge, its application to parallel search is novel.

Rather than a parallel algorithm, we present this scheme as a pattern for constructing a parallel constraint solver from component solvers. The only requirement is that these components can publish their search frontiers. We believe that this requirement is modest compared to building a parallel constraint solver from scratch. Our presentation of the scheme in Section 3 uses the notion of

**Abstract**

behavior types, and the Reo coordination model. These, and the relevant aspects of constraint solving are introduced in Section 2. To test the concept, we equipped a constraint solver with the time-out mechanism, and implemented the coordination pattern as a stand-alone distributed program. In Section 4 we give an account of this implementation, and in Section 5 we describe the experiments that were performed to test the parallel solver. Compared to parallelizing an existing constraint solver, the component-based approach has further beneﬁts.

These are discussed in Section 6, together with related work and directions for future research.

2 Preliminaries To make the paper self-contained, in this section we provide the necessary background on constraint solving (2.1), abstract behavior types, and Reo (2.2).

2.1 Constraint Solving Constraint solving deals with ﬁnding solutions to constraint satisfaction problems. A CSP consists of a number of variables and their associated domains (sets of possible values), and a set of constraints. A constraint is deﬁned on a subset of the variables, and restricts the combinations of values that these variables may assume. A solution to a CSP is an assignment of values to variables that satisﬁes all constraints. Tree search in constraint solving performs a systematic exploration of assignments of values to variables: at every node of the search tree, the descendant nodes are generated by assigning diﬀerent subdomains to some variable.

The search tree is expanded as a part of the traversal of the tree, but before generating a next level of nodes, we try to limit the number of possible alternatives. This is called pruning the search tree, and for constraint solving, this is done by constraint propagation. The purpose of constraint propagation is to remove from the variable domains the values that do not contribute to any solution. For example if two integer variables x, y ∈ [0..10] are constrained by x y, we may remove 10 from the domain of x, and 0 from the domain of y. Constraint propagation is usually implemented by computing the ﬁxpoint of a number of reduction operators [1]. These operators are functions (domain reduction functions, DRF’s) that apply to the variable domains, and enforce the constraints. If the domains of one or more variables become empty as a result of constraint propagation, the node of the search tree for which this happens is a failure. If, on the other hand, after constraint propagation all domains are singleton sets, these domains constitute a solution to the CSP. In all other cases, the node of the search tree is an internal node, and constraint solving proceeds by branching.

Important concerns in this branch-and-prune approach to constraint solving are the choice of the variable for branching, and how to construct the subdomains for that variable. In this paper we assume a fail-ﬁrst variable selection strategy, where a variable is selected for which the number of possible assignments is minimal. Subdomains are constructed by enumeration: they are singleton sets, one for every value in the original domain.

Branching adds new nodes of the search tree to the set of nodes where search may continue. This set is called the search frontier [10]. Managing the search frontier as a stack eﬀectively implements a depth-ﬁrst traversal. Other traversal strategies exist, but depth-ﬁrst keeps the search frontier small. Apart from memory requirements this is especially important for our application, because the size of the search frontier determines the communication volume of the parallel solver.

**2.2 Coordination and Abstract Behavior Types**

In our view, coordination programming deals with building complex software systems from largely autonomous component systems. The more autonomous these components are, the more it becomes justiﬁed to refer to their composition as coordination. Contrary to modules and objects, which are the counterparts of components in the classical software engineering paradigms of modular and object-oriented programming, an instance of a prospective software component has at least one thread of control. For the purpose of composition, the component is a black box, that communicates with its environment through a set of ports.

Coordination programming involves writing the “glue code” to actually make the component instances cooperate. Depending on the complexity of the interaction, it may make sense to use a dedicated coordination language. For example if the population of processes is highly dynamic, the Manifold coordination language [2] may be a logical choice.

A software system that complies with the above notion of a component can be speciﬁed conveniently by an abstract behavior type (ABT) [4]. ABT’s are the coordination counterpart of abstract data types, as used in classical software engineering. Before we can introduce ABT’s we ﬁrst need to recall the deﬁnition of timed data streams from [5].

A stream over some set A is an inﬁnite sequence of elements of A. Zerobased indices are used to denote the individual elements of a stream, e.g., α(0), α(1), α(2),... denote the ﬁrst, second, third, etc. elements of the stream α. Also α(k) denotes the stream that is obtained by removing the ﬁrst k values from stream α (so α(0) is the head of the stream, and α(1) is its tail). Relational operators on streams apply pairwise to their respective elements, e.g., α β means α(0) β(0), α(1) β(1), α(2) β(2),...

A timed data stream over some set D is a pair of streams α, a, consisting of a data stream α over D, and a time stream a over the set of positive real numbers, and having a(i) a(j), for 0 ≤ i j. The interpretation of a timed data stream α, a is that for all i ≥ 0, the input/output of data item α(i) occurs at “time moment” a(i).

An abstract behavior type is a (maximal) relation over timed data streams.

Every timed data stream involved in an ABT is tagged either as its input or output. For an ABT R with one input timed data stream I and one output timed data stream O we use the inﬁx notation I R O. Also for two such ABT’s R1 and R2, let the composition R1 ◦ R2 denote the relation { α, a, β, b | ∃ γ, c · α, a R1 γ, c ∧ γ, c R2 β, b }.

ABT’s specify only the black box behavior of components. For a model of their implementation, other speciﬁcation methods are likely to be more appropriate, but that information is irrelevant from a coordination point of view.

Reo [4, 6] is a channel-based exogenous coordination model wherein complex coordinators, called connectors are compositionally built out of simpler ones. The simplest connectors in Reo are a set of channels with well deﬁned behavior. In Section 3.2 we use Reo connectors to specify the coordination of our component solvers.

3 Speciﬁcation

3.1 Component Solver

**In this section we deﬁne an ABT for a constraint solver with the time-out mechanism. First we need some formal notion of a CSP:**

Let P be a ﬁnite set of problems and let (P ∪ { }, ) be a partial order such that for all p ∈ P, p. For a problem p ∈ P, we deﬁne the sets sub(p) = {q ∈ P ∪ { } | p q} and sol (p) = {s ∈ sub(p) | ∀q ∈ sub(p) \ {s} · s q} \ { }.

Intuitively, sub(p) represents the set of subproblems of a problem p, possibly including, which represents the deduction of a failure. The set of maximal subproblems excluding, sol (p), represents the set of solutions of p.

Next we specify that a constraint solver transforms a problem into a set of mutually disjunct problems. Let D denote the data domain P ∪ 2P ∪ {τ }, where τ ∈ P is an arbitrary data element that serves as a token. In the following, let / α, a and β, b be timed data streams over D. Now the behavior of a basic solver is captured by the BSol ABT, deﬁned as

where S is a relation on P and 2P, such that for all p ∈ P and R ∈ 2P, S(p, R) iﬀ – ∀r ∈ R, p r, – ∀r, s ∈ R, r s implies r = s, and – sol (p) = ∪r∈R sol (r) The Str (streamer) ABT speciﬁes that stream of sets of problems, as produced by a basic solver, is transformed into a stream of problems, where the sequence

**of problems for each input set is delimited by a token:**

where for all i ∈ IN, α(i) ∈ 2P and β(i) ∈ P ∪ {τ }, and k denotes |α(0)|, the cardinality of the set of problems at the head of stream α. Now the behavior of a constraint solver component is captured by the Sol ABT, deﬁned as

Our top-level model of a solver component is the composition of a basic solver and a streamer. The token τ can be thought of as the notiﬁcation “no” that a PROLOG interpreter would produce to indicate that no (more) solutions have been found. If we model a typical constraint solver as a basic solver, then for any given input problem the output set corresponds to the set of solutions for that problem, i.e. β(i) = sol (α(i)), and there is no upper bound on the time b(i) − a(i) needed to produce this set.

In contrast, the load-balancing solver component that we propose here stops searching for solutions after the elapse of a time-out t. At that moment, it generates a subproblem for every solution that it has found, plus one for every node of the search tree that must still be explored. For t ∈ IR+, the Sol t ABT deﬁnes

**this behavior:**

α, a BSol t β, b ≡ α, a BSol β, b ∧ ∀i ∈ IN · b(i) − a(i) t

** Sol t = BSol t ◦ Str3.2 Parallel Solver**

Figure 1 shows a channel-based design for a (3-way) parallel solver. All channels in this design are synchronous: read and write operations block until a matching operation is performed on the opposite channel end. The “resistors” depict Reo ﬁlters: synchronous channels that accept data items that match a certain pattern (set of allowable data items) and discard data items that do not match this pattern. At node b in Figure 1, all output of the solvers is replicated onto two ﬁlters. Channel bc ﬁlters out solutions. Its pattern (p) is Filter({p ∈ P | sol (p) = {p}}). The channel from b to T discards all solutions.

Its pattern (q) is Filter({p ∈ P | sol (p) = {p}} ∪ {τ }). The ABT’s of the channels are speciﬁed in [4].