JPS6046828B2 - 配置決定装置 - Google Patents

Description

【発明の詳細な説明】 本発明は、配置決定装置、特にＬＳＩチップ上における
論理ゲートの配置やプリント回路基板上におけるＩＣの
配置などを、従来のソフトウェアによつて決定する方法
に比べて極めて短時間に決定する配置決定装置に関する
ものである。

ＬＳＩのレイアウト設計において、そのＬＳＩチップに
搭載すべき複数個の論理ゲートをどのような相対位置関
係で配置するか、あるいはまたＩＣプリント回路基板の
設計において、そのプリント基板に搭載すべき複数個の
ＩＣを基板上のどこに配・置するかを決定する設計過程
を、それぞれＬＳＩにおける配置設計、プリント基板に
おける配置設計と呼んでいる。

この配置設計はそれに引続いて行われる配線設計の成否
に大きな影響を与える。

すなわち、良い配置が与えられれば１００％の配線径路
がみつかる論理回路が得られるのに対して、悪い配置が
与えられると如何に配線設計で努力しても１００％の配
線径路が見つけられないことがしばしば起きる。したが
つて、配置設計はプリント基板やｕ■チップの設計にお
いて重要な設計過程となつている。この配置設計は人手
によつて行われる場合が多かつたが、最近では設計時間
の短縮、配置品質の向上、設計エラーの低減等をねらつ
て、計算機を利用してプログラムによつて決定されるこ
とが多くなつてきた。配置設計をソフトウェアで処理す
る場命、品質の良い配置を得るためには入れ換え改善法
（あるいは逐次改善法）と呼ばれる配置手法が用いられ
ることが多い。

この手法はある与えられた初期配置から出発して部品（
ＬＳ■の場合には論理ゲート、プリント基板の場合には
ＩＣ）をお互いに入れ換えることによつて徐々に配置を
改善していくものである。ある部品のベアを入れ換えた
ら配置が改善されるかどうかを判断する基準を配置の評
価基準という。この評価基準としては総配線長最小化と
呼ばれる基準が用いられる。

この基準はある配置を評価する場合、論理接続関係に従
つて部品間に仮に配線を引いてみてこれらの配線の長さ
の総和が短かければ良い配置であり長ければ悪い配置と
みなす評価基準である（ここで゜゜仮に配線する゛とい
うことは配線同士がショートするかどうかなどかまわす
配線を引くことを意味する。従つて全ての配線径路はそ
れぞれ最短に引かれる）。入れ換え改善法ではある規則
によつて選んだ部品のベアを仮に交換して、それらの部
品に関与している配線を引きなおしてみて、上記の総配
線長和が小さくな−ると判断すれば実際にその部品ベア
を入れ換え、小さくならなければ入れ換えを行わないと
いう操作を順次異なる部品ベアについて繰返すことによ
つて配置改善を行うのてある。第１図〜第３図を用いて
入れ換え改善法による，配置改善手順を詳しく説明する
。

第１図は初期配置の一例である。ここでは１帽の゛部品
を４×４のアレイ上に配置する場合を想定している。部
品間の線は仮の配線を表わし、この配線長の総和で配置
の良否を評価する。配線長は例えば部品６と１０の間は
“゜１゛、部品１と２の間はＸ方向に゜゛１゛、Ｙ方向
に“゜２゛で併わせて゜゜３゛の距離と考える。このよ
うな計算の仕方で第１図の総配線長和を計算すると゜゜
５４゛となる。この値を減少させるように配置換えを行
うのである。例えば第１図て部品６と１０を入れ換える
と第２図の配置が得られるが、このとき総配線長和ぱ“
４９゛となり配置改善が行われたことになる。このよう
な操作を異なる部品のベアについて繰返していくと第３
図のような配置が得られる（総配線長和＝・゜゜２５゛
）。この配置に到達するとこのあと如何なるベアを入れ
換えても配置改善が行われないのでこれが最終配置とな
る。ここで、部品のベアの選び方は全てのベアの組合せ
を考慮するとその組合せ数は厖大になるので、普通隣接
した部品同士が選ばれることが多い。しかし、たとえ、
隣接した部品ベアの組合せにしぼつても上記手法による
配置処理においては部品交換操作の数は取扱う部品数が
増えるとともに指数関数的に増大するので部品数が数１
００以上のものに対しては処理時間がきわめて厖大とな
り、このような手法の適用が禁止的となつている。ある
いはたとえ適用したとしてもきわめて不十分な配置結果
しか得られないのが現″状である。本発明は上記のよう
な配置処理を汎用計算機を用いてソフトウェアで行うか
わりに、その大半の処理をハードウェアで行うことによ
つて処理時間を短縮するようにした配置のための専用装
置を提供することを目的としている。

