(10) Concurrent Cooperative Parallel Solvers(CCOPS)

[Contents]

1. Background of the research
2. Purpose of the research
3. Contents of the research
4. Project Organization/Research Method
5. Resulting Software

[Background of the research]

Constraint Logic Programming(CLP)[9,6]has shown to be a very active field over recent years and departs from Logic Programming in replacing unification by constraint solving on a particular domain of interest, considering the solver as a black-box that is responsible for checking the consistency of a set of constraints.
Current CLP languages such as Prolog IV(PrologIA)[7], CHIP(Cosytec)[16] or clp(FD)(INRIA)[5]have investigated several constraint domains : finite domains, reals/rationals, Booleans, intervals. Finite domains, for instance, are well-suited for many real-life applications such as combinatorial problems, scheduling, cutting-stock, circuit simulation, diagnosis, decision-making, etc.
On the other hand, interval constraints [11,3,17]address non-linear numerical problems frequently encountered in engineering, economics, chemistry, etc. To address the processing of large-scale constraint systems of linear and non-linear constraints over real numbers, Boolean and integers, we propose to investigate two promising aspects of constraint solving: the combination of symbolic and numerical methods and the development of concurrent and parallel implementations of this cooperation scheme.
In effect, recent advances in the study of constraints over the real numbers (including finite domain constraints) have shown the practical advantages of combining symbolic and numerical methods. For example, combining interval Newton methods and Grobner base computations has been shown to be an efficient approach for the processing of polynomial systems [2], with many expected applications in engineering.
With respect to concurrency, its combination with constraint logic programming has been investigated since the beginning of the 90's, but mostly from the theoretical point of view, in the so-called concurrent constraint (CC) paradigm[12]. A few systems have been actually implemented such as CAL at ICOT [1], AKL(FD) at SICS [4], and the Oz system(DFKI)[14].
However most of this research has investigated concurrency issues at the language level only and has kept the constraint solving part as a black-box. The purposed research in this project is to investigate the use of concurrency in the constraint solver itself, and to develop the notion of combination and cooperation between several constraint solvers in order to improve the overall performances of the systems.

[Purpose of the research]

The purpose of this research is to develop new constraint solving techniques and to propose a general framework where several separate constraint solvers can cooperate and be combined in order to improve constraint processing. We will propose an implementation of a prototype system by using the KLIC language developed at ICOT and AITEC and a coordination language between constraint solvers. This kind of coordination should improve convergence according to the known properties of cooperating solvers combined with limited speedups when used in control-parallel execution mode: one solver per process. We also plan to investigate the relation of this approach to the data-parallel paradigm so as to make our methods scalable for use on massively parallel platforms.
More specifically, tight cooperation of symbolic and numeric solvers was shown to be efficient for solving non-linear real constraints. Symbolic methods are often used to generate redundant constraints or to simplify constraints in order to compute more accurate approximations. In this projects, we propose to merge Grobner bases computations, factorization and substitution over rational polynomial constraints, interval Newton methods and consistency techniques over arbitrary real constraints. In the course of any solver's computation, factorization and enumeration procedures give rise to disjunctions of boxes which can be treated independently, in data-parallel mode. We will study the dynamic interaction between the amount of parallelism generated in this manner and the cost of the load-balancing required to maintain proportional speedups. Particular attention will be given to the BSP(bulk-synchronous parallel) cost-prediction formulas as dynamic indicators for "steering" data-parallel solver cooperation.

[Contents of the research]

●Cooperation between solvers:

Recently, the cooperation of symbolic and interval methods for solving systems of nonlinear equations has been discussed. However, there is a need to experiment with cooperation strategies between these methods, i.e. symbolic methods can be used either as preprocessing steps or during numeric computations. As example, the efficient cooperation of Grobner bases, factorizations, substitutions, interval Newton methods and consistency techniques will be studied. Moreover, the resulting software should handle disjunctive constraints generated after factorization of polynomial equations. For this purpose, a constructive disjunction scheme for approximating disjunction of interval constraints will be explored. Moreover, disjunctions will be studied from a data-parallel point of view: how much speedup can be expected from their parallel processing.

●Data-parallelism:

In the course of any solver's computation, factorization and enumeration procedures give rise to disjunctive constraints which can in principle all be explored in parallel. But since the amount of parallelism changes dynamically and is unknown at compile time, it is not realistic to process all constraints with the same priority. If a new process is created each for each constraint of each dynamically-occurring disjunction, the parallel machine's network will become saturated and speedup will vanish. If on the other hand only a fixed number of processes are allowed to exist at any given time, then poor utilization could result from the unequal processing times required by constraints. The difficult problem of dynamic load-balancing has been studied for declarative programs in [13] and [10].
In order to maximize parallel speedup, dynamic load-balancing strategies should be designed and implemented at minimal costs. The study of such strategies will proceed in three phases. First, the effect of different solvers on the dynamic amount of available parallelism will be estimated. Then the dynamic size-distribution between the generated constraints will be quantified experimentally. Finally, the cost of load-balancing operations will be expressed as a function of size-distribution and BSP(bulk-synchronous parallel)machine parameters [8]. As a result, data-parallel algorithms will be designed and tested to trigger load-balancing through process creation/merging at a frequency driven by the balance between cost and expected speedup. A first step in this direction already exists in the form of parallel sorting methods for load-balancing(applied to database operations in [15]).

●Implementation:

We plan to use the KLIC system developed at ICOT and distributed by AITEC for the implementation of the concurrent cooperative solvers. KLIC is an efficient language with powerful synchronization primitives which has been ported to many different architectures, and it will be used has a "harness language" to encode the cooperation protocol between the solvers. The solvers themselves will be written in a low-level language such as C, in order to reuse prototypes already developed at University of Orleans and INRIA, and therefore minimize the overall implementation effort. Attention will be given to the description in KLIC of dynamic strategies for efficient cooperation: how convergence is affected by relative priorities between solvers, how efficient/ useful is control-parallelism on standard workstation networks, how dynamic should the strategies be, etc. Data-parallel algorithms will be implemented in C with either the MPI or the BSPLib libraries, both available freely on a wide variety of architectures.

[Project Organization/Research Method]