以繞線擁擠度最佳化為導向之平面規劃與模組形狀變化

Congestion-Driven Floorplanning by Adaptive Modular Shaping

10.29948/JAE.200607.0005

黃信雄(H. H. Huang)；張仲喬(C. C. Chang)；林志遠(C. Y. Lin)；謝財明(T. M. Hsieh)；李志宏(C. H. Lee)

平面規劃 ； 模組變形 ； 非線性程式規劃 ； 擁擠度 ； floorplanning ； modular shaping ； nonlinear programming ； congestion

先進工程學刊

1卷1期（2006 / 07 / 01）

31 - 43

繁體中文

本論文使用兩階段的方法來同時改善平面規劃之擁擠度和連線總長度。首先使用模擬退火法的方式來找到一組兼具繞線長度、面積和繞線擁擠度的平面規劃解答，然後針對平面規劃中最擁擠的區域進行改善。每個被選到的模組將會被分割成一個小矩形集合，藉此來延長相鄰模組間的公用邊長度。我們將採用非線性規劃的方法以決定模組最後的形狀，目標是在不增加面積的條件下，改善局部擁擠度高的區域。和傳統的方法相比較，模組變形的方法將可降低22%的繞線擁擠度和1.54%連線總長度。

In this paper, we implement a two-stage process to simultaneously minimize wire congestion and total wire-length at floorplanning stage. We first use a simulated-annealing approach with sequential-pair representation to find a floorplan with minimal wire congestion, total wire-length and area. Each of the two selected adjacent soft modules in congested region is then divided into a set of connected sub-rectangles to increase the common boundary between the adjacent modules. The longer common boundary actually reduces total wire-length between the pins of two modules and minimizes the wire congestion. A nonlinear programming method is used for modular shaping mentioned above to further minimize the wire congestion without the penalty of area. Compared to the traditional method without consideration of the modular shaping, we show experimentally that our algorithm achieves an average reduction rate of 22% and 1.54% in wire congestion and total wire-length, respectively.