Optimization techniques for high-performance digital circuits

ABSTRACT

The relentless push for high performance in custom digital circuits has led to renewed emphasis on circuit optimization or tuning. The parameters of the optimization are typically transistor and interconnect sizes. The design metrics are not just delay, transition times, power and area, but also signal integrity and manufacturability. This tutorial paper discusses some of the recently proposed methods of circuit optimization, with an emphasis on practical application and methodology impact. Circuit optimization techniques fall into three broad categories. The first is dynamic tuning, based on time-domain simulation of the underlying circuit, typically combined with adjoint sensitivity computation. These methods are accurate but require the specification of input signals, and are best applied to small data-flow circuits and "cross-sections" of larger circuits. Efficient sensitivity computation renders feasible the tuning of circuits with a few thousand transistors. Second, static tuners employ static timing analysis to evaluate the performance of the circuit. All paths through the logic are simultaneously tuned, and no input vectors are required. Large control macros are best tuned by these methods. However, in the context of deep submicron custom design, the inaccuracy of the delay models employed by these methods often limits their utility. Aggressive dynamic or static tuning can push a circuit into a precipitous corner of the manufacturing process space, which is a problem addressed by the third class of circuit optimization tools, statistical tuners. Statistical techniques are used to enhance manufacturability or maximize yield. In addition to surveying the above techniques, topics such as the use of state-of-the-art nonlinear optimization methods and special considerations for interconnect sizing, clock tree optimization and noise-aware tuning will be briefly considered.

REFERENCES

