(57)【要約】【課題】高位レベルのイベントに関するアサーションを正確かつ簡単に記述できるようにする。【解決手段】本発明の一態様としての検証方法は、複数の各イベントの開始および終了をそれぞれ時系列に記録したトレースの入力を受け付け、前記イベントの発生順序に関する性質または制約を、時相演算子を含む含意により記述したアサーションの入力を受け付け、前記トレースに基づき前記複数のイベントの階層構造を解析し、階層レベル毎に前記イベントの発生順序を表した階層構造トレースを生成し、前記アサーションに含まれる前記含意の前件および後件の少なくとも一方に基づいて各前記階層レベルのうちの１つである選択階層レベルを選択し、前記階層構造トレースに基づき、前記アサーションの真偽を判定し、判定において、前記含意に含まれる前記時相演算子に対する処理を、前記階層構造トレースにおける前記選択階層レベルのトレースに基づいて行う。【選択図】図１
2009277135.tif 000002
【特許請求の範囲】
【請求項１】
複数の各イベントの開始および終了をそれぞれ時系列に記録したトレースの入力を受け付けるトレース入力受付部と、
前記イベントの発生順序に関する性質または制約を、時相演算子を含む含意により記述したアサーションの入力を受け付けるアサーション入力受付部と、
前記トレースに基づき前記複数のイベントの階層構造を解析し、階層レベル毎に前記イベントの発生順序を表した階層構造トレースを生成する階層構造トレース生成部と、
前記アサーションに含まれる前記含意の前件および後件の少なくとも一方に基づいて各前記階層レベルのうちの１つである選択階層レベルを選択する階層レベル選択部と、
前記階層構造トレースに基づき、前記アサーションの真偽を判定する真偽判定部と
を具備し、
前記真偽判定部は、前記含意に含まれる前記時相演算子に対する処理を、前記階層構造トレースにおける前記選択階層レベルのトレースに基づいて行う
ことを特徴とする検証装置。
【請求項２】
前記含意の前件には１つ以上のイベントまたは第２の含意またはこれらの両方が含まれ、
前記階層レベル選択部は、各イベントの階層レベルまたは前記第２の含意について選択された選択階層レベルのうち最も高いものを前記含意の前記選択階層レベルとして選択する
ことを特徴とする請求項１に記載の検証装置。
【請求項３】
前記含意の前件には１つ以上のイベントまたは第２の含意またはこれらの両方が含まれ、
前記階層レベル選択部は、各イベントの階層レベルまたは前記第２の含意について選択された選択階層レベルのうち最も低いものを前記含意の前記選択階層レベルとして選択する
ことを特徴とする請求項１に記載の検証装置。
【請求項４】
前記含意の後件には１つ以上のイベントまたは第３の含意またはこれらの両方が含まれ、
前記階層レベル選択部は、各イベントの階層レベルおよび前記第３の含意について選択された選択階層レベルのうち最も高いものを前記含意の前記選択階層レベルとして選択する
ことを特徴とする請求項１に記載の検証装置。
【請求項５】
前記含意の後件には１つ以上のイベントまたは第３の含意またはこれらの両方が含まれ、
前記階層レベル選択部は、各イベントの階層レベルまたは前記第３の含意について選択された選択階層レベルのうち最も低いものを前記含意の前記選択階層レベルとして選択する
ことを特徴とする請求項１に記載の検証装置。
【請求項６】
前記含意の前件には１つ以上のイベントまたは第２の含意またはこれらの両方が含まれ、
前記含意の後件には１つ以上のイベントまたは第３の含意またはこれらの両方が含まれ、
前記階層レベル選択部は、
前記含意の前件について各イベントの階層レベルまたは前記第２の含意について選択された選択階層レベルのうち最も高いものまたは最も低いものを第１の階層レベルとして選択し、
前記含意の後件について、各イベントの階層レベルおよび前記第３の含意について選択された選択階層レベルのうち最も高いものまたは最も低いものを第２の階層レベルとして選択し、
前記第１の階層レベルおよび前記第２の階層レベルのうち高い方または低い方を前記含意の前記選択階層レベルとして選択する
ことを特徴とする請求項１に記載の検証装置。
【請求項７】
前記アサーションを解析して構文木を生成する構文木生成部をさらに備え、
前記アサーションに含まれず、かつ、前記アサーションに含まれるイベントを兄弟または子のいずれにもたないイベントに関する情報を前記トレースから削除するイベント削除部をさらに備え、
前記階層構造トレース生成部は、削除後の前記トレースを用いる
ことを特徴とする請求項１ないし６のいずれか一項に記載の検証装置。
【請求項８】
複数の各イベントの開始および終了をそれぞれ時系列に記録したトレースの入力を受け付けるトレース入力受付ステップと、
前記イベントの発生順序に関する性質または制約を、時相演算子を含む含意により記述したアサーションの入力を受け付けるアサーション入力受付ステップと、
前記トレースに基づき前記複数のイベントの階層構造を解析し、階層レベル毎に前記イベントの発生順序を表した階層構造トレースを生成する階層構造トレース生成ステップと、
前記アサーションに含まれる前記含意の前件および後件の少なくとも一方に基づいて各前記階層レベルのうちの１つである選択階層レベルを選択する階層レベル選択ステップと、
前記階層構造トレースに基づき、前記アサーションの真偽を判定する真偽判定ステップと
を具備し、
前記真偽判定ステップは、前記含意に含まれる前記時相演算子に対する処理を、前記階層構造トレースにおける前記選択階層レベルのトレースに基づいて行う
ことを特徴とする検証方法。
【請求項９】
コンピュータに実行させるための検証プログラムであって、
複数の各イベントの開始および終了をそれぞれ時系列に記録したトレースの入力を受け付けるトレース入力受付ステップと、
前記イベントの発生順序に関する性質または制約を、時相演算子を含む含意により記述したアサーションの入力を受け付けるアサーション入力受付ステップと、
前記トレースに基づき前記複数のイベントの階層構造を解析し、階層レベル毎に前記イベントの発生順序を表した階層構造トレースを生成する階層構造トレース生成ステップと、
前記アサーションに含まれる前記含意の前件および後件の少なくとも一方に基づいて各前記階層レベルのうちの１つである選択階層レベルを選択する階層レベル選択ステップと、
前記階層構造トレースに基づき、前記アサーションの真偽を判定する真偽判定ステップと
を具備し、
前記真偽判定ステップは、前記含意に含まれる前記時相演算子に対する処理を、前記階層構造トレースにおける前記選択階層レベルのトレースに基づいて行う
ことを特徴とする検証プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検証装置、検証方法および検証プログラムに関し、たとえばデジタル回路を含む電子システムの設計、およびソフトウェアの設計開発に係わる技術に関する。
【背景技術】
【０００２】
従来のデジタル回路を含む電子システムの設計は、VHDL や Verilog HDL などの HDL (Hardware Description Language; ハードウェア記述言語) と呼ばれる低位な設計記述 (信号線やラッチなどハードウェアに近い記述)によって行われていた。
【０００３】
HDL 設計においては、先行技術である 特開2007-11467号公報 や特開 2004-286042号公報のように、PSL (Property Specification Lanugage) や SVA (SystemVerilog Assertion) などのアサーション記述言語によって記述されたアサーションを用いた検証手法が使われている。アサーションは設計記述内で発生するイベントが起きる順序に関する性質や制約を記述したものである。アサーションを用いた検証では、アサーションと設計記述を受け取り、シミュレーションまたは静的解析によって、設計記述がアサーションを満たしているかどうかを検証する。
【０００４】
従来のアサーション記述言語は、イベントが回路内のいずれかのクロックと同期すると仮定していた。すなわち、シングルクロックの回路モジュールにおいては、イベントはすべて同じ時系列上 (フラットな時系列上) で起きることになる。従来は設計記述として HDL を用いていたため、これで十分であった。
【０００５】
しかし、近年のデジタル回路設計では、ESL (Electronic System Level) 設計と呼ばれる、C 言語など高位記述が可能な言語を用いて回路設計を行う手法が使われ始めている。ESLにおいては、通信状態などに相当する高位のイベントレベル、回路に直した場合にクロックに相当する中位のイベントレベル、C 言語の関数呼び出しや変数代入に相当する低位のイベントレベルなど、階層構造をなす複数のレベル（階層レベル）を持つイベントが発生する。
【０００６】
また、アサーション記述言語をソフトウェア開発に適用する場合にも、同様に階層構造をなす複数のレベルを持つイベントを扱う必要があった。
【特許文献１】特開2007-11467号公報
【特許文献２】特開 2004-286042号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
階層構造をなす複数のレベルを持つイベントを従来のアサーション記述言語で扱うためには、複数のレベルのイベントを同じ時系列上に射影して扱う必要があった。しかしこの方法では、高位レベルのイベントの間に多数の低位レベルのイベントが挿入されるため、高位レベルのイベントに関するアサーションの記述が困難かつ不正確になる問題があった。また、低位レベルのイベントが連続時間上で発生するイベントとなっている場合、射影による方法は適用できないという問題があった。
【０００８】
本発明は、高位レベルのイベントに関するアサーションを正確かつ簡単に記述できるようにすることで、検証の精度と効率を向上し、デジタル回路やソフトウェアの品質の向上や開発期間の短縮を図ることを可能とした、検証装置、検証方法および検証プログラムを提供する。
【課題を解決するための手段】
【０００９】
本発明の一態様としての検証装置は、
複数の各イベントの開始および終了をそれぞれ時系列に記録したトレースの入力を受け付けるトレース入力受付部と、
前記イベントの発生順序に関する性質または制約を、時相演算子を含む含意により記述したアサーションの入力を受け付けるアサーション入力受付部と、
前記トレースに基づき前記複数のイベントの階層構造を解析し、階層レベル毎に前記イベントの発生順序を表した階層構造トレースを生成する階層構造トレース生成部と、
前記アサーションに含まれる前記含意の前件および後件の少なくとも一方に基づいて各前記階層レベルのうちの１つである選択階層レベルを選択する階層レベル選択部と、
前記階層構造トレースに基づき、前記アサーションの真偽を判定する真偽判定部と
を具備し、
前記真偽判定部は、前記含意に含まれる前記時相演算子に対する処理を、前記階層構造トレースにおける前記選択階層レベルのトレースに基づいて行う
ことを特徴とする。
【００１０】
本発明の一態様としての検証方法は、
複数の各イベントの開始および終了をそれぞれ時系列に記録したトレースの入力を受け付けるトレース入力受付ステップと、
前記イベントの発生順序に関する性質または制約を、時相演算子を含む含意により記述したアサーションの入力を受け付けるアサーション入力受付ステップと、
前記トレースに基づき前記複数のイベントの階層構造を解析し、階層レベル毎に前記イベントの発生順序を表した階層構造トレースを生成する階層構造トレース生成ステップと、
前記アサーションに含まれる前記含意の前件および後件の少なくとも一方に基づいて各前記階層レベルのうちの１つである選択階層レベルを選択する階層レベル選択ステップと、
前記階層構造トレースに基づき、前記アサーションの真偽を判定する真偽判定ステップと
を具備し、
前記真偽判定ステップは、前記含意に含まれる前記時相演算子に対する処理を、前記階層構造トレースにおける前記選択階層レベルのトレースに基づいて行う
ことを特徴とする。
【００１１】
本発明の一態様としての検証プログラムは、
コンピュータに実行させるための検証プログラムであって、
複数の各イベントの開始および終了をそれぞれ時系列に記録したトレースの入力を受け付けるトレース入力受付ステップと、
前記イベントの発生順序に関する性質または制約を、時相演算子を含む含意により記述したアサーションの入力を受け付けるアサーション入力受付ステップと、
前記トレースに基づき前記複数のイベントの階層構造を解析し、階層レベル毎に前記イベントの発生順序を表した階層構造トレースを生成する階層構造トレース生成ステップと、
前記アサーションに含まれる前記含意の前件および後件の少なくとも一方に基づいて各前記階層レベルのうちの１つである選択階層レベルを選択する階層レベル選択ステップと、
前記階層構造トレースに基づき、前記アサーションの真偽を判定する真偽判定ステップと
を具備し、
前記真偽判定ステップは、前記含意に含まれる前記時相演算子に対する処理を、前記階層構造トレースにおける前記選択階層レベルのトレースに基づいて行う
ことを特徴とする。
【発明の効果】
【００１２】
本発明により、高位レベルのイベントに関するアサーションが正確に、かつ簡単に記述できるようになるため、検証の精度と効率が向上し、デジタル回路やソフトウェアの品質の向上や開発期間の短縮を図れる。
【発明を実施するための最良の形態】
【００１３】
図１は、本発明の一実施の形態としての検証装置の構成を概略的に示すブロック図である。
【００１４】
図１のトレース入力部（トレース入力受付部）１１は、イベントを順序づけして並べたトレースの入力を外部装置から受け付け、入力されたトレースを、本装置での処理に適した形にして出力する。トレースは、複数の各イベントの開始および終了をそれぞれ時系列に記録したものである。
【００１５】
図２は、上記外部装置の一例を示す。この外部装置は、本発明をデジタル回路を含む電子システムの設計に適用する場合に用いられる。この外部装置は、シミュレーションを行う回路の設計記述を入力する設計記述入力部３１と、シミュレーションのテストベンチを入力するテストベンチ入力部３２と、テストベンチに対して設計記述をシミュレーション実行しシミュレーション結果およびトレースを出力するシミュレーション部３３と、シミュレーションの結果を記録するシミュレーション結果記録部３４と、トレースを記録するトレース記録部３５とを持つ。図１のトレース入力部１１は、図２に示すトレース記録部からトレースを読み込む。
【００１６】
図３および図４は、外部装置の他の例を示す。これらの外部装置は、本発明をソフトウェア開発に適用する場合に用いられる。図３に示す外部装置は、ソースコードのコンパイルを行って実行ファイルを生成するコンパイラ部４１と、実行ファイルを実行して実行結果及びトレースを出力する実行部４２と、実行結果を記録する実行結果記録部４３と、トレースを記録するトレース記録部４４と、を持つ。図１のトレース入力部１１は、図３に示すトレース記録部からトレースを読み出す。
【００１７】
図４に示す外部装置は、ソースコードの解釈実行を行い、実行結果及びトレースを出力するインタプリタ部５１と、実行結果を記録する実行結果記録部５２と、トレースを記録するトレース記録部５３を持つ。図１のトレース入力部１１は、図４に示すトレース記録部５３からトレースを読み出す。
【００１８】
図２のシミュレーション部３３が出力したトレース、または図３の実行ファイルの実行により実行部４２が出力したトレースの一例を図８に示す。このトレースは高位レベルのイベントが A 、B 、Cの順に発生し、それぞれのイベントは低位のイベントとして a1 と a2 、b1 と b2 、c1 と c2 を持つ。“begin”はイベントの開始を示し、“end”はイベントの終了を表す。本実施形態ではレベルを自然数で表現する。ここでは、A など高位のイベントのレベルを 1 、a1 など低位のイベントのレベルを 2 とする。
【００１９】
イベントレベルデータベース部１４は、イベントが属するレベル（階層レベルあるいはイベントレベル）の情報を保持するデータベースを管理する。イベントレベルデータベース部１４は、イベントの入力を受け、そのイベントが属するレベル（階層レベル）をデータベースから特定して出力する。データベースの一例を図１０に示す。
【００２０】
本発明をデジタル回路を含む電子システムの設計に適用する場合は、このデータベースは設計記述を静的解析することで構築できる。また、本発明をソフトウェア開発に適用する場合は、このデータベースはソースコードを静的解析することで構築できる。データベースの構築には任意の方法を用いることができ、本発明は、このデータベースを構築する方法の詳細を限定しない。
【００２１】
アサーション入力部（アサーション入力受付部）１５はイベントが起こる順序に関する性質または制約を、時相演算子を含む含意により記述したアサーションの入力を受け、アサーション記述の抽象構文木またはそれに準ずる表現であるアサーション内部表現を生成し出力する。
【００２２】
“含意”とは、計算機論理式等のアサーション記述言語において、「A が真ならば B が真である」という論理を表す式のことである。また、Aに相当する式を“前件”、Bに相当する式を“後件”という。含意は通常 A -> Bのように矢印で表現される。この矢印を“含意記号”という。
【００２３】
アサーションの一例を図９に示す。このアサーションは、A が発生し、次にb1 が発生し、次にb2 が発生した場合は、次に C が発生するという性質を表明している。“NEXT”が“次に”を表す時相演算子に相当する。図９のアサーションに対して生成されるアサーション内部表現を図１１に示す。
【００２４】
イベント取捨選択部１２は、トレース入力部１１が出力したトレースと、アサーション入力部１５が出力したアサーション内部表現を受け取り、トレースから、アサーション内部表現に含まれない不必要なイベントを除去する。不要なイベントとは、自分自身もしくは兄弟イベントもしくは子イベントのいずれもアサーション内部表現において指示されないイベント（すなわちアサーション内部表現に自分自身もしくは兄弟イベントもしくは子イベントのいずれも含まれないイベント）のことである。不要なイベントを削除することによってトレースの量を削減し、検証の高速化を図ることができる。たとえば図８のトレースから、図９のアサーション（図１１のアサーション内部表現）に基づき不要なイベントを削除すると、図１２のトレースが得られる。イベントa1, a2, c1, c2が不要なイベントとして削除されている。なおa1,a2同士、b2,b2同士、およびc1,c2同士は兄弟関係にある。またAと、a1,a2とは親子関係にあり、a1,a2はAの子である。同様に、Bとb1,b2の関係、およびCとc1,c2の関係も、親子関係である。
【００２５】
イベント階層構築部（階層構造トレース生成部）１３は、イベント取捨選択部１２が出力したトレースから、トレースの階層構造を復元・構築する。つまり、トレースに含まれる各イベントが属する階層レベルを特定し、階層レベル別にイベントの順序を表した階層構造トレースを生成する。イベント階層構築部１３の処理の流れを図５のフローチャートに示す。
【００２６】
イベント階層構築部１３は、まずトレースを読み込み（Ｓ１１）、空トレース 1 つを用いて、スタックを初期化し（Ｓ１２）、トレース内のイベントを順次判定する。そのイベントがイベントの開始を表す場合は（Ｓ１３のＹＥＳ）、それをスタック先頭のトレースに追加した上で（Ｓ１４）、それをスタックに詰む（Ｓ１５）。そうでなければ (つまりイベントの終了を表す場合は)（Ｓ１３のＮＯ）、スタックからイベントを 1 つ降ろす（Ｓ１６）。順次判定が終了した後では、スタックには、階層構造トレースが 1 つだけ保持されているので、イベント階層構築部１３は最後にこの階層構造トレースを取り出し（Ｓ１７）、出力する（Ｓ１８）。
【００２７】
上記図５のフローチャートの処理の具体例は後述する。図１２の削除後のトレースに対し本フローチャートの処理を行うと図１４の階層構造トレース（イベント階層構造）が得られる。
【００２８】
含意列挙部１６は、アサーション内部表現を再帰的に探索し、含意に相当する部分式を列挙する。たとえば図９のアサーション（図１１のアサーション内部表現）の場合、３つの部分式、すなわち、b2 -> next C と b1 -> next (b2 -> next C) と A -> next (b1 -> next (b2 -> next C))が列挙される。含意列挙部１６の処理の流れを図６のフローチャートに示す。含意はその前件または後件において小さな含意を持つことがあるため、含意を発見した場合は、最初に前件の含意を列挙し、次に後件の含意を列挙し、最後にこの発見した含意を出力する。これによって、含意列挙部１６はより小さい含意を先に列挙する。
【００２９】
より詳細には、含意列挙部１６は、アサーション内部表現の入力を受け（Ｓ２１）、アサーション内部表現をルートノードから辿り、含意を発見した場合は（Ｓ２２のＹＥＳ）、最初に前件について本フローチャートの再帰処理を行い（ノードを進め）（Ｓ２３）、次に後件について再帰処理を行い（Ｓ２４）、含意を出力し（Ｓ２５）、処理（あるいは再帰処理）を終了する。イベントを発見したときは（Ｓ２６のＹＥＳ）、何も行うことなく、処理（あるいは再帰処理）を終了する。ノードのデータが含意でもイベントでもないときは（Ｓ２６のＮＯ）、再帰処理を行う（Ｓ２７）。上記図６のフローチャートの処理の具体例は後述する。
【００３０】
含意列挙部１６は、列挙した各含意を含意レベル判定部１７および含意レベル注釈部１８に出力する。この後、含意列挙部１６は、含意レベル注釈部１８により各含意にレベル（階層レベル）が注釈されたイベントレベル注釈済みアサーション内部表現（後述する図１５参照）を、含意レベル注釈部１８から取得し、これを真偽判定部１９に出力する。
【００３１】
含意レベル判定部（階層レベル選択部）１７は、含意列挙部１６により列挙された各含意のレベルをそれぞれ判定して含意レベル注釈部１８に出力する。判定の方法としては、
（１）前件のレベルを含意のレベルとする方法
（２）後件のレベルを含意のレベルとする方法
（３）前件のレベルと後件のレベルの高い方を含意のレベルとする方法
（４）前件のレベルと後件のレベルの低い方を含意のレベルとする方法
がある。各方法の詳細については、後述する各実施例において説明する。含意に対して設定されたレベルは、たとえば選択階層レベルに相当する。
【００３２】
含意レベル判定部１７の処理の流れの一例を図７に示す。図７に示す処理は、含意のレベルを、当該含意の前件のレベルに合わせる方法を実行するものである。
【００３３】
まず含意から前件を取り出し（Ｓ３１、Ｓ３２）、前件がイベントである場合は（Ｓ３３のＮＯ、Ｓ３４のＹＥＳ）、イベントレベルデータベース部１４に問い合わせてそのイベントに対応するレベルを取得して（Ｓ３５）、出力する（Ｓ３９）。前件が含意である場合は（Ｓ３３のＹＥＳ）、含意に注釈されているレベルを読み込んで（Ｓ３８）、出力する（Ｓ３９）。前件がイベントでも含意でもない場合は（Ｓ３３のＮＯ、Ｓ３４のＮＯ）、前件を再帰的に探索してレベルを判定する（Ｓ３６）。この再帰によって複数のレベルの候補が得られた場合は、候補を選択して（Ｓ３７）、出力する（Ｓ３９）。Ｓ３７での選択では、（Ａ）最も高いレベルを採用する方法（後述する実施例６）と、（Ｂ）最も低いレベルを採用する方法（後述する実施例７）とがある。図７の処理の具体例については後述する。
【００３４】
含意レベル注釈部１８は、含意列挙部１６の出力した含意と、含意レベル判定部１７の出力したレベルとを読み込み、含意にレベルを注釈し（割り当て）、イベントレベル注釈済みアサーション内部表現を含意列挙部１６に返す。
【００３５】
真偽判定部１９は、イベント階層構築部１３が出力した階層構造トレースと、含意列挙部１６が出力したイベントレベル注釈済みアサーション内部表現とを用いて真偽判定を行う。従来の時相論理式判定では、1レベルのトレースとアサーション内部表現とを受け取り、トレースがアサーションを満たすかどうかの真偽を判定するが、本実施の形態における真偽判定部１９の動作は、含意記号を評価する際に、入力されるトレースを、含意記号に注釈されたレベルのトレースに切り替える。つまり真偽判定部１９は、含意に含まれる時相演算子に対する処理を、含意に注釈された階層レベルのトレースに基づいて行う。真偽判定部１９は、判定の結果（真または偽）を判定結果保持部２０に格納する。真偽判定部１９の処理の具体例は後述する。
【実施例１】
【００３６】
本実施例では、図８のトレースが図９のアサーションを満たしていることを検証する場合の動作を解説する。
【００３７】
イベントレベルデータベース部１４は、図１０に示すイベントとレベルの対応を保持する。例えば、イベントレベルデータベース部１４は、Aの問い合わせを受けた場合、問い合わせ元に 1 を返答する。a1の問い合わせを受けた場合、問い合わせ元に 2 を返答する。
【００３８】
アサーション入力部１５は、図９に示したアサーション（A -> next (b1 -> next (b2 -> next C))）を読み込み、図１１に示すアサーション内部表現を出力する。
【００３９】
イベント取捨選択部１２は、図８に示したトレースと、図１１に示すアサーション内部表現を読み込み、図８のトレースから不要なイベントを除去する。ここでは、a1 、a2 、c1 、c2 を除去し、図１２に示すトレースを出力する。
【００４０】
イベント階層構築部１３は、図１２に示したトレースを読み込み、図１４に示す階層構造トレースを出力する。イベント階層構築部１３の動作を図５のフローチャートに従って詳細に説明する。
【００４１】
最初に図１２に示したトレースを読み込み（Ｓ１１）、スタックを空のトレース 1 つによって初期化し（Ｓ１２）、トレースを順次読み込む。初期状態のスタックを { [] } と表記する。外の {} がスタックを、中の [] がトレースを表す。
【００４２】
まず begin A を読み込む。これは開始イベントであるため（Ｓ１３のＹＥＳ）、スタック先頭のトレースに A を挿入する（Ｓ１４）。これによってスタックが { [A[]] } となる。
【００４３】
次にスタックに A を挿入する（Ｓ１５）。これによってスタックが { [A[]], A[] } となる。
【００４４】
次に end A を読み込む。これは終了イベントであるため（Ｓ１３のＮＯ）、スタックを 1 つ降ろす（Ｓ１６）。これによってスタックが { [A[]] } となる。
【００４５】
これを繰り返すことで、図１３のようにスタックが遷移し、最終的にスタックは { [A[], B[b1[], b2[]], C[]] } となる。以上の手続きによって、イベント階層構築部１３は、図１４に示す階層構造トレースを取得し出力する。
【００４６】
含意列挙部１６は、図１１に示すアサーション内部表現を読み込み、含意を検出し出力する。含意列挙部１６の動作を図６に示すフローチャートに従って説明する。
【００４７】
図１１に示すアサーション内部表現を読み込む（Ｓ２１）。これは全体として含意である（Ｓ２２のＹＥＳ）。
【００４８】
したがってまず前件 Aに対して再帰を行う（Ｓ２３）。A はイベントであるため（Ｓ２２のＮＯ、Ｓ２６のＹＥＳ）、そのまま終了する。
【００４９】
次に後件に対して再帰を行う（Ｓ２４）。next (b1 -> next (b2 -> next C)) は含意でもイベントでもないため（Ｓ２２のＮＯ、Ｓ２６のＮＯ）、さらに再帰を行う（Ｓ２７）。
【００５０】
次の b1 -> next (b2 -> next C) は全体として含意であるため（Ｓ２２のＹＥＳ）、前件 b1に対して再帰を行う（Ｓ２３）。
【００５１】
b1 はイベントであるため（Ｓ２２のＮＯ、Ｓ２６のＹＥＳ）、そのまま終了する。
【００５２】
次に後件に対して再帰を行う（Ｓ２４）。next (b2 -> next C) は含意でもイベントでもないため（Ｓ２２のＮＯ、Ｓ２６のＮＯ）、さらに再帰を行う（Ｓ２７）。
【００５３】
次の b2 -> next C は全体として含意であるため（Ｓ２２のＹＥＳ）、前件 b2に対して再帰を行う（Ｓ２３）。
【００５４】
b2 はイベントであるため（Ｓ２２のＮＯ、Ｓ２６のＹＥＳ）、そのまま終了する。
【００５５】
次に後件に対して再帰を行う。next C は含意でもイベントでもないため（Ｓ２２のＮＯ、Ｓ２６のＮＯ）、さらに再帰を行う（Ｓ２７）。
【００５６】
次の C はイベントであるため（Ｓ２２のＮＯ、Ｓ２６のＹＥＳ）、そのまま終了する。
【００５７】
この後、b2 -> next C を出力し（Ｓ２５）、次に b1 -> next (b2 -> next C) を出力し（Ｓ２５）、さらにA -> next (b1 -> next (b2 -> next C)) を出力する（Ｓ２５）。
【００５８】
各出力された含意は含意レベル判定部１７および含意レベル注釈部１８に送られる。
【００５９】
含意レベル判定部１７は、含意列挙部１６が出力した含意を順次読み込み、含意のレベルを判定する。図７に示すフローチャートに従う場合（すなわち前件のイベントレベルに含意のレベルを合わせる場合）、b2 -> next C と b1 -> next (b2 -> next C) と A -> next (b1 -> next (b2 -> next C)) を入力し、それぞれ 2 、2 、1 を出力する。
【００６０】
b2 -> next Cに対する処理を例に含意レベル判定部１７の動作を示すと、まず b2 -> next C を読み込み（Ｓ３１）、b2 -> next Cの前件である b2 を取り出す（Ｓ３２）。この前件はイベントであるため（Ｓ３３のＮＯ、Ｓ３４のＹＥＳ）、イベントレベルデータベース部１４に b2のレベルを問い合わせる。その結果 2 を得て、含意のレベルとして出力する。他の含意に対しても同様である。
【００６１】
含意レベル注釈部１８は、含意列挙部１６が出力した含意と、含意レベル判定部１７が出力したレベルとを受け取り、含意に注釈を行う。すなわち b2 -> next C と 2 とからb2 ->[2] next C を生成する。次に b1 -> next (b2 ->[2] next C) と 2とから、b1 ->[2] next (b2 ->[2] next C) を生成する。最後に A ->[ next (b1 ->[2] next (b2 ->[2] next C)) と 1とから、A ->[1] next (b1 ->[2] next (b2 ->[2] next C)) を生成する。A ->[1] next (b1 ->[2] next (b2 ->[2] next C))は図１５に示すイベントレベル注釈済みアサーション内部表現に相当する。
【００６２】
真偽判定部１９は、図１４に示す階層構造トレースと、図１５に示すイベントレベル注釈済みアサーション内部表現との入力を受け、トレースがアサーションを満たしているかどうかを判定する。含意記号を評価する際は、入力するトレースを、含意記号に注釈されたレベルのトレースへ切り替える。つまり、含意に含まれる時相演算子に対する処理を、含意記号に注釈されたレベルのトレースに基づいて行う。
【００６３】
より詳細に、A ->[1] next (b1 ->[2] next (b2 ->[2] next C)) を評価する場合は A および next (b1 ->[2] next (b2 ->[2] next C)) をレベル 1に基づいて評価する。図１４に示す階層構造トレースは最初の時点で A が真であるため、次の Bの時点で b1 ->[2] next (b2 ->[2] next C) が成立するかどうか判定する。
【００６４】
b1 ->[2] next (b2 ->[2] next C) を評価する場合は、b1 および next (b2 ->[2] next C) をレベル 2に基づいて評価する。レベル2において、Aの次はb1である。したがってb1 が真であるため b2の時点で b2 ->[2] next C が成立するかどうか判定する。
【００６５】
b2 ->[2] next C を評価する場合は b2 および next C をレベル 2に基づいて評価する。b2 は真であるため、次の時点で C が成立するかどうかを判定する。ここではレベル 2のイベントが終端に到達するため、レベル 1に移動し、次の時点で C が成立するかどうかを判定する。これは成立するため、最終的に図８のトレースは、図９のアサーションを満たしていたことがわかり、真偽判定部１９は真を出力する。
【実施例２】
【００６６】
本実施例２では、図９の代わりに図１６のアサーションを用い、図８のトレースが図１６のアサーションを満たしていないことを検証する場合の動作を解説する。
【００６７】
本実施例２におけるイベントレベルデータベース部１４、イベント取捨選択部１２、イベント階層構築部１３、含意列挙部１６の動作は、実施例１と同じである。
【００６８】
アサーション入力部１５は、図１６に示すアサーションを読み込み、図１７に示すアサーション内部表現を出力する。「C&&D」はCとDが同時に成立することを意味する。
【００６９】
含意レベル判定部１７および含意レベル注釈部１８は実施例１と同様に動作し、図１８に示すイベントレベル注釈済みアサーション内部表現が得られる。
【００７０】
真偽判定部１９は、図１４に示す階層構造トレースと図１８に示すイベントレベル注釈済みアサーション内部表現とを読み込み、トレースがアサーションを満たしているかどうかを判定する。
【００７１】
すなわち、A ->[1] next (b1 ->[2] next (b2 ->[2] next (C && D))) を評価する場合は A および next (b1 ->[2] next (b2 ->[2] next (C && D))) をレベル 1に基づいて評価する。図１４に示す階層構造トレースは最初の時点で A が真であるため、次の Bの時点で b1 ->[2] next (b2 ->[2] next C) が成立するかどうか判定する。
【００７２】
b1 ->[2] next (b2 ->[2] next (C && D)) を評価する場合は、b1 および next (b2 ->[2] next (C && D)) をレベル 2に基づいて評価する。これは b1 および b2のトレースについて判定し、b1 が真であるため b2の時点で b2 ->[2] next (C && D) が成立するかどうか判定する。
【００７３】
b2 ->[2] next (C && D) を評価する場合は b2 および next (C && D) をレベル 2に基づいて評価する。b2 は真であるため、次の時点で (C && D) が成立するかどうかを判定する。ここではレベル 2のイベントが終端に到達するため、レベル 1に移動し、次の時点で (C && D) が成立するかどうかを判定する。これは成立しないため、最終的に図８のトレースは図１６のアサーションを満たしていないことがわかり、真偽判定部１９は偽を出力する。
【実施例３】
【００７４】
本実施例３におけるイベントレベルデータベース部１４、アサーション入力部１５、イベント取捨選択部１２、イベント階層構築部１３、含意列挙部１６の動作は、実施例１と同じである。
【００７５】
本実施例３における含意レベル判定部１７は含意列挙部１６が出力した含意を順次読み込み、含意のレベルとして、後件のレベルを割り当てる。
【００７６】
すなわち b2 -> next C と b1 -> next (b2 -> next C) と A -> next (b1 -> next (b2 -> next C)) の入力を受け、それぞれ 1 、1 、1 を出力する。ここでは b2 -> next Cに対する処理を説明する。
【００７７】
まず b2 -> next C を読み込み、b2 -> next Cの後件である next C を取り出す。この後件は含意でもイベントでもないため再帰を行う。次の C はイベントであるため、イベントレベルデータベース部１４に Cのレベルを問い合わせる。その結果 1 を得て、含意のレベルとして出力する。他の含意に対しても同様である。
【００７８】
含意レベル注釈部１８は、実施例１と同様に動作する。すなわち、b2 -> next C と 1とから、b2 ->[1] next C を生成する。次に b1 -> next (b2 ->[1] next C) と 1 とから、b1 ->[1] next (b2 ->[1] next C) を生成する。最後に A ->[ next (b1 ->[1] next (b2 ->[1] next C)) と 1 とからA ->[1] next (b1 ->[1] next (b2 ->[1] next C)) を生成する。A ->[1] next (b1 ->[1] next (b2 ->[1] next C))を含意列挙部１６に返し、含意例列挙部１６はこれを真偽判定部１９に送る。
【００７９】
真偽判定部１９は、A ->[1] next (b1 ->[1] next (b2 ->[1] next C)) を評価する場合は A および next (b1 ->[1] next (b2 ->[1] next C)) をレベル 1に基づいて評価する。図１４に示す階層構造トレースは最初の時点で A が真であるため、次の Bの時点で b1 ->[1] next (b2 ->[1] next C) が成立するかどうか判定する。
【００８０】
b1 ->[1] next (b2 ->[1] next C) を評価する場合は、b1 および next (b2 ->[1] next C) をレベル 1に基づいて評価する。b1 が真であるため Cの時点で b2 ->[2] next C が成立するかどうか判定する。
【００８１】
b2 ->[2] next C を評価する場合は b2 および next C をレベル 1に基づいて評価する。b2 は偽であるため、この式は真である。したがって、最終的に図８のトレースは図９のアサーションを満たしていたことがわかり、真偽判定部１９は真を出力する。
【実施例４】
【００８２】
本実施例では、含意レベル判定部１７の処理において、含意のレベルとして、前件および後件のレベルのうち、高い方のレベルを割り当てる例を説明する。
【００８３】
本実施例４におけるイベントレベルデータベース部１４、アサーション入力部１５、イベント取捨選択部１２、イベント階層構築部１３、含意列挙部１６、含意レベル注釈部１８、真偽判定部１９の動作は、実施例３と同じである。
【００８４】
含意レベル判定部１７は、含意列挙部１６が出力した含意を順次読み込み、含意のレベルとして、前件および後件のレベルのうち、高い方のレベルを割り当てる。
【００８５】
すなわち b2 -> next C と b1 -> next (b2 -> next C) と A -> next (b1 -> next (b2 -> next C)) を入力し、それぞれ 1 、1 、1 を出力する。ここでは b2 -> next Cに対する処理を説明する。
【００８６】
まず b2 -> next C を読み込み、b2 -> next Cの前件である b2 を取り出す。この前件はイベントであるため、イベントレベルデータベース部１４に b1のレベルを問い合わせる。その結果 2 を得る。次に b2 -> next Cの後件である next C を取り出す。この後件は含意でもイベントでもないため再帰を行う。次の C はイベントであるため、イベントレベルデータベース部１４に Cのレベルを問い合わせる。その結果 1 を得る。得た 2 つのレベルのうち、より高いレベルである 1 を採用して出力する。他の含意に対しても同様である。
【実施例５】
【００８７】
本実施例では、含意レベル判定部１７の処理において、含意のレベルとして、前件および後件のレベルのうち、低い方のレベルを割り当てる例を説明する。
【００８８】
本実施例５におけるイベントレベルデータベース部１４、アサーション入力部１５、イベント取捨選択部１２、イベント階層構築部１３、含意列挙部１６、含意レベル注釈部１８、真偽判定部１９の動作は、実施例１と同じである。
【００８９】
含意レベル判定部１７は含意列挙部１６が出力した含意を順次読み込み、含意のレベルとして、前件および後件のレベルのうち、低い方のレベルを割り当てる。すなわち b2 -> next C と b1 -> next (b2 -> next C) と A -> next (b1 -> next (b2 -> next C)) の入力を受け、それぞれ 1 、2 、2 を出力する。
【００９０】
ここでは b2 -> next Cに対する処理を説明する。
【００９１】
まず b2 -> next C を読み込み、b2 -> next Cの前件である b2 を取り出す。この前件はイベントであるため、イベントレベルデータベース部１４に b1のレベルを問い合わせる。その結果 2 を得る。次に b2 -> next Cの後件である next C を取り出す。この後件は含意でもイベントでもないため再帰を行う。次の C はイベントであるため、イベントレベルデータベース部１４に Cのレベルを問い合わせる。その結果 1 を得る。得た 2 つのレベルうち、より低いレベルである 2 を採用して出力する。他の含意に対しても同様である。
【実施例６】
【００９２】
本実施例６では、図８のトレースと図１９のアサーションを適用した場合の各部の挙動を説明する。
【００９３】
本実施例６におけるイベントレベルデータベース部１４、アサーション入力部１５の動作は、実施例１と同じである。
【００９４】
イベント取捨選択部１２は、実施例１と同様に働き、図２０のトレースを出力する。
【００９５】
イベント階層構築部１３は、実施例１と同様に働き、図２１の階層構造トレースを出力する。
【００９６】
含意列挙部１６は、アサーション内部表現に含まれる含意は１つのみであるため、1 回だけ、含意 A && a1 -> next B を列挙する。
【００９７】
含意レベル判定部１７は含意列挙部１６が出力した含意を読み込み、含意のレベルとして、前件のレベルを割り当てる。ここで、前件のレベルとなる候補が複数存在するときは、最も高いレベルを選択する。以下、図７のフローチャートを参照してこの処理を詳細に説明する。
【００９８】
まず A && a1 -> next B を読み込み（図７のＳ３１）、A && a1 -> next Bの前件である A && a1 を取り出す（Ｓ３２）。この前件は含意でもイベントでないため（Ｓ３３のＮＯ、Ｓ３４のＮＯ）再帰を行う（図７のＳ３６）。次の A はイベントであるため、イベントレベルデータベース部１４に Aのレベルを問い合わせる（Ｓ３５）。その結果 1 を得る。もう一つの a1 はイベントであるため、イベントレベルデータベース部１４にa1のレベルを問い合わせる（Ｓ３５）。この結果 2 を得る。レベルとなる候補が 2 つ得られたため、より高いレベルである1を選択し（Ｓ３７）、出力する。
【００９９】
含意レベル注釈部１８は、A && a1 -> next B と 1 を受け取り、A && a1 ->[1] next B を出力する。
【０１００】
真偽判定部１９は、実施例１と同様に働き、図２１に示す階層構造トレースと A && a1 ->[1] next B の入力を受け、トレースがアサーションを満たしているかどうかを判定する。
【０１０１】
A && a1 ->[1] next B を評価する場合は A && a1 および next B をレベル 1に基づいて評価する。図２１に示す階層構造トレースではこれらはともに成立する。よって図８のトレースは図１９のアサーションを満たし、真偽判定部１９は真を出力する。
【０１０２】
本実施例では前件に複数のレベル候補が存在する場合を説明したが、後件のレベルを用いた、含意レベル判定を行う場合も本実施例と同様にして行うことができる。すなわち、後件に複数のレベル候補が存在するときは、複数の候補のうち最も高いレベルを選択すればよい。
【実施例７】
【０１０３】
本実施例７では、図８のトレースと図１９のアサーションを適用した場合の各部の挙動を説明する。
【０１０４】
本実施例７におけるイベントレベルデータベース部１４、アサーション入力部１５、イベント取捨選択部１２、イベント階層構築部１３、含意列挙部１６の動作は、実施例６と同じである。
【０１０５】
含意レベル判定部１７は、含意列挙部１６が出力した含意を順次読み込み、含意のレベルとして、前件のレベルを割り当てる。ここで、前件のレベルとなる候補が複数存在するときは、最も低いレベルを選択する。以下、図７のフローチャートを参照してこの処理を詳細に説明する。
【０１０６】
まず A && a1 -> next B を読み込み（Ｓ３１）、A && a1 -> next Bの前件である A && a1 を取り出す（Ｓ３２）。この前件は含意でもイベントでないため（Ｓ３３のＮＯ、Ｓ３４のＮＯ）再帰を行う（図７のＳ３６）。次の A はイベントであるため、イベントレベルデータベース部１４に Aのレベルを問い合わせる（Ｓ３５）。その結果 1 を得る。もう一つの a1 はイベントであるため、イベントレベルデータベース部１４に a1のレベルを問い合わせる（Ｓ３５）。この結果 2 を得る。レベルとなる候補が 2 つ得られたため、より低いレベルである２を採用して出力する。
【０１０７】
含意レベル注釈部１８は、A && a1 -> next B と 2 を受け取り、A && a1 ->[2] next B を出力する。
【０１０８】
真偽判定部１９は、実施例１ と同様に働き、図２１に示す階層構造トレースと A && a1 ->[2] next B の入力を受け、トレースがアサーションを満たしているかどうかを判定する。
【０１０９】
A && a1 ->[2] next B を評価する場合は A && a1 および next B をレベル 2に基づいて評価する。すなわち、a1 と a2 からなるトレースについてこれを評価する。A && a1 は真であるが、a1の次は a2 であり B は成り立たないため、next B は偽となる。最終的に図８のトレースは図１９のアサーションを満たしていないことがわかり、真偽判定部１９は偽を出力する。
【０１１０】
本実施例では前件に複数のレベル候補が存在する場合を説明したが、後件のレベルを用いた、含意レベル判定を行う場合も本実施例と同様にして行うことができる。すなわち、後件に複数のレベル候補が存在するときは、複数の候補のうち最も低いレベルを選択すればよい。
【０１１１】
これまで述べた本発明の実施例１〜７の説明では、アサーションは１つのみであったが、本発明は、同時に複数のアサーションを扱う場合にも当然に拡張可能である。この場合は、含意列挙部１６、含意レベル判定部１７、含意レベル注釈部１８をアサーション毎に適用すればよい。
【０１１２】
またこれまで述べた本発明の実施例１〜７の説明では、時相演算子としてNEXTを用いた例を示したが、本発明はこれに限定されず、たとえばALWAYS, EVENTUALLY, UNTIL、など他の種類の時相演算子を用いることも当然に可能である。たとえば「A->ALWAYS B」はAが成立したらその後は常にBが成り立つことを意味し、「A->EVENTUALLY B」はAが成立したらその後は必ずいつかBが成り立つことを意味し、「A-> C UNTIL B」は、Aが成立したらその後は、Bが成立するまでCが常に成り立つことを意味する。
【０１１３】
以上のように、本発明の実施の形態によれば、アサーション記述言語における含意記号にイベントのレベル（階層レベル）を割り当てることによって、高位レベルのイベントに関するアサーションが正確に、かつ簡単に記述できるようになるため、検証の精度と効率が向上し、デジタル回路やソフトウェアの品質の向上や開発期間の短縮を図れる。
【０１１４】
なお、以上に説明した本実施形態における検証装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることでも実現することが可能である。すなわち、検証装置におけるトレース入力部、イベント取捨選択部、イベント階層構築部、アサーション入力部、含意列挙部、含意レベル判定部、含意レベル注釈部、真偽判定部は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、検証装置は、上記のプログラムをコンピュータ装置にあらかじめインストールすることで実現してもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。
【図面の簡単な説明】
【０１１５】
【図１】本発明の一実施の形態としての検証装置の構成を概略的に示すブロック図である。
【図２】トレースを生成する外部装置の一例を示す図。
【図３】トレースを生成する外部装置の他の例を示す図。
【図４】トレースを生成する外部装置のさらに他の例を示す図。
【図５】イベント階層構築部の処理の流れを示すフローチャート。
【図６】含意列挙部の処理の流れを示すフローチャート。
【図７】含意レベル判定部の処理の流れの一例を示すフローチャート。
【図８】トレースの一例を示す図。
【図９】アサーションの一例を示す図。
【図１０】イベントレベルデータベース部の内容の一例を示す図。
【図１１】図９のアサーションの内部表現を示す図。
【図１２】削除後トレースの例を示す図。
【図１３】イベント階層構築部の処理を説明する図。
【図１４】階層構造トレースの一例を示す図。
【図１５】イベントレベル注釈済みアサーション内部表現の一例を示す図。
【図１６】アサーションの他の例を示す図。
【図１７】図１６のアサーションの内部表現を示す図。
【図１８】イベントレベル注釈済みアサーション内部表現の他の例を示す図。
【図１９】アサーションのさらに他の例を示す図。
【図２０】削除後トレースの他の例を示す図。
【図２１】階層構造トレースの他の例を示す図。
【符号の説明】
【０１１６】
１１：トレース入力部（トレース入力受付部）
１２：イベント取捨選択部
１３：イベント階層構築部
１４：イベントレベルデータベース部
１５：アサーション入力部（アサーション入力受付部）
１６：含意列挙部
１７：含意レベル判定部（階層レベル選択部）
１８：含意レベル注釈部
１９：真偽判定部
２０：判定結果保持部
【図１】
2009277135.tif 000003
【図２】
2009277135.tif 000004
【図３】
2009277135.tif 000005
【図４】
2009277135.tif 000006
【図５】
2009277135.tif 000007
【図６】
2009277135.tif 000008
【図７】
2009277135.tif 000009
【図８】
2009277135.tif 000010
【図９】
2009277135.tif 000011
【図１０】
2009277135.tif 000012
【図１１】
2009277135.tif 000013
【図１２】
2009277135.tif 000014
【図１３】
2009277135.tif 000015
【図１４】
2009277135.tif 000016
【図１５】
2009277135.tif 000017
【図１６】
2009277135.tif 000018
【図１７】
2009277135.tif 000019
【図１８】
2009277135.tif 000020
【図１９】
2009277135.tif 000021
【図２０】
2009277135.tif 000022
【図２１】
2009277135.tif 000023