JPH06332983A

JPH06332983A - 部品配置最適化方法

Info

Publication number: JPH06332983A
Application number: JP5139842A
Authority: JP
Inventors: Masanobu Takahashi; 正信高橋; Kazuo Hisama; 和生久間
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1993-05-20
Filing date: 1993-05-20
Publication date: 1994-12-02
Also published as: US5600555A

Abstract

(57)【要約】【目的】より評価関数値の小さな部品配置を高速に求
めることができる部品配置最適化方法を得る。【構成】部品を均一な大きさのブロックまたはブロッ
クの集合に仮想的に変換して、複数のブロックまたはブ
ロックの集合の置き換えを行うことにより、総配線長な
どの評価関数値がなるべく小さくなるようにブロックの
配置を改善して、そのブロックの配置をもとに部品の配
置を決定し、また、前記ブロックの配置を改善する方法
としては、各部に期待位置座標を割り当て、評価関数値
が小さくなる位置にくるように期待位置座標を更新しな
がら、期待位置座標に近いブロック配置位置のそのブロ
ックを配置する方法などを用いる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、総配線長などの何ら
かの評価基準のもとに、最適な部品配置を決定する部品
配置最適化方法に関するものである。

【０００２】

【従来の技術】図１０は例えば、メルビン・ブルーア
編、池田敏雄校閲、林孝雄訳「ディジタル計算機の自動
設計」（産業図書コンピュータ・サイエンス翻訳選書
／３昭和４８年１０月２９日初版発行）の第２５９頁
に示された、従来の部品配置最適化方法を示すフローチ
ャートであり、図１１は部品の最適配置と非最適配置の
一例を示す説明図、図１２は図１０に示されたペア交換
法による部品配置最適化方法において交換可能な部品を
説明するための概念図である。図１１において、１はこ
の部品配置最適化方法によって配置される部品であり、
３は各部品１の相互を接続する実際の配線である。ま
た、図１２において、１ａ，１ｂ，・・・，１ｊは図１
１にて符号１を付したものと同等の部品である。

【０００３】次に動作について説明する。ここでは、評
価基準として例えば総配線長を用いて最適な部品配置を
決定する場合について説明する。例題として、部品を配
置する位置と、次の表１に示されるような４つの部品間
の配線本数が与えられた場合に、配線の総延長が最短と
なるような部品配置を見つける問題を考える。

【０００４】

【表１】

【０００５】この問題の最適解の例を図１１（ａ）に示
し、配線の総延長がそれより長い非最適解の例を図１１
（ｂ）に示す。ここで、このような最適な部品配置を見
つける問題には解析的な解法が存在せず、最適解を見つ
けるためには、一般にすべての配置を調べる必要があ
る。しかしながら、部品数をＮとした場合にはその部品
配置の組合せはＮ！通り存在し、最適解を見つけるため
の計算にかかる時間は部品数Ｎの増加とともに爆発的に
増大する。すなわち、この最適な部品配置を見つける問
題は組合せ最適化問題の一種であり、従って、通常この
問題を解くに当っては最適解に近い解（近似解）を高速
に見つけることを目的とする。

【０００６】図１０はこのような部品配置最適化方法の
最も基本的なアルゴリズムであるペア交換法を示すフロ
ーチャートである。なお、この部品配置最適化方法はも
ともと、すべての部品の大きさがほぼ等しく、すべての
部品が他のすべての部品と配置位置を交換可能な場合に
ついてのものであるが、ここではより一般的に、大きさ
の異なる部品を含む問題を扱えるように改良した部品配
置最適化方法について説明する。

【０００７】処理がスタートするとまず、部品の初期配
置を行う（ステップＳＴ１）。この部品の初期配置はラ
ンダムに決めてもよいし、ペアリンキング法、あるいは
クラスタ成長法、あるいは重心法などの方法で、ある程
度総配線長が短くなるように決めてもよい。なお、部品
配置位置の数が部品総数よりも多い場合は、部品が配置
されていない空き領域ができるが、そこには他のどの部
品とも配線を持たないダミーの部品をとりあえず配置す
ることにする。そして、最終的に部品配置が決定したあ
とで、ダミー部品のある場所を空き領域とする。次に、
１回のサイクルを始める（ステップＳＴ２）。次に、１
回のサイクルでまだ選ばれていない部品から１つの部品
Ｂ_i を選択する（ステップＳＴ３）。ここで、Ｂの添え
字ｉは部品の番号とする。ただし、ダミー部品は選ばな
い。次に、選択された部品Ｂ_i と配置位置を交換した場
合に最も総配線長が短くなる部品の集合｛Ｂ_j ｝を、部
品Ｂ_i と交換可能な部品の集合（ダミー部品を含んでも
よい）から求める（ステップＳＴ４）。

【０００８】ここで、部品Ｂ_i と交換可能な部品の集合
について図１２を用いて説明する。今、選択された部品
Ｂ_i を部品１ａとすると、図１２（ａ）の場合は部品１
ｄと１ｆの組、および部品１ｄと１ｅの組、および部品
１ｇと１ｆの組が部品１ａと交換可能な部品の集合であ
る。一方、図１２（ｂ）の場合には交換可能な部品の集
合が無い。図１２（ｃ）の場合にも、部品１ｉは部品１
ａと大きさは同じであるが、形状が異なるため交換がで
きず、交換可能な部品の集合が無い。このように、組み
合わせた場合に大きさと形状が同じになる部品の集合
が、交換可能な部品の集合である。

【０００９】次に、部品Ｂ_i と部品の集合｛Ｂ_j ｝の配
置位置を交換した場合に、交換しない場合に比べて総配
線長が短くなるかどうかを判定する（ステップＳＴ
５）。その結果、短くなる場合には部品Ｂ_i と部品の集
合｛Ｂ_j ｝の配置位置を交換し（ステップＳＴ６）、短
くならない場合にはこのステップＳＴ４９をスキップし
て部品Ｂ_i と部品の集合｛Ｂ_j ｝との交換は行わない。
次に、１回のサイクルですべての部品が選択されたかど
うかを判定する（ステップＳＴ７）。その結果、選択さ
れていなければステップＳＴ３に戻り、ダミー部品以外
の残りの部品から次の部品を選択する。一方、選択され
た場合には、１回のサイクルによる総配線長の低減率
が、あらかじめ決められた値より小さいかどうかを判定
する（ステップＳＴ８）。もし低減率が大きい場合に
は、まだ改善の余地が大きいため、ステップＳＴ２へ戻
って次のサイクルを開始する。また、低減率があらかじ
め決められた値よりも小さければそこで終了し、最終的
に総配線長が低減された部品配置を得る。

【００１０】なお、従来の部品配置最適化方法として
は、この他にも緩和法、緩和法とペア交換法を組み合わ
せた方法（力の方向によるペア単位の緩和法）などがあ
るが、これらの手法も基本的には２つまたはそれ以上の
部品および部品の集合の交換、あるいは置き換えという
ステップを含んでいる。

【００１１】

【発明が解決しようとする課題】従来の部品配置最適化
方法は以上のように構成されているので、部品の大きさ
や特に形状の種類が多くなるほど、選択された部品に対
して交換可能な部品の集合の数が減少し、その結果とし
て部品を交換できる可能性が減少するため、総配線長な
どの評価関数値を大幅に低減できなくなり、さらに、熟
練者が時間をかけて決定したものに近い良好な配置結果
を得にくいなどの問題点があった。

【００１２】この発明は上記のような問題点を解消する
ためになされたもので、部品の大きさや形状の種類が増
えても総配線長などの評価関数値が小さい良好な部品配
置を行うことのできる部品配置最適化方法を得ることを
目的とする。

【００１３】

【課題を解決するための手段】請求項１に記載の発明に
係る部品配置最適化方法は、部品をその大きさが均一な
ブロックまたはブロックの集合に仮想的に変換し、その
ブロックの配置を、評価関数値がなるべく小さくなるよ
うに決定し、決定されたブロックの位置をもとに部品の
配置位置を決定するものである。

【００１４】また、請求項２に記載の発明に係る部品配
置最適化方法は、請求項１における部品の仮想的な変換
の方式を、ブロックまたはブロックの集合の大きさの比
が整数となるように変換するものに変更したものであ
る。

