FIT（情報科学技術フォーラム）2003

LC-007
多目的分散 GA をベースとしたパフォーマンスドリブン配置手法
Performance Driven Placement based on Distributed Genetic Algorithm
吉川 雅弥†
Masaya Yoshikawa

寺井 秀一‡
Hidekazu Terai

1. はじめにの弊害を起こす可能性がある。また，１つのセル列（同じデシミクロンオーダーのVLSI設計では，タイミング・消電源ラインで駆動するセル列）に同時にスイッチングする

費電力・配線混雑などをトータルで最適化するフィジカル

消費電力の大きなセルを配置するとピーク電流が増大する。

デザイン手法が求められる。タイミングや消費電力を最適

そこで概略配置では，各部分領域に割り当てたセルの消費化するためにレイアウト結果を修正する方法がこれまで一電力の総和を求め，その最大値から最小値を引いた値を評

般的にとられているが，SIAロードマップでも指摘されてい価関数とした。また詳細配置では，各セル列の消費電力のるように，0.1μm以下のプロセスではこのような修正箇所総和を求め，その最大値から最小値を引いた値を評価関数は数千箇所を越え，後処理でのレイアウト修正は限界を超とした。

えることが予想される。そこで本稿では，基本アルゴリズ

2.2 階層化ベクトルランキング

ムに遺伝的アルゴリズム(GA)(1)を採用し，消費電力やタイ本手法で提案するような配置手法のような多目的（多評ミング制約を同時に最適化する配置手法を提案する。GAを価）最適化問題において，各評価関数の線形和を求めて，レイアウト問題に適用した報告は文献(2)〜(5)の他にいくそれを評価にすることがまず考えられる。しかし，多点探つかあるが，ベクトルランキング法をベースとした多目的索を行う GA の特性を考慮すれば，線形和によるスカラー分散GA配置とそれを並列計算機に実装し，その効果を実証化手法で探索を行うより，図 2 に示すようなベクトルデーした発表はこれまでみあたらない。

タによるランキングを用いてパレート最適解の集合を求める方が，より広い解空間を探索することができる。しかし，

2. 配置アルゴリズム

単純にベクトルデータによるランキングを用いると，評価の優先度を考慮することが出来ない。そこで，評価の優先提案する配置手法は，多段分割を行う概略配置と分割領域内での配置を行う詳細配置の２ステップで構成した。

度に応じて階層的にランキングを行うことでこの問題を回

2.1 選択オペレーション避する。具体的には，まず仮想配線長の概略値による評価・低容量化による評価・タイミング制約による評価を用いて本研究では，以下に示す５つの評価関数を導入した。
(1)チップ面積による評価

ランク付けを行い，ランクが同じ個体に対しては，残りの(2)配線混雑による評価２つの評価（配線混雑・消費電力分散）で再ランク付けを(3)タイミング制約による評価行った。

