臺灣博碩士論文加值系統

發展電腦輔助設計工具時，需要靠大量的測試電路來協助效能評估。然而，目前公開的測試電路，不是晶片面積過小，就是只為用來評估某種用途的電腦輔助設計工具而設計。本論文發展一個合成電路產生器來產生一些測試電路。這個合成電路產生器藉由真實電路的特性，如每個元件接腳數目的分佈、每條網路上元件接腳數目的分佈、每個元件面積大小的分佈等等，來產生合成電路。產生出來的合成電路，在組合邏輯元件間不存在回授迴圈，以及在最長路徑上的元件數目不會超過一個限定值。然而，有點超出我們期望的是，有一些合成電路竟然有很大的冷次(Rent’s)指數。這些使用我們自行設計的標準元件庫所產生出來的電路，會被用來產生被邏輯合成工具用來預估晶片繞線長度的繞線負載模式。但他的正確性卻不盡理想，我們相信這是那些冷次指數過高的合成電路所引起的。

Development of EDA tools needs a large number of benchmark circuits to evaluate the tools’ effectiveness. However, most of the existing circuits in the public domain are either of small size or designed for a particular purpose. In this thesis we develop a synthetic circuit generator that would use real circuit characteristics such as pins per cell, pins per net, size per cell distributions, etc. to generate synthetic benchmark circuits. The generated circuits are free from feedback loops and the number of logic cells on the longest path can be bounded by a specified number. However, it is somewhat out of our expectation that the circuits generally have a larger Rent’s exponent. The circuits have been applied to generate a wire-load model for an in-house standard cell library, but the accuracy in predicting wire length during logic synthesis is not good. We believe that this is caused by having a large Rent’s exponent of the synthetic circuits used in generating the wire-load model.

書名頁…………………………………………………………………………………i
論文口試委員審定書…………………………………………………………………ii
授權書(國家圖書館)…………………………………………………………………iii
授權書(國科會科學技術資料中心)…………………………………………………iv
摘要……………………………………………………………………………………v
Abstract………………………………………………………………………………vi
誌謝…………………………………………………………………………………..vii
Contents……………………………………………………………………viii
List of Tables…………………………………………………………………………x
List of Figures………………………………………………………………………..xi
Symbol Definitions………………………………………………………………….xii
Chapter 1. Introduction……………………………………………………………1
1.1 Motivations…………………………………………………………………1
1.2 Scope of the Work……………………………………………………………5
1.3 Thesis Organization…………………………………………………………6
Chapter 2. Related Work……………………………………………………………7
2.1 Random and Geometric Graphs……………………………………………7
2.2 Generation of Functional Equivalent Circuits By Random Transformation…7
2.3 Signature-Invariant Mutants Based Approach………………………………8
2.4 Structural Characteristics Replication Approach…………………………11
2.5 Rent’s Rule Based Approach………………………………………………15
2.6 Hybrid Approach……………………………………………………………17
Chapter 3. Characterization of the MCNC Benchmark Circuits………………19
3.1 Fan-out Distribution………………………………………………………22
3.2 Cell Pin Distribution………………………………………………………26
3.3 Cell Size Distribution………………………………………………………30
3.4 Summary……………………………………………………………………34
Chapter 4. Generation of Synthetic Logic Networks……………………………35
4.1 Problem Formulation………………………………………………………35
4.2 Cell Generation……………………………………………………………38
4.3 Establishing Connections among Cells……………………………………41
4.4 Validation of Synthetic Logic Network………………………………48
4.4.1 Validation Results…………………………………………….………49
Chapter 5. The Application of Synthetic Logic Networks………………………..53
5.1 Creation of Wire-Load Models……………………………………………53
5.2 Validation of Wire-Load Models……………………………………………54
Chapter 6. Conclusion……………………………………………………………56
References…………………………………………………………………………57

