JPH01209574A

JPH01209574A - 配置改良方式

Info

Publication number: JPH01209574A
Application number: JP63034777A
Authority: JP
Inventors: Yoshihiro Fujita; 藤田　善弘
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1988-02-17
Filing date: 1988-02-17
Publication date: 1989-08-23
Anticipated expiration: 2013-08-06
Also published as: JP2782716B2

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】（産業上の利用分野）本発明は、設計支援装置に関し、特に電気回路を実装す
るプリント板やＬＳＩ内部における、ＩＣやトランジス
タの配置を決定するための、配置改良方式に関する。

（従来の技術）　　− 従来、与えられた配置を改良する方法としては、例えば
ベア交換法がある。この方法は、全ての部品の中から、
適当な２つの部品を取り出し、その置き換えを考え、仮
想的な配線長（例えば、マンハッタン長）による評価値
が良くなるなら置き換えを受は入れ、良くならないなら
置き換えないという処理を繰り返し行うものである。

この方法では、１度に２つの部品しか交換しないので、
ある時点における配置が最適な配置ではないのにもかか
わらず、どの２つの部品の交換を考えてもそれ以上良い
配置は見つからないという、局所最適解に陥り易い。

この局所最適解に陥りにくくするためには、例ぇば４つ
の部品を同時に置き換えることを考えて、その置き換え
方の４！通り、すなわち２４通りをすべて評価して、最
も良い置き換え方を選択するという方法がとられていた
。４つの部品の交換は２つの部品の交換を含んでいるの
で、ペア交換法よりも必ず良い解が期待できる。

（発明が解決しようとする課題）このような方法によると、より良い解を得ることが出来
るが、やはり局所最適解に陥ることは避けられず、さら
に局所最適解に陥りにくくするためには、より多くの部
品を同時に置き換えることを考えて、その全ての置き換
え方を評価して、最も良い置き換え方を選択する方法が
有効である。

しかし、同時に交換する部品数ｎを増やして行くと、そ
の評価に要する計算量はｎ！に比例して増大してしまい
、同時に交換する部品数ｎを増やすのは実用的に困難で
あった。

（課題を解決するための手段）前述の課題を解決するために本発明が提供する手段は、
複数の部品を同時に交換して、その全ての置き換え方を
評価し、かつ全ての配線に対する仮想的な配線長の合計
を配置の評価に用いることにより、すでに配置された複
数の部品の配置状態を逐次改良し、配線ネットによって
相互に接続された部品群を、決められた領域内でより良
く配置する配置改良方式であって、同時に交換する部品
として互いに配線ネットによって接続されていない部品
群を選ぶ手段と、前記置き換え方を評価するときに、そ
れぞれの部品の、新しい置き場所毎の評価値を独立に計
算し、たし合わせることによって、全体の評価値を得る
手段とを備えることを特徴とする。

（作用）同時に交換する部品群を選ぶときに、互いに接続関係に
ある部品を選んでしまうと、１つの部品を他の場所に動
かしたときの評価値の変化は、その部品と接続関係にあ
る部品をどの場所に置いたかによって変わってしまう。

従って、ｎ個の部品の置き換えを考えたとき、その置き
換え方ｎ！通りの各々について、部品を置き換えた後に
評価値を計算しなければならない。

しかし、互いに接続関係にない部品を選ぶことにより、
各々の部品を動かしたときの評価値の変化を他の部品の
動かし方とは独立に計算することかできる。

従って、ｎ個の部品の置き換えを考えたとき、ｎ個の部
品それぞれについてｎケ所に置いたときの評価値を独立
に求めればよいので、個々の部品の評価値の計算はｎ２
回で済む。

個々の部品の評価値の計算後、それを足し合１〕せる時
には０１通りの計算をしなければならないが、それは単
なるｎ個の評価値の加算であるので、０１通りの評価値
をいちいち計算する従来の方法と比較すると、全体とし
て計算量を大幅に減らすことが出来る。

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

第１図は、本発明の一実施例である配置改良装置の構成
を示すブロック図である。

第１図の実施例は、ホスト・プロセッサ１１と、接続リ
スト・メモリ１２と、配置状態メモリ１３と、終了条件
判定回路１４と、交換候補作成回路１５と、評価関数表
作成回路１６と、評価関数計算回路１７と、評価結果比
較回路１８と、配置状態更新回路１９とから構成されて
いる。

