Title :
A neural network approach to PLA folding problems
Author :
Tsuchiya, Kazuhiro ; Takefuji, Yoshiyasu
Author_Institution :
Fac. of Environ. Inf., Keio Univ., Fujisawa, Japan
fDate :
10/1/1996 12:00:00 AM
Abstract :
A near-optimum parallel algorithm for solving PLA folding problems is presented in this paper where the problem is NP-complete and one of the most fundamental problems in VLSI design. The proposed system is composed of n×n neurons based on an artificial two-dimensional maximum neural network where n is the number of inputs and outputs or the number of product lines of PLA. The two-dimensional maximum neurons generate the permutation of inputs and outputs or product lines. Our algorithm can solve not only a simple folding problem but also multiple, bipartite, and constrained folding problems. We have discovered improved solutions in four benchmark problems over the best existing algorithms using the proposed algorithm
Keywords :
VLSI; circuit CAD; combinational circuits; computational complexity; integrated circuit design; logic CAD; neural nets; parallel algorithms; programmable logic arrays; NP-complete; PLA folding problems; VLSI design; benchmark problems; bipartite folding; constrained folding; multiple folding; near-optimum parallel algorithm; neural network approach; product lines; two-dimensional maximum neural network; two-dimensional maximum neurons; Algorithm design and analysis; Circuit testing; Combinational circuits; Logic design; MOS devices; Neural networks; Neurons; Parallel algorithms; Programmable logic arrays; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
