臺灣博碩士論文加值系統

中文摘要

隨著電路速度需求越來越快，頻率也要求越來越高，單單只憑縮短最長路徑(critical path)的延遲已經很難有效地將電路加速，這樣嚴重的趨勢，會帶給IC工程師和電腦輔助軟體必須額外付出很大的代價在電路延遲的最小化上。傳統上的設計必須將clock cycle time滿足最長路徑的時序，然而，最長路徑發生的機率卻是微乎其微，這表示傳統上的設計是過於悲觀的。因此，在這篇論文中，我們提出一個不同於傳統的方法來提升電路效能，並且可以讓電路的產能大幅提升。我們基本的概念是全自動將一個固定延遲的電路轉換成一個可變動延遲的電路，依據電路所需要運算的時間，動態調整延遲，這樣的方法可以平均用較少的時間完成一次電路的執行，進而提升電路的產能。因此，此篇論文提出一個完整的電路時序分析流程，並且實作出一個系統能精確地偵測出最長路徑發生的條件。根據MCNC benchmarks大量實驗的結果，那些沒有使用我們方法的電路，在使用我們的方法之後，產能平均可以大幅被提升43.97%。

Abstract

In high-performance system, it is difficult to speed up combinational circuits simply by reducing their critical path delays. Therefore, for the optimization of circuit performance, most IC designers and CAD tools put substantial efforts in minimizing the delay of critical paths. However, critical paths may be rarely activated. This thesis proposes a performance optimization paradigm called Tele-Microscopic Logic (TML) for increasing the throughput based on critical path rarely activated digital systems. The basic idea consists of transforming fixed latency units into variable latency ones that run with a faster clock cycle. This mechanism can improve the average throughput of speed critical designs automatically. In this thesis, we provide an accurate timing analysis and precise critical path activation logic. According to the experimental results, obtained a large set of MCNC benchmarks, the average throughput improvement result is better 43.97% than the circuits without our approach.

List of Contents:
Abstract 1
List of Contents 2
List of Figures 4
List of Tables 5
Chapter 1 Introduction 6
Chapter 2 Background 12
Chapter 3 Throughput Improvement 13
Chapter 4 Large Telescopic Units based on Near-Minimum Timed Supersetting 16
Chapter 5 Tele-Microscopic Logic 24
5.1. Static Timing Analysis 25
5.2 Problems of LTU Algorithm 26
5.2.1 Multiple Critical Fanin Problem 27
5.2.2 Reconvergent Fanout Problem 41
Chapter 6 Experimental Results 43
6.1. Experimental Environment 43
6.2. The Probability of the Output Signal, fh 46
6.3. The Improvement of the Circuit Throughput 48
6.4. The Area Overhead 51
6.5. The Arrival Time of the Signal, fh 55
Chapter 7 Conclusions 57
References 58
Appendix I: Background 60
Appendix II: Static Timing Analysis 63
1. Optimal Reduced Cycle Time T* 63
2. Critical Gates Classification 65
3. Side-inputs Classification 70

List of Figures:
Figure 1: Carry Propagation Distribution for Random Data 7
Figure 2: Delay Distribution of 32-bit Ripple Carry Adder 8
Figure 3: (a) A Combinational Unit and (b) A Telescopic Unit 10
Figure 4: Delay Distribution Graph 14
Figure 5: Single Path Sensitization Example 17
Figure 6: The LTU Algorithm 19
Figure 7: The LTU Algorithm 20
Figure 8: An Example under LTU Algorithm 22
Figure 9: Hold Logic Generation under LTU Algorithm 23
Figure 10: An Example under LTU Algorithm 27
Figure 11: The Results of Input Patterns with {d,e}={0,0},{0,1},{1,0}. 29
Figure 12: An Example of SPAF(y=val) 35
Figure 13: A SPAF(y=val) Traversal by A Tree Structure 36
Figure 14: An Example under TML Algorithm 37
Figure 15: Hold Logic Generation under TML Algorithm 39
Figure 16: The TML Algorithm 40
Figure 17: Reconvergent Fanout Problem 41
Figure 18: Reconvergent Fanout Duplicaiton 42
Figure 19: The Experimental Environmet 43
Figure 20: The Flow Chart of Experiments 45
Figure 21: Controlling Value 61
Figure 22: Non-Controlling Value 61
Figure 23: An Example for Preliminaries Review 62
Figure 24: An Example of Critical Gates Classification 66
Figure 25: Arrival Times Computation 67
Figure 26: Required Times Computation 68
Figure 27: Slack Computation 68
Figure 28: The Result of Critical Gates Classification 69
Figure 29: A Special Case of Side Input Classification 70
Figure 30: An Example of Side Input Classification 71
List of Tables:
Table 1: The Probability of the Output Signal, fh 47
Table 2: The Improvement of the Circuit Throughput 50
Table 3: The Area Overhead 53
Table 4: The Comparison of the Area Overhead and Throughput Improvement 54
Table 5: The Arrival Times of the Signal fh 56

References
[1]. T. Austin, V. Bertacco, D. Blaauw, and T. Mudge, “Opportunities and Challenges for Better than Worst-Case Design,” Proceedings of the ASP-DAC 2005. Asia and South Pacific Volume 1, 18-21 Jan. 2005 Page(s):I/2 - I/7.
[2]. J. M. Rabaey, A. Chandrakasan, and B. Nikolic. Digital Integrated Circuits. Prentice-Hall, 2003.
[3]. S. F. Oberman and M.J. Flynn, “Design Issues in Division and Other Floating-Point Operations,” IEEE Trans. Computer, vol. 46, no. 2, pp. 154-161, Feb. 1997.
[4]. L. Benini, G. De Micheli, E. Macii, and M. Poncino, “Telescopic Units: A New Paradigm for Performance Optimization of VLSI Designs,” IEEE Transaction Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 3, pp. 220-232, Mar. 1998.
[5]. R. I. Bahar, E. A. Frohm, C. M. Gaona, G. D. Hachtel, E. Macii, A. Pardo, and F. Somenzi, “Algebraic decision diagrams and their applications,” Formal Methods Syst. Design, vol. 10, pp. 171-206,1997.
[6]. R. I. Bahar, H. Cho, G. D. Hachtel, E. Macii, and F. Somenzi, “Timing analysis of combinational circuits using ADD’s,” EDTC-94: IEEE Eur. Design Test Conf., pp. 625-629, Paris, France, Feb. 1994.
[7]. L. Benini, G. De Micheli, A. Lioy, E. Macii, G. Odasso, and M. Poncino, “Automatic Synthesis of large telescopic units based on near-minimum timed supersetting,” IEEE Transaction on Computers, vol. 48, no. 8, pp. 769-779, Aug. 1999.
[8]. H. C. Chen, D. H. Du, “Path sensitization in Critical Path Problem,” IEEE Transaction on Computer-Aided Design, vol. 12, no.2, pp. 196-207, February 1993.