図面 (/)

技術 テストパタン生成方法および装置ならびにテストパタン生成プログラムを記録した記録媒体

出願人 日本電気株式会社
発明者 東宮玉紀
出願日 1998年12月28日 (22年1ヶ月経過) 出願番号 1998-371780
公開日 2000年7月14日 (20年7ヶ月経過) 公開番号 2000-193725
状態 特許登録済
技術分野 CAD 電子回路の試験 デジタル計算機の試験診断 電子回路の試験
主要キーワード コーン間 処理順序決定 CPU時間 各部分回路 コーン内 重複入力 CPU割当 追加候補
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2000年7月14日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (17)

課題

パタン生成時間を短縮できるテストパタン生成方法および装置を提供する。

解決手段

回路出力端子の値に影響する回路ブロックコーンとする。回路全体からコーンをゲート数昇順に抽出(S21)して集めて(S3)パタン生成単位である部分回路を作成する(S4)。抽出コーンとパタン生成中の部分回路の重なりが閾値を越えていれば(S32)当該コーンを後回しにして、該当するコーンが残っていなければ(S33)閾値を大きくする(S34)。部分回路が作成される(S4)とそこに含まれる未検出故障リストを作成して回路全体の未検出故障リストから除き(S41)、空きCPUに部分回路情報故障リストを渡し(S6)てパタンを生成させる(S7)。結果が返送(S8)されるとパタン未生成故障情報を回路全体の未検出故障リストに戻す。以上の処理を故障検出率目標値になるか全コーンのパタンを生成する(S10)まで繰り返す。

概要

背景

LSI等の集積回路の複雑化,大規模化に伴い、テストパタンを生成させる回路全体を所定の規模を持つ複数の部分回路に分割し、各部分回路テストパタン生成複数台コンピュータ分散処理させる手法が用いられるようになってきている。図11はこうした回路分割分散処理手法と用いたテストパタン生成装置についてその概略構成を示したものである。図示したように、このテストパタン生成装置は複数台のEWSエンジニアリングワークステーション)がLAN(ローカルエリアネットワーク)等のネットワークNWを介して互いに接続されている。なお、同図に示したような形態以外にも、複数台のCPU(中央演算処理装置)がバスで接続されたマルチプロセッサ構成のコンピュータを1台だけ用いるような形態であっても良く、これら以外にも様々な実現形態が考えられる。

図中、EWS1-1〜1-n(n:自然数)はいずれもテストパタンの自動生成処理を担うコンピュータであって、各EWSはある一時点では1個の部分回路についてテストパタン生成を行う。なお、以下ではこれら各EWSに搭載されているCPUを「リモートCPU」と呼ぶことにする。一般に、回路分割によって得られる部分回路の総数はリモートCPUの台数“n”に比べて遙かに大きな値としてある。一方、EWS1-0はこれらEWS1-1〜1-nを統括制御するコンピュータであって、テストパタン生成対象となっている回路全体を部分回路に分割したのち、各部分回路のテストパタン生成処理をEWS1-1〜1-nに実行させて、回路全体のテストパタン生成を分散処理させている。なお、以下ではEWS1-0に搭載されているCPUを「ローカルCPU」と呼ぶことにする。

ローカルCPUは、部分回路の構成を示す情報(図中の「部分回路情報」)と当該部分回路について検出すべき故障情報集合(図中の「故障リスト」)を各リモートCPUに渡して当該部分回路のテストパタン生成を依頼する。なお、故障情報には、回路全体における故障位置情報と当該故障が“1”故障なのか“0”故障なのかを示す識別情報などが含まれている。一方、ローカルCPUから処理を依頼されたリモートCPUは、部分回路情報と故障リストをもとにテストパタンを生成してローカルCPUに返送するほか、渡された故障リストのうち、生成されたテストパタンでは検出できない未検出故障情報を求めてローカルCPUに返送する。ここで、ローカルCPUは各リモートCPUがテストパタン生成処理を実行中であるか否かの処理状況を常に把握しており、何れかのリモートCPUからテストパタン生成の結果(パタン及び未検出故障情報)が返送されてくると、テストパタン生成処理を実行していない空き状態のリモートCPUを検索するとともに未だ処理していない部分回路を選択し、当該部分回路のテストパタン生成を当該リモートCPUに依頼するようにしている。

ところで、回路分割によって得られる部分回路の大きさ(ここでは、ゲート数)は、テストパタン生成の処理効率が最適になると考えられるゲート数の既定値を予め評価によって算出してある。そこで、ローカルCPUは各部分回路の大きさがこの既定値とほぼ同じになるように回路分割を行っているが、その際、次に述べるような「コーン」と呼ばれる回路ブロック複数個まとめて部分回路を構築している。ここで、図12はテストパタンの生成対象となっている回路全体のうちの一部分だけを抽出して例示した回路図である。図中、符号Ti1〜Ti7は入力端子,符号To1〜To2は出力端子,符号5-1〜5-6は論理ゲートである。また、符号6-1,6-2は入力端子,出力端子,論理ゲートで構成される回路ブロックであって、円錐の断面に類似した形状に着目して本明細書ではこれら回路ブロックをコーン(cone)と呼んでいる。なお、これら入力端子,出力端子は当該回路全体と外部との間の境界になっていることから、本明細書ではこれらを特に外部入力端子外部出力端子と呼ぶことがある。

各コーンは出力端子と1対1に対応しており、ある出力端子から入力端子の方向に向かって論理ゲートを順次辿っていったときに、入力端子に到達するまでに通過した全ての論理ゲート,到達した全ての入力端子,出発点となった出力端子の集合として定義される。換言すれば、ある1つの出力端子に論理値伝播させることの可能な全ての論理ゲート及び入力端子の集まりと当該出力端子とで1つのコーンが形成されることになる。例えば、出力端子To1を起点として回路内を辿ってゆくと、この出力端子To1には論理ゲート5-1が接続されているので当該論理ゲートをコーンに含ませる。また、論理ゲート5-1には入力端子Ti1,Ti2および論理ゲート5-2が接続されているが、論理ゲート5-2は入力端子の方向には無いので入力端子Ti1,Ti2だけをコーンに含める。つまり、コーン6-1は出力端子To1,論理ゲート5-1,入力端子Ti1,Ti2で構成される。コーン6-2も同様の手順で作成され、当該コーンには出力端子To2,論理ゲート5-2〜5-6,入力端子Ti2〜Ti7が含まれる。以上の説明から分かるように、テストパタン生成対象の回路全体には出力端子の数と同じだけのコーンが存在することになる。

なお、図12には示していないが、テストパタン生成対象回路スキャン化されているものについては、当該回路内に含まれるスキャン可能なフリップフロップ(以下では「FF」と略記する)は入力端子または出力端子と全く等価なものとして扱われる。つまり、当該回路の外部から論理値を設定しあるいは参照できるものは、入力端子ないし出力端子と等価なものとして扱えるということである。したがって、出力端子から回路を入力端子方向に辿っていってスキャンFFに到達したならばこれを入力端子と同等のものと見なせるとともに、当該スキャンFFを出力端子と同等のものと見なせるため、当該スキャンFFを起点として新たなコーンが定義されることになる。ちなみに、これ以降は説明が煩雑になるのを避けるために、特記しない限りはスキャンFFの含まれていない回路についてのみ説明を行うが、入力端子又は出力端子と等価なスキャンFFが含まれる回路についても全く同様に考えることができる。

次に、図13は従来のテストパタン生成装置についてその構成の要部を示したブロック図である。図中、ローカルCPU1Lは図11に示したEWS1-0上のCPUに相当し、リモートCPU1Rは図11に示したEWS1-1〜1-nの何れかに搭載されたCPUに相当する。回路情報記憶部11は、テストパタン生成対象の回路全体について、入力端子,出力端子,論理ゲートの種別とそれらの間の接続関係などが記述された回路情報を記憶する。外部出力端子リスト作成部12は、回路情報記憶部11に記憶されている回路情報の中から全ての出力端子を抽出して、これら出力端子のデータを外部出力端子リスト記憶部13に記憶させる。なお、スキャン化された回路の場合、外部出力端子リスト作成部12は出力端子のほかにスキャンFFも合わせて抽出する。部分回路作成部14は、回路情報記憶部11の記憶内容と外部出力端子リスト記憶部13の記憶内容に基づき、当該回路全体に含まれるコーンから部分回路を構築して部分回路記憶部15に記憶させる。

このほか、故障情報記憶部16は回路全体について検出すべき全ての故障情報を記憶する。パタン未作成故障リスト制御部17は、故障情報記憶部16の記憶内容とパタン作成済故障情報記憶部27(後述)の記憶内容に基づき、未だテストパタンの作成されていない故障情報がパタン未作成故障リスト記憶部18に保持されるように、その記憶内容を更新する。部分回路故障リスト作成部19は、あるリモートCPUに部分回路のテストパタン生成処理を依頼する場合に、当該部分回路に関する部分回路記憶部15の記憶内容とパタン未作成故障リスト記憶部18の記憶内容に基づき、当該部分回路に含まれる故障リストを作成してこれを部分回路故障リスト記憶部20に記憶させる。リモートCPU割当制御部24はリモートCPU1Rの各々の実行状態を管理しており、空き状態のリモートCPU1Rを選択するとともに、生成された部分回路に関する回路情報および故障リストを当該リモートCPU1Rに引き渡してテストパタン生成を依頼する。このほか、リモートCPU割当制御部24は図示を省略した信号線を介してローカルCPU1L内の各部と通信し、テストパタン生成の終了判定等の処理を実現している。

一方、リモートCPU1Rにおいて、自動テストパタン生成部25はローカルCPU1Lから渡される部分回路情報(部分回路記憶部15)と、部分回路に含まれる故障リスト(部分回路故障リスト記憶部20)に基づき、当該故障リストに含まれる各故障情報に対応するテストパタンを生成させる。その結果、自動テストパタン生成部25は生成されたテストパタンをテストパタン記憶部26へ記憶させるとともに、渡された故障リスト中でもはや処理する必要のなくなった故障情報をパタン作成済故障情報としてパタン作成済故障情報記憶部27に記憶させる。なお、パタン作成済故障情報には、テストパタンを生成することのできた故障情報のほか、テストパタン生成が困難で処理が打ち切られた故障情報や、回路の冗長性等が原因でどのコーンでもテストパタンを作成できないことが判明した故障情報なども含まれている。こうしたことから、テストパタンの作成されなかった故障情報に関しては、作成できなかった理由を示す情報が併せてパタン作成済故障情報記憶部27に記憶される。

他方、ローカルCPU1L内に設けられたパタンマージ部21は、リモートCPU1Rでそれぞれ生成されたテストパタンとテストパタン出力部28に記憶されているテストパタンを併合して、生成されたテストパタンを順次テストパタン出力部28に蓄積させてゆく。以上のほかに、上述したパタン未作成故障リスト制御部17は、回路全体に含まれている全ての部分回路についてテストパタン生成処理が行われた時点で、テストパタンの作成されなかった故障情報をパタン未作成故障リスト出力部29へ出力する。その際、パタン未作成故障リスト制御部17は、パタン未作成故障リストに加えて、各故障情報のテストパタンが如何なる理由で作成されなかったかを併せて格納するようにしている。この理由としては、所期故障検出率が得られたために未処理の故障情報についてのテストパタン生成が不要となったこと,テストパタン生成に要する処理時間が膨大でテストパタン生成を諦めたこと,回路が冗長なためにテストパタンを生成できなかったことなどが挙げられる。

ここで、図14は図13に示した部分回路作成部14の構成をさらに詳しく示したものであって、図13に示したものと同じ構成要素については同一の符号を付してある。図中、コーン抽出部31は、コーンを部分回路に追加するために、外部出力端子リスト記憶部13に記憶されている出力端子のうち、未だ取り出されていない出力端子をランダムに1個選択する。そして、コーン抽出部31は回路情報記憶部11の記憶内容に基づき、選択された出力端子に対応するコーンを求めて当該コーンの回路情報をコーン記憶部32に格納する。一方、部分回路記憶部15には作成途上にある部分回路のゲート数と当該部分回路の回路情報が保持される。

