JPH0989992A - シフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式 - Google Patents

Abstract

(57)【要約】 【課題】本発明は大規模論理回路の最短なスキャンチェ
ーンを実現する接続順を、実用上問題とならない短い計
算処理時間で求めることができるシフトレジスタ型スキ
ャン回路生成における近似的最短接続順の自動検出方式
を提供することを目的とする。 【解決手段】大規模論理回路が形成される長方形領域
を、手段１，２でｎ及びｍ分割した後、手段３，４で目
標縦及び横分割領域を検出し、この検出領域が形成する
十字領域により手段５で長方形領域を４領域に分割し、
この分割された各長方形領域の接続点数を手段７で計数
し、この計数結果接続点数が１であれば手段８により接
続点を接続し、２つ以上であれば、この２つ以上の接続
点が存在する分割長方形領域内において手段６で検出さ
れる仮接続点を接続すると共に、更に４領域に分割する
一連の処理を、１つの分割長方形領域に接続点が１つと
なるまで繰り返すように構成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はシフトレジスタ型ス
キャン回路生成における近似的最短接続順の自動検出方
式に関する。

【０００２】この方式は、大規模論理ＬＳＩ（半導体集
積回路）内の記憶素子であるフリップフロック（以下、
ＦＦと略）を数珠つなぎにしたシフトレジスタ型スキャ
ン回路（以下、スキャンチェーンと称す）の自動生成
に、配置された多数の点の全てを、その直線で結ぶ距離
の合計が最短となるような接続順を見出す問題である
「巡回セールスマンの問題」の近似的解法を適用したも
のである。

【０００３】近年、半導体技術の急速な進歩により、コ
ンピュータ等に利用されるＬＳＩの１つ当たりの論理規
模は増大の一途にある。このようなＬＳＩの製造後のテ
ストを行うためのテストパターンの生成容易化、及びテ
ストそのものの時間の短縮（テストパターン数の縮
小）、更には装置試験者による装置試験の容易化のため
に、論理回路中のＦＦの状態を外部から任意の値に変更
する可制御性としたり、或いは読み出す可観測性とする
ために、スキャンチェーンを構成する技術は既に広く利
用されている。

【０００４】但し、全てのＦＦをスキャンチェーンに組
み込む対象とすることもあるが、チップの大きさの制限
から、一部のＦＦのみをスキャンチェーンに組み込む場
合もあり、本発明の方式では、その何れであるかを問わ
ない。

【０００５】スキャンチェーンを構成する際、その中に
含まれるＦＦをどのような順番で接続するかは、論理的
機能としては通常、重要な意味がなく任意と言える。し
かし、実装設計（レイアウト設計）においては、そのス
キャンチェーンの総線長は短ければ短いほど自動配線の
成功の確率が高く、またスタンダードセル方式のＬＳＩ
ではチップ面積を小さくすることができる。

【０００６】更に、ＦＦのデータ出力に長大なスキャン
チェーンの配線負荷を繋げることは動作性能に悪影響を
及ぼすことになる。即ち、実装設計及び論理動作の性能
の２つの面からＦＦのスキャンチェーンとしての接続の
順番は、各ＦＦ間の接続距離、そして総接続線長がなる
べく短くて済むことが望ましい。

【０００７】従って、このような要求を満たす接続順番
をＦＦの配置後、自動的に短い計算処理時間で見いだす
方式が要望されている。

【０００８】

【従来の技術】上述したＦＦのスキャンチェーンとして
の接続順番を、各ＦＦ間の接続距離、そして総接続線長
がなるべく短くなるようにする方式は、一般的に「巡回
セールスマンの問題」として知られているものとほぼ同
一のものであり、「組み合わせ最適化問題」として種々
の解法が従来から提案されている。

【０００９】例えば、シミュレーテッドアニーリング法
或いは、それに学習機能を付加した方法、更には遺伝子
アルゴリズムと呼ばれる方法等である。

【００１０】

【発明が解決しようとする課題】ところで、上述した方
法は、厳密解を求めることに主眼を置いており、１万個
を越えるＦＦを含むような大規模な論理回路の最短なス
キャンチェーンを実現する接続順を求めるような課題に
適用した場合、計算処理時間が膨大となり、実用に供す
ることは不可能に近い問題があった。

