(57)【特許請求の範囲】
【請求項１】
試験ベクトルのセットであるベクトル・セットを生成する方法であって、前記ベクトル・セットがシーケンシャル回路を試験するために使用され、前記方法は下記ステップを備える。
ａ）前記シーケンシャル回路の縮退故障モデル、ディレー故障モデル、ブリッジ故障モデルを含む複数個の故障モデルを選択し、
ｂ）前記複数個の故障モデルの各々について識別すべき故障を含む故障リストを１つずつ識別し、
ｃ）前記故障リストの各々についてベクトル・セットを１つずつ識別し、
ｄ）前記故障リストの各々について許容限度値を１つずつ選択し、それにより、各故障モデルが故障リスト、ベクトル・セット、および許容限界値を１つずつ有し、
ｅ）前記ベクトル・セットの各々を、圧縮済みベクトル・セットが故障リスト内のすべての故障を識別するか、前記ベクトル・セットによって検出される故障数である故障カバレージの低下が許容限界値の範囲内にとどまるように圧縮し、及び
ｆ）ステップｅで圧縮されたすべてのベクトル・セットを結合することにより１つのベクトル・セットを作成する。
【請求項２】
前記許容限界値の少なくとも１つが計算資源に基づくことを特徴とする請求項１に記載のベクトル・セットを生成する方法。
【請求項３】
前記許容限界値の少なくとも１つが故障カバレージから除去された故障の数に基づくことを特徴とする請求項１に記載のベクトル・セットを生成する方法。
【請求項４】
前記許容限界値の少なくとも１つが電力使用量に基づくことを特徴とする請求項１に記載のベクトル・セットを生成する方法。
【請求項５】
前記許容限界値の少なくとも１つが熱放散に基づくことを特徴とする請求項１に記載のベクトル・セットを生成する方法。
【請求項６】
前記試験ベクトルから構成されるセグメントの構築中に故障が除去され、除去される故障の数がセグメントのサイズに比例することを特徴とする請求項１に記載のベクトル・セットを生成する方法。
【請求項７】
前記ベクトル・セットの圧縮処理が複数回の反復から成り、前記許容限界値の各々は動的であり、前記複数回の反復のうち少なくとも１回の反復に関して変更でき、前記許容限界値のうち少なくとも１つがゼロでありうることを特徴とする請求項１に記載のベクトル・セットを生成する方法。
【請求項８】
前記計算資源はＣＰＵ使用量であることを特徴とする請求項２に記載のベクトル・セットを生成する方法。
【請求項９】
前記計算資源はメモリー使用量であることを特徴とする請求項２に記載のベクトル・セットを生成する方法。
【請求項１０】
試験生成装置を備えるＶＬＳＩ回路を試験するための試験システムであって、試験生成装置はさらに下記要件を備える。
前記ＶＬＳＩ回路の縮退故障モデル、ディレー故障モデル、ブリッジ故障モデルを含む複数個の故障モデルを選択するための故障モデル選択装置、
前記複数個の故障モデルの各々について故障リストを１つずつ識別するための故障リスト識別装置、
前記故障リストの各々について試験ベクトルのセットであるベクトル・セットを１つずつ識別するためのベクトル・セット識別装置、
前記故障リストの各々について許容限度値を１つずつ選択するための許容限界値選択装置であって、それにより、各故障モデルが故障リスト、ベクトル・セット、および許容限界値を１つずつ有する許容限界値選択装置、
前記ベクトル・セットの各々を、圧縮済みベクトル・セットが故障リスト内のすべての故障を識別するか、前記ベクトル・セットによって検出される故障数である故障カバレージの低下が許容限界値の範囲内にとどまるように圧縮するための除去済み故障圧縮装置、
すべての圧縮済みベクトル・セットを結合するためのベクトル・セット作成装置。
【請求項１１】
前記許容限界値の少なくとも１つが計算資源に基づくことを特徴とする請求項１０に記載の試験システム。
【請求項１２】
前記許容限界値の少なくとも１つが前記故障カバレージから除去された故障の数に基づくことを特徴とする請求項１０に記載の試験システム。
【請求項１３】
前記許容限界値の少なくとも１つが電力使用量に基づくことを特徴とする請求項１０に記載の試験システム。
【請求項１４】
前記許容限界値の少なくとも１つが熱放散に基づくことを特徴とする請求項１０に記載の試験システム。
【請求項１５】
セグメント構築中に故障が除去され、除去される故障の数がセグメントのサイズに比例することを特徴とする請求項１０に記載の試験システム。
【請求項１６】
計算資源がＣＰＵ使用量であることを特徴とする請求項１１に記載の試験システム。
【請求項１７】
前記計算資源がメモリー使用量であることを特徴とする請求項１１に記載の試験システム。
【請求項１８】
コンピューター・プログラム製品であって、ＶＬＳＩ試験装置がＶＬＳＩ回路を試験できるようにする試験プログラムを格納するコンピューター読み取り可能な記録媒体であって、前記試験プログラムは下記ステップを備える。
コンピューターが前記ＶＬＳＩ回路の縮退故障モデル、ディレー故障モデル、ブリッジ故障モデルを含む複数個の故障モデルを選択できるようにするための故障モデル選択ステップ、
コンピューターが前記複数個の故障モデルの各々について故障リストを１つずつ識別できるようにするための故障リスト識別ステップ、
コンピューターが前記故障リストの各々について試験ベクトルのセットであるベクトル・セットを１つずつ識別できるようにするためのベクトル・セット識別ステップ、
コンピューターが前記故障リストの各々について許容限度値を１つずつ選択できるようにするための許容限界値選択ステップであって、それにより、各故障モデルが故障リスト、ベクトル・セット、および許容限界値を１つずつ有する許容限界値選択ステップ、
コンピューターが前記ベクトル・セットの各々を、圧縮済みベクトル・セットが故障リスト内のすべての故障を識別するか、前記ベクトル・セットによって検出される故障数である故障カバレージの低下が許容限界値の範囲内にとどまるように圧縮できるようにするための除去済み故障圧縮ステップ、
コンピューターがすべての圧縮済みベクトル・セットを結合できるようにするためのベクトル・セット作成ステップ。
【請求項１９】
前記許容限界値の少なくとも１つが計算資源に基づくことを特徴とする請求項１８に記載のコンピューター・プログラム製品。
【請求項２０】
前記許容限界値の少なくとも１つが前記故障カバレージから除去された故障の数に基づくことを特徴とする請求項１８に記載のコンピューター・プログラム製品。
【請求項２１】
前記許容限界値の少なくとも１つが電力使用量に基づくことを特徴とする請求項１８に記載のコンピュータ・プログラム製品。
【請求項２２】
前記許容限界値の少なくとも１つが熱放散に基づくことを特徴とする請求項１８に記載のコンピュータ・プログラム製品。
【請求項２３】
セグメント構築中に故障が除去され、除去される故障の数がセグメントのサイズに比例することを特徴とする請求項１８に記載のコンピュータ・プログラム製品。
【請求項２４】
前記計算資源がＣＰＵ使用量であることを特徴とする請求項１９に記載のコンピュータ・プログラム製品。
【請求項２５】
前記計算資源はメモリー使用量であることを特徴とする請求項１９に記載のコンピュータ・プログラム製品。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プルーニングおよびクリティカル故障除去の使用によるシーケンシャル回路試験用ベクトルのセグメント化圧縮のためのベクトル・セット生成方法、試験ベクトルを圧縮するための試験システム、およびコンピューターがセグメント化圧縮を実行できるようにするための試験プログラムを格納する記録媒体に関する。
【０００２】
【従来の技術】
回路は、試験ベクトルから成る試験セットを使用して試験される。試験中、試験セット内の試験ベクトルは、試験装置によって回路に適用される。回路によって生成された出力が検査され、回路内に何らかの故障が存在しているかどうかが判断される。いうまでもなく、シーケンシャル回路の試験コストは、試験セット内の試験ベクトルの数に直接比例する。つまり、試験ベクトルの数が多いほど、必要とされる時間と資源が増え、それにともなって試験コストが増大するのである。そのため、試験シーケンスは短いのが望ましい。試験セットのサイズは、静的または動的試験セット圧縮アルゴリズムを使用して縮小できる。
【０００３】
シーケンシャル回路の静的圧縮方式については、これまでにいくつかの提案がなされている。Ｔ．Ｍ．  Ｎｉｅｒｍａｎｎ，  Ｒ．Ｋ．  Ｒｏｙ，  Ｊ．Ｈ．Ｐａｔｅｌ，  ａｎｄ  Ｊ．Ａ．  Ａｂｒａｈａｍ，  ”Ｔｅｓｔ  ｃｏｍｐａｃｔｉｏｎ  ｆｏｒ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ（シーケンシャル回路に関する試験圧縮），”  ＩＥＥＥ  Ｔｒａｎｓ．  Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ，  ｖｏｌ．１１，  ｎｏ．２，  ｐｐ．２６０−２６７，  Ｆｅｂ．  １９９２、Ｂ．  Ｓｏ，  ”Ｔｉｍｅ−ｅｆｆｉｃｉｅｎｔ  ａｕｔｏｍａｔｉｃ  ｔｅｓｔ  ｐａｔｔｅｒｎ  ｇｅｎｅｒａｔｉｏｎ  ｓｙｓｔｅｍ（省時間自動試験パターン生成システム），”  ウィスコンシン大学マディソン校電気工学部博士論文（１９９４）、Ｉ．  Ｐｏｍｅｒａｎｚ  ａｎｄ  Ｓ．Ｍ．  Ｒｅｄｄｙ，  ”Ｏｎ  ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎｏｆ  ｔｅｓｔ  ｓｅｑｕｅｎｃｅｓ  ｆｏｒ  ｓｙｎｃｈｒｏｎｏｕｓ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ（同期シーケンシャル回路に関する試験シーケンスの静的圧縮について），”  Ｐｒｏｃ．  Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆ．  ｐｐ．２１５−２２０，  Ｊｕｎｅ  １９９６、Ｍ．Ｓ．  Ｈｓｉａｏ，  Ｅ．Ｍ．  Ｒｕｄｎｉｃｋ，  ａｎｄ  Ｊ．Ｈ．  Ｐａｔｅｌ，  ”Ｆａｓｔ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｏｆ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔ  ｔｅｓｔ  ｖｅｃｔｏｒｓ（シーケンシャル回路試験ベクトルの静的圧縮のための高速アルゴリズム），”  Ｐｒｏｃ．  ＩＥＥＥ  ＶＬＳＩ  Ｔｅｓｔ  Ｓｙｍｐ．，  ｐｐ．１８８−１９５，  Ａｐｒ．  １９９５、Ｍ．Ｓ．  Ｈｓｉａｏ  ａｎｄ  Ｓ．Ｔ．  Ｃｈａｋｒａｄｈａｒ，  ”Ｓｔａｔｅ  ｒｅｌａｘａｔｉｏｎ  ｂａｓｅｄ  ｓｕｂｓｅｑｕｅｎｃｅ  ｒｅｍｏｖａｌ  ｆｏｒ  ｆａｓｔ  ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｉｎ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ（シーケンシャル回路における高速静的圧縮のための状態緩和に基づくサブシーケンスの削除），”  Ｄｅｓｉｇｎ，  Ａｕｔｏｍａｔｉｏｎ  ａｎｄ  Ｔｅｓｔ  ｉｎ  Ｅｕｒｏｐｅ（ＤＡＴＥ）  議事録所収，  Ｆｅｂｒｕａｒｙ，  １９９８、およびＲ．  Ｇｕｏ，  Ｉ．  Ｐｏｍｅｒａｎｚａ  ａｎｄ  Ｓ．Ｍ．  Ｒｅｄｄｙ，  ”Ｐｒｏｃｅｄｕｒｅｓ  ｆｏｒ  ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｏｆ  ｔｅｓｔ  ｓｅｑｕｅｎｃｅｓ  ｆｏｒ  ｓｙｎｃｈｒｏｎｏｕｓ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ  ｂａｓｅｄ  ｏｎ  ｖｅｃｔｏｒ  ｒｅｓｔｏｒａｔｉｏｎ（同期シーケンシャル回路に関する試験シーケンスのベクトル復元に基づく静的圧縮プロシージャー），”  Ｄｅｓｉｇｎ，Ａｕｔｏｍａｔｉｏｎ  ａｎｄ  Ｔｅｓｔ  ｉｎ  Ｅｕｒｏｐｅ（ＤＡＴＥ）議事録所収，  Ｆｅｂｒｕａｒｙ，  １９９８参照。
【０００４】
上記の方式の一部は、ランダム・ベースまたはシミュレーション・ベースの試験生成装置で生成された試験セットを縮小することができない。その理由は、Ｔ．Ｍ．  Ｎｉｅｒｍａｎｎ，  Ｒ．Ｋ．  Ｒｏｙ，  Ｊ．Ｈ．  Ｐａｔｅｌ，  ａｎｄ  Ｊ．Ａ．  Ａｂｒａｈａｍ，  ”Ｔｅｓｔ  ｃｏｍｐａｃｔｉｏｎ  ｆｏｒ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ（シーケンシャル回路に関する試験圧縮），”  ＩＥＥＥ  Ｔｒａｎｓ．  Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ，  ｖｏｌ．１１，  ｎｏ．２，  ｐｐ．２６０−２６７，  Ｆｅｂ．  １９９２、およびＢ．  Ｓｏ，  ”Ｔｉｍｅ−ｅｆｆｉｃｉｅｎｔ  ａｕｔｏｍａｔｉｃ  ｔｅｓｔ  ｐａｔｔｅｒｎ  ｇｅｎｅｒａｔｉｏｎ  ｓｙｓｔｅｍ（省時間自動試験パターン生成システム），”  ウィスコンシン大学マディソン校電気工学部博士論文（１９９４）に示されている。
【０００５】
ベクトルの挿入、除外、および選択に基づく静的圧縮手法については、すでに研究されている。詳細については、Ｉ．  Ｐｏｍｅｒａｎｚ  ａｎｄ  Ｓ．Ｍ．Ｒｅｄｄｙ，  ”Ｏｎ  ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｏｆ  ｔｅｓｔ  ｓｅｑｕｅｎｃｅｓ  ｆｏｒ  ｓｙｎｃｈｒｏｎｏｕｓ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ（同期シーケンシャル回路に関する試験シーケンスの静的圧縮について），”  Ｐｒｏｃ．  Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆ．  ｐｐ．２１５−２２０，  Ｊｕｎｅ  １９９６を参照されたい。
【０００６】
上記の静的圧縮手法では、複数の故障シミュレーション・パスが必要とされる。ベクトルが除外またはスワップされると、故障シミュレーターが呼び出される。これが行われるのは、故障カバレージに影響が及ばないようにするためである。故障カバレージとは、特定の試験セットによって検出される故障数である。上記の静的圧縮手法は、非常に優れた圧縮効果を望めるにもかかわらず、膨大な計算を要する。
【０００７】
ベクトル復元手法は、困難度の高い故障から順に全故障を検出するために必要とされるベクトルを十分な数だけ復元することを目的とする。最近では、開始時と終了時の状態が同じとなる反復サブシーケンスを除去する高速静的試験セット圧縮も報告されている。詳細については、Ｒ．  Ｇｕｏ，  Ｉ．  Ｐｏｍｅｒａｎｚ  ａｎｄ  Ｓ．Ｍ．  Ｒｅｄｄｙ，  ”Ｐｒｏｃｅｄｕｒｅｓ  ｆｏｒ  ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｏｆ  ｔｅｓｔ  ｓｅｑｕｅｎｃｅｓ  ｆｏｒ  ｓｙｎｃｈｒｏｎｏｕｓ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ  ｂａｓｅｄ  ｏｎ  ｖｅｃｔｏｒ  ｒｅｓｔｏｒａｔｉｏｎ（同期シーケンシャル回路に関する試験シーケンスのベクトル復元に基づく静的圧縮プロシージャー），”  Ｄｅｓｉｇｎ，  Ａｕｔｏｍａｔｉｏｎ  ａｎｄ  Ｔｅｓｔ  ｉｎ  Ｅｕｒｏｐｅ（ＤＡＴＥ）議事録所収，  Ｆｅｂｒｕａｒｙ，  １９９８、およびＭ．Ｓ．  Ｈｓｉａｏ，  Ｅ．Ｍ．  Ｒｕｄｎｉｃｋ，  ａｎｄ  Ｊ．Ｈ．  Ｐａｔｅｌ，  ”Ｆａｓｔ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｏｆ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔ  ｔｅｓｔ  ｖｅｃｔｏｒｓ（シーケンシャル回路試験ベクトルの静的圧縮のための高速アルゴリズム），”  Ｐｒｏｃ．  ＩＥＥＥ  ＶＬＳＩ  Ｔｅｓｔ  Ｓｙｍｐ．，  ｐｐ．１８８−１９５，  Ａｐｒ．  １９９５を参照されたい。しかし、これらの試験セットは、複数の故障シミュレーション・パスを使用するアルゴリズムで実現される試験セットほどコンパクトではない。最近では、ベクトルの再順序付けに基づく圧縮も提案されている。詳細については、Ｍ．Ｓ．  Ｈｓｉａｏ  ａｎｄ  Ｓ．Ｔ．  Ｃｈａｋｒａｄｈａｒ，  ”Ｓｔａｔｅ  ｒｅｌａｘａｔｉｏｎｂａｓｅｄ  ｓｕｂｓｅｑｕｅｎｃｅ  ｒｅｍｏｖａｌ  ｆｏｒ  ｆａｓｔ  ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｉｎ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ（シーケンシャル回路における高速静的圧縮のための状態緩和に基づくサブシーケンスの除去），”  Ｄｅｓｉｇｎ，  Ａｕｔｏｍａｔｉｏｎ  ａｎｄＴｅｓｔ  ｉｎ  Ｅｕｒｏｐｅ（ＤＡＴＥ）  議事録所収，  Ｆｅｂｒｕａｒｙ，  １９９８を参照されたい。ただし、大規模な産業用設計の場合は、ベクトル再順序付け方式ではランタイムが非常に長時間となり、実用には耐えない。
【０００８】
動的手法では、試験生成プロセスと同時に圧縮が実行される。動的圧縮手法の詳細については、Ｉ．  Ｐｏｍｅｒａｎｚ  ａｎｄ  Ｓ．  Ｍ．  Ｒｅｄｄｙ，”Ｄｙｎａｍｉｃ  Ｔｅｓｔ  Ｃｏｍｐａｃｔｉｏｎ  ｆｏｒ  Ｓｙｎｃｈｒｏｎｏｕｓ  Ｓｅｑｕｅｎｔｉａｌ  Ｃｉｒｃｕｉｔｓ  ｕｓｉｎｇ  Ｓｔａｔｉｃ  Ｃｏｍｐａｃｔｉｏｎ  Ｔｅｃｈｎｉｑｕｅｓ（静的圧縮手法による同期シーケンシャル回路の動的試験圧縮），”  Ｆａｕｌｔ−Ｔｏｌｅｒａｎｔ  Ｃｏｍｐｕｔｉｎｇ  Ｓｙｍｐ．議事録所収，  ｐｐ．  ５３−６１，  Ｊｕｎｅ１９９６、Ｓ．Ｔ．  Ｃｈａｋｒａｄｈａｒ  ａｎｄ  Ａ．  Ｒａｇｈｕｎａｔｈａｎ，  ”Ｂｏｔｔｌｅｎｅｃｋ  ｒｅｍｏｖａｌ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｄｙｎａｍｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｉｎ  ｓｅｑｕｅｎｔｉａｌｃｉｒｃｕｉｔｓ（シーケンシャル回路における動的圧縮のためのボトルネック除去アルゴリズム），”  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ（出版受理）  １９９７、Ｅ．Ｍ．  Ｒｕｄｎｉｃｋ  ａｎｄ  Ｊａｎａｋ  Ｈ．  Ｐａｔｅｌ，  ”Ｓｉｍｕｌａｔｉｏｎ−ｂａｓｅｄ  ｔｅｃｈｎｉｑｕｅｓ  ｆｏｒ  ｄｙｎａｍｉｃ  ｔｅｓｔ  ｓｅｑｕｅｎｃｅ  ｃｏｍｐａｃｔｉｏｎ（動的試験シーケンス圧縮のためのシミュレーションに基づく手法），”  Ｐｒｏｃ．  Ｉｎｔｌ．  Ｃｏｎｆ．  Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ，  ｐｐ．６７−７３，  Ｎｏｖｅｍｂｅｒ１９９６、およびＴ．Ｊ．  Ｌａｍｂｅｒｔ  ａｎｄ  Ｋ．Ｋ．  Ｓａｌｕｊａ，  ”Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｄｙｎａｍｉｃ  Ｔｅｓｔ  Ｖｅｃｔｏｒ  Ｃｏｍｐａｃｔｉｏｎ  ｉｎ  Ｓｅｑｕｅｎｔｉａｌ  Ｔｅｓｔ  Ｇｅｎｅｒａｔｉｏｎ（シーケンス試験生成における動的試験ベクトル圧縮法），”  Ｉｎｔ．  Ｃｏｎｆ．  ｏｎ  ＶＬＳＩ  Ｄｅｓｉｇｎ議事録所収，  ｐｐ．１６６−１６９，  Ｊａｎ．  １９９６を参照されたい。ただし、これらの動的試験手法では、試験生成装置の変更が必要である。
【０００９】
動的手法とは異なり、静的手法は試験生成プロセスの後に使用される。そのため、これらの手法は試験生成アルゴリズムからは独立しており、試験生成装置を変更する必要はない。また、静的圧縮手法によって、動的圧縮後に得られた試験セットのサイズをさらに縮小することが可能である。
【００１０】
シーケンシャル回路用試験セットの静的圧縮の分野では顕著な進歩が見られている。静的圧縮法については、Ｓ．Ｋ．  Ｂｏｍｍｕ  ａｎｄ  Ｓ．Ｉ．  Ｃｈａｋｒａｄｈａｒ  ａｎｄ  Ｋ．Ｂ．  Ｄｏｒｅｓｗａｍｙ，  ”ＶｅｃｔｏｒＲｅｓｔｏｒａｔｉｏｎ  ｕｓｉｎｇ  Ａｃｃｅｌｅｒａｔｅｄ  Ｖａｌｉｄａｔｉｏｎ  ａｎｄ  Ｒｅｆｉｎｅｍｅｎｔ（加速式妥当性検査および洗練によるベクトル復元，”  Ａｓｉａｎ  Ｔｅｓｔ  Ｓｙｍｐｏｓｉｕｍ議事録所収，Ｄｅｃｅｍｂｅｒ，  １９９８、Ｒ．  Ｇｕｏ，  Ｉ．  Ｐｏｍｅｒａｎｚ  ａｎｄ  Ｓ．Ｍ．  Ｒｅｄｄｙ，  ”Ｐｒｏｃｅｄｕｒｅｓ  ｆｏｒ  ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｏｆ  ｔｅｓｔ  ｓｅｑｕｅｎｃｅｓ  ｆｏｒ  ｓｙｎｃｈｒｏｎｏｕｓ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ  ｂａｓｅｄ  ｏｎ  ｖｅｃｔｏｒ  ｒｅｓｔｏｒａｔｉｏｎ（同期シーケンシャル回路に関する試験シーケンスのベクトル復元に基づく静的圧縮プロシージャー），”  Ｄｅｓｉｇｎ，  Ａｕｔｏｍａｔｉｏｎ  ａｎｄ  Ｔｅｓｔ  ｉｎ  Ｅｕｒｏｐｅ（ＤＡＴＥ）議事録所収，  Ｆｅｂｒｕａｒｙ，  １９９８、Ｓ．Ｋ．  Ｂｏｍｍｕ  ａｎｄ  Ｓ．Ｔ．  Ｃｈａｋｒａｄｈａｒ  ａｎｄ  Ｋ．Ｂ．  Ｄｏｒｅｓｗａｍｙ，  ”Ｓｔａｔｉｃ  ｔｅｓｔ  ｓｅｑｕｅｎｃｅ  ｃｏｍｐａｃｔｉｏｎ  ｂａｓｅｄ  ｏｎ  ｓｅｇｍｅｎｔ  ｒｅｏｒｄｅｒｉｎｇ  ａｎｄｆａｓｔ  ｖｅｃｔｏｒ  ｒｅｓｔｏｒａｔｉｏｎ（セグメント再順序付けおよび高速ベクトル復元に基づく静的試験シーケンス圧縮），”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｔｅｓｔ  Ｃｏｎｆｅｒｅｎｃｅ議事録所収、Ｏｃｔｏｂｅｒ，１９９８、およびＳ．Ｋ．  Ｂｏｍｍｕ  ａｎｄ  Ｓ．Ｔ．  Ｃｈａｋｒａｄｈａｒ  ａｎｄ  Ｋ．Ｂ．  Ｄｏｒｅｓｗａｍｙ，  ”Ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｕｓｉｎｇ  ｏｖｅｒｌａｐｐｅｄ  ｒｅｓｔｏｒａｔｉｏｎ  ａｎｄ  ｓｅｇｍｅｎｔ  ｐｒｕｎｉｎｇ（重複復元およびセグメント・プルーニングによる静的圧縮），”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ議事録所収，  Ｎｏｖｅｍｂｅｒ，  １９８８で詳細に考察されている。
【００１１】
しかし、試験セット圧縮の速度と品質をさらに向上させることのできる、より優れた手法が必要とされている。
【００１２】
【発明が解決しようとする課題】
上述したように、シーケンシャル回路の静的圧縮方式については、ランダム・ベースまたはシミュレーション・ベースの試験生成装置で生成された試験セットを縮小することができないという問題点を有する。
【００１３】
また、ベクトルの挿入、除外、および選択に基づく静的圧縮手法では、非常に優れた圧縮効果を望めるにもかかわらず、膨大な計算を要する。
【００１４】
さらに、ベクトル復元手法では、これらの試験セットは、複数の故障シミュレーション・パスを使用するアルゴリズムで実現される試験セットほどコンパクトではなく、かつ大規模な産業用設計の場合は、ベクトル再順序付け方式ではランタイムが非常に長時間となり、実用には耐えない。
【００１５】
動的圧縮手法試験生成装置の変更が必要となる。
【００１６】
そこで、試験セット圧縮の速度と品質をさらに向上させることのできる、より優れた手法が必要とされている。
【００１７】
【課題を解決するための手段】
既知の静的圧縮アルゴリズムは、典型的には、与えられた試験ベクトル・セットを圧縮することによって故障カバレージの現状維持を図る。故障カバレージは、試験セットを特定の欠陥モデル（例えば、縮退故障など）に関して故障等級付けすることによって決定される。圧縮処理中、圧縮済みベクトル・セットは選択された欠陥モデルを使用して等級付けされる。本発明は、大規模な生産設計に関するベクトル・セットを圧縮するための新規な方式である。本発明の方式は、主に以下の２つの観察を前提とする。
【００１８】
（１）生産回路に関する試験セットは、さまざまな物理的欠陥に対する保護を提供する。単一の欠陥モデルですべての欠陥に対応することは不可能なので、試験セットは、縮退故障モデル、ディレー故障モデル、ブリッジ故障モデルなどの複数の故障モデルを使用して生成された試験で構成される。そのため、単一の欠陥モデルに関して生成された試験の圧縮処理中に故障カバレージの微落が発生したとしても、試験セット全体の試験品質に悪影響が出るとは考えにくい。
【００１９】
（２）故障カバレージは集合的な尺度なので、原試験セットと圧縮試験セットが検出する故障の数が同じである限り、現状に維持される。２つの試験セットが検出する故障は、大幅に異なる可能性がある。特に、ベクトル・セットの場合は、原ベクトル・セットによって検出されなかった新規な故障が圧縮ベクトル・セットによって検出されることさえある。
【００２０】
本発明の目的は、従来の技術で述べた問題を解決するために、圧縮試験セットの故障カバレージが（１）原試験セットの故障カバレージに等しいかそれを上回る、または（２）圧縮セットのカバレージが原試験セットより低い場合に、故障カバレージの低下が事前指定の許容限界値内にとどまる、のいずれかとなるように試験セットを圧縮するためのベクトル・セット生成方法、試験システム、および試験プログラムを格納する記録媒体を提供することにある。
【００２１】
事前指定の許容限界値は、圧縮処理中に無視することのできる最大故障数に変換される。これらの故障は、圧縮処理中に消費することのできる初期資源を構成する。本発明の範囲には、その他のタイプの資源制約も含まれる。例えば、圧縮プロセスは、事前指定のＣＰＵ秒数だけ消費するように制約することが可能である。
【００２２】
本発明の他の目的は、セグメント構築中に除去することのできる故障の数は構築中のセグメントのサイズに比例することを立証することにある。
【００２３】
本発明の目的を達成するために、ベクトル・セットを生成する方法が提供され、前記ベクトル・セットはシーケンシャル回路を試験するために使用され、前記方法は下記要件を備える。すなわち、複数個の故障モデルを選択する。前記複数個の故障モデルの各々について故障リストを１つずつ識別する。前記故障リストの各々についてベクトル・セットを１つずつ識別する。前記故障リストの各々について許容限度値を１つずつ選択し、それにより、各故障モデルが故障リスト、ベクトル・セット、および許容限界値を１つずつ有する。前記ベクトル・セットの各々を、圧縮済みベクトル・セットが故障リスト内のすべての故障を識別するか、前記ベクトル・セットによって検出される故障数である故障カバレージの低下が許容限界値の範囲内にとどまるように圧縮する。および、圧縮されたすべてのベクトル・セットを結合することにより１つのベクトル・セットを作成する。
【００２４】
前記許容限界値の少なくとも１つが計算資源に基づくのが望ましい。
【００２５】
前記許容限界値の少なくとも１つが故障カバレージから除去された故障の数に基づくのが望ましい。
【００２６】
前記許容限界値の少なくとも１つが電力使用量に基づくのが望ましい。
【００２７】
前記許容限界値の少なくとも１つが熱放散に基づくのが望ましい。
【００２８】
セグメント構築中に故障が除去され、除去される故障の数がセグメントのサイズに比例するのが望ましい。
【００２９】
前記圧縮処理が複数回の反復から成り、前記許容限界値の各々は動的であり、前記複数回の反復のうち少なくとも１回の反復に関して変更でき、前記許容限界値のうち少なくとも１つがゼロでありうるのが望ましい。
【００３０】
さらに、前記計算資源はＣＰＵ使用量であるのが望ましい。
【００３１】
さらに、前記計算資源はメモリー使用量であるのが望ましい。
【００３３】
本発明の他の態様は、試験生成装置を備えるＶＬＳＩ回路を試験するための試験システムであって、試験生成装置はさらに下記要件を備える。すなわち、複数個の故障モデルを選択するための故障モデル選択装置。前記故障モデルの各々について故障リストを１つずつ識別するための故障リスト識別装置。前記故障リストの各々についてベクトル・セットを１つずつ識別するためのベクトル・セット識別装置。前記故障リストの各々について許容限度値を１つずつ選択するための許容限界値選択装置であって、それにより、各故障モデルが故障リスト、ベクトル・セット、および許容限界値を１つずつ有する。前記ベクトル・セットの各々を、圧縮済みベクトル・セットが故障リスト内のすべての故障を識別するか、前記ベクトル・セットによって検出される故障数である故障カバレージの低下が許容限界値の範囲内にとどまるように圧縮するための除去済み故障圧縮装置。および、すべての圧縮済みベクトル・セットを結合するためのベクトル・セット作成装置。
【００３４】
試験システムにおいては、前記許容限界値の少なくとも１つが計算資源に基づくのが望ましい。
【００３５】
試験システムにおいては、前記許容限界値の少なくとも１つが故障カバレージから除去された故障の数に基づくのが望ましい。
【００３６】
試験システムにおいては、前記許容限界値の少なくとも１つが電力使用量に基づくのが望ましい。
【００３７】
試験システムにおいては、前記許容限界値の少なくとも１つが熱放散に基づくのが望ましい。
【００３８】
試験システムにおいては、セグメント構築中に故障が除去され、除去される故障の数がセグメントのサイズに比例するのが望ましい。
【００３９】
試験システムにおいては、さらに、計算資源がＣＰＵ使用量であるのが望ましい。
【００４０】
試験システムにおいては、さらに、前記計算資源がメモリー使用量であるのが望ましい。
【００４１】
本発明の他の態様は、ＶＬＳＩ試験装置がＶＬＳＩ回路を試験できるようにする試験プログラムを格納するコンピューター読み取り可能媒体を含み、前記試験プログラムは下記要件を備える。すなわち、コンピューターが複数個の故障モデルを選択できるようにするための故障モデル選択ステップ。コンピューターが前記複数個の故障モデルの各々について故障リストを１つずつ識別できるようにするための故障リスト識別ステップ。コンピューターが前記故障リストの各々についてベクトル・セットを１つずつ識別できるようにするためのベクトル・セット識別ステップ。コンピューターが前記故障リストの各々について許容限度値を１つずつ選択できるようにするための許容限界値選択ステップであって、それにより、各故障モデルが故障リスト、ベクトル・セット、および許容限界値を１つずつ有する許容限界値選択ステップ。コンピューターが前記ベクトル・セットの各々を、圧縮済みベクトル・セットが故障リスト内のすべての故障を識別するか、前記ベクトル・セットによって検出される故障数である故障カバレージの低下が許容限界値の範囲内にとどまるように圧縮できるようにするための除去済み故障圧縮ステップ。コンピューターがすべての圧縮済みベクトル・セットを結合できるようにするためのベクトル・セット作成ステップ。
【００４２】
試験プログラムにおいては、前記許容限界値の少なくとも１つが計算資源に基づくのが望ましい。
【００４３】
試験プログラムにおいては、前記許容限界値の少なくとも１つが故障カバレージから除去された故障の数に基づくのが望ましい。
【００４４】
試験プログラムにおいては、前記許容限界値の少なくとも１つが電力使用量に基づくのが望ましい。
【００４５】
試験プログラムにおいては、前記許容限界値の少なくとも１つが熱放散に基づくのが望ましい。
【００４６】
試験プログラムにおいては、セグメント構築中に故障が除去され、除去される故障の数がセグメントのサイズに比例するのが望ましい。
【００４７】
試験プログラムにおいては、さらに、前記計算資源がＣＰＵ使用量であるのが望ましい。
【００４８】
試験プログラムにおいては、さらに、前記計算資源はメモリー使用量であるのが望ましい。
【００４９】
【発明の実施の形態】
以下、本発明の好適な実施の形態について図面を参照して詳細に説明する。
【００５０】
試験セットの圧縮に使用される圧縮プロセスは、典型的には数回の反復で構成される。ただし、反復の回数は最初から確立されているわけではない。この回数は回路、試験セット、およびターゲットとなる故障セットによって決まる。本発明のような資源の制約に基づく圧縮は単純ではない。それは、圧縮プロセス内の１回の反復に消費可能な資源として何をどう割り当てるかが、圧縮済み試験セットのサイズと圧縮プロセスの速度の両方に大きな影響を及ぼしうるからである。また、１回の反復に割り当てられた資源が、その反復中にすべて消費されるとは限らない。したがって、反復中に実際に消費された資源を計算することによって、以降の反復への資源の割り当てをより的確に行えるようになる。
【００５１】
本発明の好適な実施の形態では、故障カバレージ曲線が検査され、反復ごとの資源割り当て戦略が数学的な手法で打ち立てられる。
【００５２】
ここで、本発明の好適な実施の形態について、高速セグメント・プルーニング手法を使用して説明する。こうした従来のプルーニング手法の詳細な説明は、Ｓ．Ｋ．  Ｂｏｍｍｕ  ａｎｄ  Ｓ．Ｔ．  Ｃｈａｋｒａｄｈａｒ  ａｎｄ  Ｋ．Ｂ．  Ｄｏｒｅｓｗａｍｙ，  ”Ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｕｓｉｎｇ  ｏｖｅｒｌａｐｐｅｄ  ｒｅｓｔｏｒａｔｉｏｎ  ａｎｄ  ｓｅｇｍｅｎｔ  ｐｒｕｎｉｎｇ（重複復元およびセグメント・プルーニングによる静的圧縮），”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ議事録所収，  Ｎｏｖｅｍｂｅｒ，  １９９８に記述されている。セグメント・プルーニング手法では、個々の故障の同期化プレフィックスを識別する作業が２段階に分けて行われる。この手法では、プルーニングの効率を損なうことなくプルーニング時間を大幅に高速化することができる。高速化に寄与するのは以下の要因である。
【００５３】
・同期化プレフィックスの識別を２段階方式で実行する。
【００５４】
・セグメント構築中に実行されるシミュレーションから得られる情報を使用して、プルーニング中のシミュレーション回数を最小限にする。
【００５５】
・故障が初期の段階に除去される。すなわち、プルーニング中に、故障のシミュレーションは検出時間までしか実行されず、これによって故障の検出可能性が判断された後に、除去される。
【００５６】
好適な実施の形態は、２段階静的圧縮アルゴリズムの一部として実施されている。２段階静的圧縮アルゴリズムについての詳細は、Ｓ．Ｋ．  Ｂｏｍｍｕ  ａｎｄ  Ｓ．Ｔ．  Ｃｈａｋｒａｄｈａｒ  ａｎｄ  Ｋ．Ｂ．  Ｄｏｒｅｓｗａｍｙ，  ”Ｓｔａｔｉｃ  ｔｅｓｔ  ｓｅｑｕｅｎｃｅ  ｃｏｍｐａｃｔｉｏｎ  ｂａｓｅｄ  ｏｎ  ｓｅｇｍｅｎｔ  ｒｅｏｒｄｅｒｉｎｇ  ａｎｄ  ｆａｓｔｖｅｃｔｏｒ  ｒｅｓｔｏｒａｔｉｏｎ（セグメント再順序付けおよび高速ベクトル復元に基づく静的試験シーケンス圧縮），”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｔｅｓｔ  Ｃｏｎｆｅｒｅｎｃｅ議事録所収、Ｏｃｔｏｂｅｒ，  １９９８に示されている。Ｓ．Ｋ．  Ｂｏｍｍｕ  ａｎｄ  Ｓ．Ｔ．  Ｃｈａｋｒａｄｈａｒ  ａｎｄ  Ｋ．Ｂ．  Ｄｏｒｅｓｗａｍｙ，  ”Ｓｔａｔｉｃ  ｃｏｍｐａｃｔｉｏｎ  ｕｓｉｎｇ  ｏｖｅｒｌａｐｐｅｄ  ｒｅｓｔｏｒａｔｉｏｎ  ａｎｄ  ｓｅｇｍｅｎｔ  ｐｒｕｎｉｎｇ（重複復元およびセグメント・プルーニングによる静的圧縮），”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ議事録所収，  Ｎｏｖｅｍｂｅｒ，  １９９８、およびＳ．Ｋ．  Ｂｏｍｍｕ  ａｎｄ  Ｓ．Ｉ．  Ｃｈａｋｒａｄｈａｒ  ａｎｄ  Ｋ．Ｂ．  Ｄｏｒｅｓｗａｍｙ，  ”Ｖｅｃｔｏｒ  Ｒｅｓｔｏｒａｔｉｏｎ  ｕｓｉｎｇ  Ａｃｃｅｌｅｒａｔｅｄ  Ｖａｌｉｄａｔｉｏｎ  ａｎｄ  Ｒｅｆｉｎｅｍｅｎｔ（加速式妥当性検査および洗練によるベクトル復元），”  Ａｓｉａｎ  Ｔｅｓｔ  Ｓｙｍｐｏｓｉｕｍ議事録所収，  Ｄｅｃｅｍｂｅｒ，  １９９８参照。
【００５７】
セグメントは、サブシーケンスｖｉ，．．．，ｖｊ（１≦ｉ≦ｊ≦ｎ）なので、将来ターゲット故障ｆについては、検出時間Ｄ（ｆ）＜ｉとなる。図１４の例では、故障ｆ５の復元プロセスによって、サブシーケンスｖ１７，．．．，ｖ２０が得られる。この時点では、故障ｆ１、ｆ２、およびｆ３は復元済みシーケンスによって検出されない。これらすべての故障の検出時間は、１７より早い。そのため、サブシーケンスｖ１７，．．．，ｖ２０はセグメントである。ｆ４の検出時間はｆ３よりも後であり、ｆ４は復元済みシーケンスによって検出されるので、ｆ４は将来ターゲット故障とはなりえない。
【００５８】
図２は、本発明の手法を使用した好適な実施の形態に関する擬似コードを示したものである。図２のｗｈｉｌｅループの反復回数は、事前に予測することはできない。図３に示すプロシージャーＯＶＥＲＬＡＰＰＥＤ−ＶＡＬＩＤＡＴＩＯＮは、セグメントを保持することが保証されたベクトル・シーケンスを識別する。このシーケンスは、セグメントを決定するために、プロシージャーＯＶＥＲＬＡＰＰＥＤ＿ＲＥＦＩＮＥＭＥＮＴによってトリムされる。セグメントのサイズが大きい場合は、これら２つのプロシージャーには大量な計算が必要となる。そのため、本発明では、故障カバレージに事前指定の許容限界値を使用して大きなセグメントの原因となる故障を除去することによって、これらのプロシージャーを加速させる。
【００５９】
次に、本発明の手法を、図１の例を使用して示す。試験セットは３５個のベクトルｖ１，．．．，ｖ３５から成り、故障リストは８個の故障ＦＵ＝｛ｆ１，．．．，ｆ８｝を有する。図１には、不明な初期状態を想定して、すべての故障を検出するための検出時間とサブシーケンスも示している。例えば、故障ｆ８はベクトルｖ３５の適用後に検出される。そのため、検出時間Ｄ［ｆ８］＝３５である。未知の初期状態を想定して、サブシーケンスｖ１８，．．．，ｖ３５のみがこの故障を検出する。ここでは、２個のサブシーケンスによって検出されるのは故障ｆ１およびｆ５のみであり、ほとんどの故障が１個のみのサブシーケンスによって検出されていることに留意されたい。
【００６０】
この例で想定されるベクトルしきい値は１５である。この例では、Ｓ１＝｛ｖ３０，．．．，ｖ３４｝およびＳ２＝｛ｖ２，．．．，ｖ１５｝の２個のセグメントが検出される。第１セグメントの構築中に、圧縮手法によってｆ８が除去される。それは、ｆ８を含むセグメントを識別するために、圧縮プロセスに課せられた資源制約を超過する資源を使用する必要があるからである。以下に、第１セグメントの資源制約付き復元について説明する。ここで留意すべきは、この例では、第２セグメントは資源制約を超過することなく導き出すことができることである。第１セグメントのベクトル数は、セグメント・プルーニング法によってこれ以上削減することはできない。しかし、第２セグメントのベクトル数はプルーニング法によって削減することが可能である。以下ではさらに、第２セグメントに関するセグメント・プルーニング・プロシージャーについても説明する。
（第１セグメントの資源制約付き復元）
第１セグメントｖ３０，．．．，ｖ３４は以下の方法で導き出される。図２に示すＳＣＯＰＥアルゴリズムは、本発明の好適な実施の形態である。復元はこのアルゴリズムで開始される。これは最初の反復なので、ＣｏｍｐａｃｔＳｅｔ内にベクトルはない。第２〜４行は、新規セグメントを導き出す前に実行されなければならない初期化ステップである。ここで、新規セグメントの検索が開始する前に、同じ初期化ステップ（第１３〜１５行）が実行されることに留意する必要がある。故障ｆ８の最大検出時間はＤ［ｆ８］＝３５なので、変数ｂａｓｅ＝３５である。ターゲット故障リストＦＴには、１個の故障（故障ｆ８）しか含まれていない。プロシージャーＲＥＳＥＴ＿ＬＯＷ＿ＨＩＧＨはアレイＬＯＷおよびＨＩＧＨを初期化する。この例では、ｆ∈ＦＵであれば、ＬＯＷ［ｆ］＝１およびＨＩＧＨ［ｆ］＝３６である。アルゴリズムＯＶＥＲＬＡＰＰＥＤ＿ＶＡＬＩＤＡＴＩＯＮでは、最初ＦＴ＝ｆ８である。ＨＩＧＨ［ｆ８］＝３６なので、変数ｓｔａｒｔ＝３６である。妥当性検査プロセスでは、以下の順序で５つのサブシーケンスが考慮される。
【００６１】
故障シミュレーションにおいて最初に考慮されるシーケンスはｖ３５である。それは、第４行から、ｌｏｗ＝３６だからである。ＦＵ内のその他すべての故障は検出時間が３５未満なので、故障セットＦ５＝｛ｆ８｝である。ベクトルｖ３５の故障シミュレーションでは、ＦＳ内に故障が検出されない。範囲情報は、プロシージャーＵＰＤＡＴＥ＿ＬＯＷ＿ＨＩＧＨを使用して、ＨＩＧＨ［ｆ８］＝３５に更新される。プロシージャーＵＰＤＡＴＥ＿ＴＡＲＧＥＴＳは新規なターゲットを生成しない。このプロシージャーで最初に考慮される故障はｆｐ＝ｆ７（第３行）である。変数ｈｉｇｈ＝ＨＩＧＨ［ｆ８］＝３５である。また、Ｄ［ｆｐ］＝３４およびｈｉｇｈ＞Ｄ［ｆｐ］である。したがって、ｆ７は新規ターゲットではない。プロシージャーＤＲＯＰ＿ＣＲＩＴＩＣＡＬ＿ＴＡＲＧＥＴＳはトリビアルとして戻る。それは、シーケンス長は１であり、ベクトルしきい値１５に満たないからである。
【００６２】
故障シミュレーションにおいて２番目に考慮されるシーケンスは、Ｓｅｑ＝ｆ｛ｖ３４，ｖ３５｝である。それは、第４行から、ｌｏｗ＝３４だからである。ここでも、セットＦＴには１個の故障ｆ８しか含まれていない。ただし、ｆ７およびｆ８の検出時間は３４と等しいか上回っているので、セットＦ８＝｛ｆ７，ｆ８｝である。シーケンスＳｅｑの故障シミュレーションでは、ＦＴ内に故障が検出されない。そのため、範囲情報はＨＩＧＨ［ｆ８］＝ＨＩＧＨ｛ｆ７｝＝３４に更新される。プロシージャーＵＰＤＡＴＥ＿ＴＡＲＧＥＴＳは１つの新規ターゲットを生成する。新規ターゲットは以下のように決定される。このプロシージャーが最初に考慮する故障はｆｐ＝ｆ７である。変数ｈｉｇｈ＝ＨＩＧＨ｛ｆ８｝＝３４である。Ｄ［ｆ７］＝３４なので、ｈｉｇｈ≦Ｄ［ｆ７］＋１である。また、ＨＩＧＨ［ｆ７］≦Ｄ［ｆ７］である。そのため、ｆ７は新規ターゲットであり、ターゲット故障リストＦＴに組み込まれる。セットＦＤは、故障シミュレーション中に検出された故障は含まない。考慮対象となる２番目の故障はｆｐ＝ｆ６である。Ｄ［ｆ６］＝２６なので、変数ｈｉｇｈ＝Ｍｉｎｉｍｕｍ（ＨＩＧＨ［ｆ７］，ＨＩＧＨ［ｆ８］）＝２９である。したがってｈｉｇｈ＞Ｄ［ｆ６］＋１であり、ｆ６は新規ターゲットではない。プロシージャーＤＲＯＰ＿ＣＲＩＴＩＣＡＬ＿ＴＡＲＧＥＴＳはトリビアルとして戻る。
【００６３】
次に考慮されるシーケンスは、Ｓｅｑ＝ｆ｛ｖ３２，．．．，ｖ３５｝である。このパスの場合、ＦＴ＝Ｆ８＝｛ｆ６，ｆ７，ｆ８｝である。ここでも、シーケンスＳｅｑの故障シミュレーションによって、セットＦＳ内で１個の故障ｆ７が検出される。範囲情報はＨＩＧＨ［ｆ６］＝ＨＩＧＨ｛ｆ８｝＝３２およびＬＯＷ［ｆ７］＝３２に更新される。プロシージャーＵＰＤＡＴＥ＿ＴＡＲＧＥＴＳはいくつかのことを行う。このプロシージャーは、まず、新規ターゲット故障ｆ６を生成する。また、故障ｆ７に検出済みのマークが付けられ、これが検出済み故障ＦＤのセットに組み込まれる。ｆ７は検出済みなので、セットＦＴおよびＦＵの両方から削除する。ここでも、シーケンスＳｅｑには４個のベクトルしかなく、ベクトルしきい値１５に満たないため、ルーチンＤＲＯＰ＿ＣＲＩＴＩＣＡＬ＿ＴＡＲＧＥＴＳはトリビアルとして戻る。
【００６４】
次に考慮されるシーケンスは、Ｓｅｑ＝ｆ｛ｖ２８，．．．，ｖ３５｝である。セットＦＴ＝｛ｆ６，ｆ８｝、およびセットＦＳ＝｛ｆ５，ｆ６，ｆ８｝である。ここでは、Ｄ［ｆ５］＝３０≧２６およびＨＩＧＨ［ｆ６］＝３１＞２６なので、ｆ５はＦＳ内にあると考えられる。シーケンスＳｅｑの故障シミュレーションにより、故障ｆ５およびｆ６が検出される。範囲情報はＨＩＧＨ［ｆ８］＝ＬＯＷ［ｆ５］＝ＬＯＷ［ｆ６］＝２６に更新される。プロシージャーＵＰＤＡＴＥ＿ＴＡＲＧＥＴＳは、故障ｆ５およびｆ６に検出済みのマークを付け、これらの故障をセットＦＴおよびＦｕから削除する。故障ｆ５およびｆ６は、検出された故障セットＦＤに追加される。この時点では、ＦＤ＝｛ｆ５，ｆ６，ｆ７｝であることに留意されたい。ルーチンＤＲＯＰ＿ＣＲＩＴＩＣＡＬ＿ＴＡＲＧＥＴＳはここでもトリビアルとして戻る。
【００６５】
次に考慮されるシーケンスは、Ｓｅｑ＝ｆ｛ｖ２０，．．．，ｖ３５｝である。セットＦＴ＝ＦＳ＝｛ｆ８｝である。ここでは、シーケンスＳｅｑの故障シミュレーションにより故障は検出されない。範囲情報はＨＩＧＨ［ｆ８］＝２０に更新される。プロシージャーＵＰＤＡＴＥ＿ＴＡＲＧＥＴＳは、新規ターゲットを生成しない。ただし、プロシージャーＤＲＯＰ＿ＣＲＩＴＩＣＡＬ＿ＴＡＲＧＥＴＳはいくつかの計算を行う。まず、第１行からプロシージャーＣＨＥＣＫ＿ＲＥＳＯＵＲＣＥＳを呼び出し、戻り値「真」が戻される。それは、ベクトルしきい値は１５であるのに、シーケンスＳｅｑがすでに１６個のベクトルを有しているからである。また、ターゲット故障の数は、許容された最大値より少ない。そのため、プロシージャーＤＲＯＰ＿ＣＲＩＴＩＣＡＬ＿ＴＡＲＧＥＴＳは、セットＦＴおよびＦｕから故障ｆ８を削除する。さらに、この故障は以降の復元の対象とはみなされない。次のステップは現在故障ＦＤ＝｛ｆ５，ｆ６，ｆ７｝を検出対象とするシーケンスＳｅｑを洗練することである。プロシージャーＣＯＭＰＵＴＥ＿ＲＥＦＩＮＥＭＥＮＴ＿ＴＡＲＧＥＴＳは、次のターゲット故障としてＦＤ内の一連の故障を選択する。グローバル・アレイＨＩＧＨおよびＬＯＷは、ＬＯＷ［ｆ５］＝ＬＯＷ［ｆ６］＝２８、ＬＯＷ［ｆ７］＝３２、ＨＩＧＨ［ｆ６］＝３２、ＨＩＧＨ［ｆ５］＝３６、およびＨＩＧＨ［ｆ７］＝３４の情報を有している。また、アレイＮＤは、ＮＤ［ｆ５］＝ＮＤ［ｆ６］＝３２、およびＮＤ［ｆ７］＝３４の情報を有している。プロシージャーＣＯＭＰＵＴＥ＿ＲＥＦＩＮＥＭＥＮＴ＿ＴＡＲＧＥＴＳの第２、３、および４行から、ｌｏｗ＝２８、ｈｉｇｈ＝３２、およびｂａｓｅ＝３４である。第５行は新規ターゲットＦＴを計算し、｛ｆ５，ｆ６｝を得る。第６行は、これらの故障をセットＦｕに追加する。第７行は、検出済み故障セットＦＤからこれらの故障を削除する。プロシージャーＣＯＭＰＵＴＥ＿ＲＥＦＩＮＥＭＥＮＴ＿ＴＡＲＧＥＴＳは、プロシージャーＯＶＥＲＬＡＰＰＥＤ＿ＶＡＬＩＤＡＴＩＯＮの第１０行に制御を戻す。１つの故障が除去されたので、制御は第３行で始まるループから離れる。これにより、重複妥当性検査段階が完了する。
【００６６】
重複妥当性検査段階後に得られたターゲット故障および復元済みシーケンスは、その後重複洗練段階に渡される。洗練処理後に得られたセグメントはｖ３０，．．．，ｖ３４であり、このシーケンスは故障｛ｆ５，ｆ６，ｆ７｝を検出する。このセグメントは、プロシージャーＳＥＧＭＥＮＴ＿ＰＲＵＮＥによっても処理される。ただし、ベクトルは除去されない。
（第２セグメントのプルーニング）
アルゴリズムＳＣＯＰＥによって導き出された第２セグメントは、故障｛ｆ１，ｆ２，ｆ３，ｆ４｝を検出するベクトルｖ２，．．．，ｖ１５で構成される。このセグメントから数個のベクトルを除去することが可能である。プロシージャーＳＥＧＭＥＮＴ＿ＰＲＵＮＥは、引数ＦＤ＝｛ｆ１，ｆ２，ｆ３，ｆ４｝、ＦＵ＝Ｎｉｌ、およびＣｏｍｐａｃｔＳｅｔ＝｛ｖ３０，．．．，ｖ３４｝を使って呼び出される。ＦＤ内の故障に関するその他の関連情報は、ＬＯＷ［ｆ１］＝２、［ＬＯＷ［ｆ２］＝４、ＬＯＷ［ｆ３］＝８、ＬＯＷ［ｆ４］＝８、およびＮＤ［ｆ１］＝８、ＮＤ［ｆ２］＝８、ＮＤ［ｆ３］＝１２、およびＮＤ［ｆ４］＝１５である。
【００６７】
この例の場合は、第２行のループが３回実行される。最初の反復では、ｔｏｐ＝２、およびＦ＝｛ｆ１，ｆ２，ｆ３，ｆ４｝１である。これらの値は、引数としてプロシージャーＶＡＬＩＤＡＴＥ＿ＰＲＵＮＥに渡される。このプロシージャーでは、初期値はｍａｘ＝２およびｍｉｎ＝１５である。プロシージャーＶＡＬＩＤＡＴＥ＿ＰＲＵＮＥのループ（第３行）の最初の反復中に、入力シーケンスから２０＝１ベクトルを削除する。新規シーケンスには、（ｖｔｅｍｐ，．．．，ｖｍｉｎ）＝（ｖ３，．．．，ｖ１５）が与えられる。手元のタスクについて、Ｆ内の故障がまだ新規シーケンスによって検出されるかどうかが判断される。今度の故障シミュレーションの初期状態は、シーケンスＣｏｍｐａｃｔＳｅｔのシミュレーション後に得られたのと同じ良好および故障回路状態である。この例では、故障シミュレーションで故障ｆ２、ｆ３、およびｆ４を考慮する必要はない。それは、これらの故障は初期状態とは関わりなく、シーケンス（ｖ３，．．．，ｖ５）によって検出されるからである。ここで、ＬＯＷ［ｆ１］＜ｔｅｍｐなのでＦｓｉｍ’＝｛ｆｉ｝であることに留意する必要がある。最終変数＝  ５である。故障シミュレーションで考慮されるシーケンスは、ｖ３，．．．，ｖ５である。それは、ベクトル・シーケンスｖ２，．．．，ｖ５に関して未知の初期状態を想定するのであれば、故障ｆ１はベクトルｖ５ですでに検出されているからである。初期状態が既知であれば、上記より短いシーケンスｖ３，．．．，ｖ５を使ってｖ５かそれより前に故障が検出される可能性がある。プルーニング・プロシージャーがいかに緻密かを説明するため、初期状態が既知であり、上記のように故障ｆ１がシーケンスｖ３，．．．，ｖ５によって検出されると想定する。故障が検出されるので、変数ｍａｘ＝３（第１２行）である。制御はループ（第３行）の冒頭に戻る。２回目の反復中、ｔｅｍｐ＝４、およびＦｓｉｍ’＝｛ｆｉ｝である。故障シミュレーションで考慮されるシーケンスは、（ｖ４，．．．，ｖ８）である。それ以降の反復は、同じ方法で実行できる。
【００６８】
本発明の他の態様は、セグメント構築中に除去することのできる故障の数は、構築中のセグメントのサイズに比例することの立証である。この関係は、故障カバレージ曲線から数学的手法で直接導き出すことができる。現在構築中のセグメントがシーケンス（ｖｉ−−−＞ｖｊ）で構成される場合、除去できる故障の数（クリティカル故障）は、構築中のセグメントのサイズ（（ｊ−ｉ））に比例する。シミュレーション実験で使用される正確な公式は、δｘ＝ＨｃＮＳＴ×［（ｊ−ｉ）／ＶＴ］である。ここで、ＶＴはベクトルしきい値を表す。セグメント構築中には、セグメント内のベクトル数がベクトルしきい値を超えるまで、故障は除去されない。どの実験についても、定数ＨｃＮＳＴの値は２が選択される。
【００６９】
本発明の方法では、許容限界値を計算資源に基づいて定めることができる。許容限界値を指定するときに使用する計算資源はどんなものでもよい。許容限界値の基準となる計算資源の例としては、ＣＰＵ使用量、メモリー、計算時間などが挙げられる。許容限界値は、さらに、故障カバレージから除去された故障数に基づいて設定することもできる。許容限界値を設定するための基準として使用できるその他のエンティティーには、電力使用量がある。たま、熱放散も、許容限界値を設定するための基準となる。
（除去済み故障によるＶＬＳＩ試験システム）
図１５は、本発明による試験システムの好適な実施の形態を示したものである。この好適な実施の形態は、ＶＬＳＩ回路を試験するためのシステムである。ＶＬＳＩ回路１５．１は、試験システムを使用して故障の有無を試験される。試験システムは、試験生成装置１５．２を備える。試験生成装置はさらに、複数個の故障モデルを選択するための故障モデル選択装置１５．３を備える。故障リスト識別装置１５．４は、複数個の故障モデルの各々について故障リストを１つずつ識別する。ベクトル・セット識別装置１５．５は、故障リストの各々についてベクトル・セットを１つずつ識別する。許容限界値選択装置１５．６は、前記故障リストの各々について許容限度値を１つずつ選択する。それにより、各故障モデルが故障リスト、ベクトル・セット、および許容限界値を１つずつ有する。除去済み故障圧縮装置１５．７は、前記ベクトル・セットの各々を、圧縮済みベクトル・セットが故障リスト内のすべての故障を識別するか、故障カバレージの低下が許容限界値の範囲内にとどまるように圧縮する。ベクトル・セット作成装置１５．８は、すべての圧縮済みベクトル・セットを結合する。
（コンピューター・プログラム製品）
本発明の他の態様は、コンピューター・プログラム製品である。このコンピューター・プログラム製品には、コンピューター読み取り可能媒体が含まれる。当業者には、コンピューター読み取り可能媒体は特定の種類の記憶装置に限定されず、コンピューター命令を記憶および／または伝送できるあらゆる種類の装置を含むことは明らかであろう。当該コンピューター・プログラム製品の好適な実施の形態には、コンピューター命令またはコンピューター・コードを格納するフロッピー・ディスクまたはＣＤ−ＲＯＭディスクが含まれる。ＶＬＳＩ試験コンピューターがＶＬＳＩ回路を試験できるようにするコンピューター・コード。当該コンピューター・コードは下記要件を備える。すなわち、コンピューターが複数個の故障モデルを選択できるようにするための故障モデル選択コード。コンピューターが前記複数個の故障モデルの各々について故障リストを１つずつ識別できるようにするための故障リスト識別コード。コンピューターが前記故障リストの各々についてベクトル・セットを１つずつ識別できるようにするためのベクトル・セット識別コード。コンピューターが前記故障リストの各々について許容限度値を１つずつ選択できるようにするための許容限界値選択コードであって、それにより、各故障モデルが故障リスト、ベクトル・セット、および許容限界値を１つずつ有する。コンピューターが前記ベクトル・セットの各々を、圧縮済みベクトル・セットが故障リスト内のすべての故障を識別するか、故障カバレージの低下が許容限界値の範囲内にとどまるように圧縮できるようにするための除去済み故障圧縮コード。コンピューターがすべての圧縮済みベクトル・セットを結合できるようにするためのベクトル・セット作成コード。
【００７０】
さらに、当業者には、本発明のＶＬＳＩ試験システムは、汎用ＰＣ、ワークステーション、またはメインフレーム・コンピューター、または特に試験システムとしての使用を目的として設計された専用コンピューティング・マシンを含むあらゆるコンピューター上で実行できることは明らかであろう。このシステムは、さらに、ネットワークを介してリモートで実行することも可能である。また、ネットワークまたは無線伝送手段を介したコンピューター・コードの伝送も、本発明の範囲に含まれる。
（実験結果）
提案される静的圧縮手法を、ＳＣＯＰＥと呼ばれるＣプログラムに実装した。この実装には、これまでの節に述べたすべての手法、クリティカル故障除去、および２φセグメント・プルーニングが含まれる。
【００７１】
ＩＳＣＡＳベンチマーク回路と数種類の産業用設計に関する実験結果を報告する。ＩＳＣＡＳベンチマークについては、Ｆ．  Ｂｒｇｌｅｚ，  Ｄ．  Ｂｒｙａｎ，  ａｎｄ  Ｋ．  Ｋｏｚｍｉｎｓｋｉ，  ”Ｃｏｍｂｉｎａｔｉｏｎａｌｐｒｏｆｉｌｅｓ  ｏｆ  ｓｅｑｕｅｎｔｉａｌ  ｂｅｎｃｈｍａｒｋ  ｃｉｒｃｕｉｔｓ（シーケンス・ベンチマーク・回路の組み合わせプロファイル），”  Ｉｎｔ．  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ，  ｐｐ．  １９２９−１９３４，  Ｍａｙ  １９８９に詳細に考察されている。表１に、ＩＳＣＡＳ回路の結果を示す。表２には、数種類の産業用設計に関する結果を示す。
【００７２】
各表では、原ベクトル・セットと圧縮ベクトル・セットのベクトル数を報告している。圧縮品質は、原ベクトル試験からの削減率として示している。ＣＰＵ秒は、Ｓｕｎ（登録商標）  ＵｌｔｒａＳＰＡＲＣ（登録商標）ワークステーションで得られた数値である。最終的な圧縮済みシーケンスの故障カバレージはクリティカル故障の除去によって変動するため、この手法による圧縮の適用前と適用後のカバレージ数も示している。
【００７３】
ＩＳＣＡＳ回路に使用した初期ベクトル・セットは、試験セット生成装置ＳＴＲＡＴＥＧＡＴＥを使用して取得した。この試験生成装置の詳細については、Ｔ．Ｍ．  Ｎｉｅｒｍａｎｎ  ａｎｄ  Ｊ．Ｈ．  Ｐａｔｅｌ，  ”ＨＩＴＥＣ：Ａ  ｔｅｓｔ  ｇｅｎｅｒａｔｉｏｎ  ｐａｃｋａｇｅ  ｆｏｒ  ｓｅｑｕｅｎｔｉａｌ  ｃｉｒｃｕｉｔｓ（ＨＩＴＥＣ：  シーケンシャル回路のための試験生成パッケージ），”  Ｐｒｏｃ．  Ｅｕｒｏｐｅａｎ  Ｃｏｎｆ  Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ（ＥＤＡＣ），  ｐｐ．  ２１４−２１８，  Ｍａｒｃｈ  １９９１に示されている。表１に、ＩＳＣＡＳ回路上の圧縮の結果を示す。ＳＣＯＰＥによって得られた結果は、クリティカル故障除去を行った場合と行わなかった場合について示している。また、カラム「ＳＣＯＰＥ−」はクリティカル故障除去を使用しなかった場合にＳＣＯＰＥによって得られた結果を示し、カラム「ＳＣＯＰＥ＋」は、カバレージの最大許容損失率を１％とした場合にＳＣＯＰＥによって得られた結果を示す。ＳＣＯＰＥ＋の場合のＳＣＯＰＥは、平均圧縮率５０％を達成し、１５分未満で全ＩＳＣＡＳベンチマーク回路上での実行を完了した。カバレージの損失率は無視できる程度であり、ほぼ常に１％未満である。例えば、ｓ４００回路では、たった１個の故障を除去しただけで、圧縮速度と圧縮効率が大幅に向上した。ＳＣＯＰＥ＋で要した時間は、初期ベクトル・シーケンスに対して故障除去処理をともなう故障シミュレーションを実行した際に要した時間の約１〜１．５倍であった。
【００７４】
産業用設計は、トリステート・バッファー、双方向バッファーおよびバスなどのいくつかの非ブーリアン・プリミティブを有する。またこれに加えて、セット／リセット・フリップフロップと複数クロックも有する。これらの回路用の原試験セットは、市販の試験生成装置を使用して導き出した。表２に圧縮結果を示す。ＳＣＯＰＥ＋では、ベクトルしきい値を２５、最大許容カバレージ損失率を１％に設定したクリティカル故障除去を行っている。概して、ＳＣＯＰＥ＋は、入力試験シーケンスに対して故障除去処理をともなう故障シミュレーションを実行した際に要した時間の約２〜３倍を要する。この表に示されるように、大規模な回路の圧縮に要する時間を制御する上では、クリティカル故障除去が重大な役割を果たす。例えば、ｐ３０６回路では、クリティカル故障除去によってランタイムが３分の１に圧縮され、しかも、プロセス中のカバレージの損失はなく、達成可能な圧縮も大幅に向上した。生産設計の場合、ＳＣＯＰＥ＋は平均４１％の圧縮を達成し、カバレージ損失率は平均０．４％であった。
【００７５】
上記の実験結果は、新規な静的圧縮アルゴリズムがパフォーマンスと圧縮効率において優れた効果を発揮することを実証している。
【００７６】
本発明のその他の変更態様と異型については、前述の開示と教示から当業者には明らかであろう。したがって、本書では本発明の一部の実施の形態を具体的に説明したにすぎないが、本発明の精神と範囲から乖離することなく無数の変更態様を作成できることは明らかであろう。
【００７７】
【発明の効果】
以上説明したように本発明によれば、圧縮試験セットの故障カバレージが（１）原試験セットの故障カバレージに等しいかそれを上回る、または（２）圧縮セットのカバレージが原試験セットより低い場合に、故障カバレージの低下が事前指定の許容限界値内にとどまる、のいずれかとなるように試験セットを圧縮するための方法、システム、およびコンピューター・プログラム製品を提供することができる。
【００７８】
また、セグメント構築中に除去することのできる故障の数は構築中のセグメントのサイズに比例することを立証することができる。
【図面の簡単な説明】
【図１】本発明の資源制約付き静的圧縮法を説明するための例を示す図である。
【図２】本発明の静的圧縮法の好適な実施の形態に関する疑似コードを示す図である。
【図３】図２の好適な実施の形態で使用される重複妥当性検査手法に関する疑似コードを示す図である。
【図４】図２に示す好適な実施の形態で使用されるアレイＬＯＷおよびＨＩＧＨの範囲情報を更新するための手法に関する疑似コードを示す図である。
【図５】ターゲットの更新を説明するための疑似コードを示す図である。
【図６】好適な実施の形態におけるセグメントを検出するための手法に関する疑似コードを示す図である。
【図７】好適な実施の形態においてクリティカル故障がどのように除去されるかを説明するための疑似コードを示す図である。
【図８】好適な実施の形態の洗練段階に関するターゲットを計算する手法を説明するための疑似コードを示す図である。
【図９】好適な実施の形態において使用されるプルーニング手法を説明するための疑似コードを示す図である。
【図１０】プルーニング手法の妥当性検査段階を説明するための疑似コードを示す図である。
【図１１】プルーニング手法の洗練段階を説明するための疑似コードを示す図である。
【図１２】いくつかのベンチマーク回路に関するシミュレーション実験の結果を説明するための表１を示す図である。
【図１３】いくつかの生産レベル回路に関するシミュレーション実験を説明するための表２を示す図である。
【図１４】セグメントの定義を説明するための例を示す図である。
【図１５】本発明による試験システムの好適な実施の形態のブロック図である。
【符号の説明】
１５．１  ＶＬＳＩ回路
１５．２  試験生成装置
１５．３  故障モデル選択装置
１５．４  故障リスト識別装置
１５．５  ベクトル・セット識別装置
１５．６  許容限界値選択装置１５．６
１５．７  除去済み故障圧縮装置
１５．８  ベクトル・セット作成装置
【図１】
0003552093.tif 000002
【図２】
0003552093.tif 000003
【図３】
0003552093.tif 000004
【図４】
0003552093.tif 000005
【図５】
0003552093.tif 000006
【図６】
0003552093.tif 000007
【図７】
0003552093.tif 000008
【図８】
0003552093.tif 000009
【図９】
0003552093.tif 000010
【図１０】
0003552093.tif 000011
【図１１】
0003552093.tif 000012
【図１２】
0003552093.tif 000013
【図１３】
0003552093.tif 000014
【図１４】
0003552093.tif 000015
【図１５】
0003552093.tif 000016