Unified Logical Effort- Delay Minimization Method in Logic Paths with RC Interconnect

Unified Logical Effort- Delay Minimization Method in Logic Paths with RC Interconnect

Unified Logical Effort- Delay Minimization Method in Logic Paths with RC Interconnect

Bujjibabu. P1, Satyanarayana. V2, GNPK Mahalakshmi. E3

1. Associate Professor ECE Department, AEC, Surampalem

2. Associate Professor ECE Department, AEC, Surampalem

3. PG Student, Al-AMEER College of Engineering & Tech

Abstract

In modern applications fast processors are needed to avoid wasting time on waiting. It needs to talk about fast processors build with fast logic gates, which introduces the main task in designing CMOS circuits: how to get fast logic gates or how should the logic gates´ transistors be designed to achieve the greatest speed or to obtain the least delay? In this paper a method will be introduced to get the answer of these questions. It is called Unified Logical Effort (ULE)[1] The Unified Logical Effort is an easy way of delay evaluation and minimization in CMOS circuits. It is an extension of the Logical Effort model, which was first introduced by Sutherland [2],[3]. This method considers only the delay caused by the logic gates and neglect on-chip wires. However the circuits continue to scale, so that the delay of wires becomes not negligible anymore and the Logical Effort needs improvement. With the method of Unified Logical Effort the logic gates as well as the wires are taken into consideration to evaluate the delay and then to minimize it.

1. Introduction

   Nowadays time is very valuable. Every second costs money. Everything is getting faster and faster: trains, cars, mobile phones and mainly processors. Fast processors are needed to avoid wasting time on waiting for loading an internet page or the execution of an instruction. Talking about fast processors means talking about fast logic gates, which introduces the main task in designing CMOS circuits: how to get fast logic gates? Or how should the logic gates´ transistors be designed to achieve the greatest speed or to obtain the least delay?

   The Unified Logical Effort method comprises two steps:

   Delay evaluation Delay optimization

2. Delay evaluation of a logic gate

   Model of a logic gate: The inner structure of the inverter is shown figure.The inverter is composed of two transistors:

   • p-mos transistor

   • n-mos transistor

     Fig 1: Evaluating the delay by considering the wires Each transistor can be modelled with 3

     capacitances (a gate capacitance, a drain capacitance and a source capacitance) and 1 resistance. The values of these parameters depend on transistor´s width. If an n-mos transistor has the width W = xi.W0, its capacitances are equal to xi .C0 and its resistance to R0/

     1. C0 and R0 are the capacitor and resistor values of the minimum sized inverter (W = W0 and xi = 1). With the same width W = xi.W0 the p-mos transistor has the same capacitances but the double resistance as the n- mos transistor because the holes are twice as slow as the electrons. Both models connected together present the following inverter model, which is called The General RC Inverter Model. In general each logic gate has

        • an input capacitance Ci : the capacitance of the transistor gates connected to the input

        • an output resistance Ri : pull-down resistance Rdi or pull-up resistance Rui depending on which switch conducts

        • a parasitic capacitance Cpi : due to the inner capacitances

        • a load Capacitance Cout : the capacitance that the gate has to drive

     The values of these parameters depend on transistor´s width. Every logic gate is defined as a scaled version of a template circuit, which is the minimum sized symmetric inverter with the minimal width W =W0, input capacitance Ci = C0, output resistance Ri

     =Rui=Rdi= R0 and parasitic capacitance Cpi =Cp0. Thus the quantities of each logic gate are related to the template parameters and the scaling factor xi as

     ===0

     0

     Fig 2: RC-Inverter Circuit Model

     Scaling the template means scaling the transistors

     ´widths by the factor xi. As shown in the Figure 2 the capacitances and the resistance of the transistor are respectively proportional and inversely proportional to the transistor width. The input capacitance Ci of a logic gate is driven by the previous logic gate. Depending on its load the load capacitance Cout and the parasitic capacitance Cpi may be respectively charged or discharged through the pull-up or the pull-down resistance. Charging and discharging capacitors through resistors take time, which represents the time delay. That means the delay depends on the output capacitance, the parasitic capacitance, the output resistance and the input capacitance. The delay is comprised of two components:

     • a fixed part caused by the parasitic capacitance called the parasitic delay p [4]

     • a part caused by the output capacitance, resistance and the input capacitance called the effort delay f

       The sum of the two parts gives the total delay:

       =+

       The effort delay is also comprised of two components:

     • a part caused by the load capacitance called the electrical effort h [5]

     • a part caused by the input capacitance and the output resistance called the logical effort g[6]

     The effort delay of the logic gate is the product of these two factors [4]

     =h

     The logical effort g quantifies the contribution of the logic gate´s topology to the delay. It is independent of the transistors´ size in the circuit. Because the inverter is the simplest logic gate, it drives loads best. The other logic gates have more transistors, some of which are connected in series, increasing the output resistance and hence the delay. The electrical effort h captures the effect of the load capacitance on the delay considering

     he ratio of driving capabilities and leads to drive the input capacitance. It is defined by:

     h = /

     So the basic equation of the total delay through a single logic gate is =h+

     Examples:

     However, as the logic gates are getting smaller and smaller, the contribution of the on-chip wires can´t be neglected anymore.

     Fig 3: wires delay evaluation