【００１５】また、請求項３に記載の発明に係る部品配
置最適化方法は、各部品に期待位置座標を割り当てて、
評価関数値がなるべく小さくなるような位置にくるよう
にその期待位置座標を更新しながら、期待位置座標に近
い部品配置位置にその部品を配置するようにしたもので
ある。

【００１６】また、請求項４に記載の発明に係る部品配
置最適化方法は、部品をその大きさが均一なブロックに
仮想的に変換した後、各ブロックに期待位置座標を割り
当てて、評価関数値がなるべく小さくなるような位置に
くるようにその期待位置座標を更新しながら、期待位置
座標に近いブロック配置位置にそのブロックを配置する
ようにし、最終的に決定されたブロック配置をもとに部
品の配置位置を決定するものである。

【００１７】また、請求項５に記載の発明に係る部品配
置最適化方法は、請求項４における部品の仮想的な変換
の方式を、ブロックの大きさの比が整数となるように変
換するように変更したものである。

【００１８】また、請求項６に記載の発明に係る部品配
置最適化方法は、請求項１あるいは２におけるブロック
の配置の決定を、複数のブロックまたはブロックの集合
を置き換えることによって行うものである。

【００１９】また、請求項７に記載の発明に係る部品配
置最適化方法は、請求項１，２または４，５におけるブ
ロック配置からの部品の配置位置の決定を、１つの部品
が変換されたブロックの集合とその部品の重なり具合、
および総配線長を考慮して行うものである。

【００２０】

【作用】請求項１に記載の発明における部品配置最適化
方法は、部品を均一な大きさのブロックまたはブロック
の集合に変換した状態で、評価関数値がなるべく小さく
なるように決定したブロックの位置をもとに、部品の配
置位置を決定することにより、交換できる部品の候補を
増大させて、評価関数値のより小さな部品配置を得るこ
とを可能とする。

【００２１】また、請求項２に記載の発明における部品
配置最適化方法は、ブロックまたはブロックの集合の大
きさの比が整数になるように変換することにより、部品
を仮想的にブロックまたはブロックの集合に変換する。

【００２２】また、請求項３に記載の発明における部品
配置最適化方法は、各部品に割り当てた期待位置座標を
評価関数値がなるべく小さくなるように更新しながら、
その期待位置座標に近い部品配置位置にその部品を配置
することにより、評価関数値のより小さな部品配置を高
速に得ることを可能とする。

【００２３】また、請求項４に記載の発明における部品
配置最適化方法は、部品を均一な大きさのブロックに変
換した後、上記と同様の処理を行い、最終的に決定され
たブロック配置をもとに部品の配置位置を決定すること
により、評価関数値のより小さな部品配置を高速に得る
ことを可能とする。

【００２４】また、請求項５に記載の発明における部品
配置最適化方法は、ブロックの大きさの比が整数になる
ように変換することにより、部品を仮想的にブロックに
変換する。

【００２５】また、請求項６に記載の発明における部品
配置最適化方法は、複数のブロックまたはブロックの集
合の置き換えによって、ブロックの配置を決定する。

【００２６】また、請求項７に記載の発明における部品
配置最適化方法は、１つの部品が変換されたブロックの
集合とその部品の重なり具合や総配線長を考慮して、決
定されたブロックの配置から部品の配置位置を決定す
る。

【００２７】

【実施例】

実施例１．以下、この発明の実施例１を図について説明
する。図１はこの発明による部品配置最適化方法の一実
施例のアルゴリズムを示すフローチャートであり、図２
は部品をブロックの集合に変換する方法の一例を示す概
念図、図３は交換可能なブロック集合を示す概念図であ
る。図２において、１ａ，１ｂは部品であり、２ａ〜２
ｅはこの部品１ａあるいは１ｂから分割されたブロック
である。このブロック２ａ〜２ｅは通常正方形をしてお
り、あらかじめ決められた均一の大きさを持っている。
また、図３において、２ａ〜２ｌは前述のブロックであ
り、同じ部品から分割されたブロックは同じテクスチャ
で示されている。

【００２８】次に動作について説明する。処理がスター
トするとまず、図２に示されるように、部品１ａ，１ｂ
を均一な大きさのブロック２ａ，２ｂの集合、または２
ｃ〜２ｅの集合に仮想的に変換する（ステップＳＴ１
１）。その時、部品１ａ，１ｂは図２に示すように、そ
の部品１ａ，１ｂより大きなブロックの集合に変換され
る。なお、総配線長を計算する際、配線は部品の中心か
らあるものとして計算するが、ブロックの集合に変換し
た場合は、１つの代表ブロックから配線があるとする
か、ブロックの集合の重心位置から配線があるとして計
算する。

【００２９】次に、ブロック配置位置の設定を行う（ス
テップＳＴ１２）。ブロック配置位置は通常、部品を配
置する領域内に等間隔の配列状に設定する。ブロック配
置位置の間隔はブロックの一辺の長さに等しくする。次
に、ブロック２ａ〜２ｅの数がブロック配置位置の数と
等しくなるように、他のブロックと配線を持たないダミ
ーのブロックを導入し（ステップＳＴ１３）、その後、
ブロックを初期配置する（ステップＳＴ１４）。ブロッ
クを配置する際、同じ部品から変換されたブロックは、
元の部品の形状を保つ必要はないが、お互いに少なくと
も１つのブロックと接するように配置する。この条件が
満たされる限り、ブロックの初期配置位置はランダムに
決めてもよいし、ペアリンキング法、あるいはクラスタ
成長法、あるいは重心法などの方法で、ある程度総配線
長が短くなるように決めてもよい。

【００３０】次に１回のサイクルを始める（ステップＳ
Ｔ１５）。次に、この１回のサイクルでまだ選ばれてい
ないブロックから同じ１つの部品から変換されたブロッ
クの集合（以下ではブロック集合と呼ぶ）｛Ｂ_i ｝を選
択する（ステップＳＴ１６）。ここで、Ｂの添字ｉはブ
ロックの番号とする。ただし、ダミーブロックは選ばな
い。次に、選択されたブロック集合｛Ｂ_i ｝と交換可能
なブロック集合（ダミーブロックを含んでもよい）か
ら、配置位置を交換した場合に最も総配線長が短くなる
ブロック集合｛Ｂ_j ｝を求める（ステップＳＴ１７）。

【００３１】ここで、ブロック集合｛Ｂ_i ｝と交換可能
なブロック集合について説明する。ブロック集合｛Ｂ
_i ｝と交換可能なブロック集合とは、ブロック集合｛Ｂ
_i ｝と同じ数のブロックを含み、かつその集合内の１つ
のブロックは同じ集合内の少なくとも１つの他のブロッ
クと接し、かつ１つの部品から変換されたブロックはす
べてその集合内に含まれるようなブロック集合である。
図３において、選択されたブロック集合｛Ｂ_i ｝を｛２
ａ，２ｂ，２ｃ｝とすると、交換可能なブロック集合
は、｛２ｄ，２ｅ，２ｆ｝または｛２ｇ，２ｈ，２ｌ｝
または｛２ｉ，２ｊ，２ｋ｝の３種類となる。また、
｛２ｅ，２ｆ｝を選択されたブロック集合｛Ｂ_i ｝とす
ると、交換可能なブロック集合は｛２ｇ，２ｈ｝の１種
類だけである。このように、組み合わせた場合に大きさ
が同じになり、かつ同じ部品から変換されたブロックを
すべて含み、かつ孤立したブロックがないブロックの集
合が交換可能なブロックの集合である。

【００３２】次に、ブロック集合｛Ｂ_i ｝とブロック集
合｛Ｂ_j ｝の配置位置を交換した場合に、交換しない場
合に比べて総配線長が短くなるかどうかを判定する（ス
テップＳＴ１８）。その結果、総配線長が短くなる場合
には、ブロック集合｛Ｂ_i ｝とブロック集合｛Ｂ_j ｝の
配置位置を交換し（ステップＳＴ１９）、短くならない
場合にはこのステップＳＴ１９をスキップしてブロック
集合｛Ｂ_i ｝とブロック集合｛Ｂ_j ｝の交換は行わな
い。この時、同じ部品から変換されたブロックはお互い
に少なくとも１つのブロックと接するように配置する。

