Fuzzy c-mean clustering-based decomposition with GA optimizer for FSM synthesis targeting to low power

摘要

Reduction on both switching and leakage power has become a research focus in VLSI design. It makes sense that finite-state machine (FSM) as a main component can contribute to low power of VLSI circuit. Decomposition has been proven an effective strategy for saving power in FSM synthesis. In order to achieve low power in FSM synthesis, a Fuzzy c-mean clustering-based decomposition method, called FCM-D, is proposed in this study. FCM-D used Fuzzy c-mean clustering (FCM) method to partition a set of states of FSM into a collection of c fuzzy clusters; hence, a FSM can be decomposed into a set of c sub machines, of which the inactive ones would not consume the power. For achieving low power, the objective function of FCM-D is defined on minimization of the cross state transition probability between sub machines and increasing the inner state transition probability within each submachine. For overcoming the local optimum, Genetic Algorithm (GA) is employed as an optimizer of FCM-D, which applies selection, crossover and mutation on FCM-D to generate better centers and more appropriate clusters. This hybrid method is denoted as FCM-D + GA. We test FCM-D + GA extensively on more than thirty benchmarks in LGSynth93 library, and compare it with previous FSM synthesis methods from various aspects. The experimental results show FCM-D + GA achieved a significant cost reduction of switching power and leakage power dissipation over the previous publications.