FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 |

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

-- [ Page 1 ] --

A Component-Based Parallel Constraint Solver

Peter Zoeteweij and Farhad Arbab

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


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 effectively 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 specific class of constraint satisfaction problems (CSP’s). By having different solvers, supporting different 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. Efficient algorithms exist for some classes of CSP’s, and when completeness is not important we may be able to find 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 specific 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 Scientific 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 sufficiently small to ensure that enough subproblems are available to keep all solvers busy, and sufficiently 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


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 benefits.

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 finding 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 defined 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 satisfies 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 different 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 fixpoint 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-first 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 effectively implements a depth-first traversal. Other traversal strategies exist, but depth-first 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 justified 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 specified 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 first need to recall the definition of timed data streams from [5].

A stream over some set A is an infinite sequence of elements of A. Zerobased indices are used to denote the individual elements of a stream, e.g., α(0), α(1), α(2),... denote the first, second, third, etc. elements of the stream α. Also α(k) denotes the stream that is obtained by removing the first 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 infix 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 specification 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 defined behavior. In Section 3.2 we use Reo connectors to specify the coordination of our component solvers.

3 Specification

3.1 Component Solver

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

Let P be a finite set of problems and let (P ∪ { }, ) be a partial order such that for all p ∈ P, p. For a problem p ∈ P, we define 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, defined as

–  –  –

where S is a relation on P and 2P, such that for all p ∈ P and R ∈ 2P, S(p, R) iff – ∀r ∈ R, p r, – ∀r, s ∈ R, r s implies r = s, and – sol (p) = ∪r∈R sol (r) The Str (streamer) ABT specifies 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, defined 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 notification “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 defines

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 filters: 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 filters. Channel bc filters 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 specified in [4].

–  –  –

Pages:   || 2 | 3 |

Similar works:

«Abschlussbericht zum UFO-PLAN-Vorhaben Abfallwirtschaftskonferenz 2007 Exportmöglichkeiten der deutschen Abfallwirtschaft in Industrie-, Schwellenund Entwicklungsländer, FKZ: 907 14 615 im Auftrag von: BMU Bundesministerium für Umwelt, Naturschutz und Reaktorsicherheit Robert-Schuman-Platz 3 53175 Bonn vorgelegt von: ARGUS Arbeitsgruppe Umweltstatistik an der Technischen Universität Berlin e.V. Franklinstr. 1 10587 Berlin in Kooperation mit: EITEP Euro Institute for Information and...»

«DISS. ETH Nr. 16286 WECHSELWIRKUNG ZWISCHEN FÖHN UND PLANETARER GRENZSCHICHT ABHANDLUNG zur Erlangung des Titels DOKTOR DER NATURWISSENSCHAFTEN der EIDGENÖSSISCHEN TECHNISCHEN HOCHSCHULE ZÜRICH vorgelegt von Stefan Gubser dipl. math., Universität Bern geboren am 09. November 1970 von Kriens, Schweiz Angenommen auf Antrag von Prof. Dr. Hans Richner, Referent Prof. Dr. Reinhold Steinacker, Korreferent Prof. Dr. Huw Davies, Korreferent Inhaltsverzeichnis Zusammenfassung Summary Verzeichnis der...»

«COPYRIGHT NOTICE: Andrew H. Kydd: Trust and Mistrust in International Relations is published by Princeton University Press and copyrighted, © 2005, by Princeton University Press. All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher, except for reading and browsing via the World Wide Web. Users are not permitted to...»

«Schnelleinstieg Die Abbildungen in dieser Anleitung wurden unter Windows® 7 erstellt, soweit nicht anders vermerkt. Ihr Aussehen kann unter anderen Betriebssystemen abweichen. WICHTIG! Aus technischen Gründen muss der Name des Druckertreibers „Nuance PDF Create“ durch den ursprünglichen Namen „ScanSoft PDF Create!“ ersetzt werden. Damit wird der Funktionalität der weltweit eingesetzten älteren Versionen unserer Produkte entsprochen. In dieser Dokumentation ist der...»

