An optimal lookahead processor to prune search space
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 215-224
- https://doi.org/10.1109/fmpc.1990.89462
Abstract
The discrete relaxation algorithm (DRA) is an efficient computational technique for enforcing arc consistency (AC) in a consistent labeling problem (CLP). The original sequential AC-1 algorithm suffers from O ( n 3 m 3 ) time complexity for an n -object and m -label problem. Sample problem runs show that all these sequential algorithms are too slow to meet the need for any useful real-time CLP applications. An optimal parallel DRA5 algorithm that reaches the optimal lower bound, O ( nm ), for parallel AC algorithms (where the number of processors is polynomial in the problem size) is given. The algorithm has been implemented on a fine-grained, massively parallel hardware computer architecture. For problems of practical interest, 4 to 10 orders of magnitude of efficiency improvement can be reached on this hardware architecture Author(s) Jun Gu Dept. of Comput. Sci., Utah Univ., Salt Lake City, UT, USAKeywords
This publication has 13 references indexed in Scilit:
- Parallel algorithms and architectures for discrete relaxation techniquePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Multichip modules: next-generation packagesIEEE Spectrum, 1990
- A structured approach for VLSI circuit designComputer, 1989
- On linear search heuristicsInformation Processing Letters, 1988
- A pipelined architecture for parallel image relaxation operationsIEEE Transactions on Circuits and Systems, 1987
- A Parallel Architecture for Discrete Relaxation AlgorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Parallel Computer Architectures and Problem Solving Strategies for the Consistent Labeling ProblemIEEE Transactions on Computers, 1985
- The Consistent Labeling Problem: Part IIEEE Transactions on Pattern Analysis and Machine Intelligence, 1979
- Consistency in networks of relationsArtificial Intelligence, 1977
- Networks of constraints: Fundamental properties and applications to picture processingInformation Sciences, 1974