【００１１】本発明は、このような点に鑑みてなされた
ものであり、大規模論理回路の最短なスキャンチェーン
を実現する接続順を、実用上問題とならない短い計算処
理時間で求めることができるシフトレジスタ型スキャン
回路生成における近似的最短接続順の自動検出方式を提
供することを目的としている。

【００１２】

【課題を解決するための手段】図１に本発明の原理図を
示す。この図１に示すシフトレジスタ型スキャン回路生
成における近似的最短接続順の自動検出方式は、大規模
論理回路の多数の素子を数珠つなぎにしたシフトレジス
タ型スキャン回路の自動生成にあって、素子を接続する
全長が最短に近くなる接続順を求めるものである。

【００１３】本発明の特徴は、長方形領域を縦にｎ分割
する縦分割手段１と、長方形領域を横にｍ分割する横分
割手段２と、ｎ分割により得られる各々の縦分割領域に
あって前記した素子である接続点を含まず、且つｎ分割
の中央のものに最も近い目標縦分割領域を検出する縦分
割領域検出手段３と、ｍ分割により得られる各々の横分
割領域にあって接続点を含まず、且つｍ分割の中央のも
のに最も近い目標横分割領域を検出する横分割領域検出
手段４と、目標縦及び横分割領域で形成される十字領域
によって長方形領域を４領域に分割する４領域分割手段
５と、十字領域の交差点を仮接続点とする仮接続点検出
手段６と、長方形領域内の接続点の数を計数する計数手
段７と、長方形領域内の接続点数が１つの場合に接続点
を接続し、接続点数が２つ以上の場合に仮接続点を接続
する接続手段８とを具備し、大規模論理回路が形成され
る長方形領域を、縦及び横分割手段１，２でｎ及びｍ分
割した後、縦及び横分割領域検出手段３，４で目標縦及
び横分割領域を検出し、この検出領域が形成する十字領
域によって４領域分割手段５で長方形領域を４領域に分
割し、この分割された各々の長方形領域の接続点の数を
計数手段７で計数し、この計数結果接続点数が１であれ
ば接続手段８により接続点を接続し、２つ以上であれ
ば、この２つ以上の接続点が存在する分割長方形領域内
において仮接続点検出手段６で検出された仮接続点を接
続すると共に、更に４領域に分割する一連の処理を、１
つの分割長方形領域に接続点が１つとなるまで繰り返す
ように構成したものである。

【００１４】

【発明の実施の形態】以下、図面を参照して本発明の実
施の形態について説明する。図１は既に前述の「課題を
解決するための手段」でその構成を説明した本発明の原
理図であるが、この図１を参照して本発明の一実施形態
によるシフトレジスタ型スキャン回路生成における近似
的最短接続順の自動検出方式について説明する。

【００１５】図２に大規模論理回路が形成された長方形
領域１０を示す。この長方形領域１０内において符号１
１，１２，１３，１４は大規模論理回路を構成する多数
のＦＦ（フリップフロップ）である。但し、ＦＦは□で
しめしてあるが、符号は任意のものに付してある。

【００１６】このＦＦ１１〜１４の近似的最短接続順を
求める場合、まず、長方形領域１０を、図１に示す縦及
び横分割手段１，２でｎ及びｍ（例えば２０及び１５）
分割した後、縦及び横分割領域検出手段３，４で目標縦
分割領域１６及び目標横分割領域１７を検出する。

【００１７】この検出は、ｎ分割により得られる各々の
縦分割領域にあってＦＦ１１〜１４を含まず、且つｎ分
割の中央のものに最も近い縦分割領域が目標縦分割領域
１６として検出され、ｍ分割により得られる各々の横分
割領域にあってＦＦ１１〜１４を含まず、且つｍ分割の
中央のものに最も近い横分割領域が目標横分割領域１７
として検出される。

【００１８】但し、ｎ及びｍは、人手で指示された数
値、又は縦及び横に分割した短冊状の分割領域の平均密
度指定された値以下となる数値などである。次に、４領
域分割手段５で、目標縦及び横分割領域１６，１７が形
成する十字領域によって長方形領域１０を４領域１９，
２０，２１，２２に分割する。