【００３３】次に、１回のサイクルでダミーブロック以
外のすべてのブロックが選択されたかどうかを判定する
（ステップＳＴ２０）。選択されていない場合、ステッ
プＳＴ１６に戻り、ダミーブロック以外の残りのブロッ
クから次のブロック集合を選ぶ。また、すべてが選択さ
れた場合には、１回のサイクルによる総配線長の低減率
が、あらかじめ決められた値より小さいかどうかを判定
する（ステップＳＴ２１）。その結果、もし低減率が大
きい場合には、まだ改善の余地が大きいため、ステップ
ＳＴ１５へ戻って次のサイクルを開始する。一方、低減
率があらかじめ決められた値より小さければ、そのブロ
ックの配置位置をもとに部品の配置位置を決定して終了
する（ステップＳＴ２２）。

【００３４】ここで、ブロックの配置位置をもとに部品
の配置位置を決定する際、同じ部品から変換されたブロ
ック集合の形状は、元の部品の形状と同じとは限らな
い。形状が同じ場合は、そこに部品が配置されていない
限り、ブロック集合のある場所へ元の部品をそのまま配
置すればよい。また、形状が異なる場合には、例えばそ
の部品から変換されたブロック集合と最も重なりが大き
くなり、かつ既に配置されている部品と重ならない位置
へ部品を配置する。もし、部品が配置されているために
重なりがまったく無い場合には、ブロック集合のなるべ
く近くに部品を配置する。なお、配置位置を決定する順
番は、サイズの大きな部品からとする。以上のステップ
により、最終的に総配線長の短い（準）最適配置が得ら
れる。

【００３５】実施例２．なお、上記実施例１では、配置
の評価基準として総配線長を用いた場合について説明し
たが、評価基準としては、評価できる限り任意の評価基
準、およびその組み合わせを用いることができる。その
場合、それらの評価基準において配置が最適に近づくほ
ど値が小さくなるように評価関数を設定し、その評価関
数値を総配線長の代わりに用いればよい。

【００３６】実施例３．また、上記実施例１では、２つ
のブロックまたはブロック集合を交換する手法、すなわ
ちペア交換法を用いて総配線長が短くなるように配置を
改善したが、２つまたは複数のブロック集合を交換また
は置き換える手法であれば、緩和法など別の手法を用い
てもよく、同様に最適化することができる。

【００３７】実施例４．また、上記実施例１では、ブロ
ック集合の中に孤立したブロックがないことをブロック
集合が交換できる条件としているが、ブロックがお互い
に近くにある限りは交換可能なブロック集合としてもよ
く、その場合も同様に最適化できる。

【００３８】実施例５．また、上記実施例１では、すべ
ての部品の配置位置はあらかじめ決まっていなかった
が、あらかじめ配置位置の決まっている部品、すなわち
固定部品がある場合でも、固定部品の配置位置を部品配
置領域並びに部品配置位置から除外し、常に固定部品を
配置しておくことにより、固定部品を含めて同様に最適
化することができる。

【００３９】実施例６．また、上記実施例１では、ステ
ップＳＴ２２において、ブロック集合との重なりを考慮
して部品配置位置を決定したが、重なりと共に総配線長
を考慮して部品配置位置を決定するようにしてもよい。

【００４０】実施例７．また、上記実施例１では、ステ
ップＳＴ２２において、配置位置を決定する順番を、サ
イズの大きな部品からとしていたが、部品配置領域の中
心に近い部品からとするなど、他の順番を用いてもよ
い。

【００４１】実施例８．また、上記実施例１では、ステ
ップＳＴ２２において、ブロックの配置位置をもとに部
品の配置位置を決定する過程を１度だけ行っていたが、
この過程を何度も繰り返し、その中で最良の部品配置を
最終的な部品配置とするようにしてもよい。

【００４２】実施例９．また、上記実施例では、ブロッ
クの大きさを均一としたが、ブロックの大きさの比が整
数倍であってもよい。

【００４３】実施例１０．次に、この発明の実施例１０
を図について説明する。図４はこの発明による部品配置
最適化方法の他の実施例のアルゴリズムを示すフローチ
ャートであり、図５は仮想配線の導入の方法を示す概念
図、図６はブロック配置位置の一例を示す説明図であ
る。図５において、１ａ，１ｂは部品、２ａ〜２ｃはブ
ロック、３ａ，３ｂは実際の配線（以下、実配線とい
う）で、以前に説明したそれらと同等のものであり、４
ａ〜４ｃはブロック２ｂと２ｃあるいはブロック２ａと
２ｂの間の仮想的な配線（以下、仮想配線という）であ
る。また、図６において、５ａ〜５ｉは１つ１つのブロ
ックが置かれる中心位置を示すブロック配置位置で、○
中の数字は位置番号を表しており、各々の座標は、Ｘ_i
＝（Ｘ_i1，Ｘ_i2）［ｉ＝１〜Ｎ、Ｎはブロック配置位置
の総数］で与えられる。

【００４４】次に動作について説明する。処理がスター
トするとまず、部品が大きさの均一なブロックの集合に
仮想的に変換される（ステップＳＴ３１）。この変換
は、図２に示した実施例１で説明した場合と同様に行わ
れる。次に、そのブロック間に仮想配線を導入する（ス
テップＳＴ３２）。この仮想配線をどのように決めるか
を図５を用いて以下に説明する。

【００４５】この図５では、部品１ａはブロック２ａ，
２ｂに変換され、部品１ｂはブロック２ｃに変換されて
いる。１つの部品から変換されたブロックのうち１つの
ブロックを主ブロック、残りのブロックを副ブロックと
呼ぶ。図５の場合、２ａ，２ｃが主ブロック、２ｂは副
ブロックである。図５に示されるように、元々部品１
ａ，１ｂ間にあった実配線３ａ，３ｂは、それらの部品
がブロックに変換された際は、主ブロック間の配線（図
の場合２ａ，２ｃ間の配線）になる。そして、主ブロッ
ク間に実配線がある場合は、主ブロックと相手の副ブロ
ック間にも同じ本数の仮想配線を仮定する。図５の場合
は主ブロック２ａ，２ｃ間に２本の実配線があるため、
主ブロック２ｃと相手の副ブロック２ｂ間にも２本の仮
想配線４ａ，４ｂを仮定する。また、同じ部品から変換
されたブロック間にも仮想配線を仮定する。図５の場
合、ブロック２ａ，２ｂは同じ部品１ａから変換された
ブロックであるため、その間に仮想配線４ｃを仮定す
る。なお、同じ部品から変換されたブロック間の仮想配
線の本数は変数であり、問題により最適化する。

【００４６】次に、ブロック配置位置を設定する（ステ
ップＳＴ３３）。このブロック配置位置は通常、図６に
示すように部品を配置する領域内に等間隔の配列状に設
定し、各ブロック配置位置５ａ〜５ｉの間隔はブロック
の一辺の長さに等しくする。図６はブロック数９個の場
合のブロック配置位置の一例を示している。次に、ブロ
ック数がブロック配置位置の数と等しくなるように、他
のブロックと配線を持たないダミーのブロックを導入す
る（ステップＳＴ２４）。従って、ブロックの総数は、
ブロック配置位置の総数と同じＮとなる。次に、各ブロ
ックに１つずつ、ブロック配置位置の座標と同じ次元の
ベクトルを割り当てる（ステップＳＴ３５）。ここで
は、このベクトルを期待位置座標と呼び、Ｗ_i ＝
（Ｗ_i1，Ｗ_i2）［ｉ＝１〜Ｎ］と表す。

【００４７】次に、その期待位置座標Ｗ_i を、部品を配
置する領域内の適当な乱数で初期化し（ステップＳＴ３
６）、その後、サイクル数Ｔを０に設定する（ステップ
ＳＴ３７）。次に、１回のサイクル中で選ばれていない
ブロック配置位置からランダムに１つのブロック配置位
置Ｓを選ぶ（ステップＳＴ３８）。そして、選ばれたブ
ロック配置位置Ｓの位置座標Ｘ_s に最も近い期待位置座
標Ｗ_i を持つブロック（これを最適ブロックと呼ぶ）
を、１回のサイクル中でまだ選ばれていないブロックか
ら選ぶ（ステップＳＴ３９）。これを式で表すと、最適
ブロックの番号ｂは次の（１）式で与えられる。

【００４８】

【数１】

