(57)【要約】  プログラムの限界実行時間の解析を正確に行うことを課題とする。最悪実行時間または最良実行時間である限界実行時間の解析をプログラムＰに対して行う限界実行時間解析システム（１００）において、経路実行時間算出部（１２０）は、プログラムを構成する複数のブロックであって、各ブロックが、１つ以上の命令を有し、入口が先頭の命令のみであり、出口が末尾の命令のみである複数のブロック間の制御関係に応じて確定されるプログラムのとり得る実行経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、プログラムが該実行経路で実行された場合の実行時間である経路実行時間を算出する。限界実行時間出力部（１４０）は、経路実行時間算出部（１２０）により算出した各経路実行時間のうちの最大値または最小値を限界実行時間として出力する。
2013128519.tif 000002
【特許請求の範囲】
【請求項１】
最悪実行時間または最良実行時間である限界実行時間の解析をプログラムに対して行う限界実行時間解析装置であって、
前記プログラムを構成する複数のブロックであって、各前記ブロックが、１つ以上の命令を有し、入口が先頭の命令のみであり、出口が末尾の命令のみである前記複数のブロック間の制御関係に応じて確定される前記プログラムのとり得る実行経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、前記プログラムが該実行経路で実行された場合の実行時間である経路実行時間を算出する経路実行時間算出手段と、
前記経路実行時間算出手段により算出した各前記経路実行時間のうちの最大値または最小値を前記限界実行時間として出力する限界実行時間出力手段とを備えることを特徴とする限界実行時間解析装置。
【請求項２】
前記複数のブロックの夫々に対して設定された、該ブロックに含まれる命令列から想定される該ブロックの最長の実行時間または最短の実行時間であるブロック限界実行時間に基づいて、前記プログラムのとり得る実行経路毎に、該実行経路に含まれる全てのブロックの前記ブロック限界実行時間の総和である概略実行時間を求める概略実行時間算出手段をさらに備え、
前記経路実行時間算出手段は、
前記プログラムのとり得る実行経路のうちの、前記概略実行時間算出手段が算出した前記概略実行時間の大きい順または小さい順における上位の所定数または所定の割合に該当する数の実行経路についてのみ前記経路実行時間を算出し、
または、前記概略実行時間算出手段が算出した最も大きい前記概略実行時間または最も小さい前記概略実行時間に対応する実行経路から前記経路実行時間の算出を行い、所定の時間が経過したときに前記経路実行時間の算出を打ち切り、
または、前記限界実行時間として最悪実行時間を解析する場合であって、既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、既に算出した前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも小さいときに、前記経路実行時間の算出を打ち切ることを特徴とする請求項１に記載の限界実行時間解析装置。
【請求項３】
前記概略実行時間算出手段は、
前記経路実行時間算出手段により前記経路実行時間の算出がまだ行われていない実行経路のうちの、前記概略実行時間が最大または最小となり得る実行経路の１つを候補経路として検索して前記経路時間算出手段に通知する処理を繰り返し、
前記経路実行時間算出手段は、
前記概略実行時間算出手段から前記候補経路が通知される度に該候補経路の前記経路実行時間を算出し、
前記概略実行時間算出手段は、
前記経路実行時間算出手段に通知した前記後候補経路の総数が前記所定数または前記所定の割合に該当する数に到達したとき、
または、前記経路実行時間算出手段に１つ目の前記候補経路を通知してから前記所定の時間が経過したとき、
または、前記限界実行時間として最悪実行時間を解析する場合であって、前記経路実行時間算出手段により既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、前記経路実行時間算出手段により既に算出した各前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より小さいときに、
前記候補経路の検索及び前記経路実行時間算出手段への前記候補経路の通知を打ち切ることを特徴とする請求項２に記載の限界実行時間解析装置。
【請求項４】
最悪実行時間または最良実行時間である限界実行時間の解析をプログラムに対して行う限界実行時間解析方法において、
前記プログラムを構成する複数のブロックであって、各前記ブロックが、１つ以上の命令を有し、入口が先頭の命令のみであり、出口が末尾の命令のみである前記複数のブロック間の制御関係に応じて確定される前記プログラムのとり得る実行経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、前記プログラムが該実行経路で実行された場合の実行時間である経路実行時間を算出する経路実行時間算出処理と、
前記経路実行時間算出処理により算出した各前記経路実行時間のうちの最大値または最小値を前記限界実行時間として出力する処理とを有することを特徴とする限界実行時間解析方法。
【請求項５】
前記複数のブロックの夫々に対して設定された、該ブロックに含まれる命令列から想定される該ブロックの最長の実行時間または最短の実行時間であるブロック限界実行時間に基づいて、前記プログラムのとり得る実行経路毎に、該実行経路に含まれる全てのブロックの前記ブロック限界実行時間の総和である概略実行時間を求める概略実行時間算出処理をさらに有し、
前記経路実行時間算出処理は、
前記プログラムのとり得る実行経路のうちの、前記概略実行時間算出処理により算出した前記概略実行時間の大きい順または小さい順における上位の所定数または所定の割合に該当する数の実行経路についてのみ前記経路実行時間を算出し、
または、前記概略実行時間算出処理により算出した最も大きい前記概略実行時間または最も小さい前記概略実行時間に対応する実行経路から前記経路実行時間の算出を行い、所定の時間が経過したときに前記経路実行時間の算出を打ち切り、
または、前記限界実行時間として最悪実行時間を解析する場合であって、既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、既に算出した前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも小さいときに、前記経路実行時間の算出を打ち切ることを特徴とする請求項４に記載の限界実行時間解析方法。
【請求項６】
前記概略実行時間算出処理は、
前記経路実行時間算出処理により前記経路実行時間の算出がまだ行われていない実行経路のうちの、前記概略実行時間が最大または最小となり得る実行経路の１つを候補経路として検索して前記経路時間算出処理に通知する処理を繰り返し、
前記経路実行時間算出処理は、
前記概略実行時間算出処理から前記候補経路が通知される度に該候補経路の前記経路実行時間を算出し、
前記概略実行時間算出処理は、
前記経路実行時間算出処理に通知した前記後候補経路の総数が前記所定数または前記所定の割合に該当する数に到達したとき、
または、前記経路実行時間算出処理に１つ目の前記候補経路を通知してから前記所定の時間が経過したとき、
または、前記限界実行時間として最悪実行時間を解析する場合であって、前記経路実行時間算出処理により既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、前記経路実行時間算出処理により既に算出した各前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より小さいときに、
前記候補経路の検索及び前記経路実行時間算出処理への前記候補経路の通知を打ち切ることを特徴とする請求項５に記載の限界実行時間解析方法。
【請求項７】
解析対象プログラムの最悪実行時間または最良実行時間である限界実行時間の解析処理をコンピュータに実行せしめるプログラムを格納した非一時的なコンピュータ可読媒体であって、
前記解析処理は、
前記プログラムを構成する複数のブロックであって、各前記ブロックが、１つ以上の命令を有し、入口が先頭の命令のみであり、出口が末尾の命令のみである前記複数のブロック間の制御関係に応じて確定される前記プログラムのとり得る実行経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、前記プログラムが該実行経路で実行された場合の実行時間である経路実行時間を算出する経路実行時間算出処理と、
前記経路実行時間算出処理により算出した各前記経路実行時間のうちの最大値または最小値を前記限界実行時間として出力する処理とを有することを特徴とするプログラムを格納した非一時的なコンピュータ可読媒体。
【請求項８】
前記解析処理は、
前記複数のブロックの夫々に対して設定された、該ブロックに含まれる命令列から想定される該ブロックの最長の実行時間または最短の実行時間であるブロック限界実行時間に基づいて、前記プログラムのとり得る実行経路毎に、該実行経路に含まれる全てのブロックの前記ブロック限界実行時間の総和である概略実行時間を求める概略実行時間算出処理をさらに有し、
前記経路実行時間算出処理は、
前記プログラムのとり得る実行経路のうちの、前記概略実行時間算出処理により算出した前記概略実行時間の大きい順または小さい順における上位の所定数または所定の割合に該当する数の実行経路についてのみ前記経路実行時間を算出し、
または、前記概略実行時間算出処理により算出した最も大きい前記概略実行時間または最も小さい前記概略実行時間に対応する実行経路から前記経路実行時間の算出を行い、所定の時間が経過したときに前記経路実行時間の算出を打ち切り、
または、前記限界実行時間として最悪実行時間を解析する場合であって、既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、既に算出した前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも小さいときに、前記経路実行時間の算出を打ち切ることを特徴とする請求項７に記載のプログラムを格納した非一時的なコンピュータ可読媒体。
【請求項９】
前記概略実行時間算出処理は、
前記経路実行時間算出処理により前記経路実行時間の算出がまだ行われていない実行経路のうちの、前記概略実行時間が最大または最小となり得る実行経路の１つを候補経路として検索して前記経路時間算出処理に通知する処理を繰り返し、
前記経路実行時間算出処理は、
前記概略実行時間算出処理から前記候補経路が通知される度に該候補経路の前記経路実行時間を算出し、
前記概略実行時間算出処理は、
前記経路実行時間算出処理に通知した前記後候補経路の総数が前記所定数または前記所定の割合に該当する数に到達したとき、
または、前記経路実行時間算出処理に１つ目の前記候補経路を通知してから前記所定の時間が経過したとき、
または、前記限界実行時間として最悪実行時間を解析する場合であって、前記経路実行時間算出処理により既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、前記経路実行時間算出処理により既に算出した各前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より小さいときに、
前記候補経路の検索及び前記経路実行時間算出処理への前記候補経路の通知を打ち切ることを特徴とする請求項８に記載のプログラムを格納した非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムの最悪実行時間または最良実行時間を解析する技術に関する。
【背景技術】
【０００２】
制御向けの組込システム等のハード・リアルタイムシステムにおいて、プログラムの最悪実行時間または最良実行時間の把握が重要である。最悪実行時間は、ＷＣＥＴ（Ｗｏｒｓｔ  Ｃａｓｅ  Ｅｘｅｃｕｔｉｏｎ  Ｔｉｍｅ）と呼ばれ、該プログラムの実行が最も長くなる場合の実行時間を意味する。最良実行時間は、ＢＣＥＴ（Ｂｅｓｔ  Ｃａｓｅ  Ｅｘｅｃｕｔｉｏｎ  Ｔｉｍｅ）と呼ばれる、該プログラムの実行が最も短くなる場合の実行時間を意味する。以下において、最悪実行時間と最良実行時間をまとめて限界実行時間という。【０００３】
近年のプロセッサでは、処理を高速化するために、キャッシュ、パイプライン、分岐予測、投機実行などの手法が導入されており、プログラムの各命令の実行時間は、プログラムの実行履歴により変化するプロセッサの実行状態によって大きく変化する。そのため、プログラムの限界実行時間の解析がより複雑になっている。【０００４】
プログラムの限界実行時間の把握は、実機またはシミュレーションにより、解析対象のプログラムに様々な入力データを与えて実行させて実行時間を測定する手法（例えば特許文献１〜２）と、プログラムを静的に解析して理論的に求める手法（例えば特許文献３〜４、非特許文献１）に大分される。【０００５】
プログラムの実行時間が、一般的に、プログラムに与える入力データによって変動するため、実行時間を測定する手法では、限界実行時間で動作するような入力データをプログラムに与える必要がある。しかし、このような入力データを特定することは、困難である。【０００６】
そのため、多数の入力データをランダムにプログラムに与えて実行させ、実行時間の長いパターンまたは短いパターンを得ることも考えられるが、この手法では、限界実行時間で動作するような入力データのパターンが抜けてしまう可能性を排除できない。その結果、測定した最長の実行時間が実際の最悪実行時間より短い、または、測定した最短の実行時間が実際の最良実行時間より長いなど、正確な限界実行時間を得ることができない問題が生じてしまう。これでは、限界実行時間を保証する必要のある用途には使用することができない。【０００７】
なお、特許文献２には、プログラムの実行時間（該文献における「実行実測時間」）の測定手法として、該実行実測時間を測定する際に用いられたハードウェア（例えばハードウェアＡ）と、別のハードウェア（例えばハードウェアＢ）との性能差に基づいて、該プログラムをハードウェアＢ上で実行させた場合の実行実測時間を推定するようにしてもよいとの記載がある（「００５５」）。当然ながら、この場合において、推定により得られた、ハードウェアＢにおける実行実測時間がハードウェアＡにおける実行実測時間に依存する。例えば、プログラムの限界実行時間として最長または最短の実行実測時間をハードウェアＡで測定した場合に、上述した入力データのパターンの抜けなどの理由からこの限界実行時間が真の限界実行時間ではない恐れがある。結果として、推定により得られた、ハードウェアＢにおける限界実行時間も、真の限界実行時間ではない可能性も多いにある。【０００８】
非特許文献１に開示された技術を代表にして、プログラムを解析して理論的に限界実行時間を求める手法を説明する。また、説明上の便宜のため、限界実行時間の例として最悪実行時間を用いる。【０００９】
この手法は、まず、プログラムを複数のブロックに分け、各ブロックの最悪実行時間の想定値となる固定値を予め制約条件として定義すると共に、これらのブロック間の制御の遷移関係を示す制御フローグラフ（ＣＦＧ：Ｃｏｎｔｒｏｌ  Ｆｌｏｗ  Ｇｒａｐｈ）を生成する。そして、定義された制約条件及びＣＦＧに基づいて、プログラム全体の最悪実行時間を数値解析により求めている。具体的には、例えば、各ブロックに対して定義された最悪実行時間に基づいて、最悪実行時間の総和が最も長くなるブロックの組合せすなわちプログラムの実行経路を算出すると共に、この実行経路に含まれる各ブロックの最悪実行時間の総和を該プログラムの最悪実行時間として推定する。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００３−２８８２３７号公報
【特許文献２】特開２００３−３０００７号公報
【特許文献３】特開２００５−２４２５６９号公報
【特許文献４】特開２０１１−１３８７４号公報
【非特許文献】
【００１１】
【非特許文献１】Ｗｈｙ  ＡＩ  ＋  ＩＬＰ  Ｉｓ  Ｇｏｏｄ  ｆｏｒ  ＷＣＥＴ,ｂｕｔ  ＭＣ  Ｉｓ  Ｎｏｔ,  Ｎｏｒ  ＩＬＰ  Ａｌｏｎｅ，Ｒｅｉｎｈａｒｄ  ＷｉｌｈｅｌｍＩｎ  Ｖｅｒｉｆｉｃａｔｉｏｎ，Ｍｏｄｅｌ  Ｃｈｅｃｋｉｎｇ  ａｎｄ  Ａｂｓｔｒａｃｔ  Ｉｎｔｅｒｐｒｅｔａｔｉｏｎ(ＶＭＣＡＩ),ＬＮＣＳ  ２９３７，ｐｐ．３０９−３３２，２００４
【発明の概要】
【発明が解決しようとする課題】
【００１２】
ところが、プログラムに含まれるブロックの実行時間は、そのブロックに至る経路の差異によって変動するものである。変動の要因としては、該ブロックに至る経路によって該ブロックに与えられる変数値や、該ブロック内の処理内容や、キャッシュメモリのヒット率などが変動することは挙げられる。【００１３】
そのため、非特許文献１により代表される解析手法は、安全のために、不確定要素に対して常に安全マージンを大きくとって行われる。例えば、プログラムの最悪実行時間を解析する際に、各ブロックの最悪実行時間として、想定される最長の実行時間を定義する。これでは、プログラム全体に対して推定された最悪実行時間は、過大になってしまう恐れがある。同様に、プログラムの最良実行時間に関しては、過小になってしまう恐れがある。
【課題を解決するための手段】
【００１４】
本発明の１つの態様は、最悪実行時間または最良実行時間である限界実行時間の解析をプログラムに対して行う限界実行時間解析方法である。該方法は、経路実行時間算出ステップと、限界実行時間出力ステップを含む。【００１５】
該方法は、経路実行時間算出ステップにおいて、前記プログラムを構成する複数のブロックであって、各前記ブロックが、１つ以上の命令を有し、入口が先頭の命令のみであり、出口が末尾の命令のみである前記複数のブロック間の制御関係に応じて確定される前記プログラムのとり得る実行経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、前記プログラムが該実行経路で実行された場合の実行時間である経路実行時間を算出する。【００１６】
そして、限界実行時間出力ステップにおいて、経路実行時間算出ステップで算出した各前記経路実行時間のうちの最大値または最小値を前記限界実行時間として出力する。【００１７】
なお、上記態様の方法を装置やシステムなどに置き換えて表現したものや、該方法をコンピュータに実行せしめるプログラムなども、本発明の態様としては有効である。
【発明の効果】
【００１８】
本発明にかかる技術によれば、プログラムの限界実行時間を正確に解析することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の第１の実施の形態にかかる限界実行時間解析システムのハードウェア構成を示す図である。
【図２】本発明の第１の実施の形態にかかる限界実行時間解析システムを機能ブロックで示す図である。
【図３】図２に示す限界実行時間解析システムの処理の流れを示すフローチャートである。
【図４】解析対象のプログラムの分割態様の一例を示す図である。
【図５】解析対象のプログラムのとり得る実行経路の一例を示す図である。
【図６】本発明の第２の実施の形態にかかる限界実行時間解析システムを機能ブロックで示す図である。
【図７】図６に示す限界実行時間解析システムの処理の流れを示すフローチャートである。
【図８】解析対象のプログラムの分割態様の一例を示す図である。
【図９】図６に示す限界実行時間解析システムによる図８に示すプログラムの解析の例を説明するための図である。
【図１０】本発明の第３の実施の形態にかかる限界実行時間解析システムを機能ブロックで示す図である。
【図１１】図１０に示す限界実行時間解析システムにおける処理の流れを示すフローチャートである。
【図１２】本発明の第４の実施の形態にかかる限界実行時間解析システムを機能ブロックで示す図である。
【図１３】図１２に示す限界実行時間解析システムにおける処理の流れを示すフローチャートである（その１）。
【図１４】図１２に示す限界実行時間解析システムにおける処理の流れを示すフローチャートである（その２）。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態について説明する。説明の明確化のため、以下の記載及び図面は、適宜、省略、及び簡略化がなされている。また、様々な処理を行う機能ブロックとして図面に記載される各要素は、ハードウェアとソフトウェア（プログラム）の組合せによっていろいろな形で実現できることは当業者には理解されるところであり、ハードウェアとソフトウェアのいずれかに限定されるものではない。なお、各図面において、同一の要素には同一の符号が付されており、必要に応じて重複説明は省略されている。
【００２１】
また、上述したプログラムは、様々なタイプの非一時的なコンピュータ可読媒体（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ  ｃｏｍｐｕｔｅｒ  ｒｅａｄａｂｌｅ  ｍｅｄｉｕｍ）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（ｔａｎｇｉｂｌｅ  ｓｔｏｒａｇｅ  ｍｅｄｉｕｍ）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ  ＰＲＯＭ）、フラッシュＲＯＭ、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（ｔｒａｎｓｉｔｏｒｙ  ｃｏｍｐｕｔｅｒ  ｒｅａｄａｂｌｅ  ｍｅｄｉｕｍ）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００２２】
＜第１の実施の形態＞
図１は、本発明の第１の実施の形態にかかる限界実行時間解析システム１００のハードウェア構成を示す図である。限界実行時間解析システム１００は、例えばコンピュータであり、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０１と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１０２と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１０３と、ハードディスク等の記憶装置１０４とを備え、ＣＰＵ１０１、ＲＡＭ１０２、ＲＯＭ１０３、記憶装置１０４は、バス１０５に接続されている。
【００２３】
ＲＯＭ１０３および記憶装置１０４には、コンピュータを本実施の形態の限界実行時間解析システム１００として機能させるためのプログラムおよび各種データが記憶されている。
【００２４】
ＣＰＵ１０１は、バス１０５を介して、ＲＯＭ１０３および記憶装置１０４に記憶されたプログラムおよび各種データをＲＡＭ１０２に読み込んで実行する。ＲＡＭ１０２は、ＣＰＵ１０１による実行中のプログラムやデータなどを一時的に記憶する。
【００２５】
図２は、図１に示す限界実行時間解析システム１００を機能ブロックで示す図である。これらの機能ブロックは、図１に示す各ハードウェアとソフトウェアの協働により実現される。
【００２６】
図２に示すように、限界実行時間解析システム１００は、解析対象のプログラムＰに対して限界実行時間ＴＭの解析を行うものであり、解析経路実行時間算出部１２０と、限界実行時間出力部１４０を備える。なお、限界実行時間ＴＭは、プログラムＰの最悪実行時間と最良実行時間のいずれか一方または両方である。
【００２７】
図３は、限界実行時間解析システム１００における処理の流れを示すフローチャートである。まず、経路実行時間算出部１２０は、プログラムＰのとり得る実行経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、プログラムＰが当該実行経路で実行された場合の実行時間を算出して限界実行時間出力部１４０に出力する（Ｓ１１０）。経路実行時間算出部１２０が夫々の経路について算出した実行時間（Ｔ１、Ｔ２、・・・）は、経路実行時間という。
【００２８】
限界実行時間出力部１４０は、経路実行時間算出部１２０からの経路実行時間Ｔ１、Ｔ２、・・・から限界実行時間ＴＭを選択して出力する（Ｓ１１０）。具体的には、限界実行時間ＴＭとして最悪実行時間を得る場合には、経路実行時間Ｔ１、Ｔ２、・・・のうちの最大値を選択し、限界実行時間ＴＭとして最良実行時間を得る場合には、経路実行時間Ｔ１、Ｔ２、・・・のうちの最大値を選択し、最悪実行時間と最良実行時間の両方を得る場合には、経路実行時間Ｔ１、Ｔ２、・・・のうちの最大値と最小値の両方を選択する。
【００２９】
プログラムＰは、例えばＣ言語などの高級言語のソースコードや、ソースコードをコンパイルした後の機械語命令もしくは類似の表現などである。
【００３０】
プログラムＰの実行経路は、該プログラムＰを構成する複数のブロックのうちの、該プログラムの実行開始から実行終了までに経由するブロックの組合せを意味する。各ブロックは、１つ以上の命令を有し、かつ、入口が先頭の命令のみであり、出口が末尾の命令のみである。すなわち、各ブロックでは、先頭の命令を除き、他のブロックから該ブロック内の命令に分岐してくることが無く、かつ、末尾の命令を除き、該ブロック内の命令から他のブロックへ分岐することがない。
【００３１】
このようなブロックの一例としては、例えば基本ブロック（Ｂａｓｉｃ  Ｂｌｏｃｋ）が知られている。また、複数の基本ブロックにより構成された大きなブロックや、ループ構造のまとまりなどであってもよい。また、プログラムＰがソースコードとして供される場合においては、上記ブロックとしては、コンパイラにより機械語命令に変換される際に実際には１つも機械語命令が生成されない疑似命令のみから構成されるものであってもよい。
【００３２】
また、プログラムＰをブロックへの分割に関しては、経路実行時間算出部１２０がプログラムＰの構文を解析し、解析結果に応じてプログラムＰを上述した複数のブロックに分割するようにしてもよく、ユーザによりプログラムＰを構成する複数のブロックを示す情報も経路実行時間算出部１２０に指示し、経路実行時間算出部１２０が指示に従ってプログラムＰの複数のブロックを確定するようにしてもよい。なお、ユーザにより指示を与える態様に関しては、例えば、指示内容を示す情報をプログラムＰに付属させるようにしてしてもよく、ユーザにより指示を経路実行時間算出部１２０に直接入力するようにしてもよい。
【００３３】
プログラムＰのとり得る実行経路は、該プログラムＰの複数のブロック間の制御関係に応じて確定できる。プログラムＰのとり得る実行経路について、例えば、経路実行時間算出部１２０がプログラムＰを解析し、それを構成する複数のブロック間の制御関係に応じた制御フローグラフＣＦＧを生成すると共に、生成した制御フローグラフＣＦＧに基づいてプログラムＰのとり得る実行経路を確定する。勿論、制御フローグラフＣＦＧをプログラムＰに付属させて経路実行時間算出部１２０に入力するようにしてもよく、ユーザにより制御フローグラフＣＦＧを経路実行時間算出部１２０に直接入力するようにしてもよい。
【００３４】
図４は、プログラムＰを複数のブロックに分割して得た一例を示す。図示のように、該例において、プログラムＰは、ブロックＡ〜Ｈの８個のブロックに分割されている。
【００３５】
図５は、図４に示す分割態様の場合に、プログラムＰのとり得る実行経路の例を示す。図示のように、この例では、プログラムＰのとり得る実行経路は、４つである。
【００３６】
経路実行時間算出部１２０は、図５に示す４つの経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、プログラムＰの実行時間（経路実行時間）を算出し、限界実行時間出力部１４０は、経路実行時間算出部１２０が算出した４つの経路実行時間のうちの最大値及び／または最小値を選択して出力する。
【００３７】
変数挙動またはハードウェア挙動の解析には、プログラムの数値解析、プロセッサモデルによる簡易シミュレーション等の一般的な手法を用いることが可能である。
【００３８】
このように、図２に示す限界実行時間解析システム１００は、解析対象となるプログラムＰの限界実行時間の解析に際して、該プログラムＰのとり得る経路毎に経路実行時間を算出して、最大の経路実行時間及び／または最小の経路実行時間を限界実行時間として出力する。経路を定義した上で経路実行時間を算出しているので、「該経路を通る場合に変数値はこの範囲にしかならない」などの変数挙動や、該経路でプログラムが実行された場合におけるキャッシュメモリのヒット率はこの範囲になる、プロセッサはこのような動作になる」などのハードウェア挙動を把握することができ、これらの変数挙動及び／またはハードウェア挙動に基づいた実行時間（経路実行時間）を詳細に解析することができる。
【００３９】
従って、限界実行時間解析システム１００によれば、最悪実行時間の過大見積り、または最良実行時間の過小見積りを回避し、プログラムの限界実行時間を正確に解析することができる。
【００４０】
＜第２の実施の形態＞
図４に示すプログラムＰの例の場合には、ブロックの数が８つのみであり、また図５に示すように、プログラムＰのとり得る実行経路が４つのみである。そのため、プログラムＰのとり得る実行経路毎に、変数挙動及び／またはハードウェア挙動を示す情報に基づいて経路実行時間を詳細に解析しても、解析時間がそれほどかからない。
【００４１】
しかし、実際には、解析対象となるプログラムのブロックの数や、とり得る実行経路の数は、一般的に膨大であり、全ての実行経路について経路実行時間を算出するのでは、限界実行時間の解析に長い時間を要してしまう。
【００４２】
そこで、本願発明者は、プログラムの限界実行時間の解析を効率良く行う手法を確立した。この手法について、本発明の第２〜４の実施の形態を用いて説明する。
【００４３】
図６は、本発明の第２の実施の形態にかかる限界実行時間解析システム２００を機能ブロックで示す図である。なお、限界実行時間解析システム２００のハードウェア構成は、図１に示したハードウェア構成と同様であり、ここで説明及び図示を省略する。
【００４４】
図６に示すように、限界実行時間解析システム２００も、解析対象のプログラムＰに対して限界実行時間ＴＭの解析を行うものであり、概略実行時間算出部２１０、経路実行時間算出部２２０、限界実行時間出力部１４０を備える。
【００４５】
図７は、限界実行時間解析システム２００における処理の流れを示すフローチャートである。まず、概略実行時間算出部２１０は、プログラムＰのとり得る全ての実行経路に対して、後述する概略実行時間を夫々算出して経路実行時間算出部２２０に出力する（Ｓ２００）。
【００４６】
経路実行時間算出部２２０は、概略実行時間算出部２１０が算出した概略実行時間の最も大きい順から（最悪実行時間を解析する場合）または最も小さい順から（最良実行時間を解析する場合）、該概略実行時間に対応する実行経路の経路実行時間を順次算出する（Ｓ２１０）。
【００４７】
すなわち、経路実行時間算出部２２０は、プログラムＰのとり得る全ての実行経路について経路実行時間を算出するのではない。プログラムＰの限界実行時間として最悪実行時間を解析する場合には、経路実行時間算出部２２０は、概略実行時間算出部２１０が算出した概略実行時間の大きい順からの上位における所定数の各概略実行時間に夫々対応する実行経路についてのみ経路時間を算出する。また、プログラムＰの限界実行時間として最良実行時間を解析する場合には、経路実行時間算出部２２０は、概略実行時間算出部２１０が算出した概略実行時間の小さい順からの上位における所定数の各概略実行時間に夫々対応する実行経路についてのみ経路時間を算出する。
【００４８】
なお、経路実行時間算出部２２０による経路実行時間の算出処理の詳細については、図２に示す限界実行時間解析システム１００における経路実行時間算出部１２０と同様であり、ここで詳細な説明を省略する。
【００４９】
限界実行時間出力部１４０は、図２に示す限界実行時間解析システム１００における限界実行時間出力部１４０と同一のものであり、経路実行時間算出部２２０が算出した各実行経路（ここではプログラムＰのとり得る実行経路の一部のみ）の経路実行時間の最大値及び／または最小値を限界実行時間ＴＭとして出力する（Ｓ２２０）。
【００５０】
ここで、ステップＳ２００における、概略実行時間算出部２１０による概略実行時間の算出について説明する。
【００５１】
概略実行時間算出部２１０は、プログラムＰの各ブロックに対して夫々設定された、該ブロックに含まれる命令列から想定される該ブロックの最長の実行時間または最短の実行時間であるブロック限界実行時間に基づいて、プログラムＰのとり得る実行経路毎に、該実行経路に含まれる各ブロックのブロック限界実行時間の総和を該実行経路の概略実行時間として算出する。
【００５２】
ブロック限界実行時間は、該ブロックに至る経路によらず、該ブロック内の命令列の内容から想定される固定値であり、例えば、該ブロック内の命令列から確定できるキャッシュメモリやプロセッサの挙動、変数挙動など、影響がブロック内にしか及ばない変動要因を織り込んで想定可能である。
【００５３】
また、各ブロックのブロック限界実行時間は、例えば、概略実行時間算出部２１０がプログラムＰの夫々のブロックを解析することにより取得するようにしてもよいし、ユーザにより設定されるようにしてもよい。ユーザにより設定する場合には、予め作成してプログラムＰに付属させるようにしてもよく、概略実行時間算出部２１０に対してユーザが直接入力するようにしてもよい。
【００５４】
なお、ブロック限界実行時間は、安全マージンをとるように設定されることが好ましい。例えば、プログラムＰの最悪実行時間を解析する場合には、ブロック限界実行時間としては、該ブロックの実行時間の実測値以上の値や、一般的に想定される実行時間以上の値を設定することが好ましい。反対に、プログラムＰの最良実行時間を解析する場合には、ブロック限界実行時間としては、該ブロックの実行時間の実測値以下の値や、一般的に想定される実行時間以下の値を設定することが好ましい。
【００５５】
図８と図９を参照して、プログラムＰに対して最悪実行時間を解析する場合を例にして、限界実行時間解析システム２００の処理をより具体的に説明する。
【００５６】
図８は、プログラムＰのブロック分割態様の一例を示す。図８から分かるように、該プログラムＰのブロック分割態様は、限界実行時間解析システム１００の説明時に用いた図４の例と同様である。
【００５７】
図８において、各ブロック内の括弧内の数字は、該ブロックに対して設定されたブロック限界実行時間を示す。ここで、プログラムＰの限界実行時間として最悪実行時間を例にしているので、ブロック限界実行時間は、該ブロックの実行時間の実測値以上の値や、該ブロックに含まれる命令列から一般的に想定される実行時間以上の値である。
【００５８】
図９は、図８に示すプログラムＰのとり得る実行経路、概略実行時間算出部２１０が算出した概略実行時間、経路実行時間算出部２２０が算出した経路実行時間、限界実行時間出力部１４０が出力する限界実行時間ＴＭの例を示す。
【００５９】
図９に示すように、プログラムＰのとり得る実行経路は、図５に示す例と同様の４つである。
【００６０】
概略実行時間算出部２１０は、この４つの実行経路の夫々の概略実行時間を求める。具体的には、夫々の実行経路毎に、該経路に含まれる全てのブロックのブロック限界実行時間の総和を求める。
【００６１】
経路実行時間算出部２２０は、概略実行時間の大きい順から、上位の所定数（例として２つ）の概略実行時間に夫々対応する経路についてのみ、経路実行時間を算出する。
【００６２】
なお、ここでは、プログラムＰの最悪実行時間の解析を例にしているため、概略実行時間の大きい順から、上位の所定数の概略実行時間に夫々対応する経路について経路実行時間を算出しているが、プログラムＰの最良実行時間を解析する場合には、概略実行時間の小さい順から、上位の所定数の概略実行時間に夫々対応する経路について経路実行時間を算出するようにすればよい。
【００６３】
図９に示すように、概略実行時間の大きい順からの上位の２つの概略実行時間（９、１０）に夫々対応する経路は、経路「ブロックＡ、Ｂ、Ｃ、Ｅ、Ｈ」と、経路「ブロックＡ、Ｂ、Ｄ、Ｅ、Ｈ」である。
【００６４】
経路実行時間算出部２２０は、この２つの実行経路についてのみ経路実行時間を算出し、限界実行時間出力部１４０は、この２つの経路実行時間の最大値を選択してプログラムＰの最悪実行時間として出力する。
【００６５】
例えば、ブロックＥに至る経路がＣ→Ｅである場合に、ブロックＥの想定される実行時間が「４」である一方、ブロックＥに至る経路がＤ→Ｅである場合に、ブロックＥの想定される実行時間が「２」であるとする。最悪実行時間を解析する場合に、ブロックＥに対して設定されるブロック限界実行時間は、安全の視点から「４」に設定される。
【００６６】
そのため、ブロック限界時間の総和（概略実行時間）のみに基づいて最悪実行時間の解析をすると、プログラムＰの最悪実行時間が「１０」であり、それに対応する経路が「ブロックＡ、Ｂ、Ｄ、Ｅ、Ｈ」であるとの解析結果が得られる。
【００６７】
対して、限界実行時間解析システム２００は、さらに、概略実行時間の大きい順からの上位の所定数の経路について、該経路により確定される変数挙動及び／ハードウェア挙動に基づいて経路実行時間を解析し、算出した経路実行時間の最大値をプログラムの最悪実行時間として得る。その結果、図９に示すように、概略実行時間が「９」である経路「ブロックＡ、Ｂ、Ｃ、Ｅ、Ｈ」の経路実行時間は「９」のままである一方、概略実行時間が「１０」である経路「ブロックＡ、Ｂ、Ｄ、Ｅ、Ｈ」の経路実行時間は「８」になる。そのため、経路「ブロックＡ、Ｂ、Ｃ、Ｅ、Ｈ」の経路実行時間「９」は、プログラムＰの最悪実行時間として得られる。
【００６８】
プログラムを構成する各ブロックは、該ブロックに至る経路によらずに、それに含まれる命令列の内容から大よその最長／最短の実行時間を推測することができる。その一方、ブロックの実際の実行時間は、それに至る経路によって変動する。図６に示す限界実行時間解析システム２００は、プログラムＰに含まれる各ブロックに対して夫々設定されたブロック限界実行時間から、プログラムＰのとり得る実行経路毎に概略実行時間を算出すると共に、概略実行時間の大きい順及び／または小さい順からの上位の所定数の実行経路、すなわちプログラムＰが限界実行時間で実行する可能性の高い経路についてのみ詳細に実行時間（経路実行時間）の解析をする。そのため、図２に示す限界実行時間解析システム１００と同様にプログラムの限界実行時間を正確に解析することができると共に、解析時間を短縮することができ、すなわちプログラムの限界実行時間の解析の効率向上を図ることができる。
【００６９】
なお、説明上の便宜のため、上記において、限界実行時間解析システム２００における経路実行時間算出部２２０が上位の２つの経路についてのみ経路実行時間を算出する例を説明したが、経路実行時間の算出がなされる経路数は、２に限られることがなく、さらに、設定などにより変更可能としてもよい。設定に際しては、例えば、プログラムが実装されるシステムの種類など、限界実行時間の保証に対する要求の厳しさに応じて、厳しいほど、数を増やすようにしてもよい。
【００７０】
また、上記において、一例として、経路実行時間算出部２２０は、上位の所定数の概略実行時間に夫々対応する経路について経路実行時間の算出を行うようになっている。例えば、プログラムＰのとり得る全ての経路のうちの、上位の所定の割合に該当する数の概略実行時間に夫々対応する経路について経路実行時間の算出を行うようにしてもよい。
【００７１】
なお、上述の本実施の形態の説明においては、概略実行時間算出部２１０にてプログラムＰのとり得る全ての実行経路に対して、概略実行時間を夫々算出して経路実行時間算出部３２０に出力し、その後概略実行時間の最大値または最小値に対応する経路から順に経路実行時間を算出する手順を示した。一方で概略実行時間算出部２１０の詳細動作の説明にあるように、実行経路に含まれる各ブロックのブロック限界実行時間の総和を該実行経路の概略実行時間として定義した場合に、概略実行時間が最大値または最小値となる最長経路・最短経路（以下候補経路という）を効率よく選択的に見つけ出す手法として、最長経路問題または最短経路問題の数学的な解法が知られている。
【００７２】
このため、本実施の形態のその他の動作例として、経路実行時間の算出がなされる経路数と同数のみ、概略実行時間の最大値または最小値に対応する経路から順に選択的に概略実行時間およびその経路実行時間の算出を行う手法を用いてもよい。
【００７３】
もしくは、概略実行時間が最大値または最小値となる経路（候補経路）を１つ検索し、その１つの経路に対して経路実行時間を算出する処理を行い、その後、既に経路実行時間の算出がなされた各経路を除外する条件を設定したうえで、再度概略実行時間が最大値または最小値となる１つの経路を候補経路として検索し、その経路に対して経路実行時間を算出する。そして、このような候補経路の検索、経路実行時間の算出を、上記経路数分繰り返す手法を用いてもよい。
【００７４】
これらの手法を用いた場合、上述の本実施の形態の説明による手順による経路実行時間算出の効率化に加え、概略実行時間の算出処理も効率化することができる。
【００７５】
このように、本実施の形態においては、プログラムのとり得る実行経路毎に、該実行経路に含まれる全てのブロックの前記ブロック限界実行時間の総和である概略実行時間を求めたうえ、前記プログラムのとり得る実行経路のうちの、前記概略実行時間算出部が算出した前記概略実行時間の大きい順または小さい順における上位の所定数または所定の割合に該当する数の実行経路についてのみ経路実行時間の算出を行う手法を用いる限りにおいて、様々な手順を用いた応用が可能である。
【００７６】
＜第３の実施の形態＞
図１０は、本発明の第３の実施の形態にかかる限界実行時間解析システム３００を機能ブロックで示す図である。なお、限界実行時間解析システム３００のハードウェア構成は、図１に示したハードウェア構成と同様であり、ここで説明及び図示を省略する。
【００７７】
図１０に示すように、限界実行時間解析システム３００も、解析対象のプログラムＰに対して限界実行時間ＴＭの解析を行うものであり、概略実行時間算出部２１０、経路実行時間算出部３２０、制御部３４０を備える。
【００７８】
経路実行時間算出部３２０は、概略実行時間算出部２１０が算出した最も大きい概略実行時間（最悪実行時間を解析する場合）または最も小さい概略実行時間（最良実行時間を解析する場合）に対応する実行経路から経路実行時間の算出を行うものである。また、本実施の形態において、経路実行時間算出部３２０による経路実行時間の算出は、制御部３４０により打ち切ることができる。
【００７９】
制御部３４０は、経路実行時間算出部３２０による１つ目の経路実行時間の算出開始から所定の時間が経過したときに、経路実行時間算出部３２０の処理を停止させることにより、経路実行時間算出部３２０による経路実行時間の算出を打ち切る。また、制御部３４０は、限界実行時間出力部としても機能し、経路実行時間の算出の打切りまでに経路実行時間算出部３２０が算出した経路実行時間の最大値／最小値をプログラムＰの限界実行時間として選択して出力する。
【００８０】
図１２は、限界実行時間解析システム３００における処理の流れを示すフローチャートである。まず、プログラムＰの限界実行時間として最悪実行時間を解析する場合を説明する。
【００８１】
まず、概略実行時間算出部２１０は、プログラムＰのとり得る全ての実行経路に対して、概略実行時間を夫々算出して制御部３４０に出力する（Ｓ３００）。
【００８２】
制御部３４０は、概略実行時間算出部２１０が算出した全ての概略実行時間のうちの最大値に対応する経路の経路時間の算出を経路実行時間算出部３２０に行わせる（Ｓ３１０、Ｓ３２０）。
【００８３】
その後、予め設定された時間Ｔを経過するまで、制御部３４０は、現在において経路実行時間の算出がなされた実行経路の概略実行時間の次に大きい概略実行時間に対応する実行経路の経路実行時間の算出を経路実行時間算出部３２０に行わせる（Ｓ３３０：Ｎｏ、Ｓ３４０、Ｓ３２０）。
【００８４】
そして、予め設定された時間Ｔが経過すると、制御部３４０は、経路実行時間算出部３２０による経路実行時間の算出を打ち切ると共に、経路実行時間算出部３２０により既に算出された各経路実行時間のうちの最大値をプログラムＰの限界実行時間として選択して出力する（Ｓ３５０）。
【００８５】
次いで、プログラムＰの限界実行時間として最悪実行時間を解析する場合を説明する。
【００８６】
この場合においても、まず、概略実行時間算出部２１０は、プログラムＰのとり得る全ての実行経路に対して、概略実行時間を夫々算出して制御部３４０に出力する（Ｓ３００）。
【００８７】
制御部３４０は、概略実行時間算出部２１０が算出した全ての概略実行時間のうちの最小値に対応する経路の経路時間の算出を経路実行時間算出部３２０に行わせる（Ｓ３１０、Ｓ３２０）。
【００８８】
その後、予め設定された時間Ｔを経過するまで、制御部３４０は、現在において経路実行時間の算出がなされた実行経路の概略実行時間の次に小さい概略実行時間に対応する実行経路の経路実行時間の算出を経路実行時間算出部３２０に行わせる（Ｓ３３０：Ｎｏ、Ｓ３４０、Ｓ３２０）。
【００８９】
そして、予め設定された時間Ｔが経過すると、制御部３４０は、経路実行時間算出部３２０による経路実行時間の算出を打ち切ると共に、経路実行時間算出部３２０により既に算出された各経路実行時間のうちの最小値をプログラムＰの限界実行時間ＴＭとして選択して出力する（Ｓ３５０）。
【００９０】
このように、本実施の形態の限界実行時間解析システム３００において、経路実行時間算出部３２０は、プログラムＰの限界実行時間として最悪実行時間を解析する場合には、概略実行時間算出部２１０が算出した最も大きい概略実行時間に対応する実行経路からの順に経路実行時間の算出を行い、所定の時間が経過すると、未計算の実行経路についての経路実行時間の算出を停止する。また、経路実行時間算出部３２０は、プログラムＰの限界実行時間として最良実行時間を解析する場合には、概略実行時間算出部２１０が算出した最も小さい概略実行時間に対応する実行経路からの順に経路実行時間の算出を行い、所定の時間が経過すると、未計算の実行経路についての経路実行時間の算出を停止する。
【００９１】
すなわち、限界実行時間解析システム２００が、経路実行時間の算出を行う実行経路の数を制限することに対して、本実施の形態の限界実行時間解析システム３００は、経路実行時間の算出が実行された時間を制限している。従って、限界実行時間解析システム３００は、限界実行時間解析システム２００と同様に、プログラムの限界実行時間の解析の効率向上を図ることができる。
【００９２】
なお、上述の本実施の形態の説明においては、概略実行時間算出部２１０にてプログラムＰのとり得る全ての実行経路に対して、概略実行時間を夫々算出して制御部４４０へと出力し、その後概略実行時間の最大値または最小値に対応する経路から順に経路実行時間を算出する手順を示した。前述したように、実行経路に含まれる各ブロックのブロック限界実行時間の総和を該実行経路の概略実行時間として定義した場合に、概略実行時間が最大値または最小値となる最長経路・最短経路（候補経路）を効率よく選択的に見つけ出す手法として、最長経路問題または最短経路問題の数学的な解法が知られている。
【００９３】
このため、本実施の形態のその他の動作例として、概略実行時間が最大値または最小値となる経路を１つ検索し、その１つの経路に対して経路実行時間を算出する処理を行い、その後、既に経路実行時間の算出がなされた各経路を除外する条件を設定したうえで、再度概略実行時間が最大値または最小値となる経路を候補経路として検索し、その経路に対して経路実行時間を算出する。そして、候補経路の検索と経路実行時間の算出を、所定時間が経過するまで繰り返す手法を用いてもよい。この手法を用いた場合、上述の本実施の形態の説明による手順による経路実行時間算出の効率化に加え、概略実行時間の算出処理も効率化することができる。
【００９４】
このように、本実施の形態においては、プログラムのとり得る実行経路毎に、該実行経路に含まれる全てのブロックの前記ブロック限界実行時間の総和である概略実行時間を求めたうえ、最大値または最小値の前記概略実行時間に対応する実行経路から前記経路実行時間の算出を行い、所定の時間が経過したときに前記経路実行時間の算出を打ち切る手法を用いる限りにおいて、様々な手順を用いた応用が可能である。
【００９５】
＜第４の実施の形態＞
上記にて説明したように、プログラムＰの各ブロックに対して夫々設定されたブロック限界実行時間は、該ブロックに含まれる命令列から想定される該ブロックの最長の実行時間または最短の実行時間である。
【００９６】
すなわち、プログラムＰの最悪実行時間の解析に際して、各ブロックに対しては、該ブロックに含まれる命令列から想定される該ブロックの最長の実行時間である。そのため、ある経路の概略実行時間は、該経路の経路実行時間以上になる。
【００９７】
従って、プログラムＰの最悪実行時間の解析に際して、既に算出した各経路実行時間のうちの最大値が、経路実行時間の算出がまだ行われていないいずれの実行経路の概略実行時間よりも大きいときに、経路実行時間の算出がまだ行われている各実行経路のうちに、最悪実行時間でプログラムＰが実行される経路が存在しないと言える。
【００９８】
同様に、プログラムＰの最良実行時間の解析に際して、各ブロックに対しては、該ブロックに含まれる命令列から想定される該ブロックの最短の実行時間である。そのため、ある経路の概略実行時間は、該経路の経路実行時間以下になる。
【００９９】
従って、プログラムＰの最良実行時間の解析に際して、既に算出した各経路実行時間のうちの最小値が、経路実行時間の算出がまだ行われていないいずれの実行経路の概略実行時間よりも小さいときに、経路実行時間の算出がまだ行われている各実行経路のうちに、最良実行時間でプログラムＰが実行される経路が存在しないと言える。
【０１００】
図１２に示す本発明の第４の実施の形態にかかる限界実行時間解析システム４００は、上記知見に基づいてなされたものである。該図は、限界実行時間解析システム４００を機能ブロックで示す図である。なお、限界実行時間解析システム４００のハードウェア構成は、図１に示したハードウェア構成と同様であり、ここで説明及び図示を省略する。
【０１０１】
図１２に示すように、限界実行時間解析システム４００も、解析対象のプログラムＰに対して限界実行時間ＴＭの解析を行うものであり、概略実行時間算出部２１０、経路実行時間算出部３２０、制御部４４０を備える。制御部４４０は、後述する、プログラムＰの限界実行時間の候補となる経路実行時間（以下候補Ｑという）を記憶する候補記憶部４４２を備える。
【０１０２】
概略実行時間算出部２１０と経路実行時間算出部３２０は、限界実行時間解析システム３００における概略実行時間算出部２１０と経路実行時間算出部３２０と夫々同様のものである。
【０１０３】
制御部３４０は、概略実行時間が大きい順または小さい順に夫々の実行経路の経路実行時間の算出を経路実行時間算出部３２０に順次行わせると共に、経路実行時間算出部３２０による経路実行時間の算出がまだなされていない実行経路のうちに、限界実行時間になり得る経路の存在可能性を判断し、存在可能性がないと判断したときに、経路実行時間算出部３２０による経路実行時間の算出を打ち切る。
【０１０４】
上述した存在可能性があるか否かの判断は、下記のように行われる。
プログラムＰの最悪実行時間の解析に際しては、経路実行時間算出部３２０により既に算出した各経路実行時間のうちの最大値が、経路実行時間の算出がまだ行われていないいずれの実行経路の概略実行時間よりも大きいときに、経路実行時間の算出がまだ行われている各実行経路のうちに、最悪実行時間でプログラムＰが実行される経路の存在可能性がないと判断する。
【０１０５】
一方、プログラムＰの最良実行時間の解析に際して、経路実行時間算出部３２０により既に算出した各経路実行時間のうちの最小値が、経路実行時間の算出がまだ行われていないいずれの実行経路の概略実行時間よりも小さいときに、経路実行時間の算出がまだ行われている各実行経路のうちに、最良実行時間でプログラムＰが実行される経路の存在可能性がないと判断する。
【０１０６】
図１３と図１４のフローチャートを参照して、限界実行時間解析システム４００における処理の流れをより具体的に説明する。
【０１０７】
図１３は、プログラムＰの限界実行時間として最悪実行時間を解析する場合のフローチャートである。
【０１０８】
まず、概略実行時間算出部２１０は、プログラムＰのとり得る全ての実行経路に対して、概略実行時間を夫々算出して制御部４４０に出力する（Ｓ４００）。
【０１０９】
制御部４４０は、概略実行時間算出部２１０が算出した全ての概略実行時間のうちの最大値に対応する経路の経路実行時間の算出を経路実行時間算出部３２０に行わせる（Ｓ４１０、Ｓ４２０）。なお、このとき、制御部４４０における候補記憶部４４２に格納された候補Ｑは、初期値の「０」であるとする。
【０１１０】
そして、制御部４４０は、現在において算出された経路実行時間ＫＴ（ｉ）が候補記憶部４４２に記憶された候補Ｑより大きいか否かを確認し（Ｓ４３０）、経路実行時間ＫＴ（ｉ）が候補記憶部４４２に記憶された候補Ｑより大きい場合には、候補Ｑを経路実行時間ＫＴ（ｉ）に更新して（Ｓ４３０：Ｙｅｓ、Ｓ４３２）、ステップＳ４４０に進む。
【０１１１】
一方、ステップＳ４３０における確認の結果、経路実行時間ＫＴ（ｉ）が候補記憶部４４２に記憶された候補Ｑ以下である場合（Ｓ４３０：Ｎｏ）には、制御部４４０は、候補Ｑの更新をせずに、直接ステップＳ４４０に進む。
【０１１２】
ステップＳ４４０において、制御部４４０は、経路実行時間算出部３２０によりまだ経路実行時間の算出がなされていない各実行経路（経路（ｉ＋１）からの経路）のうちに、概略実行時間が現在の候補Ｑ以上の実行経路の有無を確認する（Ｓ４４０）。
【０１１３】
具体的には、経路実行時間の次の算出対象となる実行経路（まだ経路実行時間の算出が行われている各実行経路のうちの、概略実行時間が最も大きい実行経路）の概略実行時間が候補Ｑより小さければ、制御部４４０は、経路実行時間の算出がまだ行われている各実行経路のうちに、最悪実行時間でプログラムＰが実行される経路の存在可能性がないと判断し、経路実行時間算出部３２０による経路実行時間の算出を打ち切ると共に、候補記憶部４４２に格納された候補Ｑを限界実行時間（ここでは最悪実行時間）として出力する（Ｓ４４０：Ｎｏ、Ｓ４５０）。
【０１１４】
一方、ステップＳ４４０における確認の結果、経路実行時間の次の算出対象となる実行経路の概略実行時間が候補Ｑ以上であれば、制御部４４０は、経路実行時間の算出がまだ行われている各実行経路のうちに、最悪実行時間でプログラムＰが実行される経路の存在可能性があると判断し、次の算出対象となる実行経路の経路実行時間の算出を経路実行時間算出部３２０に行わせる（Ｓ４４２、Ｓ４２０）。その後、ステップＳ４３０からの処理が繰り返される。
【０１１５】
図１４は、プログラムＰの限界実行時間として最良実行時間を解析する場合のフローチャートである。図１４において、図１３のステップと異なるステップ（Ｓ５１０、Ｓ５３０、Ｓ５４０）を太枠で表している。
【０１１６】
まず、概略実行時間算出部２１０は、プログラムＰのとり得る全ての実行経路に対して、概略実行時間を夫々算出して制御部４４０に出力する（Ｓ４００）。
【０１１７】
制御部４４０は、概略実行時間算出部２１０が算出した全ての概略実行時間のうちの最小値に対応する経路の経路実行時間の算出を経路実行時間算出部３２０に行わせる（Ｓ５１０、Ｓ４２０）。なお、このとき、制御部４４０における候補記憶部４４２に格納された候補Ｑ（図中ＭＡＸ）は、プログラムＰがどのような性能のハードウェアで、どのような実行経路で実行されても、それ以上の実行時間が不可能な値が設定されている。ＭＡＸ値は、例えばユーザにより予め設定されてもよいし、候補記憶部４４２の記憶可能な最大数値であってもよい。
【０１１８】
次いで、制御部４４０は、現在において算出された経路実行時間ＫＴ（ｉ）が候補記憶部４４２に記憶された候補Ｑより小さいか否かを確認し（Ｓ５３０）、経路実行時間ＫＴ（ｉ）が候補記憶部４４２に記憶された候補Ｑより小さい場合には、候補Ｑを経路実行時間ＫＴ（ｉ）に更新して（Ｓ５３０：Ｙｅｓ、Ｓ４３２）、ステップＳ５４０に進む。
【０１１９】
一方、ステップＳ５３０における確認の結果、経路実行時間ＫＴ（ｉ）が候補記憶部４４２に記憶された候補Ｑ以上である場合（Ｓ５３０：Ｎｏ）には、制御部４４０は、候補Ｑの更新をせずに、直接ステップＳ５４０に進む。
【０１２０】
ステップＳ５４０において、制御部４４０は、経路実行時間算出部３２０によりまだ経路実行時間の算出がなされていない各実行経路（経路（ｉ＋１）からの経路）のうちに、概略実行時間が現在の候補Ｑ以下の実行経路の有無を確認する（Ｓ５４０）。
【０１２１】
具体的には、経路実行時間の次の算出対象となる実行経路（まだ経路実行時間の算出が行われている各実行経路のうちの、概略実行時間が最も小さい実行経路）の概略実行時間が候補Ｑより大きければ、制御部４４０は、経路実行時間の算出がまだ行われている各実行経路のうちに、最良実行時間でプログラムＰが実行される経路の存在可能性がないと判断し、経路実行時間算出部３２０による経路実行時間の算出を打ち切ると共に、候補記憶部４４２に格納された候補Ｑを限界実行時間（ここでは最良実行時間）として出力する（Ｓ５４０：Ｎｏ、Ｓ４５０）。
【０１２２】
一方、ステップＳ５４０における確認の結果、経路実行時間の次の算出対象となる実行経路の概略実行時間が候補Ｑ以下であれば、制御部４４０は、経路実行時間の算出がまだ行われている各実行経路のうちに、最良実行時間でプログラムＰが実行される経路の存在可能性があると判断し、次の算出対象となる実行経路の経路実行時間の算出を経路実行時間算出部３２０に行わせる（Ｓ４４２、Ｓ４２０）。その後、ステップＳ５３０からの処理が繰り返される。
【０１２３】
このように、本実施の形態の限界実行時間解析システム４００において、経路実行時間算出部３２０は、まだ経路実行時間の算出がなされていない実行経路のうちに、プログラムＰが限界実行時間で実行される可能性の経路が無くなるまで、夫々の実行経路の経路実行時間を算出し、算出した各経路実行時間から限界実行時間を得るため、プログラムの限界実行時間の解析の効率向上を図ることができる。
【０１２４】
なお、上述の本実施の形態の説明においては、概略実行時間算出部２１０にてプログラムＰのとり得る全ての実行経路に対して、概略実行時間を夫々算出して制御部４４０へと出力し、その後概略実行時間の最大値または最小値に対応する経路から順に経路実行時間を算出する手順を示した。一方で前述したように、実行経路に含まれる各ブロックのブロック限界実行時間の総和を該実行経路の概略実行時間として定義した場合に、概略実行時間が最大値または最小値となる最長経路・最短経路（候補経路）を効率よく選択的に見つけ出す手法として、最長経路問題または最短経路問題の数学的な解法が知られている。
【０１２５】
このため、本実施の形態のその他の動作例として、概略実行時間が最大値または最小値となる経路を１つ検索し、その１つの経路に対して経路実行時間を算出する処理を行い、この経路実行時間が限界実行時間でない場合に、既に経路実行時間の算出がなされた各経路を除外する条件を設定したうえで、再度概略実行時間が最大値または最小値となる経路を１つ候補経路として検索し、その経路に対して経路実行時間を算出する処理を、まだ経路実行時間の算出がなされていない実行経路のうちに、プログラムＰが限界実行時間で実行される可能性の経路が無くなるまで繰り返す手法を用いることができる。この場合、上述の本実施の形態の説明による手順による経路実行時間算出の効率化に加え、概略実行時間の算出処理も効率化することができる。
【０１２６】
このように、本実施の形態においては、プログラムのとり得る実行経路毎に、該実行経路に含まれる全てのブロックの前記ブロック限界実行時間の総和である概略実行時間を求めたうえ、限界実行時間として最悪実行時間を解析する場合であって、既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、既に算出した前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも小さいときに、前記経路実行時間の算出を打ち切る手法を用いる限りにおいて、様々な手順を用いた応用が可能である。
【０１２７】
以上、実施の形態をもとに本発明を説明した。実施の形態は例示であり、本発明の主旨から逸脱しない限り、上述した各実施の形態に対してさまざまな変更、増減、組合せを行ってもよい。これらの変更、増減、組合せが行われた変形例も本発明の範囲にあることは、当業者に理解されるところである。
【０１２８】
例えば、第４の実施の形態にかかる限界実行時間解析システム４００において、制御部４４０は、候補記憶部４４２に１つの候補Ｑのみを登録するようにしているが、経路実行時間算出部３２０による経路実行時間の算出の打切りまでに算出された全ての経路実行時間を候補として候補記憶部４４２に登録しておき、打切りの後に、複数の候補のうちの最大値／最小値を限界実行時間として選択して出力するようにしてもよい。
【産業上の利用可能性】
【０１２９】
本発明にかかる技術は、例えば、機械、プラント制御等リアルタイム性が求められるシステムの制御プログラムの実行時間保証に用いることができる。また、例えば、一般的なプログラムのチューニング向けの実行時間の解析情報の取得にも利用可能である。【０１３０】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記によって限定されるものではない。本願発明の構成や詳細には、発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１３１】
この出願は、２０１２年３月２日に出願された日本出願特願２０１２−０４７０５０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１３２】
１００  限界実行時間解析システム
１０１  ＣＰＵ
１０２  ＲＡＭ
１０３  ＲＯＭ
１０４  記憶装置
１０５  バス
１２０  経路実行時間算出部
１４０  限界実行時間出力部
２００  限界実行時間解析システム
２１０  概略実行時間算出部
２２０  経路実行時間算出部
３００  限界実行時間解析システム
３２０  経路実行時間算出部
３４０  制御部
４００  限界実行時間解析システム
４４０  制御部
４４２  候補記憶部
【図１】
2013128519.tif 000003
【図２】
2013128519.tif 000004
【図３】
2013128519.tif 000005
【図４】
2013128519.tif 000006
【図５】
2013128519.tif 000007
【図６】
2013128519.tif 000008
【図７】
2013128519.tif 000009
【図８】
2013128519.tif 000010
【図９】
2013128519.tif 000011
【図１０】
2013128519.tif 000012
【図１１】
2013128519.tif 000013
【図１２】
2013128519.tif 000014
【図１３】
2013128519.tif 000015
【図１４】
2013128519.tif 000016
【手続補正書】
【提出日】平成26年8月22日(2014.8.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
最悪実行時間または最良実行時間である限界実行時間の解析をプログラムに対して行う限界実行時間解析装置であって、
前記プログラムを構成する複数のブロックであって、各前記ブロックが、１つ以上の命令を有し、入口が先頭の命令のみであり、出口が末尾の命令のみである前記複数のブロック間の制御関係に応じて確定される前記プログラムのとり得る実行経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、前記プログラムが該実行経路で実行された場合の実行時間である経路実行時間を算出する経路実行時間算出手段と、
前記経路実行時間算出手段により算出した各前記経路実行時間のうちの最大値または最小値を前記限界実行時間として出力する限界実行時間出力手段とを備えることを特徴とする限界実行時間解析装置。
【請求項２】
前記複数のブロックの夫々に対して設定された、該ブロックに含まれる命令列から想定される該ブロックの最長の実行時間または最短の実行時間であるブロック限界実行時間に基づいて、前記プログラムのとり得る実行経路毎に、該実行経路に含まれる全てのブロックの前記ブロック限界実行時間の総和である概略実行時間を求める概略実行時間算出手段をさらに備え、
前記経路実行時間算出手段は、
前記プログラムのとり得る実行経路のうちの、前記概略実行時間算出手段が算出した前記概略実行時間の大きい順または小さい順における上位の所定数または所定の割合に該当する数の実行経路についてのみ前記経路実行時間を算出し、
または、前記概略実行時間算出手段が算出した最も大きい前記概略実行時間または最も小さい前記概略実行時間に対応する実行経路から前記経路実行時間の算出を行い、所定の時間が経過したときに前記経路実行時間の算出を打ち切り、
または、前記限界実行時間として最悪実行時間を解析する場合であって、既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、既に算出した前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも小さいときに、前記経路実行時間の算出を打ち切ることを特徴とする請求項１に記載の限界実行時間解析装置。
【請求項３】
前記概略実行時間算出手段は、
前記経路実行時間算出手段により前記経路実行時間の算出がまだ行われていない実行経路のうちの、前記概略実行時間が最大または最小となり得る実行経路の１つを候補経路として検索して前記経路実行時間算出手段に通知する処理を繰り返し、
前記経路実行時間算出手段は、
前記概略実行時間算出手段から前記候補経路が通知される度に該候補経路の前記経路実行時間を算出し、
前記概略実行時間算出手段は、
前記経路実行時間算出手段に通知した前記候補経路の総数が前記所定数または前記所定の割合に該当する数に到達したとき、
または、前記経路実行時間算出手段に１つ目の前記候補経路を通知してから前記所定の時間が経過したとき、
または、前記限界実行時間として最悪実行時間を解析する場合であって、前記経路実行時間算出手段により既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、前記経路実行時間算出手段により既に算出した各前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より小さいときに、
前記候補経路の検索及び前記経路実行時間算出手段への前記候補経路の通知を打ち切ることを特徴とする請求項２に記載の限界実行時間解析装置。
【請求項４】
最悪実行時間または最良実行時間である限界実行時間の解析をプログラムに対して行う限界実行時間解析方法において、
前記プログラムを構成する複数のブロックであって、各前記ブロックが、１つ以上の命令を有し、入口が先頭の命令のみであり、出口が末尾の命令のみである前記複数のブロック間の制御関係に応じて確定される前記プログラムのとり得る実行経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、前記プログラムが該実行経路で実行された場合の実行時間である経路実行時間を算出する経路実行時間算出処理と、
前記経路実行時間算出処理により算出した各前記経路実行時間のうちの最大値または最小値を前記限界実行時間として出力する処理とを有することを特徴とする限界実行時間解析方法。
【請求項５】
前記複数のブロックの夫々に対して設定された、該ブロックに含まれる命令列から想定される該ブロックの最長の実行時間または最短の実行時間であるブロック限界実行時間に基づいて、前記プログラムのとり得る実行経路毎に、該実行経路に含まれる全てのブロックの前記ブロック限界実行時間の総和である概略実行時間を求める概略実行時間算出処理をさらに有し、
前記経路実行時間算出処理は、
前記プログラムのとり得る実行経路のうちの、前記概略実行時間算出処理により算出した前記概略実行時間の大きい順または小さい順における上位の所定数または所定の割合に該当する数の実行経路についてのみ前記経路実行時間を算出し、
または、前記概略実行時間算出処理により算出した最も大きい前記概略実行時間または最も小さい前記概略実行時間に対応する実行経路から前記経路実行時間の算出を行い、所定の時間が経過したときに前記経路実行時間の算出を打ち切り、
または、前記限界実行時間として最悪実行時間を解析する場合であって、既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、既に算出した前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも小さいときに、前記経路実行時間の算出を打ち切ることを特徴とする請求項４に記載の限界実行時間解析方法。
【請求項６】
前記概略実行時間算出処理は、
前記経路実行時間算出処理により前記経路実行時間の算出がまだ行われていない実行経路のうちの、前記概略実行時間が最大または最小となり得る実行経路の１つを候補経路として検索して前記経路実行時間算出処理に通知する処理を繰り返し、
前記経路実行時間算出処理は、
前記概略実行時間算出処理から前記候補経路が通知される度に該候補経路の前記経路実行時間を算出し、
前記概略実行時間算出処理は、
前記経路実行時間算出処理に通知した前記候補経路の総数が前記所定数または前記所定の割合に該当する数に到達したとき、
または、前記経路実行時間算出処理に１つ目の前記候補経路を通知してから前記所定の時間が経過したとき、
または、前記限界実行時間として最悪実行時間を解析する場合であって、前記経路実行時間算出処理により既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、前記経路実行時間算出処理により既に算出した各前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より小さいときに、
前記候補経路の検索及び前記経路実行時間算出処理への前記候補経路の通知を打ち切ることを特徴とする請求項５に記載の限界実行時間解析方法。
【請求項７】
解析対象プログラムの最悪実行時間または最良実行時間である限界実行時間の解析処理をコンピュータに実行せしめるプログラムであって、
前記解析処理は、
前記プログラムを構成する複数のブロックであって、各前記ブロックが、１つ以上の命令を有し、入口が先頭の命令のみであり、出口が末尾の命令のみである前記複数のブロック間の制御関係に応じて確定される前記プログラムのとり得る実行経路毎に、該実行経路を通る場合に得られる変数挙動及び／またはハードウェア挙動を示す情報に基づいて、前記プログラムが該実行経路で実行された場合の実行時間である経路実行時間を算出する経路実行時間算出処理と、
前記経路実行時間算出処理により算出した各前記経路実行時間のうちの最大値または最小値を前記限界実行時間として出力する処理とを有することを特徴とするプログラム。
【請求項８】
前記解析処理は、
前記複数のブロックの夫々に対して設定された、該ブロックに含まれる命令列から想定される該ブロックの最長の実行時間または最短の実行時間であるブロック限界実行時間に基づいて、前記プログラムのとり得る実行経路毎に、該実行経路に含まれる全てのブロックの前記ブロック限界実行時間の総和である概略実行時間を求める概略実行時間算出処理をさらに有し、
前記経路実行時間算出処理は、
前記プログラムのとり得る実行経路のうちの、前記概略実行時間算出処理により算出した前記概略実行時間の大きい順または小さい順における上位の所定数または所定の割合に該当する数の実行経路についてのみ前記経路実行時間を算出し、
または、前記概略実行時間算出処理により算出した最も大きい前記概略実行時間または最も小さい前記概略実行時間に対応する実行経路から前記経路実行時間の算出を行い、所定の時間が経過したときに前記経路実行時間の算出を打ち切り、
または、前記限界実行時間として最悪実行時間を解析する場合であって、既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、既に算出した前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていないいずれの実行経路の前記概略実行時間よりも小さいときに、前記経路実行時間の算出を打ち切ることを特徴とする請求項７に記載のプログラム。
【請求項９】
前記概略実行時間算出処理は、
前記経路実行時間算出処理により前記経路実行時間の算出がまだ行われていない実行経路のうちの、前記概略実行時間が最大または最小となり得る実行経路の１つを候補経路として検索して前記経路実行時間算出処理に通知する処理を繰り返し、
前記経路実行時間算出処理は、
前記概略実行時間算出処理から前記候補経路が通知される度に該候補経路の前記経路実行時間を算出し、
前記概略実行時間算出処理は、
前記経路実行時間算出処理に通知した前記候補経路の総数が前記所定数または前記所定の割合に該当する数に到達したとき、
または、前記経路実行時間算出処理に１つ目の前記候補経路を通知してから前記所定の時間が経過したとき、
または、前記限界実行時間として最悪実行時間を解析する場合であって、前記経路実行時間算出処理により既に算出した各前記経路実行時間のうちの最大値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より大きいとき、または、前記限界実行時間として最良実行時間を解析する場合であって、前記経路実行時間算出処理により既に算出した各前記経路実行時間のうちの最小値が、前記経路実行時間の算出がまだ行われていない実行経路のうちから検索した次の前記候補経路の前記概略実行時間より小さいときに、
前記候補経路の検索及び前記経路実行時間算出処理への前記候補経路の通知を打ち切ることを特徴とする請求項８に記載のプログラム。
【国際調査報告】
2013128519.tif 000017
2013128519.tif 000018