(57)【要約】【課題】従来のフィードバック検出器の制限を克服するフィードバック検出器を提供すること。【解決手段】回路ネットワーク中でスキャン不能なメモリ要素だけを横切るフィードバック・サイクルのすべてが、線形実行時間で検出される。本方法は、回路ネットワークを有向グラフとしてモデル化し、１つのフィードバック・サイクル要素を一定時間内に見つけることができるようネットワーク要素に属性を割り当てる。幅優先バージョンでは、せいぜい最後のスキャン可能なメモリ要素まで一定の距離だけトラバースすることにより、フィードバックを検出する。深さ優先バージョンでは、すべての先行ノードが完了になるまでは、グラフ・ノードが完了にならない。あるノードが、未完了である別のノードに出会わない場合、フィードバックはすぐに見つかる。両ノードが同じスキャン可能なメモリ要素によって定義されるゾーンにある場合、このフィードバックは基準違反である。【選択図】図１
2004198407.tif 000002
【特許請求の範囲】
【請求項１】
クリア不能な要素のみを横切るフィードバック・ループを見つけるためのシステムであって、
少なくとも１つの上位ノードの距離カウントを記録するために使用可能な第１のノードと、
距離カウントを有する第２のノードと、
前記第１のノードを前記第２のノードに接続する接続部と、
それ自体の距離カウントを有する前記第２のノードが、前記第１のノードの、前記同じ距離カウントを有する前記記録済みの上位ノードと同じノードであるかどうかを判定するために使用可能なカウント・アナライザと
を備えるシステム。
【請求項２】
前記第１のノードに結合されたスキャン可能な要素をさらに備える、請求項１に記載のシステム。
【請求項３】
前記第１のノードと前記第２のノードの間に複数のノードをさらに備え、各ノードが別々の距離カウントを有する、請求項１に記載のシステム。
【請求項４】
前記第２のノードと前記第１のノードの間の諸ノードに関連する関連カウントが、ノードからノードへと増分される、請求項３に記載のシステム。
【請求項５】
前記第２のノードが前記上位ノードと同じ場合に、前記カウント・アナライザが、前記ループに許容不能とフラグを立てるために使用可能である、請求項１に記載のシステム。
【請求項６】
前記第１のノードと前記第２のノードの間に挿入されたスキャン可能な要素をさらに備える、請求項１に記載のシステム。
【請求項７】
前記スキャン可能な要素がラッチである、請求項６に記載のシステム。
【請求項８】
前記スキャン可能な要素が、前記距離カウントをゼロにリセットするために使用可能である、請求項５に記載のシステム。
【請求項９】
前記フィードバック・ループが、電力網、通信ネットワーク、またはバス相互接続中にある、請求項１に記載のシステム。
【請求項１０】
ネットワーク中で、フィードバック条件の標識を生成する方法であって、
親論理ノードと子論理ノードの間にメモリ要素があるかどうかを判定するステップと、
メモリ要素がある場合、前記メモリ要素がスキャン可能なメモリ要素である場合に前記子論理ノードに第２の属性を割り当てるステップと、
メモリ要素がある場合、前記メモリ要素がスキャン不能なメモリ要素である場合に前記子論理ノードに第３の属性を割り当てるステップと、
前記親論理ノードの距離に１を加えた距離を前記子論理ノード中に記憶するステップと、
前記親論理ノードの前記標識を前記子論理ノード中に記憶するステップと
を含む方法。
【請求項１１】
第１の属性を入力から第１の論理要素に割り当てるステップをさらに含み、前記第１の属性が、トラバース中にメモリ要素に出会わなかったことを示す、請求項１０に記載の方法。
【請求項１２】
前記親論理ノードと前記子論理ノードの間にあるスキャン可能なメモリ要素の挿入に関して、要素の関連カウントをゼロにリセットするステップをさらに含む、請求項１０に記載の方法。
【請求項１３】
前記子論理ノードと前記親論理ノードの間に挿入されたメモリ要素がない場合、前記子論理ノードが前記親論理ノードから前記属性を継承するステップをさらに含む、請求項１０に記載の方法。
【請求項１４】
基準違反のフィードバック・ループを判定する方法であって、
第１のノードを選択するステップと、
第１、第２、または第３の属性を有する第２のノードを選択するステップと、
前記第１のノードから前記第２のノードへの接続部を作成するステップと、
前記第２のノードが前記第２の属性を有する場合に、許容可能な接続部として前記接続部にフラグを立てるステップと
を含む方法。
【請求項１５】
第２の属性を有するノードを選択する前記ステップが、第１のノードから第２のノードへのトラバース中に少なくとも１つのメモリ要素に出会うことを示す、請求項１４に記載の方法。
【請求項１６】
第３の属性を有するノードを選択する前記ステップが、スキャン不能なメモリ要素が、前記第１のノードから前記第２のノードへのトラバース中に出会った最後のメモリ要素であったことを示す、請求項１４に記載の方法。
【請求項１７】
前記許容可能な接続部が許容可能なフィードバック・ループを構成する、請求項１４に記載の方法。
【請求項１８】
前記第２のノードが前記第３の属性を有する場合に、
前記第２のノードにある前記距離カウント値を検索するステップと、
前記第２のノードと同じカウント値を有する前記第１のノードの上位ノードの標識を検索するステップと、
前記第２のノードと前記同じカウントを有する前記上位ノードが同じノードでない場合に、許容可能なループとして前記ループにフラグを立てるステップと、
前記第２のノードと前記同じカウントを有する前記上位ノードが同じノードである場合に、許容不能なフィードバック・ループとして前記フィードバック・ループにフラグを立てるステップと
をさらに含む、請求項１４に記載の方法。
【請求項１９】
２つのクリア可能な要素間に所定数より多くの論理ノードおよびスキャン不能な要素がある場合に、設計違反のフラグを立てるステップをさらに含む、請求項１４に記載の方法。
【請求項２０】
複数の集合回路ネットワークが許容可能なフィードバック・ループを有することを判定する方法であって、
第１のネットワークが、前記第１のネットワーク中に許容不能なフィードバック・ループを有するかどうかを判定するステップと、
第２のネットワークが、前記第２のネットワーク中に許容不能なフィードバック・ループを有するかどうかを判定するステップと、
前記第１および第２のネットワーク内で各ネットワークの各入力と各出力の間に配置された、少なくとも１つのスキャン可能なメモリ要素を必要とするステップと
を含む方法。
【請求項２１】
前記第１および第２のネットワークの両者の内部にスキャン不能な要素を配置する前に、入力パス上にスキャン可能な要素を配置することをさらに含む、請求項２０に記載の方法。
【請求項２２】
前記第１および第２のネットワークの両者の内部に出力の前に最後のメモリ要素としてスキャン可能な要素を配置することをさらに含む、請求項２０に記載の方法。
【請求項２３】
スキャン可能な要素がスキャン不能な要素の前の入力パス上に挿入されているという要件、およびスキャン可能なラッチが前記第１および第２のネットワークの両者の出力の前の最後のメモリ要素であるという要件の両方をスキャン・メモリ・ルールが含む、請求項２０に記載の方法。
【請求項２４】
深さ優先検索を使用して基準違反のフィードバック・ループを見つける方法であって、
上位論理ノードと子論理ノードの間にメモリ要素があるかどうかを判定するステップと、
メモリ要素がある場合、前記メモリ要素がスキャン可能なメモリ要素である場合に前記子論理ノードに第１の属性を割り当てるステップと、
メモリ要素がある場合、前記メモリ要素がスキャン不能なメモリ要素である場合に前記子論理ノードに第２の属性を割り当てるステップと、
前記子論理ノードの関連カウントを増分するステップと、
子論理ノードに対して、ＮＯＴ＿ＦＩＮＩＳＨＥＤまたはＦＩＮＩＳＨＥＤの状態を生成するステップと、
親ノードからのパス上で出会った最後のスキャン可能な要素に対して、増分スキャン・カウント標識を生成するステップと、
下位の論理ノードが前記増分スキャン・カウントを継承するステップと
を含む方法。
【請求項２５】
基準違反のフィードバック・ループを判定する方法であって、
第１のノードを選択するステップと、
第２のノードを選択するステップと、
前記第１のノードから前記第２のノードへの接続部を作るステップと、
前記第２のノードが第１、第２、または第３の属性をもたない場合に、許容可能な接続部として前記接続部にフラグを立てるステップと、
前記第２のノードが第１、第２、または第３の属性をもつ場合には、
前記第２のノードが完了済みの状態をもつ場合に、許容可能な接続部として前記接続部にフラグを立てるステップと、
前記第２のノードが未完了の状態をもつ場合に、前記第１のノードおよび前記第２のノードが同一の増分ＺＯＮＥ＿ＩＤを有するかどうかを判定するステップと、
前記第１および第２のノードが共に同一の増分ＺＯＮＥ＿ＩＤをもつ場合に、前記接続部に許容不能な接続部とフラグを立てるステップと、
前記第１および第２のノードが異なる増分ＺＯＮＥ＿ＩＤをもつ場合に、前記接続部に許容可能な接続部とフラグを立てるステップと
を含む方法。
【請求項２６】
ネットワーク中のフィードバック条件の標識を生成するためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品が、コンピュータ・プログラムをその上で実施する媒体を有しており、前記コンピュータ・プログラムが、
親論理ノードと子論理ノードの間にメモリ要素があるかどうかを判定するコンピュータ・コードと、
メモリ要素がある場合、前記メモリ要素がスキャン可能なメモリ要素である場合に前記子論理ノードに第１の属性を割り当てるコンピュータ・コードと、
メモリ要素がある場合、前記メモリ要素がスキャン不能なメモリ要素である場合に前記子論理ノードに第２の属性を割り当てるコンピュータ・コードと、
前記子論理ノードの関連カウントを増分するコンピュータ・コードと、
前記子論理ノード中に、前記親論理ノードの関連カウントおよび前記親論理ノードの標識を記憶するコンピュータ・コードと
を含むコンピュータ・プログラム製品。
【請求項２７】
ネットワーク中のフィードバック条件の標識を生成するプロセッサであって、前記プロセッサがコンピュータ・プログラムを含み、前記コンピュータ・プログラムが、
親論理ノードと子論理ノードの間にメモリ要素があるかどうかを判定するコンピュータ・コードと、
メモリ要素がある場合、前記メモリ要素がスキャン可能なメモリ要素である場合に前記子論理ノードに第１の属性を割り当てるコンピュータ・コードと、
メモリ要素がある場合、前記メモリ要素がスキャン不能なメモリ要素である場合に前記子論理ノードに第２の属性を割り当てるコンピュータ・コードと、
前記子論理ノードの関連カウントを増分するコンピュータ・コードと、
前記子論理ノード中に、前記親論理ノードの関連カウントおよび前記親論理ノードの標識を記憶するコンピュータ・コードと
を含むプロセッサ。
【請求項２８】
基準違反のフィードバック・ループを判定するためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品が、コンピュータ・プログラムをその上で実施する媒体を有しており、前記コンピュータ・プログラムが、
第１のノードを選択するコンピュータ・コードと、
第１、第２、または第３の属性を有する第２のノードを選択するコンピュータ・コードと、
前記第１のノードから前記第２のノードへの接続部を作成するコンピュータ・コードと、
前記第２のノードが前記第２の属性を有する場合に、許容可能な接続部として前記接続部にフラグを立てるコンピュータ・コードと
を含むコンピュータ・プログラム製品。
【請求項２９】
基準違反のフィードバック・ループを判定するプロセッサであって、前記プロセッサがコンピュータ・プログラムを含み、前記コンピュータ・プログラムが、
第１のノードを選択するコンピュータ・コードと、
第１、第２、または第３の属性を有する第２のノードを選択するコンピュータ・コードと、
前記第１のノードから前記第２のノードへの接続部を作成するコンピュータ・コードと、
前記第２のノードが前記第２の属性を有する場合に、許容可能な接続部として前記接続部にフラグを立てるコンピュータ・コードと
を含むプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はディジタル回路のテストに関し、より詳細には、スキャン不能メモリ要素を横切るフィードバック・ループを識別することに関する。
【背景技術】
【０００２】
現代の回路ネットワークでは、物理寸法が縮小し、素子数（トランジスタ、ゲート、配線）が時間と共に指数関数的に増大するにつれ、チップの製造後の故障のテストはますます重要かつ複雑になってきた。当技術分野の現在の状態では、コンピュータまたは手作業により生成した（テストベクトルとして知られる）テスト・ケースをその回路ネットワーク内のスキャン・ラッチに入れてスキャンする自動化テスタを取り入れている。一般に、スキャン・ラッチなどスキャン可能メモリ要素は、テスト工程の間に、それらの値を直接観測することのできる要素である。これらのスキャン可能なメモリ要素は、テスト中の回路ブロックの論理値を示すために使用可能である。
【０００３】
個々の論理機能に供給された既知の入力値の使用により、自動化テスタによって測定した出力を期待される結果と比較することができる。測定済みの結果と期待される結果の一致により、デバイスの正しい動作が検証される。
【０００４】
回路ネットワークの物理的なトポロジ、特にスキャン可能なメモリ要素の構成と動作が、検証に使用されるテスト・パターンの複雑性、各チップをテストするために必要な時間、および潜在的な故障がどの程度カバーされるかという点でのこれらのテストの品質を決定する上で役に立つ。
【０００５】
しかしながら、特定のクラスのネットワーク要素を横切るフィードバックは、この検証工程を極めて困難にする物理トポロジである。ネットワーク要素を横切るフィードバックは、一般にネットワーク要素を含むフィードバック・ループとして定義することができる。非スキャン・ラッチ（ＮＳＬ）（テスト工程の間に、記憶値を直接観測し、または変更することができないメモリ要素）を横切るフィードバックでは、テスト・パターン生成、テスト時間、およびテスト品質に関する問題が生じる。
【０００６】
ＮＳＬによって駆動される論理要素のネットワークが、その同じＮＳＬの入力にフィードバックされるとき、含まれる回路ネットワークをテストすることが困難になる可能性のあるループを作る。一般にＦ（ｔｎ）で知られる時間ｔｎにおけるＮＳＬの出力値は、フィードバックがあるので入力Ｆ（ｔｎ−１）に依存する。Ｆ（ｔｎ−１）は、Ｆ（ｔｎ−２）に依存し、全経路を回帰的に戻って最初の状態Ｆ（０）に至る。この初期状態が未知の場合、テストが不可能になる可能性がある。しかしながら、たとえこの初期状態が既知の場合でも、回路ネットワークＦ（ｔｎ−１）の次の期待出力を決定するために、Ｆ（０）ないしＦ（ｔｎ）のすべての値（あるいは、最低限、ある既知パターンが反復を開始する以前のすべての値）を、テスト・パターン生成プログラムが知るべきである。この出力値を獲得し保持するには、計算時間およびメモリの点でそれぞれ非常にコストがかかる。しかしながら、これらの情報を保持しなければ、さらに費用がかかる可能性さえある。出力値を保持しないということは、ループ中に含まれる論理ノードのテストができないこと、またその結果、顧客が使用するまで知られないままになるエラーがあり得ることを意味する。
【０００７】
しかしながら、スキャン可能ラッチ（ＳＬ）を横切るフィードバックは、この無限ループを効率よく短絡する。ＳＬを用いれば、いつでも既知の値を回路ネットワーク・ループに入力することが可能であり、これらの既知の入力との相関を取るためにその出力をテストすることができる。テスト・パターン生成に対して、どのような特別な困難な問題も生じないことから、スキャン可能な要素を横切るフィードバックは、回路ネットワーク中で一般に許される。
【０００８】
回路ネットワークは、有向グラフとしてモデル化することが可能である。この有向グラフでは、グラフのノードまたは交点が回路要素（トランジスタ、ゲートなど）であり、一方、グラフの辺は配線、バス、または回路ネットワークのネットである。一般に、回路ネットワークへ入力ピンを入れることによって、有向グラフをトラバースする（traverse）。入力から幅優先トラバース（breadth first traversal）を実施することができる。一般的に幅優先トラバースは、距離１の未訪問要素をすべて訪れマーキングし、次に入力から距離２の未訪問要素をすべて訪れマーキングし、以下同様に行うことと定義することが可能である。未訪問要素は、一般にその要素がトラバース中に有向グラフによってまだ訪問を受けていない状態と定義することができる。
【０００９】
しかしながら、かかる幅優先トラバース・アルゴリズムの実行時において、一般に有向グラフ中でフィードバック・サイクルを見出すには、２次のＯ（Ｎ２）時間を必要とする。ここで、Ｎはネットワーク要素の数にこれらの要素を接続している配線またはネットの数を加えたものである。Ｎがおよそ数億から数十億の要素の回路ネットワークでは、この実行時間は、受け入れがたいほど遅い。このＯ（Ｎ２）幅優先トラバース・アルゴリズムの場合の膨大な実行時間は、非スキャン・ラッチを横切る好ましくないフィードバック・サイクルが、たとえあるとしても、ほとんど検出されないことになることを意味する。これを言い換えれば、回路ネットワークをテストすることが困難になり、回路ネットワークのテスト・カバレージが減少し、テスト時間が増大する。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
フィードバック・ループがスキャン不能要素を横切るので、かかるループを製造に先立って見つけ除去することが望ましい。したがって、従来のフィードバック検出器の制限を克服するフィードバック検出器が必要になっている。
【課題を解決するための手段】
【００１１】
本発明は、クリアする要素をもたないフィードバック・ループを見つけることを実現する。距離カウントを有する第１のノードが、第１のノードの少なくとも１つの上位ノードに関連する距離カウントを記録するために使用可能である。第１のノードを第２のノードに接続するループが存在する。カウント・アナライザは、それ自体の距離カウントを有する第２のノードが、第１のノードの記録済み上位ノードと同一ノードであるかどうかを判定するために使用可能である。一態様では、第２のノードが第１のノードの上位ノードと同一のノードである場合、ループに承認不可能とフラグを立てる。
【００１２】
本発明および本発明の利点をより完全に理解するためには、以下の詳細な説明を、添付図面と併せ参照されたい。
【発明を実施するための最良の形態】
【００１３】
以下の議論では、本発明を完全に理解してもらうために、非常に多くの具体的な詳細について記述している。しかしながら、当業者なら、かかる具体的な詳細なしに本発明を実施することができることを理解されよう。他の場合には、不必要な詳細によって本発明が分かりにくくならないように、周知の要素を概略図またはブロック図の形で示している。さらに、主としてネットワーク通信、電磁気信号技術などに関する詳細については、かかる詳細が本発明の完全な理解を得るために必要と考えられず、また当業者の理解の範囲内であると考えられるので省略している。
【００１４】
さらに、別段の指示がない限り、本明細書で説明するすべての機能は、ハードウェアまたはソフトウェア、あるいはそれらの組合せの形で実施することができることに留意されたい。ただし、好ましい実施形態では、これらの機能は、別段の指示がない限り、コンピュータまたは電子データ・プロセッサなどのプロセッサにより、かかる機能を実施するためにコード化されたコンピュータ・プログラム・コード、ソフトウェア、または集積回路、あるいはそれらの組合せに従って実施される。
【００１５】
図１を参照すると、スキャン可能な、または「クリア可能」な要素１１０、およびスキャン不能な、または「クリア不能」な要素１２０を備える回路ネットワーク１００の有向マップが示されている。一般的に、ネットワーク１００では、異なる論理ブロック間に許容不能なフィードバック・ループがないかどうかをテストする。
【００１６】
一実施形態では、スキャン可能要素１１０およびスキャン不能要素１２０は、フリップフロップ対である。ネットワーク１００中で、スキャン・ラッチ１１０などのクリア可能要素が、回路ネットワーク１００を貫通する電気的パス中に挿入されている。図１はさらに論理ブロック１１５、１２５、および１３５を含んでいる。一般に、ノードは、メモリ要素、論理ゲート、論理ブロックなどの回路ネットワーク要素を備える。
【００１７】
ネットワーク１００は、さらに、フィードバック検出エンジン１１６内に、距離増分器１１７、属性割当機構１１９、およびカウント・アナライザ１２２を備える。一般的に、距離増分器１１７は、ノードからノードへ、またはノードからスキャン不能フリップフロップにトラバースする際に、ノードに関連するカウントを増分する。例えば、ノード１２５からスキャン不能要素１２０にトラバースするときに、カウントを１だけ増分する。一実施形態では、スキャン可能要素に出会った際に、距離増分器１１７によって設定されるカウントを、ゼロにリセットする。例えば、ノード１１５からスキャン可能要素１１０にトラバースする際に、このカウントをゼロにリセットする。
【００１８】
ネットワーク１００で、フィードバック線は、クリア可能な要素またはクリア不能な要素を横切る可能性がある。簡単に図３を参照すると、クリア可能な要素、およびクリア不能な要素を横切るフィードバックを備えるネットワーク２００が示されている。図１に戻ると、一般に、クリア可能な要素を横切る場合に、フィードバック線は回路ネットワーク中で許容される。ただし、フィードバック・ループがクリア不能な要素を横切る場合には、設計上の制約がある。一般的に、回路ネットワーク１００中のクリア可能な要素およびクリア不能な要素を示すことにより、許容不能なフィードバック・ループの検出が可能になる。一般的にスキャン・ラッチ１１０を横切るフィードバック・ループは許容される。非スキャン・ラッチ１２０だけを横切るフィードバック・サイクルは許容されない。
【００１９】
回路１００で、最後のクリア可能な要素からの最大距離Ｄ、および回路ネットワークの入力ピンからの最大距離Ｄ内に、これらのクリア可能な要素を配置する。パラメータＤは、一般に設計基準によって定義される。例えば、最大Ｄ＝３０の論理ブロックをスキャン・ラッチ間に挿入することが許容される。フィードバック・ループがクリア可能な要素を含み、設計基準を満たせば、そのフィードバック・ループは許容可能である。フィードバック・ループが指定されたパラメータＤの範囲内にクリア可能な要素を含まない場合は、そのフィードバック・ループは容認できない。
【００２０】
図１で、ネットワーク１００の各ノード１１５ごとに、グラフ情報を、属性割当機構１１９によって記憶する。ネットワーク１００のトラバースの使用により、容認できないフィードバック・ループがネットワーク１００にあるかどうかをテストする。入力から出力までネットワーク１００をトラバースする際、論理ブロック１１５は、その属性割当機構１１９によって自身に割り当てられた属性の１つをもつ。一実施形態では、これらの属性は、色分けされる。
【００２１】
【表１】
2004198407.tif 000003
【００２２】
以下の初期条件および特別な条件の場合を除いて、ノードはそれらの先行ノードの色を継承する。一実施形態では、属性割当機構１１９は、継承した属性の割当てを実施する。回路ネットワーク１００の入力としてノードを最初にトラバースするとき、属性割当機構１１９によって、ノードに第１の属性が割り当てられる。一実施形態では、第１の属性は、ＢＬＡＣＫ（黒）色である。パスが親ノードと子論理ブロックの間のスキャン・ラッチなどクリア可能な要素１１０を通過した後、ノードには属性割当機構１１９により第２の属性が割り当てられる。一実施形態では、第２の属性はＧＲＥＥＮ（緑）色である。クリア不能な要素をトラバースが横切った後、ノードには、第３の属性が割り当てられる。一実施形態では、第３の属性はＲＥＤ（赤）色である。
【００２３】
各要素に関連する距離指標ＤＩＳＴは、距離増分器１１７により、入力のゼロの出発点から、ネットワーク１００の各ノード１１５またはスキャン不能な要素１２０に応じて増分される。距離が距離増分器１１７によってゼロにリセットされるクリア可能な要素１１０を通過した後を除いて、ノードをトラバースするたびに、この増分が行われる。したがって、ノード１１５の色がＲＥＤまたはＧＲＥＥＮの場合、各ノード１１５に関連する距離指標ＤＩＳＴは、最後のクリア可能な要素１１０までの距離の測定値である。距離指標ＤＩＳＴはまた、ノード１１５の色がＢＬＡＣＫである場合には、入力までの距離の測定値である。この距離指標ＤＩＳＴが、アーキテクチャの設計基準により設定される所定の定数値Ｄを超える場合には、設計違反が起こる。
【００２４】
図１で、論理ブロック１１５を横切るフィードバック・サイクルは、設計上の制約をもつ。この場合も、フィードバック・ループが他の設計基準を満たす場合には、スキャン・ラッチ１１０を有する論理要素のパスを横切るフィードバック・ループが許容される。非スキャン・ラッチだけを横切るフィードバック・サイクルは、許容されない。
【００２５】
図１で、論理ブロック１１５が第１、第２、または第３の属性をもつ場合には、すでに論理ブロック１１５に訪問済みである。ネットワーク１００の有向グラフをトラバースする際に、第２のノードから第１のノードに出会うと、フィードバック線を示す可能性があり、あるいは２つのパスが収束したことを示す可能性がある。その後、カウント・アナライザ１２２によって、テストを実施する。
【００２６】
例えば、元のまたは第１の論理要素に関連する属性色がＧＲＥＥＮの場合、潜在的な先行第２ノードに至る潜在的なフィードバック・ループが自動的に認められる。カウント・アナライザ１２２は、このループのテストをそれ以上実施せず、このループに、許容可能な接続とフラグを立てる。この理由は、ＧＲＥＥＮのノードを起源とするフィードバックは、スキャン可能な要素１１０を必ず横切るはずであるからである。したがって、第２のノードが第１のノードの先行ノードであるかどうかを判定する必要はなく、この動作は、一定時間内に完了する。このタイプのスキャン可能な要素１１０は、それを通過した後、そのＤＩＳＴ指標が距離増分器１１７によってゼロにリセットされることから、「クリア可能な要素」として知られている。そのクリアされるゾーン、すなわちＧＲＥＥＮのゾーン内でのフィードバックの検査は、必要ではない。
【００２７】
しかしながら、第２の、すなわち交差済みのノードが、第３の、すなわちＲＥＤの属性をもつ場合、基準違反のフィードバック・ループが存在する可能性がある。第１のノードが交差する第２のノードが現行の論理ブロックの先行ノードである場合、および第１のノードと第２のノードの間にフィードバックを基準を満たすものとするスキャン可能な要素がない場合には、基準違反のフィードバック・ループがカウント・アナライザ１２２によって検出される。
【００２８】
基準違反のフィードバック・サイクルが見つかったかどうかを判定するために、カウント・アナライザ１２２は、第１の、すなわち生成中のノードの先行リストを、交差済みの第２のノードに対応する距離まで逆にたどってトラバースする。第２のノードが第１のノードの上位ノードである場合には、基準違反のフィードバック・ループが生じる。同じＤＩＳＴ値をもつ上位ノードが第２のノードでない場合、基準違反のフィードバック・ループは生じておらず、カウント・アナライザ１２２は、許容可能なフィードバック・ループのフラグを立てる。換言すれば、カウント・アナライザ１２２によってせいぜい最後のスキャン可能な要素１１０を調査し、しかもそれ以上調査しないことによって、第１のノードと第２のノードの間に、フィードバックを許容可能にするスキャン可能な要素１１０が存在しないことを、見出すことができる。フィードバックが許容可能でない場合、設計を変更して、フィードバック・ループを取り除くか、あるいはスキャン可能な要素を挿入することにより、フィードバック・ループを許容可能なものにすることもできる。
【００２９】
以下は、先行論理要素１１５がスキャン可能な要素を確実に含むまたは含まないようにする擬似コードである。
CurrNode= Y
WHILE Distance[CurrNode] > Distance[X]DO
# Iterate back through predecessor list
CurrNode = Predecessor[CurrNode]
OD
#Distance[CurrNode] == Distance[X]
IF CurrNode == X THEN
RETURN FeedbackCycleFound
FI
RETURN FeedbackCycleNotFound
【００３０】
当業者には理解されるように、ＯＤは、ＤＯで開始されたステートメントを閉じることを意味し、同様に、ＦＩはＩＦで開始されたステートメントを閉じることを意味する。
【００３１】
距離指標ＤＩＳＴは、最後のクリア可能な要素１１０または最初の入力からの距離の測定値であり、この距離は、最大でも一定の距離Ｄにしかなり得ないので、上記動作にかかる時間はＯ（Ｄ）と一定になる。すなわち、せいぜいＤだけ先行するノードを調査して、その先行ノードが交差済みのノードＸに要求されるＤＩＳＴ値とマッチするかどうかを判定することになる。実行時間は、Ｄを定数値に設定する設計基準に依存する。例えば、スキャン・ラッチ間にはＤ＝３０個の論理ゲートを超えるものはあり得ない。
【００３２】
特定の入力に対する検索が完了すると、属性割当機構１１９および距離増分器１１７を回路ネットワークの次の入力ピンに作用させ、以下ネットワークへの入力がすべてトラバースされるまで同様に行う。距離、色、および先行指標がこのプロセス中に、ノード１１５上の要素に保存される。すなわち、１つの入力ピンに対するトラバース中に訪問され属性を割り当てられたノード１１５には、次の入力ピンのトラバース時にも、まだ以前のトラバースによる色付けが残ったままとなる。
【００３３】
次に図２を参照すると、隠れたフィードバック・ループが示されている。（ＧＲＥＥＮおよびＲＥＤ、またはＢＬＡＣＫおよびＲＥＤなど）異なる色の２つのパスが収束する場合には、このＢＦＳトラバースが、ＮＳＬを横切るフィードバックを隠すように進む可能性がある。一般に、ＲＥＤパスと非ＲＥＤパスが１つの要素で合流するときだけ、これが起こる。どちらのパスが最初にそのノードに到達しても、そのノードに色を付け、そのパスが先行要素としてリストされる。
【００３４】
図２中で、ＤＩＳＴ＝そのＢＦＳによって測定された距離である。上側のパスは、ＤＩＳＴ＝２のノードＰに到達し、このノードをＧＲＥＥＮに色付けする。ノードＰがＧＲＥＥＮであることから、このアルゴリズムでは、潜在的なフィードバックとして距離１にあるＢＬＡＣＫノードに至る出力を検査しない。したがって、そのＢＦＳでは、上側のパスについては、Ｐからの許容不能なフィードバック・ループがないと判定する。しかしながら、ノードＰに至る別のパスがＲＥＤの場合、その別のパスについては、許容不能なフィードバック・ループが存在しうる。下側のパスがノードＰに到達すると、ＲＥＤが、合流するパスで優位となり、さらに伝搬される。これによって、ノードＰおよびそれより先からの、下側のパスへ戻って行く基準違反のフィードバックの検出が可能になる。
【００３５】
ＲＥＤパスがＧＲＥＥＮおよびＢＬＡＣＫよりも優位となることから、このネットワーク中の各パスは、せいぜい２回トラバースされる。すなわち、ＧＲＥＥＮまたはＢＬＡＣＫに色付けする際に一度目、また、その後ＲＥＤが合流パスで優位となる場合に二度目のトラバースが行われる可能性がある。したがって、全体としての実行時間２＊ｎ＝Ｏ（ｎ）は、線形に留まる。
【００３６】
再び図３を参照すると、スキャン可能ラッチおよびスキャン不能ラッチを横切るフィードバック・ループを有する回路ネットワーク２００が示されている。ネットワーク２００は、入力ＩＮ０、ＩＮ１、およびＩＮ２を備える。ＩＮ０はＡＮＤゲート２１０への入力である。ＡＮＤゲート２１０の出力が、スキャン可能なラッチ（ＳＬ１）２２０およびスキャン不能ラッチ（ＮＳＬ１）２３０に入力される。次いで、ＮＳＬ出力が２入力ＡＮＤゲート２３１に入力される。２入力ＡＮＤゲートの出力が、ＡＮＤゲート２１０の入力に供給され、それによってフィードバック・ループを作る。スキャン可能ラッチ２２０の出力は、インバータ２２５によって反転される。インバータ２２５の出力は、スキャン・ラッチ２３５およびスキャン不能ラッチ２３７に入力される。スキャン・ラッチ２３５およびスキャン不能ラッチ２３７の出力は、それぞれＯＵＴ０およびＯＵＴ１である。インバータ２２５の出力はまた、３入力ＡＮＤゲート２１０の入力に入力され、それによって、別のフィードバック・ループを作る。
【００３７】
ＩＮ１およびＩＮ２は、２つの信号バッファ２４０および２４１にそれぞれ入力される。次いで、このバッファの出力が、３入力ＡＮＤゲート２４２に入力される。ＡＮＤゲート２４２の出力は、スキャン可能ラッチ２４４に入力される。スキャン可能ラッチ２４４の出力は、２入力ＡＮＤゲート２４６に入力される。ＡＮＤゲート２４６の出力は２入力ＡＮＤゲート２３１に入力され、さらにＮＳＬ３  ２４８に入力される。ＮＳＬ２４８の出力は、３入力ＡＮＤゲート２４２に入力され、それによって、フィードバック・ループを作る。さらに、ＮＳＬ２４８の出力は、ＡＮＤゲート２４６に入力され、それによって他のフィードバック・ループを作る。最後に、ＮＳＬ２４８の出力は、ＯＵＴ２にも供給される。
【００３８】
次に図４を参照すると、図３のネットワーク２００が有向グラフ２７０として表して示されている。図では、有向グラフ２７０の様々なノードが、ＲＥＤ、ＧＲＥＥＮ、ＢＬＡＣＫなどの第１、第２、および第３の属性で表されているが、当業者なら、他の色分け方式も本発明の範囲に含まれることを理解されよう。
【００３９】
設計パラメータに違反するフィードバック・ループがないかどうかをテストする際に、有向グラフ２７０は特徴付けられる。ＩＮ０からスタートして、ＳＬまたは非ＳＬラッチとまだ交差していないので、ノード１１５に対応するノード「ａ」が「ＢＬＡＣＫ」に色付けされる。ノード「ａ」におけるＤＩＳＴカウントは１である。次いで、次のラウンドのＢＦＳで、各パス２１１および２１２をトラバースし、このＢＦＳでは、ＩＮ０から距離２だけ離れた要素に着目し、ラッチなどのメモリ要素に出会う。ＳＬ（２２０）はスキャン可能であり、したがって、ＧＲＥＥＮに色付けされる。さらに、距離変数がゼロに戻る。しかしながら、パス２１２では、スキャン不能ラッチＮＳＬ（２３０）に出会うので、色がＢＬＡＣＫからＲＥＤに遷移し、距離変数が増分され、スキャン不能ラッチに記憶される。次いでＳＬ２２０は、その直前の先行要素がＧＲＥＥＮであるためにＧＲＥＥＮであるノード「ｂ」までトラバースし、このノードの距離変数が「１」に増分される。次いでＮＳＬ２３０からノード「ｃ」にトラバースする。ノード「ｃ」はその直前の先行要素がＲＥＤであるので、ＲＥＤであり、その関連する距離が「２」に増分される。
【００４０】
その結果、ノード「ｂ」の出力は、ノード「ａ」へのフィードバック・ループ中にある。ＮＳＬ３の色がＲＥＤであることから、検査を実施して、ＮＳＬ３と、すでに訪問済みであることが判明しているノード「ｅ」および「ｆ」の間にスキャン可能な要素が存在するかどうかを判定する。ＤＩＳＴカウント１を有する「ｆ」がＤＩＳＴカウント１を有する、ＮＳＬ３の上位ノードであると判定する。したがって、ノード「ｆ」へのフィードバック・ループは、許容できない。ＤＩＳＴカウント２を有する「ｅ」がＤＩＳＴカウント２を有する、ＮＳＬ３の上位ノードではないと判定する。この理由から、ＮＳＬ３とノード「ｅ」の間にスキャン可能な要素がある。実際に、ＳＬ３はＮＳＬ３とノード「ｅ」の間にあり、したがって、そのフィードバックは許容可能である。さらに、図４において、その距離は許容可能な設計制約Ｄの範囲内にあり、したがって、第２の設計の特徴が満たされる。したがって、フィードバック・ループ２１３は許容可能である。
【００４１】
図４で、ノード「ａ」がすでに関連する属性を有するので、ノード「ｃ」では、最後のスキャン可能な要素の前の同じ距離カウントをもつ上位ノードが、交差済みのノードと同じかどうかを検査して確かめる。図４に示した実施形態では、ノード「ａ」は、同じ距離カウントを有する先行ノードと同じであり、したがってこのフィードバックは基準違反である。
【００４２】
入力ＩＮ１およびＩＮ２からスタートすると、入力ノード「ｄ」および「ｇ」は共にＢＬＡＣＫである。それらのノードを、次に、ノード「ｅ」にトラバースする。このノード「ｅ」はまた、色属性、この場合はＢＬＡＣＫをその直前の先行ノードから継承する。次いで、ＢＬＡＣＫの出力をＳＬ３（２４４）に入力し、このＳＬ３で、カウントをゼロにリセットし、継承不能な属性を第２の属性ＧＲＥＥＮに変更する。この第２の、すなわちＧＲＥＥＮの属性をノード「ｆ」が継承する。ノード「ｆ」の出力はノード「ｃ」およびＮＳＬ３に入力される。
【００４３】
ノード「ｆ」すなわち起点ノードが第２の属性をもつことから、ノード「ｆ」とノード「ｃ」の間で生じるフィードバックはどれも許容可能なフィードバックである。しかしながら、ノード「ｆ」は、ＮＳＬ３への入力でもあり、それによって、この要素以降で色をＧＲＥＥＮからＲＥＤに変える。次いで、ＲＥＤの出力がノード「ｅ」に入力される。
【００４４】
ノード「ｅ」に入力された色がＲＥＤであることから、検査を実施し、スキャン可能な要素がＮＳＬ３とノード「ｅ」の間に存在するかどうか判定する。次いで、その関連する距離カウントをもつノード「ｅ」が、ＮＳＬ２４８の上位ノードと同じかどうか判定する。これら２つのノードは同じでないので、これは基準を満たすループである。
【００４５】
さらなる実施形態では、スキャン可能な要素間の論理要素の合計数がＤを超えるかどうかを判定する。一般に、基準違反のフィードバック・ループかどうかを判定するのと同じトラバースの一部として、これを実施する。一実施形態では、これは、テスト済みのノードのＤＩＳＴ値が、Ｄの許容値よりも大きいかどうか判定することにより、実施される。
【００４６】
さらなる実施形態では、組合せ論理フィードバック・ループを見つける。組合せ論理ループは、非スキャン・ラッチ・フィードバック・ループと同じ理由で、チップ・テストにとって有害である。組合せ論理ループは、一般に、そのループにどのようなメモリ要素も含まない論理ループとして定義することができる。一般に、組合せ論理ループは、その値をテスト装置によって直接に観測または変更することができない無限ループを作る。
【００４７】
一実施形態では、組合せ論理ループを見つけるために、ソース・ノードの色に関係なく、交差ノードのＤＩＳＴ値まで、先行リストを検査する。ソース・ノードが交差ノードを先行ノードであると識別する場合、このループは、組合せ論理ループ、または基準違反のＮＳＬフィードバック・ループのどちらかとなる。どちらにしても、フィードバック・ループが識別され、訂正のために報告される。１つの組合せ論理ループのテストの時間は、Ｏ（Ｄ）の一定時間となる。かかるループをすべて見つけるこの新しい方法の実行時間はＯ（Ｄ＊Ｎ）＝Ｏ（Ｎ）であり、ここでＤはＮと独立な定数値であり、Ｎはこの回路ネットワークの有向グラフ表現中の交点（ノード）の数と辺（弧）の数を加えたものに等しい。同じことであるが、これは、これらの要素間の回路要素数と相互接続数を加えたものである。
【００４８】
次に、図５および図６を参照すると、ＢＦＳアルゴリズムを使用して、回路ネットワーク中の基準違反のフィードバック・ループを検査するための方法３００が示されている。ステップ３０１から、この方法はスタートする。ステップ３０２で、回路ネットワークの入力を入力する。ステップ３０５で、距離カウント（ＤＩＳＴ）をゼロに設定する。一般に、ノードにおける距離カウントは、そのノードから、最後のスキャン可能な要素に戻るパス長である。ステップ３０７で、第１の属性にデフォルトの属性を設定する。一実施形態では、第１の属性がＢＬＡＣＫ色を含む。
【００４９】
ステップ３１０で、１つの入力または親ノードから、子ノードへの増分を行う。換言すれば、ＢＦＳトラバースにおける次の子ノードを検査する。ステップ３１４で、この方法３００では、その子ノードが以前に訪問済みかどうかを判定する。一実施形態では、その子ノードが自身に割り当てられた第１、第２、または第３の属性をもつかどうかを判定することにより、これを実施する。換言すれば、その子ノードが、それに割り当てられたＲＥＤ、ＧＲＥＥＮ、またはＢＬＡＣＫのいずれかをもつかどうか判定することによりこれを実施する。
【００５０】
その子ノードが、以前に訪問済みの場合、ステップ３２０で、この方法３００は、交差ノードがＲＥＤかどうかを判定する。交差ノードがＲＥＤの場合、ステップ３２２で交差ノードのＤＩＳＴ値を決定する。次いで、ステップ３２５で、親／起点ノードの先行ノードをステップ３２２中の交差ノードと同じＤＩＳＴ値までトラバースする。ステップ３４０で、この方法３００は、交差ノードが、その先行リスト中の同じＤＩＳＴ値を有するノードと同じノードであるかどうかを判定する。同じノードの場合には、そのフィードバックは許容できず、ステップ３４５でこの方法は停止する。しかしながら、これら２つのノードが同じでない場合、ステップ３４７で、このフィードバックを許容可能と判定する。
【００５１】
しかしながら、ステップ３２０で交差ノードがＲＥＤでないと判定された場合には、ステップ３３０で、この方法３００は親ノードがＲＥＤであるかどうかを判定する。親ノードがＲＥＤでない場合は、ステップ３４７を実行し、フィードバックが許容可能になる。しかしながら、親ノードがＲＥＤの場合、ステップ３６２を実行し、交差ノードの色を第３の属性（ＲＥＤ）に設定する。
【００５２】
ステップ３１４で、子ノードが、それ自身に関連するＲＥＤ、ＧＲＥＥＮ、またはＢＬＡＣＫの属性をもたないと判定された場合、その子ノードは以前に訪問済みではなく、ステップ３５０が実行される。ステップ３５０で、子ノードがメモリ要素かどうかを判定し、メモリ要素の場合には、それがスキャン可能メモリ要素かどうかを判定する。子ノードがスキャン可能メモリ要素の場合には、ステップ３６１で、第２の属性（ＧＲＥＥＮ）をその子ノードに対して設定する。次いで、ステップ３６４で、ＤＩＳＴカウントをゼロに設定する。子ノードがスキャン不能メモリ要素の場合には、ステップ３６２で、その子ノードに対して第３の属性（ＲＥＤ）を設定する。ステップ３５０で子ノードがメモリ要素でない場合、ステップ３６３で、子ノードは、その親ノードからその色を継承する。ステップ３６２またはステップ３６３のいずれの場合にも、ステップ３６５で、その子ノードのＤＩＳＴをその親ノードのＤＩＳＴ＋１に等しくなるように設定する。ステップ３７０で、ステップ３６４またはステップ３６５のいずれの場合にも、子ノードの先行属性中の親ノードに対するポインタなど、親ノードの標識（indicia）（すなわち、第１、第２、または第３の属性）を、子ノードの先行属性中に記憶する。一般に、ノードごとに１つのかかる値を記憶する。
【００５３】
ステップ３４７またはステップ３７０の実行後、次いで、この方法３００は、ステップ３７５で、親ノードが他に調べるべき子ノードがあるかどうかを判定する。調べるべき子ノードがある場合、ステップ３１０を再実行し、次の子ノードを調べる。子ノードがない場合には、ステップ３８０で、この方法３００では、他にテストすべきノードが残っているかどうかを判定する。基準違反のフィードバックがないかどうかテストすべきノードがさらにある場合、ステップ３８２で、このＢＦＳは、次のノードに移行する。次のノードの決定は、実装に特有なものである。一般に、各ノードでは、その子へのポインタのリストを記憶する。この子のリストを介して繰り返しを行った後、待ち行列の最上要素をポップすることにより、次のノードを入手することが可能であり、ステップ３１０を再実行する。テストすべきノードがない場合、次いでステップ３８５で、その回路ネットワークに何かさらに入力があるかどうかを判定する。さらに入力がある場合、ステップ３０２で、再び新しい入力を入力し、このフローを再実行する。入力のない場合、ステップ３９０で、この方法が実行されたことを示し、プログラムを終了する。
【００５４】
さらなる実施形態では、入力から回路ネットワークに対して深さ優先トラバース（depthfirst traversal）を実施する。深さ優先検索（ＤＦＳ）は、所与のパスの端部まで移動した後、戻って次のパスの端部へと移動する。このＤＦＳの属性は以下のようである。
【００５５】
【表２】
2004198407.tif 000004
【００５６】
表１のＢＦＳの距離、先行要素、および色属性は、実質上表２のＤＦＳに相当する。しかしながら、ＤＦＳは、２つの追加の特徴を有する。これらは、「状態」属性および「ＺＯＮＥ＿ＩＤ」属性である。
【００５７】
属性を割り当てるトラバース中で出会う前には、各ノードはＮＵＬＬ／ＮＯＴ  ＶＩＳＩＴＥＤの状態をもつ。最初に訪れたとき、ノードはＮＯＴ＿ＦＩＮＩＳＨＥＤと示されている。その子ノードのすべてがそれらの深さ優先トラバースを完了してしまうまで、ノードにはＦＩＮＩＳＨＥＤとマークされない。
【００５８】
このＺＯＮＥ＿ＩＤは、論理ブロックに至るパス上で見出される最後のスキャン可能ラッチに割り当てられる固有のＩＤである。スキャン可能ラッチ（ＳＬ）を通過した後、それに続くパス上の論理ブロックは、パスが異なるＳＬを通過するまでは、所与のゾーンの内側にある。
【００５９】
トラバース中に、第１のノードが、それに関連する属性をすでに有する第２のノードに出会う場合には、第２のノードの状態を読み出すことにより、第２のノードが先行ノードであるかどうかを判定することができる。第２のノードの状態が、ＮＯＴ＿ＦＩＮＩＳＨＥＤに等しい場合には、第２のノードは先行ノードであり、フィードバックが見つかっている。これが基準違反のフィードバック・ループか、それとも許容可能なフィードバック・ループかを判定するために、第１および第２のノードのＺＯＮＥ＿ＩＤを比較する。第２のノードのＺＯＮＥ＿ＩＤが第１のノードのＺＯＮＥ＿ＩＤと等しい場合には、どのスキャン可能な要素も横切らないフィードバック・ループが見つかっている。したがって、このフィードバック・ループは、許容されない（すなわち、基準違反である）。
【００６０】
第２のノードのＺＯＮＥ＿ＩＤが第１のノードのＺＯＮＥ＿ＩＤに等しくない場合は、第１のノードと第２のノードの間にはスキャン可能な要素があり、フィードバックが許容される。これは、そのＺＯＮＥ＿ＩＤの定義に従う。この定義は、スキャン可能な要素を起点とするすべてのパスに沿ったノードが、そのスキャン可能な要素のＺＯＮＥ＿ＩＤを継承するということである。これは、これらのパスが、異なるスキャン可能な要素を通過するまで続き、その要素中でそれらのノードは異なるＺＯＮＥ＿ＩＤを得る。
【００６１】
ＤＦＳおよびＢＦＳは、グラフをトラバースする２つの基本的な広く使用されている方法である。両方のトラバースを使用して、ＮＳＬだけを横切るフィードバックを検出するための方法を提供することによって、本発明をより容易に既存のマイクロエレクトロニクスの設計ツールおよび設計方法に統合することができる。
【００６２】
ＤＦＳを使うかＢＦＳを使うかは実装に特有であり、回路ネットワークの何らかの知識に依存する可能性がある。例えば、その深さに対して相対的に広いファンアウトをもつ回路ネットワークでは、大きなＢＦＳの待ち行列および比較的小さなＤＦＳスタックを必要とするはずである。逆に言えば、小さなファンアウトおよび相対的に長い深さを有する回路ネットワークでは、ＢＦＳ待ち行列よりも大きなＤＦＳスタックを必要とするはずである。これは、システム・メモリが制限するボトルネックである場合に重要となる可能性がある。
【００６３】
次に図７を参照すると、２つのネットワーク４１０および４２０が示されている。システム・オン・チップを含め大規模な集積回路設計は、多くの相互接続モジュールまたはネットワークから構成することができる。図７では、それぞれ基準違反のＮＳＬフィードバック・ループがないネットワーク４１０と４２０を接続すると、基準違反のＮＳＬフィードバック・ループが形成される。
【００６４】
さらなる実施形態では、かかる問題を回避するために、ネットワーク４１０および４２０で、ＮＳＬを横切る好ましくないフィードバック・ループがないことが検証されると、その結果得られる合成回路ネットワークにもまた、バウンダリ違反がないことが確認される。以上は、以下のバウンダリ・ルールにより実現することができる。
【００６５】
１）スキャン不能な要素に到達する以前に、どの入力パス上でもスキャン可能な要素に到達する。これが「入力」ルールである。２）スキャン可能な要素は出力パス上で見出される最後のラッチである。これが「出力」ルールである。換言すれば、スキャン不能な要素を最後に（すなわち、スキャン可能な要素の後で）見出すことはできない。３）最後に、ラッチは、パス上のある点で、出力される以前に見出されるべきである。これが、「ラッチ」ルールである。
【００６６】
この入力ルールおよび出力ルールを複数のネットワーク４１０および４２０の設計で使用する場合には、ネットワーク４１０と４２０が接続されたときに、フィードバック・ループがＮＳＬだけを横切ることはなくなる。一般的に、入力ルールまたは出力ルールをラッチ・ルールと一緒に適用すると、第１のモジュールの出力と、第２のモジュールの入力へのその接続の間にはどのようなＮＳＬも存在し得ず、したがって基準違反のフィードバック・ループの可能性はない。
【００６７】
このさらなる実施形態では、２３５、２３７、２４８などのバウンダリ・ラッチの少なくとも一部が、ネットワーク２００などのあらゆる大きな機能ユニット間でスキャン可能である。これは、ラッチ２２０、２３０、２４４など任意の入力パスに沿ってトラバースされる少なくとも第１のラッチがスキャン可能であることを意味する。さらなる実施形態では、ラッチ２３５、２３７、２４８など、任意の出力上で見出される最後のラッチがスキャン可能である。さらに別の実施形態では、スキャン・ラッチを第１の入力ラッチとしても最後の出力ラッチとしても配置することができる。この構成では、ネットワーク２００の入力に対する制御、および期待される結果と一致するすべての出力の観測が可能になる。これら３つのバウンダリ・スキャンの実施形態のうちのどれによっても、複数の合成ネットワーク２００中で使用する場合には、ＮＳＬだけを横切るフィードバック・ループがネットワーク２００中には存在できないことが保証されることになる。図５に、これがどのように生じ得るかを示す。出力ルールだけが適用される場合、この場合にも、ラッチ・ルールを適用したと仮定して、ネットワーク４１０および４２０が接続されるときにＮＳＬだけを横切るフィードバック・ループが発生し得ないことを保証するのにこれで十分である。
【００６８】
バウンダリ・ルールを実施するためには、入力ルールで、第１の属性から第３の属性への、例えばＢＬＡＣＫからＲＥＤへの色の遷移がないことを保証することが必要である。かかる遷移は、入力パス上のクリア可能な要素の前に入力ルールの下で許容されないクリア不能な要素に出会ったことを示している。出力ルールを実施するために、最後のノード（出力ピンに接続されたノード）の属性色はＲＥＤ、すなわち第３の属性であってはならない。その属性色がＲＥＤである場合、出力パス上に見られる最後のラッチはスキャン可能でなかったことになる。ラッチ・ルールを実施するには、最後のノードの色は、ＧＲＥＥＮまたはＲＥＤでなければならない。これにより、入力から出力へに至るパス上にラッチがあることが保証される。
【００６９】
しかしながら、基準違反のフィードバック・ループの発見は、通信ネットワーク、電力網、コンピュータ・ネットワーク、制御ネットワークなどに適用することができることが当業者には理解されよう。換言すれば、本発明は、内部にフィードバックが存在するネットワークに適用することができる。
【００７０】
次に図８および図９を参照すると、本発明に記載の方法のうちのＢＦＳおよびＤＦＳをそれぞれ実施するためのソースおよび擬似コードが示されている。入力および出力のバウンダリ検査が実施される。設計基準検証も実施される。これにより、非スキャン・ラッチ間の距離が所定の値Ｄ＝ＭＡＸ＿ＤＩＳＴを決して超過しないことが保証される。
【００７１】
図８で、回路ネットワークの有向グラフ表現上で、手続きＦｉｎｄ＿Ａｌｌ＿Ｆｅｅｄｂａｃｋ（）を呼び出す。そこから、幅優先検索（ＢＦＳ）は、グラフをトラバースし、フィードバック・ループを探す。非スキャン・ラッチだけを横切るフィードバック・ループのすべてが、線形のＯ（Ｎ）時間中に見出される。Ｎ＝｜Ｖ｜＋｜Ｅ｜、すなわちノード数と辺の数とを加えたもの、または同じことであるが、回路要素数と回路要素間の相互接続／配線の数とを加えたものである。図９のさらなる実施形態では、深さ優先検索（ＤＦＳ）が、グラフをトラバースし、フィードバック・ループを探す。
【００７２】
本発明が、多くの形態および実施形態を取り得ることが理解されよう。したがって、本発明の趣旨または範囲を逸脱することなく、前記記述にいくつかの変形を施すことができる。例えば、様々な通信規格を実装することなどができる。
【００７３】
以上、本発明を、その好ましい実施形態のいくつかに関して説明してきたが、開示の実施形態は限定的ではなく、例示的な性質のものであること、広範囲の変形形態、修正形態、変更形態、代替形態が、前記開示中で企図されていること、また、ある場合には、他の特徴を対応して使用することなく、本発明の一部の特徴を使用することができることに留意されたい。かかる変形形態および修正形態の多くは、好ましい実施形態の前記記述を吟味すれば、当業者には自明であり、望ましいものと考えることができよう。したがって、添付の特許請求の範囲を、広義に、また本発明の範囲と一致するように解釈することが妥当である。
【００７４】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００７５】
（１）クリア不能な要素のみを横切るフィードバック・ループを見つけるためのシステムであって、
少なくとも１つの上位ノードの距離カウントを記録するために使用可能な第１のノードと、
距離カウントを有する第２のノードと、
前記第１のノードを前記第２のノードに接続する接続部と、
それ自体の距離カウントを有する前記第２のノードが、前記第１のノードの、同じ前記距離カウントを有する記録済みの前記上位ノードと同じノードであるかどうかを判定するために使用可能なカウント・アナライザと
を備えるシステム。
（２）前記第１のノードに結合されたスキャン可能な要素をさらに備える、上記（１）に記載のシステム。
（３）前記第１のノードと前記第２のノードの間に複数のノードをさらに備え、各ノードが別々の距離カウントを有する、上記（１）に記載のシステム。
（４）前記第２のノードと前記第１のノードの間の諸ノードに関連する関連カウントが、ノードからノードへと増分される、上記（３）に記載のシステム。
（５）前記第２のノードが前記上位ノードと同じ場合に、前記カウント・アナライザが、前記ループに許容不能とフラグを立てるために使用可能である、上記（１）に記載のシステム。
（６）前記第１のノードと前記第２のノードの間に挿入されたスキャン可能な要素をさらに備える、上記（１）に記載のシステム。
（７）前記スキャン可能な要素がラッチである、上記（６）に記載のシステム。
（８）前記スキャン可能な要素が、前記距離カウントをゼロにリセットするために使用可能である、上記（５）に記載のシステム。
（９）前記フィードバック・ループが、電力網、通信ネットワーク、またはバス相互接続中にある、上記（１）に記載のシステム。
（１０）ネットワーク中で、フィードバック条件の標識を生成する方法であって、
親論理ノードと子論理ノードの間にメモリ要素があるかどうかを判定するステップと、
メモリ要素がある場合、前記メモリ要素がスキャン可能なメモリ要素である場合に前記子論理ノードに第２の属性を割り当てるステップと、
メモリ要素がある場合、前記メモリ要素がスキャン不能なメモリ要素である場合に前記子論理ノードに第３の属性を割り当てるステップと、
前記親論理ノードの距離に１を加えた距離を前記子論理ノード中に記憶するステップと、
前記親論理ノードの前記標識を前記子論理ノード中に記憶するステップと
を含む方法。
（１１）第１の属性を入力から第１の論理要素に割り当てるステップをさらに含み、前記第１の属性が、トラバース中にメモリ要素に出会わなかったことを示す、上記（１０）に記載の方法。
（１２）前記親論理ノードと前記子論理ノードの間にあるスキャン可能なメモリ要素の挿入に関して、要素の関連カウントをゼロにリセットするステップをさらに含む、上記（１０）に記載の方法。
（１３）前記子論理ノードと前記親論理ノードの間に挿入されたメモリ要素がない場合、前記子論理ノードが前記親論理ノードから前記属性を継承するステップをさらに含む、上記（１０）に記載の方法。
（１４）基準違反のフィードバック・ループを判定する方法であって、
第１のノードを選択するステップと、
第１、第２、または第３の属性を有する第２のノードを選択するステップと、
前記第１のノードから前記第２のノードへの接続部を作成するステップと、
前記第２のノードが前記第２の属性を有する場合に、許容可能な接続部として前記接続部にフラグを立てるステップと
を含む方法。
（１５）第２の属性を有するノードを選択する前記ステップが、第１のノードから第２のノードへのトラバース中に少なくとも１つのメモリ要素に出会うことを示す、上記（１４）に記載の方法。
（１６）第３の属性を有するノードを選択する前記ステップが、スキャン不能なメモリ要素が、前記第１のノードから前記第２のノードへのトラバース中に出会った最後のメモリ要素であったことを示す、上記（１４）に記載の方法。
（１７）前記許容可能な接続部が許容可能なフィードバック・ループを構成する、上記（１４）に記載の方法。
（１８）前記第２のノードが前記第３の属性を有する場合に、
前記第２のノードにある前記距離カウント値を検索するステップと、
前記第２のノードと同じカウント値を有する前記第１のノードの上位ノードの標識を検索するステップと、
前記第２のノードと前記同じカウントを有する前記上位ノードが同じノードでない場合に、許容可能なループとして前記ループにフラグを立てるステップと、
前記第２のノードと前記同じカウントを有する前記上位ノードが同じノードである場合に、許容不能なフィードバック・ループとして前記フィードバック・ループにフラグを立てるステップと
をさらに含む、上記（１４）に記載の方法。
（１９）２つのクリア可能な要素間に所定数より多くの論理ノードおよびスキャン不能な要素がある場合に、設計違反のフラグを立てるステップをさらに含む、上記（１４）に記載の方法。
（２０）複数の集合回路ネットワークが許容可能なフィードバック・ループを有することを判定する方法であって、
第１のネットワークが、前記第１のネットワーク中に許容不能なフィードバック・ループを有するかどうかを判定するステップと、
第２のネットワークが、前記第２のネットワーク中に許容不能なフィードバック・ループを有するかどうかを判定するステップと、
前記第１および第２のネットワーク内で各ネットワークの各入力と各出力の間に配置された、少なくとも１つのスキャン可能なメモリ要素を必要とするステップと
を含む方法。
（２１）前記第１および第２のネットワークの両者の内部にスキャン不能な要素を配置する前に、入力パス上にスキャン可能な要素を配置することをさらに含む、上記（２０）に記載の方法。
（２２）前記第１および第２のネットワークの両者の内部に出力の前に最後のメモリ要素としてスキャン可能な要素を配置することをさらに含む、上記（２０）に記載の方法。
（２３）スキャン可能な要素がスキャン不能な要素の前の入力パス上に挿入されているという要件、およびスキャン可能なラッチが前記第１および第２のネットワークの両者の出力の前の最後のメモリ要素であるという要件の両方をスキャン・メモリ・ルールが含む、上記（２０）に記載の方法。
（２４）深さ優先検索を使用して基準違反のフィードバック・ループを見つける方法であって、
上位論理ノードと子論理ノードの間にメモリ要素があるかどうかを判定するステップと、
メモリ要素がある場合、前記メモリ要素がスキャン可能なメモリ要素である場合に前記子論理ノードに第１の属性を割り当てるステップと、
メモリ要素がある場合、前記メモリ要素がスキャン不能なメモリ要素である場合に前記子論理ノードに第２の属性を割り当てるステップと、
前記子論理ノードの関連カウントを増分するステップと、
子論理ノードに対して、ＮＯＴ＿ＦＩＮＩＳＨＥＤまたはＦＩＮＩＳＨＥＤの状態を生成するステップと、
親ノードからのパス上で出会った最後のスキャン可能な要素に対して、増分スキャン・カウント標識を生成するステップと、
下位の論理ノードが前記増分スキャン・カウントを継承するステップと
を含む方法。
（２５）基準違反のフィードバック・ループを判定する方法であって、
第１のノードを選択するステップと、
第２のノードを選択するステップと、
前記第１のノードから前記第２のノードへの接続部を作るステップと、
前記第２のノードが第１、第２、または第３の属性をもたない場合に、許容可能な接続部として前記接続部にフラグを立てるステップと、
前記第２のノードが第１、第２、または第３の属性をもつ場合には、
前記第２のノードが完了済みの状態をもつ場合に、許容可能な接続部として前記接続部にフラグを立てるステップと、
前記第２のノードが未完了の状態をもつ場合に、前記第１のノードおよび前記第２のノードが同一の増分ＺＯＮＥ＿ＩＤを有するかどうかを判定するステップと、
前記第１および第２のノードが共に同一の増分ＺＯＮＥ＿ＩＤをもつ場合に、前記接続部に許容不能な接続部とフラグを立てるステップと、
前記第１および第２のノードが異なる増分ＺＯＮＥ＿ＩＤをもつ場合に、前記接続部に許容可能な接続部とフラグを立てるステップと
を含む方法。
（２６）ネットワーク中のフィードバック条件の標識を生成するためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品が、コンピュータ・プログラムをその上で実施する媒体を有しており、前記コンピュータ・プログラムが、
親論理ノードと子論理ノードの間にメモリ要素があるかどうかを判定するコンピュータ・コードと、
メモリ要素がある場合、前記メモリ要素がスキャン可能なメモリ要素である場合に前記子論理ノードに第１の属性を割り当てるコンピュータ・コードと、
メモリ要素がある場合、前記メモリ要素がスキャン不能なメモリ要素である場合に前記子論理ノードに第２の属性を割り当てるコンピュータ・コードと、
前記子論理ノードの関連カウントを増分するコンピュータ・コードと、
前記子論理ノード中に、前記親論理ノードの関連カウントおよび前記親論理ノードの標識を記憶するコンピュータ・コードと
を含むコンピュータ・プログラム製品。
（２７）ネットワーク中のフィードバック条件の標識を生成するプロセッサであって、前記プロセッサがコンピュータ・プログラムを含み、前記コンピュータ・プログラムが、
親論理ノードと子論理ノードの間にメモリ要素があるかどうかを判定するコンピュータ・コードと、
メモリ要素がある場合、前記メモリ要素がスキャン可能なメモリ要素である場合に前記子論理ノードに第１の属性を割り当てるコンピュータ・コードと、
メモリ要素がある場合、前記メモリ要素がスキャン不能なメモリ要素である場合に前記子論理ノードに第２の属性を割り当てるコンピュータ・コードと、
前記子論理ノードの関連カウントを増分するコンピュータ・コードと、
前記子論理ノード中に、前記親論理ノードの関連カウントおよび前記親論理ノードの標識を記憶するコンピュータ・コードと
を含むプロセッサ。
（２８）基準違反のフィードバック・ループを判定するためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品が、コンピュータ・プログラムをその上で実施する媒体を有しており、前記コンピュータ・プログラムが、
第１のノードを選択するコンピュータ・コードと、
第１、第２、または第３の属性を有する第２のノードを選択するコンピュータ・コードと、
前記第１のノードから前記第２のノードへの接続部を作成するコンピュータ・コードと、
前記第２のノードが前記第２の属性を有する場合に、許容可能な接続部として前記接続部にフラグを立てるコンピュータ・コードと
を含むコンピュータ・プログラム製品。
（２９）基準違反のフィードバック・ループを判定するプロセッサであって、前記プロセッサがコンピュータ・プログラムを含み、前記コンピュータ・プログラムが、
第１のノードを選択するコンピュータ・コードと、
第１、第２、または第３の属性を有する第２のノードを選択するコンピュータ・コードと、
前記第１のノードから前記第２のノードへの接続部を作成するコンピュータ・コードと、
前記第２のノードが前記第２の属性を有する場合に、許容可能な接続部として前記接続部にフラグを立てるコンピュータ・コードと
を含むプロセッサ。
【図面の簡単な説明】
【００７６】
【図１】スキャン可能要素およびスキャン不能要素を含む有向マップを示す概略図である。
【図２】隠れたフィードバック・ループを含む有向マップを示す概略図である。
【図３】スキャン可能ラッチおよびスキャン不能ラッチを横切るフィードバック・ループを含む回路ネットワークを示す概略図である。
【図４】有向グラフとして表現された回路ネットワークを示す概略図である。
【図５】基準違反のフィードバック・ループを検査する方法を示す図である。
【図６】基準違反のフィードバック・ループを検査する方法を示す図である。
【図７】２つの結合ネットワークを示す概略図である。
【図８】ＢＦＳトラバース用の擬似コードを示す図である。
【図９】ＤＦＳトラバース用の擬似コードを示す図である。
【符号の説明】
【００７７】
１００  回路ネットワーク
１１０  スキャン可能な要素、クリア可能な要素
１１５  論理ブロック
１１７  距離増分器
１１９  属性割当機構
１２０  スキャン不能な要素、クリア不能な要素
１２２  カウント・アナライザ
１２５  ノード
２００  回路ネットワーク
２１０  ＡＮＤゲート
２１１  パス
２１２  パス
２２０  スキャン可能ラッチ、ＳＬ
２２５  インバータ
２３０  スキャン不能ラッチ
２３１  ２入力ＡＮＤゲート
２３５  スキャン・ラッチ
２３７  スキャン不能ラッチ
２４０  信号バッファ
２４１  信号バッファ
２４２  ３入力ＡＮＤゲート
２４４  スキャン可能ラッチ
２４６  ２入力ＡＮＤゲート
２４８  スキャン不能ラッチ、ＮＳＬ
２７０  有向グラフ
３００  方法
【図１】
2004198407.tif 000005
【図２】
2004198407.tif 000006
【図３】
2004198407.tif 000007
【図４】
2004198407.tif 000008
【図５】
2004198407.tif 000009
【図６】
2004198407.tif 000010
【図７】
2004198407.tif 000011
【図８】
2004198407.tif 000012
【図９】
2004198407.tif 000013