Title :
Systolic architecture for solving NP-hard combinatorial problems of logic design and related areas
Author :
Ho, Phuong Minh ; Perkowski, Marek A.
Author_Institution :
Dept. of Electr. Eng., Portland State Univ., OR, USA
Abstract :
A new approach to solving various NP-hard problems in logic synthesis, logic programming, graph theory, and related areas is presented. A problem to be solved is reduced to solving one or several generic combinatorial problems; this is called generalized propositional formula (GPF) minimization. A special massively parallel computer architecture for GPF minimization is discussed. The architecture is composed of a host computer and a data-flow tree of processors (Boolean product processor, or BPP). Each BPP consists of a product management unit and a sorting and absorbing architecture
Keywords :
combinatorial switching; logic CAD; minimisation of switching nets; parallel architectures; Boolean product processor; NP-hard combinatorial problems; absorbing architecture; data-flow tree; generalized propositional formula; generic combinatorial problems; graph theory; host computer; logic design; logic programming; logic synthesis; massively parallel computer architecture; minimization; product management unit; sorting architecture; Computational modeling; Computer architecture; Ducts; Hardware; Labeling; Logic design; Logic devices; Logic programming; NP-hard problem; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1989., IEEE International Symposium on
Conference_Location :
Portland, OR
DOI :
10.1109/ISCAS.1989.100561