【００４９】ここで、Ｕは１回のサイクル中でまだ選ば
れていないブロックの番号の集合である。例えば、ブロ
ック配置位置Ｓに対する最適ブロックとしてｂ番目のブ
ロックが選ばれた場合、そのサイクル中ではｂ番目のブ
ロックがブロック配置位置Ｓに配置されることを意味す
る。次に、拘束条件を考慮して、すべてのブロックの期
待位置座標に、次の（２）式および（３）式で与えられ
る更新量を加えて更新する（ステップＳＴ４０）。

【００５０】

【数２】

【００５１】

【数３】

【００５２】ここで、εは期待位置座標更新係数と呼ば
れる定数で、通常は１以下に設定される。また、ｆ
（ｉ，ｂ）はｉ番目のブロックが最適ブロックのとき１
となり、それ以外の時はａ×ｈ_ibとなる。ここで、ａは
配線係数と呼ばれる定数であり、ｈ_ibはｉ番目とｂ番目
のブロックの間の配線本数である。なお、配線本数ｈ_ib
は実配線だけでなく、仮想配線も含めた配線本数であ
る。また、ａ×ｈ_ibの上限は１であり、１以上の時には
１にする。

【００５３】次に、１回の学習サイクルにおいてすべて
のブロック配置位置が選ばれたか否かを判定し（ステッ
プＳＴ４１）、選ばれていない場合には、ふたたびブロ
ック配置位置の選択（ステップＳＴ３８）に戻る。一
方、すべてのブロック配置位置が選ばれていれば、決定
されたブロック配置に対する実配線の総配線長Ｌを求め
る（ステップＳＴ４２）。この総配線長Ｌは、例えば図
６に示されるようなブロック配置位置の場合、２つのブ
ロック配置位置の水平方向（Ｘ₁ 方向）と垂直方向（Ｘ
₂ 方向）の距離の和として計算する。次に、それまでの
サイクルで得られた最小の総配線長Ｌ_min と求めたＬを
比較する（ステップＳＴ４３）。比較の結果、ＬがＬ
_min よりも小さければ、このサイクルにおいて求まった
新しいブロック配置をそれまでのサイクルで最適の配置
として記憶し、Ｌを最小の総配線長としてＬ_min に代入
する（ステップＳＴ４４）。一方、ＬがＬ_min 以上の場
合にはこのステップＳＴ４４をスキップして当該処理を
行わない。ここまでが１回のサイクルであり、次にサイ
クル数Ｔに１を加える（ステップＳＴ４５）。

【００５４】次に、サイクル数Ｔとあらかじめ決められ
た最大サイクル数Ｔ_max を比較する（ステップＳＴ４
６）。ＴがＴ_max に達していなければ再びステップＳＴ
３８より次のサイクルを開始する。また、ＴがＴ_max に
達した場合には、最終的に最適配置として記憶したブロ
ック配置をもとの部品の配置位置を決定して終了する
（ステップＳＴ４７）。部品の配置位置を決定する際
は、例えば実施例１のステップＳＴ２２でも説明したよ
うに、サイズの大きな部品から順番に、その部品から変
換されたブロック集合との重なり具合や総配線長を考慮
して、既に配置されている部品と重ならない位置へ部品
を配置してゆく。以上のステップにより、最終的に総配
線長の短い（準）最適配置が得られる。

【００５５】次に、上記実施例１０の有効性を示すた
め、従来の部品配置最適化方法の１つである緩和法と、
上記実施例１０による部品配置最適化方法とを計算機シ
ミュレーションにて比較した結果を示す。ここで、前記
緩和法とは、部品間の配線をゴムひものような力線と考
え、力線によってその部品に働く力がつりあう位置に近
い部品配置位置に部品を配置する方法である。比較に用
いた問題は、同じ大きさの部品１００個を、１０×１０
の格子点上に配置する問題で、すべての部品間には確率
０．５で配線が存在するものと仮定した。

【００５６】計算機シミュレーションを行った結果を図
７に示す。図７は計算時間を等しくした場合に得られる
部品配置の総配線長のヒストグラムである。すなわち、
横軸は格子点の間隔を１とした時の総配線長で、縦軸は
総配線長を５０ごとに区切った場合に、総配線長がその
範囲内に収まる部品配置が得られる確率である。使用し
た計算機は、ＳＵＮ／ＳＰＡＲＣ３３０ワークステーシ
ョンで、１回の最適化に要する時間は２分とした。ま
た、シミュレーションは各方法について１０００回ずつ
行った。図７に示されるように、緩和法では、ランダム
な配置に比べて若干総配線長の短い部品配置が得られる
が、実施例１０による方法では、ランダムな配置および
緩和法に比べても大幅に総配線長の短い部品配置が得ら
れることがわかる。総配線長の平均は、ランダム配置が
１６３９５であるのに対して、緩和法では１６１５４、
実施例１０の方法では１４７８０であった。

【００５７】実施例１１．なお、上記実施例１０では、
ステップＳＴ３８におけるブロック配置位置の選択手順
をランダムにしたものを示したが、何らかの基準に従っ
て選択順序を決めてもよい。

【００５８】実施例１２．また、上記実施例１０では、
パラメータεおよびａが学習中はある値に固定されてい
るものとしたが、学習中に変更してもよく、さらに、パ
ラメータａの値として、実配線と仮想配線の別の値を用
いるようにしてもよい。

【００５９】実施例１３．また、上記実施例１０では、
総配線長をなるべく小さくすることだけを目的としてい
たが、例えば配線が混まないようにしたり、特定の部品
を近づけたり離したりするなど、他の条件を含んだ上で
配置最適化を行うことも可能である。そのためには、例
えば（１）式にこれらの条件を反映する項を導入し、ス
テップＳＴ２１において最適ブロックを選択する時にこ
れらの条件を満たすようにブロックを選択すればよい。

【００６０】実施例１４．また、上記実施例１０では、
すべての部品の配置位置はあらかじめ決まっていなかっ
たが、あらかじめ配置位置の決まっている部品、すなわ
ち固定部品がある場合でも、固定部品の配置位置を部品
配置領域ならびにブロック配置位置から除外し、常に固
定部品を配置しておくことにより、固定部品を含めて同
様に最適化することができる。

【００６１】実施例１５．また、上記実施例１０では、
ステップＳＴ４７において、配置位置を決定する順番
を、サイズの大きな部品からとしていたが、部品配置領
域の中心に近い部品からとするなど、他の順番を用いて
もよい。

【００６２】実施例１６．また、上記実施例１０では、
ステップＳＴ４７において、ブロックの配置位置をもと
に部品の配置位置を決定する過程を１度だけ行っていた
が、この過程を何度も繰り返し、その中で最良の部品配
置を最終的な部品配置とするようにしてもよい。

【００６３】実施例１７．また、上記実施例１０は前述
の実施例１と組み合わせてもよい。すなわち、部品をブ
ロックに変換後、実施例１０と実施例１による方法でブ
ロック配置を最適化し、ブロック配置をもとに部品配置
を決定してもよい。

【００６４】実施例１８．次に、この発明の実施例１８
を図について説明する。図８はこの発明による部品配置
最適化方法を実行する計算機システムの一例を示すブロ
ック図である。図において、６はオペレータからの指示
などが入力されるキーボードであり、７は処理結果など
が表示されるディスプレイである。８は当該システムの
中央処理装置（以下、ＣＰＵという）であり、９はＣＰ
Ｕ８が処理動作の過程でデータ類の記憶に用いるメモリ
である。１０はＣＰＵ８に外部接続されたハードディス
クであり、このハードディスク１０には、オペレーティ
ングシステム（ＯＳ）の他、データファイルとしての部
品サイズデータ、部品配置領域データ、部品間の配線本
数データ、ブロックサイズ等のパラメータデータ、部品
配置位置データ、さらにはプログラムなどがあらかじめ
格納されている。

【００６５】次に動作について説明する。ここで、図９
はその動作のアルゴリズムを示すフローチャートであ
る。まず、キーボード６よりプログラム名を入力するこ
とにより、ハードディスク１０より該当するプログラム
がメモリ９にロードされ、プログラムの実行が開始され
（ステップＳＴ５１）、以下、そのプログラムに従って
処理が進行する。次に、ハードディスク１０に格納され
ている部品サイズデータ、部品配置領域データ、配線本
数データ、パラメータデータなどの他のデータがメモリ
９にロードされる（ステップＳＴ５２）。次に、パラメ
ータデータの１つであるブロックサイズのデータと部品
サイズデータをもとに、個々の部品を幾つのブロックに
どのように変換するかをＣＰＵ８によって計算し、個々
のブロックに１から順番に番号を付して、ブロックの総
数データと共に結果をメモリ８に格納する（ステップＳ
Ｔ５３）。部品は実施例１のステップＳＴ１１において
説明したように、全体がその部品よりも大きくなるブロ
ック集合に変換する。