タイミング制約を満足するためには，すべてのパスディレイが 1 クロックサイクル以内に収まる必要がある。しか{し，全てのパスディレイを毎世代・全個体について計算すると計算量が増大する。そこで処理時間の短縮を目的に，

0

図 2 に示すように，ある特定の世代の時にのみ全てのパスT

2T

図 1 パス評価のタイミングでディレイを計算・評価し，それ以外の世代では，特定のパス（遅延が大きいものから n 本：n はパラメータ）についてのみパスディレイの計算・評価を行った。
rank-2(4)低容量化による評価
低消費電力を実現するために，信号遷移率が高いネットrank-3の負荷容量（配線容量）を下げる評価関数を新しく考案した。具体的には，信号遷移率が閾値以上のネットの仮想配

rank-1rank-2線長の総和を評価とした。
(5)消費電力分散度による評価
消費電力の大きなセルを１箇所に配置すると，発熱など†立命館大学 VLSI センター ‡立命館大学 理工学部
{yosikawa,terai}@se,ritsumei.ac.jp

図 2 ベクトルデータによるランキング

63

FIT（情報科学技術フォーラム）2003

4. 並列計算機への実装

図 4 より，最悪パス遅延だけでなく，すべてのパスにつ4.1 並列処理方式

いて改善したことが読み取れる。今回実験に使用したデーセル配置における並列化を考えた場合，各プロセッサ

タは，0.35μm であるが，100nm 以下の微細プロセスでは，（PU）に LSI の部分領域を割り当て，各 PU が割り当てら

RC に起因する配線遅延は増大するため，提案手法による配れた部分領域の配置処理を順次行っていく並列化が考えら線遅延の改善がより顕著に現れると考える。また，並列計れる。しかし，本稿で提案する概略配置では，最も処理時算機に実装した結果，12PU で 11.2 倍の高速化が可能とな間を要するのは１回目の分割であり（遺伝子長が最も長い），った。

このような処理時間を多く要する初期の段階において，部

6. まとめ

分領域が 十分な数（少なくともＰＵ数） 生成されていないため，各ＰＵに部分領域を割り当てる並列処理方式が有本稿では，進化戦略をベースとするパフォーマンスドリ効であるとは言えない。そこで本研究では，ＧＡの全個体ブン配置手法を提案し，商用の EDA ツールとの比較実験にをいくつかの部分個体群に分割し，それぞれの部分個体群よりその有効性を確認した。提案した配置手法では，２段にＰＵを割り当てる並列処理方式を採用した。

階の配置手法をベースに，低容量化による消費電力の削減，4.2 階層化リングトポロジー

発熱・ピーク電流の増加を抑制するための消費電力の分散

生物学的な棲み分けと分化の現象を土台に，本研究では化，タイミング制約，配線混雑緩和，チップ面積最小化の

図 3 に示すような２段階の階層構造をもつリングトポロジ

各評価関数をＧＡの進化ループの中に組み込むことで，配ーを新しく考案した。階層化リングトポロジーでは，近傍置性能を向上した。今後の課題としては，配置の段階でクの部分個体群間（下位の PU 間）では個体交換の頻度を高ロストークノイズを低減するための制約モデルの検討が挙く，遠方の部分個体群間（上位の PU 間）での個体交換のげられる。
参考文献

頻度は低くした。

(1)

5. 実験評価・考察(2)

提案手法（PDP）の有効性を確認するために，セル数(3)969・ネット数 1089 の 0.35μmCMOS 論理データを用いて商用の EDA ツール（CET）との比較実験を行った。

(4)

配置結果を表１に示す。処理時間以外全ての配置評価項目で CET に比べて PDP の方が良好な結果となった。まず，(5)

消費電力に関して，高遷移率ネットの配線容量を削減することで，レイアウト設計段階で消費電力の削減が可能であJ.Holland: Adaptation in Natural Artificial Systems,
Second edition ; MIT Press, (1992)
K.Shahookar, et al,”Genetic beam search for gate matrix
placement,” IEE-proc.E :Computers and digital
Techniques,vol.141,No.2,pp.123-128,(1994).
H.Esbensen et al, “SAGA: Unification of genetic alg orithmwith simulated annealing and its application to macro-cell
placement”, Proc.IEEE Int. Conf. VLSI Design, (1994).
L.Jens,”A Parallel genetic Algorithm for Performance- Dri
ven VLSI routing,”IEEE Trans. Evolutionary Computation,
Vol.1,No.1,pp.29-39(1997)
中矢，小出，若林： 適応的遺伝的アルゴリズムに基づくVLSI
フロアプランニングの一手法 ，情報処理学会論文誌，vol.43,No.5, pp.1361-1371(2002)

ることを確認した。次に，タイミング制約に関して最悪パ
1000

ス遅延を 22.5%改善した。各パスの状態を図 4 に示す。
PU

PDP
800

Number

PU
PU

PU

PU

PU
PU

PU

PU
PU

CET

600
400

PU

200

PU

0

図 3 階層化リングトポロジー

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48

delay [ns]表 1 配置結果

PDP
CET64

図 4 各パスの状態