JPH0240774A - ブロック配置処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はブロック配置処理方式に関し、特にＬ３１基板
、プリント基板等の配置単位となるブロックの配置処理
を行うブロック配置処理方式に関する。

〔従来の技術〕

従来、この種のブロック配置処理方式では、ブロック間
の距離（ブロック間隔）をできるだけ短くするために既
配置ブロックとの接続関係により次配置ブロックを接続
関係のある既配置ブロックの重心位置に配置していた（
参考文献［論理装置のＣＡＤＪ　、樹木行三編、情報処
理学会、昭和５３年３月２０日発行）。

近年、高速、高性能のＳＬＩ、プリント板等が要求され
るようになっており、遅延時間を短縮するためにクリテ
ィカルネットの線長制限が必要になっている。したがっ
て、ブロック配置処理においてもクリティカルパス上の
ブロックについては、ブロック間隔をある一定の値以下
にする処理が必要になってきている。

〔発明が解決しようとする課題〕 上述した従来のブロック配置処理方式では、接続間係の
ある既配置ブロックの重心位置に未配置ブロックを配置
していたので、ブロック間隔を平均的に短くするために
は有効である（事実、ブロック配置処理の評価関数とし
て総仮想配線長の最小化が採用されるのが一般的である
）が、ブロック間隔をある一定の値以下にするためには
ブロックの配置終了後に特定ブロック間の距離を調べ、
条件に合致しない場合は配置結果の修正が必要になると
いう欠点がある。

本発明の目的は、上述の点に鑑み、ブロックの配置処理
中に予め指定された特定ブロック間の許容間隔を調べる
ことにより、高速、高性能なＬＳｌ、プリント基板等の
設計時に必要となるクリティカルネットを構成するブロ
ックの配置を要求性能を満足する形で実現できるブロッ
ク配置処理方式を提供することにある。

〔課題を解決するための手段〕

本発明のブロック配置処理方式は、ＬＳ　Ｉ、プリント
基板等の配置単位となるブロックの配置処理を行うブロ
ック配置処理方式において、未配置ブロックから核ブロ
ックを選択する核ブロック選択手段と、この核ブロック
選択手段により選択された核ブロックを基板上の任意の
位置に配置する核ブロック配置手段と、未配置ブロック
の中から既配置ブロックとの接続関係が最も強（かつ他
の未配置ブロックとの接続関係が最も弱い未配置ブロッ
クを次配置ブロックとして選択する次配置ブロック選択
手段と、この次配置ブロック選択手段により選択された
次配置ブロックと接続関係のある既配置ブロックの重心
位置を求める計算手段と、この計算手段により求められ
た重心位置を次配置ブロックの配置候補位置とする移送
手段と、基板上の配置候補位置に次配置ブロックの配置
が可能かどうかを調べる配置可否判定手段と、この配置
可否判定手段により配置候補位置に次配置ブロックの配
置が可能と判定された場合にブロック間の許容間隔が指
定されている次配置ブロックの配置候補位置と既配置ブ
ロックとの間隔を求めて求めた間隔が指定された許容間
隔に適合するか否かを判定する指定許容間隔適合判定手
段と、この指定許容間隔適合判定手段により配置候補位
置が指定された許容間隔に適合しないと判定された場合
および前記配置可否判定手段により配置候補位置が次配
置ブロックの配置が不可能な位置と判定された場合に前
記計算手段により求められた重心位置からうずまき状に
探索して次配置ブロックの次の配置候補位置を求める探
索手段と、次配置ブロックを基板上の配置可能な配置候
補位置に配置する次配置ブロック配置手段とを有する。

〔作用〕

本発明のブロック配置処理方式では、核プロ・７り選択
手段が未配置ブロックから核ブロックを選択し、核ブロ
ック配置手段が核ブロック選択手段により選択された核
ブロックを基板上の任意の位置に配置し、次配置ブロッ
ク選択手段が未配置ブロックの中から既配置ブロックと
の接続関係が最も強くかつ他の未配置ブロックとの接続
関係が最も弱い未配置ブロックを次配置ブロックとして
選択し、計算手段が次配置ブロック選択手段により選択
された次配置ブロックと接続関係のある既配置ブロック
の重心位置を求め、移送手段が計算手段により求められ
た重心位置を次配置ブロックの配置候補位置とし、配置
可否判定手段が基板上の配置候補位置に次配置ブロック
の配置が可能かどうかを調べ、指定許容間隔適合判定手
段が配置可否判定手段により配置候補位置に次配置ブロ
ックの配置が可能と判定された場合にブロック間の許容
間隔が指定されている次配置ブロンクの配置候補位置と
既配置ブロックとの間隔を求めて求めた間隔が指定され
た許容間隔に適合するか否かを判定し、探索手段が指定
許容間隔適合判定手段により配置候補位置が指定された
許容間隔に適合しないと判定された場合および配置可否
判定手段により配置候補位置が次配置ブロックの配置が
不可能な位置と判定された場合に計算手段により求めら
れた重心位置からうずまき状に探索して次配置ブロック
の次の配置候補位置を求め、次配置ブロック配置手段が
次配置ブロックを基板上の配置可能な配置候補位置に配
置する。

〔実施例〕

次に、本発明について図面を参照して詳細に説明する。

第１図は、本発明の一実施例のブロック配置処理方式の
構成を示すブロック図である０本実施例のブロック配置
処理方式は、核ブロック選択手段ｌと、核ブロック配置
手段２と、次配置ブロック選択手段３と、計算手段４と
、移送手段５と、配置可否判定手段６と、指定許容間隔
適合判定手段７と、探索手段８と、次配置ブロック配置
手段９とから構成されている。

核ブロック選択手段ｌは、未配置プロ・７りから核とな
るブロック（核ブロック）を選択する。

核ブロック配置手段２は、核ブロック選択手段１により
選択された核ブロックを基板上の任意の位置に配置する
。

次配置ブロック選択手段３は、未配置ブロックの中から
すでに基板上に配置されている既配置ブロックとの接続
関係が最も強くかつ他の未配置ブロックとの接続関係が
最も弱い未配置ブロックを次配置ブロックとして選択す
る。また、次配置ブロック選択手段３は、上記の条件に
該当する未配置ブロックがなければ、ブロック配置処理
を終了する。

計算手段４は、次配置ブロックと接続関係のある既配置
ブロックの重心位置を求める。

移送手段５は、計算手段４により求められた重心位置を
次配置ブロックの配置候補位置とする。

配置可否判定手段６は、基板上の配置候補位置に次配置
ブロックの配置が可能かどうかを調べる。

指定許容間隔適合判定手段７は、次配置ブロックに特定
のブロック間の許容間隔が指定されている場合に既配置
ブロックとの間隔を計算し、次配置ブロックを基板上の
配置候補位置に配置したときに指定されたブロック間の
許容間隔に適合するかどうかを調べる。

探索手段８は、配置可否判定手段６および指定許容間隔
適合判定手段７により配置候補値Ｗｌに次配置ブロック
の配置が不可能と判定された場合に計算手段４により求
められた重心位置からうずまき状に探索して次配置ブロ
ックの次配置候補位置を求める。

次配置ブロック配置手段９は、次配置プロンクを基板上
の配置候補位置に配置する。

第２図を参照すると、本実施例のブロック配置処理方式
における処理は、核ブロック選択ステップ１１と、核ブ
ロック配置ステップ１２と、未配置ブロック有無判定ス
テップ１３と、次配置ブロック選択ステップ１４と、重
心位置計算ステップ１５と、重心位置配置候補位置設定
ステップ１６と、配置候補位置次配置ブロック配置可否
判定ステップ１７と、許容間隔指定有無判定ステップ１
８と、ブロック間隔計算ステップ１９と、指定許容間隔
適合判定ステップ２０と、うずまき状探索ステップ２１
と、次配置ブロック配置ステップ２２とからなる。

次に、このように構成された本実施例のブロック配置処
理方式の動作について説明する。

核ブロック選択手段１は、未配置ブロックから核となる
ブロック（核ブロック）を選択する（ステップ１１）。

次に、核ブロック配置手段２は、核ブロック選択手段１
により選択された核ブロックを基板上の任意の位置に配
置する（ステップ１２）。

続いて、次配置ブロック選択手段３は、未配置ブロック
の中からすでに基板上に配置されている既配置ブロック
との接続関係が最も強（かつ他の未配置ブロックとの接
続関係が最も弱い未配置ブロックがあるか否かを判定し
くステップ１３）、該当する未配置ブロックがあると判
定されたならば該当する未配置ブロックを次配置ブロッ
クとして選択する（ステップ１４）。また、次配置ブロ
ック選択手段３は、上記の条件に該当する未配置ブロッ
クがなければ、プロンク配置処理を終了する。

次配置ブロック選択手段３により次配置ブロックが選択
されたならば、計算手段４は、次配置ブロック選択手段
３により選択された次配置ブロックと接続関係のある既
配置ブロックの重心位置を求める（ステップ１５）。

計算手段４により既配置ブロックの重心位置が求められ
たならば、移送手段５は、計算手段４により求められた
重心位置を次配置ブロックの配置候補位置とする（ステ
ップ１６）。

移送手段５により次配置ブロックの配置候補位置が決定
されたならば、配置可否判定手段６は、基板上の配置候
補位置に次配置ブロックの配置が可能かどうかを調べる
（ステップ１７）。

配置可否判定手段６により基板上の配置候補位置に次配
置ブロックの配置が不可能と判定されたならば、探索手
段８は、ステップＩ６で移送手段５により配置候補位置
とされた基板上の位置からうずまき状に探索して新たな
配置候補位置を求めて（ステップ２１）、制御を配置可
否判定手段６に戻す。

ステップ１７で配置可否判定手段６により基板上の配置
候補位置に次配置プロ・ツクの配置が可能と判定された
ならば、指定許容間隔適合判定手段７は、次配置ブロッ
クに特定のブロックとの間で許容間隔が指定されている
か否かを判定する（ステップ１８）。次配置ブロックに
他のブロックとの間の許容間隔が指定されている場合に
は、指定許容間隔適合判定手段７は、次配置ブロックと
の間で許容間隔が指定されている既配置ブロックと配置
候補位置との間の距Ｍ（ブロック間隔）を求め（ステッ
プ１９）、求めたブロック間隔が指定された許容間隔内
であるか否かを判定する（ステップ２０）。許容間隔内
でないと判定された場合には、指定許容間隔適合判定手
段７は、探索手段８に制・御を渡す。

指定許容間隔適合判定手段７から制御を渡された探索手
段８は、上記と同様に、ステップ２１の処理を行う。

ステップ１８で次配置ブロックに許容間隔が指定されて
いないと判定された場合およびステップ２０で許容間隔
内と判定された場合には、指定許容間隔適合判定手段７
は、次配置ブロック配置手段９に制御を渡す。

指定許容間隔適合判定手段７から制御を渡された次配置
ブロック配置手段９は、基板上の配置候補位置に次配置
ブロックを配置しくステップ２２）、次配置ブロック選
択手段３に制御を戻す。

次に、第３図を用いて、ステップ１４の処理でブロック
Ｄが次配置ブロックとして選択された場合の配置処理に
ついて説明する。

ここで、次配置ブロックＤは、既配置ブロックＡ、既配
置ブロックＢおよび既配置ブロックＣと論理的な接続関
係があり、既配置ブロックＸとは論理的な接続関係はな
いものとする。

また、次配置ブロックＤは、既配置ブロックＣとの間隔
に予め許容間隔αが指定されているものとする。

次配置ブロック選択手段３により次配置ブロックＤが選
択されたならば、計算手段４により既配置ブロックＡ、
既配置ブロックＢおよび既配置ブロックＣの重心位置Ｇ
が求められ（ステップ１５）、求められた重心値ｆｆＧ
が移送手段５により最初の配置候補位置とされる（ステ
ップ１６）。

次に、配置可否判定手段６により最初の配置候補位置（
重心位置Ｇ）が次配置ブロックＤの配置が可能と判定さ
れるので（ステップ１７）、続いて指定許容間隔適合判
定手段７により次配置ブロックＤに許容間隔指定がある
かないかが濶ぺられる（ステップ１８）。次配置ブロッ
クＤには既配置ブロックＣとの間に許容間隔αの指定が
あるので、指定許容間隔適合判定手段７は、既配置ブロ
ックＣと最初の配置候補位置（重心値？１ｆＧ）との基
板上での間隔を求め（ステップ１９）、求めた間隔が許
容間隔α以内であるか否かを判定する（ステップ２０）
、ここでは、最初の配置候補位置（重心位置Ｇ）が既配
置ブロックＣの位置から許容間隔α以上離れているとす
ると求めた間隔が許容間隔α以内でないと判定され、最
初の配置候補位置（重心値ｆｉＧ）には次配置ブロック
Ｄを配置することができないので、探索手段８に制御が
渡される。

制御を渡された探索手段８は、重心値ｉＧからうずまき
状に探索して２番目の配置候補位置（ここでは、既配置
ブロックＸの位置とする）を求め（ステップ２１）、制
御を配置可否判定手段６に渡す。