【００１９】この分割された各々の長方形領域１９〜２
２のＦＦ１１〜１４の数を計数手段７で計数する。この
計数結果、ＦＦの数が例えば分割長方形領域２２に示す
ようにＦＦ１４の１つであれば接続手段８によりそのＦ
Ｆ１４を他の１つのＦＦ又は仮接続点と接続する。

【００２０】２つ以上であれば、この２つ以上のＦＦが
存在する分割長方形領域、例えばＦＦ１１〜１３が３つ
存在する分割長方形領域２０で、この領域２０を前記し
た十字領域を求めるまでの一連の処理を行った後に、仮
接続点検出手段６で検出された仮接続点を、ＦＦ又は他
の仮接続点と接続すると共に、更に領域２０を４領域に
分割する。

【００２１】以上の一連の処理を、１つの分割長方形領
域（例えは分割長方形領域２２）に接続点が１つとなる
まで繰り返す。このような一連の処理によれば、大規模
論理回路の多数のＦＦを数珠つなぎにした場合に、ＦＦ
を接続する全長が最短に近くなる接続順を求めることが
可能となる。

【００２２】また、上述した縦及び横分割領域検出手段
３，４で目標縦分割領域１６及び目標横分割領域１７を
検出する場合の、縦又は横分割領域にＦＦが含まれない
といった条件を、ＦＦをある一定数以上含まずといった
条件に置き換えるものとする。

【００２３】この場合、大規模論理回路のＦＦの密度が
高い場合に、目標縦分割領域１６及び目標横分割領域１
７を検出するのに有効となる。更に、縦及び横分割手段
１，２でｎ及びｍ分割する際に、その分割数ｎ及びｍを
定める場合、縦横それぞれの接続すべきＦＦの分布密度
を求め、この求められた分布密度数に応じて、最も接続
すべきＦＦが存在しない縦及び横分割領域が見出せる確
率の高い数に定めるようにする。

【００２４】図２の長方形領域１０内の周辺に破線□で
示すＦＦは、縦及び横分割手段１，２での縦及び横分割
領域への分割処理、及び縦及び横分割領域検出手段３，
４で目標縦分割領域１６及び目標横分割領域１７を検出
する処理での条件からは無視するようにする。

【００２５】これは図３に示すように、長方形領域２
５、即ちチップの内部全体に破線□で示すＦＦが、均一
的に配置されている場合も同様に無視するようにする。
これは、近年の大規模論理回路（ＬＳＩ）におけるＦＦ
が組み込まれた入出力回路が、図２に破線□で示すよう
にチップ周辺、或いは図３に破線□で示すようにチップ
の内部全体に均一に配置されており、これはその群でス
キャンチェーンを構成しなければならないためである。

【００２６】図４に符号２６示す、大規模論理回路が形
成される長方形領域、又はこの長方形領域の分割長方形
領域において、□で示すように多数のＦＦが一定の範囲
に偏って配置されている場合、そのＦＦ群の最外郭に存
在するＦＦが角にくると共に全てのＦＦを包括する長方
形線２７で囲んだ領域を、被分割長方形領域とする。

【００２７】次に、ＦＦ又は仮接続点の接続順の補正処
理方法を図５〜図２９を参照して説明する。但し、図５
〜図２９において同一部分には同一符号を付す。上述し
たように４分割を繰り返しながら各分割段階でのＦＦ又
は仮接続点の接続順を全ての組み合わせに対比しながら
評価して決定する。しかし、４分割した１つから次の同
レベルの分割領域への接続順を決定する際に、分割の細
かさのレベルが異なることになり、このため、その後分
割を進め、同様に接続順を決定する際に悪影響を及ぼす
ような接続順を決定してしまう可能性がある。

【００２８】このような状況を速い段階で除去するため
に、次に述べるような接続順の補正処理を行う。図１に
示した接続手段８は、通常、４分割領域の各領域内の接
続点又は仮接続点から、始点、終点、その間の中間点を
検出し、それらの点を順次接続する最短な接続を行う
が、前述した理由から最短な接続が行われないことがあ
る。

【００２９】接続手段８が行う第１の接続順補正処理
（４点内２点入替え改善処理）は、４分割後の接続が終
了した後に、始点から接続順に４点を取り、この４点の
中間の２点の接続順を入替え、この入れ替えた４点を接
続する線長が入れ替える前よりも短くなるか判定し、入
れ替え前よりも短くなれば、その入れ替えを採用すると
いった処理を、始点から終点まで全ての点に対して１点
ずつ順次適用するものである。