以下図面について詳細に説明する。第４図は本発明の実
施例を示し、図中の符号、２１はメモリユニット、２２
は演算ユニット、２３はデータ信号線、２４はコントロ
ール信号線、２５は多相クロック発生回路、２６，２７
，２８，２９は夫々クロック線である。

メモリユニット２１は複数語から成つており、データ信
号線２３およびコントロール信号線２４を介して演算ユ
ニット２２と接続されている。

演算ユニット２２は加減算、リードライトコントロール
、レジスタ機能等を有している。多相クロック発生回路
２５は４相のクロック信号を発生し、クロック線２６，
２７，２８，２９を介して演算ユニット２２にクロック
信号を供給する。以下第４図にもとずいて本装置の動作
を詳細に説明する。

本装置の動作は大きく分けて次の２つのフェイズに分か
れる。初期配置セットフェイズ、入れ換え改善フェイズ
である。以下順に説明する。（１）初期配置セットフェ
イズ。

このフェイズでは第４図の各メモリユニット２１に初期
配置の状態をセットする。

各メモリユニットに与えるべき情報はそのメモリユニッ
ト２１に割当てられた部品の番号とその部品が接続され
ている単一あるいは複数個の部品の番号と座標位置であ
る。第４図ではこれらの情報を各メモリユニット２１に
書込むためめ信号線等は図面が複雑になるので示してい
ないが、これは明らかに既知の方法で容易に実施できる
ので省略した。（２）入れ換え改善フェイズ。

このフェイズでは初期配置フェイズで与えられた配置か
ら出発して各演算ユニット２２でそれに隣接する上下あ
るいは左右の２つのメモリｂユニット２１の部品を入れ
換えたら配置が改善されるかどうかを計算し、その結果
にもとずいて入れ換えを実際に行つたり、行わなかつた
りする。

どの部品のベアについて入れ換え改善を調べるかは多相
クロック発生回路５によつて発１・生された４相のクロ
ック信号を各演算ユニット２２に供給することによつて
選択する。例えば、クロック線２６が′６ｒ５になつた
ときには演算ユニット２２のうちＰｌ，２，Ｐ３，２，
Ｐ，，２，Ｐ７啼２９Ｐ９ラ２およびＰ１？６９Ｐ３９
６９Ｐ５１６９Ｐ７１６９１Ｐ９，６が選択されたこと
になり、従つてメモリユニット２１のベア（Ｍｌ，ｌ，
Ｍｌ，３），（Ｍ３，ｌ，Ｍ３ｌ３）９（Ｍ５９ｌ９Ｍ
５９３）９（Ｍ７９ｌ９Ｍ７９３）９（Ｍ９９ｌ９Ｍ９
，３）および（Ｍｌ，５９Ｍｌ，７）９（Ｍ３，５９Ｍ
３，７）９（Ｍ５◆５９Ｍ５９７）９（Ｍ７ラ５９Ｍ７
９７）９（Ｍ９９５９Ｍ２９，７）が選択されたことに
なる。また、同様にしてクロック線２８が゜゜１゛にな
つたときにはメモリユニット１のベアとして（Ｍ３，ｌ
，Ｍ５，ｌ）９（Ｍ３，３９Ｍ５，３）９（Ｍ３，５ｆ
Ｍ５，５）９（Ｍ３，７９Ｍ５９７）９（Ｍお９９Ｍ５
ヤ９）および（Ｍ７９ｌ９Ｍ９？１）９２（Ｍ７，３９
Ｍ９，３）９（Ｍ７，５９Ｍ９，５）９（Ｍ７，７９Ｍ
９，７），（Ｍ７，９，Ｍ９，９）が選択されたことに
なる。このようにしてクロック線２６，２７，２８，２
９がそれぞれ時刻を異にして“゜１゛になれば全てのメ
モリユニット２１のベアが選択さ３れることになる。上
記のような方式で順番に指定されたメモリユニット２１
内の部品のベアに対して、入れ換えによる配置改善があ
るかどうかを判定し改善があれば入れ換え、なければ入
れ換えない。

