Title :
An exact algorithm for the technology fitting problem in the application specific state machine device
Author :
Perkowski, Marek A. ; Chrzanowska-Jeske, Malgorzata ; Coppola, Alan ; Pierzchala, Edmund
Author_Institution :
Dept. of Electr. Eng., Portland State Univ., OR, USA
Abstract :
The fitting problem for a new application-specific state machine device, CY7C361, from Cypress Semiconductor is formulated, and a solution is proposed. This fitting problem consists of mapping the netlist obtained from high-level synthesis into the chip´s physical resources. In general, the mapping (fitting) problem can be formulated as one of the labeled graph isomorphism between the netlist graph and the subgraph of the resources graph. However, the specific architecture-related constraints of the CY7C361 device cause the fitting problem to be generalized as a graph isomorphism problem with some additional mapping constraints. The formulation is quite general for a class of electronically programmable logic device (EPLD) fitting problems. An exact, constraint-based, tree searching algorithm with several kinds of backtracking was implemented
Keywords :
application specific integrated circuits; finite state machines; logic CAD; logic arrays; trees (mathematics); CY7C361; Cypress Semiconductor; application specific state machine device; architecture-related constraints; backtracking; electronically programmable logic device; exact algorithm; high-level synthesis; labeled graph isomorphism; netlist; resources graph; technology fitting problem; tree searching algorithm; Automata; Decision trees; Fitting; High level synthesis; Logic design; Logic devices; Macrocell networks; Programmable logic devices; Shift registers; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1992. ISCAS '92. Proceedings., 1992 IEEE International Symposium on
Conference_Location :
San Diego, CA
Print_ISBN :
0-7803-0593-0
DOI :
10.1109/ISCAS.1992.230390
