黃鐘揚臺灣大學:電機工程學研究所吳鎧竹Wu, Kai-ChuKai-ChuWu2010-07-012018-07-062010-07-012018-07-062008U0001-1107200822103000http://ntur.lib.ntu.edu.tw//handle/246246/187925隨著超大型積體電路製程的進步，緩衝器置入技術成為提昇效能的要角。現有的研究(如：VGDP演算法)主要專注在演算法效率上，我們則是著重在效能上的精進。不同於以往以動態規劃為基礎的演算法，我們利用正規化的方式來解決緩衝器置入的問題。我們所提出的正規化緩衝器置入演算法，可以更進一步的增進以路徑為基礎VGDP演算法的結果。實驗結果顯示，我們的演算法在ISCAS 85的電路上，平均有 7.64 % 的電路延遲改善。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.誌謝 Ibstract IIIist of Figures VIIist of Equations IXist of Tables Xhapter 1 Introduction 1.1 Purpose of Buffer Insertion 2.2 Pervious Works on Buffer Insertion 21) VGDP 22) Fast Buffer Insertion (FBI) 33) Path-based Buffer Insertion (PBBI) 34) Other Relevant Works 4.3 Our Formal-Assisted Algorithm 5.4 Organization of This Thesis 6hapter 2 Preliminaries 7.1 Circuit Representation 7.2 Critical Path and Critical Area 7.3 Delay Model 8.4 Problem Definition 9.4.1 Net Level Buffer Insertion Problem 9.4.2 Circuit Level Buffer Insertion Problem 10.4.3 Pseudo Boolean Optimization Problem 11.5 Path-based VGDP 11.6 PBS Algorithm 13hapter 3 Algorithm 16.1 FABI Overall Flow 16.2 Computing Circuit Timing Information 18.3 Constructing Formal Equations 20.3.1 Simple Case without Fanout Case 21.3.2 Simple Case with 2-fanout Case 22.3.3 Complicated Case without Fanout 24.3.4 Complicated Case with Multi-fanout 25.4 Simplification of FABI Constraints 26.4.1 Single-path FABI 27.4.2 Multi-path FABI 28.4.3 Pseudo Sink 30.4.4 Block FABI 30hapter 4 Implementation 33.1 File Format 33.1.1 Circuit File 34.1.2 Library File 36.2 Data Structure 37.2.1 Circuit Data Structure 37.2.2 Library Data Structure 38.2.3 (Q,C)-pair Data Structure 38.2.4 Path Data Structure 39.3 Formal Engine 39.3.1 Pueblo PB Solver 39.3.2 Pueblo Input File Format 40hapter 5 Experimental Results 42.1 Experiment One - Single-path FABI and Path-based VGDP 43.2 Experiment Two - Block FABI and Path-based VGDP 45.3 Experiment Three - Buffer Sizing 47.4 Experiment Four - Combinational Techniques 49.5 Experiment Five - Complexity Analysis 51.6 Experiment Six - Truncation Error 52hapter 6 Conclusion and Future Work 54eferences 55ppendix 58. User Manual 58I. Circuit Characteristic 591036173 bytesapplication/pdfen-US緩衝器置入正規化VGDPFABIblock-based FABIbuffer insertionformalthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/187925/1/ntu-97-R95921026-1.pdf