MULTI OBJECTIVE CIRCUIT PARTITIONING FOR POWER OPTIMIZATION USING SIMULATED ANNEALING By Sumeer Khajuria,Electronics
Abstract
Circuit partitioning is the task of dividing a circuit into smaller parts. It is an important aspect of layout for several reasons. Partitioning can be used directly to divide a circuit into portions that are implemented on separate physical components, such as printed circuit boards or chips. The objective is to partition the circuit into parts such that the sizes of the components are within prescribed ranges and the complexity of connections between the components is minimized. As the size of present-day computer chips become larger (i.e., chips containing more than ten million transistors in sub-micron areas), the importance of obtaining near-optimal layouts that efficiently place and route the signals becomes increasingly important. Partitioning is a key approach in reducing the connectivity between areas of the chip so that modules can be more efficiently placed and routed to reduce wire-length, congestion, and increase the speed of the overall design. So, circuit partitioning is the decomposition of complex system into smaller subsystems with the objective that each subsystem can be independently designed thereby speeding up the design process and to minimize the interconnections between the subsystems. A balance constraint is often imposed to ensure that each subsystem contains about same number of components and this decomposition is carried out hierarchically, till each subsystem is of manageable size. Partitioning is a Hierarchical process, which can be carried out at three independent levels: System Level Partitioning, Board Level Partitioning, N1, N2 …....Nk and Chip Level Partitioning. Partitioning problem can be formulated as bi-partitioning or a multi-partitioning problem. Partitioning algorithms are broadly classified into two classes: Constructive and Iterative. On the basis of nature of the algorithm, partitioning algorithms can be classified as deterministic or probabilistic. On the basis of process used for partitioning algorithms can be classified as group migration algorithms, simulated annealing, and evolutionary algorithm.Problem of circuit net list partitioning is non polynomial hard and cannot be effectively solved by deterministic algorithms. SA being the algorithm belonging to the probabilistic and iterative class of algorithms are stochastic in nature and can be effectively used for circuit net list partitioning. In the present work, min-set and sleep time optimization has been simultaneously attempted.