本実施例では、各々数本の配線で他の部品と接続されて
いる部品群を、すでに配置しである状態から、４個の部
品を同時に置き換えることを繰り返すことによって配置
を改良していく方法について述べる。

第２図は、各々数本の配線で他の部品と接続されている
部品群を、すでに配置しである状態の一例である。第２
図において、四角形は部品であり、線分は部品と部品を
接続する仮想的な配線である。

このように、すでにある状態に配置されている部品群の
配置を改良するのであるが、その配置の評価には第３図
に示すような仮想的な配線長を用いる。第３図において
、部品３１と部品３２を結ぶ配線３３は、部品４つ分の
長きを持つので、仮想的な配線長は４である。

処理の概要を第４図に示す。まず、互いに接続されてい
ない４つの部品を選びだす。つぎに、それらの全ての置
き換え方を評価する。その結果、元の配置より良い配置
が見つかれば、そのように置き換える。この一連の処理
を繰り返し行うことによって、配置を改良する。

第１図は、このような処理を行う装置である。

第１図において、ホスト・プロセッサ１１は、配置改良
したい問題をロードし、処理結果をセーブする機能を持
つ、ホスト・プロセッサ１１は、初期配置の状態を配置
状態メモリ１３に、部品の接続情報を接続リスト・メモ
リ１２にロードし、処理の終了条件を終了条件判定回路
１４にセットした後、終了条件判定回路１４に対して起
動をかける。また、終了条件判定回路１４から処理が終
了したという信号がくると、配置状態メモリ１３から処
理結果を読み出す。

接続リスト・メモリ１２は、ホストからロードされた、
部品の接続情報を保持するメモリである。

配置状態メモリ１３は、部品の最新の配置状態を保持す
るメモリである。

終了条件判定回路１４は、ホスト・プロセッサによって
セットされた終了条件を満たすまで、配置状態更新回路
１９から１回の処理が終わるたびに送られてくる同期信
号を受は取った後に、交換候補作成回路１５に対して起
動信号を送る。

終了条件としては、例えば（１）交換試行回数が１万回
になるまで、（２）交換成立回数が１万回になるまで、
等の条件が考えられる。

また、終了条件を満足するとホスト・プロセッサに終了
を知らせる信号を送る。

交換候補作成回路１５は、終了条件判定回路１４から起
動信号を受は取るたびに、接続リスト・メモリを参照し
ながら、互いに接続されていない４つの部品を選び出し
、その部品番号を評価関数表作成回路１６へ送る。

交換候補作成回路１５における、互いに接続されていな
い４つの部品の選び出し方としては、次のような方法が
考えられる。

交換候補作成回路１５は、第５図に示すような表を内部
に持っている。表において、左の列は各部品を示し、右
の列はその部品を選んでもよいかどうかを示すチエツク
をするためのものである。

まず、部品を１つも選んでいない状態では、全てのチェ
ック欄に０を書き込んでおく。次に、チェック欄にＯが
書かれている部品の中から１つを選び、選んだ部品及び
、その部品に接続されている部品に対応するチェック欄
に１を書き込む。

そしてまた、チンツク欄にＯが書かれている部品を１つ
選ぶ、このような処理を、必要な個数の部品が選ばれる
まで続ければ良い。

評価関数表作成回路１６は、内部に評価関数表を持ち、
交換候補作成回路１５から４つの交換候補の部品番号を
受は取ると、接続リスト・メモリ１２および配置状態メ
モリ１３を参照しながら、各部品を各場所に置いたとき
の、評価関数を、評価関数表に記録する。評価関数とし
ては、ある部品をある場所に置いたとき、その部品に接
続されている全ての配線の仮想配線長の合計を用いる。

いま、評価関数表作成回路１６が、第６図に示すような
、Ａ、Ｂ、Ｃ，Ｄの４つの部品の交換を、交換候補作成
回路１５から指示されたとする。

現在それらの置いである場所をそれぞれａ。

ｂ、ｃ、ｄとする。

このとき、選ばれたＡ、Ｂ、Ｃ，Ｄの４個の部品は、互
いに配線によって接続されていない。

