Abstract
Filtering algorithms are well accepted as a means of speeding up the solution of the consistent labeling problem (CLP). Despite the fact that path consistency does a better job of filtering than arc consistency, AC is still the preferred technique because it has a much lower time complexity. We are implementing parallel path consistency algorithms on multiprocessors and comparing their performance to the best sequential and parallel arc consistency algorithms.(1,2) (See also work by Kerethoet al. (3) and Kasif(4)) Preliminary work has shown linear performance increases for parallelized path consistency and also shown that in many cases performance is significantly better than the theoretical worst case. These two results lead us to believe that parallel path consistency may be a superior filtering technique. Finally, we have implemented path consistency as an outer product computation and have obtained good results (e.g., linear speedup on a 64K-node Connection Machine 2).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Steven Y. Susswein, Parallel Path Consistency, Master's Thesis, University of Utah, Salt Lake City, Utah (March 1991).
Steven Y. Susswein, Thomas C. Henderson, Joe Zachary, Chuck Hansen, Paul Hinker, and Gary C. Marsden, Parallel Path Consistency, Technical Report TR-91-010, University of Utah, University of Utah, Department of Computer Science, Salt Lake City, Utah (August 1991).
S. Keretho and R. Loganantharaj, On the Parallel Complexity of Constraint Propagation Algorithms for Temporal Reasoning, Technical Report TR-91-2-4, Center for Advanced Computer Studies, University of Southwest Louisiana (1991).
S. Kasif, On the Parallel Complexity of Discrete Relaxation in Constraint Satisfaction networks,Artificial Intelligence,45(11):275–286 (1990).
A. K. Mackworth, Consistency in Networks of Relations,Artificial Intelligence,8:99–118, (1977).
J. Gaschnig, A. Constraint Satisfaction Method for Inference Making,Proc. 12th Annual Allerton Conf. Circuit and Systems Theory, pp. 866–874 (1974).
J. Gaschnig, Performance Measurement and Analysis of Certain Search Algorithms, Technical Report CMU-CS-79-124, Carnegie-Mellon University (May 1979).
R. A. Hummel and S. W. Zucker, On the Foundations of Relaxation Labeling Processes,IEEE Transactions on Pattern Analysis and Machine Intelligence,5(3):267–286 (May 1983).
R. Haralick and L. Shapiro, The Consistent Labeling Problem,IEEE Transactions on Pattern Analysis and Machine Intelligence,1(2):173–183 (April 1979).
R. M. Haralick and G. Elliot, Increasing Tree Search Efficiency for Constraint Satisfaction Problems,Artificial Intelligence,14:263–313 (1980).
J. F. Allen, Maintaining Knowledge about Temporal Intervals,Communications of the ACM,26(11):832–843 (November 1983).
Peter B. Ladkin and Roger D. Maddux, Parallel Path Consistency Algorithms for Constraint Satisfaction, Technical Report TR89-045, International Computer Science Institute, Berkeley, California (August 1989).
U. Montanari, Networks of constraints: Fundamental Properties and Application to Picture Processing,Information Sciences,7:95–132 (1974).
A. K. Mackworth and E. C. Freuder, The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems,Artificial Intelligence,25:65–74, (1985).
Roger Mohr and Thomas C. Henderson, Arc and Path Consistency Revisitied,Artificial Intelligence,28(2):225–233 (March 1986).
A. K. Samal,Parallel Split-Level Relaxation, PhD Thesis, University of Utah, Salt Lake City, Utah (August 1988).
Ashok Samal and Thomas C. Henderson, Parallel Consistent Labeling Algorithms,IJPP,16(5):341–364 (1988).
Thomas C. Henderson,Discrete Relaxation Techniques, Oxford University Press, New York (1990).
Ching-Chih Han and Chia-Hoang Lee, Comments on Mohr and Henderson's Path Consistency Algorithm,Artificial Intelligence,36(1):125–130 (August 1988).
Rina Dechter and Itay Meiri, Experimental Evaluation of Preprocessing Techniques in Constraint Satisfaction Problems,Proceedings of IJCAI, pp. 271–277 (1989).
B. Nadel, Constraint Satisfaction Algorithms,Computational Intelligence,5(4):188–224 (November 1989).
Gary C. Marsden, Fouad Kiamilev, Sadik Esener, and Sing H. Lee, Highly Parallel consistent Labeling Algorithm Suitable for Optoelectronic Implementation,Applied Optics,30(2):185–194 (1991).
Thinking Machines Corporation,Model CM-2 Technical Summary (April 1987).
D. Hillis,The Connection Machine, MIT Press, Cambridge, Massachusetts (1985).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Susswein, S.Y., Henderson, T.C., Zachary, J.L. et al. Parallel path consistency. Int J Parallel Prog 20, 453–473 (1991). https://doi.org/10.1007/BF01547895
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01547895