• 1: W. Nye, D. C. Riley, A. Sangiovanni-Vincentelli, and A. L. Tits. DELIGHT.SPICE: An optimization-based system for the design of integrated circuits. IEEE Transactions on Computer-Aided Design of ICs and Systems, CAD-7(4):501-519, April 1988.
• 2: Robert King Brayton , R. Brayton, Sensitivity and Optimization, Elsevier Science Inc., New York, NY, 1980
• 3: R. K. Brayton, G. D. Hachtel, and A. L. Sangiovanni-Vincentelli. A survey of optimization techniques for integrated-circuit design. Proceedings of the IEEE, 69(10):1334-1362, October 1981.
• 4: J.-M. Shyu and A. Sangiovanni-Vincentelli. ECSTASY: a new environment for IC design optimization. IEEE International Conference on Computer-Aided Design, pages 484-487, November 1988.
• 5: Andrew R. Conn , Paula K. Coulman , Ruud A. Haring , Gregory L. Morrill , Chandu Visweswariah, Optimization of custom MOS circuits by transistor sizing, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.174-180, November 10-14, 1996, San Jose, California, United States
• 6: Andrew R. Conn , Ruud A. Haring , Chandu Visweswariah , Chai Wah Wu, Circuit optimization via adjoint Lagrangians, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.281-288, November 09-13, 1997, San Jose, California, United States
• 7: A. R. Conn, P. K. Coulman, R. A. Haring, G. L. Morrill, C. Visweswariah, and C. W. Wu. Jiffytune: circuit optimization using time-domain sensitivities. IEEE Transactions on Computer-Aided Design of ICs and Systems, 1997. Submitted for publication.
• 8: D. A. Hocevar, P. Yang, T. N. Trick, and B. D. Epler. Transient sensitivity computation for MOSFET circuits. IEEE Transactions on Computer-Aided Design of ICs and Systems, CAD- 4(4):609-620, October 1985.
• 9: S.W. Director and R. A. Rohrer. The generalized adjoint network and network sensitivities. IEEE Transactions on Circuit Theory, CT-16(3):318-323, August 1969.
• 10: L. T. Pillage, R. A. Rohrer, and C. Visweswariah. Electronic circuit and system simulation methods. McGraw-Hill, 1995.
• 11: B. D. H. Tellegen. A general network theorem, with applications. PhiIips Research Reports, 7:259-269, 1952.
• 12: A. R. Conn , N. I. M. Gould , Ph L. Toint, Lancelot: A FORTRAN Package for Large-Scale Nonlinear Optimization (Release A), Springer-Verlag New York, Inc., Secaucus, NJ, 1992
• 13: C. Visweswariah and R. A. Rohrer. Piecewise approximate circuit simulation. IEEE Transactions on Computer-Aided Design of ICs and Systems, 10(7):861-870, July 1991.
• 14: P. Feldmann, T. V. Nguyen, S. W. Director, and R. A. Rohrer. Sensitivity computation in piecewise approximate circuit simulation. IEEE Transactions on Computer-Aided Design of ICs and Systems, 10(2):171-183, February 1991.
• 15: T. V. Nguyen, P. Feldmann, S. W. Director, and R. A. Rohrer. SPECS simulation validation with efficient transient sensitivity computation. IEEE International Conference on Computer- Aided Design, pages 252-255, November 1989.
• 16: T. V. Nguyen. Transient sensitivity computation and applications. Technical Report CMUCAD-91-40, Carnegie Mellon University, Pittsburgh, PA, 1991.
• 17: R. B. Hitchcock, Sr., G. L. Smith, and D. D. Cheng. Timing analysis of computer hardware. IBM Journal of Research and Development, pages 100-105, January 1982.
• 18: J.P. Fishburn and A. E. Dunlop. TILOS: A posynomial programming approach to transistor sizing. IEEE International Conference on Computer-Aided Design, pages 326-328, November 1985.
• 19: S. S. Sapatnekar, V. B. Rao, P. M. Vaidya, and S. M. Kang. An exact solution to the transistor sizing problem for cmos circuits using convex optimization. IEEE Transactions on Computer- Aided Design of ICs and Systems, CAD-12(11):1621-1634, November 1993.
• 20: W. C. Elmore. The transient analysis of damped linear networks with particular regard to wideband amplifiers. Journal of Applied Physics, 19(1):55-63, 1948.
• 21: P. Penfield and J. Rubinstein. Signal delay in rc tree networks. In Proceedings of the Znd CaItech VLSI Conference, pages 269-283, March 1981.
• 22: M. D. Matson and L. A. Glasser. Macromodeling and optimization of digital MOS VLSI circuits. IEEE Transactions on Computer-Aided Design of ICs and Systems, CAD-5(4):659-678, October 1986.
• 23: R. J. Duffin, E. L. Peterson, and C. Zener. Geometric programming - theory and applications. John Wiley and Sons, New York, 1967.
• 24: Sachin S. Sapatnekar , Weitong Chuang, Power vs. delay in gate sizing: conflicting objectives?, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.463-466, November 05-09, 1995, San Jose, California, United States
• 25: P.K. Sancheti and S. S. Sapatnekar. Optimal design of macrocells for low power and high speed. IEEE Transactions on Computer- Aided Design of ICs and Systems, CAD-15(9):1160-1166, September 1996.
• 26: R. Spence and R. S. Soin. Tolerance design of electronic circuits. Addison-Wesley Publishing Company, 1988.
• 27: J. C. Zhang and M. A. Styblinski. Yield variabIity optimization of integrated circuits. Kluwer Academic Publishers, 1995.
• 28: S. W. Director and W. Maly, editors. Statistical approach to VLSI, volume 8 of Advances in CAD for VLSI. North-Holland, 1994.
• 29: Christopher Michael , Mohammed I. Ismail, Statistical Modeling for Computer-Aided Design of MOS VLSI Circuits, Kluwer Academic Publishers, Norwell, MA, 1993
• 30: G. Kjellstrom and L. Taxen. Stochastic optimization in system design. IEEE Transactions on Circuits and Systems, July 1981.
• 31: J. G. Ecker. Geometric programming: methods, computations and applications. SIAM review, 22(3):338-362, July 1980.
• 32: S. G. Nash and A. Sorer. Linear and nonlinear programming. McGraw-Hill, 1996.
• 33: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 34: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 35: P. E. Gill, W. Murray, and M. H. Wright. Practical optimization. Academic Press, London and New York, 1981.
• 36: Jorge J. More , Stephen J. Wright, Optimization Software Guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1993
• 37: J. E. Dennis, Jr. , R. B. Schnabel, A view of unconstrained optimization, Optimization, Elsevier North-Holland, Inc., New York, NY, 1989
• 38: P. E. Gill and W. Murray. Constrained optimization. In G. L. Nemhauser, A. H. G. Rinnooy Kan, and M. J. Todd, editors, Optimization, volume 1 of Handbooks in operations research and management science, pages 73-170. North-Holland, Amsterdam, The Netherlands, 1989.
• 39: A. R. Conn, Nick Gould, and Ph. L. Toint. Algorithms for largescale constrained nonlinear optimization: a current survey. In E. Spedicato, editor, Algorithms for continuous optimization: the state of the art, pages 287-332, Dordrecht, The Netherlands, 1994. Kluwer Academic Publishers. Volume 434 of NATO ASI Series C: Mathematical and Physical Sciences.
• 40: A. R. Conn, N. I. M. Gould, and Ph. L. Toint. Methods for nonlinear constraints in optimization calculations. In I. S. Duff and G. A. Watson, editors, The state of the art in numerical analysis, pages 363-390. Oxford University Press, 1997.
• 41: B. A. Murtagh and M.A. Saunders. MINOS 5.1 user's guide. Technical Report SOL 83-20R, Stanford University, Stanford, CA, December 1983. revised January 1987.
• 42: I. Bongartz , A. R. Conn , Nick Gould , Ph. L. Toint, CUTE: constrained and unconstrained testing environment, ACM Transactions on Mathematical Software (TOMS), v.21 n.1, p.123-160, March 1995 [doi>10.1145/200979.201043]
• 43: A. R. Conn, L. N. Vicente, and C. Visweswariah. Two-step algorithms for nonlinear optimization with structured applications. Research Report (in preparation), IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, USA, 1997.
• 44: D. P. Bertsekas. Constrained Optimization and Lagrange Multipliers Methods. Academic Press, London, 1982.
• 45: M. R. Lightner and S. W. Director. Multiple criterion optimization for the design of electronic circuits. IEEE Transactions on Circuits and Systems, CAS-28(2):169-179, March 1981.
• 46: P. L. Yu, Multiple criteria decision making: five basic concepts, Optimization, Elsevier North-Holland, Inc., New York, NY, 1989
• 47: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 48: Jason Cong , Cheng-Kok Koh, Simultaneous driver and wire sizing for performance and power optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.408-425, Dec. 1994 [doi>10.1109/92.335010]
• 49: Noel Menezes , Ross Baldick , Lawrence T. Pileggi, A sequential quadratic programming approach to concurrent gate and wire sizing, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.144-151, November 05-09, 1995, San Jose, California, United States
• 50: L. T. Pillage and R. A. Rohrer. Asymptotic waveform evaluation for timing analysis. IEEE Transactions on Computer-Aided Design of ICs and Systems, 9:352-366, April 1990.
• 51: P. Feldmann and R. W. Freund. Efficient linear circuit analysis by Pad4 approximation via the Lanczos process. IEEE Transactions on Computer-Aided Design of ICs and Systems, 14(5):639-649, May 1995.
• 52: L. Miguel Silveira , Mattan Kamon , Ibrahim Elfadel , Jacob White, A coordinate-transformed Arnoldi algorithm for generating guaranteed stable reduced-order models of RLC circuits, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.288-294, November 10-14, 1996, San Jose, California, United States
• 53: R. W. Freund , P. Feldmann, Efficient small-signal circuit analysis and sensitivity computations with the PVL algorithm, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.404-411, November 06-10, 1994, San Jose, California, United States
• 54: Howard H. Chen , David D. Ling, Power supply noise analysis methodology for deep-submicron VLSI chip design, Proceedings of the 34th annual conference on Design automation, p.638-643, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266307]
• 55: E. G. Friedman (Editor). Clock distribution networks in VLSI circuits and systems. IEEE Press, 1995.
• 56: P. J. Restle, K. A. Jenkins, A. Deutsch, and P. W. Cook. Measurement and analysis of on-chip transmission line effects in a 400mhz microprocessor. IEEE Journal of Solid State Circuits, 1997. To be published.
• 57: Kenneth L. Shepard , Vinod Narayanan, Noise in deep submicron digital design, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.524-531, November 10-14, 1996, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Design, Measurement, Performance, Theory

Keywords:
nonlinear optimization, circuit tuning, gradients, adjoints