Automatic state space decomposition for approximate FSM traversal based on circuit analysis
- 1 January 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 15 (12) , 1451-1464
- https://doi.org/10.1109/43.552079
Abstract
Exploiting circuit structure is a key issue in the implementation of algorithms for state space decomposition when the target is approximate FSM traversal. Given the gate-level description of a sequential circuit, the information about its structure can be captured by evaluating the affinity between pairs or groups of latches. Two main factors have to be considered in carrying out the structural analysis of a sequential circuit: latch connectivity and latch correlation. The first one takes into account the mutual dependency of each memory element on the others; the second one tells us how related are the functions realized by the logic feeding each latch. In this paper we estimate the affinity of two latches by combining these two factors, and we use this measure to formulate the state space decomposition problem as a graph partitioning problem. We propose an algorithm to automatically determine “good” partitions of the latch set which induce state space decomposition, and we present approximate FSM traversal and logic optimization results for the largest ISCAS'89 sequential benchmarksKeywords
This publication has 12 references indexed in Scilit:
- Combinational profiles of sequential benchmark circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- ATPG aspects of FSM verificationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient implementation of a BDD packagePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Implicit state enumeration of finite state machines using BDD'sPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A unified framework for the formal verification of sequential circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Sequential circuit verification using symbolic model checkingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Redundancy identification/removal and test generation for sequential circuits using implicit state enumerationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Representing circuits more efficiently in symbolic model checkingPublished by Association for Computing Machinery (ACM) ,1991
- MIS: A Multiple-Level Logic Optimization SystemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970