Optimistic Parallel biscrete Relaxation
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction Problems. Pages 268-274.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
Discrete relaxation is frequently used to compute the fixed point of a discrete system X= /(X), where f is monotonic with respect to some partial order $. Given an appropriate initial value for X, discrete relaxation repeats the assignment X - /(X) until a fixed point for f is found. Monotonicity of f with respect to $ is a sufficient (but in general not necessary) condition for iterative, hill-climbing techniques such as discrete relaxation to find the fixed point of f. In this paper we introduce monotonic asynchronous iteration as a novel way of implementing parallel discrete relaxation in problem domains for which monotonicity is a necessary condition. This is an optimistic technique that maintains monotonicity without limiting concurrency, resulting in good parallel performance. We illustrate this technique with the parallel implementation of a constraint satisfaction system that computes globally consistent solutions, and present performance numbers for experiments on a shared-memory implementation. The performance numbers show that it is indeed possible to obtain a reasonable speedup when parallelizing global constraint satisfaction. We believe that monotonic asynchronous iteration is applicable to parallel discrete relaxation in general.
- [Baudet, 1978] Gerard M. Baudet. Asynchronous iter- ative methods for multiprocessors. Journal of the ACM, 25(2):226-244 , April 1978.
- [Chazan and Miranker, 1969] D. Chazan and W . Mi- ranker. Chaotic relaxation. Linear Algebra and its Applications, 2:199-222, 1969.
- [Franz Inc., 1990] Franz Inc. Allegro CLiP Manual, re- lease 3.0.3 edition, March 1990.
- [Guesgen, 1989] Hans Werner Guesgen. CONSAT: A System for Constraint Satisfaction. Research Notes in Artificial Intelligence.
- Morgan Kaufmann, San Ma- teo, California, 1989.
- [Ho, 1993] Kinson Bo. High-level abstractions for srm- bolic porallel programming. PhD thesis, Computer Science Division (EECS), University of California, Berkeley, California, 1993. To appear.
- [Horn, 1986] Berthold Klaus Paul Born. Robot Vision. MIT Press, Cambridge, Massachusetts, 1986.
- [Kasif and Rosenfeld, 1983] Simon Kasif and Azriel Rosenfeld. The fixed points of images and scenes. In Proceedings CVPR '89: IEEE Compater Societr Con- ference on Comp•ter Vision and Pattern Recognition, pages 454-456, Washington, DC, June 1983.
- [Kasif, 1990] Simon Kasif. On the parallel complexity of discrete relaxation in constraint satisfaction networks. Artificial Intelligence, 45(3):275-286, October 1990.
- [Miellou, 1975] Jean-Claude Miellou. Iterations chao- tiques a retards; etudes de Ia convergence dans le cas d'espaes partiellement ordonnes (Chaotic itera- tions with delay; studies of convergence for the case of partially ordered spaces). Comptes Rendus Heb- domadaires des Seances De L 'Academie des Sciences, 280, Series A(4):233-236, January 1975. In French.
- [Parker, 1987] D. Stott Parker. Partial order program- ming. Technical Report CSD-870067, Computer Sci- ence Department, University of California, Los Ange- les, California, December 1987.
- [Pohlmann, 1991] Werner Pohlmann. A fixed point ap- proach to parallel discrete event simulation. Acta In- formatica, 28(7):611-629, October 1991.
- [Rosenfeld et al., 1976] Azriel Rosenfeld, Robert A. Hummel, and Steven W. Zucker. Scene labeling by re- laxation operations. IEEE Transactions on Systems, Man and Cybernetics, 6(6):420-433, June 1976.
- [Schmidt, 1986] David A. Schmidt. Denotational Se- mantics: A Methodology for Language Development. Allyn and Bacon, Boston, Massachusetts, 1986.
- [Stoy, 1977] Joseph E. Stoy. Denotational Semantics: The Scott-Strachey Approach to Programming Lan- guage Theory. MIT Press, Cambridge, Massachusetts, 1977.
- [Tanaka and Uzuhara, 1990] Tomoyuki Tanaka and Shigeru Uzuhara. Multipro- cessor Common Lisp on TOP-1. In Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing, Dallas, Texas, December 1990.
- [Waltz, 1972] D. L. Waltz. Generating semantic descrip- tions from drawings of scenes with shadows. Techni- cal Report AI-TR-271, MIT Laboratory for Computer Science, Cambridge, Massachusetts, 1972.
- [Zorn et al., 1989] Benjamin Zorn, Kinson Ho, James Larus, Luigi Semenzato, and Paul Hilfinger. Multi- processing extensions in Spur Lisp. IEEE Software, 6(4):41-49, July 1989.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Discrete relaxation is frequently used to compute the fixed point of a discrete system X= /(X), where f is monotonic with respect to some partial order $. Given an appropriate initial value for X, discrete relaxation re peats the assignment X -/(X) until a fixed point for f is found. Monotonicity off with respect to $ is a suf ficient (but in general not necessary) condition for itera tive, hill-climbing techniques such as discrete relaxation to find the fixed point off [Parker, 1987].
·Ho and Hilfinger are supported by NSF Grant CCR-8451213. Guesgen performed part of this work while at the Ger man National Research Center for Computer Science (GMD). in St. Augustin, Germany, and the International Computer Science Institute in Berkekey, California. At the GMD he was supported by the German Federal Ministry for Research and Technology (BMFT) within the joint projects TEX-B (grant ITW8506D) and TASSO (grant ITW8900A7).
Discrete relaxation is widely used in the solution of constraint satisfaction problems (CSPs), and many par allel implementations of discrete relaxation for CSPs have been reported [Kasif and Rosenfeld, 1983; Rosen feld et al., 1976]. These attempts have all focused on CSP solvers that compute locally consistent (arc con sistent) solutions, which are relatively straightforward to parallelize as the computations are inherently mono tonic. On the other hand, discrete relaxation algorithms used in CSP solvers that compute globally consistent so lutions are very difficult to parallelize because for this class of problems, monotonicity is a necessary correct ness condition that is not automatically satisfied. The need to maintain monotonicity (for correctness) often limits the amount of concurrency available in a paral lel implementation, degrading the performance signifi cantly.
In this paper we introduce monotonic asynchronous iteration as a novel way of implementing parallel dis crete relaxation in problem domains for which mono tonicity is a necessary condition. This is an optimistic technique that maintains monotonicity without limiting concurrency, resulting in good parallel performance. We illustrate this technique with the parallel implementa tion of CONSAT [Guesgen, 1989], a constraint satisfac tion system that computes globally consistent solutions, and describes an experiment on a shared-memory im plementation. The performance numbers show that it is indeed possible to obtain a reasonable speedup when par allelizing global constraint satisfaction, and thus proving that Kasif's conjecture is correct [1990]. We believe that monotonic asynchronous iteration is applicable to paral lel discrete relaxation in general.
2 Discrete Relaxation
Consider the problem of finding the fixed point of a dis crete system X= /(X). For our purposes, the system has the following properties:
- f: Dx D, for some domain D, is a relation. We shall notate it as a non-deterministic function, writing, for example, Y- /(X) to mean "set Y to some value standing in relation f with X." An equation Y = /(X) means that Y is a value satisfying the relation.
- Values in Dare structured, so that for any XED, X= (X1, ... ,Xn), where X; ED; and D = D1 X ··· X Dn.
- I = { 1, ... , n} is the indez aet.
- There exist functions /e ( c ~ I) such that a solution of X= /(X) is a solution of a system of equations X= /e(X) for all c ~I, where each /e: D- Dis deterministic. Each relaxation step X- /(X) is equivalent to X- /e(X) for some c ~I. ForiE I and c~ I, /e(X) = (Y1, ... ,Yn), where
The new value of any such component i (i E c) is given by de(X) (de : D- D;). /c(X) only differs from X at the indices in c.
- f is monotonic with respect to some partial order $, i.e., X $ /(X) for any X E D. Consequently, X $ /e.(X) for any c ~ I, and X; $i de(X) for i E I. For X, Y ED, where X= (Xlt ... , Xn) and Y = (Y1, ... , Yn), X$ Y iff Xi $i }'i for all i E I.
Assumption We assume that domain-specific knowl edge has been used to ensure that f has a fixed point that can be computed in a finite number of steps us ing discrete relaxation. The precise conditions for this may be found in the lattice theory literature [Stoy, 1977; Schmidt, 1986].
Notation Let Xi denote the value of X computed in the jth iteration of a discrete relaxation, and let X 0 be the initial value of X.
Sequential Iterations Given an appropriate X 0 , dis crete relaxation repeats the assignment X -/(X) until a fixed point for f is found. In a sequential implementa tion .of discrete. relaxation,, X -/(X) becomes Xi = f(X1- 1 ), or XJ = fc(XJ- 1) for some c ~I.
For i E I and j = 1, 2, ... , a sequential iteration has the following form:
where c ~ I is not fixed for successive values of j. Xi only depends on Xi- 1 , and not on other (older) values of X.
Asynchronous Iterations We would like to compute the fixed point of f in parallel by computing fc for dif ferent values of c ( c ~ I) concurrently. For example, fc and /d (c, d ~ I) should be allowed to proceed in parallel if c and d do not intersect . This is not possible under sequential iterations, because Xi is computed using the value of X from the most recent iteration (Xi - 1) only, serializing the computations for /e and /tJ. Intuitively, fe and /tJ may be computed in parallel if the restriction that XJ is computed using the value from the most re cent iteration (Xi-1) is relaxed so that values from some relativelr recent iterations may be used instead.
Following Baudet [1978], we define aarnchrono·a iteration& by removing the restriction imposed by &eeJUential iter~ions. . An asynchronous iteration XJ = J;(x·re(J,1 ... n),XJ-1) is defined as follows:
where x·re(j,l.. .n) = (xre(j,1)' ... 'x~re(j,n)), and src(j,k) E {O, ... ,j-1}. The function src(j,k) deter mines what past value of X~; is used in the computation. For any k E I, x:re(i,t) is the value of X~: used by de to compute xf. We make two observations:
- src(j, k) is not a function of i. For any value of k E J, de (i E c) uses the value of X~: computed in iteration src(j, k), x:re(i,l:).
- For a given value of j, src(j,k) is a function of k. Consequently, the value of X~; (k E /)used to compute xf may have been computed in different it erations. This freedom reduces the amount of syn chronization required in a parallel implementation of asynchronous iterations significantly.
For example,
For sequential iterations src(j, k) = j - 1.
The value of Xi computed by an asynchronous itera tion
depends on multiple previous states. The components of X not modified by J; come from the most recent state, Xi- 1 , while the components of X modified by J; come from x·rc(j,t...n). As Xi is not computed using a single (consistent) state of X, f~ is not monotonic in general, and so xi- 1 ~ /~(Xm(i,t...n),Xi- 1 ). Conse quently, asynchronous iterations may lead to incorrect results for parallel discrete relaxations.
Monotonic Asynchronous Iterations Given an ar bitrary discrete, monotonic and non-deterministic func tion f with functions /c (c ~ I), it is relatively diffi cult to derive a condition such that the corresponding f~ functions defined by an asynchronous iteration are monotonic. To use asynchronous iteration for parallel discrete relaxation, we apply an application-specific test for monotonicity to the result computed by /~ such that if xi- 1 $ /~(x·re(i,t...n), xi- 1 ), then Xi is updated us ing this value off~ . Otherwise, /~ is re-computed (using more recent values of X). We call this optimistic scheme monotonic asynchronous iteration:

