セル移動に基づく改良型ミニカット配置アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
配置アルゴリズムに広く採用されているミニカット法には、局所最適解に陥り易いという問題がある。また、カット数の最小化のみに捕らわれて処理を進めるとセルの分布が不均一な配置となる恐れがある。本稿では、セル移動処理に基づく改良型ミニカット配置アルゴリズムを提案する。この方法は、カットラインで分割された各領域内のセル配置可能面積に対するセルの面積和の比率(占有率)の高い領域から低い領域へのセル移動を全てのセルに対して繰り返し実行するので、局所最適解に陥り難く、占有率が均一でカット数が最小の分割を得ることが出来る。ゲートアレイの実データを用いた計算機実験の結果、従来のミニカット法に対し約1/2の処理時間でカット数が10%少ない配置を得た。
1992-09-28

著者

関連論文

スポンサーリンク