臺灣博碩士論文加值系統

隨著電晶體製造技術不斷創新，影響整體電路性能表現之主要因素已逐漸轉為電路中的連線延遲大小。這個問題的有效解決方案之一便是在適當位置”置入緩衝器” 。然而，增加緩衝器雖然有助於減少電路連線延遲，但同樣的也增加了整體電路使用的面積大小、功率消耗並增加電路壅塞程度。本研究目的在探討如何充分利用必要之反閘在電路中的推力來改善電路連線延遲的問題並有效減少緩衝器的使用量。必要的反閘乃在能使電路產生正確功能。刪除任何一個反閘將會導致電路的錯誤。大部分的必要反閘屬於同向閘，如AND，OR等。
以較大型電路如ITC99’而言，本研究所提方法相較於未利用必要反閘的方法，在時效性上有0.78%至4.90%的改進幅度，而對於較小型電路如ISCAS89’則無明顯改善。

With the advance of VLSI process technology, interconnect delay increasely dominates the circuit performance. Buffer insertion is one of the crucial approaches to this problem. However, buffer insertion not only increases total chip area but also increases power dissipation. In this thesis, we propose to use essential inverters to reduce the use of buffers. An essential inverter is an inverter required to make a circuit function correctly. Removing of any essential inverters will result in malfunctioning of a circuit. Most of the essential inverters are embedded in positive unate gates such as AND, OR etc. In our experiment, we extract essential inverters from positive unate gates.
Compared to without using essential inverters, our approach results in 0.78% to 4.90% timing improvement on ITC99’ benchmark circuits with larger sizes while no improvement on ISCAS89’ benchmark suits with smaller sizes.

書名頁……………………………………………………………………i
摘要……………………………………………………………………ii
Abstract………………………………………………………………iii
誌謝……………………………………………………………………iv
Table of Contents ……………………………………………………v
List of Tables………………………………………………………vi
List of Figures……………………………………………………viii
Chapter 1. Introduction……………………………………………1
1.1 Background and Motivation…………………………………1
1.2 Related Work……………………………………………………3
1.3 Thesis Organization…………………………………………6
Chapter 2. Methodology………………………………………………7
2.1 Using traditional design flow……………………………9
2.2 Set-don’t-use in standard cell library………………11
2.3 Gate replacing method………………………………………13
2.3.1 With Driving Strength Replaced Ratio 1:M………13
2.3.2 With Driving Strength Replaced Ratio 2:M………15
2.3.3 With Driving Strength Replaced Ratio M:M………17
Chapter 3. Experiment………………………………………………19
3.1 Experimental Setup…………………………………………19
3.2 Experimental Results………………………………………24
3.3 Experimental Results Analyses…………………………30
Chapter 4. Conclusions and Future work………………………37
4.1 Contribution…………………………………………………37
4.2 Future Work……………………………………………………38
References……………………………………………………………39

[1] Yi-Hui Cheng,Yao-Wen Chang Integrating Buffer Planning with Floorplanning for Simultaneous Multi-Objective Optimization Asia and South Pacific Design Automation Conference 2004 (ASP-DAC''04) pp. 624-627
[2] D.Strochle, “Avoiding the pitfalls in CMOS design,” New electronics, vol. 20, no. 12,p. 30, June 1987.
[3] P. Saxena, N. Menezes, P. Cocchini, D. Kirkpatrick, “The scaling challenge: Can correct-by-construction design help?”, ISPD 2003.
[4] K. Bernstein, C.-T. Chuang, R. Joshi, R. Puri, “Design and CAD challenges in sub-90nm technologies”, ICCAD 2003.
[5] P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick. Repeater scaling and its impact on CAD. IEEE Trans. on CAD, 23(4):451–463, April 2004.
[6] H. B. Bakoglu. Circuits, interconnections and packaging for VLSI. Addison-Wesley, Reading, MA, 1990.
[7] J. Lillis, C. K. Cheng, and T. Y. Lin. Optimal wire sizing and buffer insertion for low power and a generalized delay model. IEEE Journal of Solid-State Circuits, 31(3):437–447, March 1996.
[8] C. J. Alpert, A. Devgan, and S. T. Quay. Buffer insertion for noise and delay optimization. In Proc. of DAC, pages 362–367, 1998.
[9] C. J. Alpert, M. Hrkic, J. Hu, and S. T. Quay. Fast and flexible buffer trees that navigate the physical layout environment. In Proc. of DAC, pages 24–29, 2004.
[10] P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick. Repeater scaling and its impact on CAD. IEEE Trans. on CAD, 23(4) : 451–463, April 2004.
[11] C. J. Alpert1, M. Hrkic2, J. Hu1, A. B. Kahng3, J. Lillis2, B. Liu3,
S. T. Quay1, S. S. Sapatnekar4, A. J. Sullivan1, P. Villarrubia1,Buffered Steiner Trees for Difficult Instances.ISPD’01, April 1-4, 2001
[12] C. N. Sze, Charles J. Alpert†, Jiang Hu and Weiping Shi. Path Based Buffer Insertion DAC 2005, June 13–17, 2005.
[13] Weiping Shi, Zhuo Charles J. Alpert Complexity Analysis and Speedup Techniques for Optimal Buffer Insertion with Minimum Cost LiAsia and South Pacific Design Automation Conference 2004 (ASP-DAC''04) pp. 609-614.

[14] L.P.P.P van Ginneken,”Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay”, Intl.Symposium on Circuits and Systems,1990,pp.865-868.
[15] W.Shi and Z.Li, “An O(nlogn) Time Algorithm for Optimal Buffer Insertion”,IEEE/ACM Design Automation Conf.,2003,pp.580-585.
[16] Hai Zhou and Adnan Aziz, Buffer Minimization in Pass Transistor Logic.Supported in part by an IBM Research Partnership Award
[17] Jingyu XU, Xianlong HONG and Tong JING, Timing-Driven Global Routing with Efficient Buffer Insertion. The Institute of Electronics, Information and Communication Engineers,2005
[18] C.J.Alpert and A.Devgan,Wire segmenting for improved buffer insertion. In Proc.of DAC,pages 588-593,1997.
[19] Kluwer-Bhatnagar. Advanced ASIC Chip Synthesis using Synopsys.