成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	詹凱仲 Chan, Kai-Chung
論文名稱：	在固定框架限制下考量可繞線性之平面規劃方法 A Routability-Driven Floorplanning Methodology With Fixed-outline Constraint
指導教授：	林家民 Lin, Jai-Ming
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2013
畢業學年度：	101
語文別：	英文
論文頁數：	49
中文關鍵詞：	平面規劃、固定框架、可繞線性
外文關鍵詞：	floorplanning, fixed-outline, routability
相關次數：	點閱：147 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

隨著電路設計的複雜度上升，大量的連線(nets)以及標準元件(standard cells)將會造成繞線的困難，使得在元件擺置(placement)/平面規劃(floorplan)考量可繞線性成為一個重要的議題。即使平面規劃在晶片設計中佔了舉足輕重的地位，但是相對於元件擺置，甚少有討論平面規劃的可繞線性之論文。而那些在元件擺置中考量可繞線性之方法，由於兩者的情況不同，並不適合直接套用在平面規劃中。因此在此篇論文中，我們提出了一個可以增進可繞線性的平面規劃方法，與傳統平面規劃法使用模擬退火法(simulated annealing)相比不同的是，我們以數學最佳化逼近的方式為基礎，來處理平面規劃的問題，讓我們的方法有著更高的穩定性以及更快的執行速度。
此平面規劃演算法大致上可以分成兩個階段，分別為全域散佈階段(global distribution stage)，以及合法化階段(legalization stage)。在全域散佈階段，此篇論文致力於在減少連線線長以及繞線擁擠的情況下，將電路模組均勻地散布至整個固定框架的晶片中。即使在此階段後，仍存在一些電路模組彼此重疊的情況，但是此初步的平面規劃之解具有良好的線長以及較佳的可繞線性。因此在合法化階段，重點在於盡量不移動電路模組相對位置的情況下，移除重疊的情形。在此階段，我們首先提出了一個遞迴分割的演算法，將前一階段之平面規劃結果建出一棵切割樹(slicing tree)。接著針對此切割樹，使用曲線合併以及座標點回溯的方式，完成一個無重疊，且有著優良連線線長以及更高可繞線性的平面規劃。
為了在平面規劃階段能夠更精確的評估擁擠程度，此篇論文提出一個新的模型來去預測實際繞線的使用量；我們亦將此模型轉換為一可微分且連續之方程式，讓我們能套用數學分析的方式將此模型做最佳化。
實驗結果顯示出我們提出的模型，相比於NTUPlcae4提出的模型有著更高的準確性。我們利用此方法產生之平面規劃結果與DeFer以及我們不考量可繞性之結果相比，不只在繞線擁擠程度上下降外，也得到更好的線長。

As design complexity grows continuously, large number of nets and cells (modules) causes routing much difficulty in modern designs, which makes routability become an important issue in floorplanning/placement. Although floorpalnning still plays an important role in an SOC design, there exists less number of papers discussing routability in floorplanning relative to placement. However, approaches which are adopted in placement cannot be directly applied to deal with floorplanning because of the difference between floorplanning and placement. In this thesis, we propose a methodology which can improve the routability in floorplanning. Unlike traditional floorplanners which adopted the simulated annealing algorithm, this thesis uses a analytical based approach to handle routability-driven floorplanning, which is steadier and faster.
It consists of two stages which include global distribution stage and legalization stage. In global distribution stage, it aims to obtain better wirelength and less overflows while distributing modules evenly over the fixed-outline. Since a good result is obtained in the first stage, it is only has to remove the overlaps between modules and maintain the topology order of modules in legalization stage. In legalization stage, curve merging [24] in a slicing tree [20] which is generated by a partition based approach, is applied to legalize the floorplan. After legalization stage, a legal floorplan which has good wirelength and little overflows can be obtained.
In order to estimate congestion more accurately in floorplanning, this thesis proposes a new model to measure net usages, and then transform it into differentiable function such that it can be solved by the analytical approach.
The experimental results demonstrate that the new routing usage model is more precise than that used by NTUPlace4 [10]. Besides, our floorplanning results induce less number of overflows compared to those by DeFer [28] and mine without considering routability, moreover, the wirelength is even smaller than theirs.