3. Delay evaluation of logic gate with interconnect

   Thanks to the Elmore delay model [7] the delay of a circuit comprising logic gates and wires can be easily calculated.

   The Elmore delay of the above RC-circuit is defined by:

   =1 (1+2+3) +2 (2+3) +33

   Fig: 4: RC Circuit Model

   Analogous to the Elmore delay the absolute delay expression of the following first logic gate is

   =(+++1) + (0.5 ++1)

   Fig 5: Cascaded logic gates with RC-interconnect

   This expression can be rewritten in function of the delay of a minimum sized inverter =R0.C0, where R0 and C0 are the output resistance and input capacitance of a minimum sized inverter:

   Fig 6: Logic gate delay with interconnect

4. Delay minimization using Unified Logical Effort

   D .d

   Ri . (Cwi Ci1 Cpi )

   Rwi

   (0.5C

   • C )

     i i R C R C

     wi i1

     0 0 0 0

     The delay di normalized with respect to a minimum sized inverter delay is defined by:

     Fig 7: Cascaded logic gates with RC-interconnect

     Cw Rw .(0.5Cw Ci1 )

     The total delay of the two stages is:

     d g (h

     i ) i i p

     d g * (h h ) ( p p ) g * (h h

     ) ( p p )

     C

     C

     i i i i

     i

     i i wi

     C

     i wi

     R .(0,5.C

     i 1

   • C )

   i 1

   wi 1

   C C

   i 1

   wi 1

   R .C

   d g * h wi p wi wi i1 g

   i2 wi 1 p p

   where

   g i i

   is the logical effort,

   i i C i

   R .C

   i 1 C

   1. i 1

      wi1

      i

      i

      Ro .Co

      with

      i o o

      Ci1 hi .Ci

      i 1 i 1

      Ci 1

      C R .(0,5.C C )

      C C

      hi is the electrical effort

      d g * h wi p wi wi i1 g

      i2 wi 1 p p

      Ci i i C i

      R .C

      i 1 h C C

      i 1

      wi1

      i

      o o i i

      i 1

      and

      p Ri .Cpi

      i R .C

      is the parasitic delay.

      To achieve the least delay the logic gates ´transistors must have the optimal size, that means the derivative of

      o o the delay with respect to the logic gate size must be

      The capacitive interconnect effort hw and the resistive

      interconnect effort pw are, respectively,

      equated to zero,

      Rw .Ci

      C R .(0.5C C )

      g i .h g

      i

      i

      i

      i

      *h h

      w

      w

      1. wi

         i C

         , pwi

         wi wt i 1

         Ro .Co

      2. 1

      i 1

      wi1

      i By multiplying by R0.C0 and using the relationships

      R

      R

      C

      C

      x

      x

      The wire influences the electrical effort of the logic

      gate with hw and contributes more delay to the total

      h Ci 1 , C

      C .g .x

      and R o

      delay with pw.

      The final expression of the ULE delay of a single logic gate considering the inter-connect is:

      i i o i i i

      i i

      The optimum condition can be rewritten as following:

      (R R ).C R .(C C )

      = (h+h)+(+)

      i wi

      i1

      i1

      i2

      wi1

      For an N stage logic path with interconnect the ULE delay is the sum of each delay of the single stage:

      N

      That means that the optimum size of gate i+1 is met when the delay part + +1 caused by the logic

      gate input capacitance is equal to the delay part +1

      d g * (h h ) ( p p )

      i1 i i w i

      i w i

      +2 + +1 caused by the output resistance of the logic gate.

      The delay due to the capacitance of gate i is defined by: minimization without considering on-chip

      C

      C

      i1

      i1

      i1

      i1

      i

      i

   2. (Ri1 Rw ).Ci (Ri1 Rw ).Co .gi xi

   The delay due to the resistance of gate i is defined by:

   wires)

   • For long wires, the gate size in the middle of the path converges to a fixed value, Xiopt=50

   DRi

   Ri .C

   i1

   • CWi

     R0 C

     i

     i1

   • CWi

