臺灣博碩士論文加值系統

由於VLSI的晶片設計進入到深次微米 (Deep-Submircon , DSM)以及
單一系統晶片(System-on-Chip , SoC)的廣泛應用，使得積體電路的
電路設計愈趨複雜，傳統以縮小面積為導向的板面規劃也因成本下降
，而顯得不再重要，代之而起的是決定IC設計成敗關鍵的繞線(Routing)
問題，為了提高電路可繞性(Routability)，在繞線之前的板面規劃階段
，若能使用較佳的資料表示法及透過有效的擁塞(Congestion)評估，將
可改善擁擠度，提高IC設計的成功率。
面對各種不同需求的板面規劃問題，本論文所採用的資料表示方法為雙重界限串列(Double-Bound-List, DBL)表示法，其除了集目前幾個代表性表示法(如sequence pair、O-tree與B*-tree)之優點外，尚可直接從表示法中得知總面積和區塊鄰近關係，而只需使用少量記憶體，更符合P-admissible特性的需求；板面規劃的成本計算繁複且耗時，冀望能在最短的時間內得到最佳化板面規劃，本論文還採用了階層式階梯輪廓(hierarchical stair contour)的資料結構記錄板面規劃的輪廓，以提高搜尋的效率。為了有效處理 擁塞問題，則採用階層式四分格模型(Hierarchical Quad-Grid Model)來 預估擁擠度，其隨著繞線疏密做動態的四分格分割方式，可以避免以往二維 格子模型因單一大小格子的分割方式，所造成評估不精確及浪費執行時間的 缺點。
一個在繞線之前就考慮擁擠度問題的板面規劃，可以減少日後繞線(Routing)程序所花費的時間，縮短產品上市的時程，增加市場競爭力。實驗結果顯示，所提出的方法很明顯的可以降低繞線擁擠度，雖然面積會稍微增大，但相對於因擁塞而繞線失敗，其效益是值得的。

As VLSI technology reaches deep-sub micron dimensions and
the application of SoC (System-on-Chip) design is general,
the scale of VLSI circuit becomes more complex. A traditional
area-driven floorplan become less important because of the
decrease in cost of chip area. In floorplan stage, it is
necessary for a successful chip design to develop an effective
congestion analysis before global routing base on floorplan or
placement information.
To deal with multi-objective floorplan issue, we proposed
double-bound-list (DBL) representation. DBL representation is
more advanced than other representations (Ex. sequence pair,
O-tree and B*-tree) and conform to the property of P-admissible
because we can find out the total area and the adjacent relation between blocks with less memory. We also proposed hierarchical stair contour as our data structure to record the contour of floorplan and reduce the time complexity of data searching. In order to handle routability problem efficiently, hierarchical quad-grid model is proposed to estimate congestion. Quid-grid partition depend on wire density to avoid less accurate and more timing-consuming in 2-D static uniform grid-based model.
A floorplan with congestion estimation before routing stage can reduce time complexity of routing procedure. The experimental results show that the method we proposed can decrease routing congestion with a few penalties for chip area.

