AITEC Contract Research Projects in FY1997:Intermediate Report

(10) Concurrent Cooperative Parallel Solvers(CCOPS)

Principal Investigator : Dr. Frederic Benhamou, Professor
Universite de Nantes & Ecole de Nantes


Title of the Research Project, Principal Investigator
(1) Title of the Research Project
Concurrent Cooperative Parallel Solvers(CCOPS)

(2) Principal Investigator
Dr. Frederic Benhamou, Professor
Universite de Nantes&Ecole de Nantes

Contents
(1)Intermediate research results

To facilitate reuse, cooperation and parallelization of solvers, a new execution model for distributed-memory systems has been designed. It represents a constraint solver as a set of closure operators acting on constraints and variable domains together with a strategy for applying them. Variable domains and constraints are local structures and accordingly, an operator represents a sequential computation. In this manner, a system design emerges where reuse of existing solvers amounts to their inclusion as operators, cooperation is a mixture of local interleaving and control-parallelism, and data-parallelism occurs when operators are coordinated between many processes. The three paradigms can be dynamically combined by strategies expressed in our system.

A high-level software design has been completed, based on the BSP model of scalable parallel programming. Computation alternates between phases of purely local solving with synchronization barriers during which necessary communications are performed. Local solving operates on explicit partitions of the constraints and variable domains while barriers and communications are triggered by contraction/expansion library calls. Resolution strategies are programmed as sequential agents and cooperation strategies as compositions of contraction and expansion.

(2)Planned schedule

- December:The above-described kernel system will be implemented in KLIC and MPI or BSP-Lib.
- December:A library of functions for defining strategies will be implemented and documented. Agent- and operator constructors, constraint system observers (variables, load distribution, constraint dependencies etc.) and communicators.
- December-january:A small library of sequential solvers for numerical constraints will be assembled. They will include symbolic and numerical solvers for finite and continuous domains.
- January-february:Source code examples involving KLIC, predefined solvers, our kernel and libraries. Small-scale parallelism by variable sharing and/or solvers competing on a shared set of constraints. Data-parallelism by solver replication on large sets of constraints and by repetitive domain splitting. Load balancing strategies to optimize data-parallelism.
- February:A monitoring system for predicting parallel performance from sequential simulation. Benchmarks on small and medium-size parallel architectures.


www-admin@icot.or.jp