部分回路ゲート数カウント部33は、コーン記憶部32上に抽出されたコーンを部分回路記憶部15上の部分回路に追加する。すなわち、部分回路ゲート数カウント部33は、コーン記憶部32からコーンの回路情報を取り出してそのゲート数を算出し、これを部分回路記憶部15上の部分回路のゲート数に加算することで、作成途上にある部分回路の総ゲート数を更新する。その際、部分回路ゲート数カウント部33は、コーン間重複している論理ゲートについてはそれらのゲート数を部分回路の総ゲート数へ算入しないようにしている。また、部分回路ゲート数カウント部33は取り出されたコーンの回路情報を部分回路記憶部15上の部分回路の回路情報に追加する。さらに、部分回路ゲート数カウント部33は、更新された部分回路の総ゲート数が上述した既定値に達したかどうかを調べて、当該条件が満足された時点でコーン抽出部31に指示を行ってコーンの選択動作を停止させる。以上のような構成によって、リモートCPU1Rに与えるべき部分回路が部分回路記憶部15上に作成される。なお、部分回路ゲート数カウント部33は部分回路の作成を新たに始める度に、部分回路記憶部15上における部分回路の総ゲート数を“0”に初期化するとともに回路情報を空の状態に初期化する。

次に、図15は上記構成を有するテストパタン生成装置で実施されるテストパタン生成処理の手順を示したフローチャートである。まず、テストパタン生成対象の回路に関して、回路情報および故障情報をそれぞれ回路情報記憶部11および故障情報記憶部16に記憶させておく(ステップS1)。次に、ローカルCPU1Lに対してテストパタン生成を指示すると、外部出力端子リスト作成部12は回路情報の中から出力端子を全て抽出して外部出力端子リストを作成する。そこで、部分回路作成部14は作成された外部出力端子の中からまだ選択されていない出力端子をランダムに1個選択して当該出力端子に対応するコーンを求める(ステップS2)。次いで、部分回路作成部14は選択されたコーンをこれから作成する部分回路に加え(ステップS3)たのち、当該部分回路のゲート数を算出して作成途中の部分回路の総ゲート数が上記既定値に達しているかどうかを判定する(ステップS4)。もし部分回路のゲート数が上記既定値に達していない(同判断結果が“No”)のであれば、当該既定値に達する(同判断結果が“Yes”)までステップS2〜S4を繰り返す。こうして、コーンがランダムに1つずつ選択されて部分回路に加えられてゆき、最終的に充分な大きさの部分回路が得られる。この後も、部分回路作成部14は部分回路を順次作成してゆく。なお、テストパタン生成対象の回路から取り出すべきコーンがなくなった場合、部分回路作成部14は作成途上の部分回路の総ゲート数が上記既定値に達していなくともその時点の部分回路を最終的な部分回路として決定する。

一方、パタン未作成故障リスト制御部17は与えられた故障情報をもとに回路全体のパタン未作成故障リストを作成し、これをパタン未作成故障リスト記憶部18に格納しておく。次に、部分回路故障リスト作成部19は、部分回路作成部14が部分回路を生成する度に、パタン未作成故障リスト記憶部18の記憶内容を参照しつつ、生成された部分回路に含まれるパタン未作成故障リストを作成してこれを部分回路故障リスト記憶部20に格納する(ステップS5)。次に、リモートCPU割当制御部24は、作成済みの部分回路の中から何れかを選択し、当該部分回路に関する回路情報と故障リストをそれぞれ部分回路記憶部15と部分回路故障リスト記憶部20から読み出し、空き状態にあるリモートCPU1Rを検索して当該リモートCPUへ部分回路情報および故障リストを渡す(ステップS6)。このリモートCPU1Rでは、自動テストパタン作成部25が選択された部分回路についてテストパタンを生成(ステップS7)してテストパタン記憶部26に格納するとともに、テストパタンの作成された故障情報のリストをパタン作成済故障情報記憶部27に格納する。

この後、テストパタンを生成していた何れかのリモートCPU1Rがその処理を完了させると、当該リモートCPUは生成させたテストパタンとパタン作成済故障情報をローカルCPU1Lに返送する(ステップS8)。これにより、ローカルCPU1Lでは、パタン未作成故障リスト制御部17がパタン未作成故障リスト記憶部18に記憶されている回路全体のパタン未作成故障リストの中から、返送されてきたパタン作成済故障情報を削除する。このとき、パタン未作成故障リスト制御部17は更新されたパタン未作成故障リストをもとに回路全体の故障検出率を算出しておく。また、パタンマージ部21は返送されてきたテストパタンをテストパタン出力部28に記憶されているテストパタン(この場合は最初なので空)へ追加する(ステップS9)。

次に、リモートCPU割当制御部24は、パタン未作成故障リスト制御部17の算出した故障検出率が予め決められた目標値(たとえば95%)に達しているかどうかを判定するとともに、テストパタン生成対象回路内に処理されていないコーンが未だ残っているかどうかを部分回路作成部14に問い合わせる。そして、未処理のコーンがまだ残っており,かつ,故障検出率も上記目標値に到達していない(ステップS10の判断結果が“No”)のであれば、前述したステップS2〜S10の処理を繰り返して、部分回路を空き状態のリモートCPU1Rに割り当ててゆく。その後、故障検出率が上記目標値に達するか或いは未処理のコーンが無くなってステップS10の判断結果が“Yes”になると、リモートCPU割当制御部24はパタン未作成故障リスト制御部17に指示して、パタン未作成故障リスト18に記憶されているパタン未作成故障リストをパタン未作成故障リスト出力部29に転送する。これによって、テストパタンおよびパタン未作成故障リストを取り出すことが可能になる(ステップS11)。

概要

パタン生成時間を短縮できるテストパタン生成方法および装置を提供する。

回路の出力端子の値に影響する回路ブロックをコーンとする。回路全体からコーンをゲート数の昇順に抽出(S21)して集めて(S3)パタン生成単位である部分回路を作成する(S4)。抽出コーンとパタン生成中の部分回路の重なりが閾値を越えていれば(S32)当該コーンを後回しにして、該当するコーンが残っていなければ(S33)閾値を大きくする(S34)。部分回路が作成される(S4)とそこに含まれる未検出故障リストを作成して回路全体の未検出故障リストから除き(S41)、空きCPUに部分回路情報と故障リストを渡し(S6)てパタンを生成させる(S7)。結果が返送(S8)されるとパタン未生成故障情報を回路全体の未検出故障リストに戻す。以上の処理を故障検出率が目標値になるか全コーンのパタンを生成する(S10)まで繰り返す。

目的

本発明は上記の点に鑑みてなされたものであり、その目的は、回路分割の手法を用いてテストパタンを生成させる場合に、部分回路の処理順序を考慮することで、テストパタン生成に要する処理時間を短縮できるテストパタン生成方法および装置を提供することにある。また、本発明の目的は、回路分割とともに分散処理の手法を用いてテストパタンを生成する場合に、既に処理中の部分回路と作成中の部分回路へ追加すべきコーンとの間の重なりを考慮することで、テストパタン生成にかかる処理時間を小さくすることのできるテストパタン生成方法および装置を提供することにある。さらに、本発明の目的は、回路分割とともに分散処理の手法を用いてテストパタンを生成する場合に、分散処理される部分回路間の重複をなくすことで、テストパタン生成の処理時間をいっそう短くできるテストパタン生成方法および装置を提供することにある。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

テストパタン生成対象となる全体回路を複数の部分回路に分割し、各部分回路についてテストパタンを生成して、テストパタンが生成された故障を前記全体回路の未検出故障リストから削除してゆくテストパタン生成装置において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンテストパタン生成に要する処理時間の小さな順番に並べるコーン選択順序決定手段と、該順番で前記コーンを選択しながら集めて前記部分回路を生成する部分回路作成手段とを具備することを特徴とするテストパタン生成装置。

請求項2

前記部分回路を一つずつ選択し、前記部分回路のテストパタンを生成するテストパタン生成手段へ前記選択された部分回路を割り当ててゆくことで、前記部分回路のテストパタンを逐次的に生成させる手段を具備することを特徴とする請求項1記載のテストパタン生成装置。

請求項3

前記部分回路のテストパタンを互いに独立して生成する複数のテストパタン生成手段と、前記部分回路をテストパタン生成処理中でないテストパタン生成手段へ割り当ててゆくことで、前記複数の部分回路のテストパタン生成を前記複数のテストパタン生成手段に分散処理させる手段とを具備することを特徴とする請求項1記載のテストパタン生成装置。

請求項4

テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆきながら、テストパタンが生成された故障を前記全体回路の未検出故障リストから削除して、前記全体回路のテストパタン生成を分散処理させるテストパタン生成装置において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンと、前記複数のテストパタン生成手段に割り当てられている全ての部分回路との間の重なりの度合いを算出する算出手段と、前記重なりの度合いが閾値を越えているか否かを判定する判定手段と、該判定の結果をもとに、前記重なりの度合いが前記閾値を越えないコーンを集めて前記部分回路を生成する部分回路作成手段とを具備することを特徴とするテストパタン生成装置。

請求項5

テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆくことで、前記全体回路のテストパタン生成を分散処理させるテストパタン生成装置において、前記全体回路の未検出故障リストのうち、前記複数のテストパタン生成手段に割り当てられている全ての部分回路の未検出故障リストを除外した未検出故障リストを保持する未検出故障保持手段を具備し、該未検出故障保持手段に保持されている未検出故障リストをもとに、前記各部分回路の未検出故障リストを生成して、これら未検出故障リストのテストパタンを前記複数のテストパタン生成手段にそれぞれ生成させることを特徴とするテストパタン生成装置。

請求項6

テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆくことで、前記全体回路のテストパタン生成を分散処理させるテストパタン生成装置において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンをテストパタン生成に要する処理時間の小さな順番に並べるコーン選択順序決定手段と、前記複数のテストパタン生成手段に割り当てられている全ての部分回路と前記コーンとの間の重なりの度合いを算出する算出手段と、前記重なりの度合いが閾値を越えているか否かを判定する判定手段と、前記コーンを前記順番で選択しながら、前記判定手段による判定結果をもとに、前記重なりの度合いが前記閾値を越えないコーンを集めて前記部分回路を生成する部分回路作成手段と、前記全体回路の未検出故障リストのうち、前記複数のテストパタン生成手段に割り当てられている全ての部分回路の未検出故障リストを除外した未検出故障リストを保持する未検出故障保持手段とを具備し、該未検出故障保持手段に保持されている未検出故障リストをもとに、前記部分回路作成手段で生成された部分回路の未検出故障リストを生成し、該未検出故障リストのテストパタンを前記テストパタン生成手段に生成させることを特徴とするテストパタン生成装置。

請求項7

テストパタンの生成対象となる全体回路を複数の部分回路に分割し、各部分回路についてテストパタンを生成して、テストパタンが生成された故障を前記全体回路の未検出故障リストから削除してゆくテストパタン生成方法において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンを予めテストパタン生成に要する処理時間の小さな順番に並べておく手順と、該順番で前記コーンを選択しながら集めて前記部分回路を生成し、該部分回路について前記テストパタンを生成してゆく手順とを有することを特徴とするテストパタン生成方法。

請求項8

テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆきながら、テストパタンが生成された故障を前記全体回路の未検出故障リストから削除して、前記全体回路のテストパタン生成を分散処理させるテストパタン生成方法において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンと、前記複数のテストパタン生成手段に割り当てられている全ての部分回路との間の重なりの度合いを算出する算出手順と、前記重なりの度合いが閾値を越えているか否かを判定する判定手順と、前記重なりの度合いが前記閾値を越えている場合は、前記コーンを後回しにして新たなコーンについて前記算出手順及び前記判定手順を実行してゆくことで、前記重なりの度合いが前記閾値を越えないコーンを集めて前記部分回路を生成し、該部分回路について前記テストパタンを生成してゆく手順とを有することを特徴とするテストパタン生成方法。