5. ULE Optimization in paths with branches

   The total delay of gate i is:

   Di DCi DRi Const

   So to obtain the least delay the derivatives of the delay components with respect to the logic gate size xi have to be equal to 0

   The ULE method can be also used in paths including branches or gates with multiple fanout.

   DCi

   i

   Ri1

   • RWi1

     .C0 .gi

     DRi

     i

     R0 C

     2

     2

     i

     i1

   • CWi

   Di

   DCi DRi 0

   i

   i i

   Solving this equation provides the optimal sizing factor

   xiopt,

   Fig 9: A logic path segment including RC interconnect and two branches

   The optimum condition of this case is:

   iopt

   Ro

   Ri1 RWi1

   (Ci1 CWi )

   0 i

   0 i

   C .g .

   Ri1 RWi1 .Ci Ri .Ci1 CWi Cb1i1 C f 1i1 Cb2i1 C f 2i1

   Cbf1 Cbf2

   Example: The method of ULE is applied to a logic path with nine identical NAND gates with equal wire segments for various lengths shown in the Figure 8. The input capacitance of the first and the last stage are 10.C0 and 100.C0, respectively. The solution range

   Fig 10: Equivalent circuit with the effective branch and fanout capacitances

   Introducing CBF

   nC

   1 bn

   m

   • C

   • C

   1 fm

   the optimum

   condition can be simplified to:

   Ri1 Rwi1 .Ci Ri .Ci1 Cwi CBFi

   between two limits:

   Fig 8: Optimization of ULE sizing (normalized with respect to C0) for a chain of nine NAND gates with equal wire segments for a variety of lengths [8]

   • For zero wire lengths the solution converges to LE optimization (delay evaluation and

6. Comparison with benchmark circuits

   ULE Optimization is compared with the results of Cadence Virtuoso® Analog Optimizer, a numerical optimizer that uses a circuit simulator for delay modeling. The delay of a four-bit carry-lookahead adder is minimized with three methods: LE, ULE and the Analaog Optimizer (AO). All three optimization results are presented in Figure 11.

   Fig 11: Delay of a carry-lookahead adder for various wire segment lengths after gate size optimization by LE, ULE and Analog Optimizer (AO) [9]

   The results of the ULE optimization are very close to the results of the numerical optimizer. But the LE method becomes more and more inaccurate with the increasing wire lengths. Comparing the runtimes the ULE is the fastest method for delay evaluation and minimization.

7. Conclusion

Delay minimization through logic gate sizing is a main task in integrated circuit design. Due to the continuous scaling of the integrated circuits, the inter-connect has to be taken into consideration to get the greatest speed. Thus the Logical Effort model can´t achieve the desired optimization anymore. The Unified Logical Effort has been introduced as an extension of the Logical Effort method solving the problem and considering not only the logic gates but also the on-chip wires to get the least delay. The ULE provides optimum conditions to achieve the optimal gate sizing in logical paths with wires. The delay component caused by the gate capacitance has to be equal to the delay caused by the gate resistance. If the wires´ lengths are negligible the ULE solutions converge to the LE solutions. Compared with the industrial Analogue Optimizer tool the ULE optimization shows in much shorter runtime close results in terms of delay with same accuracy. The ULE has a high potential to be integrated into EDA tools.

1. Arkadiy Morgenshtein, Eby G. Friedman, Ran Ginosar and Avinoam Kolodny. Unified Logical Effort- A Method for Delay Evaluation and Minimization in Logic Paths with RC Interconnect

2. Ivan Sutherland, Bob Sproull and David Harris, Logical Effort: Designing Fast CMOS Circuits, Morgan Kaufmann Publishers, 1999.

3. I.E.Sutherland and R.F.Sproull, Logical Effort: Designing for Speed on the Back of an envelope, Proceeding of the university of California/Santa Cruz

   Conference on Advanced Research in VLSI (ARVLSI),pp. 1-16, 1991.

4. Ivan Sutherland, Bob Sproull and David Harris, Logical Effort: Designing Fast CMOS Circuits, Morgan Kaufmann Publishers, pp. 80-82, 1999.

5. Ivan Sutherland, Bob Sproull and David Harris, Logical Effort: Designing Fast CMOS Circuits, Morgan Kaufmann Publishers, pp. 5-12, 1999.

6. Ivan Sutherland, Bob Sproull and David Harris, Logical Effort: Designing Fast CMOS Circuits, Morgan Kaufmann Publishers, pp. 5-12, 63-69, 1999.

7. W.C.Elmore, The Transient Response of Damped Linear Networks with Particular Regard to Wide Band Amplifiers,Journal of Applied hysics, vol. 19, no. 1, pp.55-63, January 1948.

8. Arkadiy Morgenshtein, Eby G. Friedman, Ran Ginosar and Avinoam Kolodny. Unified Logical Effort- A Method for Delay Evaluation and Minimization in Logic Paths with RC Interconnect, p 9.

9. Arkadiy Morgenshtein, Eby G. Friedman, Ran Ginosar and Avinoam Kolodny. Unified Logical Effort- A Method for Delay Evaluation and Minimization in Logic Paths with RC Interconnect, p 12.