USING SAT-BASED TECHNIQUES IN LOW POWER STATE ASSIGNMENT
Assim A. Sagahyroon, Fadi Aloul, Alexander Sudnitson · Journal of Circuits Systems and Computers · 2011
Power consumption of synchronous sequential circuits can be reduced by careful encoding of the states of the circuit. The idea is to reduce the average number of bit changes per state transition by finding an optimal state assignment. This state assignment problem is NP-hard, and existing techniques rely mainly on heuristic-based methods. The primary goal of this work is to assess the suitability of using complete advanced Boolean Satisfiability and Integer Linear Programming (ILP) methods in finding an optimized solution. We formulate the problem as a 0-1 ILP instance with power minimization being the objective. Using generic and commercial solvers, the proposed approach was tested on sample circuits from the MCNC benchmark suite. Furthermore, in an effort to accelerate the search process, circuits were checked for symmetries and symmetry breaking predicates were added whenever applicable. The experimental results provide a pragmatic insight into the problem and basis for further exploration.