«Lights, Cameras, and Assemblies! Animating using Autodesk® Inventor® Studio Mark Allen Flayler : ASCENT – Center for Technical Knowledge® ML311-3 Autodesk Inventor Studio bridges the gap between engineering and marketing. This class presents methods to create an animation of an assembly using moving cameras and lights. Learn how to animate components in your assembly, animate lights, and animate cameras. Finally, you’ll see how to combine animations using the new Video Producer feature....»

«De Re Atari Converted by Andreas Bertelmann for ABBUC www.abbuc.de Preface Introduction by enter value here This manual is about the ATARI Home Computer. It covers both the ATARI 400TM and the ATARI 800TM Computers. These two computers are electrically identical, differing only in mechanical features such as the keyboards and cartridge slots. The purpose of this manual is to explain in detail how to use all the features of the ATARI Computer. Because this is a complex and powerful machine, the...»

«Ecole polytechnique fédérale de Zurich Eidgenössische Politecnico federale di Zurigo Technische Hochschule Swiss Federal Institute of Technology Zurich Zürich Semesterarbeit Kurvenmodellierung magnetischer Eigenschaften von antiferromagnetischen Nanopartikeln Gabriela Stamm SS 05 Betreuung: Franziska Brem, Institut für Geophysik, Gruppe für Magnetik, ETH Zürich Inhaltsverzeichnis 1 Zusammenfassung.. 3 2 Einleitung.. 3 3 Theorie.. 4 4 Vorgehen.. 7 5 Resultate.. 8 6 Diskussion.. 14 7...»

«13. Interacting single molecules 13.1. Basic interaction mechanisms We already had to consider the interactions of an absorbing molecule with the surrounding matrix molecules. These interactions are responsible for, among others, the solvent shift. They arise from Van der Waals (or dispersive) forces and shortrange repulsion between molecular electronic clouds, from electrostatic and polarization interactions, from specific effects such as hydrogen-bonds, etc. In such interactions, the...»

«Diss. ETH No. 14465 Modelling of Combustion and Nitric Oxide Formation for Medium-Speed DI Diesel Engines: A Comparative Evaluation of Zeroand Three-Dimensional Approaches A thesis submitted to the SWISS FEDERAL INSTITUTE OF TECHNOLOGY ZURICH for the degree of Doctor of Technical Sciences presented by German Andreas Weisser Dipl. Ing. Universität (TH) Karlsruhe born May 7, 1965 German citizen Accepted on the recommendation of Prof. Dr. M.K. Eberle, examiner Prof. Dr. D. Poulikakos, co-examiner...»

«Biogenic Amine Transporters 25 Mechanisms of Biogenic Amine Neurotransmitter Transporters Gary Rudnick 1. INTRODUCTION The biogenic amine transporters, as described in Chapters 1, 3, and 5 of this book, terminate the action of released biogenic amine neurotransmitters. These transporters utilize norepinephrine (NE), dopamine (DA), and serotonin (5-HT), and are referred to as NET, DAT, and SERT, respectively. Interruption of their function by agents such as antidepressants and stimulants causes...»

«Dynamics of submarine debris flow and tsunami Shiva P. Pudasaini Acta Mechanica ISSN 0001-5970 Volume 225 Number 8 Acta Mech (2014) 225:2423-2434 DOI 10.1007/s00707-014-1126-0 Your article is protected by copyright and all rights are held exclusively by SpringerVerlag Wien. This e-offprint is for personal use only and shall not be self-archived in electronic repositories. If you wish to self-archive your article, please use the accepted manuscript version for posting on your own website. You...»

«Your Statistical Consultant: Answers to Your Data Analysis Questions Rae R. Newton Do you ever think at a loss on the best way to continue with a specific set of data? Your Statistical advisor supplies the answer. This complete advisor introduces, describes, and makes techniques relating to tricky statistical difficulties and techniques. The authors speak about universal difficulties by way of addressing commonly asked questions; supply a conceptual evaluate of themes and techniques; supply...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.