請求項9

テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆくことで、前記全体回路のテストパタン生成を分散処理させるテストパタン生成方法において、前記部分回路を前記テストパタン生成手段へ割り当てる場合に、前記全体回路の未検出故障リストをもとに該部分回路の未検出故障リストを求める手順と、該部分回路の未検出故障リストを前記全体回路の未検出故障リストから一旦削除して、前記部分回路の未検出故障リストのテストパタンを前記テストパタン生成手段に生成させる手順と、前記テストパタン生成手段でテストパタンが生成されなかった故障を前記全体回路の未検出故障リストに戻してやる手順とを有することを特徴とするテストパタン生成方法。

請求項10

テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆくことで、前記全体回路のテストパタン生成を分散処理させるテストパタン生成方法において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンを予めテストパタン生成に要する処理時間の小さな順番に並べておく手順と、前記コーンを前記順番で選択してゆく選択手順と、前記複数のテストパタン生成手段に割り当てられている全ての部分回路と前記選択手順で選択されたコーンとの間の重なりの度合いを算出する算出手順と、前記重なりの度合いが閾値を越えているか否かを判定する判定手順と、前記重なりの度合いが前記閾値を越えている場合は、前記選択されたコーンを後回しにして前記選択手順から前記判定手順までをさらに実行することで、前記重なりの度合いが前記閾値を越えないコーンを集めて前記部分回路を生成する部分回路生成手順と、前記全体回路の未検出故障リストをもとに、前記部分回路生成手順で生成された部分回路の未検出故障リストを求めて、該部分回路の未検出故障リストを前記全体回路の未検出故障リストから一旦削除する手順と、前記部分回路の未検出故障リストのテストパタンを前記テストパタン生成手段に生成させるテストパタン生成手順と、該テストパタン生成手順でテストパタンが生成されなかった故障を前記全体回路の未検出故障リストに戻してやる手順とを有することを特徴とするテストパタン生成方法。

請求項11

請求項7〜10の何れかの項に記載された各手順をコンピュータに実行させることを特徴とするテストパタン生成プログラムを記録した記録媒体

技術分野

0001

本発明は、LSI(大規模集積回路)等の故障検出に用いられるテストパタンを作成するテストパタン生成方法および装置ならびにテストパタン生成プログラムを記録した記録媒体に関する。さらに詳しくは、テストパタン生成の対象になっている回路全体を複数の部分回路に分割し、これら部分回路のテストパタンを分散処理によって生成してゆく場合に好適なテストパタン生成方法および装置ならびにテストパタン生成プログラムを記録した記録媒体に関するものである。

背景技術

0002

LSI等の集積回路の複雑化,大規模化に伴い、テストパタンを生成させる回路全体を所定の規模を持つ複数の部分回路に分割し、各部分回路のテストパタン生成を複数台コンピュータで分散処理させる手法が用いられるようになってきている。図11はこうした回路分割分散処理手法と用いたテストパタン生成装置についてその概略構成を示したものである。図示したように、このテストパタン生成装置は複数台のEWSエンジニアリングワークステーション)がLAN(ローカルエリアネットワーク)等のネットワークNWを介して互いに接続されている。なお、同図に示したような形態以外にも、複数台のCPU(中央演算処理装置)がバスで接続されたマルチプロセッサ構成のコンピュータを1台だけ用いるような形態であっても良く、これら以外にも様々な実現形態が考えられる。

0003

図中、EWS1-1〜1-n(n:自然数)はいずれもテストパタンの自動生成処理を担うコンピュータであって、各EWSはある一時点では1個の部分回路についてテストパタン生成を行う。なお、以下ではこれら各EWSに搭載されているCPUを「リモートCPU」と呼ぶことにする。一般に、回路分割によって得られる部分回路の総数はリモートCPUの台数“n”に比べて遙かに大きな値としてある。一方、EWS1-0はこれらEWS1-1〜1-nを統括制御するコンピュータであって、テストパタン生成対象となっている回路全体を部分回路に分割したのち、各部分回路のテストパタン生成処理をEWS1-1〜1-nに実行させて、回路全体のテストパタン生成を分散処理させている。なお、以下ではEWS1-0に搭載されているCPUを「ローカルCPU」と呼ぶことにする。

0004

ローカルCPUは、部分回路の構成を示す情報(図中の「部分回路情報」)と当該部分回路について検出すべき故障情報集合(図中の「故障リスト」)を各リモートCPUに渡して当該部分回路のテストパタン生成を依頼する。なお、故障情報には、回路全体における故障位置情報と当該故障が“1”故障なのか“0”故障なのかを示す識別情報などが含まれている。一方、ローカルCPUから処理を依頼されたリモートCPUは、部分回路情報と故障リストをもとにテストパタンを生成してローカルCPUに返送するほか、渡された故障リストのうち、生成されたテストパタンでは検出できない未検出故障情報を求めてローカルCPUに返送する。ここで、ローカルCPUは各リモートCPUがテストパタン生成処理を実行中であるか否かの処理状況を常に把握しており、何れかのリモートCPUからテストパタン生成の結果(パタン及び未検出故障情報)が返送されてくると、テストパタン生成処理を実行していない空き状態のリモートCPUを検索するとともに未だ処理していない部分回路を選択し、当該部分回路のテストパタン生成を当該リモートCPUに依頼するようにしている。

0005

ところで、回路分割によって得られる部分回路の大きさ(ここでは、ゲート数)は、テストパタン生成の処理効率が最適になると考えられるゲート数の既定値を予め評価によって算出してある。そこで、ローカルCPUは各部分回路の大きさがこの既定値とほぼ同じになるように回路分割を行っているが、その際、次に述べるような「コーン」と呼ばれる回路ブロック複数個まとめて部分回路を構築している。ここで、図12はテストパタンの生成対象となっている回路全体のうちの一部分だけを抽出して例示した回路図である。図中、符号Ti1〜Ti7は入力端子,符号To1〜To2は出力端子,符号5-1〜5-6は論理ゲートである。また、符号6-1,6-2は入力端子,出力端子,論理ゲートで構成される回路ブロックであって、円錐の断面に類似した形状に着目して本明細書ではこれら回路ブロックをコーン(cone)と呼んでいる。なお、これら入力端子,出力端子は当該回路全体と外部との間の境界になっていることから、本明細書ではこれらを特に外部入力端子外部出力端子と呼ぶことがある。

0006

各コーンは出力端子と1対1に対応しており、ある出力端子から入力端子の方向に向かって論理ゲートを順次辿っていったときに、入力端子に到達するまでに通過した全ての論理ゲート,到達した全ての入力端子,出発点となった出力端子の集合として定義される。換言すれば、ある1つの出力端子に論理値伝播させることの可能な全ての論理ゲート及び入力端子の集まりと当該出力端子とで1つのコーンが形成されることになる。例えば、出力端子To1を起点として回路内を辿ってゆくと、この出力端子To1には論理ゲート5-1が接続されているので当該論理ゲートをコーンに含ませる。また、論理ゲート5-1には入力端子Ti1,Ti2および論理ゲート5-2が接続されているが、論理ゲート5-2は入力端子の方向には無いので入力端子Ti1,Ti2だけをコーンに含める。つまり、コーン6-1は出力端子To1,論理ゲート5-1,入力端子Ti1,Ti2で構成される。コーン6-2も同様の手順で作成され、当該コーンには出力端子To2,論理ゲート5-2〜5-6,入力端子Ti2〜Ti7が含まれる。以上の説明から分かるように、テストパタン生成対象の回路全体には出力端子の数と同じだけのコーンが存在することになる。

0007

なお、図12には示していないが、テストパタン生成対象回路スキャン化されているものについては、当該回路内に含まれるスキャン可能なフリップフロップ(以下では「FF」と略記する)は入力端子または出力端子と全く等価なものとして扱われる。つまり、当該回路の外部から論理値を設定しあるいは参照できるものは、入力端子ないし出力端子と等価なものとして扱えるということである。したがって、出力端子から回路を入力端子方向に辿っていってスキャンFFに到達したならばこれを入力端子と同等のものと見なせるとともに、当該スキャンFFを出力端子と同等のものと見なせるため、当該スキャンFFを起点として新たなコーンが定義されることになる。ちなみに、これ以降は説明が煩雑になるのを避けるために、特記しない限りはスキャンFFの含まれていない回路についてのみ説明を行うが、入力端子又は出力端子と等価なスキャンFFが含まれる回路についても全く同様に考えることができる。

0008

次に、図13は従来のテストパタン生成装置についてその構成の要部を示したブロック図である。図中、ローカルCPU1Lは図11に示したEWS1-0上のCPUに相当し、リモートCPU1Rは図11に示したEWS1-1〜1-nの何れかに搭載されたCPUに相当する。回路情報記憶部11は、テストパタン生成対象の回路全体について、入力端子,出力端子,論理ゲートの種別とそれらの間の接続関係などが記述された回路情報を記憶する。外部出力端子リスト作成部12は、回路情報記憶部11に記憶されている回路情報の中から全ての出力端子を抽出して、これら出力端子のデータを外部出力端子リスト記憶部13に記憶させる。なお、スキャン化された回路の場合、外部出力端子リスト作成部12は出力端子のほかにスキャンFFも合わせて抽出する。部分回路作成部14は、回路情報記憶部11の記憶内容と外部出力端子リスト記憶部13の記憶内容に基づき、当該回路全体に含まれるコーンから部分回路を構築して部分回路記憶部15に記憶させる。

0009

このほか、故障情報記憶部16は回路全体について検出すべき全ての故障情報を記憶する。パタン未作成故障リスト制御部17は、故障情報記憶部16の記憶内容とパタン作成済故障情報記憶部27(後述)の記憶内容に基づき、未だテストパタンの作成されていない故障情報がパタン未作成故障リスト記憶部18に保持されるように、その記憶内容を更新する。部分回路故障リスト作成部19は、あるリモートCPUに部分回路のテストパタン生成処理を依頼する場合に、当該部分回路に関する部分回路記憶部15の記憶内容とパタン未作成故障リスト記憶部18の記憶内容に基づき、当該部分回路に含まれる故障リストを作成してこれを部分回路故障リスト記憶部20に記憶させる。リモートCPU割当制御部24はリモートCPU1Rの各々の実行状態を管理しており、空き状態のリモートCPU1Rを選択するとともに、生成された部分回路に関する回路情報および故障リストを当該リモートCPU1Rに引き渡してテストパタン生成を依頼する。このほか、リモートCPU割当制御部24は図示を省略した信号線を介してローカルCPU1L内の各部と通信し、テストパタン生成の終了判定等の処理を実現している。

0010

一方、リモートCPU1Rにおいて、自動テストパタン生成部25はローカルCPU1Lから渡される部分回路情報(部分回路記憶部15)と、部分回路に含まれる故障リスト(部分回路故障リスト記憶部20)に基づき、当該故障リストに含まれる各故障情報に対応するテストパタンを生成させる。その結果、自動テストパタン生成部25は生成されたテストパタンをテストパタン記憶部26へ記憶させるとともに、渡された故障リスト中でもはや処理する必要のなくなった故障情報をパタン作成済故障情報としてパタン作成済故障情報記憶部27に記憶させる。なお、パタン作成済故障情報には、テストパタンを生成することのできた故障情報のほか、テストパタン生成が困難で処理が打ち切られた故障情報や、回路の冗長性等が原因でどのコーンでもテストパタンを作成できないことが判明した故障情報なども含まれている。こうしたことから、テストパタンの作成されなかった故障情報に関しては、作成できなかった理由を示す情報が併せてパタン作成済故障情報記憶部27に記憶される。

0011

