平行化基因演算法應用於超大型積體電路之平面規劃

A Parallel Genetic Algorithm for Floorplanning in VLSI

陳致嘉(Chih-Chia Chen)

指導教授 ： 方志鵬 ； 張陽郎

國立臺北科技大學/電資學院/電機工程系研究所/碩士(2009年)

摘要

平面規劃是在傳統積體電路設計流程中的後端，實體設計裡所處理。平面
規劃的結果直接影響晶片面積的大小，面積越小則成本降低，故平面規劃問題
在積體電路設計中的重要性十分的高。
一般而言，在解平面規劃問題通常搭配模擬退火法(Simulated Annealing, SA)
來尋求較佳的解；然而隨著記憶體越來越大也越來越便宜，處理器亦邁入多核心
的時代，因此解決了基因演算法(Genetic Algorithm, GA)較耗記憶體的問題，平行
運算亦十分適合應用在基因演算法單一世代中染色體(Chromosome)的交配
(Crossover)及突變(Mutation)運算，並且，我們使用序列對(Sequence Pair)表示法，
其資料結構類似於染色體的結構，相當適合用於基因演算法的交配運算中，故我
們使用基因演算法搭配序列對表示法為基礎來處理平面規劃的問題。
為了加強搜尋解空間(Solution Space) 的能力， 我們引入直交實驗設計
(Orthogonal Experimental Design, OED)的概念，以期在相同的世代數(Generation)
中可以得到更好的解。
此外，我們使用多核心處理器(Chip Multiprocessor, CMP)在OpenMP的環境下
實驗上述的方法，其結果與傳統的循序式(Sequential)方法比較，我們可以在更快的
時間內得到同樣好的解。

關鍵字

平面規劃 ； 模擬退火法 ； 基因演算法 ； 平行計算 ； 直交實驗設計

並列摘要

In the traditional integrated circuit design flow, floorplanning is performed at the
earlier stage of physical design phase. Since the design cost significantly depends on
the result of floorplanning, a lot of attentions and efforts have been paid on solving the
floorplanning problem.
Because the floorplanning problem is intractable, floorplan problem can be
solved with indeterministic algorithm such as Simulated Annealing(SA) or Genetic
Algorithm(GA). For these two options, although GA is in nature suitable to be
performed in a parallel style, it seems SA rather than GA is preferred in the past studies
because of lower memory consumption. However, as the computers are equiped with
enormous memory, the weakness of GA becomes negligible. Besides, as the CPU has
entered the era of multicore, parallel computing environment makes GA a reasonable
approach for solving floorplanning problem of a complex design.
In our approach, we use GA and sequence pair representation to deal with
floorplan problems, in which sequence pair is used to simulate the chromosome's
structure. In order to strengthen the ability to search solution space, we have added
Orthogonal Experimental Design(OED) such that a better solution can be found faster
in each generation.
In addition, we use the Chip Multiprocessor(CMP) with the OpenMP
environment to perform parallel computing. After comparing the experimental results
with the traditional sequential approaches reported by the literatures, our approach
indeed is a competent approach for solving floorplanning problem.

並列關鍵字

Floorplan ； Simulated Annealing ； Genetic Algorithm ； Parallel ； Orthogonal Experimental Design

參考文獻

[5] 韓端勇、沈孟呈，「以二階段基因演算法解決帶有邊界限制之平面規劃最佳

[1] S. H. Gerez, Algorithms for VLSI Design Automation, John Wiley & Sons, 1999.

The MIT Press; 2th Ed. , 2001.

[3] Naveed Sherwani, Algorithms for VLSI Physical Design Automation, 3th Ed.,

[4] Sadiq M. Sait, Habib Youssef, VLSI Physical Design Automation: Theory and