多階段階層式平面規劃

Multistage Hierarchical Floorplanning

傅文佑(Wen-Yu Fu)

指導教授 ： 謝財明

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

https://doi.org/10.6840/cycu200200069

摘要

隨著製程技術進入深次微米後，電路連線上的延遲效應愈來愈明顯。在考量電路的效能與穩定度時，如何有效降低連線上的延遲已成為當前的重要課題。平面規劃階段決定模組的擺放位置，因此會直接影響晶片上模組間的連線及晶片面積。
傳統平面規劃與模組置放問題之研究，大多於提出各種模組間關係位置之表示法後，再利用模擬退火演算法以單一階段(one stage)方式求解。求解的過程中，解的接受與否是由目標函數 所決定，其中Ａ為該解的晶片面積大小，而W為晶片上模組間連線長度預估值之總和。此類方法在同時考慮面積最小化及連線最小化時，如何決定目標函數中的權重係數 , …值，使最後得到的解能在面積最佳化上與連線最佳化上取得很好效果卻是非常困難的。
本論文提出一個多階段 (multiple stage) 處理之平面規劃方法，不只使連線最小化並能同時有效降低晶片面積。在第一階段中本計劃將以模組間訊號連線為考量，求得一初始平面規劃；第二階段是根據前一階段所得之平面規劃，在不大幅更動原模組擺置相對位置之前提下，以階層式方法進行面積最小化。
實驗結果顯示，我們的演算法可以很有效率的使連線總長最小化並能同時有效降低晶片面積。

關鍵字

模組置放 ； 連線總長度 ； 內接連線 ； 平面規劃 ； 階層式 ； 面積最小化

並列摘要

As the process technology enter the deep sub-micron era, the delay effect caused by the interconnection is more and more obvious. Today, how to reduce the interconnection delay effectively has become an important subject when we consider the performance and stability of circuits. Because the position of each module is decided during floorplanning, the overall interconnection delay among modules can be calculated from the result of floorplanning.
To solve floorplanning and module placement problems, most of the previous researches attempted to provide placement representations and used the single stage approach based on the simulated annealing algorithm. During the annealing process, the solution will be accepted or not is decided by the objective functions such as where A is the final chip size and W is the total wirelength. The one stage approach based on SA is powerful and can find satisfied solutions for the single optimized objective. However, when we consider the multiple optimization goals on both area and total wirelength at the same time, it is very difficult to find the balanced point for deciding the weighted cofactors , …and so on.
We propose a project to develop a multiple stage floorplanning algorithm that can minimize not only the total interconnection wirelength but also the chip area. In the first stage, we propose an algorithm to find an initial floorplan according the interconnection relation of signals among modules. In the second stage, we will develop a hierarchical area minimization algorithm that can premise the module topology generated by the first stage will not be modified violently. And we will introduce the module partition concept of in the second stage to further improve the solution for the area minimization.

並列關鍵字

interconnection ； area minimization ； total wirelength ； module placement ； floorplanning ； hierarchical approach

參考文獻

[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.

[6] 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.

[7] 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.