他方、ローカルCPU1L内に設けられたパタンマージ部21は、リモートCPU1Rでそれぞれ生成されたテストパタンとテストパタン出力部28に記憶されているテストパタンを併合して、生成されたテストパタンを順次テストパタン出力部28に蓄積させてゆく。以上のほかに、上述したパタン未作成故障リスト制御部17は、回路全体に含まれている全ての部分回路についてテストパタン生成処理が行われた時点で、テストパタンの作成されなかった故障情報をパタン未作成故障リスト出力部29へ出力する。その際、パタン未作成故障リスト制御部17は、パタン未作成故障リストに加えて、各故障情報のテストパタンが如何なる理由で作成されなかったかを併せて格納するようにしている。この理由としては、所期故障検出率が得られたために未処理の故障情報についてのテストパタン生成が不要となったこと,テストパタン生成に要する処理時間が膨大でテストパタン生成を諦めたこと,回路が冗長なためにテストパタンを生成できなかったことなどが挙げられる。

0012

ここで、図14図13に示した部分回路作成部14の構成をさらに詳しく示したものであって、図13に示したものと同じ構成要素については同一の符号を付してある。図中、コーン抽出部31は、コーンを部分回路に追加するために、外部出力端子リスト記憶部13に記憶されている出力端子のうち、未だ取り出されていない出力端子をランダムに1個選択する。そして、コーン抽出部31は回路情報記憶部11の記憶内容に基づき、選択された出力端子に対応するコーンを求めて当該コーンの回路情報をコーン記憶部32に格納する。一方、部分回路記憶部15には作成途上にある部分回路のゲート数と当該部分回路の回路情報が保持される。

0013

部分回路ゲート数カウント部33は、コーン記憶部32上に抽出されたコーンを部分回路記憶部15上の部分回路に追加する。すなわち、部分回路ゲート数カウント部33は、コーン記憶部32からコーンの回路情報を取り出してそのゲート数を算出し、これを部分回路記憶部15上の部分回路のゲート数に加算することで、作成途上にある部分回路の総ゲート数を更新する。その際、部分回路ゲート数カウント部33は、コーン間重複している論理ゲートについてはそれらのゲート数を部分回路の総ゲート数へ算入しないようにしている。また、部分回路ゲート数カウント部33は取り出されたコーンの回路情報を部分回路記憶部15上の部分回路の回路情報に追加する。さらに、部分回路ゲート数カウント部33は、更新された部分回路の総ゲート数が上述した既定値に達したかどうかを調べて、当該条件が満足された時点でコーン抽出部31に指示を行ってコーンの選択動作を停止させる。以上のような構成によって、リモートCPU1Rに与えるべき部分回路が部分回路記憶部15上に作成される。なお、部分回路ゲート数カウント部33は部分回路の作成を新たに始める度に、部分回路記憶部15上における部分回路の総ゲート数を“0”に初期化するとともに回路情報を空の状態に初期化する。

0014

次に、図15は上記構成を有するテストパタン生成装置で実施されるテストパタン生成処理の手順を示したフローチャートである。まず、テストパタン生成対象の回路に関して、回路情報および故障情報をそれぞれ回路情報記憶部11および故障情報記憶部16に記憶させておく(ステップS1)。次に、ローカルCPU1Lに対してテストパタン生成を指示すると、外部出力端子リスト作成部12は回路情報の中から出力端子を全て抽出して外部出力端子リストを作成する。そこで、部分回路作成部14は作成された外部出力端子の中からまだ選択されていない出力端子をランダムに1個選択して当該出力端子に対応するコーンを求める(ステップS2)。次いで、部分回路作成部14は選択されたコーンをこれから作成する部分回路に加え(ステップS3)たのち、当該部分回路のゲート数を算出して作成途中の部分回路の総ゲート数が上記既定値に達しているかどうかを判定する(ステップS4)。もし部分回路のゲート数が上記既定値に達していない(同判断結果が“No”)のであれば、当該既定値に達する(同判断結果が“Yes”)までステップS2〜S4を繰り返す。こうして、コーンがランダムに1つずつ選択されて部分回路に加えられてゆき、最終的に充分な大きさの部分回路が得られる。この後も、部分回路作成部14は部分回路を順次作成してゆく。なお、テストパタン生成対象の回路から取り出すべきコーンがなくなった場合、部分回路作成部14は作成途上の部分回路の総ゲート数が上記既定値に達していなくともその時点の部分回路を最終的な部分回路として決定する。

0015

一方、パタン未作成故障リスト制御部17は与えられた故障情報をもとに回路全体のパタン未作成故障リストを作成し、これをパタン未作成故障リスト記憶部18に格納しておく。次に、部分回路故障リスト作成部19は、部分回路作成部14が部分回路を生成する度に、パタン未作成故障リスト記憶部18の記憶内容を参照しつつ、生成された部分回路に含まれるパタン未作成故障リストを作成してこれを部分回路故障リスト記憶部20に格納する(ステップS5)。次に、リモートCPU割当制御部24は、作成済みの部分回路の中から何れかを選択し、当該部分回路に関する回路情報と故障リストをそれぞれ部分回路記憶部15と部分回路故障リスト記憶部20から読み出し、空き状態にあるリモートCPU1Rを検索して当該リモートCPUへ部分回路情報および故障リストを渡す(ステップS6)。このリモートCPU1Rでは、自動テストパタン作成部25が選択された部分回路についてテストパタンを生成(ステップS7)してテストパタン記憶部26に格納するとともに、テストパタンの作成された故障情報のリストをパタン作成済故障情報記憶部27に格納する。

0016

この後、テストパタンを生成していた何れかのリモートCPU1Rがその処理を完了させると、当該リモートCPUは生成させたテストパタンとパタン作成済故障情報をローカルCPU1Lに返送する(ステップS8)。これにより、ローカルCPU1Lでは、パタン未作成故障リスト制御部17がパタン未作成故障リスト記憶部18に記憶されている回路全体のパタン未作成故障リストの中から、返送されてきたパタン作成済故障情報を削除する。このとき、パタン未作成故障リスト制御部17は更新されたパタン未作成故障リストをもとに回路全体の故障検出率を算出しておく。また、パタンマージ部21は返送されてきたテストパタンをテストパタン出力部28に記憶されているテストパタン(この場合は最初なので空)へ追加する(ステップS9)。

0017

次に、リモートCPU割当制御部24は、パタン未作成故障リスト制御部17の算出した故障検出率が予め決められた目標値(たとえば95%)に達しているかどうかを判定するとともに、テストパタン生成対象回路内に処理されていないコーンが未だ残っているかどうかを部分回路作成部14に問い合わせる。そして、未処理のコーンがまだ残っており,かつ,故障検出率も上記目標値に到達していない(ステップS10の判断結果が“No”)のであれば、前述したステップS2〜S10の処理を繰り返して、部分回路を空き状態のリモートCPU1Rに割り当ててゆく。その後、故障検出率が上記目標値に達するか或いは未処理のコーンが無くなってステップS10の判断結果が“Yes”になると、リモートCPU割当制御部24はパタン未作成故障リスト制御部17に指示して、パタン未作成故障リスト18に記憶されているパタン未作成故障リストをパタン未作成故障リスト出力部29に転送する。これによって、テストパタンおよびパタン未作成故障リストを取り出すことが可能になる(ステップS11)。

発明が解決しようとする課題

0018

以上のように、従来のテストパタン生成装置では、複数のコーンをまとめて部分回路を作成してゆく際にこれらコーンの選択順序をいっさい考慮しておらず、テストパタン生成対象回路に存在するコーンの中からランダムにコーンを選択しているに過ぎない。そのため、従来のテストパタン生成装置では次に述べるような不都合が生じており、それが原因で無駄な処理時間がかかっているものと考えられる。すなわち、コーンを集めて部分回路を作ってゆくと、テストパタン生成対象の回路構成によっては、図12の領域Aに示したようにコーンとコーンとの間(ないしはこれらコーンの含まれる部分回路間)で入力端子やゲート共有されて互いに重なる部分が生じる。こうした場合に、コーン6-1,6-2のうちの何れかについて先にテストパタン生成がなされると、最初のテストパタン生成過程でテストパタンの生成された故障情報は回路全体のパタン未作成故障リストから除外されて、それ以後のテストパタン生成過程では処理対象外とされる。例えば、コーン6-2が先に処理されて領域A内の全ての故障についてもテストパタンが生成されたとすれば、その後にコーン6-1のテストパタンを生成する時点では、当該領域Aに含まれる故障情報が除かれた故障リストを対象にテストパタン生成処理が行われることになる。

0019

ここで、コーンの規模(ここではゲート数とする)と当該コーンのテストパタン生成に要する処理時間との関係は、単なる比例関係ではなく例えば指数関数的な関係があることが分かっている。そのため、図12に示した領域Aのテストパタン生成に要する処理時間に着目すると、同一の領域についてテストパタンを生成しているにもかかわらず、コーン6-2のテストパタン生成過程でかかる処理時間は、コーン6-1のテストパタン生成過程でかかる処理時間よりも長くなる。つまり、コーン間で重なりの生じる領域に着目した場合、ゲート数のより小さなコーンのテストパタン生成を先に行った方が、ゲート数のより大きなコーンのテストパタン生成を先に行うよりも全体の処理時間が少なくて済むことになる。

0020

しかるに、従来のようにコーンをランダムな順番で選択して部分回路を構成してゆくと、コーン間で重なりの存在する領域において、ゲート数のより大きなコーンのテストパタン生成処理が先に行われる事態が頻繁に発生してしまうことになる。換言すれば、ゲート数のより小さなコーンを優先させてテストパタンを生成しておけば処理時間が短くて済んだところが、ゲート数のより大きなコーンを先を処理しているために余分な処理時間がかかってしまっているわけである。なお、こうした不都合は、図11に示したように複数台のCPUでテストパタン生成を分担させる形態に限って生じるものではなく、例えば1台のCPUだけを用いてテストパタン生成処理を逐次的に行わせるような形態においても発生しうるものである。

0021

このほか、図11に示したように複数台のCPUでテストパタン生成を分散処理させる場合、従来のテストパタン生成装置がコーン間の重なりを考慮していないことが原因となって次のような不都合も生じてきている。いま、図16に示すように、あるリモートCPUが部分回路7についてテストパタン生成を行っており、その最中に当該リモートCPU以外の他のリモートCPUが空き状態となり、この空きリモートCPUに対して部分回路を割り当てる場合を想定する。そして、図示したコーン6-3,6-4のうちの何れかだけを新たに作成する部分回路へ追加するものとする。そうした場合、部分回路7との間で重複している領域がより小さいコーン6-3を選択する方が、新たに作成される部分回路と部分回路7との間で重複して生成されるテストパタンの数を少なくできる。ところが、前述したように、従来はコーンや部分回路の重なりを全く考慮に入れていないため、コーン6-4の含まれた部分回路が先に割り当てられて処理されてしまう可能性がある。そのため、余分なテストパタンが生成されてしまい、先に指摘したのと同様の問題が生じて分散処理による効用減殺してしまうことになる。

0022

また、従来のテストパタン生成装置では、テストパタンの生成を分散処理させることで以下に述べるような不都合も存在している。例えば、図12に示したコーン6-1,コーン6-2をそれぞれ含む部分回路について2台のEWSが並行してテストパタンを生成する場合を考える。この場合、従来のテストパタン生成装置ではコーン間の重なりを何ら考慮していないため、領域Aに含まれる故障情報に関しては2台のEWSでほぼ同時にテストパタンが重複して作成されてしまう。しかしながら、ある一つの故障については何れか一つの部分回路でだけテストパタンを作成すれば充分であって、テストパタンを多重に生成するようなことが頻繁に発生すると、せっかく複数台のEWSで分散処理させた効果がなくなってしまう。すなわち、テストパタンを記憶するためのメモリ容量やテストパタン生成に要する処理時間がそれだけ余分に必要となるのみならず、生成されたテストパタンを用いて回路をテストする場合にもそれだけ余計なテスト時間が必要になってくるためである。