References
[CBL] Computer-Aided Design Benchmarking Laboratory. URL:
http://www.cbl.ncsu.edu/benchmarks/
[Alp98] C. J. Alpert, “The ISPD98 Circuit Benchmark suite,” in Proc. ACM/SIGDA Int. Symp. Physical Design, Apr. 1998, pp. 85-90. URL:
http://vlsicad.cs.ucla.edu/~cheese/ispd98.html/
[Iwa94] K. Iwama and K. Hino, “Random Generation of Test Instances for Logic Optimizers,” in Proc. ACM/IEEE Design Automation Conf., June 1994, pp. 430-434.
[Iwa97] K. Iwama, K.Hino, H. Kurokawa, and S. Sawada, “Random Benchmark Circuits with Controlled Attributes,” in Proc. Eur. Design Test Conf., 1997.
[Hut97a] Michael D. Hutton, “Characterization and Parameterized Generation of Digital Circuits”, Ph D. Thesis, Graduate Department of Computer Science, University Of Toronto, 1997.
[Hut97b] M. Hutton, J. Rose, and D.Corneil, “Generation of Synthetic Sequential Benchmark Circuits,” in Proc. ACM/SIGDA Int. Symp. FPGA, Feb 1997, pp. 149-155.
[Kap98] D. Ghosh, N. Kapur, J. Harlow III, and F. Brglez, “Synthesis of Wiring Signature-Invariant Equivalent Class Circuit Mutants and Applications to Benchmarking,” in Proc. Design, Automation, and Test in Eur. Conf., Feb. 1998, pp. 656-663.
[Dar96] J. Darnauer and W. W. Dai, “A Method for Generating Random Circuits and Its Application to routability measurement,” in Proc. ACM/SIGDA Int. Symp. FPGA, Feb. 1996, pp. 66-72.
[Hut98] M. D. Hutton, J. Rose, J. P. Grossman, and D. Corneil, “Characterization and Parameterized Generation of Synthetic Combinational Circuits,” IEEE Trans. Computer-Aided Design, vol. 17, Oct. 1998, pp. 985-996.
[Che98] Jiunn-Ren Chen, “Genrtation of Wire-Load Models for Logic Synthesis”, Master Thesis, Graduate Institute of Electrical Engineering and Computer Engineering and Science, Yuan-Ze University, Taiwan, R.O.C., 1998.
[Str00] D. Stroobandt, P. Verplaetse, and J. Van Campenhout, “Generating Synthetic Benchmark Circuits for Evaluating CAD Tools,” IEEE Trans. Computer-Aided Design, vol. 19, Sept. 2000, pp. 1011-1022.
[Pis99] J. Pistorius, E. Legai, and M. Minoux, “Generation of Very Large Circuits to Benchmark the Partitioning of FPGAs,” in Proc. ACM/SIGDA Int. Symp. Physical Design, April 1999, pp.67-73.
[Lan71] B. S. Landman and R. L. Russo, “On a Pin Versus Block Relationship for Partitions of Logic Graphs,” IEEE Trans. Computers, vol. C-20, no. 12, Dec. 1971, pp. 1469-1479.
[Rus72] R. L. Russo, “On the Tradeoff Between Logic Performance and Circuit-to-Pin Ratio for LSI,” IEEE Trans. Computers, vol. C-21, no 2, pp. 147-153, Feb. 1972.
[Hag94] L. Hagen, A. B. Kahng, F. J. Kurdahi, and C. Ramachandran, “On the Intrinsic Rent Parameter and Spectra-Based Partitioning Methodologies,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 13, Jan. 1994, pp. 27-37.
[Tet95a] A. Y. Tetelbaum, ”Generalizations of Rent’s Rule,” in Proc Southeastern Symp. System Theory, March 1995, pp. 370-374.
[Tet95b] A. Y. Tetelbaum, “Estimations of Layout Parameters of Hierarchical Syztems,” Proc. Of the 27th SouthEastern Symp. On System Theory, pp. 353-357, 1995.
[Cal98] A. E. Caldwell, A. B. Kahng, and I. L. Markov, ”Relax Partitioning Balance Constraints in Top-Down Placement,” 17th ASIC Conference, 1998, pp. 229-232.
[Chr00] P. Christie, ”Rent exponent prediction methods,” IEEE Trans. Very Large Scale Integration Systems, vol. 8, Dec. 2000, pp. 679-688.
[Don79] W. E. Donath, “Placement and Average Interconnection Lengths of Computer Logic,” IEEE Trans. On Circuits and Systems, vol. CAS-26, no. 4, pp. 272-277, April 1979.
[Don81] W. E. Donath, “Wire Length Distribution for Placements of Computer logic,” IBM J. Res. Develop., vol. 25, no. 3, pp. 152-155 May 1981.
[Feu82] M. Feuer, “Connectivity of Random Logic,” IEEE Trans. On Computers, vol. C-31, no. 1,pp. 29-33, Jan. 1982.
[Gur89] C. V. Gura and J. A. Abraham, “Average Interconnection Length and Interconnection Distribution Based on Rent’s Rule,” 26th ACM/IEEE Design Automation Conf., pp. 574-577, 1989.
[Hel78] W. R. Heller, W. F. Mikhail;, and W. E. Donath, “Prediction of Wiring Space Requirements for LSI,” J. of Design Automation and Fault-Tolerant Computing, vol. 2, pp. 117-144, May 1978.
[Sas86] S. Sastry and A. C. Parker, “Stochastic Models for Wirability Analysis of Gate Arrays,” IEEE Trans. On Computer-Aided Design, vol. CAD-5, no. 1, pp.52-65, Jan 1986.
[Sch82] D. C. Schmidt, “Circuit Pack Parameter Estimation Using Rent’s,” IEEE Trans. On Computer-Aided Design of Intergrated Circuits and Systems, vol. CAD-1, no. 4, pp. 186-192, 1982.
[Str99] D. Stroobandt, “On an Efficient Method for Estimating the Interconnection Complexity of Designs and on the Existence if Region III in Rent’s Rule,” VLSI, Lakes Symp., 1999, pp. 330-331.
[Ver01] P. Verplaetse, “Refinements of Rent’s Rule Allowing Accurate Interconnect Complexity Modeling,” Quality Eletronic Design, International Symp., 2001 pp. 251-252.
[Kar97] G. Karypis, R. Aggarwal, V. Kumar and S. Shekhar, “Multilevel Hypergraph Partitioning: Application in VLSI Domain”, 34th IEEE/ACM Design Automation Conference, 1997, pp. 526-529.