従って、部品Ａを場所ａ、ｂ、ｃ、ｄに置いたときの、
部品Ａにつながっている配線の仮想配線長は、部品Ｂ、
Ｃ，Ｄの配置とは無関係に求めることが出来る。この結
果、第７図に示す様な評価関数表をつくることが出来る
。

第６図において各空欄には、部品Ａ、Ｂ、Ｃ。

Ｄをそれぞれ場所ａ、ｂ、ｃ、ｄに置いたときの、各部
品に接続されている全ての配線の仮想配線長の合計を書
き込む。

評価関数表作成回路１６は評価関数表を完成すると、そ
の評価関数表を評価関数計算回路１７に送る。

評価関数計算回路１７は、評価関数表作成回路１６から
送られてきた評価値を受けとると、Ａ、Ｂ。

Ｃ，Ｄの４つの部品の置き換え方、２４通りのそれぞれ
に対する評価値を求める。第８図に、Ａ。

Ｂ、Ｃ，Ｄの４個の部品をａ、ｂ、ｃ、ｄの４ケ所に置
く全ての買き方を示す。第８図において、各行は、それ
ぞれ１通りの置き換え方を示し、Ａ、Ｂ、Ｃ，Ｄの４個
の部品をそれぞれどの場所に置くかを表している。２４
通りの評価値をもとめるには、第７図に示した評価関数
表の各行、各列から、選び方を順に変えながら１つずつ
選んでたし合わせればよい０例えば、第９図に示した選
び方は、Ａをす、Ｂをｄ、Ｃをａ、ＤをＣに置いたとき
の評価値を求めるときのものである。

評価関数計算回路１７は、評価値の計算を終えると、２
４個の評価結果を評価結果比較回路１８に送る。

評価結果比較回路１８は、評価関数計算回路１７から送
られてきた２４個の評価結果を比較し、どの置き換え方
が一番良いかを判定し、その結果を配置状態更新回路１
９に送る。

配置状態更新回路１９は、評価結果比較回路１８から送
られてきた結果および交換候補作成回路１５から送られ
てきた４つの部品番号をもとにして、評価値が改善きれ
るなら配置状態メモリ１３の配置を更新し、終了状態判
定回路１４に１回の処理が終わったことを知らせるため
の同期信号を、配置の更新を行ったかどうかという情報
と共に送る。

（発明の効果）以上述べた通り、本発明には、同時に交換する部品群を
選ぶときに、互いに接続関係にない部品を選ぶことによ
り、各々の部品を動かしたときの評価値の変化を他の部
品の動かし方とは独立に計算することができ、計算量を
大幅に減らすことが出来るという効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック図、第２図は
第１図実施例が対象とする問題の一例を示す図、第３図
は仮想配線長の説明図、第４図は第１図実施例の処理手
順を示すフローチャート、第５図は互いに接続されてい
ない部品を選ぶ方法の説明図、第６図は交換候補の一例
を示す図、第７ｒ！ｌＪは各部品を各場所に置いたとき
の、それぞれの部品ごとの評価値を記録するための評価
関数表の説明図、第８図は４つの部品の貧き換え方２４
通りを示す説明図、第９図は置き換え方の一例を示す図
である。１１・・・ホスト・プロセッサ、１２・・・接続リスト
−メモリ、１３・・・配置状態メモリ、１４・・・終了
条件判定回路、１５・・・交換候補作成回路、１６・・
・評価関数表作成回路、１７・・・評価関数計算回路、
１８・・・評価結果比較回路、１９・・・配置状態更新
回路、３１〜３２・・・部品、３３・・・仮想的な配線
。

Claims

【特許請求の範囲】複数の部品を同時に交換して、その全ての置き換え方を
評価し、かつ全ての配線に対する仮想的な配線長の合計
を配置の評価に用いることにより、すでに配置された複
数の部品の配置状態を逐次改良し、配線ネットによって
相互に接続された部品群を、決められた領域内でより良
く配置する配置改良方式において、同時に交換する部品として互いに配線ネットによって接
続されていない部品群を選ぶ手段と、前記置き換え方を
評価するときに、それぞれの部品の、新しい置き場所毎
の評価値を独立に計算し、たし合わせることによって、
全体の評価値を得る手段とを備えることを特徴とする配
線改良方式。