0023

本発明は上記の点に鑑みてなされたものであり、その目的は、回路分割の手法を用いてテストパタンを生成させる場合に、部分回路の処理順序を考慮することで、テストパタン生成に要する処理時間を短縮できるテストパタン生成方法および装置を提供することにある。また、本発明の目的は、回路分割とともに分散処理の手法を用いてテストパタンを生成する場合に、既に処理中の部分回路と作成中の部分回路へ追加すべきコーンとの間の重なりを考慮することで、テストパタン生成にかかる処理時間を小さくすることのできるテストパタン生成方法および装置を提供することにある。さらに、本発明の目的は、回路分割とともに分散処理の手法を用いてテストパタンを生成する場合に、分散処理される部分回路間の重複をなくすことで、テストパタン生成の処理時間をいっそう短くできるテストパタン生成方法および装置を提供することにある。

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

0024

以上の課題を解決するために、請求項1記載の発明は、テストパタンの生成対象となる全体回路を複数の部分回路に分割し、各部分回路についてテストパタンを生成して、テストパタンが生成された故障を前記全体回路の未検出故障リストから削除してゆくテストパタン生成装置において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンをテストパタン生成に要する処理時間の小さな順番に並べるコーン選択順序決定手段と、該順番で前記コーンを選択しながら集めて前記部分回路を生成する部分回路作成手段とを具備することを特徴としている。また、請求項2記載の発明は、請求項1記載の発明において、前記部分回路を一つずつ選択し、前記部分回路のテストパタンを生成するテストパタン生成手段へ前記選択された部分回路を割り当ててゆくことで、前記部分回路のテストパタンを逐次的に生成させる手段を具備することを特徴としている。また、請求項3記載の発明は、請求項1記載の発明において、前記部分回路のテストパタンを互いに独立して生成する複数のテストパタン生成手段と、前記部分回路をテストパタン生成処理中でないテストパタン生成手段へ割り当ててゆくことで、前記複数の部分回路のテストパタン生成を前記複数のテストパタン生成手段に分散処理させる手段とを具備することを特徴としている。

0025

また、請求項4記載の発明は、テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆきながら、テストパタンが生成された故障を前記全体回路の未検出故障リストから削除して、前記全体回路のテストパタン生成を分散処理させるテストパタン生成装置において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンと、前記複数のテストパタン生成手段に割り当てられている全ての部分回路との間の重なりの度合いを算出する算出手段と、前記重なりの度合いが閾値を越えているか否かを判定する判定手段と、該判定の結果をもとに、前記重なりの度合いが前記閾値を越えないコーンを集めて前記部分回路を生成する部分回路作成手段とを具備することを特徴としている。また、請求項5記載の発明は、テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆくことで、前記全体回路のテストパタン生成を分散処理させるテストパタン生成装置において、前記全体回路の未検出故障リストのうち、前記複数のテストパタン生成手段に割り当てられている全ての部分回路の未検出故障リストを除外した未検出故障リストを保持する未検出故障保持手段を具備し、該未検出故障保持手段に保持されている未検出故障リストをもとに、前記各部分回路の未検出故障リストを生成して、これら未検出故障リストのテストパタンを前記複数のテストパタン生成手段にそれぞれ生成させることを特徴としている。

0026

また、請求項6記載の発明は、テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆくことで、前記全体回路のテストパタン生成を分散処理させるテストパタン生成装置において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンをテストパタン生成に要する処理時間の小さな順番に並べるコーン選択順序決定手段と、前記複数のテストパタン生成手段に割り当てられている全ての部分回路と前記コーンとの間の重なりの度合いを算出する算出手段と、前記重なりの度合いが閾値を越えているか否かを判定する判定手段と、前記コーンを前記順番で選択しながら、前記判定手段による判定結果をもとに、前記重なりの度合いが前記閾値を越えないコーンを集めて前記部分回路を生成する部分回路作成手段と、前記全体回路の未検出故障リストのうち、前記複数のテストパタン生成手段に割り当てられている全ての部分回路の未検出故障リストを除外した未検出故障リストを保持する未検出故障保持手段とを具備し、該未検出故障保持手段に保持されている未検出故障リストをもとに、前記部分回路作成手段で生成された部分回路の未検出故障リストを生成し、該未検出故障リストのテストパタンを前記テストパタン生成手段に生成させることを特徴としている。また、請求項7記載の発明は、テストパタンの生成対象となる全体回路を複数の部分回路に分割し、各部分回路についてテストパタンを生成して、テストパタンが生成された故障を前記全体回路の未検出故障リストから削除してゆくテストパタン生成方法において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンを予めテストパタン生成に要する処理時間の小さな順番に並べておく手順と、該順番で前記コーンを選択しながら集めて前記部分回路を生成し、該部分回路について前記テストパタンを生成してゆく手順とを有することを特徴としている。

0027

また、請求項8記載の発明は、テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆきながら、テストパタンが生成された故障を前記全体回路の未検出故障リストから削除して、前記全体回路のテストパタン生成を分散処理させるテストパタン生成方法において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンと、前記複数のテストパタン生成手段に割り当てられている全ての部分回路との間の重なりの度合いを算出する算出手順と、前記重なりの度合いが閾値を越えているか否かを判定する判定手順と、前記重なりの度合いが前記閾値を越えている場合は、前記コーンを後回しにして新たなコーンについて前記算出手順及び前記判定手順を実行してゆくことで、前記重なりの度合いが前記閾値を越えないコーンを集めて前記部分回路を生成し、該部分回路について前記テストパタンを生成してゆく手順とを有することを特徴としている。また、請求項9記載の発明は、テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆくことで、前記全体回路のテストパタン生成を分散処理させるテストパタン生成方法において、前記部分回路を前記テストパタン生成手段へ割り当てる場合に、前記全体回路の未検出故障リストをもとに該部分回路の未検出故障リストを求める手順と、該部分回路の未検出故障リストを前記全体回路の未検出故障リストから一旦削除して、前記部分回路の未検出故障リストのテストパタンを前記テストパタン生成手段に生成させる手順と、前記テストパタン生成手段でテストパタンが生成されなかった故障を前記全体回路の未検出故障リストに戻してやる手順とを有することを特徴としている。

0028

また、請求項10記載の発明は、テストパタンの生成対象となる全体回路を複数の部分回路に分割し、互いに独立してテストパタンを生成する複数のテストパタン生成手段に前記各部分回路を割り当ててゆくことで、前記全体回路のテストパタン生成を分散処理させるテストパタン生成方法において、前記全体回路に含まれる出力端子又はスキャンフリップフロップから回路を入力端子方向にたどって入力端子又はスキャンフリップフロップに到達するまでの集合であるコーンを予めテストパタン生成に要する処理時間の小さな順番に並べておく手順と、前記コーンを前記順番で選択してゆく選択手順と、前記複数のテストパタン生成手段に割り当てられている全ての部分回路と前記選択手順で選択されたコーンとの間の重なりの度合いを算出する算出手順と、前記重なりの度合いが閾値を越えているか否かを判定する判定手順と、前記重なりの度合いが前記閾値を越えている場合は、前記選択されたコーンを後回しにして前記選択手順から前記判定手順までをさらに実行することで、前記重なりの度合いが前記閾値を越えないコーンを集めて前記部分回路を生成する部分回路生成手順と、前記全体回路の未検出故障リストをもとに、前記部分回路生成手順で生成された部分回路の未検出故障リストを求めて、該部分回路の未検出故障リストを前記全体回路の未検出故障リストから一旦削除する手順と、前記部分回路の未検出故障リストのテストパタンを前記テストパタン生成手段に生成させるテストパタン生成手順と、該テストパタン生成手順でテストパタンが生成されなかった故障を前記全体回路の未検出故障リストに戻してやる手順とを有することを特徴としている。また、請求項11記載の発明は、請求項7〜10の何れかの項に記載された各手順をコンピュータに実行させることを特徴としている。

発明を実施するための最良の形態

0029

以下、図面を参照して本発明の実施形態について説明する。ここで、以下に述べる各実施形態で開示されるテストパタン生成装置の全体構成は図11に示した従来のものと同じである。また、本発明の各実施形態ではテストパタン生成プログラムと呼ばれるプログラムがEWS1-0〜1-nの動作を制御している。このテストパタン生成プログラムは、フロッピーディスク光磁気ディスクCD−ROMコンパクトディスク読み取り専用メモリ)等の可搬性のある記録媒体や、EWSに内蔵されるハードディスク装置等のコンピュータ読み取り可能な記録媒体に格納されている。そして、テストパタン生成プログラムはテストパタン生成処理を開始させるにあたって、ローカルCPU1L又はリモートCPU1Rの指示の下に上述した記録媒体からEWS1-0〜1-nの主記憶上に転送される。その後、これらEWS1-0〜1-nは主記憶上のテストパタン生成プログラムを実行することによって、テストパタン生成装置内の各部の動作を制御して以下に詳述する各種処理を実現している。なお、上述したように、ローカルCPU1LとリモートCPU1Rの機能は互いに大きく異なっており、テストパタン生成プログラムはEWS1-0とEWS1-1〜1-nとで別々のものが作成される。その際、テストパタン生成プログラムはそれぞれのEWSに内蔵されているハードディスク装置等へ個別に記憶させておくことができる。あるいは、テストパタン生成プログラムをEWS1-0側に一括して記憶しておき、テストパタン生成処理を開始する以前に、EWS1-1〜1-n用のテストパタン生成プログラムをEWS1-0からこれらn台のEWSへそれぞれ転送するようにしても良い。

0030

〔第1実施形態〕図1は本実施形態によるテストパタン生成装置の詳細な構成を示すブロック図であって、図中、図13に示した従来のものと同じ構成要素については同一の符号を付してある。図1において、外部出力端子リスト作成部41は、テストパタン生成に要する処理時間の小さなコーンから順次選択されてゆくように、各コーンに対応する外部出力端子のリストを生成して外部出力端子リスト記憶部42へ格納する。そこで以下、図2を参照して外部出力端子リスト作成部41の詳細な構成について説明する。なお、同図では図1に示したものと同じ構成要素については同一の符号を付してある。まず、外部出力端子抽出部51は図13に示した従来の外部出力端子リスト作成部12と同様の機能を持っている。すなわち外部出力端子抽出部51は、回路情報記憶部11に記憶されている回路情報の中から全ての出力端子を抽出して外部出力端子リスト記憶部13に格納する。外部出力端子リスト記憶部13は図13で説明した通りのものであるが、本実施形態では、中間的な外部出力端子リストを外部出力端子リスト記憶部13に記憶させておき、最終的な外部出力端子リストは外部出力端子リスト記憶部42に格納されるようにしている。

0031

一方、コーン処理順序調整部52は、テストパタン生成に要する処理時間の昇順ソートされた外部出力端子リストを生成するための回路であって、以下、このコーン処理順序調整部52を構成している各部について説明する。まず、コーン抽出部53は外部出力端子リスト記憶部13に記憶されている出力端子の中から未だ取り出されていないものを任意に1個選択し、回路情報記憶部11の記憶内容に基づいて、選択された出力端子に対応するコーンの回路情報を求めてこれをコーン記憶部54に格納する。また、コーン抽出部53はテストパタン生成対象回路内に含まれているコーンを全て取り出した場合に、その旨を処理順序決定部57(後述)へ通知する。ゲート数カウント部55は、コーン記憶部54に格納されているコーンの回路情報から当該コーンのゲート数を算出してコーンゲート数記憶部56に格納する。その際、ゲート数カウント部55は算出されたゲート数がどのコーンのものであるかを示す情報と、当該コーンに含まれる出力端子を示す情報をコーンゲート数記憶部56へ一緒に格納する。

0032

