Layout-driven Timing Optimization by Generalized De Morgan Transform

ABSTRACT

We propose a timing-oriented logic optimization technique called Generalized De Morgan (GDM) transform, that integrates gate resizing, net buffering and De Morgan transformation. The contribution of our work lies in the integration of the three techniques, allowing them to interact at a much finer level of granularity than would be otherwise possible. This produces better results than those obtainable by individual techniques like net buffering or gate resizing applied to the circuit in various combinations. GDM transform is also layout-friendly since it does not alter the routing patterns and placement of cells, except possibly some buffer insertions/deletions. Hence it is useful for achieving timing closure in late stages of the design flow. We propose a comprehensive GDM algorithm that (a) determines the best replacement of a gate, possibly with inverted inputs and outputs, along with the best buffering configurations of nets incident on it, and (b) embeds this into a global scheme for optimizing large designs. We have implemented this algorithm in a layout-driven, industrial-strength logic optimization framework, and have successfully applied it to large industrial designs.

REFERENCES

• 1: Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion with accurate gate and interconnect delay computation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.479-484, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309983]
• 2: Charles Alpert , Anirudh Devgan, Wire segmenting for improved buffer insertion, Proceedings of the 34th annual conference on Design automation, p.588-593, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266291]
• 3: Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion for noise and delay optimization, Proceedings of the 35th annual conference on Design automation, p.362-367, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277145]
• 4: Michel R. C. M. Berkelaar , Jochen A. G. Jess, Gate sizing in MOS digital circuits with linear programming, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 5: C. Leonard Berman , J. Lawrence Carter , Ken F. Day, The fanout problem: from theory to practice, Proceedings of the decennial Caltech conference on VLSI on Advanced research in VLSI, p.69-99, June 1989, Cambridge, Massachusetts, United States
• 6: [6] R. Carragher, R. Murgai, S. Chakraborty, M. Prasad, A. Srivastava, and N. Vemuri. Layout-driven logic optimization. In Proceedings of the International Workshop on Logic Synthesis, pages 270-276, June 2000.
• 7: Olivier Coudert , Ramsey Haddad , Srilatha Manne, New algorithms for gate sizing: a comparative study, Proceedings of the 33rd annual conference on Design automation, p.734-739, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240658]
• 8: J. P. Fishburn, LATTIS: an iterative speedup heuristic for mapped logic, Proceedings of the 29th ACM/IEEE conference on Design automation, p.488-491, June 08-12, 1992, Anaheim, California, United States
• 9: [9] J. P. Fishburn and A. E. Dunlop. TILOS: A Posynomial Programming Approach to Transistor Sizing. In Proceedings of the International Conference on Computer-Aided Design, pages 326-328. IEEE, 1985.
• 10: H. J. Hoover , M. M. Klawe , N. J. Pippenger, Bounding Fan-out in Logical Networks, Journal of the ACM (JACM), v.31 n.1, p.13-18, Jan. 1984 [doi>10.1145/2422.322412]
• 11: [11] T. Ishioka, M. Murofushi, and M. Murakata. Layout Driven Delay Optimization With Logic Re-synthesis. In Workshop Notes of the International Workshop on Logic Synthesis, 1997.
• 12: Lalgudi N. Kannan , Peter R. Suaris , Hong-Gee Fang, A methodology and algorithms for post-placement delay optimization, Proceedings of the 31st annual conference on Design automation, p.327-332, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196399]
• 13: David S. Kung, A fast fanout optimization algorithm for near-continuous buffer libraries, Proceedings of the 35th annual conference on Design automation, p.352-355, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277143]
• 14: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Optimal wire sizing and buffer insertion for low power and a generalized delay model, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.138-143, November 05-09, 1995, San Jose, California, United States
• 15: [15] L. P. P. P. van Ginneken. Buffer Placement in Distributed RC-tree Networks for Minimum Elmore Delay. In Proceedings of the International Symposium on Circuits and Systems, pages 865- 868, 1990.
• 16: Peyman Rezvani , Amir H. Ajami , Massoud Pedram , Hamid Savoj, LEOPARD: a Logical Effort-based fanout OPtimizer for ARea and Delay, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.516-519, November 07-11, 1999, San Jose, California, United States
• 17: An integrated placement and synthesis approach for timing closure of PowerPC/sup TM/ microprocessors, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.206, October 12-15, 1997
• 18: [18] S. S. Sapatnekar, V. Rao, P. Vaidya, and S. Kang. An exact solution to the transistor sizing problem for cmos circuits using convex optimization. IEEE Transactions on Computer-Aided Design, CAD-6(6):1621-1634, Nov. 1993.
• 19: [19] H. Savoj, K. Xiang, K. Pan, and A. Domic. Technology dependent timing optimization. In Proceedings of the International Workshop on Logic Synthesis, June 1997.
• 20: A Robust Solution to the Timing Convergence Problem in High-Performance Design, Proceedings of the 1999 IEEE International Conference on Computer Design, p.250, October 10-13, 1999
• 21: Kanwar Jit Singh, Performance optimization of digital circuits, University of California at Berkeley, Berkeley, CA, 1992
• 22: Herve Jacques Touati, Performance-oriented technology mapping, University of California at Berkeley, Berkeley, CA, 1991

INDEX TERMS

Keywords:
Timing optimization, timing closure, layout-driven optimization, in-place circuit optimization, DeMorgan transformation, deep sub-micron design