AUTOMATIC STATE-SPACE DECOMPOSITION FOR APPROXIMATE FSM TRAVERSAL BASED ON CIRCUIT ANALYSIS

Exploiting circuit structure is a key issue in the implementation of a lgorithms for state space decomposition when the target is approximate FSM traversal, Given the gate-level description of a sequential circu it, 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 sequent ial circuit: Latch connectivity and latch correlation. The first one t akes 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 affini ty of two latches by combining these two factors, and rye use this mea sure to formulate the state space decomposition problem as a graph par titioning problem. We propose an algorithm to automatically determine ''good'' partitions of the latch set which induce state space decompos ition, and we present approximate FSM traversal and logic optimization results for the largest ISCAS'89 sequential benchmarks.