A game theoretic framework for interconnect optimization in deep submicron and nanometer design

The continuous scaling of interconnect wires in deep submicron (DSM)circuits result in increased interconnect delay, power and crosstalk noise. In this dissertation, we address the problem of multi-metric optimization at post layout level in the design of deep submicron designs and develop a game theoretic framework for its solution. Traditional approaches in the literature can only perform single metric optimization and cannot handle multiple metrics. However, in interconnect optimization, the simultaneous optimization of multiple parameters such as delay, crosstalk noise and power is necessary and critical. Thus, the work described in this dissertation research addressing multi-metric optimization is an important contribution.Specifically, we address the problems of simultaneous optimization of interconnect delay and crosstalk noise during (i) wire sizing (ii) gate sizing (iii) integrated gate and wire sizing, and (iv) gate sizing considering process variations. Game the ory provides a natural framework for handling conflicting situations and allows optimization of multiple parameters. This property is exploited in modeling the simultaneous optimization of various design parameters such as interconnect delay, crosstalk noise and power, which are conflicting in nature. The problem of multi-metric optimization is formulated as a normal form game model and solved using Nash equilibrium theory. In wire sizing formulations, the net segments within a channel are modeled as the players and the range of possible wire sizes forms the set of strategies. The payoff function is modeled as (i) the geometric mean of interconnect delay andcrosstalk noise and (ii) the weighted-sum of interconnect delay, power and crosstalk noise, in order to study the impact of different costfunctions with two and three metrics respectively. In gate sizing formulations, the range of possible gate sizes is modeled as the set of strategies and the payoff function is modeled as the geome tric mean of interconnect delay and crosstalk noise. The gates are modeled as the players while performing gate sizing, whereas, the interconnect delay and crosstalk noise are modeled as players for integrated wire and gate sizing framework as well as for statistical gate sizing under the impact of process variations.The various algorithms proposed in this dissertation (i) perform multi-metric optimization (ii) achieve significantly better optimization and run times than other methods such as simulated annealing, genetic search, and Lagrangian relaxation (iii) have linear time and space complexities, and hence can be applied to very large SOC designs, and (iv) do not require rerouting or incur any area overhead. Thecomputational complexity analysis of the proposed algorithms as well as their software implementations are described, and experimental results are provided that establish the efficacy of the proposed algorithms