コーンゲート数記憶部56は、ゲート数カウント部55によって格納動作がなされる度にその旨を処理順序決定部57に通知する。処理順序決定部57は、コーンゲート数記憶部56から格納動作の通知がある度にコーン抽出部53に対してコーンの抽出を指示する。また、処理順序決定部57は、コーン抽出部53からテストパタン生成対象回路に含まれるコーンが全て取り出されたことを通知された場合に、コーンゲート数記憶部56に記憶されている全コーンのゲート数を参照することで、ゲート数をキーとして各コーンを昇順(つまりゲート数の小さい順)にソートしたのち、各コーンに対応する出力端子をソートされた順番で並べて外部出力端子リスト記憶部42に格納する。

0033

一方、図1に示した部分回路作成部43は、図13に示した部分回路作成部14とほぼ同様の構成および機能を有するものであって、以下の点で従来のものと相違している。すなわち、従来の部分回路作成部14においては、コーン抽出部31(図14参照)が外部出力端子リスト記憶部13の中から出力端子をランダムに選択するようにしていた。これに対して、本実施形態の部分回路作成部43では、コーン抽出部(図14に示したコーン抽出部31に相当)が外部出力端子リスト記憶部42に記憶されている順に出力端子を選択してゆくように構成されている。つまり、本実施形態ではゲート数の小さなものから順番にコーンが取り出されてコーン記憶部(図14に示したコーン記憶部32に相当)に格納されてゆくことになる。なお、本実施形態における部分回路作成部43の構成は、図14に示した部分回路作成部14と実質的に同じであるため、図示を省略する。なお、図1では回路情報記憶部11,故障情報記憶部16,テストパタン出力部28,パタン未作成故障リスト出力部29をローカルCPU1Lの外部に設けているが、これらの一部又は全部をローカルCPU1Lに内蔵させても良い。

0034

次に、図3は本実施形態のテストパタン生成装置で実施されるテストパタン生成処理の手順を示したフローチャートであって、図中、図15に示した従来のものと同じ処理ステップについては同一のステップ番号を付してある。まず、従来と同じく、テストパタン生成対象となる回路全体に関する回路情報と故障情報をそれぞれ回路情報記憶部11と故障情報記憶部16に記憶させておく(ステップS1)。次に、EWS1-0に設けられた図示しない入力装置等を操作して、ローカルCPU1Lへテストパタン生成を指示すると、外部出力端子リスト作成部41では以下に述べる処理が行われる。すなわち、外部出力端子抽出部51(図2参照)は、回路情報記憶部11から抽出した全ての出力端子を外部出力端子リスト記憶部13に格納して、まずは中間的な外部出力端子リストを作成する。次に、コーン抽出部53はテストパタン生成対象回路に含まれているコーンを1個選択してコーン記憶部54に格納する。すると、ゲート数カウント部55はコーン記憶部54上のコーンのゲート数を算出してこれをコーンゲート数記憶部56に格納する。

0035

こうしてコーンのゲート数が格納されると、処理順序決定部57はコーン抽出部53に対して次のコーンの選択を指示して、これ以降は、いま述べた一連の処理を繰り返し行う。その後、テストパタン生成対象の回路に存在するコーンが全て選択されたならば、コーンゲート数記憶部56には全てのコーンのゲート数が記憶されている。そこで処理順序決定部57は、全てのコーンをゲート数の小さな順にソートしたのち、各コーンに対応する出力端子をコーンがソートされた順番に並べて外部出力端子リスト記憶部42に格納する。これにより、部分回路作成部43(図1参照)は、外部出力端子リスト記憶部42に記憶されている順番で出力端子を選択してゆく。したがって、最初はゲート数の最も少ないコーンに含まれている出力端子が選択され、部分回路作成部43はこの最小ゲート数のコーンを部分回路に追加すべきコーンに決定する(ステップS21)。

0036

これ以後は図15に示した従来の場合と同様である。すなわち、部分回路作成部43はステップS21で選択されたコーンを部分回路に加え(ステップS3)、当該部分回路のゲート数が先の既定値に達する(ステップS4の判断結果が“Yes”)まで、ステップS21,S3,S4のループを繰り返す。この一連の処理で、テストパタン生成対象回路内のコーンがゲート数の小さい順に部分回路へ追加されて上記既定値にほぼ等しいゲート数の部分回路が得られる。これらの動作と並行して、パタン未作成故障リスト制御部17は回路全体のパタン未作成故障リストを作成する。その後、部分回路作成部43が部分回路記憶部15上に部分回路を格納すると、部分回路故障リスト作成部19は当該部分回路に含まれるパタン未作成故障リストを作成する(ステップS5)。そしてリモートCPU割当制御部24は、作成されている何れかの部分回路を選択して部分回路情報と故障リストを空き状態のリモートCPU1Rに引き渡し(ステップS6)てテストパタンを生成させる(ステップS7)。その後、何れかのリモートCPU1Rからテストパタン生成の結果が返送される(ステップS8)と、パタン未作成故障リスト制御部17は回路全体の未作成故障リストからパタン作成済故障情報を削除して回路全体の故障検出率を算出する。また、パタンマージ部21は返送されたテストパタンをテストパタン出力部28に追加する(ステップS9)。この後は、故障検出率が目標値に達するか未処理のコーンがなくなる(ステップS10の判断結果が“Yes”)までステップS21〜S10を繰り返すことで、テストパタンとパタン未作成故障リストが得られる(ステップS11)。

0037

以上のように、本実施形態では、部分回路が互いに重なっている場合には、テストパタン生成に要する時間が小さい部分回路を先に処理した方が回路全体の処理時間が小さくなることに着目して、ゲート数の小さい順にコーンを選択して部分回路を作成している。そのため、回路全体のテストパタンを生成させるのに必要となる処理時間を従来よりも短縮させることが可能である。なお、上述した説明では、テストパタン生成の処理時間の大小を予測するための指標として各コーンのゲート数を用いるようにしていた。こうした指標を用いたのは、コーン内部の論理ゲート間の接続関係等を調べることなく短時間で処理時間を算定できるためである。したがって、処理時間の予測に必要となるCPU時間やそれに必要となるメモリ容量として許容される範囲内で、各コーンの回路構成の詳細を考慮しても良く、そうすることで、コーンのゲート数のみを指標とした場合に比べていっそう高い精度で処理時間を見積もることが可能となる。また、上述した説明では、必要となるメモリ容量をなるべく少なくするために、コーンの情報を外部出力端子リストの形で保持するようにしていたが、メモリ容量に余裕があれば、コーンの回路情報そのものを保持するようにしても良い。

0038

〔第2実施形態〕図4は、本実施形態によるテストパタン生成装置の詳細な構成を示すブロック図であり、図中、図13に示した従来のものと同じ構成要素については同一の符号を付してある。本実施形態の部分回路作成部44は、部分回路を生成するにあたって、テストパタン生成対象回路から抽出されるコーンとその時点でテストパタン生成処理が実行中の部分回路との間の重なりの度合いを調べるようにしている。ここで、本実施形態ではこの重なりの度合いとして入力端子が重複している本数を用いている。そして、部分回路作成部44はこの重なりの度合いが或る閾値(後述する「入力端子重なり許容数」)を越えているコーンは部分回路に追加せずに、未だ抽出されていない別のコーンを抽出して部分回路への追加を試みるようにしている。なお、テストパタン処理中の部分回路と全く重なりのないコーンのみを選択肢とするのではなく、所定範囲内の重なりを許容しているのは、クロック信号やある種のコントロール信号は多数のコーンへ共通に入力されるため、全く重なりのないコーンがそれほど多くないためである。

0039

次に、図5を参照しつつ部分回路作成部44の詳細な構成を説明する。なお、図5において図4又は図14に示したものと同じ構成要素については同一の符号を付してある。まず、処理中外部入力端子リスト記憶部61は、EWS1-1〜1-n(即ち、リモートCPU1R)上でテストパタン生成処理が実行されている部分回路に含まれる入力端子を記憶するものである。そのために、処理中外部入力端子リスト記憶部61は、部分回路のゲート数が上記既定値に達したことを部分回路ゲート数カウント部33が検出した時点で、当該部分回路の回路情報を部分回路記憶部15から取り込み、その中から入力端子を抽出して現時点で記憶している外部入力端子リストへ追加する。その際、処理中外部入力端子リスト記憶部61は、追加された入力端子がEWS1-1〜1-nのうちの何れに割り当てられたのかを示す割当情報を併せて記憶しておく。このほか、処理中外部入力端子リスト記憶部61は、何れかのリモートCPU1Rからテストパタン生成結果が返送されると、上記割当情報をもとにして、その時点で記憶している外部入力端子リストから当該リモートCPU1Rに割り当てていた入力端子を削除する。なお、処理中外部入力端子リスト記憶部61は、テストパタン生成装置の初期化時において、その記憶内容を入力端子の全く登録されていない状態に初期化しておく。

0040

次に、重複数チェック部62は、コーン抽出部63によって抽出されたコーンをコーン記憶部32から取り出して当該コーンに含まれる外部入力端子リストを求める。そして、重複数チェック部62はこの外部入力端子リストに含まれている個々の入力端子について、処理中外部入力端子リスト記憶部61に登録されている外部入力端子リストの何れかに一致するかどうか判定し、一致する外部入力端子の数をカウントする。また、重複数チェック部62は、これら両者で重複する外部入力端子数が入力端子重なり許容数を越えているか否かを判定し、もし越えているのであれば、コーン抽出部63に対し、直前に抽出したコーンを後回しにして別のコーンを抽出するように指示するとともに、新たに抽出されたコーンについて上記判定処理を再度行うようにする。重複数チェック部62は上記判定条件を満足しないうちは別のコーンを繰り返し抽出させて、上記判定条件を満足するようになった時点でコーン記憶部32上のコーンを部分回路ゲート数カウント部33に送出する。

0041

なお、ここで言う「後回し」とは、入力端子重なり許容数を越えたコーンを作成中の部分回路に含ませないということである。つまり、後回しにされたコーンは部分回路に追加されないままであるため、この後に別の部分回路を作成する際には、後回しにされたコーンをこの別の部分回路へ追加する際の一候補とする必要がある。そこでコーン抽出部63は、重複数チェック部62からコーンを後回しにすることを通知されると、直前に抽出したコーンを当面は抽出対象候補から除外しておき、部分回路ゲート数カウント部33から部分回路が生成されたことを通知された時点で、後回しにしておいたコーンを次の部分回路生成の際の抽出対象候補となるようにする。なお、コーン抽出部63が有する機能はいま述べた点を除いて従来のコーン抽出部31(図14参照)と同じである。

0042

ところで、コーンの残り数が少なくなってきたり入力端子重なり許容数が小さ過ぎたりすると、部分回路に未だ追加されていないコーンの中に上記判定条件を満足するコーンが全く無くなってしまうことがある。そうした場合、重複数チェック部62は入力端子重なり許容数を現在値よりも大きな値(例えば現在値の2倍)に変更したのち、変更後の入力端子重なり許容数を越えないコーンが、部分回路へ未だ追加されていないコーンの中に存在するかどうかを再度調べるようにしている。この場合、後回しにされていたコーンを全て抽出対象候補とする必要があるため、重複数チェック部62は入力端子重なり許容数の変更をコーン抽出部63に通知し、コーン抽出部63が後回しにしておいたコーンを再び抽出対象候補とするようにしている。なお、入力端子重なり許容数として最初に設定しておく値,入力端子重なり許容数を大きくしてゆく場合の倍率(上述の場合は2倍)は、いずれもテストパタン生成対象の回路構成に応じておおよその値を設定するようにする。

0043