【００６６】次に、部品配置領域データとブロックサイ
ズのデータをもとに、ＣＰＵ８によってブロック配置位
置座標を計算し、個々のブロック配置位置に１から順番
に番号をつけて、結果をメモリ９に格納する（ステップ
ＳＴ５４）。ブロック配置位置は通常、部品を配置する
領域内に等間隔の配列状に設定する。ブロック配置位置
の間隔はブロックのサイズ（ブロックの１辺の長さ）に
等しくする。次に、ブロック配置位置の総数よりブロッ
ク数を引いた値をＣＰＵ８により計算し、その値をダミ
ーブロック数としてメモリ９に格納する（ステップＳＴ
５５）。なお、そのダミーブロックにもステップＳＴ２
７において各ブロックにつけたブロック番号の最大値＋
１から順番に番号を付す。ここで、このダミーブロック
は他のどのブロックとも配線を持たない。

【００６７】次に、ブロックを初期配置する（ステップ
ＳＴ５６）。すなわち、個々のブロックについて、その
ブロックを配置するブロック配置位置番号をＣＰＵ８を
用いて決定し、結果をメモリ９に格納する。ブロックを
配置する際、同じ部品から変換されたブロックは、元の
部品の形状を保つ必要はないが、お互いに少なくとも１
つのブロックと接するように配置する。この条件が満た
される限り、ブロックの初期配置位置はランダムに決め
てもよいし、ペアリンキング法、あるいはクラスタ成長
法、あるいは重心法などの方法で、ある程度総配線長が
短くなるように決めてもよい。その後、１回のサイクル
を開始し（ステップＳＴ５７）、次いで部品のブロック
への変換データなどをもとに、ＣＰＵ８を用いて、１回
のサイクルでまだ選ばれていないブロックから同じ１つ
の部品から変換されたブロック集合｛Ｂ_i ｝の選択を行
う（ステップＳＴ５８）。ここで、Ｂの添え字ｉはブロ
ックの番号とする。ただし、ダミーブロックの選択は行
わない。

【００６８】次に、部品のブロックへの変換データ、配
線本数データ、部品配置位置座標データ、ブロック配置
位置番号データなどをもとに、ＣＰＵ８を用いて、選択
されたブロック集合｛Ｂ_i ｝と交換可能なブロック集合
（この場合にはダミーブロックを含んでもよい）から、
配置位置を交換した場合に最も総配線長が短くなるブロ
ック集合｛Ｂ_j ｝を求める（ステップＳＴ５９）。ここ
で、交換可能なブロック集合とは、実施例１のステップ
ＳＴ１７において説明したのと同様に、ブロック集合
｛Ｂ_i ｝と同じ数のブロックを含み、かつ同じ部品から
変換されたブロックをすべて含み、かつ孤立したブロッ
クがないブロックの集合である。

【００６９】次に、ブロック集合｛Ｂ_i ｝とブロック集
合｛Ｂ_j ｝の配置位置を交換した場合に、交換しない場
合に比べて総配線長が短くなるかどうかをＣＰＵ８を用
いて判定する（ステップＳＴ６０）。もし判定の結果、
短くなる場合には、ブロック集合｛Ｂ_i ｝とブロック集
合｛Ｂ_j ｝の配置位置を交換し（ステップＳＴ６１）、
短くならない場合にはこのステップＳＴ６１をスキップ
して、ブロック集合｛Ｂ_i ｝とブロック集合｛Ｂ_j ｝の
交換は行わない。ここで、ブロックの配置位置を交換す
るとは、ブロック配置位置番号データにおいて、対応す
るブロックの配置位置番号を入れ換えることを意味す
る。この時、同じ部品から変換されたブロックは、配置
位置交換後もお互いに少なくとも１つのブロックと接す
るように配置位置を決定する。

【００７０】次に、１回のサイクルでダミーブロック以
外のすべてのブロックが選択されたかどうかをＣＰＵ８
によって判定する（ステップＳＴ６２）。その結果、選
択されていない場合には、ステップＳＴ５８に戻って、
ダミーブロック以外の残りのブロックから次のブロック
集合を選ぶ。一方、すべてのブロックが選択されていれ
ば、１回のサイクルによる総配線長の低減率をＣＰＵ８
を用いて計算し、その値があらかじめ決められた値より
小さいかどうかをＣＰＵ８によって判定する（ステップ
ＳＴ６３）。もし低減率が大きければまだ改善の余地が
大きいため、ステップＳＴ５７へ戻って次のサイクルを
開始する。また、低減率があらかじめ決められた値より
小さい場合には、ブロック配置位置番号データ、部品の
ブロックへの変換データなどをもとに、ＣＰＵ８を用い
て部品の配置位置を決定し、結果をハードディスク１０
にセーブして終了する（ステップＳＴ６４）。

【００７１】なお、この部品の配置位置は、ブロックの
最終的な配置位置をもとに決定する。同じ部品から変換
されたブロック集合の形状が元の部品の形状と同じ場合
は、そこに部品が配置されていない限り、ブロック集合
のある位置をそのまま部品の配置位置とする。また元の
部品の形状と異なる場合には、例えばその部品から変換
されたブロック集合と最も重なりが大きくなり、かつ既
に配置されている部品と重ならない位置を部品の配置位
置とする。もし、部品が配置されているために重なりが
まったくない場合には、ブロック集合のなるべく近くを
部品の配置位置とする。なお、配置位置を決定してゆく
順番は、サイズの大きな部品からとする。以上のステッ
プにより、最終的に、総配線長の短い（準）最適配置が
得られる。

【００７２】実施例１９．なお、上記実施例１８では、
配置の評価基準として総配線長を用いた場合について説
明したが、評価基準としては、評価できる限り任意の評
価基準、およびその組み合わせを用いることができる。
その場合、それらの評価基準において配置が最適に近づ
くほど値が小さくなるように評価関数を設定し、その評
価関数値を総配線長の代わりに用いればよい。

【００７３】実施例２０．また、上記実施例１８では、
２つのブロックまたはブロック集合を交換する手法、す
なわちペア交換法を用いて総配線長が短くなるように配
置を改善したが、２つまたは複数のブロック集合を交換
または置き換える手法であれば、緩和法など別の手法を
用いてもよく、同様に最適化することができる。

【００７４】実施例２１．また、上記実施例１８では、
ブロック集合の中に孤立したブロックがないことをブロ
ック集合の配置位置を交換できる条件としているが、ブ
ロックがお互いに近くにある限りは交換可能なブロック
集合としてもよく、その場合も同様に最適化できる。

【００７５】実施例２２．また、上記実施例１８では、
すべての部品の配置位置はあらかじめ決まっていなかっ
たが、あらかじめ配置位置の決まっている部品、すなわ
ち固定部品がある場合でも、固定部品の配置位置を部品
配置領域並びに部品配置位置から除外し、常に固定部品
を配置しておくことにより、固定部品を含めて同様に最
適化することができる。

【００７６】実施例２３．また、上記実施例１８では、
ステップＳＴ６４において、ブロック集合との重なりを
考慮して部品配置位置を決定したが、重なりと共に総配
線長を考慮して部品配置位置を決定するようにしてもよ
い。

【００７７】実施例２４．また、上記実施例１８では、
ステップＳＴ６４において、配置位置を決める順番をサ
イズの大きな部品からとしていたが、部品配置領域の中
心に近い部品からとするなど、他の順番を用いてもよ
い。

【００７８】実施例２５．また、上記実施例１８では、
ステップＳＴ６４において、部品の配置位置を決定する
過程を１度だけ行っていたが、この過程を部品の配置位
置が決定していない状態から何度も繰り返し、その中で
最良の部品配置を最終的な部品配置とするようにしても
よい。

【００７９】実施例２６．また、上記実施例１８では、
ブロックの大きさを均一としたが、ブロックの大きさの
比が整数倍であってもよい。

【００８０】実施例２７．また、上記実施例１８は、図
１に示された実施例１による部品配置最適化方法を計算
機システムを用いて実現したものについて示したが、図
４に示された実施例１０をはじめとする他の部品配置最
適化方法を適用してもよく、それを上記の実施例１８と
同様にして計算機システムを用いて実現することによ
り、部品配置を最適化するための装置が得られる。

