臺灣博碩士論文加值系統

隨著超大型積體電路設計與製造技術的蓬勃發展，積體電路變得日益複雜，為了有效降低設計過程中的複雜度，叢集的概念已被廣泛利用。平面規劃在超大型積體電路實體設計流程中是相當重要的一個步驟，除了決定出模組間的相對位置外，亦直接決定整個晶片的面積大小及模組間訊號之連線長度，因此有效率的平面規劃演算法會同時影響到晶片的成本及其運作的效能。
在早期之製程技術中連線上訊號之延遲現象較不明顯，因此先前之平面規劃相關研究中大多數接著重在對面積之考量。近年來於深次微米的製程中發現連線產生的訊號延遲已變得十分明顯，因此，有必要重視模組間連線長度問題。
本篇論文將不同於先前的研究，針對平面規劃問題將優先考量連線長度問題，以模組間相對位置與訊號連線長度間之關係進行分析，利用序列對為基礎的表示法引入有叢集概念的方式，以得到一組對於連線長度是不錯的平面規劃初始解。在得到模組間之相對位置關係後，藉由在不大幅更動模組相對位置與不違反模組間不能相互重疊的條件下進行面積最小化。

Recently due to the advance of the technology in VLSI design and the manufacturing technique, the circuits become more and more complicated. In order to reduce the complexity in the design process effectively, the concepts of modulization and hierarchy are generally used. In the physical design stage, floorplanning determines not only the relative positions modules but also the area of the total chip and the length of wires between modules. Therefore, a good algorithm for floorplanning problem will impact on the cost and the performance of chips.

In the previous design techniques the signal delay on wires was not so obvious and the researches of floorplanning problem only focused on the reduction of chip area. However, the signal delay on wires becomes significant in SOC design and it’s necessary to pay attention to the wire-length between modules.

Differing from previous researches, our paper will consider the problem of wire-length first in the floorplanning problem. We will analysis the relation between the relative positions of modules and the length of wires. And then we will using the sequence-pair with clustering to get an initial solution and violating the non-overlapping constraint between modules. Finally we wish to obtain an admissible/non-admissible floorplanning solution which is good both on the area and wire-length.

摘要
ABSTRACT
誌謝辭
目次
第一章 前言
第二章 相關背景介紹
2.1 平面規劃之問題描述
2.1.1 平面規劃之表示法
2.2 模擬退火演算法
第三章 研究方法
3.1 問題描述
3.2 平面規劃演算法簡介
3.3 對模組進行叢集分群
3.3.1 以非線性規劃方式求得模組初始擺放解
3.3.2 叢集演算法
3.4 建立各個叢集之子平面規劃(SUBFLOORPLAN)
3.5 產生完整之平面規劃初始解
3.6 全域性面積最小化處理
3.7 分配I/O PINS
第四章 模擬退火演算法
4.1 鄰近解
4.2 計價函數
4.3 演算法以及退火過程
第五章 實驗結果
5.1 實驗平台
5.2 實驗測試電路
5.3實驗結果
第六章 結論與未來展望
參考文獻
作者簡介

