(57)【特許請求の範囲】
【請求項１】
大規模論理回路の多数の素子を数珠つなぎにしたシフトレジスタ型スキャン回路の自動生成にあって、該素子を接続する全長が最短に近くなる接続順を求めるシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式において、  前記大規模論理回路内の任意の長方形領域を縦にｎ分割する縦分割手段と、
前記長方形領域を横にｍ分割する横分割手段と、
該ｎ分割により得られる各々の縦分割領域にあって前記素子である接続点を含まず、且つ該ｎ分割の中央のものに最も近い目標縦分割領域を検出する縦分割領域検出手段と、
該ｍ分割により得られる各々の横分割領域にあって該接続点を含まず、且つ該ｍ分割の中央のものに最も近い目標横分割領域を検出する横分割領域検出手段と、
前記目標縦分割領域及び前記目標横分割領域で形成される十字領域によって前記長方形領域を４個の分割長方形領域に分割する４領域分割手段と、
前記分割長方形領域内の一点を仮接続点として検出する仮接続点検出手段と、
前記各分割長方形領域内の該接続点の数を計数する計数手段と、
前記各分割長方形領域についての前記計数手段による計数結果該接続点数が１つの場合に該接続点を接続し、該接続点数が２つ以上の場合に前記仮接続点検出手段により検出された仮接続点を接続する接続手段と、
前記大規模論理回路が形成される長方形領域を、前記縦及び横分割手段で前記ｎ及びｍ分割した後、前記縦及び横分割領域検出手段で前記目標縦及び横分割領域を検出し、この検出領域が形成する十字領域によって前記4領域分割手段で該長方形領域を４個の分割長方形領域に分割し、この分割された各々の分割長方形領域の前記接続点の数を前記計数手段で計数し、この計数結果該接続点数が1であれば前記接続手段により該接続点を接続し、２つ以上であれば、この２つ以上の接続点が存在する分割長方形領域内において前記仮接続点検出手段で検出される仮接続点を接続すると共に、更に該４個の分割長方形領域に分割する一連の処理を、1つの分割長方形領域に該接続点が1つとなるまで繰り返すよう制御する制御手段と、
を具備したことを特徴とするシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項２】
前記縦及び横分割領域検出手段が、前記目標縦及び横分割領域を検出する際の、前記接続点を含まずの条件を、該接続点を所定数以上含まずの条件に置き換えたことを特徴とする請求項１記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項３】
前記縦及び横分割手段でｎ及びｍ分割する際に、その分割数ｎ及びｍを定める場合、前記接続点の分布密度を求め、この求められた分布密度数に応じて、最も接続すべき接続点が存在しない縦及び横分割領域が見出せる確率の高い数に定めるようにしたことを特徴とする請求項１又は２記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項４】
前記接続点が前記長方形領域の周辺に特定の特徴を持って均一的に存在する場合、前記縦及び横分割手段での前記縦及び横分割領域への分割処理、及び前記縦及び横分割領域検出手段での前記目標縦及び横分割領域の検出処理での条件から無視することを特徴とする請求項１〜３の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項５】
前記接続点が前記長方形領域の全域に特定の特徴を持って均一的に存在する場合、前記縦及び横分割手段での前記縦及び横分割領域への分割処理、及び前記縦及び横分割領域検出手段での前記目標縦及び横分割領域の検出処理での条件から無視することを特徴とする請求項１〜３の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項６】
前記長方形領域において、前記接続点が一定の範囲に偏って配置されている場合、その接続点群の最外郭に存在する接続点が角にくると共に全ての接続点を包括する長方形線で囲んだ領域を被分割長方形領域とすることを特徴とする請求項１〜５の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項７】
前記接続手段が、前記４個の分割長方形領域に分割する処理後の前記接続点又は前記仮接続点の接続終了後に、接続の始点から接続順に４点を取り、この４点の中間の２点の接続順を入替え、この入れ替えた４点を接続する線長が入れ替前よりも短くなれば、その入れ替えを採用する第１の接続順補正処理を、始点から終点までの全ての点に対して１点ずつ順次行うことを特徴とする請求項１〜６の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項８】
前記接続手段が、前記４個の分割長方形領域に分割する処理後の前記接続点又は前記仮接続点の接続終了後に、接続の始点から接続されている第１の点が始点に最も近い点で無い場合、始点から始点に最も近い第２の点を経由して第１の点に接続する置換を行い、この置換後の総線長が置換前よりも短くなれば、その置換を採用する第２の接続順補正処理を、始点から終点まで全ての点に対して１点ずつ順次行うことを特徴とする請求項１〜６の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項９】
前記接続手段が、前記第１及び第２の接続順補正処理を行った後と前の線長の比較評価を、前記接続点又は前記仮接続点を接続する直線の合計線長で行うと共に、直線が交差する数の増減に対して一定の重みを加味して評価するようにしたことを特徴とする請求項７又は８記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１０】
前記接続手段が、前記第１及び第２の接続順補正処理を、単独或いは双方を順不同で適用することを特徴とする請求項７又は８記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１１】
前記接続手段に、前記接続点の全ての接続後に、該接続点間が信号が適正に伝搬できない距離以上離れて接続された場合に、適正に信号が伝搬できるようにする素子を介在接続するための中継点を、該接続点間の中間位置を計算することによって求める第１手段を具備したことを特徴とする請求項１〜１０の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１２】
前記接続手段に、前記第１手段による前記中継点の算出後に、該中継点情報を配置設計手段に伝達する第２手段を具備したことを特徴とする請求項１１記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１３】
前記接続手段に、前記第１手段により算出された前記中継点が、前記配置設計手段による配置設計上不適正位置であった場合に、該不適正位置以外に該中継点を配置する補正を行う第３手段を具備したことを特徴とする請求項１〜１０の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１４】
前記接続手段に、前記接続点の全ての接続後に、出力側に２つの送信用接続端子を有する該接続点である素子において、信号が適正に伝搬できない状態で一方の送信用接続端子から他の複数の接続点へ接続がなされた場合、他方の未接続の送信用接続端子から信号の論理を適合させる中継素子を介して該他の複数の接続点の何れかを接続変更することによって、適正に信号が伝搬できるようにする第４手段を具備したことを特徴とする請求項１〜１０の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１５】
前記第４手段が、前記接続変更が行われた際に、前記中継素子が前記配置設計上不適正位置であった場合、該不適正位置以外の位置に該中継素子が配置されるように補正することを特徴とする請求項１４記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１６】
前記接続手段に、前記接続点間に回路が存在する場合、該回路を最短距離で迂接続する第５手段を具備したことを特徴とする請求項１〜１０の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１７】
前記接続手段に、所定距離離れた１対の入出力端子を有する回路を検出した際に、その中央を１つの接続点と認識する第６手段を具備したことを特徴とする請求項１〜１０の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１８】
前記接続手段に、予め接続順が定められた複数の接続点を検出した際に、該複数の接続点を囲む長方形領域の中央を１つの接続点と認識する第７手段を具備したことを特徴とする請求項１〜１０の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【請求項１９】
前記接続手段に、前記接続点が複数の独立した領域に分散している場合に、領域毎に該接続点を接続した後、各領域を所定順に接続する第８手段を具備ことを特徴とする請求項１〜１０の何れかに記載のシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式に関する。
【０００２】
この方式は、大規模論理ＬＳＩ（半導体集積回路）内の記憶素子であるフリップフロック（以下、ＦＦと略）を数珠つなぎにしたシフトレジスタ型スキャン回路（以下、スキャンチェーンと称す）の自動生成に、配置された多数の点の全てを、その直線で結ぶ距離の合計が最短となるような接続順を見出す問題である「巡回セールスマンの問題」の近似的解法を適用したものである。
【０００３】
近年、半導体技術の急速な進歩により、コンピュータ等に利用されるＬＳＩの１つ当たりの論理規模は増大の一途にある。このようなＬＳＩの製造後のテストを行うためのテストパターンの生成容易化、及びテストそのものの時間の短縮（テストパターン数の縮小）、更には装置試験者による装置試験の容易化のために、論理回路中のＦＦの状態を外部から任意の値に変更する可制御性としたり、或いは読み出す可観測性とするために、スキャンチェーンを構成する技術は既に広く利用されている。
【０００４】
但し、全てのＦＦをスキャンチェーンに組み込む対象とすることもあるが、チップの大きさの制限から、一部のＦＦのみをスキャンチェーンに組み込む場合もあり、本発明の方式では、その何れであるかを問わない。
【０００５】
スキャンチェーンを構成する際、その中に含まれるＦＦをどのような順番で接続するかは、論理的機能としては通常、重要な意味がなく任意と言える。しかし、実装設計（レイアウト設計）においては、そのスキャンチェーンの総線長は短ければ短いほど自動配線の成功の確率が高く、またスタンダードセル方式のＬＳＩではチップ面積を小さくすることができる。
【０００６】
更に、ＦＦのデータ出力に長大なスキャンチェーンの配線負荷を繋げることは動作性能に悪影響を及ぼすことになる。即ち、実装設計及び論理動作の性能の２つの面からＦＦのスキャンチェーンとしての接続の順番は、各ＦＦ間の接続距離、そして総接続線長がなるべく短くて済むことが望ましい。
【０００７】
従って、このような要求を満たす接続順番をＦＦの配置後、自動的に短い計算処理時間で見いだす方式が要望されている。
【０００８】
【従来の技術】
上述したＦＦのスキャンチェーンとしての接続順番を、各ＦＦ間の接続距離、そして総接続線長がなるべく短くなるようにする方式は、一般的に「巡回セールスマンの問題」として知られているものとほぼ同一のものであり、「組み合わせ最適化問題」として種々の解法が従来から提案されている。
【０００９】
例えば、シミュレーテッドアニーリング法或いは、それに学習機能を付加した方法、更には遺伝子アルゴリズムと呼ばれる方法等である。
【００１０】
【発明が解決しようとする課題】
ところで、上述した方法は、厳密解を求めることに主眼を置いており、１万個を越えるＦＦを含むような大規模な論理回路の最短なスキャンチェーンを実現する接続順を求めるような課題に適用した場合、計算処理時間が膨大となり、実用に供することは不可能に近い問題があった。
【００１１】
本発明は、このような点に鑑みてなされたものであり、大規模論理回路の最短なスキャンチェーンを実現する接続順を、実用上問題とならない短い計算処理時間で求めることができるシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式を提供することを目的としている。
【００１２】
【課題を解決するための手段】
図１に本発明の原理図を示す。この図１に示すシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式は、大規模論理回路の多数の素子を数珠つなぎにしたシフトレジスタ型スキャン回路の自動生成にあって、素子を接続する全長が最短に近くなる接続順を求めるものである。
【００１３】
本発明の特徴は、大規模論理回路内の任意の長方形領域を縦にｎ分割する縦分割手段１と、長方形領域を横にｍ分割する横分割手段２と、ｎ分割により得られる各々の縦分割領域にあって前記した素子である接続点を含まず、且つ該ｎ分割の中央のものに最も近い目標縦分割領域を検出する縦分割領域検出手段３と、ｍ分割により得られる各々の横分割領域にあって該接続点を含まず、且つ該ｍ分割の中央のものに最も近い目標横分割領域を検出する横分割領域検出手段４と、目標縦分割領域及び目標横分割領域で形成される十字領域によって長方形領域を４個の分割長方形領域に分割する４領域分割手段５と、分割長方形領域内の一点を仮接続点として検出する仮接続点検出手段６と、各分割長方形領域内の該接続点の数を計数する計数手段７と、各分割長方形領域についての計数手段７による計数結果該接続点数が１つの場合に接続点を接続し、接続点数が２つ以上であれば、仮接続点検出手段６により検出された仮接続点を接続する接続手段８と、大規模論理回路が形成される長方形領域を、縦及び横分割手段１，２でｎ及びｍ分割した後、縦及び横分割領域検出手段３，４で目標縦及び横分割領域を検出し、この検出領域が形成する十字領域によって4領域分割手段５で該長方形領域を４個の分割長方形領域に分割し、この分割された各々の分割長方形領域の接続点の数を計数手段７で計数し、この計数結果該接続点数が１であれば接続手段８により該接続点を接続し、２つ以上であればこの２つ以上の接続点が存在する分割長方形領域内において仮接続点検出手段６で検出される仮接続点を接続すると共に、更に該４個の分割長方形領域に分割する一連の処理を、１つの分割長方形領域に該接続点が１つとなるまで繰り返すよう制御する制御手段９とを具備する。
【００１４】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態について説明する。図１は既に前述の「課題を解決するための手段」でその構成を説明した本発明の原理図であるが、この図１を参照して本発明の一実施形態によるシフトレジスタ型スキャン回路生成における近似的最短接続順の自動検出方式について説明する。
【００１５】
図２に大規模論理回路が形成された長方形領域１０を示す。この長方形領域１０内において符号１１，１２，１３，１４は大規模論理回路を構成する多数のＦＦ（フリップフロップ）である。但し、ＦＦは□でしめしてあるが、符号は任意のものに付してある。
【００１６】
このＦＦ１１〜１４の近似的最短接続順を求める場合、まず、長方形領域１０を、図１に示す縦及び横分割手段１，２でｎ及びｍ（例えば２０及び１５）分割した後、縦及び横分割領域検出手段３，４で目標縦分割領域１６及び目標横分割領域１７を検出する。
【００１７】
この検出は、ｎ分割により得られる各々の縦分割領域にあってＦＦ１１〜１４を含まず、且つｎ分割の中央のものに最も近い縦分割領域が目標縦分割領域１６として検出され、ｍ分割により得られる各々の横分割領域にあってＦＦ１１〜１４を含まず、且つｍ分割の中央のものに最も近い横分割領域が目標横分割領域１７として検出される。
【００１８】
但し、ｎ及びｍは、人手で指示された数値、又は縦及び横に分割した短冊状の分割領域の平均密度指定された値以下となる数値などである。
次に、４領域分割手段５で、目標縦及び横分割領域１６，１７が形成する十字領域によって長方形領域１０を４領域１９，２０，２１，２２に分割する。
【００１９】
この分割された各々の長方形領域１９〜２２のＦＦ１１〜１４の数を計数手段７で計数する。この計数結果、ＦＦの数が例えば分割長方形領域２２に示すようにＦＦ１４の１つであれば接続手段８によりそのＦＦ１４を他の１つのＦＦ又は仮接続点と接続する。
【００２０】
２つ以上であれば、この２つ以上のＦＦが存在する分割長方形領域、例えばＦＦ１１〜１３が３つ存在する分割長方形領域２０で、この領域２０を前記した十字領域を求めるまでの一連の処理を行った後に、仮接続点検出手段６で検出された仮接続点を、ＦＦ又は他の仮接続点と接続すると共に、更に領域２０を４領域に分割する。
【００２１】
制御手段９は、以上の一連の処理を、１つの分割長方形領域（例えば、分割長方形領域２２）に接続点が１つとなるまで繰り返すよう制御する。
このような一連の処理によれば、大規模論理回路の多数のＦＦを数珠つなぎにした場合に、ＦＦを接続する全長が最短に近くなる接続順を求めることが可能となる。
【００２２】
また、上述した縦及び横分割領域検出手段３，４で目標縦分割領域１６及び目標横分割領域１７を検出する場合の、縦又は横分割領域にＦＦが含まれないといった条件を、ＦＦをある一定数以上含まずといった条件に置き換えるものとする。
【００２３】
この場合、大規模論理回路のＦＦの密度が高い場合に、目標縦分割領域１６及び目標横分割領域１７を検出するのに有効となる。
更に、縦及び横分割手段１，２でｎ及びｍ分割する際に、その分割数ｎ及びｍを定める場合、縦横それぞれの接続すべきＦＦの分布密度を求め、この求められた分布密度数に応じて、最も接続すべきＦＦが存在しない縦及び横分割領域が見出せる確率の高い数に定めるようにする。
【００２４】
図２の長方形領域１０内の周辺に破線□で示すＦＦは、縦及び横分割手段１，２での縦及び横分割領域への分割処理、及び縦及び横分割領域検出手段３，４で目標縦分割領域１６及び目標横分割領域１７を検出する処理での条件からは無視するようにする。
【００２５】
これは図３に示すように、長方形領域２５、即ちチップの内部全体に破線□で示すＦＦが、均一的に配置されている場合も同様に無視するようにする。
これは、近年の大規模論理回路（ＬＳＩ）におけるＦＦが組み込まれた入出力回路が、図２に破線□で示すようにチップ周辺、或いは図３に破線□で示すようにチップの内部全体に均一に配置されており、これはその群でスキャンチェーンを構成しなければならないためである。
【００２６】
図４に符号２６示す、大規模論理回路が形成される長方形領域、又はこの長方形領域の分割長方形領域において、□で示すように多数のＦＦが一定の範囲に偏って配置されている場合、そのＦＦ群の最外郭に存在するＦＦが角にくると共に全てのＦＦを包括する長方形線２７で囲んだ領域を、被分割長方形領域とする。
【００２７】
次に、ＦＦ又は仮接続点の接続順の補正処理方法を図５〜図２９を参照して説明する。但し、図５〜図２９において同一部分には同一符号を付す。
上述したように４分割を繰り返しながら各分割段階でのＦＦ又は仮接続点の接続順を全ての組み合わせに対比しながら評価して決定する。しかし、４分割した１つから次の同レベルの分割領域への接続順を決定する際に、分割の細かさのレベルが異なることになり、このため、その後分割を進め、同様に接続順を決定する際に悪影響を及ぼすような接続順を決定してしまう可能性がある。
【００２８】
このような状況を速い段階で除去するために、次に述べるような接続順の補正処理を行う。
図１に示した接続手段８は、通常、４分割領域の各領域内の接続点又は仮接続点から、始点、終点、その間の中間点を検出し、それらの点を順次接続する最短な接続を行うが、前述した理由から最短な接続が行われないことがある。
【００２９】
接続手段８が行う第１の接続順補正処理（４点内２点入替え改善処理）は、４分割後の接続が終了した後に、始点から接続順に４点を取り、この４点の中間の２点の接続順を入替え、この入れ替えた４点を接続する線長が入れ替える前よりも短くなるか判定し、入れ替え前よりも短くなれば、その入れ替えを採用するといった処理を、始点から終点まで全ての点に対して１点ずつ順次適用するものである。
【００３０】
第２の接続順補正処理（隣接点置換改善処理）は、始点に接続されている第１の中間点が始点に最も近い点で無い場合、始点から始点に最も近い第２の中間点を経由して第１の中間点に接続する置換を行い、この置換後の総線長が置換前よりも短くなるか判定し、置換前よりも短くなれば、その置換を採用するといった処理を、始点から終点まで全ての点に対して１点ずつ順次適用するものである。
【００３１】
また、第１及び第２の接続順補正処理を行った後と前の線長の比較評価は、接続点を接続する直線の合計線長で行うが、更に、直線が交差する数の増減に対して、一定の重みを加味して評価するようにする。
【００３２】
第１及び第２の接続順補正処理の適用は、単独、或いは双方を順不同で適用することができるものとする。
まず、図５に示すように第１回目の分割で、大規模論理回路が形成される長方形領域３０が４分割され、この４分割された各領域において、図４を参照して説明したように、更にＦＦが密集した部分を囲んだ長方形領域３１，３２，３３，３４が求められる。
【００３３】
長方形領域３１においてはＦＦが１つのみなのでＦＦが接続点３５とされ、長方形領域３２においては多数のＦＦが存在するので、仮接続点検出手段６（図１）で仮接続点３６が検出され、長方形領域３３においては同様に多数のＦＦが存在するので仮接続点３７が検出され、長方形領域３４においては複数のＦＦが存在するので仮接続点３８が検出されたとする。
【００３４】
この時、接続手段８が、接続点３５を始点、仮接続点３６を終点、他の仮接続点３７，３８を中間点として、それら４点を接続する最短な接続を行う。即ち、始点３１と中間点３８とが接続され、中間点３８と３７とが接続され、中間点３７と終点３６とが接続される。
【００３５】
次に、図６に示すように第２回目の分割で、図５に示す長方形領域３２が前述同様に符号４３，４４，４５，４６で示す領域に４分割され、長方形領域３３が符号４７，４８，４９，５０で示す領域に４分割され、長方形領域３４が符号５１，５２，５３，５４で示す領域に４分割される。
【００３６】
領域４３において仮接続点５５が検出され、領域４４において仮接続点５６が、領域４５において接続点５７が、領域４６において仮接続点５８が、領域４７において仮接続点５９が、領域４８において仮接続点６０が、領域４９において仮接続点６１が、領域５０において仮接続点６２が、領域５１において仮接続点６３が、領域５２において接続点６４が、領域５３において接続点６５が、領域５４において仮接続点５４が検出されたとする。
【００３７】
この時、接続手段８が、接続点３５を始点、仮接続点５６を終点、他の点中間点として、それらを接続する最短な接続を行う。
この接続後に、接続手段８が前述した第２の接続順補正処理（隣接点置換改善処理）を適用したとする。この場合の例を図７に示す。図６との比較から判るように、図７においては、仮接続点６０と６１とが接続され、仮接続点６１と５９とが、５９と６２とが、６２と６６とが、ＦＦ６５と仮接続点６３とが接続され、図６の場合の接続長よりも短くなっている。
【００３８】
この後、更に接続手段８が前述した第１の接続順補正処理（４点内２点入替え改善処理）を適用したとする。この場合の例を図８に示す。図７との比較から判るように、図８においては、仮接続点５５と５７とが接続され、仮接続点５８と６０とが、６０と５９とが、５９と６１とが、６１と６２とが接続され、図７の場合の接続長よりも短くなっている。
【００３９】
以降、４分割処理と通常の接続処理、第１及び第２接続順補正処理を繰り返すことによって最終的に図９に示すように全てのＦＦが近似的最短接続順で接続されることになる。
【００４０】
次に、図９に示したように最終的に全てのＦＦが接続された後、ＦＦ（接続点）間の距離が所定以上離れている場合の処理を、図１０〜図１２を参照して説明する。
【００４１】
最初に第１の処理を図１０を参照して説明する。図１０に示すように、チップ６６内のＦＦ６７と６８との間の距離が所定以上離れている場合、電気抵抗が大きく信号が適正に伝搬しなくなる。
【００４２】
このためバッファ用のゲートを挿入する必要があるが、そのゲートを自動的に挿入する中継点を求める。このため、実装設計が適切に行われるようにゲートの配置位置を計算する第１手段と、この第１手段によって求められ中継点情報を実装設計を行う配置設計処理手段に伝搬する第２手段とを接続手段８に有した。
【００４３】
ゲートの配置位置は、図に符号６９で示すようにＦＦ６７と６８間の中間が適当なので、第１手段によってそれを計算し、この後、第２手段によって６９で示す位置にゲート（中継点配置候補）を配置する。
【００４４】
しかし、スタンダードセル方式のＬＳＩでは、符号７０と７１で示すレイアウトブロックと呼ばれる実装単位の間にゲートが配置されることがある。このような位置にゲートが配置されることは実装設計規則から外れるので許されない。
【００４５】
そこで、最初に求まった中継点６９に最も近いレイアウトブロック７１内で、かつ信号を適正に伝搬できる位置７２に、ゲートを配置しなおす第３手段を接続手段８に有した。
【００４６】
即ち、第３手段の制御で、所定以上離れた互いに接続されるＦＦ６７と６８間にバッファゲートを挿入接続する位置７２を求めれば、電気抵抗を小さくして信号を適正に伝搬させることができる。
【００４７】
また、図１１に示すように、チップ６６内において、出力端Ｑと反転出力端ＸＱを有するＦＦ７４の出力端Ｑから線７７及び７８によって複数のＦＦ７５及び７６に接続されている場合に、それら接続間の距離が電気抵抗が大きく信号が適正に伝搬しないものであるとする。
【００４８】
この場合、接続手段８に、図１２に示すように接続元のＦＦ７４の使用されない反転出力端ＸＱからインバータ７９を介して１つのＦＦ７６にスキャンチェーン接続変更する第４手段を設けた。
【００４９】
第４手段の制御で、図１２のように接続変更することによって電気抵抗を小さくして信号を適正に伝搬させることができる。
図１２の接続変更において、インバータ７９が図１０を参照して説明したように、レイアウトブロックと呼ばれる実装単位の間に配置された場合は、第４手段が、インバータ７９を、インバータ７９に最も近いレイアウトブロック内で、かつ信号を適正に伝搬できる位置に配置しなおす制御を行うものとする。
【００５０】
次に、図１３に示すように、互いに接続されるＦＦ８１，８２の間に、ＲＡＭ又はレジスタファイル等のような巨大なマクロ回路８０が存在する場合の迂回配線について説明する。
【００５１】
このような場合、マクロ回路８０の上側又は下側を迂回してＦＦ８１と８２とを接続するが、そのうち短いほうで配線する第５手段を接続手段８に設けた。
即ち、図示するように第１迂回配線８３又は第２迂回配線８４のうち短いほうを第５手段によって求め、その短いほうである例えば第１迂回配線８３を採用するようにすれば、全体の配線長の短縮に寄与することができる。
【００５２】
次に、図１４に示すように、スキャンデータ入出力端子ＳＤＩ，ＳＤＯが遠く離れた巨大マクロ回路８６を１つの接続点と見なす場合について説明する。
ＲＡＭ又はレジスタファイル等のように大きさが通常のＦＦよりも遙に大きく、それらに内蔵されるスキャンチェーンとして接続されるＦＦを含む巨大マクロ回路８６にあっては、ＳＤＩとＳＤＯとが遠く離れておりＳＤＩから入力されるデータがＳＤＯから出力されるものがある。
【００５３】
このようなＳＤＩとＳＤＯとは、対を成すものなので各々を１つの接続点と見なすのが適当でない。そこで、このような巨大マクロ回路８６にあっては、その中央を１つの接続点８７と認識する第６手段を接続手段８に設けた。
【００５４】
また、図１５に示すように、複数のＦＦ８９，９０，９１，９２の接続順が予め定められている場合も、各々を１つの接続点と見なすのが適当でない。そこで、このような場合、複数のＦＦ８９〜９２を囲む長方形領域９３を求め、この領域９３の中央を１つの接続点９４と認識する第７手段を接続手段８に設けた。
【００５５】
次に、図１６に示すように、□で示すＦＦが複数の独立した領域９６，９７，９８，９９に分散している場合の接続について説明する。
この場合、各領域９６〜９９の各々において全てのＦＦを接続し、この後、各領域９６〜９９を所定の▲１▼〜▲４▼で示す順に接続する第８手段を接続手段８に設けた。また各領域９６〜９９の接続順は人手で指示することも可能とする。
【００５６】
このような接続方法は、スタンダードセル方式ＬＳＩの場合、機能的にまとまりのある回路を１つのレイアウトブロックとして実装設計し、スキャンチェーンは装置試験の都合から機能的まとまりの単位でアクセスしたいという要求、或いは、実装配線設計上、レイアウトブロックを出入りするような配線の発生の抑止等に有効である。
【００５７】
【発明の効果】
以上説明したように、本発明によれば、大規模論理回路の最短なスキャンチェーンを実現する接続順を、実用上問題とならない短い計算処理時間で求めることができる効果がある。
【図面の簡単な説明】
【図１】本発明の原理図である。
【図２】大規模論理回路が形成された長方形領域を示す第１の図である。
【図３】大規模論理回路が形成された長方形領域を示す第２の図である。
【図４】長方形領域決定処理説明図である。
【図５】接続順補正処理を説明する第１の図である。
【図６】接続順補正処理を説明する第２の図である。
【図７】接続順補正処理を説明する第３の図である。
【図８】接続順補正処理を説明する第４の図である。
【図９】接続完了図である。
【図１０】接続点間距離が所定以上離れている場合の第１処理説明図である。
【図１１】接続点間距離が所定以上離れている状態を示す図である。
【図１２】接続点間距離が所定以上離れている場合の第２処理説明図である。
【図１３】巨大マクロ回路を迂回配線する場合の説明図である。
【図１４】スキャンデータ入出力端子が離れた巨大マクロ回路を１つの接続点と見なす場合の説明図である。
【図１５】接続順が指定された全接続点を囲む長方形領域を１つの接続点と見なす場合の説明図である。
【図１６】接続点が複数の独立した領域に分散している場合の接続説明図である。
【符号の説明】
１  縦分割手段
２  横分割手段
３  縦分割領域検出手段
４  横分割領域検出手段
５  ４領域分割手段
６  仮接続点検出手段
７  計数手段
８  接続手段
９  制御手段
【図１】
0003568647.tif 000002
【図２】
0003568647.tif 000003
【図３】
0003568647.tif 000004
【図４】
0003568647.tif 000005
【図５】
0003568647.tif 000006
【図６】
0003568647.tif 000007
【図７】
0003568647.tif 000008
【図８】
0003568647.tif 000009
【図９】
0003568647.tif 000010
【図１０】
0003568647.tif 000011
【図１１】
0003568647.tif 000012
【図１２】
0003568647.tif 000013
【図１３】
0003568647.tif 000014
【図１４】
0003568647.tif 000015
【図１５】
0003568647.tif 000016
【図１６】
0003568647.tif 000017