【００８１】

【発明の効果】以上のように、請求項１に記載の発明に
よれば、部品を均一な大きさのブロックまたはブロック
の集合に仮想的に変換した後、評価関数値がなるべく小
さくなるようにそのブロックの配置を決定し、決定され
たブロックの位置をもとに部品の配置位置を決定するよ
うに構成したので、ある部品に対してそれとは形状の異
なる部品についても、部品または部品の集合の大きさが
同一であれば交換可能となり、交換できる部品または部
品の候補が大幅に増加して、結果的に総配線長などの評
価関数値がより小さな部品配置が得られる効果がある。

【００８２】また、請求項２に記載の発明によれば、部
品をその大きさの比が整数となるブロックまたはブロッ
クの集合に仮想的に変換するように構成したので、交換
できる部品または部品の候補をさらに増やすことができ
る効果がある。

【００８３】また、請求項３に記載の発明によれば、評
価関数値がなるべく小さくなるような位置にくるよう
に、各部品に割り当てた期待位置座標を更新しながら、
期待位置座標に近い部品配置位置にその部品を配置する
ように構成したので、総配線長などの評価関数値がより
小さな部品配置を、より高速に求めることができる効果
がある。

【００８４】また、請求項４に記載の発明によれば、部
品をその大きさが均一なブロックに仮想的に変換した
後、上記と同様の処理を実行し、最終的に決定されたブ
ロック配置をもとに部品の配置位置を決定するように構
成したので、総配線長などの評価関数値がより小さな部
品配置を、より高速に求めることができる効果がある。

【００８５】また、請求項５に記載の発明によれば、部
品をその大きさの比が整数になるブロックに仮想的に変
換するように構成したので、交換できる部品または部品
の候補をさらに増やすこともできる効果がある。

【００８６】また、請求項６に記載の発明によれば、複
数のブロックまたはブロックの集合を置き換えることに
よってブロックの配置を決めるように構成したので、ブ
ロックの配置の決定の処理が容易となる効果がある。

【００８７】また、請求項７に記載の発明によれば、１
つの部品が変換されたブロックの集合とその部品の重な
り具合、および総配線長を考慮して、ブロック配置から
部品の配置位置を決めるように構成したので、ブロック
配置からの部品の配置位置の決定の処理が容易となる効
果がある。

【図面の簡単な説明】

【図１】この発明の実施例１による部品配置最適化方法
のアルゴリズムを示すフローチャートである。

【図２】上記実施例にて部品をブロックへ変換する方法
の一例を示す概念図である。

【図３】上記実施例における交換可能なブロック集合を
示す概念図である。

【図４】この発明の実施例１０による部品配置最適化方
法のアルゴリズムを示すフローチャートである。

【図５】上記実施例における仮想配線の導入方法を示す
概念図である。

【図６】上記実施例におけるブロック配置位置の一例を
示す説明図である。

【図７】上記実施例による部品配置最適化方法と従来の
緩和法の性能を計算機シミュレーションにより比較した
結果を示す説明図である。

【図８】この発明の実施例１８による部品配置最適化方
法を実現する計算機システムの構成を示すブロック図で
ある。

【図９】上記実施例の動作のアルゴリズムを示すフロー
チャートである。

【図１０】従来の部品配置最適化方法を示すフローチャ
ートである。

【図１１】部品の最適配置と非最適配置の一例を示す説
明図である。

【図１２】従来の部品配置最適化方法における交換可能
な部品を説明するための概念図である。

【符号の説明】

１，１ａ〜１ｊ部品２ａ〜２ｌブロック３，３ａ，３ｂ実際の配線（実配線）４ａ〜４ｃ仮想的な配線（仮想配線）５ａ〜５ｉブロック配置位置

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成５年９月２９日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】特許請求の範囲

【補正方法】変更

【補正内容】

【特許請求の範囲】

【手続補正２】

【補正対象書類名】明細書

【補正対象項目名】発明の詳細な説明

【補正方法】変更

【補正内容】

【発明の詳細な説明】

【０００１】

【０００２】

【０００４】

【表１】

【００１１】

【００１３】

【００１９】また、請求項７に記載の発明に係る部品配
置最適化方法は、請求項１，２または４，５，６におけ
るブロック配置からの部品の配置位置の決定を、１つの
部品が変換されたブロックの集合とその部品の重なり具
合、および評価関数値を考慮して行うものである。

【００２０】

【００２６】また、請求項７に記載の発明における部品
配置最適化方法は、１つの部品が変換されたブロックの
集合とその部品の重なり具合や評価関数値を考慮して、
決定されたブロックの配置から部品の配置位置を決定す
る。

【００２７】

【実施例】実施例１．以下、この発明の実施例１を図について説明
する。図１はこの発明による部品配置最適化方法の一実
施例のアルゴリズムを示すフローチャートであり、図２
は部品をブロックの集合に変換する方法の一例を示す概
念図、図３は交換可能なブロック集合を示す概念図であ
る。図２において、１ａ，１ｂは部品であり、２ａ〜２
ｅはこの部品１ａあるいは１ｂから分割されたブロック
である。このブロック２ａ〜２ｅは通常正方形をしてお
り、あらかじめ決められた均一の大きさを持っている。
また、図３において、２ａ〜２ｌは前述のブロックであ
り、同じ部品から分割されたブロックは同じテクスチャ
で示されている。

【００３９】実施例６．また、上記実施例１では、ステ
ップＳＴ２２において、ブロック集合との重なりを考慮
して部品配置位置を決定したが、重なりと共に総配線長
などの評価関数値を考慮して部品配置位置を決定するよ
うにしてもよい。

【００４８】

【数１】

【００５０】

【数２】

【００５１】

【数３】

【００６４】実施例１８．また、上記実施例１０では、
（２）式で用いられる関数ｆ（ｉ，ｂ）を（３）式のよ
うに定義しているが、ｆ（ｉ，ｂ）は（３）式に限られ
ず、他の関数を用いてもよい。たとえば、次式（４）に
示すように、他の部品を介しての影響を考慮するように
してもよい。次式（４）においてａ₁ は定数である。

【００６５】

【数４】

【００６６】実施例１９．次に、この発明の実施例１９
を図について説明する。図８はこの発明による部品配置
最適化方法を実行する計算機システムの一例を示すブロ
ック図である。図において、６はオペレータからの指示
などが入力されるキーボードであり、７は処理結果など
が表示されるディスプレイである。８は当該システムの
中央処理装置（以下、ＣＰＵという）であり、９はＣＰ
Ｕ８が処理動作の過程でデータ類の記憶に用いるメモリ
である。１０はＣＰＵ８に外部接続されたハードディス
クであり、このハードディスク１０には、オペレーティ
ングシステム（ＯＳ）の他、データファイルとしての部
品サイズデータ、部品配置領域データ、部品間の配線本
数データ、ブロックサイズ等のパラメータデータ、部品
配置位置データ、さらにはプログラムなどがあらかじめ
格納されている。

【００６７】次に動作について説明する。ここで、図９
はその動作のアルゴリズムを示すフローチャートであ
る。まず、キーボード６よりプログラム名を入力するこ
とにより、ハードディスク１０より該当するプログラム
がメモリ９にロードされ、プログラムの実行が開始され
（ステップＳＴ５１）、以下、そのプログラムに従って
処理が進行する。次に、ハードディスク１０に格納され
ている部品サイズデータ、部品配置領域データ、配線本
数データ、パラメータデータなどの他のデータがメモリ
９にロードされる（ステップＳＴ５２）。次に、パラメ
ータデータの１つであるブロックサイズのデータと部品
サイズデータをもとに、個々の部品を幾つのブロックに
どのように変換するかをＣＰＵ８によって計算し、個々
のブロックに１から順番に番号を付して、ブロックの総
数データと共に結果をメモリ８に格納する（ステップＳ
Ｔ５３）。部品は実施例１のステップＳＴ１１において
説明したように、全体がその部品よりも大きくなるブロ
ック集合に変換する。

