JPH0642254B2 - 等サイズブロックレイアウト方法 - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、ＬＳＩ設計プリント板設計において電子部品
の配置の改良方式に関する。

（従来の技術） 従来、ＩＣや論理ゲートの配置改良を行う場合、ペア変
換法がよく用いられていた。この方法はｎ×ｎ個の２次
元に配置された部品の中からランダムに２つの部品をと
り出し、これを交換することにより、総配線長が小さく
なるかどうかをマンハッタン距離の総和を求めて評価し
ながら改良を行っていた。この方法は、いわゆる山登り
法と呼ばれる方法の類の一つであり、総配線長を山の高
さに対応させ、部品配置の全ての仕方に対して図示した
とすると、任意の２つの部品交換により、山の高さが低
くなるかどうかを判定し、低い方へ向かうように交換ペ
アを選択しながら処理を進めていく方法であった。

（発明が解決しようとする問題点） 従来のペア交換法によると、同時に２つのペアの交換の
みを考えており、交換前の配置に対する評価関数の値
が、どの２つの部品ペアを交換しても変化しなくなった
とき処理を停止するというものであったため、３つ以上
の部品を同時に交換すれば、評価関数の値が最適値に近
づくことがあっても、同時に２つの部品のみしか交換し
ないという制限を設けているため、評価関数が比較的悪
い所で止まってしまい、それ以上の処理が打ち切られて
しまうという欠点があった。

（問題を解決するための手段） 本発明の方法は、ペア交換法における同時に２つの部品
しか交換しないという制約を緩め、同時にｍ個の（ｍ≧
３）部品まで交換の対象とすることで評価関数の値を、
より最適値に近づけると共に、同時にｍ個の部品を交換
する際のｍの階乗通りの組み合わせに対する評価関数の
計算を並列に独立して実行し、高速に処理を行うことに
より実現される。

（実施例） 次に本発明の実施例について図面を参照して説明する。

第１図は本発明の原理を示す説明図である。

第１図において数字１〜６４は８×８の格子状に区分さ
れた小領域を示しており、各小領域には１つの部品がそ
れぞれ配置される。初期配置においては例えば重心法と
呼ばる方法により、予め与えられた各部品間の配線接続
情報を用いて求められた配置に従い、各部品が置かれ
る。本実施例においては、一例として６４個の矩形状の
部品を６４個の位置に置く場合を考えたが、部品点数が
増えても同様の方法が適用できる。

本発明の方法は、まず第１ステップとして、６４個の初
期配置された部品の中からランダムにｍ個の部品を選択
する。第２図においては斜線を施した小領域19,30,50,5
6を選んだ場合（ｍ＝４の場合）を示す。

次に第２ステップとして、この４個の部品の任意の配置
交換の全ての仕方である４の階乗＝２４通りの配置につ
いて、それぞれ評価関数を求める。評価関数としては４
個の部品と接続さている部品との間でマンハッタン距離
と呼ばる値の接続線の本数に関する総和を用いる。マン
ハッタン距離というのは接続すべき始点と終点をＸ方
向、Ｙ方向に平行な線分のみを用いて最短距離で結ぶ線
分の長さである。第３ステップとして、求まった２４通
りの評価関数の中で交換を行う以前に比べて値が小さく
なったものがあれば、その中から１つだけ選んでその交
換を実行する。小さくなったものが１つもなかった場合
には、処理は終了する。交換が行われた場合には、その
配置の状態を元にして更に上記の配置交換処理をくり返
す。

以上の例では同時に４つの部品をとり出して、２４通り
の配置の仕方について評価関数を求める方法について述
べたが、同時にとり出す部品点数を更に増やすことによ
り、評価関数を、より最適値に近づけることが可能であ
る。量産品の場合などでは歩留まり向上のため少しでも
最適値に近づけることが有利となり、例えば同時に５つ
の部品をとり出し１２０通りの配置の仕方につき並列に
処理することも可能であるが、処理量が増大すること
と、改善の度合が飽和していくので、実用上は４つの部
品程度がコストパフォーマンスの点で良い結果が得られ
る。

本実施例ではペア交換法のみについて述べたが、ペア交
換法の拡張として、シミュレーティドアニーリング法が
あり、この場合には評価関数が多少悪くなっても一定範
囲の下で、ペアを交換する。この方法においても本発明
が同様にして適用できる。

第２図は本発明の等サイズブロックレイアウト方法を実
施するための装置の一例を示すブロック図である。第１
図の等サイズブロックレイアウト方式はホストパーソナ
ルコンピユータ101と、インタフェース回路102と、デー
タ駆動パイプラインプロセッサ103〜110と、イメージメ
モリ111とから構成される。

処理の対象となる部品の位置情報、部品間結線情報はパ
ーソナルコンピユータ101とからインタフェース回路102
を介してイメージメモリ111に格納される。８個のパイ
プラインプロセッサ103〜110はプログラマブルであり、
処理の内容に応じてあらかじめパーソナルコンピユータ
から制御コードを初期設定され、インタフェース回路10
2はイメージメモリ111のアドレス発生、読み出し書き込
み制御、プロセッサ群103〜110とのデータ転送を時分割
的に切換えておこなう。

初期配置済みの配置情報は６個のプロセッサ群104〜109
にコピーされ、評価関数の計算に用いられる。全部で２
４通りの配置の仕方があるので、４通りずつ６個のプロ
セッサに均等に割り当てられ、並列に処理される。プロ
セッサ103と110はそれぞれ前処理と後処理に用いいら
れ、プロセッサ103では２４通りの配置の仕方の分割が
行われ、６個のプロセッサ群104〜110に対して必要なイ
メージメモリ111のアドレス値や配置交換の対象となる
小領域のX,Y座標値が転送される。

プロセッサ111では、２４通りの評価関数のうち配置交
換される以前の評価数値と比べて小さくなったもののう
ちの１つを選択し、部品位置の交換を行い、イメージメ
モリ111の中に貯えられている部品配置情報の更新を行
う。評価関数値がそれ以上良くならないかどうかを判定
し、良くならないならば、処理を終了し、パーソナルコ
ンピュータ101に処理終了割込信号を送出する。

（発明の効果） 以上述べたとおり、本発明には、電子部品の結線情報及
び初期配置情報に基づいてマンハッタン距離の総和を評
価関数とし、より最適な値に近いところまで求めること
が可能となり、しかも並列プロセッサ構成のシステムに
より高速に処理することができるという効果がある。

【図面の簡単な説明】

第１図は本発明の原理の説明図、第２図は本発明を実施
するための装置の一例を示すブロック図である。 101……パーソナルコンピユータ、102……インタフェー
ス回路、103〜110……データ駆動形パイプラインプロセ
ッサ、111……イメージメモリ。

Claims (1)

【特許請求の範囲】
1. 【請求項１】２次元の等間隔格子状に並べられたｎ×ｎ
   個の等サイズの部品のうち、同時にｍ個以上（ｍ≧３）
   をとり出し、その全ての組み合わせであるｍの階乗通り
   の配置交換に対し、部品相互間の最短配線長の総和を評
   価関数として評価関数値を求め、配置交換以前の評価関
   数値に比べ、配置交換後の評価関数値が小さくなる場合
   にのみ、その配置交換を施す操作を繰り返し行うことに
   より、評価関数を最小に近づけ、前記ｍの階乗通りの評
   価関数の計算処理を並列に実行して電子部品の配置改良
   を行うことを特徴とする等サイズブロックレイアウト方
   法。