黃鐘揚臺灣大學：電子工程學研究所李晨豪Lee, Chen-HaoChen-HaoLee2007-11-272018-07-102007-11-272018-07-102007http://ntur.lib.ntu.edu.tw//handle/246246/57610本篇論文提出一種新的時序分析方法，不同於傳統中只考慮單邊轉換的靜態時序分析，它可能提供使用者比靜態時序分析更大的電路延遲。此演算法主要的部分有：(1) 使用靜態時序分析取得電路初使的關鍵路徑。 (2) 我們利用正規引擎去對這條關鍵路徑作謬誤路徑的確認。 (3) 如果這條關鍵路徑是存在的，我們會試著在考慮電路多重輸入轉換的情況下找出相關的最大延遲測試訊號。 (4) 如果我們能找出前述的測試訊號，我們會用動態時序分析來驗證我們得到的最大電路延遲。如此一來我們的時序分析方法可以提供使用者作電路關鍵路徑的確認，並且能在不錯的效率下找出最大的電路延遲測試訊號，這些測試訊號對使用者在電路佈局的時序模擬是相當有幫助的。In this thesis, we propose a new timing analysis method which is different from traditional ones. Our method consists of several steps：(1) We use static timing analysis (STA) to find out an initial critical path in the circuit. (2) We perform false path checking on the critical path by the Boolean Satisfiability (SAT) engine. (3) If the critical path is a true path (i.e. not false), we will try to push the delay bound obtained in the STA process by considering simultaneous input transitions of the circuit. (4) If we get certain input patterns from SAT engine, then we can evaluate the new delay data by dynamic timing analysis (DTA). In this way we can get an accurate delay bound and solve the circuit false path problem at the same time. Moreover, because we only simulate several input patterns in the circuit, the performance of our method must be better than traditional DTA. In our experiments, we demonstrate that our method can achieve both better performance and accuracy than random simulation. Finally we believe that the test patterns we derive by the SAT engine would be useful and important to the post-layout timing simulation stage.Table Content 序言 iv List of Figures v List of Tables vii Abstract 1 中文摘要 2 1. Introduction 3 2. Problem Definition 7 2.1 Input of Our Problem 7 2.2 Output of Our Problem 7 2.3 Assumptions and Simplifications in Our Method 7 2.4 An Illustrative Example 7 3. Timing Analysis Considering Multiple Input Transitions 9 3.1 Spice Experiments to Collect Multi-Input Transition Delay Table 9 3.2 Multi-Input Transition Delay Calculation Model 10 3.3 Boundary Conditions 12 3.4 Multiple Transition Timing Table 13 4. Algorithm and Framework Architecture 14 4.1 Main Algorithm 14 4.2 Framework Architecture 15 5. Internal Netlist Representation 17 5.1 Ckt Module 17 5.2 Ckt Module Cell 18 5.3 Ckt PI Cell 19 5.4 Ckt PO Cell 19 5.5 Timing Engine Components 19 6. Framework Implementation and Data Structure 21 6.1 Critical Path Record and Organization 21 6.2 Static Timing Analysis 22 6.3 SAT Engine and Boolean Constraints 24 6.3.1 SAT Engine 24 6.3.2 Time Frame Extension 25 6.3.3 True Path Constraints 26 6.3.4 Variable and Clause 27 6.3.5 Boolean Constraint Determination Algorithm 29 6.4 Dynamic Timing Analysis 31 7. Case Study 34 7.1 Critical Path from STA is False Path 34 7.2 Delay Bound Refinement 35 7.3 Critical Path Change 36 7.4 Delay Bound of New Algorithm is less Than the One of STA 36 8. Experimental Result 38 8.1 Delay Bound Refinement with New Algorithm 38 8.2 STA & Random Simulation 39 8.3 Timing Analysis with All Solutions 40 8.4 Critical Path Refinement 42 8.5 Found Critical Input Constraints 43 8.6 Run Time Comparison 44 9. Conclusion 46 Reference 47 Appendix 49 I. User's Manual 491001444 bytesapplication/pdfen-US靜態時序分析動態時序分析多重變換測試訊號布林限制可滿足性問題STADTAmultiple transitionstest patternsBoolean constraintsSATthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/57610/1/ntu-96-R93943162-1.pdf