【００６８】次に、部品配置領域データとブロックサイ
ズのデータをもとに、ＣＰＵ８によってブロック配置位
置座標を計算し、個々のブロック配置位置に１から順番
に番号をつけて、結果をメモリ９に格納する（ステップ
ＳＴ５４）。ブロック配置位置は通常、部品を配置する
領域内に等間隔の配列状に設定する。ブロック配置位置
の間隔はブロックのサイズ（ブロックの１辺の長さ）に
等しくする。次に、ブロック配置位置の総数よりブロッ
ク数を引いた値をＣＰＵ８により計算し、その値をダミ
ーブロック数としてメモリ９に格納する（ステップＳＴ
５５）。なお、そのダミーブロックにもステップＳＴ２
７において各ブロックにつけたブロック番号の最大値＋
１から順番に番号を付す。ここで、このダミーブロック
は他のどのブロックとも配線を持たない。

【００６９】次に、ブロックを初期配置する（ステップ
ＳＴ５６）。すなわち、個々のブロックについて、その
ブロックを配置するブロック配置位置番号をＣＰＵ８を
用いて決定し、結果をメモリ９に格納する。ブロックを
配置する際、同じ部品から変換されたブロックは、元の
部品の形状を保つ必要はないが、お互いに少なくとも１
つのブロックと接するように配置する。この条件が満た
される限り、ブロックの初期配置位置はランダムに決め
てもよいし、ペアリンキング法、あるいはクラスタ成長
法、あるいは重心法などの方法で、ある程度総配線長が
短くなるように決めてもよい。その後、１回のサイクル
を開始し（ステップＳＴ５７）、次いで部品のブロック
への変換データなどをもとに、ＣＰＵ８を用いて、１回
のサイクルでまだ選ばれていないブロックから同じ１つ
の部品から変換されたブロック集合｛Ｂ_i ｝の選択を行
う（ステップＳＴ５８）。ここで、Ｂの添え字ｉはブロ
ックの番号とする。ただし、ダミーブロックの選択は行
わない。

【００７０】次に、部品のブロックへの変換データ、配
線本数データ、部品配置位置座標データ、ブロック配置
位置番号データなどをもとに、ＣＰＵ８を用いて、選択
されたブロック集合｛Ｂ_i ｝と交換可能なブロック集合
（この場合にはダミーブロックを含んでもよい）から、
配置位置を交換した場合に最も総配線長が短くなるブロ
ック集合｛Ｂ_j ｝を求める（ステップＳＴ５９）。ここ
で、交換可能なブロック集合とは、実施例１のステップ
ＳＴ１７において説明したのと同様に、ブロック集合
｛Ｂ_i ｝と同じ数のブロックを含み、かつ同じ部品から
変換されたブロックをすべて含み、かつ孤立したブロッ
クがないブロックの集合である。

【００７１】次に、ブロック集合｛Ｂ_i ｝とブロック集
合｛Ｂ_j ｝の配置位置を交換した場合に、交換しない場
合に比べて総配線長が短くなるかどうかをＣＰＵ８を用
いて判定する（ステップＳＴ６０）。もし判定の結果、
短くなる場合には、ブロック集合｛Ｂ_i ｝とブロック集
合｛Ｂ_j ｝の配置位置を交換し（ステップＳＴ６１）、
短くならない場合にはこのステップＳＴ６１をスキップ
して、ブロック集合｛Ｂ_i ｝とブロック集合｛Ｂ_j ｝の
交換は行わない。ここで、ブロックの配置位置を交換す
るとは、ブロック配置位置番号データにおいて、対応す
るブロックの配置位置番号を入れ換えることを意味す
る。この時、同じ部品から変換されたブロックは、配置
位置交換後もお互いに少なくとも１つのブロックと接す
るように配置位置を決定する。

【００７２】次に、１回のサイクルでダミーブロック以
外のすべてのブロックが選択されたかどうかをＣＰＵ８
によって判定する（ステップＳＴ６２）。その結果、選
択されていない場合には、ステップＳＴ５８に戻って、
ダミーブロック以外の残りのブロックから次のブロック
集合を選ぶ。一方、すべてのブロックが選択されていれ
ば、１回のサイクルによる総配線長の低減率をＣＰＵ８
を用いて計算し、その値があらかじめ決められた値より
小さいかどうかをＣＰＵ８によって判定する（ステップ
ＳＴ６３）。もし低減率が大きければまだ改善の余地が
大きいため、ステップＳＴ５７へ戻って次のサイクルを
開始する。また、低減率があらかじめ決められた値より
小さい場合には、ブロック配置位置番号データ、部品の
ブロックへの変換データなどをもとに、ＣＰＵ８を用い
て部品の配置位置を決定し、結果をハードディスク１０
にセーブして終了する（ステップＳＴ６４）。

【００７３】なお、この部品の配置位置は、ブロックの
最終的な配置位置をもとに決定する。同じ部品から変換
されたブロック集合の形状が元の部品の形状と同じ場合
は、そこに部品が配置されていない限り、ブロック集合
のある位置をそのまま部品の配置位置とする。また元の
部品の形状と異なる場合には、例えばその部品から変換
されたブロック集合と最も重なりが大きくなり、かつ既
に配置されている部品と重ならない位置を部品の配置位
置とする。もし、部品が配置されているために重なりが
まったくない場合には、ブロック集合のなるべく近くを
部品の配置位置とする。なお、配置位置を決定してゆく
順番は、サイズの大きな部品からとする。以上のステッ
プにより、最終的に、総配線長の短い（準）最適配置が
得られる。

【００７４】実施例２０．なお、上記実施例１９では、
配置の評価基準として総配線長を用いた場合について説
明したが、評価基準としては、評価できる限り任意の評
価基準、およびその組み合わせを用いることができる。
その場合、それらの評価基準において配置が最適に近づ
くほど値が小さくなるように評価関数を設定し、その評
価関数値を総配線長の代わりに用いればよい。

【００７５】実施例２１．また、上記実施例１９では、
２つのブロックまたはブロック集合を交換する手法、す
なわちペア交換法を用いて総配線長が短くなるように配
置を改善したが、２つまたは複数のブロック集合を交換
または置き換える手法であれば、緩和法など別の手法を
用いてもよく、同様に最適化することができる。

【００７６】実施例２２．また、上記実施例１９では、
ブロック集合の中に孤立したブロックがないことをブロ
ック集合の配置位置を交換できる条件としているが、ブ
ロックがお互いに近くにある限りは交換可能なブロック
集合としてもよく、その場合も同様に最適化できる。

【００７７】実施例２３．また、上記実施例１９では、
すべての部品の配置位置はあらかじめ決まっていなかっ
たが、あらかじめ配置位置の決まっている部品、すなわ
ち固定部品がある場合でも、固定部品の配置位置を部品
配置領域並びに部品配置位置から除外し、常に固定部品
を配置しておくことにより、固定部品を含めて同様に最
適化することができる。

【００７８】実施例２４．また、上記実施例１９では、
ステップＳＴ６４において、ブロック集合との重なりを
考慮して部品配置位置を決定したが、重なりと共に総配
線長を考慮して部品配置位置を決定するようにしてもよ
い。

【００７９】実施例２５．また、上記実施例１９では、
ステップＳＴ６４において、配置位置を決める順番をサ
イズの大きな部品からとしていたが、部品配置領域の中
心に近い部品からとするなど、他の順番を用いてもよ
い。

【００８０】実施例２６．また、上記実施例１９では、
ステップＳＴ６４において、部品の配置位置を決定する
過程を１度だけ行っていたが、この過程を部品の配置位
置が決定していない状態から何度も繰り返し、その中で
最良の部品配置を最終的な部品配置とするようにしても
よい。

【００８１】実施例２７．また、上記実施例１９では、
ブロックの大きさを均一としたが、ブロックの大きさの
比が整数倍であってもよい。

【００８２】実施例２８．また、上記実施例１９は、図
１に示された実施例１による部品配置最適化方法を計算
機システムを用いて実現したものについて示したが、図
４に示された実施例１０をはじめとする他の部品配置最
適化方法を適用してもよく、それを上記の実施例１８と
同様にして計算機システムを用いて実現することによ
り、部品配置を最適化するための装置が得られる。

【００８３】

【００８４】また、請求項２に記載の発明によれば、部
品をその大きさの比が整数となるブロックまたはブロッ
クの集合に仮想的に変換するように構成したので、交換
できる部品または部品の候補をさらに増やすことができ
る効果がある。