Table of Contents
摘要	i
ABSTRACT	iii
誌    謝	v
List of Tables	viii
List of Figures	ix
Chapter 1.	Introduction	1
1.1	Previous Works	1
1.1.1	Floorplanning Algorithms	1
1.1.2	Routability-Driven Algorithms	2
1.2	Motivation	4
1.2.1	Flexible Floorplanning Algorithm	4
1.2.2	Routing Usage Model	4
1.3	Our Contribution	7
Chapter 2.	Problem Formulation	9
2.1	Floorplanning information	9
2.2	Routing Information	9
2.3	Target	10
Chapter 3.	Review of Relative Works	11
3.1	Enumerative Packing	11
3.2	Routing Resource Blockage	13
Chapter 4.	Overview of Our Algorithm	15
Chapter 5.	Global Distribution Stage	17
5.1	Review of Wirelength and Density Terms	18
5.2	Routability-Driven Term	19
5.2.1	New Usage Model	20
5.2.2	Optimization of Ue(x,y)	23
Chapter 6.	Legalization Stage	27
6.1	Generation of Slicing Tree	28
6.1.1	Assignment of Modules	29
6.1.2	Allocation of Regions in Each Partition	31
6.1.3	Re-Distribution of Modules	33
6.2	Merging and Tracing Back of Curves	35
Chapter 7.	Experimental Results	37
7.1	Usage Model	37
7.2	Floorplanning Results	38
Chapter 8.	Conclusion	45
References	46

List of Tables
Table 7 1	Comparison of routing usage estimation model	43
Table 7 2	Comparison of floorplanning results	44

List of Figures
Figure 1 1. (a) A floorplanning result which only minimizes wirelength. The green dotted lines denote the nets which connect to pins. If the capacity of a routing edge is 1, there exist two routing edges violating the constraint (enclosed by red lines). (b) If the routability is considered, it is possible to eliminate overflows while maintaining good wirelength in the same density condition.	6
Figure 2 1. The routing grids and a routing graph. (a) Each routing grid is surrounded by four routing edges. (b) The edges in routing graph denote the capacity of associative routing edges.	10
Figure 3 1. All relationships between module A and B can be recorded by ⊕.	12
Figure 3 2. Shape curves operations. Each point in a curve denotes a shape of a module with its width and height shown in the x and y coordinates. (a) Horizontal combination of two curves A and B, and the resulting shape curve is Ch. (b) Flipping Ch by the 45 degree line and Cv curve is obtained. (c) The resulting shape curve Cm is merging from Ch and Cv.	12
Figure 3 3. The different slicing tree structures for modules 3-6.	13
Figure 4 1. (a) In global distribution stage, the modules are spread over the specified region. (b) A slicing tree is constructed according the topological order (relative positions) among modules. (c) Based on the slicing tree, it can legalize the floorplan by operating merging shape curves and tracing back on this slicing tree.	16
Figure 5 1. To evenly spread modules over a specified region, we divide chip region into many uniform bins.	19
Figure 5 2. (a) Decompose the multi-pin net into a set of 2-pin nets according to the x-coordinates of pins along x-direction. (b) Decompose the multi-pin net into a set of 2-pin nets according to the y coordinates of pins along y-direction.	20
Figure 5 3. Given a routing graph G with a set of routing edges in red color, the enclosed region R(p1,p2) for a two-pin net n(p1,p2) is covered by blue color (xp1,yp1) and (xp2,yp2) are the coordinates of p1 and p2 in n(p1,p2), respectively. The edges in G which are overlapped by R(p1,p2) (in red color) are more likely to be used for routing  n(p1,p2). Since five columns in G are covered by R(p1,p2). Col(p1,p2) for n(p1,p2) is 5.	22
Figure 5 4. The proposed logical function f(u,x,v), where u and v are set to two and four, respectively. While the value ε becomes larger, the value of estimated logical function will be closer to exact logical function f(u,x,v).	24
Figure 5 5. The x-coordinate and y-coordinate denote dx and overlap between m and eh, respectively. The exact overlap is drawn by brown color, and the overlap estimated by bell-shape is drawn by blue color.	26
Figure 6 1. Our legalization flow.	28
Figure 6 2. While the straight line passes across modules, it produces jags between such line and modules’ boundary.	30
Figure 6 3. (a) Divide the region into many tiles, and a min cost cutline ld is selected. (b) Modules are assigned into two partitions according to their relative locations to ld.	32
Figure 6 4.(a) The width of left region is not enough for placing the largest module. (b) Reallocate the location of the cutline la, and some modules should be re-assigned.	34
Figure 6 5. (a) The initial locations of modules before re-distribution. (b) Compact those modules which are crossed by sub-region’s boundary into sub-region. (c) Re-spread the modules to mitigate local un-uniform density.	35
Figure 6 6. After a slicing tree has been generated, we first apply enumerative to generate the curve of each leaf node. And then, we merge the curves bottom-up to construct the root node’s curve Cr. The points which are within fixed-outline are called valid points, and we choose those points to trace back and pack to find out the final solution.	36
Figure 7 1 The resulting floorplans of different benchmarks. (a) ibm04 with wirelength 8.38e+06 and overflows 82260. (b) ibm06 with wirelength 7.92e+06 and overflows 137110. (c) ibm12 with wirelength 29.08e+06 and overflows 544478 (d) ibm16 with wirelength 53.43+06 and overflows 1101584 .	40
Figure 7 2. The normalized congestion maps of different floorplanners on benchmark ibm01 which are generated by (a) DeFer (b) Our un-routability work (c) Our routability-driven work.	41
Figure 7 3. The normalized congestion maps of different floorplanners on benchmark ibm04 which are generated by (a) DeFer (b) Our un-routability work (c) Our routability-driven work.	41
Figure 7 4. The normalized congestion maps of different floorplanners on benchmark ibm06 which are generated by (a) DeFer (b) Our un-routability work (c) Our routability-driven work.	42
Figure 7 5. The normalized congestion maps of different floorplanners on benchmark ibm09 which are generated by (a) DeFer (b) Our un-routability work (c) Our routability-driven work.	42


                                    

