Title :
Parallel exhaustive search for several NP-complete problems using content addressable memories
Author :
Yasuura, Hiroto ; Tsujimoto, Taizo ; Tamaru, Keikichi
Author_Institution :
Dept. of Electron., Kyoto Univ., Japan
Abstract :
The authors propose a simple parallel algorithm design technique for several NP-complete problems called parallel exhaustive search. Algorithms can be implemented on an SIMD (simple instruction, multiple data flow) architecture with very simple and regular array structure. Actually, the architecture is realized by a content-addressable memory (CAM). The authors design almost-linear algorithms for several NP-complete problems by this approach and estimate the performance and limitation. The computation time of the parallel algorithm for the knapsack problem using the CAM is evaluated, and it is shown that the parallel algorithm is 100 or 1000 times faster than the sequential algorithms.<>
Keywords :
computational complexity; content-addressable storage; parallel algorithms; parallel architectures; parallel programming; NP-complete problems; SIMD; almost-linear algorithms; content addressable memories; knapsack problem; parallel algorithm design technique; parallel exhaustive search; Algorithm design and analysis; Application software; Associative memory; CADCAM; Computer aided manufacturing; Computer architecture; Concurrent computing; Logic; Parallel algorithms; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1988., IEEE International Symposium on
Conference_Location :
Espoo, Finland
DOI :
10.1109/ISCAS.1988.14933
