An integrated state assignment and flip-flop selection technique for FSM synthesis

In the automatic synthesis of Finite State Machines (FSMs), the state assig nment and the choice of flip-flops significantly affect the cost of the com binational logic. To meet the demands of the increasing complexity of integ rated circuits, we present an integrated state assignment and sequential el ement selection approach to synthesize area-efficient FSMs. The FSM synthes is approach is modeled as an optimization problem and is solved by using th e guided evolutionary simulated annealing (GESA) technique. The GESA is a n ew type of parallel and distributed processing approach for searching the o ptimal solutions. Since the optimization problem at hand is NP-hard, a dist ributed algorithm for the GESA technique is developed and implemented on Ne twork of Workstations (NOW) to speedup the search process. Promising speedu ps are obtained by running the distributed GESA algorithm on a NOW. Efficac y of the proposed technique is demonstrated by carrying out a comparison wi th other state-of-the-art techniques such as the MUSTANG, NOVA and JEDI for MONO benchmarks. The proposed integrated state assignment and sequential e lement selection approach allows all types of flip-hops and offers consider able improvement in PLA area as compared to the existing techniques that us e only D type flip-flops as the sequential element. (C) 2000 Elsevier Scien ce B.V. All rights reserved.