If/~ and 1:, (c, d ~I) are computed concurrently, a race occurs if X is modified by 1:, after the values of x·rc(j,l...n) used to compute dc(X'"c(j,l...n)) have been read, but before X is modified by f~. Monotonic asyn chronous iteration only detects (and rejects) races that would violate monotonicity. Races that maintain moo~ tonicity are allowed, so xi- 1 and x·rc(j ,l.. .n) do not have to be equal. In fact , these legal races provide a source of concurrency not found in other parallel relax ation schemes, and lead to improved performance. Intu itively, /c and /d may be computed concurrently if they modify disjoint components of X, or if they modify com mon components of X in such a way that monotonicity between successive values of X is maintained.
We do not have a general way of deriving the application-specific test for monotonicity for a given sys tem. Instead, we expect the programmer to provide this test by using high-level knowledge about the problem d~ main. In the context of CSP solvers that compute glob ally consistent solutions, this test reduces to a subset test between successive sets of value combinations that may be associated with the variables of a constraint network (see Section 3).
Parallel Implementation of Monotonic Asyn chronous Iterations A step of a monotonic asyn chronous iteration Xi = /~(X'"c(j, l...n) , Xi-1) with par tial order $ may be implemented in parallel in the fol lowing way:
- Read current value of X, x·rc(j ,l.. .n) _ (X'"c(j,1) x·rc(J,n)) - 1 ' .. . , n (X~;s may come from different iterations.)
- Unlock X
2. Compute d c(X'"c(j,l...n)) for all i E c 3. Lock X 4. if V i E c: Xf - 1 $ dc(Xm(j,l.. .n)) then for each i E c, update X:X{ = d c(X'"c(j,l...n)) else schedule f~ for re-execution
X is not locked while the dc(X'"c(j,l...n)) values are computed in step 2. If these computations are time consuming, this implementation can lead to much better parallel performance than a naive alternative that locks X for the entire step of the monotonic asynchronous iter ation. Nevertheless, the maximum speedup is bounded by 1 + (T1 + T2)/T4, where T; is the time for step i. For example, if T4 is 10% of (T1 + T2), the speedup limit is 11.
Practical Considerations Monotonic asynchronous iteration does not specify how a function f~ (c ~ I) is chosen for execution in any iteration j, or whether /~ and 1:, (c, d ~ I) should be executed concurrently in a parallel implementation for optimal performance. There is considerable freedom in applying application-specific scheduling strategies for good performance.
3 Example: CONSAT
CONSAT is a system for the definition and satisfaction of constraints in arbitrary finite discrete domains. A constraint consists of a set of variables and a relation among the variables, and a constraint network is a set of constraints connected by common variables. A glob ally consistent solution of a constraint network is a tuple of values, one per variable of the network, that satisfies all the constraints of the network simultaneously. CON SAT is a global CSP solver whose constraint satisfaction technique is based on filtering [Waltz, 1972], i.e., on the successive deletion of inconsistent values from the set of potential values for the variables. Unlike traditional filtering algorithms, CONSAT uses values that are~ dated with some additional information (called tags) for maintaining interrelationships among values (of different variables). In the following we give an informal explana tion of how CONSAT modifies local constraint propaga tion, a technique commonly used to compute locally con sistent solutions, with tagging to compute the globally consistent solutions of a constraint network. As global constraint satisfaction problems over finite domains are generally NP-complete, the algorithm used by CONSAT is exponential in the worst case. A more formal treat ment of CONSAT is given elsewhere [Guesgen, 1989].
Constraint Network Example Figure 1 defines con straint network A, which will be used in the examples throughout this paper. There are three variables (Va, Vb, Vc) and six constraints (C1-C6). For example, con straint C1 restricts the possible values of Va to R or Y, and constraint C4 restricts the values of (Va,Vb) to one of the combinations (R,G) or (R,B). Va and Vb are called the adjacent variables of constraint C4. (A constraint may be adjacent to more than two variables, i.e., we do not restrict ourselves to binary constraints.) · The steps of CONSAT as it computes the global solutions of con straint network A are shown in Figure 2. Details of the algorithm used may be found elsewhere [Guesgen, 1989].

Tagged Values For any variable of a constraint net work, the potential values are associated with additional information called tags, and tagged values (of different variables) with the same full tag form a global solution of the constraint network. For a constraint network of
| Initial: | Step | |
|---|---|---|
| Va • | Vb • Vc • UnConstrained | 0 |
| C1: | Va • { R(1,-,-,-,-,-), Y(2,-,-,-,-,-) } | 1 |
| C2: Vb• { 0(-,1,-,-,-,-), C3: Vc • | Y(-,2,-,-,-,-), 8(-,3,-,-,-,-) } { 8(-,-,1,-,-,-), T(-,-,2,-,-,-), 0(-,-,3,-,-,-) } | 2 3 |
| • { R(1,1,-,1,-,-), R(1,3,-,2,-,-) } | 4 | |
| C4: | Va Vb • { 0(1,1,-,1,-,-), 8(1,3,-,2,-,-) } | |
| CS: | Vb• { 0(1,1,1,1,1,-), 8(1,3,3,2,2,-) } Vc • { 8(1,1,1,1,1,-), 0(1,3,3,2,2,-) } | 5 |
| C6: | Va • { R(1,1,1,1,1,1), R(1,3,3,2,2,2) } Vc • { 8(1,1,1,1,1,1), 0(1,3,3,2,2,2) } | 6 |
| C4: | Va • { R(1,1,1,1,1,1), R(1,3,3,2,2,2) } Vb• { "0(1,1,1,1,1,1), 8(1,3,3,2,2,2) } | . 7 . |
| CS: | Vb• { 0(1,1,1,1,1,1), 8(1,3,3,2,2,2) } Vc • { 8(1,1,1,1,1,1), 0(1,3,3,2,2,2) } | 8 . |
| C1: | . 9 | |
| Va • { R(1,1,1,1,1,1), R(1,3,3,2,2,2) } | ||
| C2: | Vb • { 0(1,1,1,1,1,1), 8(1,3,3,2,2,2) } | • 10 |
| C3: Vc • { 8(1,1,1,1,1,1), 0(1,3,3,2,2,2) | } | • 11 |
| Solution(Va, Vb, Vc): | ||
| (R(1,1,1,1,1,1), 0(1,1,1,1,1,1), 8(1,1,1,1,1,1)) (R(1,3,3,2,2,2), 8(1,3,3,2,2,2), 0(1,3,3,2,2,2)) | ||
Figure 2: Activations of constraint network A: Each con straint being activated (leftmost column) is shown with the feasible sets of its adjacent variables after its activa tion. An "*" at the end of a variable means that it has not been changed in the current activation. The feasible set of any variable non-adjacent to the current constraint can be found by searching backwards from the current activation. (Componentwise unification offull tags is the key idea behind the algorithm.)
(Va,Vb,Vc) · (R,0,8) vith full tag (1,1,1,1,1,1) C1(Va) · { R,Y } C2(Vb) · { O,Y,8} C3(Vc) · { 8,Y,O} C4(Va,Vb) · { (R,O), (R,8) } CS(Vb,Vc) · { (0,8), (8,0) } C6(Va,Vc) · { (R,8), (R,O) } 1 Va · R 1 Vb · 0 1 Vc · 8 1 (Va,Vb) · (R,O) 1 (Vb,Vc) · (0,8) 1 (Va,Vc) · (R,8) (Va,Vb,Vc) · (R,8,0) vith full tag (1,3,3,2,2,2) C1(Va) · { R,Y} C2(Vb) · { O,Y,8} C3(Vc) · { 8,Y,O} C4(Va,Vb) · { (R,G), (R,8) } CS(Vb,Vc) · { (0,8), (8,0) } C6(Va,Vc) · { (R,8), (R,G) } 1 Va · R 3 Vb · 8 3 Vc · 0 2 (Va,Vb) · (R,8) 2 (Vb,Vc) · (8,0) 2 (Va,Vc) · (R,G)
m constraints, each full tag is an m-tuple, where the rth component (the rth nbtag) indicates the tuple in the rth constraint that is part of the global solution. (For example, in constraint Col of Figure 1 the tuple (R,B) corresponds to the subtag 2.) The special symbol "-" is the wildcard character for subtags and indicates that a tuple for the corresponding constraint has not been chosen. A subtag with a tuple number is said to be determined, while one with the special symbol "-" is said to be tmdetermined. As an example, consider the global solutions of constraint network A shown in Figure 2. The two solutions (Va, Vb, Vc) are (R,G,B) with full tag (1,1,1,1,1,1) and (R,B,G) with full tag ( 1 , 3, 3, 2, 2, 2). An intuitive explanation of the use of tags for constraint network A is given in Figure 3.
Filtering of Tagged Values The fea&ible &et of a vari able contains its current set of potential (tagged) values, and is initialized to the special value UnConatrained, meaning the variable may take any value from the do main under consideration. The filtering function f of the constraint network uses local propagation of tagged values to eliminate inconsistent values from the feasi ble sets, and replaces undetermined subtags with deter mined subtags. Guesgen showed in his thesis that filter ing of tagged values is guaranteed to terminate with the globally consistent solutions of a constraint network in a finite number of steps provided that it is fair [1989]. This means each constraint is evaluated (or activated) at least once, and if a constraint changes the feasible set of any adjacent variable during filtering, other con straints adjacent to the modified variable have to be re activated. (This is not the usual definition of fairness in the parallel programming literature.) Upon termina tion of local propagation, each tuple of values-one per variable-with identical full tags form a globally consis tent solution of the constraint network (see Figure 2). If the feasible set of any variable becomes empty, there is no solution for the constraint network. Local propaga tion computes the fixed point of the filtering function f of the constraint network.
Filtering is Monotonic with respect to Partial Order :5 of Tagged Values For two tagged val ues v4 and v· with identical domain values, V4 :5 v· iff every determined rth subtag in v4 has an identical rth subtag in "·. For example, R( 1,-,-,-,-,-) :5 R( 1,1,-, 1,-,-) < R( 1,1, 1,1, 1,1). For two sets of tagged values v and w, we extend the definition such that V :5 W iff for every w E W, there exists v E V such that v :5 w. In addition, :5 is defined such that UnConstrained :5 V for any set of tagged values V. For the activation of constraint network A in Figure 2, Va.Step1 = { R(1,-,-,-,-,-), Y(2,-,-,-,-,-) }, Va.Step4 = { R(1,1,-,1,-,-), R(1,3,-,2,-,-) }, so Va.Step1 :5 Va.Step4.
Intuitively, filtering either eliminates a tagged value if it is inconsistent, or replaces one or more undetermined subtags of a tagged value by determined subtags. A de termined subtag is never replaced by an undetermined sub tag or another determined sub tag. A more formal ex planation of why filtering of tagged values is monotonic with respect to ::5 will be given elsewhere [Ho, 1993].
CONSAT as Discrete Relaxation In this section we show that CONSAT is a special case of discrete re laxation as defined in Section 2.
- CONSAT computes the fixed point of the discrete system X= /(X) for the non-deterministic f that corresponds to the filtering function of the entire constraint network. This fixed point corresponds to the set of all the globally consistent solutions of the constraint network.
- I = { 1, ... , n} is the set of all the variables of the constraint network.
- f may be decomposed into component functions/c for constraints c ~ I. fc: D - D is the filtering function of constraint c, and eliminates value com binations inconsistent with c from the feasible sets of its adjacent variables. Without loss of generality, we assume that a constraint may be uniquely iden tified by its set of adjacent variables. For example, /{2,3,5} is the filtering function of the constraint that is adjacent to variables 2, 3 and 5. /c only depends on the values of variables i E c, and /c(X) only dif fers from X for the same set of variables. The new value of any such variable i is given by dc(X).
- For X E D, X = (Xt, ... ,Xn)· Each X; ED; is the feasible set of variable i.
- X 0 is the initial state of the feasible sets of all the variables. All its components have the special value UnConstrained
- The partial order $ on D has been defined on page 4.
We have shown that CONSAT is a special case of dis crete relaxation, and have defined an application-specific monotonicity test between successive states of the relax ation. Consequently, an efficient parallel implementation of CONSAT may be obtained by using monotonic asyn chronous iteration.
Performance We implemented parallel CONSAT us ing CLiP [Franz Inc., 1990], a commercial imple mentation of the multiprocessing features of SPUR Lisp [Zorn et al., 1989] that currently runs on the shared memory Sequent Symmetry multiprocessor. To esti mate the performance of parallel CONSAT in the ab sence of garbage collection-an upper bound on paral lel performance-we define speedup as the ratio of real time excluding garbage collection of the sequential ver sion relative to the real time (excluding garbage collec tion) of the parallel version on n processors. This def inition is chosen because the current CLiP implemen tation uses a sequential garbage collector that stops all but one processor each time a collection occurs. We feel our definition better models the performance of parallel CONSAT in a parallel Lisp system with a more realis tic garbage collector, such as the concurrent collector in TOP-1 Common Lisp [Tanaka and Uzuhara, 1990].
We measured the parallel performance of CONSAT for a problem in machine vision, which assigns three dimensional edge labelings (convex, concave, or occluding) to line drawings in a polyhedral world of trihedral vertices [Horn, 1986]. The constraints restrict the la beling of edges meeting at a vertex to be the few com binations physically p088ible. In addition, each edge is constrained to have the same label at both ends (where it meets other edges). The particular scene (constraint network) cboeen, StairS, has 33 variabl~ and 56 con straints (36 2-variable and 20 3-variable constraints).
| 2 | 50 | 7 |
| 3 | 36 | 10 |
| 4 | 28 | 13 |
| 5 | 25 | 17 |
| 6 | 20 | 16 |
The results for StairS are summarized in Table 1. Speedup ranges between 0.9 on one processor to 4.6 on six processors. The one processor time is within 5% of the sequential time, showing that the parallel implemen tation is reasonably efficient. The speedup is less than linear because a small number of constraint activations (relaxation steps) have to be re-executed because they vi olate monotonicity. Serial bottlenecks in the allocation routines of the current CLiP implementation also pre vent parallel CONSAT from achieving better speedup.
An earlier parallel implementation of CONSAT that performs the update to the feasible sets (X) in a single critical section for each constraint activation has virtu ally no speedup because contention for X serializes all the concurrent constraint activations. The current im plementation based on monotonic asynchronous itera tion performs significantly better.
4 Related Work in Parallel Relaxation
The formulation of asynchronous iterations in Section 2 is similar to generalized iterations defined by Pohlmann in the context of parallel discrete event simulation [1991]. Generalized iterations operate in the domain of infinite streams of elements, each of which corresponds to an event over time in the system being simulated.
Parallel relaxation is also used by various schemes for solving systems of equations X -/(X) in the domain of real numbers in parallel, including chaotic relaxations defined by Chazan and Miranker [1969], asynchronous it erations defined by Baudet [1978] and chaotic iterations with delay defined by Miellou [1975]. In these systems f is made up of component functions /e, and the state X of the fixed-point computation may be decomposed into a set of (potentially disjoint) components that are computed by different /e functions concurrently. Each le may be computed using m·ltiple previous states, with a different state for each component of X, to minimize the amount of synchronization required. These schemes are optimized for the domain of real numbers by using the properties of real numbers, and their convergence criteria are somewhat analogous to the test for mono tonicity used in monotonic asynchronous iterations. Our formulation of asynchronous iterations for parallel dis crete relaxation is a domain-independent generalization of these parallel iteration schemes. In addition, the use of an optimistic test for monotonicity for improved par allel performance is unique to our approach.
5 Conclusion
In this paper we proposed monotonic asynchronous it eration as a correct and efficient way of implementing parallel discrete relaxation for systems for which mono tonicity is a necessary correctness condition. Mono tonic asynchronous iteration uses an optimistic scheme to compute a possible next state of the system. This optimistic scheme is highly efficient but is not necessar ily monotonic (i.e., correct). An application-specific test for monotonicity is then applied to the computed state. If the test succeeds, the state transition is made (atom ically). Otherwise, the computation is repeated using the current state. We have applied our technique to the parallel implementation of a constraint satisfaction system that computes globally consistent solutions, for which monotonicity is a necessary correctness condition that is not automatically satisfied. We believe monotonic asynchronous iteration is applicable to parallel discrete relaxation in general. It will be interesting to see if this application-specific monotonicity test is easy to derive for other discrete relaxation problems.
6 Acknowledgements ·
We thank Suresh Krishna for translating Miellou's paper on chaotic iterations from French into English, and Ed Wang for explaining the subtleties of lattice theory. We also thank Chu-Cheow Lim, Ed Wang, Luigi Semenzato and Kathy Yelick for their comments on various drafts of this paper.
@inproceedings{ijcai1993p38,
title = {Optimistic Parallel biscrete Relaxation},
author = {Ho, Kinson and Hilfinger, Paul N. and Guesgen, Hans W.},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {268--274},
year = {1993},
note = {Constraint Satisfaction Problems},
url = {https://ijcai.org/proceedings/1993/38},
}
TY - CPAPER TI - Optimistic Parallel biscrete Relaxation AU - Ho, Kinson AU - Hilfinger, Paul N. AU - Guesgen, Hans W. T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 268 EP - 274 UR - https://ijcai.org/proceedings/1993/38 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: