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

Volume

4

fYear

1992

fDate

3-6 May 1992

Firstpage

1977

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ISCAS.1992.230390

Filename

230390