【００８５】また、請求項３に記載の発明によれば、評
価関数値がなるべく小さくなるような位置にくるよう
に、各部品に割り当てた期待位置座標を更新しながら、
期待位置座標に近い部品配置位置にその部品を配置する
ように構成したので、総配線長などの評価関数値がより
小さな部品配置を、より高速に求めることができる効果
がある。

【００８６】また、請求項４に記載の発明によれば、部
品をその大きさが均一なブロックに仮想的に変換した
後、上記と同様の処理を実行し、最終的に決定されたブ
ロック配置をもとに部品の配置位置を決定するように構
成したので、総配線長などの評価関数値がより小さな部
品配置を、より高速に求めることができる効果がある。

【００８７】また、請求項５に記載の発明によれば、部
品をその大きさの比が整数になるブロックに仮想的に変
換するように構成したので、交換できる部品または部品
の候補をさらに増やすこともできる効果がある。

【００８８】また、請求項６に記載の発明によれば、複
数のブロックまたはブロックの集合を置き換えることに
よってブロックの配置を決めるように構成したので、ブ
ロックの配置の決定の処理が容易となる効果がある。

【００８９】また、請求項７に記載の発明によれば、１
つの部品が変換されたブロックの集合とその部品の重な
り具合、および評価関数値を考慮して、ブロック配置か
ら部品の配置位置を決めるように構成したので、ブロッ
ク配置からの部品の配置位置の決定の処理が容易となる
効果がある。

Claims

【特許請求の範囲】

【請求項１】配置する部品を、その大きさが均一なブ
ロックまたはブロックの集合に仮想的に変換する変換手
順と、前記変換手順にて前記ブロックまたはブロックの
集合に変換した状態で、評価関数値をより小さくするよ
うに前記ブロックの配置を決定するブロック配置手順
と、前記ブロック配置手順にて決定された前記ブロック
の配置をもとに、前記部品の配置を決定する部品配置手
順とを含んだ部品配置最適化方法。
【請求項２】配置する部品を、その大きさの比が整数
となるブロックまたはブロックの集合に仮想的に変換す
る変換手順と、前記変換手順にて前記ブロックまたはブ
ロックの集合に変換した状態で、評価関数値をより小さ
くするように前記ブロックの配置を決定するブロック配
置手順と、前記ブロック配置手順にて決定された前記ブ
ロックの配置をもとに、前記部品の配置を決定する部品
配置手順とを含んだ部品配置最適化方法。
【請求項３】部品を配置すべき部品配置位置の設定を
行う部品配置位置設定手順と、部品数が前記部品配置位
置設定手順にて設定された部品配置位置の数と等しくな
るように、他の部品と配線を持たないダミーの部品を導
入するダミー導入手順と、前記部品配置位置の座標と同
じ次元の期待位置座標ベクトルを前記各部品上に割り当
てる期待位置座標割当手順と、前記部品配置位置より、
まだ選択されていない部品配置位置を１つ選択する部品
配置位置選択手順と、前記部品配置位置選択手順によっ
て選ばれた部品配置位置に対して最もコスト関数値が小
さな最適部品を、まだ選択されていない前記部品より１
つ選択する最適部品選択手順と、前記最適部品選択手順
にて選択された最適部品を、前記部品配置位置選択手順
にて選択された部品配置位置に配置することに決定する
配置決定手順と、前記最適部品の期待位置座標を、前記
部品配置位置選択手順にて選択された部品配置位置に近
づける座標調整手順と、前記最適部品以外の部品の期待
位置座標を拘束条件に従って更新する座標更新手順と、
前記部品すべての部品配置位置が選択されるまで前記部
品配置位置選択手順から前記座標更新手順までの処理を
繰り返し、すべての前記部品の配置を決定する配置決定
手順と、前記配置決定手順を１回または複数回繰り返し
て、そのうちで評価関数値が最も小さな配置を最終的な
部品配置として決定する最終決定手順とを含んだ部品配
置最適化方法。
【請求項４】配置する部品を、その大きさが均一なブ
ロックに仮想的に変換する変換手順と、同一の前記部品
より変換された前記ブロックの間に、実際の配線とは別
に仮想的な配線を仮定する仮想配線仮定手順と、前記ブ
ロックを配置すべきブロック配置位置の設定を行うブロ
ック配置位置設定手順と、ブロック数が前記ブロック配
置位置設定手順にて設定されたブロック配置位置の数と
等しくなるように、他のブロックと配線を持たないダミ
ーのブロックを導入するダミー導入手順と、前記ブロッ
ク配置位置の座標と同じ次元の期待位置座標ベクトルを
前記各ブロック上に割り当てる期待位置座標割当手順
と、前記ブロック配置位置より、まだ選択されていない
ブロック配置位置を１つ選択するブロック配置位置選択
手順と、前記ブロック配置位置選択手順によって選ばれ
たブロック配置位置に対して最もコスト関数値が小さな
最適ブロックを、まだ選択されていない前記ブロックよ
り１つ選択する最適ブロック選択手順と、前記最適ブロ
ック選択手順にて選択された最適ブロックを、前記ブロ
ック配置位置選択手順にて選択されたブロック配置位置
に配置することに決定する配置決定手順と、前記最適ブ
ロックの期待位置座標を、前記ブロック配置位置選択手
順にて選択されたブロック配置位置に近づける座標調整
手順と、前記最適ブロック以外のブロックの期待位置座
標を拘束条件に従って更新する座標更新手順と、前記ブ
ロックすべてのブロック配置位置が選択されるまで前記
ブロック配置位置選択手順から前記座標更新手順までの
処理を繰り返し、すべての前記ブロックの配置を決定す
る配置決定手順と、前記配置決定手順を１回または複数
回繰り返して、そのうちで評価関数値が最も小さな配置
を最終的なブロック配置として決定するブロック配置手
順と、前記ブロック配置手順にて決定された前記ブロッ
クの配置をもとに、前記部品の配置を決定する部品配置
手順とを含んだ部品配置最適化方法。
【請求項５】配置する部品を、その大きさの比が整数
となるブロックに仮想的に変換する変換手順と、同一の
前記部品より変換された前記ブロックの間に、実際の配
線とは別に仮想的な配線を仮定する仮想配線仮定手順
と、前記ブロックを配置すべきブロック配置位置の設定
を行うブロック配置位置設定手順と、ブロック数が前記
ブロック配置位置設定手順にて設定されたブロック配置
位置の数と等しくなるように、他のブロックと配線を持
たないダミーのブロックを導入するダミー導入手順と、
前記ブロック配置位置の座標と同じ次元の期待位置座標
ベクトルを前記各ブロック上に割り当てる期待位置座標
割当手順と、前記ブロック配置位置より、まだ選択され
ていないブロック配置位置を１つ選択するブロック配置
位置選択手順と、前記ブロック配置位置選択手順によっ
て選ばれたブロック配置位置に対して最もコスト関数値
が小さな最適ブロックを、まだ選択されていない前記ブ
ロックより１つ選択する最適ブロック選択手順と、前記
最適ブロック選択手順にて選択された最適ブロックを、
前記ブロック配置位置選択手順にて選択されたブロック
配置位置に配置することに決定する配置決定手順と、前
記最適ブロックの期待位置座標を、前記ブロック配置位
置選択手順にて選択されたブロック配置位置に近づける
座標調整手順と、前記最適ブロック以外のブロックの期
待位置座標を拘束条件に従って更新する座標更新手順
と、前記ブロックすべてのブロック配置位置が選択され
るまで前記ブロック配置位置選択手順から前記座標更新
手順までの処理を繰り返し、すべての前記ブロックの配
置を決定する配置決定手順と、前記配置決定手順を１回
または複数回繰り返して、そのうちで評価関数値が最も
小さな配置を最終的なブロック配置として決定するブロ
ック配置手順と、前記ブロック配置手順にて決定された
前記ブロックの配置をもとに、前記部品の配置を決定す
る部品配置手順とを含んだ部品配置最適化方法。
【請求項６】前記ブロック配置手順が、複数の前記ブ
ロックまたはブロックの集合を置き換えることによっ
て、前記評価関数値をより小さくするように前記ブロッ
クの配置を決定するものであることを特徴とする請求項
１または２に記載の部品配置最適化方法。
【請求項７】前記部品配置手順が、１つの前記部品は
変換された前記ブロックの集合とその部品との重なり具
合、および総配線長を考慮して前記部品の配置を決定す
るものであることを特徴とする請求項１、２、４または
５のいずれか１項に記載の部品配置最適化方法。