中文摘要.......................................Ⅰ
英文摘要.......................................Ⅱ
致謝...........................................Ⅲ
目錄...........................................Ⅳ
圖形目錄.......................................Ⅵ
表格目錄.......................................Ⅷ
第一章 簡 介...................................1
第二章 相關研究................................5
2.1 可分割板面規劃..........................6
2.2 不可分割板面規劃........................6
2.2.1 序列對映(Sequence Pair)表示法...........7
2.2.2 O樹(O-tree)表示法.......................8
2.2.3 B*-樹(B*-tree)表示法....................8
2.2.4 CS(Corner Sequence)表示法...............9
2.2.5 TCG(Transitive Closure Graph)表示法.....9
2.2.6 CBL(Corner Block List)表示法............9
2.3 擁擠度評估(CONGESTION ESTIMATION)......10
2.4 研究動機...............................14
第三章 DBL表示法之模擬退火板面規劃............15
3.1 LB緊密板面規劃(LB COMPACT FLOORPLAN)...15
3.2 階層式階梯輪廓結構(HIERARCHICAL STAIR
CONTOUR STRUCTURE).....................16
3.2.1 實體的 L 類型角落......................17
3.2.2 凹陷的 L 類型角落......................19
3.2.3 緊密的板面規劃的建構與其階層式階梯輪廓.22
3.3 左下壓縮解的模型(LB-PACKING SOLUTION
MODEL).................................25
3.4 雙重界限串列表示法(DBL)................26
3.4.1 相鄰關係...............................27
3.4.2 一個緊密板面規劃的雙重界限串列表示法
(DBL)..................................29
3.4.3 一個雙重界限串列表示法(DBL)的緊密板面
規劃.............................. ...30
3.5 以模擬退火為基礎藉由有效搗亂操作的板面
規劃設計...............................31
3.6 DBL與其他表示法之比較..................35
第四章 階層式四分格模型與其擁塞可能性評估模型.37
4.1 階層式四分格模型(HIERARCHICAL QUAD-GRID
MODEL).................................37
4.2 階層式四分格中擁塞可能性評估模型.......43
第五章 以雙重界限串列表示法為基礎之擁擠導向板
面規劃.................................47
5.1 擁擠度估算.............................47
5.2 成本函式估算...........................52
5.3 攪亂運算...............................53
5.4 終止條件...............................53
第六章 實驗結果...............................55
第七章 結論與未來研究.........................59
參考文獻.................................... ...60