【００３０】第２の接続順補正処理（隣接点置換改善処
理）は、始点に接続されている第１の中間点が始点に最
も近い点で無い場合、始点から始点に最も近い第２の中
間点を経由して第１の中間点に接続する置換を行い、こ
の置換後の総線長が置換前よりも短くなるか判定し、置
換前よりも短くなれば、その置換を採用するといった処
理を、始点から終点まで全ての点に対して１点ずつ順次
適用するものである。

【００３１】また、第１及び第２の接続順補正処理を行
った後と前の線長の比較評価は、接続点を接続する直線
の合計線長で行うが、更に、直線が交差する数の増減に
対して、一定の重みを加味して評価するようにする。

【００３２】第１及び第２の接続順補正処理の適用は、
単独、或いは双方を順不同で適用することができるもの
とする。まず、図５に示すように第１回目の分割で、大
規模論理回路が形成される長方形領域３０が４分割さ
れ、この４分割された各領域において、図４を参照して
説明したように、更にＦＦが密集した部分を囲んだ長方
形領域３１，３２，３３，３４が求められる。

【００３３】長方形領域３１においてはＦＦが１つのみ
なのでＦＦが接続点３５とされ、長方形領域３２におい
ては多数のＦＦが存在するので、仮接続点検出手段６
（図１）で仮接続点３６が検出され、長方形領域３３に
おいては同様に多数のＦＦが存在するので仮接続点３７
が検出され、長方形領域３４においては複数のＦＦが存
在するので仮接続点３８が検出されたとする。

【００３４】この時、接続手段８が、接続点３５を始
点、仮接続点３６を終点、他の仮接続点３７，３８を中
間点として、それら４点を接続する最短な接続を行う。
即ち、始点３１と中間点３８とが接続され、中間点３８
と３７とが接続され、中間点３７と終点３６とが接続さ
れる。

【００３５】次に、図６に示すように第２回目の分割
で、図５に示す長方形領域３２が前述同様に符号４３，
４４，４５，４６で示す領域に４分割され、長方形領域
３３が符号４７，４８，４９，５０で示す領域に４分割
され、長方形領域３４が符号５１，５２，５３，５４で
示す領域に４分割される。

【００３６】領域４３において仮接続点５５が検出さ
れ、領域４４において仮接続点５６が、領域４５におい
て接続点５７が、領域４６において仮接続点５８が、領
域４７において仮接続点５９が、領域４８において仮接
続点６０が、領域４９において仮接続点６１が、領域５
０において仮接続点６２が、領域５１において仮接続点
６３が、領域５２において接続点６４が、領域５３にお
いて接続点６５が、領域５４において仮接続点５４が検
出されたとする。

【００３７】この時、接続手段８が、接続点３５を始
点、仮接続点５６を終点、他の点中間点として、それら
を接続する最短な接続を行う。この接続後に、接続手段
８が前述した第２の接続順補正処理（隣接点置換改善処
理）を適用したとする。この場合の例を図７に示す。図
６との比較から判るように、図７においては、仮接続点
６０と６１とが接続され、仮接続点６１と５９とが、５
９と６２とが、６２と６６とが、ＦＦ６５と仮接続点６
３とが接続され、図６の場合の接続長よりも短くなって
いる。

【００３８】この後、更に接続手段８が前述した第１の
接続順補正処理（４点内２点入替え改善処理）を適用し
たとする。この場合の例を図８に示す。図７との比較か
ら判るように、図８においては、仮接続点５５と５７と
が接続され、仮接続点５８と６０とが、６０と５９と
が、５９と６１とが、６１と６２とが接続され、図７の
場合の接続長よりも短くなっている。

【００３９】以降、４分割処理と通常の接続処理、第１
及び第２接続順補正処理を繰り返すことによって最終的
に図９に示すように全てのＦＦが近似的最短接続順で接
続されることになる。

【００４０】次に、図９に示したように最終的に全ての
ＦＦが接続された後、ＦＦ（接続点）間の距離が所定以
上離れている場合の処理を、図１０〜図１２を参照して
説明する。

【００４１】最初に第１の処理を図１０を参照して説明
する。図１０に示すように、チップ６６内のＦＦ６７と
６８との間の距離が所定以上離れている場合、電気抵抗
が大きく信号が適正に伝搬しなくなる。