[1]Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu and Shu-Wei Wu, “B*-trees: a new representation for non-slicing floorplans,” Proc. DAC, pp. 458-463, 2000.[2]T. Chen and M. K. H. Fan.,“On Convex Formulation of the Floorplan Area Minimization Problem,” Proc. ISPD, pp. 124-128, Apr. 1998. [3]Hung-Ming Chen, Hai Zhou, F.Y. Young, D.F. Wong, H.H. Yang and N. Sherwani, “Integrated floorplanning and interconnect planning,” Proc. ICCAD, pp. 354-357, 1999.[4]Jason Cong, Tianming Kong and D.Z. Pan “Buffer block planning for interconnect-driven floorplanning,” Proc. ICCAD, pp. 358 —363, 1999.[5]P.-N. Guo, C.-K. Cheng and T. Yoshimura, “An O-Tree Representation of Non-Slicing Floorplan and Its Application,” Proc. DAC, pp. 268-273, 1999.[6]Pei-Ning Guo, T. Takahashi, Chung-Kuan Cheng and T. Yoshimura “Floorplanning using a tree representation,” IEEE Trans. On Comp. Aided Design of IC’s and System, Vol.20, No.2, pp. 281-289,Feb 2001.[7]Xianlong Hong, Sheqin Dong, Gang Huang, Yuchun Ma, Yici Cai, Chung-Kuan Cheng, Jun Gu, “A non-slicing floorplanning algorithm using corner block list topological representation,” IEEE APCCAS, pp. 833-836, 2000.[8]S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, no. 4598, pp. 671-680, May 13, 1983.[9]D.P. Lapotin and S.W. Director, “A global floor-planning tool,” Proc. ICCAD, pp. 143-145, 1985.[10]S.-C. Lee, J.-M. Hsu, and Y.-W. Chang, “Multilevel large-scale module placement/floorplanning using B*-trees,” in Proceedings of The 12th VLSI Design/CAD Symposium, Hsinchu, Taiwan, Aug. 2001.[11]Chih-Hung Lee, Yu-Chung Lin, Wen-Yu Fu, Chung-Chiao Chang, Tsai-Ming Hsieh, “A New Formulation for SOC Floorplan Area Minimization Problem” to appear in Proc. of ACM/IEEE Design Automation and Test in Europe (DATE-2002), Paris, France, March 2002.[12]T. Lengauer and R. Muller ,“Robust and accurate hierarchical floorplanning with integrated global wiring,” IEEE Trans. On Comp. Aided Design of IC’s and System, Vol.12, No.6, pp. 802-809,June 1993.[13]J.-M Lin and Y.-W Chang, “TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans,” Proc. DAC, pp.764-769, 2001. [14]J.-M. Lin, S.-P. Lin, and Y.-W. Chang, “A P-admissible non-slicing floorplan representation with a worst-case linear-time packing scheme,” in Proceedings of The 12th VLSI Design/CAD Symposium, Hsinchu, Taiwan, Aug. 2001.[15]T.S. Moh, T.S. Chang, and S.L. Hakimi. “Globally optimal floorplanning for a layout problem”. IEEE Trans. on Circuit and Systems - I: Fundamental Theory and Applications, Vol. 43: pp.713—720, Sep. 1996.[16]H. Murata and E.S. Kuh, “Sequence-Pair Based Placement Method for Hard/Soft/Pre-placed Modules”. Proc. ISPD, pp. 167—172, Apr. 1998.[17]H. Murata, K. Fujiyoshi, S.Nakatake and Y.Kajitani, “Rectangle-Packing-Based Module Placement,” Proc. ICCAD, pp. 472-479, 1995.[18]S. Nakatake, K. Fujiyoshi, H. Murata and Y.Kajitani, “Module Placement on BSG-Structure and IC Layout Applications,” Proc. ICCAD, pp. 484-491, 1996.[19]Shigetoshi NAKATAKE, Yukiko KUBO and Yoji KAJITANI, “Consistent Floorplanning with Super Hierarchical Constraints” Proc. ISPD, pp. 144-149, 2001.[20]T. Ohmura, K. Fujiyoshi and C. Kodama, “Area optimization of packing represented by sequence-pair,” Proc. APCCAS, pp. 813 -816, 2000.[21]M. Ohmura, S. Wakabayashi, Y. Toyohara, J. Miyao and N. Yoshida, “Hierarchical floorplanning and detailed global routing with routing-based partitioning,” Proc. ISCAS, vol.2, pp.1640-1643, 1990.[22]R.H.J.M. Otten, “Automatic floorplan design,” Proc. DAC, pp. 261-267,1982.[23]M. Pedram and B. Preas, “A hierarchical floorplanning approach,” Proc. ICCD, pp. 332-338, 1990.[24]A. Ranjan, K. Bazargan, and M. Sarrafzadeh, “Floorplanner 1000 Times Faster: A Good Predictor and Constructor,” In System Level Interconnect Prediction, pp. 115-120, 1999.[25]A. Ranjan, K. Bazargan, S. Ogrenci, and M. Sarrafzadeh, “Fast Floorplanning for Effective Prediction and Constructor,” IEEE Transactions on VLSI System, Vol.9,No.2, pp. 341-351,April 2001.[26]A. Rnjan, K. Bazargan and M. Sarrafzadeh, “Fast hierarchical floorplanning with congestion and timing control,” Proc. ICCD, pp. 357-362, 2000.[27]E. Rosenberg, “Optimal Module Sizing in VLSI Floorplanning by Non-linear Programming,” Methods Models Operations Res., Vol. 33, pp. 131-143, 1989.[28]Y. Takashima and H. Murata, “SLASH: a deterministic block placement algorithm based on sequence-pair,” Proc. APCCAS, pp. 825 —828, 2000.[29]Xiaoping Tang, Ruiqi Tian and D.F. Wong, “Fast evaluation of sequence pair in block placement by longest common subsequence computation,” IEEE Trans. On Comp. Aided Design of IC’s and System, Vol.20, No.12, pp. 1406-1413,Dec 2001.[30]Ting-Chi Wang and D.F. Wong, “Efficient Shape Curve Construction in Floorplan Design,” Proc. EDAC, pp. 356-360,1991.[31]S. Wimer. I. Koren, and J Cederbaum, “ Floorplans, planar graphs, and layouts,” IEEE Trans, Circuits Syst., Vol. 35, pp. 267-278, Mar. 1988.[32]D.F. Wong and K.-S. The “An algorithm for hierarchical floorplan design,” Proc. ICCAD, pp. 484-487, 1989.[33]D.F. Wong and C.L. Lin, “A New Algorithm for Floorplan Design,” Proc. DAC, pp. 101-107,1986.[34]G.-M. Wu, Y.-C. Chang, and Y.-W. Chang, “Rectilinear Block placement Using B*-Trees,” Proc. ICCD, pp. 351-356, Austin, TX, Oct. 2000.[35]T. Xiaoping, T. Ruiqi, D.F. Wong “Fast evaluation of sequence pair in block placement by longest common subsequence computation “I IEEE Transactions on CAD of Integrated Circuits and Systems, Vol: 20 , No. 12 , pp. 1406 —1413 ,Dec. 2001 .[36]J. Xu, P.-N. Guo, and C.-K. Cheng, “Rectilinear Block Placement Using Sequence-Pair,” Proc. ISPD, pp. 173-178, 1998.[37]F.Y. Young and D.F. Wong, “How good are slicing floorplans,” Integration VLSI J. vol. 23, pp. 61-73, 1997.[38]F.Y. Young, D.F. Wong, and Hannah H. Yang “Slicing Floorplans with Range Constraint,” IEEE Transactions on CAD of Integrated Circuits and Systems, Vol. 19, NO. 2, February, pp. 272-278,2000.[39]F.Y. Young, Chris C.N. Chu, W.S. Luk and Y.C. Wong. “Floorplan Area Minimization using Lagrangian Relaxation”. Proc. ISPD, San Diego, CA., pp.174-179,2000.[40]F.Y. Young, C.C.N. Chu, W.S. Luk and Y.C. Wong “Handling soft modules in general nonslicing floorplan using Lagrangian relaxation,” IEEE Trans. On Comp. Aided Design of IC’s and System, Vol.20, No.5, pp. 687-692,May 2001.