請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37559完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 黃鐘揚 | |
| dc.contributor.author | Kai-Chu Wu | en |
| dc.contributor.author | 吳鎧竹 | zh_TW |
| dc.date.accessioned | 2021-06-13T15:32:42Z | - |
| dc.date.available | 2010-07-16 | |
| dc.date.copyright | 2008-07-16 | |
| dc.date.issued | 2008 | |
| dc.date.submitted | 2008-07-14 | |
| dc.identifier.citation | 1. Weiping Shi, Zhuo Li, and C.J. Alpert, Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost. Design Automation Conference, 2004. Proceedings of the ASP-DAC 2004. Asia and South Pacific, Jan. 2004: p. 609-614.
2. P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick, Repeater Scaling And it's Impact on Cad, in IEEE Trans. CAD. 2004. p. 451-463. 3. L.P.P.P. van Ginneken, Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay, in Intl. Symposium on Circuits and Systems. 1990. p. 865-868. 4. M. Waghmode, Zhuo Li, and Weiping Shi, Buffer insertion in large circuits with constructive solution search techniques, in Design Automation Conference, 2006 43rd ACM/IEEE 24-28 July 2006. p. 296 - 301 5. Weiping Shi and Zhuo Li, A fast algorithm for optimal buffer insertion, in Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on June 2005 p. 879 - 891 6. Ruiming Chen and Hai Zhou, A flexible data structure for efficient buffer insertion, in Computer Design: VLSI in Computers and Processors, 2004. ICCD 2004. Proceedings. IEEE International Conference on. 11-13 Oct. 2004. p. 216 - 221. 7. A.K. Murugavel and N. Ranganathan, Gate sizing and buffer insertion using economic models for power optimization, in VLSI Design, 2004. Proceedings. 17th International Conference on 2004. p. 195 - 200. 8. Zhuo Li, C.N. Sze, C.J. Alpert, Jiang Hu, and Weiping Shi, Making fast buffer insertion even faster via approximation techniques. Design Automation Conference, 2005. Proceedings of the ASP-DAC 2005. Asia and South Pacific, 18-21 Jan. 2005 1: p. 13 - 18. 9. Zhuo Li and Weiping Shi, An O(bn/sup 2/) time algorithm for optimal buffer insertion with b buffer types, in Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on March 2006 p. 484 - 489 10. Weiping Shi and Zhuo Li, An O(nlogn) time algorithm for optimal buffer insertion. Design Automation Conference, 2003. Proceedings, 2-6 June 2003: p. 580- 585. 11. C.N. Sze, C.J. Alpert, Jiang Hu, and Weiping Shi, Path based buffer insertion, in Design Automation Conference, 2005. Proceedings. 42nd. 2005. p. 509- 514. 12. C. Alpert, C. Chu, G. Gandham, M. Hrkic, Jiang Hu, C. Kashyap, and S. Quay, Simultaneous driver sizing and buffer insertion using a delay penalty estimation technique, in Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on Jan. 2004 p. 136 - 141. 13. Charles J. Alpert, Milos Hrkic, and Stephen T. Quay, A Fast Algorithm for Identifying Good Buffer Insertion Candidate Locations. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 2001. 22(5): p. 573- 583. 14. J. Lillis, Chung-Kuan Cheng, and Lin T.-T.Y., Optimal wire sizing and buffer insertion for low power and ageneralized delay model, in Solid-State Circuits, IEEE Journal of. Mar 1996. p. 437-447. 15. C.C.N. Chu and D.F. Wong, A polynomial time optimal algorithm for simultaneous buffer and wire sizing, in Design, Automation and Test in Europe, 1. Weiping Shi, Zhuo Li, and C.J. Alpert, Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost. Design Automation Conference, 2004. Proceedings of the ASP-DAC 2004. Asia and South Pacific, Jan. 2004: p. 609-614. 2. P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick, Repeater Scaling And it's Impact on Cad, in IEEE Trans. CAD. 2004. p. 451-463. 3. L.P.P.P. van Ginneken, Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay, in Intl. Symposium on Circuits and Systems. 1990. p. 865-868. 4. M. Waghmode, Zhuo Li, and Weiping Shi, Buffer insertion in large circuits with constructive solution search techniques, in Design Automation Conference, 2006 43rd ACM/IEEE 24-28 July 2006. p. 296 - 301 5. Weiping Shi and Zhuo Li, A fast algorithm for optimal buffer insertion, in Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on June 2005 p. 879 - 891 6. Ruiming Chen and Hai Zhou, A flexible data structure for efficient buffer insertion, in Computer Design: VLSI in Computers and Processors, 2004. ICCD 2004. Proceedings. IEEE International Conference on. 11-13 Oct. 2004. p. 216 - 221. 7. A.K. Murugavel and N. Ranganathan, Gate sizing and buffer insertion using economic models for power optimization, in VLSI Design, 2004. Proceedings. 17th International Conference on 2004. p. 195 - 200. 8. Zhuo Li, C.N. Sze, C.J. Alpert, Jiang Hu, and Weiping Shi, Making fast buffer insertion even faster via approximation techniques. Design Automation Conference, 2005. Proceedings of the ASP-DAC 2005. Asia and South Pacific, 18-21 Jan. 2005 1: p. 13 - 18. 9. Zhuo Li and Weiping Shi, An O(bn/sup 2/) time algorithm for optimal buffer insertion with b buffer types, in Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on March 2006 p. 484 - 489 10. Weiping Shi and Zhuo Li, An O(nlogn) time algorithm for optimal buffer insertion. Design Automation Conference, 2003. Proceedings, 2-6 June 2003: p. 580- 585. 11. C.N. Sze, C.J. Alpert, Jiang Hu, and Weiping Shi, Path based buffer insertion, in Design Automation Conference, 2005. Proceedings. 42nd. 2005. p. 509- 514. 12. C. Alpert, C. Chu, G. Gandham, M. Hrkic, Jiang Hu, C. Kashyap, and S. Quay, Simultaneous driver sizing and buffer insertion using a delay penalty estimation technique, in Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on Jan. 2004 p. 136 - 141. 13. Charles J. Alpert, Milos Hrkic, and Stephen T. Quay, A Fast Algorithm for Identifying Good Buffer Insertion Candidate Locations. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 2001. 22(5): p. 573- 583. 14. J. Lillis, Chung-Kuan Cheng, and Lin T.-T.Y., Optimal wire sizing and buffer insertion for low power and ageneralized delay model, in Solid-State Circuits, IEEE Journal of. Mar 1996. p. 437-447. 15. C.C.N. Chu and D.F. Wong, A polynomial time optimal algorithm for simultaneous buffer and wire sizing, in Design, Automation and Test in Europe, 1998, Proceedings. Feb. 1998 p. 479 - 485. 16. Zhuo Li and Weiping Shi, An O(mn) time algorithm for optimal buffer insertion of nets with m sinks, in Design Automation, 2006. Asia and South Pacific Conference. Jan. 2006. 17. Yifang Liu, Jiang Hu, and Weiping Shi, Multi-scenario buffer insertion in multi-core processor designs, in Proceedings of the 2008 international symposium on Physical design 2008. p. 15-22. 18. H.M. Sheini and K.A. Sakallah, Pueblo: a modern pseudo-Boolean SAT solver. Design, Automation and Test in Europe, 2005. Proceedings, 7-11 March 2005. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37559 | - |
| dc.description.abstract | 隨著超大型積體電路製程的進步，緩衝器置入技術成為提昇效能的要角。現有的研究(如：VGDP演算法)主要專注在演算法效率上，我們則是著重在效能上的精進。不同於以往以動態規劃為基礎的演算法，我們利用正規化的方式來解決緩衝器置入的問題。我們所提出的正規化緩衝器置入演算法，可以更進一步的增進以路徑為基礎VGDP演算法的結果。實驗結果顯示，我們的演算法在ISCAS 85的電路上，平均有 7.64 % 的電路延遲改善。 | zh_TW |
| dc.description.abstract | Along with the progress of VLSI technology, buffer insertion plays an increasingly important role in improving circuit performance. Prior works (e.g. VGDP algorithm) are focused on enhancing the running time of buffer insertion algorithms, while our main objective in this thesis is to improve the solution quality. In contract to the traditional dynamic programming algorithms, we propose a formal-assisted buffer insertion (FABI) algorithm which can further improve circuit delay optimized by path-based VGDP buffer insertion. Experimental results show that block-based FABI has average 7.64 % circuit delay improvement over the path-based VGDP on ISCAS 85 benchmark circuits. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T15:32:42Z (GMT). No. of bitstreams: 1 ntu-97-R95921026-1.pdf: 1036173 bytes, checksum: 9d40284cc6edb0b2123d8dd3e9be141f (MD5) Previous issue date: 2008 | en |
| dc.description.tableofcontents | 誌謝 I
Abstract III List of Figures VII List of Equations IX List of Tables X Chapter 1 Introduction 1 1.1 Purpose of Buffer Insertion 2 1.2 Pervious Works on Buffer Insertion 2 (1) VGDP 2 (2) Fast Buffer Insertion (FBI) 3 (3) Path-based Buffer Insertion (PBBI) 3 (4) Other Relevant Works 4 1.3 Our Formal-Assisted Algorithm 5 1.4 Organization of This Thesis 6 Chapter 2 Preliminaries 7 2.1 Circuit Representation 7 2.2 Critical Path and Critical Area 7 2.3 Delay Model 8 2.4 Problem Definition 9 2.4.1 Net Level Buffer Insertion Problem 9 2.4.2 Circuit Level Buffer Insertion Problem 10 2.4.3 Pseudo Boolean Optimization Problem 11 2.5 Path-based VGDP 11 2.6 PBS Algorithm 13 Chapter 3 Algorithm 16 3.1 FABI Overall Flow 16 3.2 Computing Circuit Timing Information 18 3.3 Constructing Formal Equations 20 3.3.1 Simple Case without Fanout Case 21 3.3.2 Simple Case with 2-fanout Case 22 3.3.3 Complicated Case without Fanout 24 3.3.4 Complicated Case with Multi-fanout 25 3.4 Simplification of FABI Constraints 26 3.4.1 Single-path FABI 27 3.4.2 Multi-path FABI 28 3.4.3 Pseudo Sink 30 3.4.4 Block FABI 30 Chapter 4 Implementation 33 4.1 File Format 33 4.1.1 Circuit File 34 4.1.2 Library File 36 4.2 Data Structure 37 4.2.1 Circuit Data Structure 37 4.2.2 Library Data Structure 38 4.2.3 (Q,C)-pair Data Structure 38 4.2.4 Path Data Structure 39 4.3 Formal Engine 39 4.3.1 Pueblo PB Solver 39 4.3.2 Pueblo Input File Format 40 Chapter 5 Experimental Results 42 5.1 Experiment One - Single-path FABI and Path-based VGDP 43 5.2 Experiment Two - Block FABI and Path-based VGDP 45 5.3 Experiment Three - Buffer Sizing 47 5.4 Experiment Four - Combinational Techniques 49 5.5 Experiment Five - Complexity Analysis 51 5.6 Experiment Six - Truncation Error 52 Chapter 6 Conclusion and Future Work 54 References 55 Appendix 58 I. User Manual 58 II. Circuit Characteristic 59 | |
| dc.language.iso | en | |
| dc.subject | block-based FABI | zh_TW |
| dc.subject | 緩衝器置入 | zh_TW |
| dc.subject | 正規化 | zh_TW |
| dc.subject | VGDP | zh_TW |
| dc.subject | FABI | zh_TW |
| dc.subject | VGDP | en |
| dc.subject | block-based FABI | en |
| dc.subject | FABI | en |
| dc.subject | buffer insertion | en |
| dc.subject | formal | en |
| dc.title | 利用正規化解決緩衝器置入問題 | zh_TW |
| dc.title | Formal-Assisted Buffer Insertion | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 96-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 江介宏,張耀文 | |
| dc.subject.keyword | 緩衝器置入,正規化,VGDP,FABI,block-based FABI, | zh_TW |
| dc.subject.keyword | buffer insertion,formal,VGDP,FABI,block-based FABI, | en |
| dc.relation.page | 59 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2008-07-14 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-97-1.pdf 未授權公開取用 | 1.01 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。