以二階段基因演算法解決帶有邊界限制之平面規劃最佳化問題

A Two-phase Genetic Algorithm for the Floorplan Problem with Boundary Constraints

韓端勇(Tuan-Yung Han) ； 沈孟呈(Meng-Cheng Shen)

《建國科大學報》 26卷1期 (2006/10) Pp. 51-62

https://doi.org/10.6995/JCTU.200610.0051

摘要

本論文提出二階段基因演算法用以解決帶有邊界限制之超大型積體電路平面規劃最佳化問題。第一階段會找到可能有最佳解的區域，然後在第二階段仔細的檢視每個可能有最佳解區域內的合理解。此外也提出一種無需維護水平／垂直限制圖即可進行邊界檢查的方法，如此可以有效且快速的確認帶有邊界限制的區塊位置正確與否。由實驗的結果可看出在合理的時間內可滿足所有邊界限制要求並達成最後平面規劃最佳化之目的。

關鍵字

超大型積體電路平面規劃 ； 序列對 ； 基因演算法 ； 邊界限制

並列摘要

A two-phase genetic algorithm is presented in this paper to handle the boundary constraints on non-slicing floorplans. This algorithm is divided into two phases. In the first phase, it searches the whole solution space in order to find several promising areas. In the second phase, each of these promising areas is searched more thoroughly. In addition, a new boundary checking heuristic without using horizontal/vertical constraint graphs is also presented to effectively reduce the time to locate boundary blocks. The experimental results achieve promising area utilization with reasonable computation time that will satisfy the boundary constraints as required

並列關鍵字

VLSI floorplan ； sequence pair ； genetic algorithm ； boundary constraints