(57)【要約】【課題】模擬実行の速度を高速化する。【解決手段】本発明の一態様としての模擬実行装置は、周期的な信号を受信する受信部と、複数のレジスタと、前記周期的な信号と前記複数のレジスタとを用いて動作する論理回路モデルを模擬実行する模擬実行部と、前記周期的な信号に基づいて時刻をカウントするカウンタと、前記複数のレジスタの値を監視するレジスタ値監視部と、前記複数のレジスタのうち少なくとも１つの値が変更されたとき、前記複数のレジスタの値からなるデータ列を前記時刻と関連づけて記録するレジスタ値記録部と、前記レジスタ値記録部を参照してデータ列の周期性を検出する周期性検出部と、前記模擬実行の停止を指示する停止指示信号を前記模擬実行部に与える停止部と、を備える。【選択図】図１
2008181227.tif 000002
【特許請求の範囲】
【請求項１】
周期的な信号を受信する受信部と、
複数のレジスタと、
前記周期的な信号と前記複数のレジスタとを用いて動作する論理回路モデルを模擬実行する模擬実行部と、
前記周期的な信号に基づいて時刻をカウントするカウンタと、
前記複数のレジスタの値を監視するレジスタ値監視部と、
前記複数のレジスタのうち少なくとも１つの値が変更されたとき、前記複数のレジスタの値からなるデータ列を前記時刻と関連づけて記録するレジスタ値記録部と、
前記レジスタ値記録部を参照してデータ列の周期性を検出する周期性検出部と、
前記模擬実行の停止を指示する停止指示信号を前記模擬実行部に与える停止部と、
を備えた模擬実行装置。
【請求項２】
前記周期性検出部は、同じ値をもつデータ列が２つ以上存在し、かつ２つのデータ列の時刻の差が、前記周期的な信号の周期の倍数であるとき、データ列の周期性を検出することを特徴とする請求項１に記載の模擬実行装置。
【請求項３】
前記受信部は、各々周期が異なる２つ以上の周期的な信号を受信し、
前記周期性検出部は、前記２つのデータ列の時刻の差が、各周期的な信号の倍数に該当するとき、データ列の周期性を検出することを特徴とする請求項２に記載の模擬実行装置。
【請求項４】
前記周期性検出部は、時間的に最も近い同一の値からなる２つのデータ列の時刻の差をデータ列の周期として得ることを特徴とする請求項２または３に記載の模擬実行装置。
【請求項５】
ある時刻におけるレジスタの値を要求する要求信号を受信する要求信号受信部と、
前記レジスタ値記録部における１周期分の各データ列のうち、前記ある時刻に対応するデータ列から前記レジスタの値を取得するレジスタ値取得部と、
前記レジスタ値取得部により取得されたレジスタの値を出力する出力部と、
をさらに備えたことを特徴とする請求項１ないし４のいずれか一項に記載の模擬実行装置。
【請求項６】
前記論理回路モデルの記述に基づき、他のレジスタから値を決定可能な第１レジスタを検出するレジスタ検出部をさらに備え、
前記レジスタ値記録部は、前記複数のレジスタのうち前記第１レジスタと異なるレジスタの値からなるデータ列を記録する、
ことを特徴とする請求項１ないし４のいずれか一項に記載の模擬実行装置。
【請求項７】
ある時刻における前記第１レジスタの値を要求する要求信号を受信する要求信号受信部と、
前記レジスタ値記録部における１周期分の各データ列のうち、前記ある時刻に対応するデータ列に含まれる前記他のレジスタの値を用いて前記第１レジスタの値を計算するレジスタ値計算部と、
前記レジスタ値計算部により計算された前記第１レジスタの値を出力する出力部と、
をさらに備えたことを特徴とする請求項６に記載の模擬実行装置。
【請求項８】
前記模擬実行が停止されている間、前記複数のレジスタのうち外部へ出力する値を格納する出力レジスタを、前記レジスタ値記録部における１周期分の前記出力レジスタの値と、前記周期的な信号または前記カウンタとに基づいて更新するレジスタ更新部をさらに備えることを特徴とする請求項１ないし７のいずれか一項に記載の模擬実行装置。
【請求項９】
前記レジスタ値記録部内のデータ列によって前記複数のレジスタを回復するレジスタ回復部と、
不規則な割込信号の入力を検出する入力検出部と、をさらに備え、
前記複数のレジスタは、前記不規則な割込信号の入力に応じた割込値を格納するための割込レジスタを含み、
前記レジスタ回復部は、前記レジスタ値記録部における１周期分の各データ列のうち、前記不規則な割込信号の入力時刻に対応するデータ列によって、前記割込レジスタを除く前記複数のレジスタを更新し、また、前記割込値を前記割込レジスタに格納し、
前記停止部は、前記模擬実行の停止を解除する停止解除信号を前記模擬実行部に与える、
ことを特徴とする請求項１ないし８のいずれか一項に記載の模擬実行装置。
【請求項１０】
前記レジスタ回復部は、前記模擬実行部が模擬実行を行っているときに前記不規則な割込信号が入力されたら、前記レジスタ値記録部をクリアし、前記割込値を前記割込レジスタに格納することを特徴とする請求項８に記載の模擬実行装置。
【請求項１１】
前記論理回路モデルを解析し、第２レジスタから第１レジスタへの代入がある場合、第２レジスタを表すノードから第１レジスタを表すノードへ方向付きのアークを追加し、また、前記代入のタイミングが第３レジスタの値により決定される場合は、第３レジスタを表すノードから前記第１レジスタを表すノードへの方向付きアークを追加することにより、レジスタ間依存グラフを生成するグラフ生成部をさらに備え、
前記周期性検出部は、前記レジスタ間依存グラフにおける強連結成分ごとに周期性の検出を行い、
前記停止部は、前記模擬実行のうち前記周期性の検出された強連結成分に含まれるレジスタを扱う処理の停止を指示する指示信号を前記模擬実行部に与える、
ことを特徴とする請求項１に記載の模擬実行装置。
【請求項１２】
周期的な信号を受信し、
前記周期的な信号と複数のレジスタとを用いて動作する論理回路モデルを模擬実行し、
前記周期的な信号に基づいて時刻をカウントし、
前記複数のレジスタの値を監視し、
前記複数のレジスタのうち少なくとも１つの値が変更されたとき、前記複数のレジスタの値からなるデータ列を前記時刻と関連づけてレジスタ値記録部に記録し、
前記レジスタ値記録部を参照してデータ列の周期性を検出し、
前記模擬実行を停止する、
模擬実行方法。
【請求項１３】
前記レジスタ値記録部において同じ値をもつデータ列が２つ以上存在し、かつ２つのデータ列の時刻の差が、前記周期的な信号の周期の倍数であるとき、データ列の周期性を検出することを特徴とする請求項１２に記載の模擬実行方法。
【請求項１４】
時間的に最も近い同一の値からなる２つのデータ列の時刻の差をデータ列の周期として得ることを特徴とする請求項１３に記載の模擬実行方法。
【請求項１５】
さらに、
ある時刻におけるレジスタの値を要求する要求信号を受信し、
前記レジスタ値記録部における１周期分の各データ列のうち、前記ある時刻に対応するデータ列から前記レジスタの値を取得し、
取得されたレジスタの値を出力する、
ことを特徴とする請求項１２ないし１４のいずれか一項に記載の模擬実行方法。
【請求項１６】
さらに、前記論理回路モデルの記述に基づき、他のレジスタから値を決定可能な第１レジスタを検出し、
前記複数のレジスタのうち前記第１レジスタと異なるレジスタの値からなるデータ列を記録する、
ことを特徴とする請求項１２ないし１４のいずれか一項に記載の模擬実行方法。
【請求項１７】
ある時刻における第１レジスタの値を要求する要求信号を受信し、
前記レジスタ値記録部における１周期分の各データ列のうち、前記ある時刻に対応するデータ列に含まれる前記他のレジスタの値を用いて前記第１レジスタの値を計算し、
計算された前記第１レジスタの値を出力する、
ことを特徴とする請求項１６に記載の模擬実行方法。
【請求項１８】
さらに、前記模擬実行が停止されている間、前記複数のレジスタのうち外部へ出力する値を格納する出力レジスタを、前記レジスタ値記録部における１周期分の前記出力レジスタの値と、前記周期的な信号または前記カウンタとに基づいて更新する、
ことを特徴とする請求項１２ないし１７のいずれか一項に記載の模擬実行方法。
【請求項１９】
さらに
不規則な割込信号の入力を検出し、
前記レジスタ値記録部における１周期分の各データ列のうち前記不規則な割込信号の入力時刻に対応するデータ列によって、前記複数のレジスタのうち前記不規則な割込信号の入力に応じた割込値を格納するための割込レジスタ以外のレジスタを回復し、また、前記割込値を前記割込レジスタに格納し、
前記模擬実行の停止を解除する、
ことを特徴とする請求項１２ないし１８のいずれか一項に記載の模擬実行方法。
【請求項２０】
さらに、前記論理回路モデルを解析して、第２レジスタから第１レジスタへの代入がある場合、第２レジスタを表すノードから第１レジスタを表すノードへ方向付きのアークを追加し、また、前記代入のタイミングが第３レジスタの値により決定される場合は、第３レジスタを表すノードから前記第１レジスタを表すノードへの方向付きアークを追加することにより、レジスタ間依存グラフを生成し、
前記レジスタ間依存グラフにおける強連結成分ごとに周期性の検出を行い、
前記模擬実行のうち前記周期性の検出された強連結成分に含まれるレジスタを扱う処理を停止する、
ことを特徴とする請求項１２に記載の模擬実行方法。
【請求項２１】
周期的な信号を受信するステップと、
前記周期的な信号と複数のレジスタとを用いて動作する論理回路モデルを模擬実行するステップと、
前記周期的な信号に基づいて時刻をカウントするステップと、
前記複数のレジスタの値を監視するステップと、
前記複数のレジスタのうち少なくとも１つの値が変更されたとき、前記複数のレジスタの値からなるデータ列を前記時刻と関連づけてレジスタ値記録部に記録するステップと、
前記レジスタ値記録部を参照してデータ列の周期性を検出するステップと、
前記模擬実行を停止するステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハードウェア記述言語等で表現された論理回路モデルの模擬実行を行う模擬実行装置、方法およびプログラムに関する。
【背景技術】
【０００２】
近年、LSI（Large-Scale Integration）等の大規模な論理回路の設計・製造では、ハードウェア記述言語(Hardware Description Language: HDL) と呼ばれる言語でハードウェアを記述し、記述したHDL から実際のLSI 等のハードウェアを製造することが多い。  
一方、近年、携帯電話などの組込み機器においては、ソフトウェアの大規模化と開発サイクルの短縮化とが同時進行しており、開発やテストの速度が追いつかなくなりつつある。このため、ハードウェア製造前に論理検証や評価を効率的におこなうことが可能な、HDL の模擬実行の重要性は増している。
【０００３】
HDL としては、たとえば、Verilog-HDL 、VHDL、などがよく利用される。このHDL を模擬実行するために、等価なコード(たとえばCコード)を、人間が手作業で作成する場合がある。人間は、仕様書やHDL の意図を理解できるため、模擬実行向けの高速なコードを作成できる場合がある。
【０００４】
一方、模擬実行を自動的におこなうツールとして、たとえばVerilog-HDL に対して、iverilog 、verilator、NC-verilog, などのツールが知られている。これらの模擬実行ツールは、基本的には、HDL に表現された回路動作を時間軸に沿って忠実に実行する。ただし一般に論理回路は、並列性と小記憶領域とを前堤として設計・記述されるため、PC（Personal Computer） などのように演算部の並列度が低く記憶領域の大きな環境で忠実な模擬実行をおこなう場合、冗長で無駄な処理となり易い。
【０００５】
そこで、模擬実行速度を上げるために様々な工夫がされている。たとえば特開２００５−３２１８４８公報（特許文献１）では、模擬実行前にHDL の静的解析をおこない、無駄な記述を削除する高速化手法が開示されている。また、上述のverilator では、HDL を一旦等価なCコードに変換することにより、コンパイラによる最適化を活用することが可能である。また半自動の手法として、上述のNC-verilog に見られるような、模擬実行時間のボトルネック部分を自動識別し、人間がボトルネック部分を編集することで実行速度を上げる手法も知られている。 
【特許文献１】特開２００５−３２１８４８公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
HDL で記述された論理回路を模擬実行する場合、模擬実行の動作の正確さ、作成の手間、実行速度の3個の観点が共に重要となる。
【０００７】
上述した人間が実行コードを手動で作成する場合や、半自動で作成する場合は、作業者が十分熟練している場合は、高速な実行コードを作成することが可能である。しかし、作成の手間がかかり、また、人間の手を経るために動作が不正確となる可能性がある。
【０００８】
一方、模擬実行コードを自動的に作成する場合は、模擬実行の正確さは保証され、作成の手間が少ない場合が多いが、実行速度を上げることは難しい。
【０００９】
実行速度を上げることが困難な原因の一つとして、iverilog やverilator などの既存手法では、実際の回路動作に忠実に模擬実行し、繰り返し動作も忠実に実行するため、無駄な実行時間を消費していることが挙げられる。
【００１０】
一方、上述の特開２００５−３２１８４８では、静的解析により、回路動作の周期性を検出する手法について述べられているが、周期するパターンを予め登録しておく必要があり、手間がかかる。
【００１１】
以上より依然として、模擬実行を高速におこなう手法には改良の余地がある。
【００１２】
本発明は、模擬実行を誤りなく高速に実行可能な模擬実行装置、方法およびプログラムを提供する。
【課題を解決するための手段】
【００１３】
本発明の一態様としての模擬実行装置は、
周期的な信号を受信する受信部と、
複数のレジスタと、
前記周期的な信号と前記複数のレジスタとを用いて動作する論理回路モデルを模擬実行する模擬実行部と、
前記周期的な信号に基づいて時刻をカウントするカウンタと、
前記複数のレジスタの値を監視するレジスタ値監視部と、
前記複数のレジスタのうち少なくとも１つの値が変更されたとき、前記複数のレジスタの値からなるデータ列を前記時刻と関連づけて記録するレジスタ値記録部と、
前記レジスタ値記録部を参照してデータ列の周期性を検出する周期性検出部と、
前記模擬実行の停止を指示する停止指示信号を前記模擬実行部に与える停止部と、
を備える。
【００１４】
本発明の一態様としての模擬実行方法は、
周期的な信号を受信し、
前記周期的な信号と複数のレジスタとを用いて動作する論理回路モデルを模擬実行し、
前記周期的な信号に基づいて時刻をカウントし、
前記複数のレジスタの値を監視し、
前記複数のレジスタのうち少なくとも１つの値が変更されたとき、前記複数のレジスタの値からなるデータ列を前記時刻と関連づけてレジスタ値記録部に記録し、
前記レジスタ値記録部を参照してデータ列の周期性を検出し、
前記模擬実行を停止する。
【００１５】
本発明の一態様としてのプログラムは、
周期的な信号を受信するステップと、
前記周期的な信号と複数のレジスタとを用いて動作する論理回路モデルを模擬実行するステップと、
前記周期的な信号に基づいて時刻をカウントするステップと、
前記複数のレジスタの値を監視するステップと、
前記複数のレジスタのうち少なくとも１つの値が変更されたとき、前記複数のレジスタの値からなるデータ列を前記時刻と関連づけてレジスタ値記録部に記録するステップと、
前記レジスタ値記録部を参照してデータ列の周期性を検出するステップと、
前記模擬実行を停止するステップと、
をコンピュータに実行させる。
【発明の効果】
【００１６】
本発明により、模擬実行を誤り無く高速に実行できる。
【発明を実施するための最良の形態】
【００１７】
（第１実施形態）
図１は、本発明の第１実施形態としての模擬実行用回路モデル（模擬実行装置）6000の構成を示すブロック図である。
【００１８】
この模擬実行用回路モデル6000は、忠実模擬実行機構2800と、レジスタ値テーブル4600と、レジスタ値監視機構2300と、過去データ記憶テーブル4700と、周期性検出機構2500と、回路切替機構2700と、レジスタ値回復機構2400とを備える。
【００１９】
図１の各機構は、たとえば各々に対応する記述を、レジスタ値監視機構記述1300, レジスタ値回復機構記述1400, 周期性検出機構記述1500、回路切換機構記述1700, 忠実模擬実行機構記述1800として用意し（図２参照）、これらを実行することにより実現される。レジスタ値監視機構記述1300, レジスタ値回復機構記述1400, 周期性検出機構記述1500、回路切換機構記述1700, 忠実模擬実行機構記述1800は、模擬実行対象となる論理回路記述1100（図３参照）を解析することにより自動生成してもよいし、あらかじめユーザが論理回路記述1100に基づき作成してもよい。
【００２０】
自動生成する場合、図２に示すように、あらかじめ用意する模擬実行用回路モデル作成装置（図示せず）の模擬実行用回路モデル作成部1000に、論理回路記述1100を与え、レジスタ値監視機構2300, レジスタ値回復機構2400, 周期性検出機構2500, 回路切換機構2700, 忠実模擬実行機構2800 を実現するようなレジスタ値監視機構記述1300, レジスタ値回復機構記述1400, 周期性検出機構記述1500, 回路切換機構記述1700, 忠実模擬実行機構記述1800を自動作成する。
【００２１】
模擬実行用回路モデル作成部1000において生成されたレジスタ値監視機構記述1300, レジスタ値回復機構記述1400, 周期性検出機構記述1500, 回路切換機構記述1700, 忠実模擬実行機構記述1800は、模擬実行時にはそれぞれ、レジスタ値監視機構2300, レジスタ値回復機構2400, 周期性検出機構2500、回路切換機構2700, 忠実模擬実行機構2800として動作することとなる。忠実模擬実行機構2800は、上記論理回路記述1100を時系列に沿って忠実に実行する機能を有する。忠実模擬実行機構2800は、たとえば、iverilog, verilator, NC-verilog などの既存ツールと同等な手法により実現できる。
【００２２】
図３は、タイマ回路の論理回路記述1100の一例を示す。図３（Ａ）は分周器（module Divider）の回路記述に相当し、図３（Ｂ）はカウンタ（module Counter）の回路記述に相当する。これらの両方の回路記述によってタイマ回路の回路記述が構成される。なお、論理回路記述1100に関しては、verilog HDL 以外のHDLによって記述 されても構わない。また、HDL と同等の情報を有する別のグラフデータにより記述されてもよい。
【００２３】
図３（Ａ）および図３（Ｂ）に示すように、タイマ回路では、クロック信号(clk) を入力とするDivider モジュールがクロック信号の分周を行い、Counter モジュールが分周クロックを元に、一定周期の割り込み信号(output) を出力する。また、RESET 信号が0から1に変化した場合は、カウンタ(cnt およびdivide_cnt) の値が0にクリアされる。
【００２４】
図３（Ａ）および図３（Ｂ）の回路記述において、RESET, cnt, cnt_next, divide_clk, divide_cnt, divide_cnt_next, output は回路の記憶領域に相当し、これらの回路の記憶領域を「レジスタ」と称する。各レジスタの値が時間と共に変化の様子を、後に詳述する図１０に示す。
【００２５】
ここでDividerモジュールにおいて、“reg[1:0] cnt”は２ビット分のレジスタcntを確保したことを意味し、たとえばcnt[1]は上位ビット、cnt[0]は下位ビットを示す。“posedge_clk”はクロックが立ち上がったとき（たとえば値が０から１に変化したとき）を意味し、“posedge_RESET”はRESET信号が立ち上がったときを意味する。“assign”は右辺の値が変わったら左辺に代入することを意味する。たとえば“assign divide_clk=cnt[1]”は、レジスタcntが２（10）または３(11)になったら、上位ビットの１をdivide_clkに代入し、レジスタcntが０（00）または１(01)になったら、上位ビットの０をdivide_clkに代入することを意味する。
【００２６】
各レジスタは、回路への入力信号を保持するレジスタ、回路からの出力信号を保持するレジスタおよびそれ以外の信号を保持するレジスタのいずれかに該当する。タイマ回路では、RESET のレジスタが回路への入力信号を保持するレジスタであり、output が回路からの出力信号を保持するレジスタである、cnt, cnt_next, divide_clk, divide_cnt, divide_cnt_nextが、入力信号および出力信号以外の信号を保持するレジスタである。
【００２７】
さらに、回路への入力信号に関しては、周期的な入力信号とイレギュラー（不規則）な入力信号とに区別される。たとえば図３（Ａ）および図３（Ｂ）の論理回路記述1100では、Divider モジュールに入力されるclk は、1、0、1、0 という周期動作を繰り返すため周期的な入力信号に分類される。一方、RESET は、ユーザの設定などにより、突発的に変化するので、イレギュラーな入力信号に分類される。
【００２８】
忠実模擬実行機構2800は、論理回路記述1100に基づいた模擬実行を時系列に沿って忠実に実行しつつ、レジスタ値テーブル4600 に各レジスタの値を保持および更新する。すなわちレジスタ値テーブル4600は、模擬実行中の最新のレジスタ値が保持されている。つまり、模擬実行中において扱うレジスタの値はレジスタ値テーブル4600に格納されている。
【００２９】
レジスタ値監視機構2300 は、周期的な入力信号4100 が変化するごとに（図３の例ではclk が立ち上がるタイミングごとに）、レジスタ値テーブル4600に記録された各レジスタの値を監視し、少なくとも１つのレジスタの値に変更があったら、全てのレジスタ値を現在時刻とともに過去データ記憶テーブル4700 に記録する。現在時刻を記録するため、レジスタ値監視機構2300は周期的な入力信号4100に基づき時刻をカウントするカウンタを有している。周期的な入力信号4100は、たとえば別途用意したクロックジェネレータの論理回路記述を図１の模擬実行用回路モデル6000の外側で模擬実行することにより生成できる。周期的な入力信号4100は、図１の模擬実行用回路モデル6000（特にレジスタ値監視機構2300および忠実模擬実行機構2800）に入力される。クロックジェネレータの論理回路記述の一例を図４に示しておく。図４は、HDL の1つであるverilog-HDL 風に記述したクロックジェネレータ回路(module clk_generator )の回路記述を示す。クロックジェネレータは、2(時刻単位)周期で立ち上がるクロック信号を発生する。“〜”は１と０とを反転させることを意味し、“＃１”は時間を１つ進めることを意味する。
【００３０】
忠実模擬実行機構2800による論理回路記述1100の模擬実行に伴い、過去データ記憶テーブル4700に各レジスタの値が時間と共に記憶されていく様子を図１０に示す。２時刻ごとに少なくとも１つのレジスタの値が変更されるため、２時刻ごとに各レジスタの値が記録されている。なお、予め監視するべきレジスタを限定できる場合は、レジスタ値テーブル4600において、限定したレジスタの監視のみを行う。これについては第４実施形態で説明する。
【００３１】
周期性検出機構2500 は、現在におけるレジスタ値テーブル4600 の各レジスタの値（データ列）が、過去データ記憶テーブル4700内の過去の各レジスタの値（データ列）と一致し、かつ一致するまでの時間が、周期的な入力信号4100 の周期の倍数であるかどうか（周期性検出条件）を調べる。すなわち、各レジスタの値からなるデータ列に周期があるかどうかを調べる。
【００３２】
上記周期性検出条件を満たす場合は、現在時刻から、レジスタ値テーブル4600の各レジスタ値と一致する過去の各レジスタ値の時刻までの回路の動作を周期動作である（データ列に周期性がある）と判定する。その場合、回路切換機構2700 に対し、周期検出シグナル4800 を発し、レジスタ値テーブル4600の各レジスタ値と一致する過去の各レジスタ値の時刻を周期開始時刻Tsとして、現在時刻を周期終了時刻Tgとして、過去データ記憶テーブル4700 に記憶する。C= Tg − Tsは周期に相当する。図１０の例の場合、時刻０の各レジスタの値（時刻０のデータ列）と、時刻３２の各レジスタの値（時刻３２のデータ列）とが同じであり、かつ３２−０＝３２が、入力信号の周期である２の倍数であるため、周期が３２として検出され、時刻Tsは０、時刻Tgは３２となる。
【００３３】
周期的な入力信号4100 が複数ある場合は、現在時刻との差が、全ての周期的な入力信号4100 の周期の倍数になる限り、回路に周期動作が存在する（周期性有り）と判定する。現在時刻との差が、全ての周期的な入力信号4100 の周期の倍数になる場合、次にイレギュラーな入力信号（たとえばRESET）が入力される時刻までの回路動作が、周期動作となることは、数学的に保証される。
【００３４】
回路切換機構2700 は、周期性検出機構2500から周期検出シグナル4800 を受けとったとき、動作中の忠実模擬実行機構2800 に対し、回路停止シグナル5000 を発行する。回路停止シグナル5000を受け取った忠実模擬実行機構2800は、タイマ回路の動作を停止させる。すなわち、図３のタイマ回路の回路記述の模擬実行を停止する。
【００３５】
レジスタ値回復機構2400 は、模擬実行の停止中に、時刻tのレジスタ値の要求4300 を受けとったら、過去データ記憶テーブル4700を参照し、時刻ｔに対応する、上記周期内の位置を特定し、特定した位置に対応する各レジスタの値（データ列）を取得して、時刻tのレジスタ値4400として出力する。レジスタ値回復機構2400はたとえば要求信号受信部、レジスタ値取得部および出力部を含む。なお模擬実行中に、時刻ｔのレジスタ値の要求4300があったときは、レジスタ値テーブル4600の値をそのまま出力すればよい。
【００３６】
図５は、図１の模擬実行用回路モデル6000の動作を説明するフローチャートである。
【００３７】
忠実模擬実行機構2800およびレジスタ値監視機構2300を起動する（Ｓ１０）。忠実模擬実行機構2800 は時系列に沿って忠実に回路動作を模擬し、回路動作に応じてレジスタの値が変更される（レジスタ値テーブル4600が更新される）。レジスタ値監視機構2300 は、周期的な入力信号に基づいて、レジスタ値テーブル4600を監視し、レジスタ値テーブル4600が更新されたら、レジスタ値テーブル4600内の各レジスタの値（データ列）を、現在時刻とともに過去データ記憶テーブル4700 に格納する(Ｓ１１) 。
【００３８】
周期性検出機構2500は、過去データ記憶テーブル4700 に格納された上記現在時刻の各レジスタ値が、過去の各レジスタ値と一致し、かつ、上記現在時刻と、該過去の各レジスタ値の時刻との差が、周期的な入力信号の周期（入力周期）の倍数となるかどうかを調べる（Ｓ１２）。もしこの条件が満たされない場合は(Ｓ１２のＮＯ)、ステップＳ１１に戻る。
【００３９】
もしこの条件が満たされる場合は（Ｓ１２のＹＥＳ）、周期性検出機構2500 が周期検出シグナル4800 を発し、また、周期開始時刻、周期終了時刻を過去データ記憶テーブル4700 に格納する(Ｓ１３）。
【００４０】
周期検出シグナル4800 を受けた回路切換機構2700 は、忠実模擬実行機構2800 に回路停止シグナル4900 を送り、回路停止シグナル4900を受けた忠実模擬実行機構2800は模擬実行を停止する（Ｓ１４）。
【００４１】
模擬実行の停止後に時刻t のレジスタ値の要求4300があった場合(Ｓ１５のＹＥＳ)、レジスタ値回復機構2400 が、周期開始時刻と周期終了時刻とにより定まる周期における、時刻ｔに対応する位置を特定し、特定した位置のレジスタ値を時刻t のレジスタ値4400 として出力する（Ｓ１６）。レジスタ値の要求4300が特定のレジスタを示している場合は、その特定のレジスタの値のみを出力し、それ以外の場合は、全てのレジスタの値を出力するようにしてもよい。模擬実行停止後に時刻t のレジスタ値の要求4300 がないとき(Ｓ１５のＮＯ)、ユーザからの終了指示の入力等に応じて、処理を終了する。
【００４２】
図５のフローチャートのステップＳ１１およびＳ１２に相当するレジスタ値監視機構2300 および周期性検出機構2500 の処理を効率的に実現する例として、ハッシュを用いた手法に関して、図６のフローチャートを用いて説明する。ここでハッシュは、図７のように、エントリ領域と実体格納領域とからなるとする。エントリ領域には、実体格納領域へのポインタ（４バイトとする）を格納し、実体格納領域にはレジスタ値（ｎビットとする）を登録する。
【００４３】
まず回路に使用される各レジスタ（レジスタ値テーブル4600の各レジスタ）のビットを並べた値VAL（図１０の横一列分に相当） を作成する(Ｓ２１) 。VALはｎビットからなるとする。たとえば図１０の一行目（time =0）を参照して、VALは、cnt, cnt_next のビット幅が2ビットであり、それ以外のレジスタのビット幅は1ビットであるため、各レジスタの値を並べた2進数で表すと“1000010010”となる。
【００４４】
次にVALを元にhashKey を作成する（Ｓ２２）。たとえば、VALを所定のハッシュサイズ（HASH_SIZE）で割り算した余りをハッシュキー（hashKey）とする。
【００４５】
次に、hashKey 番目のエントリ領域にポインタが登録されているかどうかを調べる(Ｓ１３)。もし登録されていなければ(Ｓ２３のＮＯ)、空いている実体格納領域にVALを登録し、hashkey 番目のエントリ領域に実体格納領域へのポインタを格納する(Ｓ２４) 。
【００４６】
もしhashKey 番目のエントリ領域にポインタが登録されていれば(Ｓ２３のＹＥＳ) 、該ポインタが指す実体領域に登録された値がVAL と同じであるか、および現在時刻と実態領域に登録された値がもつ時刻との差が入力周期の倍数となるかを調べる（Ｓ２５）。もしこれらの条件が両方とも満たされれば (Ｓ２５のＹＥＳ) 、周期性検出機構2500 が周期検出シグナル4800 を発する（Ｓ２６） 。
【００４７】
もしこれらの条件が満たされなければ（Ｓ２５のＮＯ）、衝突が生じたことになり、オープンアドレス法に従い、新たなhashKey を決定する。たとえば元のhashKey に1を加えればよい(Ｓ２７)。そして、ステップＳ２３に戻る。
【００４８】
上記ハッシュを用いる場合において、レジスタ値回復機構2400 の処理（図５のステップＳ１６）の詳細に関して、図８および図９を用いて説明する。
【００４９】
上記ステップＳ１６では、模擬実行停止中において、要求された時刻ｔのレジスタ値を求めて出力する。ここで、周期開始時刻Ts, 周期終了時刻Tgは過去データ記憶テーブル4700 に記憶されており、周期CはTg − Tsとして表される。
【００５０】
時刻t のレジスタ値の要求4300 があったら、T ≡ t(modC )および、Ts < T < Tg を満たすT を求める(Ｓ３１)。T ≡ t(modC )は、TをCで割った余りと、tをCで割った余りが等しいことを意味する。次に、図９に示すように、時刻T のときのレジスタ値を取りだす(Ｓ３２) 。
【００５１】
ここでは、レジスタ値監視機構2300、レジスタ値回復機構2400 に関わる過去データ記憶テーブル4700 の実現方法の一例として、ハッシュを用いる手法に関して説明したが、このように、データ列（各レジスタの値）を逐次格納し、高速に参照する手法としては、木を用いる手法など、別の手法を用いることも可能である。またハッシュを用いる場合の衝突の対策として、ここではオープンアドレス法を用いる実施例を示したが、チェインハッシュ法などの別の手法を用いることも可能である。
【００５２】
以下、図１の模擬実行用回路モデル6000の動作の具体例を示す。
【００５３】
図１０は、図３の論理回路記述（論理回路モデル）1100を忠実模擬実行機構2800に実行させたとき、周期性検出までの、各レジスタの値の変化を表す。図１１は、時刻100のレジスタ値の要求4300 を受けた場合にレジスタ値回復機構2400により回復されたレジスタ値を表す。
【００５４】
上述した図５のフローチャートの通り、周期性が検出されるまでは、忠実模擬実行機構2800 およびレジスタ値監視機構2300が動作し、この結果、図１０のように各レジスタの値が時刻とともに過去データ記憶テーブル4700 に記憶される(図５のＳ１１) 。
【００５５】
ここで、time = 32 における各レジスタの値が、time =0 と完全に一致し、かつ、時間差（32-0=32）が入力周期（＝２）の倍数に一致するため、周期性検出機構2500 が各レジスタの値（データ列）の周期性を検出する(図５のＳ１２のＹＥＳ)。
【００５６】
周期性検出機構2500は、周期開始時刻Ts = 0, 周期終了時刻Tg = 32 を過去データ記憶テーブル4700 に登録し、周期検出シグナル4800を回路切替機構2700に発行する（Ｓ１３）。
【００５７】
回路切換機構2700はtime = 32 において忠実模擬実行機構2800 に対し回路停止シグナル5000を発行して、忠実模擬実行機構2800による模擬実行を停止させる(図５のＳ１４) 。
【００５８】
この後、時刻100のレジスタ値の要求4300 を受けた場合は、図８のステップＳ３１で説明したようにしてT の値を得る。この場合time = 100, Ts = 0, Tg = 32, 周期C = 32 であるため、簡単な計算によりT =4が得られる。従って、図９に示すようにして、time =4の実体格納領域の値を取り出す(図６のＳ３２) 。
【００５９】
以上のように本実施形態によれば、模擬実行時に各レジスタ値の周期性を検出した場合は、忠実模擬実行機構を停止するようにしたことにより、模擬実行を高速に行うことができる。
【００６０】
（第２実施形態）
本実施形態では、回路（タイマ回路）に対してイレギュラーな入力信号はないが、該回路からの出力信号が必要な場合に関して説明する。
【００６１】
図１２は、本発明の第２実施形態としての模擬実行用回路モデル（模擬実行装置）7000の構成を示す図である。
【００６２】
この模擬実行用回路モデル7000は、レジスタ値監視機構2300、周期性検出機構2500、過去データ記憶テーブル4700、回路切換機構2700, 忠実模擬実行機構2800, および出力機構2900 を備える。模擬実行用回路モデル7000は、外部からの周期的な入力信号4100 を入力とし、模擬実行停止中において、回路からの出力信号4500 を正確に出力することを目的とする。各機構は、第１実施形態と同様に、図１３に示すように、模擬実行用回路モデル作成部1000において論理回路記述1100を解析して各々に対応する記述（レジスタ値監視機構記述1300,周期性検出機構記述1500、回路切換機構記述1700, 忠実模擬実行機構記述1800、出力機構記述1900）を自動生成し、これらの記述を解釈および実行することにより実現される。第１実施形態における模擬実行用回路モデル6000と同様に、レジスタ値回復機構2400 を加えることにより、時刻t のレジスタ値の要求4300 を受けた場合に、時刻t のレジスタ値4400 を出力するように本実施形態を拡張することも可能である。
【００６３】
図１４は、図１２の模擬実行用回路モデル7000の動作を説明するフローチャートである。
【００６４】
第２実施形態と第１実施形態との相異点は、周期性検出機構2500による周期性検出時およびそれ以降の処理のみである。よって、相異点であるステップＳ４４のみを説明することとし、他のステップＳ４０〜Ｓ４３の説明は省略する。
【００６５】
周期性検出機構2500 は、各レジスタの値（データ列）の周期性を検出したら、前述の第１実施形態で説明した処理に加えて、以下の処理を行う。
【００６６】
周期性検出機構2500は、周期開始時刻Ts から周期終了時刻Tg までの周期の間の出力レジスタの動きを全て調べ、出力レジスタの値を時系列に記録した出力レジスタ動作テーブル（後述）を作成する。
【００６７】
周期性検出機構2500から周期検出シグナル4800 を受けた回路切換機構2700は、忠実模擬実行機構2800による模擬実行の停止および出力機構2900 の起動を指示する回路切替シグナル5000 を忠実模擬実行機構2800 に発する。これにより忠実模擬実行機構2800は模擬実行を停止し、出力機構2900を起動し、起動した出力機構2900は、上記出力レジスタ動作テーブルと、外部から入力される周期的な入力信号4100に基づき、レジスタ値テーブル4600における出力レジスタの値のみを変化させる。
【００６８】
以下、図１２の模擬実行用回路モデル7000の動作の具体例に関して述べる。
【００６９】
図３の論理回路記述（論理回路モデル）1100の模擬実行において、出力レジスタoutput の値の出力が必要な場合を考える。この場合、周期性を検出するまでの処理は、第１実施形態と同様であり、図１０と同一の各レジスタの値が過去データ記憶テーブル4700に逐次記憶されていく。
【００７０】
周期性検出機構2500が、周期性を検出した場合(time = 32において検出される) は、図１４のステップＳ４４に従って、処理を行う。
【００７１】
まず周期性検出機構2500 は周期性を検出した時点で、周期開始時刻から周期終了時刻までの出力レジスタの動きを調べ、調べた結果を記録した出力レジスタ動作テーブルを作成する。図３の論理回路記述1100の模擬実行の例では、1周期に相当する、時刻0 から時刻32 までの出力レジスタoutput の値は、図１０のように、時間2ごとの値が{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0} である。よって、値の継続時間と、該値とをセットにして、{{20,0}, {8,1}, {4,0}} といった情報を出力レジスタ動作テーブルとして記憶する。
【００７２】
また回路切換機構2700 は、周期性検出機構2500から周期検出シグナル4800 を受け取ると、回路切替シグナル5000 を発し、この結果、忠実模擬実行機構2800 が停止し、出力機構2900 が起動する。
【００７３】
出力機構2900 は、出力レジスタ動作テーブルを利用して、図１５に示す、verilog-HDL 風のコードに相当する処理を繰り返し行うことにより、レジスタ値テーブル4600における出力レジスタの値を更新する。模擬実行停止中においてもレジスタ値テーブル4600の出力レジスタを参照することで出力レジスタの正確な値を取得可能である。
【００７４】
以上のように本実施形態によれば、回路らの出力が必要な場合においても、忠実模擬実行機構を停止した後は、周期性に基づいて出力レジスタ値を変化させる軽い処理のみを行えばよいため、模擬実行を高速に行うことができる。
【００７５】
（第３実施形態）
本実施形態では、回路（タイマ回路）からの出力信号が必要であり、かつ該回路へのイレギュラーな入力信号（たとえばRESET信号）があり得る場合に関して説明する。
【００７６】
図１６は、本発明の第３実施形態としての模擬実行用回路モデル（模擬実行装置）8000の構成を示す図である。
【００７７】
この模擬実行用回路モデル8000は、レジスタ値監視機構2300,レジスタ値回復機構2400周期性検出機構2500,入力監視機構（入力検出機構）2600,回路切換機構2700,忠実模擬実行機構2800,出力機構2900、レジスタ値テーブル4600、過去データ記憶テーブル6520を備える。
【００７８】
この模擬実行用回路モデル8000は、模擬実行の停止中に、イレギュラーな入力信号4200があっても、回路から出力されるべき出力信号4500 を正確に外部の回路へ出力することを目的とする。外部の回路は、たとえば模擬実行用回路モデル8000の外側で模擬実行されている回路である。入力監視機構2600 は、模擬実行の停止中にイレギュラーな入力信号4200 を検出し、回路切換機構2700 に対し入力検出シグナル5200 を発する。各機構は、第１および第２実施形態と同様に、図１７に示すように、模擬実行用回路モデル作成部1000において論理回路記述1100を解析して各々に対応する記述（レジスタ値監視機構記述1300,周期性検出機構記述1500、入力監視機構記述1600、回路切換機構記述1700, 忠実模擬実行機構記述1800、出力機構記述1900）を自動生成し、これらの記述を解釈および実行することにより実現される。
【００７９】
図１８は、論理回路記述1100に相当する回路から出力されるべき出力信号4500 を正確に出力する処理を説明するフローチャートである。
【００８０】
本実施形態では、第２実施形態と比べると、回路切換機構2700およびレジスタ値回復機構2400 の処理が異なる。これは、回路へのイレギュラーな入力信号4200 があった場合、周期動作の前提条件が崩れるため、忠実模擬実行機構2800 の動作に復帰する必要があるからである。
【００８１】
イレギュラーな入力信号4200 を検出するまでの処理（Ｓ５０〜Ｓ５４）は、第２実施形態と同じであるため詳細な説明を省略する。
【００８２】
忠実模擬実行機構2800 の停止中に、入力監視機構2600 がイレギュラーな入力信号4200 を検出した場合は（Ｓ５５のＹＥＳ）、回路切換機構2700 に入力検出シグナル5200 を発する。入力検出シグナル5200 を受けた回路切換機構2700 は、まず、イレギュラーな入力信号4200 を検出した時刻をt として、レジスタ値回復機構2400 に時刻t のレジスタ値の要求4300 を送る。時刻t のレジスタ値の要求4300 を受けたレジスタ値回復機構2400 は、過去データ記憶テーブル4700 に記憶された時刻tに対応するレジスタ値をレジスタ値テーブル4600 に書き込む（Ｓ５６）。またイレギュラーな入力信号4200 によるレジスタ（たとえばＲＥＳＥＴ）の値の変化もレジスタ値テーブル4600 に書き込む（Ｓ５６）。この後、回路切換機構2700 は、出力機構2900および模擬実行機構2800 に回路切替シグナル5000 を送り、この結果、出力機構2900の動作は停止し、忠実模擬実行機構2800 の動作が再開する。このような一連の処理により、イレギュラーな入力信号4200 が検出された時点から再び忠実模擬実行機構2800 の動作を再開できる。
【００８３】
以下、図１６の模擬実行用回路モデル8000の動作の具体例に関して述べる。
【００８４】
図３の論理回路記述1100の模擬実行の停止中において、時刻time = 100 に、“RESET← 1”（RESETレジスタへ１を入力する）という、イレギュラーな入力信号4200 が検出される例を考える。 
まず、入力監視機構2600 が回路切換機構2700 に入力検出シグナル5200 を発する。回路切換機構2700 は、レジスタ値回復機構2400 に時刻100 のレジスタ値の要求4300 を送る。レジスタ値回復機構2400 は、t = 100に対応するレジスタ値を取得し、レジスタ値テーブル4600 に書き込む。ここまでの処理は、第１実施形態の処理と同一である。本例ではさらに、“RESET ← 1”に基づき、レジスタ値テーブル4600におけるRESET レジスタの値を1に変更する。その後に、忠実模擬実行機構2800 の動作を再開することにより、正確に動作を継続することができる。
【００８５】
以上では、模擬実行の停止中にイレギュラーな入力信号4200が入力された場合を説明したが、模擬実行中にイレギュラーな入力信号4200が入力された場合はたとえば以下のようにする。入力監視機構2600は、イレギュラーな入力信号4200を検出すると、その旨をレジスタ値回復機構2400に通知する。この通知を受けたレジスタ値回復機構2400は、過去データ記憶テーブル6520をクリアするとともに（周期動作の前提が崩れるため）、レジスタ値テーブル4600におけるレジスタ（例えばRESETレジスタ）に、イレギュラーな入力信号4200に基づく値（１）を書き込む。
【００８６】
以上のように、本実施形態によれば、レジスタ値の周期性が検出された後、回路からの出力処理以外の回路動作を停止できるとともに、イレギュラーな入力信号が入力されたときは、記憶したレジスタ値を元にレジスタ値を回復し、通常回路動作を再開するようにしたことにより、模擬実行を誤り無く高速に行うことができる。
【００８７】
（第４実施形態）
第４および第５実施形態では、第１〜第３実施形態の改良手法に関して述べる。第４および第５実施形態では、模擬実行時の周期性検出以降の処理は、第１〜第３実施形態とほぼ同一である。そこで、第４および第５実施形態では、一例として、第３実施形態の模擬実行時における周期性検出までの処理との相異点を中心に説明する。
【００８８】
第４実施形態および第５実施形態では、図１９に示すように、模擬実行用回路モデル作成装置に対して依存グラフ作成部2000を追加し、依存グラフ作成部2000において、論理回路記述1100からレジスタ間の依存グラフ1200 を作成する。
【００８９】
レジスタ間の依存グラフ1200 は有向グラフであり、頂点（ノード）はレジスタに対応し、頂点Aから頂点B への辺（方向付きアーク）は、頂点Aの値が、頂点B の値の計算に使われることを表す。図２１に、図３の論理回路記述1100に対し作成されたレジスタ間の依存グラフ1200 の例を示す。
【００９０】
図２０は、論理回路記述1100がverilog-HDL である場合の、レジスタ間の依存グラフ1200 を作成するための処理の概要を説明するフローチャートである。verilog-HDL 以外の他の論理回路記述1100に対しても同様の処理を行うことができる。
【００９１】
まず、論理回路記述1100に現れるレジスタをレジスタ間の依存グラフ1200 の頂点とする（Ｓ６１）。
【００９２】
次に、論理回路記述1100において、代入処理(A<= Bを含む式 もしくはA = Bを含む式)があれば（Ｓ６２のＹＥＳ）、頂点B （第２レジスタ）から頂点A（第１レジスタ）向きの実線の辺（方向付きアーク）をレジスタ間の依存グラフ1200 に追加する(Ｓ６３)。第１レジスタを検出するレジスタ検出部を依存グラフ作成部2000は有している。また、代入処理のタイミングが他のレジスタC（第３レジスタ） の値（値の変化も含む）により決定される場合は、頂点C から頂点A向きの点線の辺（方向付きアーク）をレジスタ間の依存グラフ1200 に追加する(Ｓ６３) 。
【００９３】
最後に、イレギュラーな入力信号に基づく値を格納するレジスタ（イレギュラーな入力レジスタ）に相当する、頂点および辺を消去する(Ｓ６４) 。
【００９４】
第４実施形態および第５実施形態ではこのようにして作成したレジスタ間の依存グラフ1200を用いて、回路全体の周期性検出までの処理を効率化する。以下本実施形態について詳細に説明する。
【００９５】
図２２は、第４実施形態に係わる、レジスタの一部を監視する例（監視レジスタ集合Rを限定する手法）を説明するフローチャートである。
【００９６】
まず、R ←{φ} とする(Ｓ７１) 。すなわちRを空集合とする。
【００９７】
次に、未処理の各頂点に関して順番に、処理を行う（Ｓ７２）。
【００９８】
対象とする頂点mについて、頂点mに点線辺の入力があり、頂点mに入力する実線辺がある場合、その実線を出力する頂点nについて、R←R+{n} とする（Ｓ７３）。すなわち頂点nを監視レジスタ集合Ｒに入れる。また、頂点m が点線を出力するならば、R← R+{m} とする(Ｓ７３) 。すなわち頂点mを監視レジスタ集合Ｒに入れる。この処理を全ての頂点に対して行うことにより、監視レジスタ集合Rが得られる。このように監視レジスタ集合Ｒには、他のレジスタ（第２レジスタまたは第３レジスタまたはこれらの両方）から値を計算できるレジスタを第１レジスタとしたときの当該他のレジスタが格納される。
【００９９】
本実施形態の模擬実行方法は、レジスタ値監視機構2300が監視および登録し、レジスタ値回復機構2400 が回復するレジスタがレジスタ全体から監視レジスタ集合Rに限定される以外は、第３実施形態と全く同じとなる。この手法により、レジスタ値監視機構2300 およびレジスタ値回復機構2400 の１回当りの処理コストを削減することができる。監視レジスタ集合Rに含まれないレジスタの値は、同時刻、または、同時刻とその前または後の時刻、における監視レジスタ集合Rのレジスタの値から計算可能である。
【０１００】
以下、図３の論理回路記述1100を例に、本実施形態の具体例に関して説明する。
【０１０１】
最初にRESET レジスタがイレギュラーな入力信号4200 に基づく値を格納するレジスタ（イレギュラーな入力レジスタ）であるため、RESETレジスタを消去し、図２３のレジスタ間の依存グラフ1200 が得られる。
【０１０２】
この依存グラフ1200において、たとえばcnt 頂点は、点線辺の入力があり、またcnt_next 頂点からの実線辺の入力があるため、cnt_next をRに追加する。同様の理由で、divide_cnt_next もR に追加する。
【０１０３】
また、divide_clk からは点線辺の出力があるので、divide_clk をRに追加する。
【０１０４】
以上より、最終的に、監視レジスタ集合R = { cnt_next, divide_cnt_next, divide_clk} が得られる。
【０１０５】
次に図２４を用いて、本実施形態における模擬実行の例を説明する。本実施形態の模擬実行では、上述したとおり、cnt_next, divide_clk, divide_cnt_next のみを監視すればよい。time = 32において、cnt_next, divide_clock, divide_cnt_next の3個のレジスタの値が、time =0のときの値と完全に一致するので、周期性（周期32）が検出される。
【０１０６】
ここで、第１実施形態のように、時刻ｔのレジスタ値の要求4300を受けた場合は、レジスタ値回復機構2400が、時刻ｔに対応する、監視レジスタ集合に属するレジスタの値を過去データ記憶テーブル6520から取得する。そして、レジスタ値回復機構2400は、取得したレジスタ値から、監視対象となっていないレジスタの値を求め、各レジスタの値を、時刻ｔのレジスタ値4400として出力する。レジスタ値回復機構2400は要求信号受信部、レジスタ値計算部および出力部を有している。たとえば時刻６のdivide_cntの値の要求を受けた場合は、図３（Ｂ）の「assign divide_cnt_next=divide_cnt+1」を参照して、時刻６のdivide_cnt_nextの値である２から１を引いた１を、時刻６のdivide_cntの値として返す。必要に応じて、要求された時刻ｔのレジスタの値だけでなく、時刻ｔの前または後のレジスタの値を用いて、監視対象となっていないレジスタの値を求めることもある。
【０１０７】
以上のように本実施形態によれば、監視対象とするレジスタを限定したことにより、周期性を検出するまでの監視によるオーバーヘッドを削減することが可能となり、模擬実行時間を短縮することが可能となる。
【０１０８】
（第５実施形態）
本実施形態では、レジスタ間の依存グラフ1200 の強連結成分ごとに、監視・登録を行う改良手法について説明する。
【０１０９】
図２６は、レジスタ間の依存グラフ1200 の強連結成分を説明する図である。
【０１１０】
上述したように依存グラフ1200は有効グラフである。有向グラフが強連結であるとは、グラフ上の任意の2ノード間に双方向に有向パス（ループ）が存在することである。有向グラフは、必ず強連結な部分グラフに分解できる。この分解した各部分グラフのことを強連結成分と呼ぶ。有向グラフを強連結成分に分解するアルゴリズムとしては、Tarjanのアルゴリズムが知られており、その計算量は、グラフのノード数をn, エッジ数をm としたとき、O(m+n)となる。
【０１１１】
図２６の例では、レジスタ間の依存グラフ1200 は、R1 = {cnt, cnt_next}, R2 = {divide_clk}, R3 = {divide_cnt, divide_cnt_next}, R4 = {output} の4個の強連結成分に分解される。また、それぞれの強連結成分の入力レジスタは、R1 : {clk}, R2 : {cnt}, R3: {divide_clk}, R4 : {divide_cnt} 、また、それぞれの出力レジスタは、R1 :{cnt}, R2 :{divide_clk}, R3:{divide_cnt}, R4 :{ なし} となる。
【０１１２】
以下、本実施形態の動作について図２５のフローチャートを用いて説明する。本実施形態の動作と第３実施形態の動作との相異点は、第３実施形態で用いた図１８のステップＳ５２〜Ｓ５４の部分であるため、図２５のフローチャートには、ステップＳ５２〜Ｓ５４に対応する変更部分のみを示した。
【０１１３】
模擬実行開始時は、第３実施形態と同様に全てのレジスタについて監視する。ここで、該監視、ならびに過去データ記憶テーブル4700への登録は、未停止の強連結成分ごとに行う(Ｓ８１) 。監視および登録のタイミングは強連結成分内のレジスタ値が変化するたび、あるいは周期的な入力信号4100の周期ごとに行う。
【０１１４】
強連結成分内のレジスタ値が、過去のレジスタ値と一致し、かつ一致するまでの時間が、各強連結成分における全ての入力レジスタの変化周期の倍数となるか（周期性検出条件）を調べる（Ｓ８２）。すなわちあらかじめ入力レジスタの周期が分かっている必要があり、各強連結成分の入力レジスタの内、一部のレジスタの変化周期が不明である場合は、当該条件を満たさない。
【０１１５】
もし上記周期性検出条件を満たすならば(Ｓ８２のＹＥＳ)、周期性検出機構2500は、回路切換機構2700 に対し、周期性が検出された強連結成分に関する周期検出シグナル4800 を発し、周期開始時刻Ts, 周期終了時刻Tg を過去データ記憶テーブル4700 に格納する(Ｓ８３) 。
【０１１６】
周期検出シグナル4800 を受けた回路切換機構2700 は、忠実模擬実行機構2800 が模擬実行している処理のうち、周期性が検出された強連結成分に含まれるレジスタを扱う処理を停止し、該強連結成分における出力レジスタ（ここでは次段の強連結成分への入力値を格納するレジスタを示す）の振舞いを計算する出力機構を起動する（Ｓ８４）。
【０１１７】
全ての強連結成分に対応する処理を停止したかどうかを調べ（Ｓ８５）、もしそうでない場合はステップＳ８１に戻り、もしそうである場合は（Ｓ８５のＹＥＳ）、図１８のステップＳ５５に進む。
【０１１８】
上記手法により、回路の中で、周期動作する部分ごとに、段階的に停止することができる。また回路全体の動きが周期動作ではない場合にも、周期動作する部分のみを停止することができる。
【０１１９】
以下、図３の論理回路記述1100の模擬実行を例にとって、本実施形態の動作の具体例を説明する。
【０１２０】
まず、レジスタ間の依存グラフ1200 は、図２６に示したように、R1 = {cnt, cnt_next}, R2 = {divide_clk}, R3 = {divide_cnt, divide_cnt_next}, R4 = {output} の4個の強連結成分に分解される。また、それぞれの強連結成分の入力レジスタは、R1 : {clk}, R2 : {cnt}, R3: {divide_clk}, R4 : {divide_cnt} 、また、それぞれの出力レジスタは、R1 :{cnt}, R2 :{divide_clk}, R3:{divide_cnt}, R4 :{ なし} となる。
【０１２１】
周期性検出までの模擬実行は、上述した図２５のフローチャートに従っておこなう。より詳細には以下の通りである。
【０１２２】
まず忠実模擬実行機構2800は、論理回路記述1100に従い模擬実行を行う。そして、レジスタ値監視機構2300は、強連結成分R1,R2,R3,R4 ごとに、レジスタ値テーブル4600におけるレジスタ値を監視する（Ｓ８１）。レジスタ値が更新された強連結成分を検出したら、レジスタ値テーブル4600におけるレジスタ値を現在時刻とともに過去データ記憶機構4700に記憶させる（Ｓ８１）。周期性検出機構2500は、強連結成分ごとに、周期検出処理を行う(Ｓ８２) 。
【０１２３】
本例では、図２７のように、time =8 の時点で、強連結成分R1 のレジスタcnt およびcnt_next の値がtime =0と一致し, かつ、強連結成分R1 の周期(= 8) が、入力レジスタであるclkレジスタの周期(=2)の倍数であるため、強連結成分R1 の周期として8が検出される（Ｓ８３）。なお本例では監視および登録のタイミングは周期的な入力信号4100の周期ごとになっている。強連結成分R1 の周期として8が検出されると、回路切換機構2700 は、cnt およびcnt_next レジスタに関する代入演算処理を全て停止し、出力レジスタであるcntレジスタの出力機構を起動する（Ｓ８４）。ここでcntレジスタの周期が8であることを利用すると、同じtime =8 の時点で、強連結成分R2 の周期を検出できる。なぜなら、強連結成分R2 を構成するdivide_clkレジスタの値がtime =8と、time =0の時点で一致し、かつこの強連結成分R2 の周期(= 8) が、強連結成分R2 の入力レジスタであるcnt レジスタの周期(=8)の倍数となるからである。この結果、強連結成分R1 およびR2 に関する忠実模擬実行機構2800 は、R1, R2 からの出力レジスタである、divide clk レジスタの出力機構を除いて、強連結成分R1 およびR2に関する模擬実行を全て停止する（先ほど起動したcntレジスタの出力機構も停止する）。すなわち、time =8以降は、図２８（Ａ）および図２８（Ｂ）に相当する論理回路記述のみを実行する。この後、同様に、time = 32 の時点で、強連結成分R3, R4 に関する周期性が検出され、time = 32 以降は、回路全体の模擬実行を停止できる。
【０１２４】
以上のように、本実施形態によれば、論理回路記述1100に相当する回路の中で周期性が検出された部分を順に停止するため、回路全体の周期性を検出するまでの、回路そのものの処理量を減らすことが可能となり、模擬実行時間を短縮することができる。
【０１２５】
以下、第１〜第５実施形態のそれぞれについて高速化の効果に関して詳細に述べる。
【０１２６】
最初に第１実施形態に関しては、周期性を検出するまでの間は、レジスタ値監視機構2300 および周期性検出機構2500 の処理が余分に必要となるために、単純に忠実模擬実行機構2800 のみを動作させる場合と比べると、オーバーヘッドがある。一方、時刻tのレジスタ値の要求4300 のtが1周期より長い場合には、その時間tの長さに依存する処理時間はかからないため、tが大きければ大きい程、高速化効果が大きい。
【０１２７】
また、第２実施形態に関しては、周期性の検出後も、出力機構を動作させる必要がある。この場合、元の回路全体の動作負荷と、出力機構の動作負荷の比の分だけの高速化効果が得られる。
【０１２８】
次に、第３実施形態では、イレギュラーな入力信号4200 が生じる時刻t 以降は、再び、忠実模擬実行機構2800 の動作を再開する必要がある。そのため、tが十分大きい場合には、第２実施形態と同じ高速化効果が得られるが、t が小さい場合は効果が小さくなる。
【０１２９】
一方、第４実施形態の監視レジスタの絞り込み手法は、周期性が検出されるまでのオーバーヘッドを削減する効果がある。レジスタ値監視機構2300 および周期性検出機構2500 の処理のオーバーヘッドは、ほぼ監視レジスタの個数に比例するので、監視レジスタを絞りこんだ分に比例してオーバーヘッドを削減でき、高速化が見込める。
【０１３０】
最後に第５実施形態では、論理回路記述に相当する回路の中で周期検出した部分を順に停止するため、回路全体の周期性を検出するまでの、回路そのものの処理量を減らすことができ、高速化が見込める。また、回路全体のレジスタ値が周期をもたない場合は、上記第１実施形態から第４実施形態までの手法では、高速化効果が得られないが、この第５実施形態の場合には、回路全体において周期検出できた部分のみを停止できるため、高速化が見込める。
【図面の簡単な説明】
【０１３１】
【図１】第１実施形態に係わる模擬実行用回路モデルの構成を示す図。
【図２】図１の模擬実行用回路モデルの自動作成方法の一例を示す図。
【図３】論理回路記述の例を示す図。
【図４】論理回路記述の例を示す図。
【図５】図１のモデルを模擬実行したときの動作を説明するフローチャート。
【図６】レジスタ値の登録処理および周期検出処理のハッシュによる実装の詳細を示すフローチャート。
【図７】ハッシュを用いたレジスタ値の登録方法を説明する図。
【図８】レジスタ値の回復処理のハッシュによる実装の詳細を説明するフローチャート。
【図９】時刻t のレジスタ値の回復方法を説明する図。
【図１０】周期性検出処理の例を説明する図。
【図１１】レジスタ値の回復処理の例を説明する図。
【図１２】第２実施形態に係わる模擬実行用回路モデルの構成を示す図。
【図１３】図１２の模擬実行用回路モデルの自動作成方法の一例を示す図。
【図１４】図１２のモデルを模擬実行したときの動作を説明するフローチャート。
【図１５】出力機構の処理を記述した例を示す図。
【図１６】第３実施形態に係わる模擬実行用回路モデルの構成を示す図。
【図１７】図１６の模擬実行用回路モデルの自動作成方法の一例を示す図。
【図１８】図１６のモデルを模擬実行したときの動作を説明するフローチャート。
【図１９】依存グラフ作成部を示す図。
【図２０】依存グラフの作成処理を説明するフローチャート。
【図２１】依存グラフの一例を示す図。
【図２２】監視レジスタ限定処理を説明するフローチャート。
【図２３】監視レジスタの例を示す図。
【図２４】第４実施形態に係わる周期検出の例を示す図。
【図２５】第５実施形態の動作を説明するフローチャート。
【図２６】強連結成分の例を示す図。
【図２７】周期検出の例を示す図。
【図２８】回路の一部が停止した場合後に行われる処理の内容の記述例。
【符号の説明】
【０１３２】
１１００：論理回路記述（論理回路モデル）
１２００：依存グラフ
２０００：依存グラフ作成部
２３００：レジスタ値監視機構
２４００：レジスタ値回復機構
２５００：周期性検出機構
２６００：入力監視機構
２７００：回路切替機構
２８００：忠実模擬実行機構
２９００：出力機構
４１００：周期的な入力信号
４７００：過去データ記憶テーブル
６０００、７０００、８０００：模擬実行用回路モデル
【図１】
2008181227.tif 000003
【図２】
2008181227.tif 000004
【図３】
2008181227.tif 000005
【図４】
2008181227.tif 000006
【図５】
2008181227.tif 000007
【図６】
2008181227.tif 000008
【図７】
2008181227.tif 000009
【図８】
2008181227.tif 000010
【図９】
2008181227.tif 000011
【図１０】
2008181227.tif 000012
【図１１】
2008181227.tif 000013
【図１２】
2008181227.tif 000014
【図１３】
2008181227.tif 000015
【図１４】
2008181227.tif 000016
【図１５】
2008181227.tif 000017
【図１６】
2008181227.tif 000018
【図１７】
2008181227.tif 000019
【図１８】
2008181227.tif 000020
【図１９】
2008181227.tif 000021
【図２０】
2008181227.tif 000022
【図２１】
2008181227.tif 000023
【図２２】
2008181227.tif 000024
【図２３】
2008181227.tif 000025
【図２４】
2008181227.tif 000026
【図２５】
2008181227.tif 000027
【図２６】
2008181227.tif 000028
【図２７】
2008181227.tif 000029
【図２８】
2008181227.tif 000030