臺灣博碩士論文加值系統

由於繞線的執行處於整個實體設計過程的後段，假如繞線的執行成效不佳，那麼我們先前所完成的步驟將不斷地反覆被執行，來改善繞線不佳的窘境。在這個反覆改善設計的過程當中，產品便會失去市場的先機。為了增加繞線的成功機率，我們應該及早進行繞線的規劃。在這篇論文當中，我們發展了一個簡單的置放後可繞性分析器。這個方法是基於計算每一個detailed routing graph vertex上的垂直方向繞線密度與水平方向繞線密度，其中當然也會考慮了繞線前障礙物所造成的影響，這些障礙物包括了邏輯元件的接腳與置放前之繞線。我們利用可繞性分析器來調整的晶片面積與繞線層數。根據實驗結果，我們觀察到我們的方法可以正確地預估最小晶片面積的繞線層數。然而截至目前為止，我們還是無法正確地調整出晶片面積使整個晶片得以完成繞線。

Because routing is performed at the very end of the design process, if the routing of a design is badly performed, the design tasks previously done before routing may be iterated again to solve the routing problem. This often incurs a delay for time-to-market. In order to increase the probability of having a successful routing, routing planning should be performed early. This thesis develops a simple methodology to perform post placement routability analysis. The methodology is based on the vertical and horizontal wiring densities calculated for each of the detailed routing graph vertexes by taking into account the blockages formed by cell pins, prerouted wires, etc. The routability analyzer is used to tune chip area and the number of routing layers. The experimental results show that it can accurately estimate the number of routing layers for a chip but can not accurately predict the chip area. It is yet to find out an effective method to tune chip area.

Chapter 1. Introduction
1.1 Background
1.2 Scope of the Work
1.3 Thesis Organization
Chapter 2. Related Work
2.1 Routability Analysis Based on Circuit Netlist
2.2 Routability Analysis During or Post Placement
2.3 Routability Analysis in Other Applications
Chapter 3. A Post Placement Routability Analyzer
3.1 Preliminaries
3.2 Implementation
3.2.1 Definitions
3.2.2 Handling Pre-routing Obstacles
3.2.3 Wiring Length Estimation
3.2.4 Layer Estimation
3.2.5 Track Insertion
Chapter 4. Experimental Results
Chapter 5. Conclusions and Future Work

[Cad44a] "Chapter 6. DEF Syntax," Cadence, Lef/Def Language Reference Manual 4.4.
[Cad44b] "Chapter 1. LEF Syntax," Cadence, Lef/Def Language Reference Manual 4.4.
[Cal99] A. E. Caldwell, A. B. Kahng, S. Mantik, I. L. Markov, and A. Zelikovsky, "On wirelength estimations for row-based placement," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, no. 9, pp. 1265-1278, Sept. 1999.
[Che94] C.-L. E. Cheng, "RISA: accurate and efficient placement routability modeling," IEEE/ACM Int. Conf. on Computer-Aided Design, pp. 690-695, Nov. 1994.
[Che00] Q. Chen, J. A. Davis, P. Zarkesh-Ha, and J. D. Meindl, "A novel via blockage model and its implications," Proc. of the IEEE 2000 Int. Interconnect Technology Conf., pp. 15-17, June 2000.
[Dia99] E. Diaz-Alvarez and J. P. Krusius, "Probabilistic prediction of wiring demand and routing requirements for high density interconnect substrates," IEEE Trans. on Advanced Packaging, vol. 22, no. 4, pp. 642-648, Nov. 1999.
[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.
[Ho90] J.-M. Ho, G. Vijayan, and C. K. Wong, "New algorithms for the rectilinear steiner tree problem," IEEE Trans. on Computer-Aided Design, vol. 9, no. 2, pp. 185-193, 1990.
[Hom96] I. Hom and J. Granacki, "Estimation of the number of routing layers and total wirelength in a PCB through wiring distribution analysis," Proc. of EURO-DAC, with EURO-VHDL ’96 and Exhibition, pp. 310-315, Sept. 1996.
[Iso97] N. Iso, Y. Kawaguchi, and T. Hirata, "Efficient routability checking for global wires in planar layouts," Proc. of the ASP-DAC, pp. 641-644, Jan. 1997.
[Kur89] F. J. Kurdahi and A. C. Parker, "Techniques for area estimation of VLSI layouts," IEEE Trans. on Computer-Aided Design, vol. 8, no. 1, pp. 81-92, Jan. 1989.
[Kus99] Kusnadi and J. D. Carothers, "Routability checking for general area routing problems," Proc. of Twelfth Annual IEEE Int. ASIC/SOC Conf., pp. 201-205, Sept. 1999.
[Lan71] B. S. Landman and R. L. Russo, "On a pin versus block relationship for partitions of logic graphs," IEEE Trans. on Computers, vol. C-20, no. 12, pp. 1469-1479, Dec. 1971.
[Mas87] A. Masaki and M. Yamada, "Equations for estimating wire length in various types of 2-D and 3-D system packaging structures," IEEE Trans. on Components, Hybrids, and Manufacturing Technology, vol. CHMT-10, no. 2, pp. 190-198, June 1987.
[May90] S. Mayrhofer and U. Lauther, "Congestion-driven placement using a new multi-partitioning heuristic," Digest of Technical Papers, IEEE Int. Conf. on Computer-Aided Design, pp. 332-335, Nov. 1990.
[Ped89a] M. Pedram and B. Preas, "Accurate prediction of physical design characteristics for random logic," IEEE Int. Conf. on Computer-Aided Design, pp. 100-108, Oct. 1989.
[Ped89b] M. Pedram and B. Preas, "Interconnection length estimation for optimized standard cell layouts," IEEE Int. Conf. on Computer-Aided Design, pp. 390-393, 1989.
[Rus72] R. L. Russo, "On the tradeoff between logic performance and circuit-to-pin ratio for LSI," IEEE Trans. on Computers, vol. C-21, no. 2, pp. 147-153, Feb. 1972.
[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 Rule," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. CAD-1, no. 4, pp. 186-192, 1982.
[Son00] X. Song, Q.-Y. Tang, D. Zhou, and Y. Wang, "Wire space estimation and routability analysis," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 19, no. 5, pp. 624-628, May 2000.[Tet95] A. Y. Tetelbaum, "Estimations of layout parameters of hierarchical systems," Proc. of the 27th SouthEastern Symp. on System Theory, pp. 353-357, 1995.
[Tsa92] R.-S. Tsay, S. C. Chang, and J. Thorvaldson, "Early wirability checking and 2-D congestion-driven circuit placement," Proc. of Fifth Annual IEEE Int. ASIC Conf. and Exhibit, pp. 50-53, Sept. 1992.
[Wan00] M. Wang and M. Sarrafzadeh, "Modeling and minimization of routing congestion," Proc. of the ASP-DAC 2000, pp. 185-190, Jan. 2000.
[Xio91] X.-M. Xiong, "Routability design for sea-of-cells," Proc. of Fourth Annual IEEE Int. ASIC Conf. and Exhibit, pp. p14-3/1-4, Sept. 1991.