A CSP consists of a set V of variables, the domains D of these variables and a set C of constraints over these variables. The objective is to assign values in D to the variables in such a way that all constraints are satisfied. CSP∫ are known to be N P-Complete. Considerable efforts have been made to identify tractable classes. One approach is based on exploiting structural properties of the constraints network. If the CSP is tree structured then it can be solved in polynomial time. Many techniques have been developed to transform a CSP into a tree or an equivalent hypertree structured CSP, we can cite [4,6,1]. The Generalized Hypertree Decomposition method is the most general method. However the algorithm proposed to solve the hypertree structured CSP is not efficient in practice. In this work, we propose to improve this algorithm. Mainly we propose two algorithms: an improved sequential algorithm and a parallel algorithm. The sequential algorithm is based on the hashing technique, while the parallel algorithm explores the pipeline technique and the parallel tree contraction algorithm between the nodes to achieve the semi-join operation. In order to validate our proposition we first compare the sequential algorithm proposed in this paper with the basic algorithm proposed in [5] . Based on some experiments done on benchmarks from the literature, we observed a promising gain in terms of cpu time with our sequential approach. More particularly, good results are observed when large size relations are considered. To validate our parallel algorithm, we have proposed a simulation model using logical time assumptions. The experimental results outline the practical efficiency of this algorithm and its performances in term of space memory. This paper is organized as follows : section 2 gives preliminaries of constraint satisfaction problems and well known CSP decomposition methods by developing more particulary the (generalized) hypertree decomposition method which is the most general one. In section 3, we present our sequential algorithm called S HBR (for Sequential Hash Based Resolution) which solves the hypertree structured CSP and we give some experiments of our proposition with respect to the algorithm proposed in [5]. In section 4, we present our parallel algorithm and in section 5, we give some experimental results of this algorithm. Finally, in section 6, we give our conclusion and some perspectives to this work.
The notion of Constraint Satisfaction Problem CSP was introduced by [7].
A constraint satisfaction problem is defined as a 3-tuple P = X, D, C where :
A solution of a CSP is an assignment of values to variables which satisfies all constraints.
Definition 2. Hypergraph: The constraint hypergraph [2] of a CSP P =< X, D, C > is given by H =< V, E > where E is a set of hyperedges corresponding to the scopes of the constraints in C, V is the set of variables of P.
In this paper, hyperedges(H) is the set of the hyperedges of the hypergraph H. If h is a hyperedge, then var(h) is the set of variables of h. Definition 3. A join tree for a hypergraph H is a tree T whose nodes are the hyperedges of H, such that, when a vertex v of H occurs in two hyperedges e1 and e2 then v occurs in each node of the unique path connecting e1 and e2 in the tree T. Definition 4. Hypertree: A hypertree for a hypergraph H is a triple < T, χ, λ > where T = (N, E) is a rooted tree, and χ and λ are labelling functions which associate each vertex p ∈ N with two sets χ(p) ⊆ var(H) and λ(p) ⊆ hyperedges(H). If T = (N , E ) is a subtree of T, we define χ(T ) = v∈N χ(v). We denote the set of vertices N of T by vertices(T) and the root of T by root(T). T p denotes the subtree of T rooted at the node p. Proposition 1. A CSP whose structure is acyclic can be solved in polynomial time [6].
The goal of all structural decomposition methods is to transform a CSP into an equivalent acyclic CSP which can be solved in polynomial time. A decomposition method D associates to each hypergraph H a parameter D-width called the width of H. The method D ensures that for a fixed k, each CSP instance with D-width ≤ k is tractable and then can be solved in polynomial time. Among these methods, the generalized hypertree decomposition (GHD) dominates all the other structural decomposition methods. In the next paragraph, we present the (generalized) hypertree decomposition method. Definition 5. A generalized hypertree decomposition [10] of a hypergraph H =< V, E >, is a hypertree HD =< T, χ, λ > which satisfies the following conditions :
1. For each edge h ∈ E, there exists p ∈ vertices(T ) such that var(h) ⊆ χ(p). We say that p covers h.
2. For each variable v ∈ V , the set {p ∈ vertices(T )|v ∈ χ(p)} induces a connected subtree of T.
A hypertree decomposition of a hypergraph H =< V, E >, is a generalized hypertree decomposition HD =< T, χ, λ > which additionally satisfies the following special condition :
The width of a (generalized) hypertree decomposition < T, χ, λ > is max p∈vertices(T ) |λ(p)|. The (generalized) hypertree width (g)hw(H) of a hypergraph H is the minimum width over all its (generalized) hypertree decompositions.
A hyperedge h of a hypergraph H = V, E is strongly covered in HD = T , χ, λ if there exists p ∈ vertices(T ) such that the vertices in h are contained in χ(p) and h ∈ λ(p). A (generalized) hypertree decomposition HD = T , χ, λ of H = V, E is called complete if every hyperedge h of H is strongly covered in HD.
The sequential resolution of a CSP represented by its hypertree decomposition is given by the following algorithm [5] (see algorithm 1), called in this paper B A algorithm (for Basic algorithm).
1: Input : HD = T , χ, λ 2: step1: complete the hypertree decomposition HD 3: step2: Solve each λ-term using multi-join operation. 4: step3: Solve the resulting CSP using semi-join operation. 5: Output: A solution of the given problem.
The second step consists in Solving each sub-problem represented as the λ-term in each node of the hypertree. As a result, we have a new hypertree whose the λ-terms are replaced by a unique constraint relation R p corresponding to the projection on the variables in χ(p) of the join of the constraint relations in λ(p). More formally Rp = ( t∈λ(p) t) [χ(p)]. This operation is expensive. The third step consists in semi-join operation which is an other expensive operation.
Some notations : ϑ i represents the intersection variables of the constraint C i with the set of all variables in the union of C j where j < i in a given order. HT i is the hash table associated to R i .
The S HBR for Sequential Hash Based Resolution algorithm, is formally presented by Algorithm 2. It proceeds in two steps : The SP HBR for Sub Problem Hash Based Resolution algorithm (lines 3 to 6 ) is the optimization of the join operation. The A HBR for (Acyclic Hash Based Resolution) algorithm (line7) is an optimization of the classical Acyclic solving algorithm [3].
We now give more details about SP HBR and A HBR algorithms. a) SP HBR algorithm: The result of the SP HBR execution is a join-tree whose every node n contains only one table R n composed of the tuples satisfying all sub-problems constraints. Nodes of this join-tree are represented as follows: R n = χ(p), Hrel(p) where χ(p) is the set of variables of the node p, and Hrel(p) is the constraint relation generated by the join operation. Additionally, for the leaves nodes, Hrel(p)'s tuples are hashed on intersection variables with the parent node of p. This algorithm decomposes each node of the join tree into connected components. Then it applies the join operation algorithm for each component using the hash join Algorithm 2 Sequential hash Based Resolution(S HBR)
1: Input: a hypertree < T , χ, λ > of a hypergraph < H = V, E > where T is a tree, χ associates to each t of T a set of nodes χ(t) ⊂ V , and λ, a set of arcs λ(t) ⊂ E 2: Output : A solution. Apply the SP HBR algorithm on the node n. 6: end for 7: Step2: Apply A HBR algorithm on T .
principle. For doing that, we establish an order among relations in the same component. Then, we hash each relation R i of the constraint C i , except the first one, on intersection variables with the relations of the constraints that are before C i in this order. The join operation is applied using the Join procedure. These procedures cannot be described in this paper for restricted space reason. We illustrate SP HBR by the following example.
Example 1. We consider a node p of a hypertree HD labelled as follows:
There are two connected components
According to the order of the constraints in each component, we have:
Therefore, for the first component, the R 3 's tuples will be hashed on the set of intersection variables ϑ 3 = {a}, those of R 4 and R 5 on, respectively, ϑ 4 = {b, d} and ϑ 5 = {f }. For the second component, the tuples of R 6 will be hashed on ϑ 6 = {i}. After computing a cartesian product of the components, the resulting tuples t are hashed according to the intersection variables with the parent node of p, if p is a leaf. So, t will be ready for the semi-join operation in A-HBR algorithm. We do not add t to its related partition P unless if P = φ. Thus, we will have one and only one tuple in each partition by eliminating the duplicated tuples. This elimination has no impact on the resolution because, for the A-HBR algorithm, each parent node is filtered on its sons 1 . Moreover, we are interested to get only one solution for the CSP.
b) The A HBR algorithm: The A HBR algorithms tests the consistency of a constraint acyclic network and generates a solution if it exists. This algorithm takes the hypertree resulting from the SP HBR algorithm as its input. The A HBR algorithm (see. Algorithm 3 ) proceeds in two steps: the CONTRACT step and the S SEARCH step. The first step contracts the deep-rooted hypertree HT . A semi-join operation is associated to each contraction operation. The result is a directional from root toward leaves arc consistent hypertree HT (line 3). The second step is the solution search operation, which develops the solution from the HT 's root to leaf nodes (line 4).
1: Input: A hypertree HT = T , χ, λ 2: Output : Determine a directional arc consistent and generate a solution. The CONTRACT algorithm strengths the directional arc consistency of the input hypertree. Given a hypertree, a contraction operation is realized between each leaf node and its parent. For each contraction operation we hash each tuple t of a parent node (p) relation on intersection variables with its sons leaves nodes a i . We denote h i the hashed values. If a i 's hash tables partitions related to h i are not empty , we hash t on intersection variables of p with its parent node and save it. Otherwise, we eliminate t. The leaves nodes a i are marked and considered as pruned. We make the same with the obtained hypertree, and so on, until all the nodes, excepted the root, will be marked. The final result of the contraction operation of a parent node p with its sons leaves nodes, is a node p = χ(p ), Hrel(p ) , whose relation is arc consistent with those of the son nodes relations, and hashed on the intersection variables of p with its parent node. If the hashed relation Hrel(p ) is empty, the problem has no solution. The S SEARCH algorithm is a classical Backtrack free algorithm applied to the directional arc consistent hypertree resulting from the CONTRACT algorithm execution.
The complexity of the SP HBR algorithm is
Where r is the the maximum relation size, h is the hypertree width, P is the maximum number of tuples in the partition of hashing on the variables of ϑ (ϑ represents the intersection variables of C i with all variables in C j where j < i ). For the A HBR algorithm, its complexity is O(nP2 ). Where n is the number of constraints in the obtained CSP. But in our case, we have only one tuple by partition, so the complexity of A HBR algorithm is only O(n).
We have implemented the S HBR algorithm and the basic algorithm [5] (noted here B A). We have tested the two solvers on a set of CSP benchmarks. This benchmarks collection is represented using the new XCSP 2.1 format proposed by The organizational committee of the 3 th international competition of the CSPs solvers
We observe that S-HBR clearly improves the B A algorithm in terms of CPU time for all the instances. The S HBR algorithm gets more better results for the instances which have large relations, because it browses only a sub-part of the relation rather than the totality one as in B A.
In this section, we introduce a parallel version of our previous sequential algorithm S HBR. We called it P HT R for Parallel Hypertree Resolution algorithm and it is described by the algorithm 4. This algorithm uses both pipeline technique and the parallel tree contraction technique. The pipeline avoids the storage of intermediate results so it reduces the memory space explosion. The parallel tree contraction is the most well known adapted approach for the semi-join operation. However the known parallel The P HT R(algorithm 4) procedure proceeds in two steps. The first one concerns the parallel resolution of sub-problems using the P SBR algorithm (line 4). The second step is the resolution of the whole problem. It is performed using the P Solving algorithm (line 6). P SBR (n) // Apply the P SBR algorithm on the node n. 5: end for 6: P Solving(T') // Apply P Solving algorithm on T (T is the obtained hypertree in the step 3).
The P SBR for Parallel Sub Problem Resolution algorithm uses the hash technique. The P SBR algorithm proceeds as the SP HBR algorithm.
After establishing an order on the constraints, it builds a pipeline line composed of join operators whose the first relation is the probe relation and the remaining ones are build relations. The join operation is performed according to the hash pipelined join principle. Thus, each build relation is hashed on its intersection variables (ϑ i ) with the union of the previous relations.
The parallelism in this algorithm is provided by the Pipeline. At each level of the pipeline corresponds a join operation with two operands. The first one is R 1 (the probe relation) for the first operator, R tmp [i − 1] for the i th operator. The second one is the build relation R i for the i th operator. We make a join operation between each tuple of the first operand and all the tuples of the second operand. The obtained tuples from the i th operator are saved in the temporary relation of (R tmp [i + 1]) of the following operator.
P Solving algorithm is the parallel version of A HBR algorithm. It consists in two operations, P CON T RACT (for Parallel CONTRACT), and P S SEARCH (for Parallel SEARCH ). The first operation concerns the parallelization of the CONTRACT operation, while the second one corresponds to the parallel version of the S SEARCH operation.
Algorithm 5 P Solving algorithm 1: Input: A join tree T .
2: Output : The solution for the problem.
3: T = P CON T RACT (T ). 4: P S SEARCH(T ).
The P CON T RACT operation strengths the directional arc consistency in the input hypertree. It is based on two operations, P RAKE (for Parallel RAKE), and P COM P RESS (for Parallel COMPRESS ), where RAKE and COM P RESS are the basic operations of a parallel tree contraction [9]. We explain these two operations. P RAKE operation: is based on the fact that the existence of only one resource is the reason of the sequential execution. This resource is the parent node relation. This resource must be manipulated simultaneously by all processors. Therefore, it must be shared between them. Thus, this technique consists in partitioning the parent relation between all processors which compute the semi-join operation of this last relation with its son nodes relations. These partitions are manipulated periodically between processors. P COM P RESS operation : is a pipelined execution of COMPRESS operation. It is applied on a sequence of nodes or a chain. Let {n 1 , n 2 , ..., n j } be a chain of a tree T where n i+1 is the n i 's only son, the application of P COM P RESS to this chain results in a new tree contracted T in which the node n 1 is transformed thus:
It makes a pipeline of join operations between the chain's nodes, and at each time when it takes a tuple from the probe relation, it joins it with all tuples of the corresponding partition in the hash table of the build relation. Then it communicates it to the probe relation of the next operator. After the execution of the last operator, it projects the tuples results on the variable set χ of each node of the chain, it hashes it on the intersection variables of each node with its parent node, and puts the tuple result in the corresponding node relation.
P S SEARCH algorithm is the parallel version of S SEARCH algorithm. It works in the same way, except that, each time, after taking a tuple from a parent node, the research of corresponding tuples in the son nodes is made in parallel.
For a binary hypertree, the complexity of the P SBR algorithm is
using O(h) operations in a PRAM of type EREW. r is the the maximum relation size, h is the hypertree width, P is the maximum number of tuples in the partition of hashing on the variables of ϑ (ϑ represents the intersection variables of C i with all variables in C j where j < i ). For the P Solving algorithm, its complexity is O(log n 2 ) using O(n) operations. n is the hypertree size (number of nodes).
We have developed a simulation model for P SBR and P Solving algorithms based on logical time assumptions.
Our system is composed of simple modules described as classical sequential programs, which are collected and executed in a parallel way by the simulator. A module is the set of operations performed by a processor we called a process. For the internal working of a process, we split operations that can be performed in three main types : Reading a tuple, Searching in hash tables including the tuples join operation and Writing a result tuple. These operations are executed sequentially between them and in parallel with those of the other processes. Each process explores the maximum of potential parallelism if its environment (its input variables) do not conflict during the other process execution. For a pipeline execution, if the processes are not adjacent, there is no conflict. Otherwise, we use the semaphore mechanism to synchronize them.
Each operation or each event is performed in an interval of time and the simulator must therefore keep a logical time counter. The asked question is : When we increment this counter, and what is the relation between this counter and the events execution time (physical counter)? We make a stepby-step simulation so that for each step (logical time unit) all operations which can be performed at the same time start as follows :
1. The simulator executes all processes and it increments the logical time counter at each iteration.
2. For all processes that are not in conflict, the simulator increments the physical time counter.
3. After a logical time step, the simulator updates all the shared variables.
4. It restarts a new step by considering the new variable states.
We developed a simulation of P HT R algorithm in order to check: first, if it gives good temporal and spatial complexities and second, if the new approach of parallel tree contraction proposed in this paper can be considered as an interesting alternative of the one considered in [9]. In order to compare our results, we simulate PT AC algorithm. In this section, experimentations are divided in three categories :
1. Simulation of P SBR algorithm in order to estimate its interest in term of space memory, since the sub-problems resolution is the source of a bad spatial complexity in general.
2. Simulation of P RAKE in order to evaluate its performances.
3. Simulation of P Solving algorithm in order to estimate its temporal optimization, and to measure the contribution of the new parallel tree contraction technique P Rake by leading a comparison with the one proposed in (PT AC algorithm).
The simulation has been accomplished on a PC under Linux 6.0.52 version with CPU Intel Pentium IV 2.4 GHz and 512 Mb of RAM. We use a set of benchmarks CSP which exist in the literature. We take the average of the data obtained after several executions. In our results, |V |, |E| et |r| represent respectively the variables number, the constraints number and the maximum relations cardinality. N d , N f and HT W are respectively, the nodes number, the leaf nodes number and the hypertree width. N p represents the processors number and N bS represents the number of pipeline stages.
In order to be hardware independent, measure units are Tuple for space and Operation (Reading, Searching Writing) for time.
The table 2 presents the space memory required for a pipeline (R P SBR) and no pipeline (R join) execution of the join operations for different CSP instances (consistent and inconsistent). N N W > 2 denotes the number of nodes in the hypertree with width more than 2. We observed that the gain in space memory is very important in instances for which the pipeline executions number (NNW>2) is important (haystacks-07 ). We also observed that the gain depends on the number of nodes in hypertree (mug-100-25-4 ). It is also proportional to the number of tuples by relation. As the two factors that influence on CSP problems complexity are the constraints relations size, and the structural decomposition width, and in order to estimate the contribution of P SBR, we evaluate in figure 1, in (a) and (b), the P SBR algorithm behavior w.r.t respectively the constraints relations size and the stages number in pipeline for two classes of CSP problems: aim-100-6 and full-Insertion.
N.B: P SBR algorithm forms a pipeline in each node of the hypertree. So, the stages number in the pipeline is the number of constraints in the node minus one. Figure 1 shows that more the relations size important more the memory space gain is considerable. A similar interpretation is illustrated for the stages number in pipeline.
P RAKE tries to optimize the CPU time of the whole problem. We present here a simulation of this operation by computing its efficiency Ef f = T s N P * T p where N P is the processors number and T s (reps. T p ) the time of sequential (reps. parallel) resolution of the sub-hypertree. 3 presents the obtained results for some sub-hypertrees of different CSP instances. We observed a good efficiency of P RAKE operation from 1 to ten processors. This algorithms allows a load balancing by sharing tuples to be filtered between all processors.
N.B: The number of processors used to contract a sub-hypertree is equal to the number of semi-join operations which is equal to the stages number in pipeline. The P RAKE algorithm speedup is presented in Figure 2. It is obvious that it is close to theoretical speedup (linear).
Before comparing P Solving with A HBR, it seems natural to compare P CON T RACT algorithm with an algorithm applying the tree contraction. N c represents the number of contraction operations performed and T the computational time. We have considered 1000 operations as a measure unit. Table 4 gives the CPU time of both A HBR algorithm and P T AC algorithm (CONTRACT operation) and the one of P Solving (P CON T RACT operation). It results that P CON T RACT generates a gain in temporal complexity inversely proportional to the number of contractions. More the number of the leaf nodes contracted is big more the number of contraction is less and more the gain in time is important (myc-3-4, Renault and hole-6 ), and vice versa, which is the case for hayst06 and mug25-4. We can also remark for the problem hole-6, the CPU time gain (29 instead of 1201) is considerable. This is due to the fact the hypertree is contracted on only one step, instead of taking 81 steps.
In this paper, we have presented sequential and parallel algorithms to solve CSPs by exploiting their structural properties. The algorithms exploit the hash technique. For the sequential algorithm, we have done some experiments on benchmarks from the literature and the results we have obtained are promising. Good results are observed when the number of tuples of relations is important. The parallel algorithm is based on the notion of pipeline and parallel tree contraction which is a parallel version of the well known tree contraction. We performed simulations on some benchmarks and the results are very good. Future works include the execution of our parallel algorithm on a parallel machine.