３以下クロック線２６が゜“１゛の状態をとつたとき
を仮定して説明を行う。このとき（Ｍｌ，ｌ９Ｍｌ９３
）９（Ｍ３９ｌ９Ｍ３９３）９，（Ｍ９ラ５９Ｍ９９７
），がベアとして選択されたことになるが、このうち（
Ｍｌ，ｌ，Ｍｌ，３）のベアに着目する。ク演算ユニッ
トＰｌ，２によつてメモリユニットＭｌ，ｌとＭｌ，３
の内容を読み出しＭｌ，，中の部品とＭｌ，３中の部品
を入れ換えたと仮定したとき総配線長和が増えるか減る
かを計算し、減る場合にはＭｌ，，とＭｌ，３中の部品
番号およびそれに伴なう情報の入れ換えを行う。同じか
、増える場合には情報の入れ換えは行わない。このよう
な処理が選択された全てのベアについて行われる。その
結果、一つ以上のメモリユニットのベアについて部品の
入れ換えがあつた場合、その部品と接続関係をもつ部品
が格納されているメモリユニット２１中の位置情報を更
新する必要がある。従つて入れ換えのあつたメモリユニ
ットから部品番号と位置情報を読み出し、これに関与す
る部品が格納されているメモリユニットの内容を更新す
る。これを第１図、第２図を例にとつて説明すると、部
品６と１０が入れ換えになつた場合に部品１０に接続関
係のある部品５，７，９，１３，１４でもつている部品
１０の位置情報を第１図での（Ｘ＝１，Ｙ＝４）から第
２図での（Ｘ＝１，Ｙ＝３）というデータに書き変える
ことに相当する。このようにして入れ換えによつて生じ
た部品位置データの変更を全て終えると初期配置セット
フェイズ後の状態と同じになる（但し部品位置は第１図
から第２図へというような変化をしている）。引続いて
クロック線２７が“ｒ１になり、クロック線２８が゜゜
１゛になるという経過に従つて、次々に異なるメモリユ
ニットのベアが選択され上記と同様の処理が繰返される
。

この操作を繰返してクロック線２６，２７，２８，２９
が１周期経過しても如何なるノードベアにも入れ換えに
よる改善がなくなつたときあるいはある時間が経過した
とき入れ換えフェイズを完了する。この時点の各メモリ
ユニットに格納されている部品位置データが最終配置に
なる。以上説明したように本装置は従来ソフトウェアこ
よつて求めていた配置決定の問題をハードウェアで直接
解くことによつて極めて短時間に処理しうる効果をもた
らす。

従来のソフトウェアによる易合にも、汎用計算機という
ハードウェアを用いてはいるが、演算回路が単一である
ため逐次的にしか処理することができなかつたが、本発
明の装餡こよれば複数の演算回路によつて並列処理が可
圭になる。そのため従来のソフトウェアによる方去に比
べて処理時間の大幅な短縮が期待できる。なお、本実施
例ではメモリユニットアレイを５×５にしているが、こ
れは一般にＮｘｍになる。

【図面の簡単な説明】

第１図、第２図、第３図は配置改善処理手法を説明する
説明図、第４図は本発明装置の一実施例の回路図を示す
。 ２１・・・・・メモリユニット、２２・・・・・演算ユ
ニット、２３・・・・・データ信号線、２４・・・・・
コントロール信号線、２５・・・・・多相クロック発生
回路、２６，２７，２８，２９・・・・・クロック線。

Claims (1)

1. 【特許請求の範囲】 １ アレイ状に配置されたメモリ回路、これらの各メモ
   リ回路の間に設けられた少なくとも加減算と読み書き制
   御とレジスタ機能とを有する演算回路、これらの演算回
   路の位置する行・列に対応して異なる相のクロック信号
   を供給するための回路からなり、各メモリユニットに初
   期配置データとして部品番号とその部品に接続関係のあ
   る部品の番号と位置を格納しておき、上記クロック信号
   によつて選択された演算回路に隣接した一対のメモリ回
   路に格納された部品を入れ換えたときに配置が改善され
   るか否かを所定の評価基準にもとずいて該演算回路で判
   定し、改善されれば部品を入れ換え、改善されなければ
   入れ換えを行わないという処理を繰返して配置改善を逐
   次行つて最終配置を得ることを特徴とする配置決定装置
   。 ２ 上記演算回路は、互に隣接するメモリ回路の間にも
   うけられかつ該隣接するメモリ回路の両者をアクセスす
   るよう構成されることを特徴とする特許請求の範囲第１
   項記載の配置決定装置。 ３ 上記異なる相の各クロック信号は、当該クロック信
   号が与えられる複数の上記演算回路における演算処理を
   並列的に始動することを特徴とする特許請求の範囲第１
   項または第２項記載の配置決定装置。