次に、図6は本実施形態のテストパタン生成装置で行われるテストパタン生成処理の手順を示したフローチャートであって、図中、図15に示した従来のものと同じ処理ステップについては同一のステップ番号を付してある。まず、従来と同じく、回路情報,故障情報をそれぞれ回路情報記憶部11,故障情報記憶部16に設定しておく(ステップS1)。次に、ローカルCPU1Lに対してテストパタン生成を指示すると、部分回路作成部44では、重複数チェック部62が入力端子重なり許容数の値(図中の“閾値”)を予め設定された値として例えば“3”に初期化する(ステップS31)。一方、外部出力端子リスト作成部12は従来と同様にテストパタン生成対象回路について外部出力端子リストを作成し、部分回路作成部44ではコーン抽出部63が作成された外部出力端子リストから未選択の外部出力端子をランダムに一つ選択し、これに対応するコーンを求めてコーン記憶部32に格納する(ステップS2)。

0044

次に、重複数チェック部62はコーン記憶部32からコーンを取り出し、当該コーンに含まれる入力端子と処理中外部入力端子リスト記憶部61に格納されている外部入力端子リストを照合して重複する入力端子数を算出し、その値がステップS31で初期設定された入力端子重なり許容数を越えているかどうか判定する(ステップS32)。最初のうちは、EWS1-1〜1-nのうちテストパタン生成処理を実行しているものが少なく、特に、最初の部分回路を作成する段階では同ステップの判断結果が必ず“No”となる。このように重複する入力端子数が許容範囲内にある場合、重複数チェック部62はコーン記憶部32から取り出したコーンを部分回路ゲート数カウント部33にそのまま送出する。すると部分回路ゲート数カウント部33は、従来と同様に、送られてきたコーンをこれから作成する部分回路に加え(ステップS3)てからそのゲート数を算出し、このゲート数が上述の既定値に達しているかどうかを判定する(ステップS4)。これ以降は従来と同様に、作成途上にある部分回路のゲート数が上記既定値に達する(同ステップの判断結果が“Yes”)までステップS2〜S4を繰り返してゆくことで充分な大きさの部分回路を得る。これにより、処理中外部入力端子リスト記憶部61は部分回路記憶部15から部分回路情報を取り込んでその中から入力端子を抽出し、これを現時点で記憶している外部入力端子リストへ追加する。

0045

これ以後は従来とほぼ同様の手順で行われることになる。すなわち、上述したステップS31〜S4の処理と並行してパタン未作成故障リストが作成される。その後、上述したように部分回路作成部44が部分回路を生成すると、当該部分回路に関するパタン未作成故障リストが生成(ステップS5)されるので、当該部分回路の回路情報およびパタン未作成故障リストを空き状態のリモートCPU1Rに引き渡して(ステップS6)テストパタンを生成させる(ステップS7)。その後、何れかのリモートCPU1Rがテストパタン生成の結果をローカルCPU1L側に返送する(ステップS8)と、パタン作成済故障情報を回路全体のパタン未作成故障リストから削除して回路全体の故障検出率を算出するとともに、生成されたテストパタンを作成済みのテストパタンとマージする(ステップS9)。このとき本実施形態では、処理中外部入力端子リスト記憶部61が、現時点で記憶されている外部入力端子リストのうち、テストパタン生成の結果を返送してきたリモートCPU1Rに割り当てていた入力端子を削除する。そして、回路全体の故障検出率が目標値に達するかあるいは未処理のコーンがなくなる(ステップS10)まで、ステップS31〜S10の処理を繰り返し、最後にテストパタンおよびパタン未作成故障リストを出力する(ステップS11)。

0046

以上のようにして、空き状態のリモートCPU1Rへ部分回路を割り当ててゆくと、ステップS2で抽出したコーンの入力端子と処理中部分回路の外部入力端子リストの間の重複数が入力端子重なり許容数を越えて、ステップS32の判断結果が“Yes”となる状況が生じうる。そうした場合、重複数チェック部62は、コーン抽出部63に対して未だ抽出されていないコーンが残っているかどうかを問い合わせる(ステップS33)。まだ残存コーンが存在する(同ステップの判断結果が“Yes”)場合、重複数チェック部62はコーン抽出部63に対して、直前のステップS2で抽出したコーンを後回しにさせて、未だ選択されていないコーンの中から何れかを再選択させる。これ以降、ステップS32の判断結果が“Yes”の間はステップS2,S32,S33を繰り返して抽出されたコーンを後回しにしてゆく。そしてステップS32の判断結果が“No”となった時点で、重複数チェック部62は抽出されたコーンを部分回路ゲート数カウント部33に送出し、ステップS3以下の処理を上述のように実行してゆく。

0047

ここで、ステップS2,S32,S33から成るループを繰り返しているうちに、未抽出のコーンの中でステップS32の条件を満足するものが全くなくなる状況(ステップS33の判断結果が“No”)も生じうる。こうした場合、重複数チェック部62は、入力端子重なり許容数を例えば現在値の2倍である“6”に変更(ステップS34)したのち、後回しにしていたコーンも含めて未だ部分回路に追加されていないコーンの中から何れかのコーンを選択(ステップS2)しながら、当該コーンがステップS32の条件を満たすかどうかを調べてゆく。これ以後は、ステップS32の条件を満たさない場合には新たなコーンを抽出してゆくとともに、未抽出のコーンが無くなった場合には入力端子重なり許容数をさらに大きくしてゆく。

0048

以上のように、本実施形態では、分散処理される部分回路同士が重なってしまう場合に、その重なりをできる限り小さくしてテストパタン生成処理を効率化させており、従来に比べて分散処理によるテストパタン生成効率を向上させることが可能となっている。なお、上述した説明では、処理中の部分回路と抽出コーンの間の重なりの度合いの指標として外部入力端子数を用いるようにしたが、これ以外の様々な指標を採用することも考えられる。例えば、重なりの度合いの算出に必要となるCPU時間およびメモリ容量が許容される範囲内で、互いに重複している論理ゲートのゲート数を指標として用いることができる。こうした指標を採用することによって、単に外部入力端子の重複数を用いた場合に比べてより高い精度で重なりの度合いを評価できるようになる。

0049

〔第3実施形態〕図7は、本実施形態によるテストパタン生成装置の詳細な構成を示すブロック図であって、図中、図13に示した従来のものと同じ構成要素については同一の符号を付してある。本実施形態では、図13に示したパタン作成済故障情報記憶部27の代わりにパタン未作成故障情報記憶部45が設けられている。パタン未作成故障情報記憶部45は、ローカルCPU1Lから渡された故障リストのうち、この後のテストパタン生成処理過程における処理対象とする必要がある故障情報を記憶するものである。すなわちこれら故障情報としては、自動テストパタン作成部46でテストパタンが生成されなかった故障情報のうち、全てのコーンでテストパタンを生成できないことが判明した故障およびテストパタン生成が困難で処理を打ち切るべきであると判定された故障を除外したものである。一方、自動テストパタン作成部46は、パタン作成済故障情報を出力するのでなく、テストパタンの生成されなかった故障情報を出力する点で図13に示した従来の自動テストパタン作成部25と相違している。したがって、これ以外の機能については従来のものと同じである。

0050

このほか本実施形態では、図13に示したパタン未作成故障リスト制御部17の代わりにパタン未作成故障リスト制御部47が設けられている。パタン未作成故障リスト制御部47は、部分回路に含まれている故障リストが作成された時点で、当該故障リストを部分回路故障リスト記憶部20から取り込み、その時点で記憶している回路全体のパタン未作成故障リストから当該部分回路の故障リストを削除する。つまり、ある部分回路とその後に生成される部分回路が重なっている場合に、重複している故障のテストパタン生成処理を先に作成した部分回路のみで行うようにしている。したがって本実施形態では、同一の故障が複数のリモートCPU1R上で同時に処理されることがなくなる。以上のほか、パタン未作成故障リスト制御部47は、リモートCPU1Rから送られてくるパタン未作成故障情報を取り込み、これをその時点で記憶しているパタン未作成故障リストへ追加する。

0051

次に、図8は本実施形態のテストパタン生成装置で行われるテストパタン生成処理の手順を示したフローチャートであって、図15に示した従来のものと同じ処理ステップについては同一のステップ番号を付してある。まず、ステップS1〜S5の各ステップの処理は従来のものと全く同じである。すなわち、回路情報および故障情報を設定(ステップS1)しておき、テストパタン生成が指示されると、全体の回路情報から外部出力端子リストを作成して、部分回路のゲート数が上記既定値に達する(ステップS4)まで、未選択の外部出力端子をランダムに選択して対応するコーンを求めて(ステップS2)部分回路に追加する(ステップS3)ことを繰り返す。一方で、設定された故障情報から回路全体のパタン未作成故障リストを作成しておき、部分回路が生成された時点で当該部分回路に含まれるパタン未作成故障リストを作成する(ステップS5)。

0052

こうして部分回路に含まれる故障リストが作成されると、パタン未作成故障リスト制御部47は、部分回路故障リスト記憶部20からいま生成された部分回路故障リストを取り込み、パタン未作成故障リスト記憶部18に記憶されている回路全体のパタン未作成故障リストのうち、当該部分回路故障リストを削除する(ステップS41)。この場合に、例えば図12に示した回路構成を想定し、コーン6-1を含む部分回路がEWS1-2に割り当てられ、その後のある時点において、コーン6-2を含む部分回路がEWS1-1に割り当てられるものとする。そうした場合、領域A中の故障情報を含めてコーン6-1内に存在する故障情報がまずEWS1-2に渡され、その後に、コーン6-2のうち領域Aを除外した部分の故障情報がEWS1-1に渡されることになる。

0053

この後、リモートCPU割当制御部24が生成された部分回路の回路情報と故障リストを空き状態のリモートCPU1Rに渡す(ステップS6)と、当該リモートCPU1R内の自動テストパタン生成部46はテストパタン生成処理を開始させる。その後、何れかのリモートCPU1Rでテストパタンの生成処理が完了すると、自動テストパタン作成部46は生成されたテストパタンを従来と同様にテストパタン記憶部26へ格納するとともに、テストパタンが生成されなかった故障リストを求めてパタン未作成故障情報記憶部45に格納する。この後、当該リモートCPU1RからローカルCPU1Lに対してテストパタンおよびパタン未作成故障情報が返送される(ステップS8)。

0054

すると、パタン未作成故障リスト制御部47は、この時点でパタン未作成リスト記憶部18に記憶されているパタン未作成故障リストに対して、リモートCPU1Rから返送されたパタン未作成故障情報を追加する(ステップS42)。これにより、当該リモートCPU1Rでテストパタンの生成されなかった故障については、これ以後に順次生成されてゆく部分回路のテストパタン生成過程でテストパタンを作成してゆくことが可能となる。そして、これ以後の動作は従来の場合と同様である。パタン未作成故障リスト制御部47は、部分回路のパタン未作成故障情報を追加後のパタン未作成故障リストに基づいて回路全体の故障検出率を算出し、また、パタンマージ部21はリモートCPU1Rから返送されたテストパタンをテストパタン出力部28の記憶内容に追加する。そして、算出された故障検出率が目標値に達するかあるいは未処理のコーンがなくなる(ステップS10)まで、ステップS2〜S10からなるループを繰り返し、最後にテストパタンおよびパタン未作成故障情報を出力する(ステップS11)。

0055

なお、本実施形態では、ある特定のコーンでのみ検出可能な故障がある場合に、この故障についてテストパタンが生成されないことがある。例えば、図12に示した領域A中の故障をコーン6-1だけが検出できるものとする。この場合に、コーン6-2を含む部分回路をEWS1-2に割り当て、引き続いてコーン6-1を含む部分回路をEWS1-1に割り当てて、これら2つの部分回路のテストパタン生成処理を並列的に行うとする。そうした場合、コーン6-2を含む部分回路を作成した時点で、パタン未作成故障リスト制御部47が領域Aに含まれる故障情報をパタン未作成故障リスト18から削除する。したがって、その後にコーン6-1を含む部分回路を作成する時点では、領域Aに含まれる故障がテストパタン未作成のものとして扱われず、EWS1-1に渡される部分回路の故障リストには含まれない。こうしたことから、コーン6-1を処理するEWS1-1では領域A内の故障は検出されず、一方で、領域A内の故障はコーン6-1でのみ検出できるためEWS1-2が当該故障を検出することもない。したがって、EWS1-2がテストパタン生成を完了させ、当該故障をパタン未作成故障情報としてパタン未作成故障リスト記憶部18に戻してもこれ以降のどのコーンでもテストパタンは生成されなくなる。