[1] R. H. J. M. Otten, "Automatic Floorplan Design,"
ACM/IEEE Design Automation Conference, pp.261-267
, 1982.
[2] D. F. Wong and C. L. Liu, "A New Algorithm for
Floorplan Design," ACM/IEEE Design Automation
Conference, pp.101-107, 1986.
[3] T. Ohtsuki, N. Suzigama, and H. Hawanishi, "An
Optimization Technique for Integrated Circuit
Layout Design," ICCST, pp. 67-68, 1970.
[4] S. M. Sait and H. Youssef, VLSI Physical Design
Automation: Theory and Practice, Singapore: World
Scientific, 1999.
[5] H. Onodera, Y. Taniquchi, and K. Tamaru, "Branch-
and-bound placement for building block layout," Proc.
DAC, pp.433-439, 1991.
[6] H.Murata,K. Fujiyoshi, S. Nakatake, and Y. Kajitani,
"Rectangle-Packing-Based Module Placement," IEEE/ACM
International Conference on Computer-Aided Design,
pp.472-479, 1995.
[7] S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani,
"Module Placement on BSG-Structure and IC Layout
Applications," IEEE/ACM International Conference on
Computer-Aided Design, pp.484-491, 1996.
[8] X. Tang and D. F. Wong, "FAST-SP: A Fast Algorithm
for Block Placement based on Sequence Pair," ACM
Asia and South Pacific Design Automation Conference,
pp.521-526, 2001.
[9] P. N. Guo, C. K. Cheng, and T. Yoshimura, "An O-tree
Representation of Nonslicing Floorplan and Its
pplications," ACM/IEEE Design Automation Conference,
pp.268-273, 1999.
[10] Y. Pang, C. K. Cheng, and T. Yoshimura, "An Enhanced
Perturbing Algorithm for Floorplan Design using the
O-tree Representation," ACM International Symposium
on Physical Design, pp. 168-173, 2000.
[11] Y. C. Chang, Y.-W. Chang, G. M.Wu, and S. W.Wu, "B*-
trees: A New Representation for Nonslicing Floorplans,
" ACM/IEEE Design Automation Conference, pp.458-463,
2000.
[12] J. M. Lin, Y. W. Chang and S. P. Lin, "Corner Sequence
- A P-Admissible Floorplan Representation with a
Worst Case Linear-Time Packing Scheme", IEEE
Transactions on VLSI Systems, Vol. 11, No. 4, pp. 679- 686, 2003.
[13] J. M. Lin and Y. W. Chang, "TCG: A Transitive Closure
Graph-Based Representation for Nonslicing Floorplans,
" ACM/IEEE Design Automation Conference, pp.764-769,
2001.
[14] X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C. K.
Cheng, and J. Gu, "Corner Block List: An Effective
and Efficient Topological Representation of
Nonslicing Floorplan," IEEE/ACM International
Conference on Computer-Aided Design, pp.8-12, 2000.
[15] S. Zhou, S. Dong, X. Hong, Y. Cai, and C. K.
Cheng, "ECBL: An Extended Corner Block List with
Solution Space including Optimum Placement," ACM
International Symposium on Physical Design, pp.156-
161, 2001.
[16] K. Sakanushi and Y. Kajitani, "The Quarter-State
Sequence(Q-Sequence) to Represent the Floorplan
and Applications to Layout Optimization," IEEE Asia
Pacific Conference on Circuits and Systems, pp.829-
832, 2000.
[17] C. Zhuang, K. Sakanushi, L. Jin and Y. Kajitani,
"An Enhanced Q-Sequence Augmented with Empty-Room-
Insertion and Parenthesis Trees," Design, Automation
and Test in Europe, pp.61-68, 2002.
[18] B. Yao, H. Chen, C. K. Cheng and R.
Graham, "Revisiting Floorplan Representations," ACM
International Symposium on Physical Design, pp.138-
143, 2001.
[19] Jin-Tai Yan, Feng-Ming Chen and Kai-Ping Lin, "Double
Bound List: A Dynamic Contour-Based Compacted
Representation of Non-Slicing Floorplans on LB-
Packing Solution Model," 15th VLSI Design/CAD
Symposium, 2004.
[20] J. Cong, J. Fang and Y. Zhang, "Multilevel approach
to full-chip gridless routing," IEEE International
Conference Computer-Aided Design, pp.396-403, 2001.
[21] J. Cong, M. Xie and Y. Zhang, "An enhanced multilevel
routing system," International Conference Computer-
Aided Desing, pp. 51-58, 2002.
[22] S. T. Wen, "Double-Bound List : A New Placement
Representation with Application to Simulated-
Annealing-Based Floorplan," Chung Hua University,
Master Thesis,2002.
[23] Jin-Tai Yan, "An efficient cut-based algorithm on
minimizing the number of L-shaped channels for safe
routing ordering," IEEE Trans. on Computer-Aided
Design of Integrated Circuits and Systems, Vol. 18,
pp. 1519- 1526, 1999.
[24] Jin-Tai Yan, "Designing a channel router by hybrid
methodology of top routing and bottom routing,"
Journal of Computers & Electrical Engineering, Vol.
25, pp. 57-75, 1999.
[25] J. Cong, J. Fang and Y. Zhang, "Multilevel approach
to full-chip gridless routing," IEEE International
Conference Computer-Aided Design, pp.396-403, 2001.
[26] J. Cong, M. Xie and Y. Zhang, "An enhanced multilevel
routing system," International Conference Computer-
Aided Desing, pp. 51-58, 2002.
[27] S. P. Lin and Y. W. Chang, "A novel framework for
multilevel routing considering Routability and
performance," International Conference Conputer-Aided
Design, pp. 44-50, 2002.
[28] J. Hu and S. S. Sapatnekar, "A timing-constrained
simultaneous global routing algorithm," IEEE Trans.
on Computer-Aided Design of Integrated Circuits and
Systems, Vol. 21, pp. 1025-1036, 2002.
[29] F. Y. Young, C. N. Chu and Z. C. Shen, "Twin Binary
Sequence: A Non-redundant Representation for General
Non-Slicing Floorplan," IEEE Transactions on Computer-
Aided Design, Vol. 22, No. 4, pp.457-469, 2003.
[30] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi,
"Optimization by Simulated Annealing," Science, Vol.
220, pp. 671-680, 1983.