FSM state-assignment for area, power and testability using non-deterministic evolutionary heuristics

The rapid increase in complexity of VLSI circuits along with their proliferation in new domains has posed new challenges to the VLSI CAD industry. Mobile devices have added low power computation paradigm in VLSI design process along with conventional area (size) and performance (timing) goals. Similarly, increasing chip complexities (size) have further amplified the difficulty in VLSI testing with the focus now shifting towards efficient design techniques to ease in the device testability. With shrinking time to market windows, the need for efficient tools that can automate such multiobjective design processes at abstract levels has significantly increased.;A central problem in the synthesis of VLSI digital systems is controller synthesis which has traditionally been accomplished using Finite State Machines (FSMs). The complexity of FSM implementation depends on its state assignment. State assignment of FSMs for efficient area implementation alone is an NP-hard problem. The problem gets further involved if additional objectives such as low-power and ease of testability are considered. Non-deterministic evolutionary heuristics such as Genetic-Algorithms (GA) and Tabu-Search (TS) have shown to yield good results in solving such multiobjective hard combinatorial optimization problems in other areas of design automation.;In this thesis, the FSM state assignment problem (SAP) for area, power and testability as single as well as multiobjective optimization (MOP) is investigated. The work employs non-deterministic heuristics, GA and TS, in developing efficient design automation for search space exploration. New methods for estimating area, power and testability of a state assignment are presented. Experimental results compared with previous measures demonstrate the effectiveness of the proposed techniques.