Yield-area optimizations of digital circuits using non-dominated sorting genetic algorithm (YOGA)

ABSTRACT

With shrinking technology, the timing variation of a digital circuit is becoming the most important factor while designing a functionally reliable circuit. Gate sizing has emerged as one of the efficient way to subside the yield deterioration due to manufacturing variations. In the past single-objective optimization techniques have been used to optimize the timing variation whereas on the other hand multi-objective optimization techniques can provide a more promising approach to design the circuit. We propose a new algorithm called YOGA, based on multi-objective optimization technique called Non-dominated Sorting Genetic Algorithm (NSGA). YOGA optimizes a circuit in multi domains and provides the user with Pareto-optimal set of solutions which are distributed all over the optimal design spectrum, giving users the flexibility to choose the best fitting solution for their requirements. YOGA overcomes the disadvantages of traditional optimization techniques, while even providing solutions in very stringent bounds.

REFERENCES

• 1: Seung Hoon Choi , Bipul C. Paul , Kaushik Roy, Novel sizing algorithm for yield improvement under process variation in nanometer technology, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996695]
• 2: Sreeja Raj , Sarma B. K. Vrudhula , Janet Wang, A methodology to improve timing yield in the presence of process variations, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996694]
• 3: A. A. Ilumoka, Optimal transistor sizing for CMOS VLSI circuits using modular artificial neural networks, Proceedings of the 29th Southeastern Symposium on System Theory (SSST '97), p.310, March 09-11, 1997
• 4: Jaskirat Singh , Vidyasagar Nookala , Zhi-Quan Luo , Sachin Sapatnekar, Robust gate sizing by geometric programming, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065662]
• 5: Alessandra Nardi , Alberto L. Sangiovanni-Vincentelli, Synthesis for Manufacturability: A Sanity Check, Proceedings of the conference on Design, automation and test in Europe, p.20796, February 16-20, 2004
• 6: M. Pan, C. C. N. Chu, and H. Zhou, "Timing yield estimation using statistical static timing analysis," in Intl Symposium on Circuits and Systems, 2005.
• 7: Osama Neiroukh , Xiaoyu Song, Improving the Process-Variation Tolerance of Digital Circuits Using Gate Sizing and Statistical Techniques, Proceedings of the conference on Design, Automation and Test in Europe, p.294-299, March 07-11, 2005 [doi>10.1109/DATE.2005.180]
• 8: Murari Mani , Anirudh Devgan , Michael Orshansky, An efficient algorithm for statistical minimization of total power under timing yield constraints, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065661]
• 9: Carlos M. Fonseca , Peter J. Fleming, Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization, Proceedings of the 5th International Conference on Genetic Algorithms, p.416-423, June 01, 1993
• 10: N. Srinivas and K. Deb, "Multi-objective function optimization using non-dominated sorting genetic algorithms," in Evolutionary Computation, 1994.
• 11: A. G. Cunha, P. Oliveira, and J. A. Covas, "Use of genetic algorithms in multicriteria optimization to solve industrial problems," in Proceedings of the Seventh International Conference on Genetic Algorithms, 1997, pp. 682--688.
• 12: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 13: K. Deb, "Non-linear goal programming using multi-objective genetic algorithms," Evolutionary Computation Journal, 1994.
• 14: Anirudh Devgan , Chandramouli Kashyap, Block-based Static Timing Analysis with Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.607, November 09-13, 2003 [doi>10.1109/ICCAD.2003.41]
• 15: Jing-Jia Liou , Kwang-Ting Cheng , Sandip Kundu , Angela Krstic, Fast statistical timing analysis by probabilistic event propagation, Proceedings of the 38th conference on Design automation, p.661-666, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379043]
• 16: C. Clark, "The greatest of a finite set of random variables," Operations Research, vol. 9, no. 2, 1961.
• 17: Mark C. Hansen , Hakan Yalcin , John P. Hayes, Unveiling the ISCAS-85 Benchmarks: A Case Study in Reverse Engineering, IEEE Design & Test, v.16 n.3, p.72-80, July 1999 [doi>10.1109/54.785838]
• 18: "Berkeley ptm." {Online}. Available: http://www-device.eecs.berkeley.edu/~ptm/

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
        G.1.10 Applications
      G.1.6 Optimization

General Terms:
Algorithms, Design, Performance