Evolutionary Techniques for Multi-Objective VLSI Netlist Partitioning


Abstract

The problem of partitioning appears in several areas ranging from VLSI, parallel programming, to molecular biology. The interest in achieving better partitioning of any system is growing rapidly especially in VLSI, and has been a hot issue in recent years. In VLSI circuit partitioning, the problem of obtaining a minimum cut has been of prime importance and most literature available is for this single objective optimization. However, with current technology trends partitioning has become a multi-objective problem (MOP), where power and delay, in addition to minimum cut, need to be optimized. In this thesis, the multi-objective optimization problem at the partitioning phase in VLSI physical design step is addressed. This problem involves multiple, possibly conflicting objectives; hence fuzzy rules have been incorporated in designing the overall cost function. Iterative algorithms, namely Genetic Algorithm (GA), Tabu Search (TS), and Simulated Evolution (SimE) are tailored for finding good quality solutions for the above mentioned MOP problem. Another deterministic algorithm PowerFm which is an extension to Fidducia Mattheyeses (FM) heuristic is proposed and results compared and analyzed.