0056

以上のことは、あるコーン内では或る故障が冗長であると判断され、他のコーン内では当該故障が冗長ではないと判断される場合にも生じうる。つまり、回路全体として見れば当該故障は冗長ではないが、特定のコーン内に限定して見た場合に冗長に見えるような場合である。このような場合、前者のコーンを含む部分回路が先に生成され、その後に、後者のコーンを含む部分回路が生成されて、これら両コーンを分散処理させるときが問題となる。というのも、当該故障は前者の部分回路を作成した時点で回路全体のパタン未作成故障リストから一旦除外されるため、後者の部分回路には含まれなくなる。したがって、テストパタン生成処理の結果、前者のコーンでは当該故障が冗長とされ、後者のコーンでは当該故障がテストパタン生成対象となっておらず、結果的に当該故障に対するテストパタンは全く作成されなくなる。

0057

しかしながら、以上のような理由でテストパタンの生成されない故障があっても実際上は全く問題とならない。すなわち、一般的に回路全体の故障検出率を常に100%にする必要はなく、例えば95%程度の検出率図8のステップS10参照)が得られるテストパタンを用いて故障が発見されなければ、テスト対象のLSIに問題のないことが統計的に分かっている。したがって、上記程度の故障検出率が得られるテストパターンが生成されていれば良く、特定のコーンでのみ検出可能な故障が幾つか存在したとしても実用上は何ら問題ないわけである。以上のように、本実施形態では、部分回路間で重なる領域が存在する場合に、部分回路を作成した時点で当該領域内の未検出故障リストを回路全体の未検出故障リストから削除するようにしているため、当該領域内の故障について複数のリモートCPUが同時にテストパタンを生成するような状況を回避することができる。そのため、分散処理によるテストパタン生成処理がいっそう効率化される。

0058

〔各実施形態の組み合わせ〕以上説明した第1実施形態〜第3実施形態のうち、2つの実施形態を任意に組み合わせ、あるいは、全ての実施形態を組み合わせても良い。これら組み合わせによるテストパタン生成装置の構成とその動作は、これまでの説明と図1図8から明らかであるが、念のため、全実施形態を組み合わせた場合について以下に説明する。図9は第1実施形態〜第3実施形態を組み合わせた場合におけるテストパタン生成装置の構成を示すブロック図であって、図1図4図7に示したものと同じ構成要素については同一の符号を付してある。図9に示した各部の構成は上述した通りであるため、ここでは説明を繰り返さない。なお、部分回路作成部50は、図1に示した部分回路作成部43(第1実施形態)と図4に示した部分回路作成部44(第2実施形態)の機能を併せ持つものである。つまり、図5に示したコーン抽出部63が、外部出力端子をランダムに選択するのではなく、外部出力端子リスト記憶部(即ち、図9に示す外部出力端子リスト記憶部42)に記憶されているコーンゲート数の昇順に選択するようになっている。

0059

一方、図10図9に示したテストパタン生成装置の動作を示すフローチャートであって、図3図6図8に示したのと同じ処理ステップについては同一のステップ番号を付してある。そこで以下、このテストパタン生成装置の動作についてその概略を説明する。まず、回路情報および故障情報を設定(ステップS1)して、テストパタン生成対象回路に含まれるコーンをゲート数の昇順にソートして、これらコーンに対応する外部出力端子リストを作成するとともに、回路全体のパタン未作成故障リストを作成しておく。このほか、入力端子重なり許容数を予め決めてある値に初期化(ステップS31)しておく。次に、コーンをゲート数の小さい順に取り出し(ステップS21)、当該コーンと各リモートCPUで処理中の部分回路との間で互いに重複する入力端子数を求める(ステップS32)。もし、重複入力端子数が入力端子重なり許容数を越えていれば、当該コーンを後回しにして次のコーンを再抽出して、ステップS32の条件を満たすコーンを部分回路に追加(ステップS3)してゆく。その際、ステップS32の条件を満たすコーンが一つも無くなった場合(ステップS33)は、入力端子重なり許容数の値を増やし(ステップS34)て再度コーンの選択を試みる。つまり、コーンのゲート数は静的に定まるのでこれを基本としてコーンの処理順序を取り敢えず決定しておき、複数のリモートCPUによる分散処理を開始させた後は、テストパタン生成処理中の部分回路との間の重なりの程度を考慮しながらコーンの処理順序を動的に変更してゆくことになる。

0060

そして、部分回路のゲート数が既定値に達した時点(ステップS4)で、当該部分回路に含まれる未検出故障リストを作成(ステップS5)したのち、これを回路全体の未検出故障リストからいったん除外する(ステップS41)。次に、生成された部分回路の回路情報と未検出故障リストを空き状態のリモートCPU1Rに引き渡し(ステップS6)てテストパタンを生成させる(ステップS7)。以上の手順でテストパタン生成対象回路内の部分回路を順次作成してリモートCPU1Rに引き渡してゆくとともに、何れかのリモートCPU1Rがテストパタン生成を完了させる(ステップS8)と、ローカルCPU1Lは生成されたテストパタンを蓄積させるとともに、当該リモートCPU1Rがテストパタンを生成できなかった故障を回路全体の未検出故障リストに戻す(ステップS42)。この後は、以上述べた一連の処理を各部分回路について実施してゆき、回路全体の故障検出率が目標値に達するかテストパタン生成対象回路中に処理すべきコーンがなくなれば、回路全体のテストパタン生成が完了してテストパタンとパタン未検出故障リストを取り出し可能となる(ステップS11)。

発明の効果

0061

以上説明したように、請求項1〜3,7記載の発明では、テストパタン生成対象の全体回路を分割した各部分回路についてテストパタンを生成してゆくときに、テストパタン生成に要する処理時間の小さな順番にコーンを並べ、この順番でコーンを選択しながら集めて各部分回路を生成している。こうすることで、部分回路同士が重なって複数の部分回路に同一の故障が含まれる場合に、先に処理時間の小さな部分回路で重なり部分の故障のテストパタン生成が試みられ、テストパタンの生成された当該部分回路の故障リストが全体回路の未検出故障リストから除かれ、その後、処理時間の大きな部分回路のテストパタンが生成される時点では重なり部分の故障に対してテストパタンがさらに生成されることはない。したがって、従来に比べてテストパタン生成に要する全体の処理時間を短縮させることができる。

0062

また、請求項4,8記載の発明では、複数のテストパタン生成手段に割り当てられている全ての部分回路との間の重なりの度合いが或る閾値を越えないコーンを集めて部分回路を生成している。ここで、互いに重なりを持つ部分回路が異なるテストパタン手段へ同時に割り当てられると、この重なり部分に含まれる故障のテストパタンがこれらテストパタン生成手段で重複して作成されることになる。そうした場合に、請求項4,8記載の発明では、生成途上にある部分回路と既に処理中の部分回路との重なりができるだけ小さくなるようにしているため、複数のテストパタン生成手段で重複して作成されるテストパタンの数を低減でき、分散処理手法を用いたテストパタン生成処理全体を効率化させることができる。

0063

また、請求項5,9記載の発明では、複数のテストパタン生成手段に割り当ててある全ての部分回路の未検出故障リストを全体回路の未検出故障リストに含ませないようにして、この全体回路の未検出故障リストをもとに、部分回路の未検出故障リストをテストパタン生成手段に渡してテストパタンを生成させている。こうすることで、何れかのテストパタン生成手段で処理されている故障をこれから割り当てようとしているテストパタン生成手段に与えなくて済む。そのため、同一の故障が複数のテストパタン生成手段で同時に処理されるといった事態を回避することができ、分散処理手法を用いたテストパタン生成処理の効率を向上させることが可能となる。また、請求項6,10,11記載の発明は上述した全ての特徴を備えているため、前述した各種の効果が得られることになる。

図面の簡単な説明

0064

図1本発明の第1実施形態によるテストパタン生成装置の詳細な構成を示すブロック図である。
図2同実施形態によるテストパタン生成装置に設けられた外部出力端子リスト作成部41の詳細な構成を示すブロック図である。
図3同実施形態によるテストパタン生成装置の動作を示すフローチャートである。
図4本発明の第2実施形態によるテストパタン生成装置の詳細な構成を示すブロック図である。
図5同実施形態における部分回路作成部44の詳細な構成を示すブロック図である。
図6同実施形態によるテストパタン生成装置の動作を示すフローチャートである。
図7本発明の第3実施形態によるテストパタン生成装置の詳細な構成を示すブロック図である。
図8同実施形態によるテストパタン生成装置の動作を示すフローチャートである。
図9本発明の第1〜第3実施形態を組み合わせたときのテストパタン生成装置の詳細な構成を示すブロック図である。
図10本発明の第1〜第3実施形態を組み合わせたときのテストパタン生成装置の動作を示すフローチャートである。
図11回路分割手法を用いてテストパタン生成を分散処理するテストパタン生成装置の概略構成を示したブロック図である。
図12テストパタンの生成対象となる回路の一部分を例示した回路図である。
図13従来の技術によるテストパタン生成装置の詳細な構成を示すブロック図である。
図14従来の技術によるテストパタン生成装置に設けられた部分回路作成部14の詳細な構成を示すブロック図である。
図15従来の技術によるテストパタン生成装置の動作を示すフローチャートである。
図16テストパタン生成処理中の部分回路と生成中の部分回路への追加候補であるコーンとの重なりの様子を示した説明図である。

--

0065

1-0〜1-n…EWS、1L…ローカルCPU、1R…リモートCPU、5-1〜5-6…論理ゲート、6-1〜6ー4…コーン、7…部分回路、11…回路情報記憶部、12,41…外部出力端子リスト作成部、13,42…外部出力端子リスト記憶部、14,43,44,50…部分回路作成部、15…部分回路記憶部、16…故障情報記憶部、17,47…パタン未作成故障リスト制御部、18…パタン未作成故障リスト記憶部、19…部分回路故障リスト作成部、20…部分回路故障リスト記憶部、21…パタンマージ部、25,46…自動テストパタン作成部、26…テストパタン記憶部、27…パタン作成済故障情報記憶部、28…テストパタン出力部、29…パタン未作成故障リスト出力部、31,53,63…コーン抽出部、32,54…コーン記憶部、33…部分回路ゲート数カウント部、45…パタン未作成故障情報記憶部、51…外部出力端子抽出部、52…コーン処理順序調整部、55…ゲート数カウント部、56…コーンゲート数記憶部、57…処理順序決定部、61…処理中外部入力端子リスト記憶部、62…重複数チェック部、Ti1〜Ti7…入力端子、To1,To2…出力端子

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 東芝エレベータ株式会社の「 BIMシステム、サーバ装置、および方法」が 公開されました。( 2020/12/17)

    【課題】昇降機のBIMモデルに表示不良部が生じるのを抑制する。【解決手段】実施形態のBIMシステムは、第1のBIMパーツに対応する第2のBIMパーツを含み第1のBIMモデルに対応する昇降機の第2のBI... 詳細

  • 学校法人東海大学の「 蓄熱器の設計方法、設計装置及びプログラム」が 公開されました。( 2020/12/17)

    【課題】振動流を利用したエネルギー変換装置が備える蓄熱器の熱効率を最大とする設計支援を行うための設計方法を提供する。【解決手段】エネルギー変換装置の設計方法であって、振動流に関する流体の方程式に基づい... 詳細

  • 三菱電機株式会社の「 設計支援装置および設計支援方法」が 公開されました。( 2020/12/17)

    【課題・解決手段】設計支援装置(1)は、部品表データにおける複数の選定部品を順に適否判定対象部品とし、適否判定対象部品と被部品との部品間関係値を用いて選定部品の適否の判定値を算出する。... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