(57)【要約】  【課題】  動的再構成可能ハードウエア上の模擬実行時にメモリの使用量を削減する。  【解決手段】  動的再構成可能ハードウエアに論理回路を書き込む動作を模擬するとき、該論理回路の実行状態を格納するメモリ領域は該論理回路の再構成単位ごとに実行時割当メモリ２００に割り当て、該論理回路の構成データを格納するメモリ領域は、該構成データに識別子３が付与されているときは参照テーブル３００を用いて実行時割当メモリ２００のメモリ領域を共有し、識別子が付与されていないときはハッシュテーブル４００を用いて実行時割当メモリ２００のメモリ領域を共有して、模擬を実行する。【選択図】  図７
2005056038.tif 000002
【特許請求の範囲】
【請求項１】
記憶素子の保持内容を書き換えることによって部分的に論理回路の構成あるいは機能を実行中に変更可能な動的再構成可能ハードウェアを対象として、その動作を模擬する模擬方法であって、
模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際には、該論理回路の構成データ及び実行状態を格納するメモリ領域を該論理回路の再構成単位ごとに実行時割当メモリに動的に割り当ててその模擬を行い、
書き込まれた前記論理回路を消去する動作を模擬する際には、前記実行時割当メモリの前記割り当てたメモリ領域を開放することを特徴とする模擬方法。
【請求項２】
請求項１に記載の模擬方法において、
論理回路の構成データに再構成単位ごとに予め付与した識別子をインデックスとして前記実行時割当メモリのアドレスを検索する参照テーブルを用い、
前記模擬対象ハードウエア上に論理回路を書き込む動作を模擬する際には、
該論理回路の実行状態を格納するメモリ領域は、該論理回路の再構成単位ごとに前記実行時割当メモリに割り当て、
前記論理回路の構成データを格納するメモリ領域は、該構成データの識別子をインデックスとして前記参照テーブルからアドレスを検索し、該アドレスが未登録のときは前記実行時割当メモリにメモリ領域を割り当てて該割り当てたメモリ領域のアドレスを前記参照テーブルに登録し、前記検索したアドレスが登録済みのときは前記実行時割当メモリの登録済みアドレスのメモリ領域を共有して、
模擬を行うことを特徴とする模擬方法。
【請求項３】
請求項１に記載の模擬方法において、
論理回路の構成データをハッシュ関数により計算し得られた要約値をインデックスとして前記実行時割当メモリのアドレスを検索するハッシュテーブルを用い、
前記模擬対象ハードウエア上に論理回路を書き込む動作を模擬する際には、
該論理回路の実行状態を格納するメモリ領域は、該論理回路の再構成単位ごとに前記実行時割当メモリに割り当て、
前記論理回路の構成データを格納するメモリ領域は、該論理回路の再構成単位ごとに該構成データの要約値を計算し得られた要約値と同じ要約値をもつ構成データのアドレスを前記ハッシュテーブルで検索し、該検索したアドレスに対応する構成データの中からデータが一致する構成データを探し、データが一致する構成データがなければ、該構成データを格納するメモリ領域を前記実行時割当メモリに割り当てて該メモリ領域のアドレスを前記ハッシュテーブルに登録し、データが一致する構成データのメモリ領域があれば、該データが一致する構成データのメモリ領域を共有して、
模擬を行うことを特徴とする模擬方法。
【請求項４】
請求項１に記載の模擬方法において、
請求項２に記載の参照テーブルと請求項３に記載のハッシュテーブルを用い、
前記模擬対象ハードウエア上に論理回路を書き込む動作を模擬する際には、
該論理回路の実行状態を格納するメモリ領域は、該論理回路の再構成単位ごとに前記実行時割当メモリに割り当て、
該論理回路の構成データを格納するメモリ領域は、請求項２に記載の識別子が付与されているときは、請求項２に記載の参照テーブルを用いて請求項２に記載のように前記実行時割当メモリに割り当てを行い、請求項２に記載の識別子が付与されていないときは、請求項３に記載のハッシュテーブルを用いて請求項３に記載のように前記実行時割当メモリに割り当て、
模擬を実行することを特徴とする模擬方法。
【請求項５】
記憶素子の保持内容を書き換えることによって部分的に論理回路の構成あるいは機能を実行中に変更可能な動的再構成可能ハードウェアを対象として、その動作を模擬する模擬システムであって、
実行時割当メモリと、
模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際に、前記実行時割当メモリに該論理回路の構成データ及び実行状態を格納するメモリ領域を該論理回路の再構成単位ごとに動的に割り当て、あるいは該割り当てたメモリ領域を再利用可能に開放するメモリ管理手段と、
を具備することを特徴とする模擬システム。
【請求項６】
請求項５に記載の模擬システムにおいて、
前記論理回路の構成データに前記論理回路の再構成単位ごとに付与された識別子をインデックスとして前記実行時割当メモリのアドレスを検索する参照テーブルを具備し、
模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際に、該論理回路の実行状態を格納するメモリ領域は前記実行時割当メモリに割り当てられ、該論理回路の構成データを格納するメモリ領域は前記識別子をインデックスとして前記参照テーブルから検索した前記実行時割当メモリのアドレスのメモリ領域と共有されるようにしたことを特徴とする模擬システム。
【請求項７】
請求項５に記載の模擬システムにおいて、
前記論理回路の構成データをハッシュ関数により計算し得られた要約値をインデックスとして前記実行時割当メモリのアドレスを検索するハッシュテーブルを具備し、
模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際に、該論理回路の実行状態を格納するメモリ領域は前記実行時割当メモリに割り当てられ、該論理回路の構成データを格納するメモリ領域は前記要約値により前記ハッシュテーブルで検索した前記実行時割当メモリのアドレスの中のデータが一致する構成データのメモリ領域と共有されるようにしたことを特徴とする模擬システム。
【請求項８】
請求項５に記載の模擬システムにおいて、
請求項６に記載の参照テーブルと請求項７に記載のハッシュテーブルとを具備し、
模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際に、該論理回路の実行状態を格納するメモリ領域は前記実行時割当メモリに割り当てられ、前記論理回路の構成データを格納するメモリ領域は、請求項６に記載の識別子が付与されているときは前記識別子をインデックスとして前記参照テーブルから検索した前記実行時割当メモリのアドレスのメモリ領域と共有され、前記識別子が付与されていないときは前記要約値により前記ハッシュテーブルで検索した前記実行時割当メモリのアドレスの中のデータが一致する構成データのメモリ領域と共有されるようにしたことを特徴とする模擬システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶素子に保持された論理回路の構成データを書き換えることによって部分的に該論理回路の構成あるいは機能を実行中に変更可能な動的再構成可能ハードウェアを対象として、その動作を模擬する模擬方法及び模擬システムに関するものである。
【背景技術】
【０００２】
論理回路をプログラムできる素子としてＰＬＤ(Programmable Logic Device)やＦＰＧＡ(Field Programmable Gate Array)が知られている。回路を電気的に何度でも書き換え可能なＦＰＧＡは、製造後にハードウェアの機能や構成を変更できる素子として利用されるようになっている。このような素子を用いたハードウエアは再構成可能ハードウェアと呼ばれる。中でも回路構成を処理の内容や計算状況に応じて実行時に変えることができるものは動的再構成可能ハードウェアと呼ばれ、ソフトウェアの柔軟性とハードウェアの性能を両立するものとして期待されている。
【０００３】
動的再構成可能ハードウェアは、商用のＳＲＡＭベースのＦＰＧＡに回路の構成データを格納するメモリとＦＰＧＡの書き換えを制御するプロセッサを結合して構成することもできるが、実行時の再構成能力を高めるためマルチコンテクスト型ＦＰＧＡやＰＣＡ（Plastic Cell Architecture、特許文献１）などの専用アーキテクチャが提案されている。
【０００４】
マルチテクスト型ＦＰＧＡは、回路の構成を保持するメモリを多重に持ち、それを実行時に切り替えることで、通常のＦＰＧＡより大規模な論理回路の実行をオンチップで行えるようにするものである。一方ＰＣＡは、ＦＰＧＡとセルオートマトンを結合して、デバイス上にプログラムされる論理回路を部分的に読み出して、バイナリデータに分解して別の場所に運び、書き込むなどより強力な実行時再構成能力を与えたものである。
【０００５】
従来の静的なハードウェアの模擬システムとしては、ハードウェア設計の各工程に対応した、ハードウェア記述言語（ＨＤＬ）レベルのシミュレータ、ＲＴＬ(Register Transfer Level)シミュレータ、ゲートレベルシミュレータがあり、その技術は確立している。一方、動的再構成可能ハードウェアに村しては、現在のところ、再構成機構そのものを模擬対象に加えた専用の模擬システムが開発され、存在している。
【特許文献１】特開平１１−１６７５５６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ＰＣＡのような動的再構成可能アーキテクチャの振る舞いを厳密に模擬するために、実デバイスと同様のデータ構造を採用し、構成データを保持するメモリを固定的に割り付けて用いると、ハードウェアの規模に比例して多量のメモリリソースを必要とし、模擬規模が制限される。
【０００７】
本発明の目的は、動的再構成可能ハードウェア上で実行するアプリケーションの特性を利用して、使用メモリ容量を削減可能にした模擬方法及び模擬システムを提供することである。
【課題を解決するための手段】
【０００８】
請求項１にかかる発明の模擬方法は、記憶素子の保持内容を書き換えることによって部分的に論理回路の構成あるいは機能を実行中に変更可能な動的再構成可能ハードウェアを対象として、その動作を模擬する模擬方法であって、模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際には、該論理回路の構成データ及び実行状態を格納するメモリ領域を該論理回路の再構成単位ごとに実行時割当メモリに動的に割り当ててその模擬を行い、書き込まれた前記論理回路を消去する動作を模擬する際には、前記実行時割当メモリの前記割り当てたメモリ領域を開放することを特徴とする。
【０００９】
請求項２にかかる発明の模擬方法は、請求項１に記載の模擬方法において、論理回路の構成データに再構成単位ごとに予め付与した識別子をインデックスとして前記実行時割当メモリのアドレスを検索する参照テーブルを用い、前記模擬対象ハードウエア上に論理回路を書き込む動作を模擬する際には、該論理回路の実行状態を格納するメモリ領域は、該論理回路の再構成単位ごとに前記実行時割当メモリに割り当て、前記論理回路の構成データを格納するメモリ領域は、該構成データの識別子をインデックスとして前記参照テーブルからアドレスを検索し、該アドレスが未登録のときは前記実行時割当メモリにメモリ領域を割り当てて該割り当てたメモリ領域のアドレスを前記参照テーブルに登録し、前記検索したアドレスが登録済みのときは前記実行時割当メモリの登録済みアドレスのメモリ領域を共有して、模擬を行うことを特徴とする。
【００１０】
請求項３にかかる発明の模擬方法は、請求項１に記載の模擬方法において、論理回路の構成データをハッシュ関数により計算し得られた要約値をインデックスとして前記実行時割当メモリのアドレスを検索するハッシュテーブルを用い、前記模擬対象ハードウエア上に論理回路を書き込む動作を模擬する際には、該論理回路の実行状態を格納するメモリ領域は、該論理回路の再構成単位ごとに前記実行時割当メモリに割り当て、前記論理回路の構成データを格納するメモリ領域は、該論理回路の再構成単位ごとに該構成データの要約値を計算し得られた要約値と同じ要約値をもつ構成データのアドレスを前記ハッシュテーブルで検索し、該検索したアドレスに対応する構成データの中からデータが一致する構成データを探し、データが一致する構成データがなければ、該構成データを格納するメモリ領域を前記実行時割当メモリに割り当てて該メモリ領域のアドレスを前記ハッシュテーブルに登録し、データが一致する構成データのメモリ領域があれば、該データが一致する構成データのメモリ領域を共有して、模擬を行うことを特徴とする。
【００１１】
請求項４にかかる発明の模擬方法は、請求項１に記載の模擬方法において、請求項２に記載の参照テーブルと請求項３に記載のハッシュテーブルを用い、前記模擬対象ハードウエア上に論理回路を書き込む動作を模擬する際には、該論理回路の実行状態を格納するメモリ領域は、該論理回路の再構成単位ごとに前記実行時割当メモリに割り当て、該論理回路の構成データを格納するメモリ領域は、請求項２に記載の識別子が付与されているときは、請求項２に記載の参照テーブルを用いて請求項２に記載のように前記実行時割当メモリに割り当てを行い、請求項２に記載の識別子が付与されていないときは、請求項３に記載のハッシュテーブルを用いて請求項３に記載のように前記実行時割当メモリに割り当て、模擬を実行することを特徴とする。
【００１２】
請求項５にかかる発明の模擬システムは、記憶素子の保持内容を書き換えることによって部分的に論理回路の構成あるいは機能を実行中に変更可能な動的再構成可能ハードウェアを対象として、その動作を模擬する模擬システムであって、実行時割当メモリと、擬対象ハードウェア上に論理回路を書き込む動作を模擬する際に、前記実行時割当メモリに該論理回路の構成データ及び実行状態を格納するメモリ領域を該論理回路の再構成単位ごとに動的に割り当て、あるいは該割り当てたメモリ領域を再利用可能に開放するメモリ管理手段と、を具備することを特徴とする。
【００１３】
請求項６にかかる発明の模擬システムは、請求項５に記載の模擬システムにおいて、前記論理回路の構成データに前記論理回路の再構成単位ごとに付与された識別子をインデックスとして前記実行時割当メモリのアドレスを検索する参照テーブルを具備し、模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際に、該論理回路の実行状態を格納するメモリ領域は前記実行時割当メモリに割り当てられ、該論理回路の構成データを格納するメモリ領域は前記識別子をインデックスとして前記参照テーブルから検索した前記実行時割当メモリのアドレスのメモリ領域と共有されるようにしたことを特徴とする。
【００１４】
請求項７にかかる発明の模擬システムは、請求項５に記載の模擬システムにおいて、前記論理回路の構成データをハッシュ関数により計算し得られた要約値をインデックスとして前記実行時割当メモリのアドレスを検索するハッシュテーブルを具備し、模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際に、該論理回路の実行状態を格納するメモリ領域は前記実行時割当メモリに割り当てられ、該論理回路の構成データを格納するメモリ領域は前記要約値により前記ハッシュテーブルで検索した前記実行時割当メモリのアドレスの中のデータが一致する構成データのメモリ領域と共有されるようにしたことを特徴とする。
【００１５】
請求項８にかかる発明の模擬システムは、請求項５に記載の模擬システムにおいて、請求項６に記載の参照テーブルと請求項７に記載のハッシュテーブルとを具備し、模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際に、該論理回路の実行状態を格納するメモリ領域は前記実行時割当メモリに割り当てられ、前記論理回路の構成データを格納するメモリ領域は、請求項６に記載の識別子が付与されているときは前記識別子をインデックスとして前記参照テーブルから検索した前記実行時割当メモリのアドレスのメモリ領域と共有され、前記識別子が付与されていないときは前記要約値により前記ハッシュテーブルで検索した前記実行時割当メモリのアドレスの中のデータが一致する構成データのメモリ領域と共有されるようにしたことを特徴とする。
【発明の効果】
【００１６】
請求項１及び５にかかる発明によれば、動的再構成可能ハードウェアの動作を模擬する際に、論理回路の構成データ及び実行状態を保持するために使用するメモリ領域を、模擬対象ハードウェアで論理回路が書き込まれている領域相当分に限定できる。
【００１７】
請求項２及び６にかかる発明によれば、模擬実行前に構成や機能が決まっていて実行中に変化しない論理回路について、その構成データを保持するために使用するメモリ領域を論理回路の再構成単位ごとに共有でき、論理回路の同一の再構成単位が多数複製して書き込まれる場合に、構成データの保持に必要なメモリ量を複製の数によらず一定に抑えることができる。
【００１８】
請求項３および７にかかる発明によれば、模擬実行中に生じた論理回路についても、その構成データを保持するために使用するメモリ領域を論理回路の再構成単位ごとに共有することが可能になる。つまり論理回路の構成データ自体が操作の対象となるような模擬（請求項２及び６にかかる発明でカバーできない模擬）に対しても、論理回路の同一の再構成単位が多数複製して書き込まれる場合に、構成データの保持に必要なメモリ量を複製の数によらず一定に抑えることができる。
【００１９】
請求項４及び８にかかる発明によれば、請求項２及び６にかかる発明と請求項３及び７にかかる発明の欠点を相互に補完することができ、模擬実行前に構成や機能が決まっていて実行中に変化しない論理回路と、構成データが操作の対象になるような論理回路の両方について、構成データの共有化が計れ、なおかつ通常の応用で多いと考えられる前者の場合については、ハッシュ関数による要約値の計算や、構成データの中身（データ）の比較といったオーバヘッドを避けることができる。
【００２０】
また、汎用コンピュータ上で請求項１〜８にかかる発明により動的再構成可能ハードウェアの模擬システムを実装する際には、シミュレータのワーキングセットを小さくできるので、大規模な模擬対象については、物理メモリ不足によるスワップ発生を低減することによる性能向上が期待できる。また、物理メモリに十分収まる規模の模擬対象についても、プロセッサのデータキャッシュのミスヒットを低減したり、仮想メモリのページ情報がチップ上のＴＬＢ（テーブル・ルックアサイド・バッファ）になく主記憶アクセスを生じさせるＴＬＢミスを低減することによる性能向上が期待できる。
【００２１】
また、請求項２〜４，６〜８にかかる発明により、動的再構成可能ハードウェアを模擬するにあたって、実行時に書き込まれる論理回路の同定が容易になる。これにより、論理回路のシンボル情報（端子名、ゲート名、ネット名など）やブレークポイントなどのデバッグ情報を論理回路の種類ごとに共有したり、論理回路のコンパイルコードなど実行を高速化するための付加的なコードやデータを共有することが容易になる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施例１〜実施例４を詳しく説明する。
【実施例１】
【００２３】
図１に動的再構成可能ハードウェアの実施例１の模擬システム（装置）のメモリ使用例を示す。実施例１の模擬システムは、模擬対象ハードウェアの状態を記憶するために、主状態保持メモリ１００に加えて実行時割当メモリ２００を利用する。
【００２４】
主状態保持メモリ１００は、模擬対象ハードウェアの状態のうち、固定的な機能を再現するための固定機能の状態格納部分１３０と実行時割当メモリ２００のメモリ領域（２１１〜２１４等）のアドレスを保持する格納アドレス部分１４０とをもつ再構成単位１１０（ハードウエアの再構成単位に相当）を有し、それらの状態格納部分１３０と格納アドレス部分１４０は模擬実行前に静的に割り当てられる。
【００２５】
一方、実行時割当メモリ２００は、実行時に書き込まれた論理回路の構成データ及び実行状態を保持するもので、模擬実行の進行に応じて動的に割り当てられる。図１ではメモリ領域２１１〜２１４を論理回路の構成データ及び実行状態を格納するために使用中の領域とし、他は未使用領域２９０となっている。なおここで、「論理回路の実行状態」とは、論理回路の構成要素であるゲートの入力信号や出力信号の論理値、ラッチやＦＦ（フリップフロップ）などの記憶要素の保持する値を指す。
【００２６】
主状態保持メモリ１００の格納アドレス部分１４０は、上記のように再構成可能ハードウェアの再構成単位ごとに割り当てられるが、再構成単位の構成は、模擬対象とする再構成可能ハードウェアのアーキテクチャによって異なる。しかし一般的には模擬対象ハードウェアの物理的あるいは論理的な広がりに対して、位置情報から状態の格納アドレスが効率的に計算できるよう、主状態保持メモリ１００上で例えば配列などの形態で割り付けられる。
【００２７】
初期化時や回路クリア後などように有効な回路が書き込まれていない状態では、主状態保持メモリ１００のアドレス保持部分１４０には、回路が未割付けであることを示す値ＮＵＬＬが格納される。固定的な機能を再現するための状態格納部分１３０について、図１では再構成単位１１０ごとに分割して管理するイメージで示しているが、必ずしも再構成単位１１０ごとに分割されている必要はない。一方、前述のＰＣＡの場合には、再構成能力を提供する機能が論理回路を保持する可変的な部分と対になって、物理的にセルアレイ構造に展開されるので、図１のように固定的な機能の状態格納部分１３０も再構成可能単位１１０に関連して分割すると実装上効率がよい。
【００２８】
上記のようなメモリ構成において、動的再構成可能ハードウェアの動作を模擬する際、固定的な機能については、主状態保持メモリ１００上の固定機能の状態格納部分１３０を参照しながら模擬を行う。そして、模擬実行の過程で新たな論理回路がハードウェア上に書き込まれる場合には、実行時割当メモリ２００の未使用のメモリ領域２９０に、その論理回路の構成データ及び実行状態を保存するのに必要なメモリ領域（２１１〜２１４等）を割り当て、そのメモリ領域のアドレス（ａ１〜ａ４等）をその論理回路の再構成単位ごとに主状態保持メモリ１００の書込部分１２０（その論理回路に対応する書込部分）内の格納アドレス部分１４０に格納する。そして、その論理回路の構成データを、実行時割当メモリ２００の割り当てたメモリ領域（２１１〜２１４等）に書き込み、その実行状態を初期化してその論理回路の模擬を開始する。
【００２９】
模擬実行の過程で、論理回路が上書きされる場合には、実行時割当メモリ２００上の構成データ及び実行状態を格納するメモリ領域（２１１〜２１４等）の内容を単に書き換えればよい（ただし構成データのサイズが変わる場合、再割当が必要）。一方、論理回路がクリアされる場合には、その構成データ及び実行状態を格納するメモリ領域（２１１〜２１４等）は、再利用できるように開放し、主状態保持メモリ１００の対応するアドレス格納部１４０にはＮＵＬＬをセットする。
【００３０】
なお、通常の静的なハードウェアの模擬システムでは、論理回路の構成は実行前に分かっていて変化しないので、実行時割当メモリ２００上における論理回路の構成データ及び実行状態を保持するメモリ領域は予め決めて固定的に割り付けてしまえば良く、そのメモリ領域を模擬動作に合せて動的に管理する必要性はない。
【００３１】
図２に実施例１による模擬システムをイベント駆動方式に基づいて構成した場合の構成例を示す。この場合、模擬システムは、前述の主状態保持メモリ１００、実行時割当メモリ２００に加えて、模擬対象ハードウェア上の状態の変化をイベントとして管理するイベント管理部５００、模擬対象ハードウェアの振る舞いを再現する模擬実行部６００、各メモリを管理するメモリ管理部７００から主に構成される。模擬システムが汎用コンピュータの上で実装される場合には、模擬実行部６００はプログラムであり、イベント管理部５００、主状態保持メモリ１００、実行時割当メモリ２００はそのデータである。メモリ管理部７００は、これらデータを保持するメモリを管理する機能を提供し、イベント管理部５００や主状態保持メモリ１００を実行前に静的に割り付けるとともに、実行時割当メモリ２００に模擬実行時に必要となるメモリ領域を割り当て、あるいはその割り当てたメモリ領域を開放する。
【００３２】
イベント５０１は、それが発生した場所を示す「位置」情報、「種別」情報、イベントの内容である「データ」を持つ。通常、イベント５０１はそれが生じる時刻に対応するタイムスロット５１０ごとに分けてイベント管理部５００で管理される。同一時刻に発生するイベント５０１は、そのタイムスロット５１０上で、例えばキュー５０２の構造で管理される。
【００３３】
この場合、イベント管理部５００は、このキュー５０２を保持するポインタの集まり（例えば配列）であるが、模擬実行にともなって、過去のタイムスロットは未来のタイムスロットとして再利用され、現在時刻のタイムスロットは循環するので、概念的にタイムホイール５２０と呼ばれる。
【００３４】
模擬実行部６００は、イベントを分配するイベントディスパッチャ６１０、ハードウェアの挙動を与える回路動作模擬部６２０、再構成機構模擬部６３０、人出力機構模擬部６４０などからなる。
【００３５】
動的再構成可能ハードウェアの模擬実行では、通常のイベント駆動方式と同じく、タイムホイール５２０から現在の時刻のイベントを１つずつ取得し、それをイベントディスパッチャ６１０に渡す。イベントディスパッチャ６１０は、イベントの種別を参照して、対応する模擬部６２０〜６４０のいずれかにイベントを渡す。模擬部６２０〜６４０の対応するものはイベントを処理しつつ、模擬の結果として新たなイベントを引き起こす場合には、タイムホイール５２０上の対応する未来のタイムスロット５１０のイベントキュー５０２に新たなイベント５０１を登録する。
【００３６】
例えば、論理回路の計算を行う模擬イベントの場合は、回路動作模擬部６２０が、主状態保持メモリ１００と、そこから参照される実行割当メモリ２００上の、論理回路の構成データ及び実行状態を参照し、必要に応じて実行状態を書き換える。
【００３７】
入力動作の模擬イベントの場合は、人出力機構模擬部６４０が、入力データを模擬システムに取り込んで、主状態保持メモリ１００などに保持される模擬対象ハードウェアの状態を書き換える。出力動作の模擬イベントの場合は、入出力機構模擬部６４０は、主状態保持メモリ１００などを参照しつつ、出力データを模擬システムから外部に出力する。
【００３８】
再構成動作の模擬イベントの場合は、再構成機構模擬部６３０が、主状態保持メモリ１００を参照し、必要に応じて更新する。もしそれが、実行時割当メモリ２００の未割当のメモリ領域に対して論理回路を書き込む動作であった場合には、メモリ管理部７００を通じて、実行時割当メモリ２００に新たに構成データ及び実行状態を格納するメモリ領域を割り当て、主状態保持メモリ１００の格納アドレス部分１４０にその割り当てたメモリ領域のアドレスを格納する。もしそれが、論理回路をクリアする動作であった場合には、メモリ管理部７００を通じて、実行時割当メモリ２００上で割り当てられている論理回路の構成データ及び実行状態を格納したメモリ領域を開放し、主状態保持メモリ１００上の対応する格納アドレス部分１４０にＮＵＬＬを設定する。
【００３９】
このようにして、現在時刻のタイムスロット５１０から全てのイベント５０１を消化し終わったら、システムは、現在時刻を１つ進めて次のタイムスロットを処理する。これを繰り返すことにより動的再構成可能ハードウェアの動作が模擬される。
【実施例２】
【００４０】
図３に論理回路の構成データに一意の識別子（ＵＩＤ）を付与する例を示す。Ａ，Ｂは論理回路である。この論理回路Ａ，Ｂは、概念的にはゲートなどの基本演算要素とそれらを接続するネットの集合体であるが、再構成可能ハードウェア上では、論理回路の構成や機能を決める記憶素子に格納するバイナリデータとして扱われる。このバイナリデータが論理回路の構成データ２である。再構成可能ハードウェアが全体を一括して書き換えるのではなく、部分ごとの書き換えを許す場合、論理回路Ａは例えば回路Ａｌ、Ａ２のように再構成単位ごとに分割される。図３では論理回路Ａの再構成単位回路Ａ１，Ａ２に対応する構成データ２を２−Ａｌ、２−Ａ２、論理回路Ｂの再構成単位回路Ｂ１，Ｂ２に対応する構成データ２を２−Ｂｌ、２−Ｂ２と表している。
【００４１】
再構成可能ハードウェア上の論理回路の構成と機能は、一般に多容量のデータによって与えられる。このように構成データが多数のデータ語からなる場合、２つの構成データが同一であるか比較するのは効率が悪い。そこで、模擬対象ハードウェアに書き込むことが予め分かっている論理回路については、構成データ２のそれぞれに一意の識別子３を付加しておく。このようにすれば、模擬システム上で、論理回路を同定する必要が生じた時に、構成データの全比較を行わずに識別子３により効率的に同定できる。識別子３は、例えば模擬システム内で重複しない整数値である。異なる論理回路の構成データの一致検出が目的でなければ、図３のように単にシリアルに番号（＃００１〜＃００４等）を付加するだけで良い。
【００４２】
識別子３は、再構成可能ハードウェア上で同一の論理回路が複数書き込まれるような応用を模擬する際に、構成データを効率的に共有するのに用いることができる。このような構成データの共有を行う実施例２の模擬システムのメモリの利用法を図４に示す。
【００４３】
この実施例２では、動的再構成可能ハードウェアの主状態保持メモリ１００と実行時割当メモリ２００に加えて、構成データの参照テーブル３００を利用する。実施例１の図２のメモリ利用法と同様、論理回路の構成データ及び実行状態を格納するメモリ領域は、実行時割当メモリ２００に必要に応じて割り当てる。主状態保持メモリ１００の再構成単位１１０は、固定的な機能の状態格納部分１３０と実行状態の格納アドレス部分１４０’の他に、識別子の保持部分１５０を持つ。
【００４４】
そして論理回路を模擬対象ハードウエア上に書き込む動作を模擬する際に、その論理回路の実行状態を格納するメモリ領域（２３１〜２３６等）を実行時割当メモリ２００に論理回路の再構成単位ごとに個別に割り当ててそのアドレス（ａ５〜ａ１０等）をアドレス保持部分１４０’に保持させる。一方、その論理回路の構成データの格納アドレスについては、書き込む論理回路の構成データに付随する識別子３を識別子保持部分１５０に保持しこれをインデックスとして構成データ参照テーブル３００を検索する。その参照テーブル３００に識別子３に対応するアドレスが既に登録されていればそれを用いることで構成データを格納するメモリ領域（２２１〜２２４等）の共有を計る。アドレスがまだ登録されていない場合には、新たに構成データを格納するメモリ領域（２２１〜２２４等）を実行時割当メモリ２００に割り当てて、そこに構成データを格納し、そのメモリ領域のアドレス（ａ１〜ａ４等）を構成データ参照テーブル３００の識別子で指定されるエントリに登録する。
【００４５】
なお、論理回路の実行状態を格納するメモリ領域（２３１〜２３６等）は論理回路のインスタンス毎に割り当てられるので、識別子３は主状態保持メモリ１００上ではなく、実行時割当メモリ２００の実行状態を格納するメモリ領域（２３１〜２３６等）に置いて、参照テーブル３００を検索するようにしても良い。また構成データを格納するメモリ領域（２２１〜２２４等）は、論理回路がクリアされたり別の論理回路で上書きされ、模擬対象ハードウェア上に存在しなくなれば開放できる。これは構成データを格納するメモリ領域（２２１〜２２４等）に参照カウンタを持たせて参照元の数を管理し、参照カウンタの値が０になった契機でメモリ開放と構成データ参照テーブル３００からの格納アドレスの登録解除を行うことで、効率的に実装できる。
【００４６】
実施例２の模擬システムをイベント駆動方式に基づいて構成する場合には、イベント処理は基本的に図２と同様の構成で行える。ただし、メモリ１００，２００は上述の図４の説明のように割り付けて管理し、模擬実行部６００の入出力機構模擬部６４０と再構成機構模擬部６３０は、論理回路の構成データを入力したり移動する動作を模擬する際に識別子３を伴わせる。そして前処理として、論理回路を構成データに変換する際に識別子３を発行して各構成データに付与する。
【実施例３】
【００４７】
上記実施例２の方法ではただし、再構成可能ハードウェアシステム上で、構成データが別の論理回路によって加工される場合、あるいは論理回路が変化する場合には対応できない。構成データが加工される例としては、例えば構成データを別の論理回路によって圧縮する場合などが挙げられる。また、論理回路が変化する例としては、例えば進化可能型ハードウェアを実行する場合などが挙げられる。そこで、実施例３では、ハッシュテーブルを使用する。
【００４８】
図５に、ハッシュ関数により論理回路の構成データから要約値（もしくはハッシュ値）を計算する概念を示す。ハッシュ関数とは、入力データの集合に対し、その出力値がなるべく一様に散らばるような性質を持つ関数である。論理回路の構成データ２はバイナリデータであるから、例えばＣＲＣ(Cyclic Redundancy Check)のように、要約値５を計算する計算機能部４が実装できる。ハッシュ関数には、加算法、乗算法、除算法、回転法、ＣＲＣ、・・・など様々な計算法がある。具体的な計算法は、構成データ２のパターンの性質に従って、再構成可能ハードウェアの論理回路の再構成単位ごとに要約値５が一様になるよう選べばよく、ここでは問題にしない。要約値５は、構成データ２と一意に対応するとは限らず、図５のＨ（Ａ２）とＨ（Ｂ２）のように、異なる再構成単位回路Ａ２，Ｂ２の構成データに対して同じ値（＃２９１）が導かれる可能性がある。しかしこれを用いれば、構成データを同定する際に中身（データ）を比較する構成データの候補を絞ることができる。
【００４９】
図６に、再構成可能ハードウェア上で同一の論理回路が複数書き込まれるような応用を模擬する際に、構成データのメモリ領域を共有する手段として上記した要約値５を用いる実施例３のメモリ利用の例を示す。この例では、模擬対象としての再構成可能ハードウェアの主状態保持メモリ１００と実行時割当メモリ２００に加えて、構成データのハッシュテーブル４００を利用する。実施例２の図４のメモリ利用法と同様、論理回路の構成データ及び実行状態を格納するメモリ領域は、実行時割当メモリ２００に必要に応じて割り当てるが、論理回路の実行状態は個別にメモリ領域（２３１〜２３６等）を割り当てそのアドレス（ａ５〜ａ１０等）をアドレス保持部分１４０に保存する一方、構成データはその種類ごとにメモリ領域（２１１〜２２４等）を共有する。
【００５０】
主状態保持メモリ１００の各再構成単位１１０は、固定的な機能の状態格納部分１３０と構成データ及び実行状態の格納アドレス部分１４０を持つ。論理回路の実行状態は格納アドレス部分１４０から直接参照する。一方、論理回路の構成データは、初回のみハッシュテーブル４００を用いて格納アドレス（ａ１〜ａ４等）を探索し、以降の参照では格納アドレス部分１４０から直接参照する。
【００５１】
具体的には、論理回路を模擬対象ハードウェア上に書き込む動作を模擬する際に、実行状態を格納するメモリ領域を実行時割当メモリ２００上に再構成単位ごとに個別に割り当てる。一方、構成データの格納アドレスについては、書き込む構成データから要約値５を計算して求め、それをインデックスとしてハッシュテーブル４００を検索して格納アドレスを得る。そして書き込む構成データと同じ要約値をもつ登録済みの構成データの中身（データ）を比較する。もし一致するものがなければ、新たに構成データを格納するメモリ領域を実行時割当メモリ２００に割り当ててそこに構成データを格納し、そのアドレス（ａ１〜ａ４等）をハッシュテーブル４００の要約値で指定されるエントリに登録する。中身（データ）が一致するものがあれば、その格納アドレスを単に格納アドレス部分１４０に設定して、以後それを参照する。同じ要約値を持つ構成データの数が多いと構成データの比較コストは高くつく。従って比較コストを抑えるにはハッシュ関数の一様性が重要となる。
【００５２】
一般に、複数の異なる構成データが同じ要約値をもちうるので、ハッシュテーブル４００は要約値が衝突しても問題ないように設計する。図６では、単に複数の構成データの格納アドレスが登録できるよう十分な数のエントリを設けているだけだが、開アドレス法や連鎖法といった広く用いられているハッシュテーブルの衝突時の対処法が採用できる。また、構成データの数の変化に応じてハッシュ関数を動的に変化させる動的ハッシュ法の適用も可能である。逆に、再構成される論理回路が模擬実行前に予め分かっているのであれば、要約値の衝突が全く起こらない完全ハッシュ関数を構成できる。従ってこの場合、前処理として完全ハッシュ関数を生成し、それをハッシュテーブル４００の参照・登録に用いれば、構成データを中身（データ）の比較なしに同定することが可能になる。ただしこの場合、構成データの比較だけでなく要約値の計算も不要な前記実施例２が適用できる。
【００５３】
なお、実施例２と同様に、実行状態を格納するメモリ領域（２３１〜２３６等）は論理回路のインスタンス毎に割当られるので、構成データの格納アドレスは、検索後、主状態保持メモリ１００上ではなく、実行状態を格納するメモリ領域（２３１〜２３６等）に置いても良い。構成データを格納するメモリ領域についても、構成データを格納するメモリ領域に参照カウンタと要約値を持たせて管理することで、論理回路がクリアされたり別の回路で上書きされ、元の構成データのインスタンス数が０になり保持する必要がなくなったときに、効率的にそのメモリ領域を開放し、ハッシュテーブル４００から格納アドレスの登録を解除するようにできる。
【００５４】
実施例３の模擬システムをイベント駆動方式に基づいて構成する場合には、イベント処理は基本的に図２と同様の構成で行なえる。ただし、メモリ１００，２００は上述の図６の説明のように構成する。
【実施例４】
【００５５】
図７に、実施例２と実施例３を組み合わせた実施例４のメモリ利用の例を示す。この実施例４は、模擬する再構成可能ハードウェアの主状態保持メモリ１００と実行時割当メモリ２００に加えて、構成データのメモリ領域の共有化のために、実施例２の参照テーブル３００と実施例３のハッシュテーブル４００を併用する。実施例２、実施例３と同様、論理回路の構成データ及び実行状態を格納するメモリ領域は、実行時割当メモリ２００に必要に応じて割り当てるが、論理回路の実行状態は再構成単位ごとに個別にメモリ領域（２３１〜２３６等）を割り当てて保存する一方、構成データを格納するメモリ領域は中身（データ）が同じものを以下に述べる方法で共有する。主状態保持メモリ１００の各再構成単位１１０は、固定的な機能の状態格納部分１３０と構成データ及び実行状態の格納アドレス部分１４０の他に、構成データの識別子の保持部分１５０を持つ。
【００５６】
模擬対象ハードウェア上に論理回路を書き込む動作を模擬する際に、その論理回路の実行状態を格納するメモリ領域（２３１〜２３６等）を実行時割当メモリ２００上に再構成単位ごとに個別に割り当てる一方、その論理回路の構成データの格納アドレスについては、もし有効な識別子が構成データに伴っていれば、それをインデックスとして構成データ参照テーブル３００を検索して得る。実施例２と同様に、アドレスが既に登録されていればそれを用いることで構成データのメモリ領域の共有を計り、アドレスがまだ登録されていない場合には、新たに構成データを格納するメモリ領域を実行時割当メモリ２００に割り当てて、そこに構成データを格納し、そのアドレスを参照テーブル３００の識別子で指定されるエントリに登録する。
【００５７】
書き込む論理回路の構成データが有効な識別子を伴わない場合には、実施例３の要領に従い、要約値を計算して、それをインデックスとしてハッシュテーブル４００を検索して格納アドレスを得る。そして書き込む論理回路の構成データと同じ要約値をもつ登録済みの構成データの中身（データ）を比較する。もし一致するものがなければ、その構成データを格納するメモリ領域を実行時割当メモリ２００に新たに割り当てて、そこに構成データを格納し、そのアドレスをハッシュテーブル４００の要約値で指定されるエントリに登録する。以後の参照のために、構成データの格納アドレスと実行状態の格納アドレスは書き込んだ場所に対応する格納アドレス部分１４０に設定する。
【００５８】
図７では、論理回路Ａと論理回路Ｂが有効な識別子を伴い、論理回路Ａ’が論理回路Ａと構成は同じであるが、模擬対象の再構成可能ハードウェア上で構成データ自体が操作の対象となり、有効な識別子を失った例である。この場合、論理回路Ａと論理回路Ｂは、有効な識別子を利用して構成データ参照テーブル３００にその構成データの格納アドレス（ａ１〜ａ４等）を登録することにより、そのメモリ領域（２１１〜２２４等）が共有可能な状態になる。一方、論理回路Ａ’については、その構成データの格納アドレス（ａ５，ａ６等）はハッシュテーブル４００に登録され、そのメモリ領域（２２５〜２２６等）が共有可能な状態になる。
【００５９】
なお実施例２と同様に、実行状態を格納するメモリ領域（２３１〜２３６等）は論理回路のインスタンス毎に割当られるので、構成データの識別子や格納アドレスは主状態保持メモリ１００上ではなく、実行状態を格納するメモリ領域（２３１〜２３６等）に置いても良い。構成データを格納するメモリ領域（２２１〜２２６等）の開放方法についても、構成データを格納するメモリ領域（２２１〜２２６等）に参照カウンタと要約値（ハッシュを使っている場合）を持たせて管理すれば、論理回路がクリアされたり別の回路で上書きされ、元の構成データのインスタンス数が０になったときに、効率的にそのメモリ領域を開放し、参照テーブル３００もしくはハッシュテーブル４００から格納アドレスの登録を解除するようにできる。
【００６０】
実施例４の模擬システムをイベント駆動方式に基づいて構成する場合には、実施例２や実施例３と同様、イベント処理は基本的に図２と同様の構成で行なえる。ただし、メモリ１００，２００は上述の図７の説明のように割り付けて管理し、実施例２に従って、模擬実行部６００の入出力機構模擬部６４０と再構成機構模擬部６３０は、構成データを入力したり移動する動作を模擬する際に識別子を伴わせる。そして前処理として、論理回路を構成データに変換する際に識別子を発行して各構成データに付与する。
【図面の簡単な説明】
【００６１】
【図１】実施例１の模擬システムのメモリ使用法の説明図である。
【図２】実施例１の模擬システムの構成図である。
【図３】論理回路の構成データに一意の識別番号を付与する説明図である。
【図４】実施例２の模擬システムのメモリ使用法の説明図である。
【図５】ハッシュ関数により構成データの要約値を計算する説明図である。
【図６】実施例３の模擬システムのメモリ使用法の説明図である。
【図７】実施例４の模擬システムのメモリ使用法の説明図である。
【符号の説明】
【００６２】
Ａ，Ｂ：論理回路
２：論理回路の構成データ
３：論理回路の構成データの一意の識別子（ＵＩＤ）
４：要約値の計算機能部
５：論理回路の構成データの要約値
１００：動的再構成可能ハードウエアの主状態保持メモリ
１１０：論理回路の再構成単位
１２０：論理回路の書込部分
１３０：論理回路の固定機能の状態格納部分
１４０：論理回路の構成データ及び実行状態の格納アドレス部分
１４０’：論理回路の実行状態の格納アドレス部分
１５０：論理回路の構成データの一意の識別子の保持部分
２００：実行時割当メモリ
２１１〜２１４：論理回路の構成データ及び実行状態を格納するメモリ領域
２２１〜２２６：論理回路の構成データを格納するメモリ領域
２３１〜２３６：論理回路の実行状態を格納するメモリ領域
２９０：未使用領域
３００：構成データの参照テーブル
４００：構成データのハッシュテーブル
５００：イベント管理部
５０１：イベント
５０２：イベントキュー
５１０：タイムスロット
５２０：タイムホイール
６００：模擬実行部
６１０：イベントディスパッチャ
６２０：回路動作模擬部
６３０：再構成機構模擬部
６４０：入出力機構模擬部
７００：メモリ管理部
【図１】
2005056038.tif 000003
【図２】
2005056038.tif 000004
【図３】
2005056038.tif 000005
【図４】
2005056038.tif 000006
【図５】
2005056038.tif 000007
【図６】
2005056038.tif 000008
【図７】
2005056038.tif 000009