Ant Colony Optimization for Vlsi Floorplanning with Clustering Constraints

[[abstract]]在超大型積體電路的設計過程中，平面規劃扮演著極其重要的角色。在給定 N 個大小不一的矩形電路模組且必須滿足特定限制條件的情況下，平面規劃旨在探討如何設計一種電路元件組合方式，使得容納所有模組的矩形晶片具有最小的面積。此一問題的一般形式已被證實為是 NP-完備 (NP-complete) 問題。因此目前的解決方案大多是以泛用啟髮式 (metaheuristic) 演算方法為解題工具，試圖在合理的時間之內產生可接受的問題解。本計畫中，我們擬以螞蟻族群優化法為基礎，發展出可用以求解 VLSI 平面規劃問題的演算法。我們將提出數種可能的設計策略，並針對各種設計策略進一步地分析其特性以及效能上的表現。初步的實驗結果顯示，本計畫所將發展之演算法在平面規劃問題的求解上確實是一個可行的方法。除此之外，為了能夠有效提升演算法的執行效能，我們也將探討如何將所設計的演算法予以平行化的相關議題。我們還將建置一個具有模組擴充能力之系統軟體工具。此一軟體工具不僅可以提供便於操作與觀察的視覺化介面，同時也能允許研究人員自行設計模組以提昇此工具之功能與彈性。[[note]]NSC95-2221-E327-02