【００４２】このためバッファ用のゲートを挿入する必
要があるが、そのゲートを自動的に挿入する中継点を求
める。このため、実装設計が適切に行われるようにゲー
トの配置位置を計算する第１手段と、この第１手段によ
って求められ中継点情報を実装設計を行う配置設計処理
手段に伝搬する第２手段とを接続手段８に有した。

【００４３】ゲートの配置位置は、図に符号６９で示す
ようにＦＦ６７と６８間の中間が適当なので、第１手段
によってそれを計算し、この後、第２手段によって６９
で示す位置にゲート（中継点配置候補）を配置する。

【００４４】しかし、スタンダードセル方式のＬＳＩで
は、符号７０と７１で示すレイアウトブロックと呼ばれ
る実装単位の間にゲートが配置されることがある。この
ような位置にゲートが配置されることは実装設計規則か
ら外れるので許されない。

【００４５】そこで、最初に求まった中継点６９に最も
近いレイアウトブロック７１内で、かつ信号を適正に伝
搬できる位置７２に、ゲートを配置しなおす第３手段を
接続手段８に有した。

【００４６】即ち、第３手段の制御で、所定以上離れた
互いに接続されるＦＦ６７と６８間にバッファゲートを
挿入接続する位置７２を求めれば、電気抵抗を小さくし
て信号を適正に伝搬させることができる。

【００４７】また、図１１に示すように、チップ６６内
において、出力端Ｑと反転出力端ＸＱを有するＦＦ７４
の出力端Ｑから線７７及び７８によって複数のＦＦ７５
及び７６に接続されている場合に、それら接続間の距離
が電気抵抗が大きく信号が適正に伝搬しないものである
とする。

【００４８】この場合、接続手段８に、図１２に示すよ
うに接続元のＦＦ７４の使用されない反転出力端ＸＱか
らインバータ７９を介して１つのＦＦ７６にスキャンチ
ェーン接続変更する第４手段を設けた。

【００４９】第４手段の制御で、図１２のように接続変
更することによって電気抵抗を小さくして信号を適正に
伝搬させることができる。図１２の接続変更において、
インバータ７９が図１０を参照して説明したように、レ
イアウトブロックと呼ばれる実装単位の間に配置された
場合は、第４手段が、インバータ７９を、インバータ７
９に最も近いレイアウトブロック内で、かつ信号を適正
に伝搬できる位置に配置しなおす制御を行うものとす
る。

【００５０】次に、図１３に示すように、互いに接続さ
れるＦＦ８１，８２の間に、ＲＡＭ又はレジスタファイ
ル等のような巨大なマクロ回路８０が存在する場合の迂
回配線について説明する。

【００５１】このような場合、マクロ回路８０の上側又
は下側を迂回してＦＦ８１と８２とを接続するが、その
うち短いほうで配線する第５手段を接続手段８に設け
た。即ち、図示するように第１迂回配線８３又は第２迂
回配線８４のうち短いほうを第５手段によって求め、そ
の短いほうである例えば第１迂回配線８３を採用するよ
うにすれば、全体の配線長の短縮に寄与することができ
る。

【００５２】次に、図１４に示すように、スキャンデー
タ入出力端子ＳＤＩ，ＳＤＯが遠く離れた巨大マクロ回
路８６を１つの接続点と見なす場合について説明する。
ＲＡＭ又はレジスタファイル等のように大きさが通常の
ＦＦよりも遙に大きく、それらに内蔵されるスキャンチ
ェーンとして接続されるＦＦを含む巨大マクロ回路８６
にあっては、ＳＤＩとＳＤＯとが遠く離れておりＳＤＩ
から入力されるデータがＳＤＯから出力されるものがあ
る。

【００５３】このようなＳＤＩとＳＤＯとは、対を成す
ものなので各々を１つの接続点と見なすのが適当でな
い。そこで、このような巨大マクロ回路８６にあって
は、その中央を１つの接続点８７と認識する第６手段を
接続手段８に設けた。

【００５４】また、図１５に示すように、複数のＦＦ８
９，９０，９１，９２の接続順が予め定められている場
合も、各々を１つの接続点と見なすのが適当でない。そ
こで、このような場合、複数のＦＦ８９〜９２を囲む長
方形領域９３を求め、この領域９３の中央を１つの接続
点９４と認識する第７手段を接続手段８に設けた。

