Proceedings

Optimistic Parallel biscrete Relaxation

Download BibTeX Cite

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.

  1. [Baudet, 1978] Gerard M. Baudet. Asynchronous iter- ative methods for multiprocessors. Journal of the ACM, 25(2):226-244 , April 1978.
  2. [Chazan and Miranker, 1969] D. Chazan and W . Mi- ranker. Chaotic relaxation. Linear Algebra and its Applications, 2:199-222, 1969.
  3. [Franz Inc., 1990] Franz Inc. Allegro CLiP Manual, re- lease 3.0.3 edition, March 1990.
  4. [Guesgen, 1989] Hans Werner Guesgen. CONSAT: A System for Constraint Satisfaction. Research Notes in Artificial Intelligence.
  5. Morgan Kaufmann, San Ma- teo, California, 1989.
  6. [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.
  7. [Horn, 1986] Berthold Klaus Paul Born. Robot Vision. MIT Press, Cambridge, Massachusetts, 1986.
  8. [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.
  9. [Kasif, 1990] Simon Kasif. On the parallel complexity of discrete relaxation in constraint satisfaction networks. Artificial Intelligence, 45(3):275-286, October 1990.
  10. [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.
  11. [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.
  12. [Pohlmann, 1991] Werner Pohlmann. A fixed point ap- proach to parallel discrete event simulation. Acta In- formatica, 28(7):611-629, October 1991.
  13. [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.
  14. [Schmidt, 1986] David A. Schmidt. Denotational Se- mantics: A Methodology for Language Development. Allyn and Bacon, Boston, Massachusetts, 1986.
  15. [Stoy, 1977] Joseph E. Stoy. Denotational Semantics: The Scott-Strachey Approach to Programming Lan- guage Theory. MIT Press, Cambridge, Massachusetts, 1977.
  16. [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.
  17. [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.
  18. [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.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards