以繞線擁擠度最佳化為導向之平面規劃

Congestion-Driven Floorplanning

張仲喬(Chung-Chiao Chang)

指導教授 ： 謝財明

中原大學/工學院/資訊工程研究所/碩士(2004年)

https://doi.org/10.6840/cycu200400247

摘要

平面規劃在超大型積體電路的實體設計中扮演了很重要的角色，其決定了晶片上每一個模組的形狀及位置，平面規劃的結果將會深深地影響整個電路設計的效能。隨著製程技術不斷的進步，電晶體數目與訊號連線數亦隨之增加，電路連線對於整體晶片效能的影響愈來愈嚴重，因此近年來超大型積體電路實體設計皆提早考量與電路連線相關的最佳化問題。最小化晶片面積已不再是平面規劃階段主要的目標，取而代之的是縮短預估繞線長度、降低繞線擁擠度與解決訊號延遲等目標的考量。
本論文針對平面規劃繞線擁擠度最佳化的問題，利用平面規劃解之繞線擁擠度分佈特性，提出的新繞線擁擠度估計模型，其具有下列優點：(1) 增加彈性模組平面規劃在繞線擁擠度估計上的準確性，改進以兩模組中心點連線與模組邊界交點決定腳位位置之方式估計繞線擁擠度；(2) 不同於將晶片分割等大方格並以機率分析的方式估計繞線擁擠度，因此沒有如何分割等大方格大小的困擾；(3) 時間複雜度只與模組總個數n有關係(Ο(n^2))，可有效減低平面規劃求解的過程中，花費於估計繞線擁擠度的時間。此外並提出以數學規劃為基礎，結合模組切割的概念與新繞線擁擠度估計模型，依據繞線擁擠度的分佈情形，將模組切割使之形狀重新調整，以達到繞線擁擠度降低之目的。
最後以三種實驗方法對於新繞線擁擠度估計模型，與以數學規劃為基礎之模組切割平面規劃演算法進行測試：(1) 將新估計模型嵌入平面規劃求解演算法中，所求得之平面規劃解與未考慮繞線擁擠度的情況下，以及使用機率分析方式所得之平面規劃解之比較，具有較佳的繞線擁擠度；(2) 更進一步針對切割等大方格大小不同之機率分析方式，與利用新估計模型所求得之平面規劃解，並使用一個公正的評量模型估算其繞線擁擠度進行比較，新估計模型能有效地降低繞線擁擠度與節省求解時間；(3) 針對一組初始平面規劃解，依據繞線擁擠分佈情形切割模組，比較經由模組切割後之平面規劃解與初始平面規劃解，於繞線擁擠度上有明顯的降低。

關鍵字

繞線擁擠度 ； 非線性規劃 ； 平面規劃

並列摘要

Floorplanning plays an important role in physical design of VLSI circuits. It plans the shapes and locations of the modules on the chip, and the result of which will greatly affect the performance of the final circuit. As technology continues to scale down, the number of transistors and interconnections increasing rapidly, chip performance degradation caused by interconnection becomes more and more obvious. Therefore the related problems for interconnection optimization have been processed as early as possible in physical design of VLSI circuits design flow. Area minimization becomes less important while the minimization of interconnection length, the reduction on congestion, and the satisfaction at delay constraints become the major concern in floorplanning.
In this study, we analyze the distribution of wire congestion in a floorplan and propose the wire congestion model in response to the optimization problem relating to congestion in a floorplan. The advantages of our new model are listed as follows: (1) The results of the estimated wire congestion in soft module floorplanning by the model is more accurate than those determining position of the I/O pins by intersection-to-intersection method. (2) Different from the probability analysis based congestion model with fixed-size estimating grid, the new model has no shortcoming in how to determine the size of the grid. (3) Time complexity of the new model is O(n^2), where n is the number of modules, such that the time used in estimating the wire congestion is effectively reduced. Furthermore, combining the concept of reshaping and sizing of modules and the new congestion model, the nonlinear mathematical programming model is formulated to solve the congestion minimization problem according to the distribution of wire congestion.
We test our new congestion model and mathematical programming based floorplanning algorithm with module partition by three experimental methods: (1) We implement three floorplanning algorithms: embedded the new congestion model; without considering congestion; probability analysis based congestion model with fixed-size estimating grid. Experimental results show that our new model improves the floorplan solution on congestion. (2) We compare our new model with the probabilistic model with different size of fixed-size grid. Experimental results show that congestion can be better optimized using the new model with little penalty in area and wirelength. (3) Furthermore, by partitioning the module based on mathematical programming, we can obviously reduce the congestion of a given floorplan.

並列關鍵字

Floorplanning ； Wire congestion ； Nonlinear Programming

參考文獻

[2] T. Chen and M. K. H. Fan., “On Convex Formulation of the Floorplan Area Minimization Problem,” Proc. of International Symposium on Physical Design, pp. 124-128, Apr. 1998.

[5] P.N. Guo, C.K. Cheng and T. Yoshimura, “An O-tree representation of non-slicing floorplan and its application,” Proc. ACM/IEEE Design Automation Conference, pp. 268-273, 1999.

[7] X. Hong, S. Dong, G. Huang, Y. Ma, Y. Cai, C.K. Cheng and J. Gu, “A non-slicing floorplanning algorithm using corner block list topological representation,” IEEE Asia-Pacific Conference on Circuits and Systems, pp. 833-836, 2000.

[8] Y.L. Hsieh and T.M. Hsieh, “A New Effective Congestion model in Floorplan Design,” Proc. ACM/SIGDA Design, Automation and Test in Europe Conference and Exhibition, pp. 21204-21209, 2004.

[13] T. Lengauer, “Combinatorial Algorithms for Integrated Circuit Layout,” John Wiley & Sons, 1990.