【００５５】次に、図１６に示すように、□で示すＦＦ
が複数の独立した領域９６，９７，９８，９９に分散し
ている場合の接続について説明する。この場合、各領域
９６〜９９の各々において全てのＦＦを接続し、この
後、各領域９６〜９９を所定の〜で示す順に接続す
る第８手段を接続手段８に設けた。また各領域９６〜９
９の接続順は人手で指示することも可能とする。

【００５６】このような接続方法は、スタンダードセル
方式ＬＳＩの場合、機能的にまとまりのある回路を１つ
のレイアウトブロックとして実装設計し、スキャンチェ
ーンは装置試験の都合から機能的まとまりの単位でアク
セスしたいという要求、或いは、実装配線設計上、レイ
アウトブロックを出入りするような配線の発生の抑止等
に有効である。

【００５７】

【発明の効果】以上説明したように、本発明によれば、
大規模論理回路の最短なスキャンチェーンを実現する接
続順を、実用上問題とならない短い計算処理時間で求め
ることができる効果がある。

【図面の簡単な説明】

【図１】本発明の原理図である。

【図２】大規模論理回路が形成された長方形領域を示す
第１の図である。

【図３】大規模論理回路が形成された長方形領域を示す
第２の図である。

【図４】長方形領域決定処理説明図である。

【図５】接続順補正処理を説明する第１の図である。

【図６】接続順補正処理を説明する第２の図である。

【図７】接続順補正処理を説明する第３の図である。

【図８】接続順補正処理を説明する第４の図である。

【図９】接続完了図である。

【図１０】接続点間距離が所定以上離れている場合の第
１処理説明図である。

【図１１】接続点間距離が所定以上離れている状態を示
す図である。

【図１２】接続点間距離が所定以上離れている場合の第
２処理説明図である。

【図１３】巨大マクロ回路を迂回配線する場合の説明図
である。

【図１４】スキャンデータ入出力端子が離れた巨大マク
ロ回路を１つの接続点と見なす場合の説明図である。

【図１５】接続順が指定された全接続点を囲む長方形領
域を１つの接続点と見なす場合の説明図である。

【図１６】接続点が複数の独立した領域に分散している
場合の接続説明図である。

【符号の説明】

１ 縦分割手段 ２ 横分割手段 ３ 縦分割領域検出手段 ４ 横分割領域検出手段 ５ ４領域分割手段 ６ 仮接続点検出手段 ７ 計数手段 ８ 接続手段

───────────────────────────────────────────────────── フロントページの続き (72)発明者 深瀬 久敬 神奈川県横浜市港北区新横浜二丁目15番16 株式会社富士通コンピュータテクノロジ 内

Claims (19)

【特許請求の範囲】
1. 【請求項１】 大規模論理回路の多数の素子を数珠つな
   ぎにしたシフトレジスタ型スキャン回路の自動生成にあ
   って、該素子を接続する全長が最短に近くなる接続順を
   求めるシフトレジスタ型スキャン回路生成における近似
   的最短接続順の自動検出方式において、 長方形領域を縦にｎ分割する縦分割手段と、 長方形領域を横にｍ分割する横分割手段と、 該ｎ分割により得られる各々の縦分割領域にあって前記
   素子である接続点を含まず、且つ該ｎ分割の中央のもの
   に最も近い目標縦分割領域を検出する縦分割領域検出手
   段と、 該ｍ分割により得られる各々の横分割領域にあって該接
   続点を含まず、且つ該ｍ分割の中央のものに最も近い目
   標横分割領域を検出する横分割領域検出手段と、 該目標縦及び横分割領域で形成される十字領域によって
   前記長方形領域を４領域に分割する４領域分割手段と、 該十字領域の交差点を仮接続点とする仮接続点検出手段
   と、 長方形領域内の該接続点の数を計数する計数手段と、 長方形領域内の該接続点数が１つの場合に該接続点を接
   続し、該接続点数が２つ以上の場合に該仮接続点を接続
   する接続手段とを具備し、 前記大規模論理回路が形成される長方形領域を、前記縦
   及び横分割手段で前記ｎ及びｍ分割した後、前記縦及び
   横分割領域検出手段で前記目標縦及び横分割領域を検出
   し、この検出領域が形成する十字領域によって前記４領
   域分割手段で該長方形領域を４領域に分割し、この分割
   された各々の長方形領域の前記接続点の数を前記計数手
   段で計数し、この計数結果該接続点数が１であれば前記
   接続手段により該接続点を接続し、２つ以上であれば、
   この２つ以上の接続点が存在する分割長方形領域内にお
   いて前記仮接続点検出手段で検出される仮接続点を接続
   すると共に、更に該４領域に分割する一連の処理を、１
   つの分割長方形領域に該接続点が１つとなるまで繰り返
   すことを特徴とするシフトレジスタ型スキャン回路生成
   における近似的最短接続順の自動検出方式。