[1] S. N. Adya, and I. L. Markov, “Fixed-Outline Floorplanning: Enabling Hierarchical Design,” IEEE Transactions on VLSI, Vol. 11, No. 6, pp. 1120-1135, 2003.
[2] T.-C. Chen, Y.-W. Chang, S.-C. Lin, IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs. In Proc. ICCAD, pp. 159-164, 2005.
[3] J. Cong, M. Romesis, and J. Shinnerl, “Fast Floorplanning By Look Ahead Enabled Recursive Bipartitioning,” IEEE Transactions on CAD, Vol. 25, No. 9, pp. 1719-1732, 2006.
[4] M. Cho, K. Lu, K. Yuan, and D. Z. Pan, “BoxRouter 2.0: Architecture And Implementation Of A Hybrid And Robust Global Router,” in Proc. ICCAD, pp. 503-508, 2007.
[5] Y. -J. Chang, Y. -T. Lee, and T. -C. Wang, “NTHU-Route 2.0: A Fast And Stable Global Router,” in Proc. ICCAD, pp. 338-343, 2008.
[6] C. C. N. Chu and Y. C. C. Wong, “FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm For VLSI Design,” IEEE Transactions on CAD, pp. 70-83, Vol. 27, No. 1, 2008.
[7] T. -C. Chen, Z. –W. Jiang, T. –C. Hsu, H. –C. Chen, and Y. –W. Chan, “NTUPlace3: An Analytical Placer For Large-Scale Mixed-Size Designs With Preplaced Blocks And Density Constraint,” IEEE Transactions on CAD, vol. 27, No. 7, 2008.
[8] K. R. Dai, W. H. Liu, and Y. L. Li, “NCTU-GR: Efficient Simulated Evolution-Based Rerouting And Congestion-Relaxed Layer Assignment On 3-D Global Routing,” IEEE Transactions on VLSI, Vol. 20, No. 3, pp. 459-472, 2012.
[9] M. Hanan, “On Steiner’s Problem With Rectilinear Distance,” in SIAM J. Appl. Math., vol. 14, no. 2, pp. 255-265, 1966.
[10] M. -K. Hsu, S. Chou, T. -H. Lin, and Y. -W. Chang, “Routability-Driven Analytical Placement For Mixed-Size Circuit Designs,” in Proc. ICCAD, pp. 80-84, 2011.
[11] Z. W. Jiang, B. Y. Su, Y. W. Chang, “Routability-driven Analytical Placement By Net Overlapping Removal For Large-scale,” in Proc. DAC, pp.167-172, 2008.
[12] G. Karypis and V. Kumar, “Multilevel K-way Hypergraph Partitioning,” in Proc. DAC, pp. 343-348, 1999.
[13] M. Kuwano, and Y. Takashima. Stable-LSE based analytical placement with overlap removable length. In Proc. SASIMI, pp. 115-120, 2010.
[14] M. C. Kim, D. J. Lee, I. L. Markov, “A SimPLR Method For Routability-driven Placement,” in Proc. ICCAD, pp. 67-73, 2011.
[15] M. Lai, D. Wang, “Slicing Tree Is A Complete Floorplan Representation,” in Proc. DATE, pp. 228-232, 2001.
[16] J. -M. Lin and Y. -W. Chang, “TCG: A Transitive Closure Graph Representation For Non-slicing Floorplans,” in Proc. DAC, pp. 764-769, 2001.
[17] C. Li, M. Xie, C. -K. Koh, J. Cong, and P. H. Madden, “Routability-driven Placement And White Space Allocation,” in Proc. ICCAD, pp. 394-401, 2004.
[18] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Rectangle-Packing Based Module Placement,” in Proc. ICCAD, pp. 472-479, 1995.
[19] W. C. Naylor, R. Donelly, and L. Sha. “Non-linear Optimization System And Method For Wire Length And Delay Optimization For An Automatic Electric Placer,” U.S. Patent 6 301 693, Oct. 9, 2001.
[20] R. H. J. M. Otten, “Automatic Floorplan Design,” in Proc. DAC, pp.261-267, 1982.
[21] R. H. J. M. Otten, “Efficient Floorplan Optimization,” in Proc. ICCD, pp.499-502, 1983.
[22] J. A. Roy, N. Viswanathan, G.-J. Nam, C. J. Alpert, and I. L. Markov, “CRISP: Congestion Reduction By Iterated Spreading During Placement,” in Proc. ICCAD, pp. 357–362, 2009.
[23] P. Spindler and F. M. Johannes, “Fast And Accurate Routing Demand Estimation For Efficient Routability-driven Placement,” in Proc. DATE, pp. 1266-1231, 2007.
[24] D. F. Wong and P. S. Sakhamuri, “Efficient Floorplan Area Optimization,” in Proc. DAC, pp. 586-589, 1989.
[25] Y. -C. Wang, Y. -W. Chang, G. -M. Wu and S. -W. Wu, “B*-Tree: A New Representation For Non-Slicing Floorplans,” in Proc. DAC, pp. 458-463, 2000.
[26] Y. Xu, Y. Zhang, and C. Chu, “FastRoute4.0: Global Router With Efficient Via Minimization,” in Proc. ASPDAC, pp. 576-581, 2009.
[27] X. Yang, B. -K. Choi, and M. Sarrafradeh, “Routability-Driven White Space Allocation For Fixed-Die Standard-Cell Placement,” IEEE Transactions on CAD, Vol 22, No. 4, pp. 410-419, 2003.
[28] J. Z. Yan and C. Chu, “DeFer: DeFered Decision Making Enable Fixed-outline Floorplanning Algorithm,” IEEE Transaction on CAD, Vol. 29, No. 3, pp. 119-130, 2010.
[29] Y. Zhan, Y. Feng and S. S. Sapatnekar, “A Fixed-Die Floorplanning Algorithm Using an Analytical Approach,” in Proc. ASP-DAC, pp. 771–776, 2006.
[30] Wikipedia, the free encyclopedia. Avaliable : http://en.wikipedia.org/wiki/Sigmoid_function
[31] HB Floorplan Benchmarks. Available: http://cadlab.cs.ucla.edu/cpmo/HBsuite.html.
[32] 2012 ICCAD CAD CONTEST. Avaliable : http://cad_contest.cs.nctu.edu.tw/CAD-contest-at-ICCAD2012/problems/p2/p2.html

校內：2018-08-06公開
校外：不公開電子論文尚未授權公開，紙本請查館藏目錄

簡易檢索 / 詳目顯示

相關論文