制御を渡された配置可否判定手段６は、２番目の配置候
補位置が既配置ブロックＸの位置であるために次配置ブ
ロックＤの配置が不可能と判定するので（ステップ１７
）、制御が再度探索手段８に移り、探索手段８は、重心
値１ｉｆＧからのうずまき状の探索を既配置ブロックＸ
の位置から続行して３番目の配置候補位置として例えば
基板上の位置Ｚを求める（ステップ２１）。

次に、配置可否判定手段６により３番目の配置候補位Ｉ
ｚに次配置ブロックＤの配置が可能と判定されたとする
と（ステップ１７）、指定許容間隔適合判定手段７によ
り次配置ブロックＤとの間で許容間隔αが指定されてい
るブロックＣの位置と３番目の配置候補位ＷＺとの間隔
が許容間隔α以内であるかないかが判定される（ステッ
プ１８〜ステツプ２０）。

ここでは、配置可否判定手段６により許容間隔α以内で
あると判定されたとすると、次配置ブロック配置手段９
により３番目の配置候補位ＷＺに次配置ブロフクＤが配
置される（ステップ２２）。

なお、上記の許容範囲の指定には、種々のケースが考え
られる０例えば、ブロック間の間隔は、α以上必要であ
るとか、α以上β以下である必要があるとか等である。

これらのいずれの場合にも本実施例のブロック配置処理
方式が適用できることは明白である。

また、本発明のブロック配置処理方式は、プログラムを
作成してコンピュータ上で動作させることにより実現す
ることもできるし、ハードウェア化して動作させること
により実現することもできる。

〔発明の効果〕

以上説明したように本発明は、ブロック配置処理中に予
め指定された特定ブロック間の許容間隔を調べることに
より、高速、高性能な■、ＳＩ、プリント基板等の設計
時に必要となるクリティカルネツトを構成するブロック
の配置を要求性能を満足する形で実現することができる
という効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例のブロック配置処理方式の構
成を示すブロック図、 第２図は本実施例のブロック配置処理方式における処理
を示す流れ図、 第３図は次配置ブロックのブロック配置処理の動作を説
明するための図である。 図において、 １・・・核ブロック選択手段、 ２・・・核ブロック配置手段、 ３・・・次配置ブロック選択手段、 ４・・・計算手段、 ５・・・移送手段、 ６・・・配置可否判定手段、 ７・・・指定許容間隔適合判定手段、 ８・・・探索手段、 ９・・・次配置ブロック配置手段である。

Claims (1)

1. 【特許請求の範囲】 ＬＳＩ、プリント基板等の配置単位となるブロックの配
   置処理を行うブロック配置処理方式において、 未配置ブロックから核ブロックを選択する核ブロック選
   択手段と、 この核ブロック選択手段により選択された核ブロックを
   基板上の任意の位置に配置する核ブロック配置手段と、 未配置ブロックの中から既配置ブロックとの接続関係が
   最も強くかつ他の未配置ブロックとの接続関係が最も弱
   い未配置ブロックを次配置ブロックとして選択する次配
   置ブロック選択手段と、この次配置ブロック選択手段に
   より選択された次配置ブロックと接続関係のある既配置
   ブロックの重心位置を求める計算手段と、 この計算手段により求められた重心位置を次配置ブロッ
   クの配置候補位置とする移送手段と、基板上の配置候補
   位置に次配置ブロックの配置が可能かどうかを調べる配
   置可否判定手段と、この配置可否判定手段により配置候
   補位置に次配置ブロックの配置が可能と判定された場合
   にブロック間の許容間隔が指定されている次配置ブロッ
   クの配置候補位置と既配置ブロックとの間隔を求めて求
   めた間隔が指定された許容間隔に適合するか否かを判定
   する指定許容間隔適合判定手段と、この指定許容間隔通
   合判定手段により配置候補位置が指定された許容間隔に
   適合しないと判定された場合および前記配置可否判定手
   段により配置候補位置が次配置ブロックの配置が不可能
   な位置と判定された場合に前記計算手段により求められ
   た重心位置からうずまき状に探索して次配置ブロックの
   次の配置候補位置を求める探索手段と、次配置ブロック
   を基板上の配置可能な配置候補位置に配置する次配置ブ
   ロック配置手段と を有することを特徴とするブロック配置処理方式。