2. 【請求項２】 前記縦及び横分割領域検出手段が、前記
   目標縦及び横分割領域を検出する際の、前記接続点を含
   まずの条件を、該接続点を所定数以上含まずの条件に置
   き換えたことを特徴とする請求項１記載のシフトレジス
   タ型スキャン回路生成における近似的最短接続順の自動
   検出方式。
3. 【請求項３】 前記縦及び横分割手段でｎ及びｍ分割す
   る際に、その分割数ｎ及びｍを定める場合、前記接続点
   の分布密度を求め、この求められた分布密度数に応じ
   て、最も接続すべき接続点が存在しない縦及び横分割領
   域が見出せる確率の高い数に定めるようにしたことを特
   徴とする請求項１又は２記載のシフトレジスタ型スキャ
   ン回路生成における近似的最短接続順の自動検出方式。
4. 【請求項４】 前記接続点が前記長方形領域の周辺に特
   定の性格を持って均一的に存在する場合、前記縦及び横
   分割手段での前記縦及び横分割領域への分割処理、及び
   前記縦及び横分割領域検出手段での前記目標縦及び横分
   割領域の検出処理での条件から無視することを特徴とす
   る請求項１〜３の何れかに記載のシフトレジスタ型スキ
   ャン回路生成における近似的最短接続順の自動検出方
   式。
5. 【請求項５】 前記接続点が前記長方形領域の全域に特
   定の性格を持って均一的に存在する場合、前記縦及び横
   分割手段での前記縦及び横分割領域への分割処理、及び
   前記縦及び横分割領域検出手段での前記目標縦及び横分
   割領域の検出処理での条件から無視することを特徴とす
   る請求項１〜３の何れかに記載のシフトレジスタ型スキ
   ャン回路生成における近似的最短接続順の自動検出方
   式。
6. 【請求項６】 前記長方形領域において、前記接続点が
   一定の範囲に偏って配置されている場合、その接続点群
   の最外郭に存在する接続点が角にくると共に全ての接続
   点を包括する長方形線で囲んだ領域を被分割長方形領域
   とすることを特徴とする請求項１〜５の何れかに記載の
   シフトレジスタ型スキャン回路生成における近似的最短
   接続順の自動検出方式。
7. 【請求項７】 前記接続手段が、前記４領域に分割する
   処理後の前記接続点又は前記仮接続点の接続終了後に、
   接続の始点から接続順に４点を取り、この４点の中間の
   ２点の接続順を入替え、この入れ替えた４点を接続する
   線長が入れ替前よりも短くなれば、その入れ替えを採用
   する第１の接続順補正処理を、始点から終点まで全ての
   点に対して１点ずつ順次行うことを特徴とする請求項１
   〜６の何れかに記載のシフトレジスタ型スキャン回路生
   成における近似的最短接続順の自動検出方式。
8. 【請求項８】 前記接続手段が、前記４領域に分割する
   処理後の前記接続点又は前記仮接続点の接続終了後に、
   接続の始点に接続されている第１の点が始点に最も近い
   点で無い場合、始点から始点に最も近い第２の点を経由
   して第１の点に接続する置換を行い、この置換後の総線
   長が置換前よりも短くなれば、その置換を採用する第２
   の接続順補正処理を、始点から終点まで全ての点に対し
   て１点ずつ順次行うことを特徴とする請求項１〜６の何
   れかに記載のシフトレジスタ型スキャン回路生成におけ
   る近似的最短接続順の自動検出方式。
