Ant Colony Optimization for VLSI Floorplanning with Clustering Constraints

螞蟻族群最佳化應用於具有叢聚限制之超大型積體電路平面規劃

江傳文(Chuan-Wen Chiang)

《工業工程學刊》 26卷6期 (2009/11) Pp. 440-448

https://doi.org/10.29977/JCIIE.200911.0002

摘要

本文中，我們以螞蟻族群最佳化的基本原理爲基礎，提出一個可用以解決具有叢聚限制之超大型積體電路平面規劃問題的演算法。此一演算法採用兩種不同類型的費洛蒙嗅跡做爲人工螞蟻彼此間的溝通媒介，有效地導引人工螞蟻建構出高品質的平面規劃內容。此外，針對演算法以及所求解問題之特性，我們同時也設計出一個名爲「動態接合點串列」表示法用以記錄所得之平面規劃的內容。相較於傳統的叢聚限制平面規劃技術，實驗結果顯示本文所提出之方法在求解效能方面有更爲顯著的優異表現。

關鍵字

超大型積體電路平面規劃 ； 叢聚限制 ； 組合最佳化問題 ； 螞蟻族群最佳化

並列摘要

In this study the very large scale integration (VLSI) floorplanning problem with clustering constraints and the layout area as the minimization criterion is considered. An algorithm, which is based on the primary principles of ant colony optimization (ACO), to solve this problem is presented. This ACO-based algorithm employs two different types of pheromone trails as the communication media among artificial ants to effectively guide them to cooperatively construct a high quality floorplan. On the basis of the characteristics of ACO, moreover, an encoding scheme, which is referred to as dynamic junction list (DJL), is proposed to represent the geometric relationships between circuit modules for a floorplan. Experimental results using the Microelectronics Center of North Carolina (MCNC) benchmarks demonstrate the effectiveness of the proposed algorithm.

並列關鍵字

very large scale integration floorplanning ； clustering constraints ； combinatorial optimization problems ； ant colony optimization

參考文獻

Chiang, C. W.(2008).Applying an improved fast ant system to DAG scheduling for computational grids.Journal of the Chinese Institute of Engineers.31,1113-1125.

Chiang, C. W.,Y. Q. Huang,W. Y. Wang(2008).Ant colony optimization with parameter adaptation for multi-mode resource-constrained project scheduling.Journal of Intelligent and Furry Systems.19,345-358.

Dorigo, M.,C. Blum(2005).Ant colony optimization theory: a survey.Theoretical Computer Science.344,243-278.

Dorigo, M.,L. M. Gambardella(1997).Ant colony system: a cooperative learning approach to the traveling salesman problem.IEEE Transactions on Evolutionary Computation.1,53-66.

Dorigo, M.,V. Maniezzo,A. Colorni(1996).The ant system: optimization by a colony of cooperating agents.IEEE Transactions on Systems, Man, and Cybernetics Part B.26,29-41.