9. 【請求項９】 前記接続手段が、前記第１及び第２の接
   続順補正処理を行った後と前の線長の比較評価を、前記
   接続点又は前記仮接続点を接続する直線の合計線長で行
   うと共に、直線が交差する数の増減に対して一定の重み
   を加味して評価するようにしたことを特徴とする請求項
   ７又は８記載のシフトレジスタ型スキャン回路生成にお
   ける近似的最短接続順の自動検出方式。
10. 【請求項１０】 前記接続手段が、前記第１及び第２の
    接続順補正処理を、単独或いは双方を順不同で適用する
    ことを特徴とする請求項７又は８記載のシフトレジスタ
    型スキャン回路生成における近似的最短接続順の自動検
    出方式。
11. 【請求項１１】 前記接続手段に、前記接続点の全ての
    接続後に、該接続点間が信号が適正に伝搬できない距離
    以上離れて接続された場合に、適正に信号が伝搬できる
    ようにする素子を介在接続するための中継点を、該接続
    点間の中間位置を計算することによって求める第１手段
    を具備したことを特徴とする請求項１〜１０の何れかに
    記載のシフトレジスタ型スキャン回路生成における近似
    的最短接続順の自動検出方式。
12. 【請求項１２】 前記接続手段に、前記第１手段による
    前記中継点の算出後に、該中継点情報を配置設計処理手
    段に伝達する第２手段を具備したことを特徴とする請求
    項１１記載のシフトレジスタ型スキャン回路生成におけ
    る近似的最短接続順の自動検出方式。
13. 【請求項１３】 前記接続手段に、前記第１手段により
    算出された前記中継点が、前記配置設計処理手段による
    配置設計上不適正位置であった場合に、該不適正位置以
    外に該中継点を配置する補正を行う第３手段を具備した
    ことを特徴とする請求項１〜１０の何れかに記載のシフ
    トレジスタ型スキャン回路生成における近似的最短接続
    順の自動検出方式。
14. 【請求項１４】 前記接続手段に、前記接続点の全ての
    接続後に、出力側に２つの送信用接続端子を有する該接
    続点である素子において、信号が適正に伝搬できない状
    態で一方の送信用接続端子から他の複数の接続点へ接続
    がなされた場合、他方の未接続の送信用接続端子から信
    号の論理を適合させる中継素子を介して該他の複数の接
    続点の何れかを接続変更することによって、適正に信号
    が伝搬できるようにする第４手段を具備したことを特徴
    とする請求項１〜１０の何れかに記載のシフトレジスタ
    型スキャン回路生成における近似的最短接続順の自動検
    出方式。
15. 【請求項１５】 前記第４手段が、前記接続変更が行わ
    れた際に、前記中継素子が前記配置設計上不適正位置で
    あった場合、該不適正位置以外の位置に該中継素子が配
    置されるように補正することを特徴とする請求項１４記
    載のシフトレジスタ型スキャン回路生成における近似的
    最短接続順の自動検出方式。
16. 【請求項１６】 前記接続手段に、前記接続点間に回路
    が存在する場合、該回路を最短距離で迂回して接続する
    第５手段を具備したことを特徴とする請求項１〜１０の
    何れかに記載のシフトレジスタ型スキャン回路生成にお
    ける近似的最短接続順の自動検出方式。
17. 【請求項１７】 前記接続手段に、所定距離離れた１対
    の入出力端子を有する回路を検出した際に、その中央を
    １つの接続点と認識する第６手段を具備したことを特徴
    とする請求項１〜１０の何れかに記載のシフトレジスタ
    型スキャン回路生成における近似的最短接続順の自動検
    出方式。
18. 【請求項１８】 前記接続手段に、予め接続順が定めら
    れた複数の接続点を検出した際に、該複数の接続点を囲
    む長方形領域の中央を１つの接続点と認識する第７手段
    を具備したことを特徴とする請求項１〜１０の何れかに
    記載のシフトレジスタ型スキャン回路生成における近似
    的最短接続順の自動検出方式。
19. 【請求項１９】 前記接続手段に、前記接続点が複数の
    独立した領域に分散している場合に、各領域毎に該接続
    点を接続した後、各領域を所定順に接続する第８手段を
    具備したことを特徴とする請求項１〜１０の何れかに記
    載のシフトレジスタ型スキャン回路生成における近似的
    最短接続順の自動検出方式。