(57)【特許請求の範囲】
【請求項１】
プログラムの実行時間を推定する実行時間推定装置による実行時間推定方法であって、
前記実行時間推定装置が、
前記プログラムから、条件分岐命令および関数呼出命令の少なくとも１つを境界点として分割された部分プログラムを抽出する第１のステップと、
各部分プログラムの実行時間を算出して、記憶部に格納する第２のステップと、
前記各部分プログラムの先頭命令と、終端命令と、算出した部分プログラムの前記実行時間とを対応付けて前記記憶部に格納する第３のステップと、
前記プログラムを実行させたときの前記条件分岐命令についての真偽の系列である分岐履歴ビット系列を生成して、前記記憶部に格納する第４のステップと、
前記分岐履歴ビット系列を基に、前記部分プログラムの実行順番が記述されている部分プログラム実行系列を生成する第５のステップと、
前記部分プログラム実行系列に基づいて、前記部分プログラムの実行時間を加算する第６のステップと、
を行うことを特徴とする実行時間推定方法。
【請求項２】
前記記憶部は、第１の記憶部と、第２の記憶部とからなり、
前記実行時間推定装置は、
前記第２のステップ終了後、
前記部分プログラムが、所定回数繰り返されるループである場合、前記ループ内部に、前記ループを継続するか否かを決定する分岐であるループ継続条件命令以外の条件分岐命令を含まず、かつ前記ループにおける部分プログラムの繰り返し回数が、前記プログラム中において不変であるとき、前記ループ内の部分プログラムの実行時間に、前記繰り返し回数を乗算してループ実行時間を算出し、前記算出したループ実行時間を１つの前記部分プログラムの実行時間とする縮退を行う第６のステップを行った後、前記第３のステップを行い、
前記第４のステップにおいて、前記第１の記憶部に前記分岐履歴ビット系列を格納した後、前記縮退を行ったループに該当する部分プログラムに関連する前記真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納すること
を行うことを特徴とする請求項１に記載の実行時間推定方法。
【請求項３】
前記記憶部は、第１の記憶部と、第２の記憶部とからなり、
前記実行時間推定装置は、
前記部分プログラムが、所定回数繰り返されるループである場合、前記ループ内部に、前記ループを継続するか否かを決定する分岐であるループ継続条件命令以外の条件分岐命令を含まず、かつ前記ループにおける部分プログラムの繰り返し回数が、個々の前記ループ中で不変であるとき、
前記第３のステップにおいて、
各ループの繰り返し回数の系列を生成する第１１のステップと、
前記ループ内の部分プログラムの実行時間に、前記繰り返し回数の系列における繰り返し回数を乗算したループの実行時間を算出する第１２のステップと、
前記算出した各ループの実行時間を加算する第１３のステップと、を行い、
前記第４のステップにおいて、前記第１の記憶部に前記分岐履歴ビット系列を格納した後、前記ループに該当する部分プログラムに関連する前記真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納すること、
を行うことを特徴とする請求項１に記載の実行時間推定方法。
【請求項４】
前記実行時間推定装置は、
前記第４のステップ終了後に、
前記部分プログラムが、所定回数繰り返されるループである場合、前記ループ内部に、ｉｆ−ｅｌｓｅ分岐命令を含むとき、前記ｉｆ−ｅｌｓｅ分岐命令が真となる確率および前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率を算出する第２１のステップと、
前記ｉｆ−ｅｌｓｅ分岐命令が真となるときに実行される部分プログラムの実行時間に前記ｉｆ−ｅｌｓｅ分岐命令が真となる確率を乗算した値および前記ｉｆ−ｅｌｓｅ分岐命令が偽となるときに実行される部分プログラムの実行時間に前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率を乗算した値を加算する第２２のステップと、
前記ｉｆ−ｅｌｓｅ分岐命令が真となるときに実行される前記部分プログラムおよび前記ｉｆ−ｅｌｓｅ分岐命令が偽となるときに実行される前記部分プログラムを１つの部分プログラムとする縮退を行う第２３のステップと、
前記第４のステップにおいて前記第１の記憶部に格納された前記分岐履歴ビット系列から、前記縮退が行われた部分プログラムに関連する前記真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納する第２４のステップと、
を行った後、前記第５のステップを行うことを特徴とする請求項２または請求項３に記載の実行時間推定方法。
【請求項５】
前記記憶部は、第１の記憶部と、第２の記憶部とからなり、
前記実行時間推定装置は、
前記第４のステップにおいて、生成された分岐履歴ビット系列を、前記第１の記憶部に格納し、
前記部分プログラムが、所定回数繰り返されるループで構成される多重ループであり、前記多重ループにおける各ループは、前記ループを継続するか否かを決定する分岐であるループ継続条件命令を１つ含むループのみで構成されており、
前記第４のステップ終了後に、
前記実行時間推定装置は、
前記多重ループ内に、ループ継続条件命令とは異なる条件分岐命令であるｉｆ−ｅｌｓｅ分岐命令が含まれている場合、
当該ループ内におけるｉｆ−ｅｌｓｅ分岐命令が真となる確率と、前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率とを算出する第３１のステップと、
前記確率を基に、前記ループの平均実行時間を内側のループから順に算出し、前記算出した前記ループの平均実行時間を１つの前記部分プログラムの実行時間とする縮退を行う第３２のステップと、
前記第４のステップにおいて前記第１の記憶部に格納された前記分岐履歴ビット系列から、前記縮退を行ったループに該当する真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納する第３３のステップと、
を行った後、前記第５のステップを行うことを特徴とする請求項１に記載の実行時間推定方法。
【請求項６】
前記記憶部は、第１の記憶部と、第２の記憶部とからなり、
前記実行時間推定装置は、
前記第４のステップにおいて、生成された分岐履歴ビット系列を、前記第１の記憶部に格納し、
前記第４のステップ終了後に、
前記部分プログラムを複数有する関数において、
前記部分プログラムの出現頻度を算出する第４１のステップと、
前記算出した部分プログラムの前記実行時間と、前記部分プログラムの出現頻度と、を乗算することによって、前記関数内における前記部分プログラムの全実行時間推定値を算出する第４２のステップと、
前記関数内の前記部分プログラムについて、前記部分プログラムの全実行時間推定値の総和を算出することによって関数の全実行時間推定値を算出する第４３のステップと、
前記第４のステップにおいて前記第１の記憶部に格納された前記分岐履歴ビット系列から、前記全実行時間推定値を算出した関数に該当する真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納する第４４のステップと、
を行った後、前記第５のステップを行うことを特徴とする請求項１に記載の実行時間推定方法。
【請求項７】
前記記憶部は、第１の記憶部と、第２の記憶部とからなり、
前記部分プログラムが、所定回数繰り返されるループである場合、
前記実行時間推定装置は、
前記第４のステップにおいて、生成された分岐履歴ビット系列を、前記第１の記憶部に格納し、
前記第４のステップ終了後に、
前記ループのうち、第１のループが、所定回数繰り返されるループで構成される多重ループであり、前記多重ループにおける各ループは、前記ループを継続するか否かを決定する分岐であるループ継続条件命令を１つ含むループのみで構成されており、前記第１のループが前記プログラムにおいて、少なくとも１つ存在する場合、
当該第１のループ内部に、前記ループ継続条件命令とは異なる条件分岐命令であるｉｆ−ｅｌｓｅ分岐命令が含まれる場合、前記ｉｆ−ｅｌｓｅ分岐命令が真となる確率と、前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率とを算出する第５１のステップと、
前記確率を基に、前記第１のループの平均実行時間を内側のループから順に算出し、前記算出した第１のループの平均実行時間を１つの前記部分プログラムの実行時間とする縮退を行う第５２のステップと、
第２のループは、前記第２のループ内部に、前記ループを継続するか否かを決定する分岐であるループ継続条件命令以外の条件分岐命令を含まず、かつ繰り返し回数が、個々の前記第２のループ中で不変であるループであり、前記第２のループが前記プログラムにおいて、少なくとも１つ存在する場合、
各前記第２のループにおける部分プログラムの繰り返し回数の系列を生成する第５３のステップと、
前記第２のループに該当する部分プログラムの実行時間に、前記繰り返し回数の系列における繰り返し回数を乗算したループの実行時間推定値を算出する第５４のステップと、
前記算出した各第２のループの実行時間推定値を加算する第５５のステップと、
前記第４のステップにおいて前記第１の記憶部に格納された前記分岐履歴ビット系列から、前記第１のループおよび前記第２のループに該当する真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納する第５６のステップと、
を行った後、前記第５のステップを行うことを特徴とする請求項１に記載の実行時間推定方法。
【請求項８】
前記実行時間推定装置は、
前記第５１のステップ終了後に、
ｉｆ−ｅｌｓｅ分岐命令の真偽による前記部分プログラムの実行時間の偏重度であるｉｆ−ｅｌｓｅ実行時間偏重度を算出する第６１のステップと、
前記ｉｆ−ｅｌｓｅ実行時間偏重度が所定の値以下である場合、前記ｉｆ−ｅｌｓｅ分岐命令が真となるときに実行される部分プログラムの実行時間に前記ｉｆ−ｅｌｓｅ分岐命令が真となる確率を乗算した値および前記ｉｆ−ｅｌｓｅ分岐命令が偽となるときに実行される部分プログラムの実行時間に前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率を乗算した値を加算する第６２のステップと、
前記ｉｆ−ｅｌｓｅ分岐命令が真となるときに実行される前記部分プログラムおよび前記ｉｆ−ｅｌｓｅ分岐命令が偽となるときに実行される前記部分プログラムを１つの部分プログラムとする縮退を行う第６３のステップと、
を行った後に、前記第５２のステップを行い、
前記ｉｆ−ｅｌｓｅ実行時間偏重度が所定の値より大きい場合、前記第６２のステップおよび前記第６３のステップを実行しないことを特徴とする請求項７に記載の実行時間推定方法。
【請求項９】
前記ｉｆ−ｅｌｓｅ実行時間偏重度は、前記ｉｆ−ｅｌｓｅ分岐命令が真であったときの部分プログラムの実行時間と、前記ｉｆ−ｅｌｓｅ分岐命令が偽であったときの部分プログラムの実行時間との差の絶対値に、前記ｉｆ−ｅｌｓｅ分岐命令の実行回数を乗算した値であることを特徴とする請求項８に記載の実行時間推定方法。
【請求項１０】
前記実行時間推定装置は、
前記第１のループ内の各ループにおける繰り返し回数の分散と、前記ループの繰り返し回数と、前記ループの平均実行時間とを乗算した値であるループ実行時間偏重度を算出する第７１のステップを行った後、
前記ループ実行時間偏重度が所定の値より大きい場合、前記第５２のステップを実行せず、
前記ループ実行時間偏重度が所定の値以下の場合、前記第５２のステップを実行することを特徴とする請求項７に記載の実行時間推定方法。
【請求項１１】
前記実行時間推定装置は、シングルプロセッサを搭載したコンピュータであることを特徴とする請求項１から請求項１０のいずれか一項に記載の実行時間推定方法。
【請求項１２】
前記実行時間推定装置は、マルチプロセッサを搭載したコンピュータであり、
複数のプログラムの実行時間の推定を並列に算出することを特徴とする請求項１から請求項１０のいずれか一項に記載の実行時間推定方法。
【請求項１３】
前記プログラムは、通信同期しつつ他のプログラムと連動して実行されるプログラムであり、
前記部分プログラムは、他のプログラムとの通信同期を指示するプログラムである通信同期部分プログラムを含み、
前記実行時間推定装置が、
前記分岐履歴ビット系列を基に、前記部分プログラムの実行系列を生成する際に、処理の対象となっている前記部分プログラムが前記通信同期部分プログラムである場合、前記通信同期部分プログラムの種類に応じて、前記マルチプロセッサを構成するプロセッサの実行状態を更新することを特徴とする請求項１２に記載の実行時間推定方法。
【請求項１４】
請求項１から請求項１１のいずれか一項に記載の実行時間推定方法をコンピュータに実行させるための実行時間推定プログラム。
【請求項１５】
請求項１２に記載の実行時間推定方法をコンピュータに実行させるための実行時間推定プログラム。
【請求項１６】
請求項１３に記載の実行時間推定方法をコンピュータに実行させるための実行時間推定プログラム。
【請求項１７】
プログラムの実行時間を推定する実行時間推定装置であって、
前記プログラムから、条件分岐命令および関数呼出命令の少なくとも１つを境界点として分割された部分プログラムを抽出するプログラム分割部と、
各部分プログラムの実行時間を算出し、前記各部分プログラムの先頭命令と、終端命令と、算出した部分プログラムの前記実行時間とを対応付けて記憶部に格納する部分プログラム実行時間推定算出部と、
前記プログラムを実行させたときの前記条件分岐命令についての真偽の系列である分岐履歴ビット系列を生成して、前記記憶部に格納する分岐履歴情報生成部と、
前記分岐履歴ビット系列を基に、前記部分プログラムの実行順番が記述されている部分プログラム実行系列を生成する実行トレース再生部と、
前記部分プログラム実行系列に基づいて、前記部分プログラムの実行時間を加算する実行時間推定算出部と、
を有することを特徴とする実行時間推定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムの実行時間を推定する実行時間推定方法、実行時間推定プログラムおよび実行時間推定装置に関する。
【背景技術】
【０００２】
プログラムの実行時間を推定する方法が複数提示されている（例えば、非特許文献１参照）。
このようなプログラムの実行時間を推定する方法の１つとして、命令セットシミュレータがある（例えば、非特許文献２〜非特許文献６参照）。また、予測実行時間情報をプログラム内に埋め込んだものを実行することによって実行時間を算出する方法（例えば、非特許文献７参照）や、プログラムの一部だけを実行し、この一部の実行時間からプログラム全体の実行時間を推定する方法（例えば、非特許文献８〜非特許文献１０参照）も提示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】J. J. Yi and D. J. Lilja. Simulation of Computer Architectures: Simulators, Benchmarks,  Methodologies, and Recommendations. IEEE Trans. Comput., 55(3), 2006.
【非特許文献２】A. Nohl, G. Braun, O. Schliebusch, R. Leupers, H. Meyr, and A. Hoffmann. A Universal Technique for Fast and Flexible Instruction-Set Architecture Simulation. In DAC ’02: Conference on Design automation, New York, NY, USA, 2002. ACM Press.
【非特許文献３】M. Poncino and J. Zhu. DynamoSim: A Trace-based Dynamically Compiled Instruction Set Simulator. In ICCAD ’04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, Washington, DC, USA, 2004. IEEE Computer Society.
【非特許文献４】W. Qin, J. D’Errico, and X. Zhu. A Multiprocessing Approach to Accelerate Retargetable and Portable Dynamic-compiled Instruction-set Simulation. In CODES+ISSS ’06: Conference on Hardware/Software Codesign and System Synthesis, New York, NY, USA, 2006. ACM Press.
【非特許文献５】M. Reshadi, P. Mishra, and N. Dutt. Instruction Set Compiled Simulation: A Technique for Fast and Flexible Instruction Set Simulation. In DAC ’03: Conference on Design Automation, New York, NY, USA, 2003. ACM Press.
【非特許文献６】HySim: A Fast Simulation Framework for Embedded Software Development Stefan Kraemer, Lei Gao, Jan Weinstock, Rainer Leupers, Gerd Ascheid and Heinrich Meyr In CODES+ISSS ’07: Conferenceon Hardware/Software Codesign and System Synthesis, New York, NY, USA, 2007. ACM Press.
【非特許文献７】T. Kempf, K. Karuri, S. Wallentowitz, G. Ascheid, R. Leupers, and H. Meyr. A SW Performance Estimation Framework for Early System-Level-Design using Fine-Grained Instrumentation. In DATE ’06: Conference on Design, Automation and Test in Europe, 3001 Leuven, Belgium, Belgium, 2006. European Design and Automation Association.
【非特許文献８】T. Sherwood, E. Perelman, G. Hamerly, and B. Calder. Automatically Characterizing Large Scale Program Behavior. In ASPLOS-X: Proceedings of the 10th international conference on Architectural Support for Programming Languages and Operating Systems, New York, NY, USA, 2002. ACM Press.
【非特許文献９】T. Sherwood, E. Perelman, G. Hamerly, S. Sair, and B. Calder. Discovering and Exploiting Program Phases. IEEE Micro, December 2003.
【非特許文献１０】R. Wunderlich, T. Wenisch, B. Falsafi, and J. Hoe. SMARTS: Accelerating Microarchitecture Simulation via Rigorous Statistical Sampling. In 30th Annual International Symposium on Computer Architecture, June 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献２〜非特許文献６に記載の命令セットシミュレータは、正確な実行時間の推定値が算出されるが、シミュレーションの実行時間が長くなるという問題がある。また、非特許文献７〜非特許文献１０に記載された方法では、シミュレーションの実行時間を短くすることができるが、推定値の精度が低くなるという問題がある。【０００５】
そこで、本発明は、短い処理時間で正確なプログラムの実行時間推定を実現することを目的とする。
【課題を解決するための手段】
【０００６】
前記課題を解決するために、実行時間推定方法は、プログラムの実行時間を推定する実行時間推定装置による実行時間推定方法であって、前記実行時間推定装置が、前記プログラムから、条件分岐命令および関数呼出命令の少なくとも１つを境界点として分割された部分プログラムを抽出する第１のステップと、各部分プログラムの実行時間を算出して、記憶部に格納する第２のステップと、前記各部分プログラムの先頭命令と、終端命令と、算出した部分プログラムの前記実行時間とを対応付けて前記記憶部に格納する第３のステップと、前記プログラムを実行させたときの前記条件分岐命令についての真偽の系列である分岐履歴ビット系列を生成して、前記記憶部に格納する第４のステップと、前記分岐履歴ビット系列を基に、前記部分プログラムの実行順番が記述されている部分プログラム実行系列を生成する第５のステップと、前記部分プログラム実行系列に基づいて、前記部分プログラムの実行時間を加算する第６のステップと、を行うことを特徴とする。
【０００７】
かかる構成によれば、算出された実行時間推定値は、高い精度で算出された部分プログラムの実行時間を加算するため、プログラムの実行時間を高い精度で推定することができる。さらに、生成される分岐履歴ビット系列はプログラム実行命令数に比べて著しく少ないことから、実際のプログラム実行時間よりもはるかに短い処理時間で実行時間の推定を行うことができる。【０００８】
また、前記記憶部は、第１の記憶部と、第２の記憶部とからなり、前記実行時間推定方法において、前記第２のステップ終了後、前記部分プログラムが、所定回数繰り返されるループである場合、前記ループ内部に、前記ループを継続するか否かを決定する分岐であるループ継続条件命令以外の条件分岐命令を含まず、かつ前記ループにおける部分プログラムの繰り返し回数が、前記プログラム中において不変であるとき、前記ループ内の部分プログラムの実行時間に、前記繰り返し回数を乗算してループ実行時間を算出し、前記算出したループ実行時間を１つの前記部分プログラムの実行時間とする縮退を行う第６のステップを行った後、前記第３のステップを行い、前記第４のステップにおいて、前記第１の記憶部に前記分岐履歴ビット系列を格納した後、前記縮退を行ったループに該当する部分プログラムに関連する前記真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納すること、を行うことを特徴とする。
【０００９】
かかる構成によれば、同じ部分プログラムが繰り返されるループを１つの部分プログラムとしてまとめて扱うことができるため、短い処理時間でプログラムの実行時間を推定することが可能となる。【００１０】
また、前記記憶部は、第１の記憶部と、第２の記憶部とからなり、前記実行時間推定方法において、前記部分プログラムが、所定回数繰り返されるループである場合、前記ループ内部に、前記ループを継続するか否かを決定する分岐であるループ継続条件命令以外の条件分岐命令を含まず、かつ前記ループにおける部分プログラムの繰り返し回数が、個々の前記ループ中で不変であるとき、前記第３のステップにおいて、各ループの繰り返し回数の系列を生成する第１１のステップと、前記ループ内の部分プログラムの実行時間に、前記繰り返し回数の系列における繰り返し回数を乗算したループの実行時間を算出する第１２のステップと、前記算出した各ループの実行時間を加算する第１３のステップと、を行い、前記第４のステップにおいて、前記第１の記憶部に前記分岐履歴ビット系列を格納した後、前記ループに該当する部分プログラムに関連する前記真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納すること、を行うことを特徴とする。
【００１１】
かかる構成によれば、ループ外で繰り返し回数が変更されるおそれがあるために、１つの部分プログラムとしてまとめて扱うことが困難なループも、繰り返し回数の系列などを基に他の部分プログラムとは別にループの実行時間を推定することができる。これにより、１つの部分プログラムとして扱うことが可能となり、短い処理時間でプログラムの実行時間を推定することが可能となる。【００１２】
また、前記実行時間推定方法は、前記第４のステップ終了後に前記部分プログラムが、所定回数繰り返されるループである場合、前記ループ内部に、ｉｆ−ｅｌｓｅ分岐命令を含むとき、前記ｉｆ−ｅｌｓｅ分岐命令が真となる確率および前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率を算出する第２１のステップと、前記ｉｆ−ｅｌｓｅ分岐命令が真となるときに実行される部分プログラムの実行時間に前記ｉｆ−ｅｌｓｅ分岐命令が真となる確率を乗算した値および前記ｉｆ−ｅｌｓｅ分岐命令が偽となるときに実行される部分プログラムの実行時間に前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率を乗算した値を加算する第２２のステップと、前記ｉｆ−ｅｌｓｅ分岐命令が真となるときに実行される前記部分プログラムおよび前記ｉｆ−ｅｌｓｅ分岐命令が偽となるときに実行される前記部分プログラムを１つの部分プログラムとする縮退を行う第２３のステップと、前記第４のステップにおいて前記第１の記憶部に格納された前記分岐履歴ビット系列から、前記縮退が行われた部分プログラムに関連する前記真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納する第２４のステップと、を行うことを特徴とする。
【００１３】
かかる構成によれば、ループ内部にｉｆ−ｅｌｓｅ分岐命令が含まれるため、ループを１つの部分プログラムにまとめることが困難な場合においても、ｉｆ−ｅｌｓｅ分岐命令の真偽に伴って実行される部分プログラムを１つにまとめることによって内部にｉｆ−ｅｌｓｅ分岐命令が含まれるループを１つの部分プログラムにまとめることが可能となる。【００１４】
また、前記記憶部は、第１の記憶部と、第２の記憶部とからなり、前記第４のステップにおいて、生成された分岐履歴ビット系列が、前記第１の記憶部に格納され、前記実行時間推定方法において、前記部分プログラムが、所定回数繰り返されるループで構成される多重ループであり、前記多重ループにおける各ループは、前記ループを継続するか否かを決定する分岐であるループ継続条件命令を１つ含むループのみで構成されており、前記第４のステップ終了後に、前記多重ループ内に、ループ継続条件命令とは異なる条件分岐命令であるｉｆ−ｅｌｓｅ分岐命令が含まれている場合、当該ループ内におけるｉｆ−ｅｌｓｅ分岐命令が真となる確率と、前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率とを算出する第３１のステップと、前記確率を基に、前記ループの平均実行時間を内側のループから順に算出し、前記算出した前記ループの平均実行時間を１つの前記部分プログラムの実行時間とする縮退を行う第３２のステップと、前記第４のステップにおいて前記第１の記憶部に格納された前記分岐履歴ビット系列から、前記縮退を行ったループに該当する真偽の系列の記述を削除した前記分岐履歴ビット系列を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納する第３３のステップと、を行った後、前記第５のステップを行うことを特徴とする。
【００１５】
かかる構成によれば、ループの内部にループが含まれる多重ループであるために、多重ループのブロックを１つの部分プログラムにまとめることが困難な場合においても、ループ毎の平均実行時間を、多重ループの内側からループ順に求めていくことで、多重ループも１つの部分プログラムとしてまとめることが可能となる。【００１６】
前記記憶部は、第１の記憶部と、第２の記憶部とからなり、前記第４のステップにおいて、生成された分岐履歴ビット系列が、前記第１の記憶部に格納され、前記第４のステップ終了後に前記部分プログラムを複数有する関数において、前記部分プログラムの出現頻度を算出する第４１のステップと、前記算出した部分プログラムの前記実行時間と、前記部分プログラムの出現頻度と、を乗算することによって、前記関数内における前記部分プログラムの全実行時間推定値を算出する第４２のステップと、前記関数内の前記部分プログラムについて、前記部分プログラムの全実行時間推定値の総和を算出することによって関数の全実行時間推定値を算出する第４３のステップと、前記第４のステップにおいて前記第１の記憶部に格納された前記分岐履歴ビット系列から、前記全実行時間推定値を算出した関数に該当する真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納する第４４のステップと、を行った後、前記第５のステップを行うことを特徴とする。
【００１７】
かかる構成によれば、再帰関数呼び出し（例えば関数内で自分自身の関数を呼び出すケースなど）が存在しないプログラムであれば、必ず全プログラムを１つの部分プログラムに縮退することができる。【００１８】
また、前記記憶部は、第１の記憶部と、第２の記憶部とからなり、前記実行時間推定方法は、前記部分プログラムが所定回数繰り返されるループである場合、前記第４のステップにおいて、生成された分岐履歴ビット系列を、前記第１の記憶部に格納し、前記第４のステップ終了後に、前記ループのうち、第１のループが、所定回数繰り返されるループで構成される多重ループであり、前記多重ループにおける各ループは、前記ループを継続するか否かを決定する分岐であるループ継続条件命令を１つ含むループのみで構成されており、記第１のループが前記プログラムにおいて、少なくとも１つ存在する場合、当該第１のループ内部に、前記ループ継続条件命令とは異なる条件分岐命令であるｉｆ−ｅｌｓｅ分岐命令が含まれる場合、前記ｉｆ−ｅｌｓｅ分岐命令が真となる確率と、前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率とを算出する第５１のステップと、前記確率を基に、前記第１のループの平均実行時間を内側のループから順に算出し、前記算出した第１のループの平均実行時間を１つの前記部分プログラムの実行時間とする縮退を行う第５２のステップと、第２のループは、前記第２のループ内部に、前記ループを継続するか否かを決定する分岐であるループ継続条件命令以外の条件分岐命令を含まず、かつ繰り返し回数が、個々の前記第２のループ中で不変であるループであり、前記第２のループが前記プログラムにおいて、少なくとも１つ存在する場合、各前記第２のループにおける部分プログラムの繰り返し回数の系列を生成する第５３のステップと、前記第２のループに該当する部分プログラムの実行時間に、前記繰り返し回数の系列における繰り返し回数を乗算したループの実行時間推定値を算出する第５４のステップと、前記算出した各第２のループの実行時間推定値を加算する第５５のステップと、前記第４のステップにおいて前記第１の記憶部に格納された前記分岐履歴ビット系列から、前記第１のループおよび前記第２のループに該当する真偽の系列の記述を削除した前記分岐履歴ビット系列を前記第２の記憶部へ格納する第５６のステップと、を行った後、前記第５のステップを行うことを特徴とする。
【００１９】
かかる構成によれば、ｉｆ−ｅｌｓｅ分岐ブロックを１つの部分プログラムにまとめる処理と、ループを１つの部分プログラムにまとめることができ、短い処理時間でプログラムの実行時間を推定することが可能となる。【００２０】
また、前記実行時間推定方法は、前記第５１のステップ終了後に、ｉｆ−ｅｌｓｅ分岐命令の真偽による部分プログラムの実行時間の偏重度であるｉｆ−ｅｌｓｅ実行時間偏重度を算出する第６１のステップと、前記ｉｆ−ｅｌｓｅ実行時間偏重度が所定の値以下である場合、前記ｉｆ−ｅｌｓｅ分岐命令が真となるときに実行される部分プログラムの実行時間に前記ｉｆ−ｅｌｓｅ分岐命令が真となる確率を乗算した値および前記ｉｆ−ｅｌｓｅ分岐命令が偽となるときに実行される部分プログラムの実行時間に前記ｉｆ−ｅｌｓｅ分岐命令が偽となる確率を乗算した値を加算する第６２のステップと、前記ｉｆ−ｅｌｓｅ分岐命令が真となるときに実行される前記部分プログラムおよび前記ｉｆ−ｅｌｓｅ分岐命令が偽となるときに実行される前記部分プログラムを１つの部分プログラムとする縮退を行う第６３のステップと、を行った後に、前記第５２のステップを行い、前記ｉｆ−ｅｌｓｅ実行時間偏重度が所定の値より大きい場合、前記第６２のステップおよび前記第６３のステップを実行しないことを特徴とする。
【００２１】
かかる構成によれば、確率を用いることによる部分プログラムの実行時間のゆらぎの影響の消失を抑止することが可能となり、局所的なプログラム実行時間を確認することができる。【００２２】
また、前記実行時間推定方法において、前記ｉｆ−ｅｌｓｅ実行時間偏重度は、前記ｉｆ−ｅｌｓｅ分岐命令が真であったときの部分プログラムの実行時間と、前記ｉｆ−ｅｌｓｅ分岐命令が偽であったときの部分プログラムの実行時間との差の絶対値に、前記ｉｆ−ｅｌｓｅ分岐命令の実行回数を乗算した値であることを特徴とする。【００２３】
かかる構成によれば、実行時間偏重度を正確に算出することが可能となる。【００２４】
また、前記実行時間推定方法において、前記第１のループ内の各ループにおける繰り返し回数の分散と、前記ループの繰り返し回数と、前記ループの平均実行時間とを乗算した値であるループ実行時間偏重度を算出する第７１のステップを行った後、前記ループ実行時間偏重度が所定の値より大きい場合、前記第５２のステップを実行せず、前記ループ実行時間偏重度が所定の値以下の場合、前記第５２のステップを実行することを特徴とする。
【００２５】
かかる構成によれば、ループの平均実行時間を用いることによるループの実行時間のゆらぎの影響の消失を抑止することが可能となる。
また、かかる構成によれば、ループ実行時間偏重度を正確に算出することが可能となる。
【００２８】
また、前記実行時間推定装置は、シングルプロセッサを搭載したコンピュータであることを特徴とする。【００２９】
かかる構成によれば、前記実行時間推定方法をシングルプロセッサで実現することが可能となり、汎用性を高めることができる。【００３０】
また、前記実行時間推定方法において、前記実行時間推定装置は、マルチプロセッサを搭載したコンピュータであり、複数のプログラムの実行時間の推定を並列に算出することを特徴とする。【００３１】
かかる構成によれば、前記実行時間推定方法をマルチプロセッサで実現することが可能となり、複数のプログラムの実行時間の推定を並列に処理することが可能となり、高速化を実現することができる。【００３２】
また、前記実行時間推定方法において、前記プログラムは、通信同期しつつ他のプログラムと連動して実行されるプログラムであり、前記部分プログラムは、他のプログラムとの通信同期を指示するプログラムである通信同期部分プログラムを含み、前記実行時間推定装置が、前記分岐履歴ビット系列を基に、前記部分プログラムの実行系列を生成する際に、処理の対象となっている前記部分プログラムが前記通信同期部分プログラムである場合、前記通信同期部分プログラムの種類に応じて、前記マルチプロセッサを構成するプロセッサの実行状態を更新することを特徴とする。【００３３】
かかる構成によれば、複数のプロセスによって構成されるプログラムの実行時間の推定が、プロセス間の通信同期を忠実に再現しつつ行うことが可能となる。【００３４】
前記実行時間推定方法を、コンピュータに実行させるための実行時間推定プログラムとした。
【００３５】
かかる構成によれば、前記実行時間推定方法をコンピュータに実行させるプログラムを提供することができる。【００３６】
また、プログラムの実行時間を推定する実行時間推定装置であって、前記プログラムから、条件分岐命令および関数呼出命令の少なくとも１つを境界点として分割された部分プログラムを抽出するプログラム分割部と、各部分プログラムの実行時間を算出し、前記各部分プログラムの先頭命令と、終端命令と、算出した部分プログラムの前記実行時間とを対応付けて記憶部に格納する部分プログラム実行時間推定算出部と、前記プログラムを実行させたときの前記条件分岐命令についての真偽の系列である分岐履歴ビット系列を生成して、前記記憶部に格納する分岐履歴情報生成部と、前記分岐履歴ビット系列を基に、前記部分プログラムの実行順番が記述されている部分プログラム実行系列を生成する実行トレース再生部と、前記部分プログラム実行系列に基づいて、前記部分プログラムの実行時間を加算する実行時間推定算出部と、を有することを特徴とする。
【００３７】
かかる構成によれば、算出された実行時間推定値は、高い精度で算出された部分プログラムの実行時間を加算するため、プログラムの実行時間を高い精度で推定することができる。さらに、生成される分岐履歴ビット系列はプログラム実行命令数に比べて著しく少ないことから、実際のプログラム実行時間よりもはるかに短い処理時間で実行時間の推定を行うことができる。
【発明の効果】
【００３８】
本発明によれば、短い処理時間で正確なプログラムの実行時間推定を実現することが可能となる。
【図面の簡単な説明】
【００３９】
【図１】第１実施形態に係る実行時間推定装置の構成例を示す図である。
【図２】本実施形態に係る実行時間推定装置のハードウェア構成の例を示す図である。
【図３】第１実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。
【図４】第１実施形態に係る対象プログラムの例である。
【図５】第１実施形態に係る部分プログラムテーブルの例を示す図である。
【図６】分岐履歴ビット系列を出力するためのファイル入出力関数の例を示す図である。
【図７】図４における対象プログラムの一部を示す図である。
【図８】図７に示すプログラムを書き換えた後のプログラムの例を示す図である。
【図９】第２実施形態に係る実行時間推定装置の構成例を示す図である。
【図１０】第２実施形態に係るプログラム実行時間推定方法の処理の流れを示すフローチャートである。
【図１１】第２実施形態に係るループ情報抽出処理の流れを示すフローチャートである。
【図１２】ある対象プログラムにおけるループに関する図であり、（ａ）は、あるループの構造を模式化した図であり、（ｂ）は、（ａ）に示すような構造を有するループから生成される部分プログラムの構成の例を示す表である。
【図１３】第２実施形態において用いられる部分プログラムテーブルの例である。
【図１４】第１種ループの縮退を説明するための図であり、（ａ）は、縮退前の部分プログラムテーブルであり、（ｂ）は、縮退後の部分プログラムテーブルである。
【図１５】第２実施形態に係るプログラム実行履歴情報生成処理の流れを示すフローチャートである。
【図１６】第２種ループ回数データ系列を生成するための対象プログラムの書き換え例を示す図であり、（ａ）は書き換え前、（ｂ）は書き換え後、（ｃ）は第２種ループ回数データ系列および分岐履歴ビット系列を生成する関数を示す。
【図１７】第２種ループ実行時間推定算出部の処理を具体的に説明するための図である。
【図１８】第３実施形態に係る実行時間推定装置の構成例を示す図である。
【図１９】第３実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。
【図２０】第３実施形態に係る分岐確率情報抽出処理の流れを示すフローチャートである。
【図２１】第３種ループの他の例を含む対象プログラムを示す図である。
【図２２】図２１に示す対象プログラムから生成される部分プログラムテーブルの例を示す図である
【図２３】第３実施形態に係る多重ｉｆ−ｅｌｓｅ縮退処理の流れを示す図である。
【図２４】第３種ループを含む対象プログラムの例を示す図であり、
【図２５】図２４に示す対象プログラムから生成される部分プログラムテーブルの例を示す図である。
【図２６】縮退処理を行った部分プログラムテーブルの例であり、（ａ）は「Ｊ」に対するｉｆ−ｅｌｓｅ縮退処理を行った結果を示し、（ｂ）は（ａ）の結果に対して隣接縮退処理を行った結果であり、（ｃ）は「Ｈ」に対するｉｆ−ｅｌｓｅ縮退処理を行った結果であり、（ｄ）は（ｃ）の結果に対して隣接縮退処理を行った結果である。
【図２７】第４実施形態に係る実行時間推定装置の構成例を示す図である。
【図２８】第４種ループを含む対象プログラムの例を示す図である。
【図２９】第４実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。
【図３０】第４実施形態に係る多重ループ縮退処理の流れを示す図である。
【図３１】図２８に示す対象プログラムから生成される部分プログラムテーブルの例を示す図である。
【図３２】条件変数の分岐確率の表を示す図である。
【図３３】第４種ループ縮退処理が行われた部分プログラムテーブルの例を示す図であり、（ａ）はｉｆ−ｅｌｓｅ縮退処理が行われた例、（ｂ）は（ａ）の結果に隣接縮退処理を行った例を示す。
【図３４】図３３（ｂ）に示す部分プログラムテーブルに対し縮退処理を行った例であり、（ａ）は図３３（ｂ）の結果にループ縮退処理を行った例、（ｂ）は（ａ）の結果に隣接縮退処理を行った例、（ｃ）は（ｂ）の結果にループ縮退処理を行った例、（ｄ）は（ｃ）の結果に隣接縮退処理を行った例である。
【図３５】第５実施形態に係る実行時間推定装置の構成例を示す図である。
【図３６】ループ内に「ｂｒｅａｋ」文および「ｒｅｔｕｒｎ」文を含む対象プログラムの例を示す図である。
【図３７】第５実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。
【図３８】部分プログラム実行頻度の情報を記述した部分プログラムテーブルの例を示す図である。
【図３９】図３８に示す部分プログラムテーブルに対し縮退処理をを行った例であり、（ａ）は、関数ｆｕｎｃ４縮退処理を行った例、（ｂ）は、部分プログラム「６３」の縮退処理を行った例、（ｃ）は、縮退後の最終的な部分プログラムテーブルの例である。
【図４０】対象プログラムにおけるコードを繰り返し実行した際のコード実行時間を示す模式図であり、（ａ）は、第２実施形態を適用した例、（ｂ）は、第４実施形態を適用した例である。
【図４１】第６実施形態に係る実行時間推定装置の構成例を示す図である。
【図４２】第６実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。
【図４３】ステップＳ５０３およびステップＳ５０４における処理の結果、生成される部分プログラムテーブルの例を示す図である。
【図４４】第６実施形態に係る多重ループ縮退処理の流れを示すフローチャートである。
【図４５】比較例として命令セットシミュレータを用いた実験結果を示す表である。
【図４６】第１実施形態に係る実験結果を示す例である。
【図４７】第４実施形態に係る実験結果を示す表である。
【図４８】第１〜第４，第６実施形態に係る実験結果をまとめた表である。
【図４９】第１〜第４，第６実施形態における実験結果を示すグラフである。
【図５０】第７実施形態に係る実行時間推定装置の構成例を示す図である。
【図５１】第７実施形態に係る実行時間推定装置のハードウェア構成を示す図である。
【図５２】第７実施形態に係る前処理部の詳細な構成例を示す図である。
【図５３】第７実施形態に係る後処理部の詳細な構成例を示す図である。
【図５４】第７実施形態に係る後処理部における処理の流れを示すフローチャートである。
【図５５】プロセッサの実行可能状態から実行待機状態へ遷移する条件を示した表である。
【図５６】通信同期リソース状態情報の更新内容と、実行待機状態であるプロセッサの実行可能状態への復帰条件とを示した表である。
【図５７】比較例として命令セットシミュレータを用いた実験結果を示す表である。
【図５８】第７実施形態に係る実験結果を示す例である。
【図５９】局所タイミング再生精度の比較を示すグラフである。
【発明を実施するための形態】
【００４０】
次に、本発明を実施するための最良の形態（以降、「実施形態」と称す）について、適宜図面を参照しながら詳細に説明する。なお、本実施形態において、ブロックとは、ループや、ｉｆ−ｅｌｓｅ分岐命令などが支配するプログラム範囲を示すこととする。例えば、ループブロック中には、ｉｆ−ｅｌｓｅ命令や、ループなどが含まれる場合があるし、ｉｆ−ｅｌｓｅブロック中には、他のｉｆ−ｅｌｓｅ命令などが含まれることとなる。以下、必要に応じて適宜「ブロック」の語を使用することとする。なお、ｉｆ−ｅｌｓｅブロックは、ｉｆ文が支配する範囲と、ｅｌｓｅ文が支配する範囲を含むこととする。
【００４１】
（第１実施形態：構成）
図１は、第１実施形態に係る実行時間推定装置の構成例を示す図である。
実行時間推定装置１ａ（１）は、プログラム分割部１１、部分プログラム実行時間推定算出部１２、分岐履歴情報生成部１３、実行トレース再生部１４および実行時間推定算出部１５を有してなる。以下、実行時間推定装置１ａにおける各部の概略を説明するが、詳細な処理の内容は、図３〜図８を参照して説明する。
プログラム分割部１１は、実行時間推定の対象となっているプログラム（以下、対象プログラムと記載）を、条件分岐命令および関数呼出命令を境界点として複数の部分プログラムに分割し、それぞれの部分プログラムをテーブル内に示した部分プログラムテーブルを生成する機能を有する。部分プログラムテーブルについては、図５を参照して後記する。なお、本実施形態では、条件分岐命令とは、ｉｆ−ｅｌｓｅ分岐命令や、ｆｏｒ文において、ループを継続するか否かの条件命令であるループ継続条件命令を含むものとする。
部分プログラム実行時間推定算出部１２は、プログラム分割部１１が生成した部分プログラムのそれぞれについて実行時間（部分プログラム実行時間推定値）を算出し、算出した部分プログラム実行時間推定値を部分プログラムテーブルに追加する機能を有する。さらに、部分プログラム実行時間推定算出部１２は、部分プログラム実行時間推定値が追加済みの部分プログラムテーブルを実行トレース再生部１４や実行時間推定算出部１５へ送る機能を有する。
分岐履歴情報生成部１３は、対象プログラム内の条件分岐命令における条件変数の真偽値（「１」および「０」の２値表現）の系列である分岐履歴ビット系列を生成し、実行時間推定算出部１５へ送る機能を有する。
【００４２】
実行トレース再生部１４は、部分プログラム実行時間推定算出部１２から送られた、部分プログラム実行時間推定値が追加済みの部分プログラムテーブルと、分岐履歴情報生成部１３が生成した分岐履歴ビット系列とを基に、部分プログラムの実行順に部分プログラムの実行時間推定値を部分プログラムテーブルから読み出し、読み出した部分プログラム実行時間推定値を、逐次実行時間推定算出部１５へ送る機能を有する。
実行時間推定算出部１５は、実行トレース再生部１４がから送られた部分プログラム実行時間推定値を逐次加算することによって、対象プログラム全体の実行時間を推定する機能を有する。
【００４３】
図２は、本実施形態に係る実行時間推定装置のハードウェア構成の例を示す図である。
図２に示すハードウェア構成は、図１に示す実行時間推定装置１ａのハードウェア構成でもよいし、図９、図１８、図２７、図３５、図４１に示す実行時間推定装置１ｂ〜１e，１ｇのハードウェア構成でもよい。
実行時間推定装置１は、ＣＰＵ（Central Processing Unit）１５１、ＲＯＭ（Read Only Memory）１５２、ＲＡＭ（Random Access Memory）１５３およびＥＥＰＲＯＭ（Electrically Erasable and Programmable Read Only Memory）１５４を備え、これらがバス１６１を介して、互いに接続されている。さらに、実行時間推定装置１は、ディスプレイなどの出力部１５５、キーボードや、マウスなどの入力部１５６、ＮＩＣ（Network Interface Card）などの通信インタフェースである通信部１５７、およびリムーバブル記録媒体１５９から情報を読み出すドライブ１５８が入出力インタフェース１６０に接続している。入出力インタフェース１６０は、バス１６１に接続されることによって、出力部１５５、入力部１５６、通信部１５７およびドライブ１５８と、ＣＰＵ１５１、ＲＯＭ１５２、ＲＡＭ１５３およびＥＥＰＲＯＭ１５４との間の情報の流れを制御している。なお、本実施形態では、ＲＡＭ１５３や、ドライブ１５８とリムーバブル記録媒体１５９とを合わせた装置などを記憶装置１７０と記載する。
【００４４】
図１に示す各部１１〜１５は、記憶装置１７０などに記憶されている実行時間推定プログラムが、ＲＡＭ１５３に展開され、ＣＰＵ１５１が実行することによって具現化する。
【００４５】
次に、図１を参照しつつ、図３に沿って本実施形態に係るプログラム実行時間推定方法を説明する。
図３は、第１実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。
【００４６】
（プログラム分割処理）
まず、プログラム分割部１１が、プログラム分割処理を行って（Ｓ１０１）、対象プログラムを部分プログラムに分割する。部分プログラムとは、条件分岐命令および関数呼出命令を境界点とし、内部に条件分岐命令や、関数呼出命令を含まない実行命令系列である。
【００４７】
＜＜プログラム分割の実際＞＞
図４は、第１実施形態に係る対象プログラムの例である。
図４に示す対象プログラムには、条件変数「Ａ」、「Ｂ」、「Ｃ」、「Ｄ」および「Ｅ」に係る５つの条件分岐命令がある。
プログラム分割部１１が、図４に示す対象プログラムに対して図３のステップＳ１０１におけるプログラム分割処理を行うと図５に示す部分プログラムテーブルを出力する。
【００４８】
＜部分プログラムテーブル＞
以下、図４を参照しつつ図５における部分プログラムテーブルについて説明する。
図５は、第１実施形態に係る部分プログラムテーブルの例を示す図である。
部分プログラムテーブルは、「部分プログラムＩＤ（Identification）」（以下、部分プログラムテーブルの図面内では「ＩＤ」と記載する）、「部分プログラム先頭命令」、「部分プログラム終端命令」および「部分プログラム実行時間推定値」をそれぞれフィールド（列）として有する。なお、部分プログラムテーブルは、プログラム分割部１１によって生成されるとＲＡＭ１５３（図２）などの記憶装置１７０（図２）に格納されるデータである。
「部分プログラムＩＤ」は、部分プログラム分割部１１によって部分プログラム毎に一意に付されるＩＤである。
「部分プログラム先頭命令」は、それぞれの部分プログラムにおける先頭の命令を記述するフィールドである。
例えば、図５の部分プログラムＩＤ「１」に該当する部分プログラム（以下、部分プログラムＩＤ「ｎ」に該当する部分プログラムを部分プログラム「ｎ」と記載する）における「ｍａｉｎ：ｓｔａｒｔ」、および部分プログラム「８」における「ｆｕｎｃ１：ｓｔａｒｔ」はそれぞれの関数（ｍａｉｎ関数およびｆｕｎｃ１関数）の最初の命令を表す。また、部分プログラム「２」における「ｂｒａｎｃｈ（Ａ）［Ｔ］」は、図４における条件変数「Ａ」が「真」の値のときの条件分岐命令を表し、部分プログラム「３」における「ｂｒａｎｃｈ（Ａ）［Ｆ］」は図４における条件変数「Ａ」が「偽」の値のときの条件分岐命令を表す。
【００４９】
「部分プログラム終端命令」は、それぞれの部分プログラムの終端の命令を記述するフィールドである。
例えば、部分プログラム「１」を参照すると、「ｂｒａｎｃｈ（Ａ）」が部分プログラムの終端命令であることがわかる。すなわち、部分プログラム「１」は、「ｍａｉｎ：ｓｔａｒｔ」（部分プログラム先頭命令）から「ｂｒａｎｃｈ（Ａ）」（部分プログラム終端命令）までであることがわかる。同様に、部分プログラム「２」は、「ｂｒａｎｃｈ（Ａ）」が「真」の値を有するときから、ｂｒａｎｃｈ（Ｂ）までである。
【００５０】
なお、部分プログラム「６」の「部分プログラム終端命令」における「ｆｕｎｃ１：ｓｔａｒｔ  ｜  ｂｒａｎｃｈ（Ａ）」のように、命令が複数個記載されている（「｜」の記号で分けられている）場合、「部分プログラム先頭命令」に記載されている関数から呼び出し関数「ｆｕｎｃ１」の最初の命令「ｆｕｎｃ１：ｓｔａｒｔ」へ制御が移り、関数「ｆｕｎｃ１」の実行が終了した後（すなわち、「ｆｕｎｃ１：ｅｎｄ」に到達した後）に最終的にｂｒａｎｃｈ（Ａ）に到達することを表す。
【００５１】
なお、図５における「部分プログラム実行時間推定値」は、部分プログラム実行時間推定算出部１２によってステップＳ１０２で算出される部分プログラムの実行時間の推定値であり、ステップＳ１０１の段階においてこのフィールドは空欄となっている。
【００５２】
（部分プログラム実行時間推定算出処理）
図３に戻り、ステップＳ１０１の次に、部分プログラム実行時間推定算出部１２が、部分プログラム実行時間推定算出処理を行う（Ｓ１０２）。
【００５３】
ステップＳ１０２において部分プログラム実行時間推定算出部１２は、ステップＳ１０１において生成された各部分プログラムの対象プロセッサ上の実行時間の推定値を算出する。なお、部分プログラム実行時間推定算出部１２は、部分プログラムを実際に実行することで部分プログラムの実行時間を算出する。ここで、対象プログラムにおいて繰り返し生じる部分プログラムに関しては、１回分の実行時間を算出すればよいので、対象プログラムをそのまま実行時間推定する方法に比べ、はるかに短い時間でステップＳ１０２を終了することができる。例えば、「α」という部分プログラムが、ループや、条件分岐命令などによって複数回実行されるような状態でも、ステップＳ１０２では、「α」１回分の実行時間を算出すればよい。なお、対象プログラムの実行機械コードを生成するコンパイラが既に存在する場合、各分割プログラムの処理時間は、内部に条件分岐命令や関数呼出しを含まないため、高精度に推定することができる。また、対象プロセッサ専用のコンパイラが未開発の場合、各分割プログラムの処理時間は、各命令の実行時間の予測値を対象プロセッサの構造的特徴から算出し（各演算命令の実行時間やメモリアクセス時間）、これら予測値から実行時間の推定値が算出される。
【００５４】
部分プログラム実行時間推定算出部１２は、算出した部分プログラム実行時間推定値を図５の部分プログラムテーブルの「部分プログラム実行時間推定値」のフィールドに書き込む。
ここで、図５の「部分プログラム実行時間推定値」のフィールドは、該当する部分プログラムの先頭命令から終端命令までの実行時間を表す。例えば、部分プログラム「１」における「Ｔ１」は、「ｍａｉｎ：ｓｔａｒｔ」から「ｂｒａｎｃｈ（Ａ）」までの実行時間を示し、この中には「コード領域１」や、「ｉ＝０」および「ｉ＜Ｎ」（図４）といった演算命令を含む。
また、部分プログラム「４」における「Ｔ４」は条件「Ｂ」が「真」の場合の分岐命令から「ｂｒａｎｃｈ（Ａ）」までの実行時間を示し、その中には「コード領域２」や、「コード領域３」や、「ｉ＋＋」、「ｉ＜Ｎ」（図４）といった演算命令を含む。
【００５５】
なお、図５における部分プログラム「６」における「Ｔ６ａ」は、条件「Ｃ」が「真」の場合の分岐命令から呼び出し関数「ｆｕｎｃ１」の開始命令「ｆｕｎｃ１：ｓｔａｒｔ」までの実行時間を示す。
同じく部分プログラム「６」における「Ｔ６ｂ」は、関数「ｆｕｎｃ１」から制御が「ｍａｉｎ」に戻った後から「ｂｒａｎｃｈ（Ａ）」までの実行時間を示し、その中には「コード領域３」や、「ｉ＋＋」および「ｉ＜Ｎ」（図４）といった演算命令を含む。
【００５６】
（分岐履歴情報生成処理）
図３に戻り、ステップＳ１０２の処理が終了すると、分岐履歴情報生成部１３が、分岐履歴情報生成処理を行う（Ｓ１０３）。
ステップＳ１０３において分岐履歴情報生成部１３は、対象プログラムを実行し、対象プログラムを実行した際におけるすべての条件分岐命令における「真」および「偽」を１ビット情報で表現し、この１ビット情報を実行された順序で結合して生成される分岐履歴ビット系列をＲＡＭ１５３などの記憶装置１７０に格納する。分岐履歴ビット系列は、例えば「真」が「１」、「偽」が「０」で表現された「１１１０１１１０１０」のような１ビット情報の系列となる。
【００５７】
対象プログラムにおける条件分岐命令実行数は、全命令実行数のうちの数％程度であり、しかも分岐条件の実行結果を１ビットで表現できるため、非常に長い対象プログラムを実行した場合でも比較的少ないデータ容量で分岐履歴ビット系列を表現できる。そのため、ハードディスクのように非常に大きい遅延時間を伴う情報記憶媒体への保存においても、プログラム実行履歴情報を保存するためのオーバーヘッド時間を大幅に短縮する効果がある。さらに、分岐履歴情報生成部１３は、条件変数の真偽値を１ビットずつハードディスクなどの外部記憶装置に直接記録するのではなく、内部レジスタ、キャッシュメモリ、主記憶装置（メインメモリ）等のメモリ階層を介することにより、最終的に外部記憶装置（ハードディスクなど）に分岐履歴情報を保存するため、逐次的にハードディスクに保存する場合と比較して、遅延時間を短縮することができる。
【００５８】
＜＜分岐履歴情報生成処理の実際＞＞
分岐履歴情報生成部１３は、各部分プログラムの先頭命令が、条件分岐命令の場合に、それら条件変数の真偽値（「１」および「０」の２値表現の値）を記憶装置１７０に記録する命令プログラムを、対象プログラムに付加することで実現できる。付加する命令プログラムは、例えば図６に示すようなファイル出力関数プログラムである。つまり、図６に示すファイル出力関数プログラムを実行時間推定装置１ａが呼び出すことで、分岐履歴情報生成部１３は具現化することができる。
【００５９】
図６は、分岐履歴ビット系列を出力するためのファイル入出力関数の例を示す図であり、図７は、図４における対象プログラムの一部を示す図であり、図８は、図７に示すプログラムを書き換えた後のプログラムの例を示す図である。
なお、図７は、図４の対象プログラムにおける３行目および４行目を示す。
分岐履歴情報生成部１３は、図５のようなファイル出力関数を定義しておいた上で、図６において、条件変数「Ａ」および「Ｂ」がプログラム上で出現する箇所を、図８に示すように書き換えればよい。そして、分岐履歴情報生成部１３は、図８のように書き換えられた対象プログラムを実行時間推定装置１ａが実行することにより具現化され、分岐履歴ビット系列を取得することができる。
【００６０】
（実行トレース再生処理）
図３に戻り、ステップＳ１０３が終了すると、実行トレース再生部１４が、部分プログラムテーブルおよび分岐履歴ビット系列を基に実行トレース再生処理を行う（Ｓ１０４）。ステップＳ１０４において実行トレース再生部１４は、ステップＳ１０３で生成された分岐履歴ビット系列のビットを逐次的に読み出し、ステップＳ１０２で生成された部分プログラムテーブルを基にプログラム実行トレースを再生し、部分プログラム実行系列を生成する。
【００６１】
＜＜実行トレース再生処理の実際＞＞
以下に分岐履歴ビット系列が「１１１０１１１０１０」であった場合における実行トレース再生処理の実際について図５を参照しつつ説明する。
まず、実行トレース再生部１４は、部分プログラムテーブルにおける部分プログラム「１」を読み込み、「部分プログラム終端命令」「ｂｒａｎｃｈ（Ａ）」に到達する。このとき、実行トレース再生部１４は、部分プログラム「１」の部分プログラム実行時間推定値「Ｔ１」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
分岐履歴ビット系列の先頭のビット「１」は、条件変数「Ａ」が「真」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ａ）［Ｔ］」である部分プログラム「２」に遷移し、その「部分プログラム終端命令」「ｂｒａｎｃｈ（Ｂ）」に到達する。そして、実行トレース再生部１４は、部分プログラム「２」の部分プログラム実行時間推定値「Ｔ２」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
分岐履歴ビット系列の２番目のビット「１」は、条件変数「Ｂ」が「真」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ｂ）［Ｔ］」である部分プログラム「４」に遷移し、その「部分プログラム終端命令」「ｂｒａｎｃｈ（Ａ）」に到達する。そして、実行トレース再生部１４は、部分プログラム「４」の部分プログラム実行時間推定値「Ｔ４」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
【００６２】
以下、同様に、分岐履歴ビット系列の３番目の分岐履歴ビット「１」は、条件変数「Ａ」が「真」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ａ）［Ｔ］」である部分プログラム「２」に遷移し、その「部分プログラム終端命令」である「ｂｒａｎｃｈ（Ｂ）」に到達する。そして、実行トレース再生部１４は、部分プログラム「２」の部分プログラム実行時間推定値「Ｔ２」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
次に、分岐履歴ビット系列の４番目の分岐履歴ビット「０」は、条件変数「Ｂ」が「偽」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ｂ）［Ｆ］」である部分プログラム「５」に遷移し、その「部分プログラム終端命令」である「ｂｒａｎｃｈ（Ｃ）」に到達する。そして、実行トレース再生部１４は、部分プログラム「５」の部分プログラム実行時間推定値「Ｔ５」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
そして、分岐履歴ビット系列の５番目の分岐履歴ビット「１」は、条件変数「Ｃ」が「真」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ｃ）［Ｔ］」である部分プログラム「６」に遷移し、第１終端命令である呼び出し関数「ｆｕｎｃ１：ｓｔａｒｔ」に到達する。このとき、実行トレース再生部１４は、部分プログラムをスタックにプッシュして呼び出し、元の部分プログラムをＲＡＭ１５３などの記憶装置１７０（図２）に記録しておく。そして、実行トレース再生部１４は、部分プログラム「６」の部分プログラム実行時間推定値「Ｔ６ａ」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。その後、実行トレース再生部１４は、部分プログラム「８」に無条件で遷移しその「部分プログラム終端命令」「ｂｒａｎｃｈ（Ｄ）」に到達する。
【００６３】
次に、分岐履歴ビット系列の６番目の分岐履歴ビット「１」は、条件変数「Ｄ」が「真」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ｄ）［Ｔ］」である部分プログラム「９」に遷移し、その「部分プログラム終端命令」である「ｂｒａｎｃｈ（Ｄ）」に到達する。そして、実行トレース再生部１４は、部分プログラム「９」の部分プログラム実行時間推定値「Ｔ９」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
そして、分岐履歴ビット系列の７番目の分岐履歴ビット「１」は、条件変数「Ｄ」が「真」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ｄ）［Ｔ］」である部分プログラム「９」に遷移し、その「部分プログラム終端命令」である「ｂｒａｎｃｈ（Ｄ）」に到達する。そして、実行トレース再生部１４は、部分プログラム「９」の部分プログラム実行時間推定値「Ｔ９」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
【００６４】
さらに、分岐履歴ビット系列の８番目の分岐履歴ビット「０」は、条件変数「Ｄ」が「偽」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ｄ）［Ｆ］」である部分プログラム「１０」に遷移し、その「部分プログラム終端命令」である「ｂｒａｎｃｈ（Ｅ）」に到達する。そして、実行トレース再生部１４は、部分プログラム「１０」の部分プログラム実行時間推定値「Ｔ１０」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
続いて、分岐履歴ビット系列の９番目の分岐履歴ビット「１」は、条件変数「Ｅ」が「真」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ｅ）［Ｔ］」である部分プログラム「１１」に遷移し、その「部分プログラム終端命令」である「ｆｕｎｃ１：ｅｎｄ」に到達する。その後、実行トレース再生部１４は、スタックから部分プログラム「６」をポップし、この第２部分プログラム終端命令である「ｂｒａｎｃｈ（Ａ）」に到達する。そして、実行トレース再生部１４は、部分プログラム「６」の第２部分プログラム実行時間推定値「Ｔ６ｂ」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
そして、分岐履歴ビット系列の１０番目の分岐履歴ビット「０」は、条件変数「Ａ」が「偽」であることを示すので、実行トレース再生部１４は、「部分プログラム先頭命令」が「ｂｒａｎｃｈ（Ａ）［Ｆ］」である部分プログラム「３」に遷移し、その「部分プログラム終端命令」である「ｍａｉｎ：ｅｎｄ」に到達する。この時点でプログラム実行が終了する。そして、実行トレース再生部１４は、部分プログラム「３」の部分プログラム実行時間推定値「Ｔ３」を読み込み、この部分プログラム実行時間を実行時間推定算出部１５へ送る。
【００６５】
このような処理を行い、実行トレース再生部１４は、部分プログラムテーブルから部分プログラムＩＤに対応する部分プログラム実行時間推定値を順次取得することにより、以下のような部分プログラム実行系列が、実行時間推定算出部１５へ送られる。
【００６６】
ｍａｉｎ：ｓｔａｒｔ→［Ｔ１］→Ａ（１）→［Ｔ２］→Ｂ（１）→［Ｔ４］→Ａ（１）→［Ｔ２］→Ｂ（０）→［Ｔ５］→Ｃ（１）→［Ｔ６ａ］→ｆｕｎｃ１：ｓｔａｒｔ→［Ｔ８］→Ｄ（１）→［Ｔ９］→Ｄ（１）→［Ｔ９］→Ｄ（０）→［Ｔ１０］→Ｅ（１）→［Ｔ１１］→ｆｕｎｃ１：ｅｎｄ→［Ｔ６ｂ］→Ａ（０）→［Ｔ３］→ｍａｉｎ：ｅｎｄ
【００６７】
ここで［Ｔｘ］は、その部分プログラムの実行時間（図５の部分プログラムテーブルの「部分プログラム実行時間推定値」）を表し、Ａ（１）は、条件変数「Ａ」が「真」であることを表し、Ａ（０）は、条件変数「Ａ」が「偽」であることを表す。なお、実際には、実行トレース再生部１４が、部分プログラム実行時間推定値を部分プログラムテーブルから読み出す毎に、逐次的に実行時間推定算出部１５へ送られる。
【００６８】
このような実行トレース再生処理（Ｓ１０４）を行うことにより、対象プログラムを実際に実行したときのすべての実行命令系列を正確に再生することが可能となる。さらに、実行トレース再生処理を行うことで、多様なプログラム実行プロファイル情報（各命令の実行頻度、各関数呼出しの実行頻度、各条件分岐命令の分岐確率など）を正確に計算することが可能となるという副次的な効果も発生する。
【００６９】
（実行時間推定算出処理）
ステップＳ１０４の後、実行時間推定算出部１５が、実行トレース再生部１４から逐次的に送られる部分プログラム実行時間推定値を、送られてきた順に加算することによって対象プログラム全体の実行時間推定値を算出する実行時間推定算出処理を行う（Ｓ１０５）。なお、実行時間推定算出部１５は、実行トレース再生部１４から送られる部分プログラム実行系列を基に、部分プログラムテーブルから部分プログラム実行時間推定値を読み出し、実行系列に代入して、加算することによって対象プログラム全体の実行時間推定値を算出してもよい。
【００７０】
＜＜実行時間推定算出処理の実際＞＞
ステップＳ１０４において生成された部分プログラム実行系列を再度記載すると、以下のような系列となっている。
【００７１】
ｍａｉｎ：ｓｔａｒｔ→［Ｔ１］→Ａ（１）→［Ｔ２］→Ｂ（１）→［Ｔ４］→Ａ（１）→［Ｔ２］→Ｂ（０）→［Ｔ５］→Ｃ（１）→［Ｔ６ａ］→ｆｕｎｃ１：ｓｔａｒｔ→［Ｔ８］→Ｄ（１）→［Ｔ９］→Ｄ（１）→［Ｔ９］→Ｄ（０）→［Ｔ１０］→Ｅ（１）→［Ｔ１１］→ｆｕｎｃ１：ｅｎｄ→［Ｔ６ｂ］→Ａ（０）→［Ｔ３］→ｍａｉｎ：ｅｎｄ
【００７２】
ここで、実行時間推定算出部１５が、［Ｔｘ］（部分プログラム実行時間推定値）を順次加算することにより、部分プログラム実行系列に対応するプログラム実行トレースの実行時間（対象プログラム全体の実行時間推定値）は以下の式（１．１）となる。
【００７３】
ＴｏｔａｌＴｉｍｅ＿１＝Ｔ１＋Ｔ２＋Ｔ４＋Ｔ２＋Ｔ５＋Ｔ６ａ＋Ｔ８＋Ｔ９＋Ｔ９＋Ｔ１０＋Ｔ１１＋Ｔ６ｂ＋  Ｔ３・・・（１．１）
【００７４】
次に、分岐履歴ビット系列の別の例として以下の分岐履歴ビット系列「１００１０１１１００」を示す。
前記した分岐履歴ビット系列と同様の処理により、この分岐履歴ビット系列から以下のような部分プログラム実行系列が生成される。
【００７５】
ｍａｉｎ：ｓｔａｒｔ→［Ｔ１］→Ａ（１）→［Ｔ２］→Ｂ（０）→［Ｔ５］→Ｃ（０）→［Ｔ７］→Ａ（１）→［Ｔ２］→Ｂ（０）→［Ｔ５］→Ｃ（１）→［Ｔ６ａ］→ｆｕｎｃ１：ｓｔａｒｔ→［Ｔ８］→Ｄ（１）→［Ｔ９］→Ｄ（１）→［Ｔ９］→Ｄ（０）→［Ｔ１０］→Ｅ（０）→［Ｔ１２］→ｍａｉｎ：ｅｎｄ
【００７６】
従って、この分岐履歴ビット系列に対応するプログラム実行トレースの実行時間（実行時間推定値）は以下の式（１．２）となる。
【００７７】
ＴｏｔａｌＴｉｍｅ＿２＝Ｔ１＋Ｔ２＋Ｔ５＋Ｔ７＋Ｔ２＋Ｔ５＋Ｔ６ａ＋Ｔ８＋Ｔ９＋Ｔ９＋Ｔ１０＋Ｔ１２・・・（１．２）
【００７８】
（第１実施形態の効果）
第１実施形態によって算出された実行時間推定値は、ステップＳ１０２で算出された部分プログラム実行時間推定値と同じく高い精度を有する。さらに、ステップＳ１０３で生成された分岐履歴ビット系列はプログラム実行命令数に比べて著しく少ないことから、実際のプログラム実行時間よりもはるかに短い処理時間で実行時間見積りを算出することができることができる。
また、ステップＳ１０２において部分プログラムの実行時間を推定するが、同じ部分プログラムがループや、条件分岐命令などで複数回実行されるような対象プログラムでも、１回分の実行時間を算出すればよいので、対象プログラムを頭から実行時間推定する場合に比べ短時間の処理で済むことが可能となる。
【００７９】
（第２実施形態）
図９は、第２実施形態に係る実行時間推定装置の構成例を示す図である。
図９において、第１実施形態と同様の要素については同一の符号を付して説明を省略する。
実行時間推定装置１ｂ（１）は、ループ情報抽出部２１と、プログラム実行履歴情報生成部２２と、後記して説明する第２種ループの実行時間を推定算出する第２種ループ実行時間推定算出部２３とを有する点である。さらに、実行時間推定装置１ｂは、第１実施形態で前記した部分プログラム実行系列以外に、後記して説明する第２種ループ実行系列を生成する実行トレース再生部１４ｂと、部分プログラム実行系列、第２種ループ以外の部分プログラム実行時間推定値および後記する第２種ループ実行時間推定値から対象プログラムの実行時間を推定算出する実行時間推定算出部１５ｂを備えている。
【００８０】
ループ情報抽出部２１は、第１実施形態と同様の機能を有するプログラム分割部１１および部分プログラム実行時間推定算出部１２を有する。さらに、ループ情報抽出部２１は、対象プログラムを基に後記して説明する第１種ループおよび第２種ループを判別し、第２種ループＩＤを部分プログラムテーブルに追加したり、判別の結果生成される第１種ループ情報（後記）を第１種ループ縮退部２１２へ送ったり、第２種ループ情報（後記）を第２種ループ回数データ系列生成部２２１へ送る第１種・第２種ループ判別処理部２１１を有する。また、ループ情報抽出部２１は、第１種ループ情報を基に、部分プログラムテーブルにおいて第１種ループの縮退処理を行い、第１種ループ縮退済みであり、第２種ループＩＤを追加済みの部分プログラムテーブルを実行時間推定算出部１５ｂへ送る第１種ループ縮退部２１２とを有する。
プログラム実行履歴情報生成部２２は、第２種ループＩＤと、第２種ループの繰り返し回数との対の情報の系列である第２種ループ回数データ系列を生成する第２種ループ回数データ系列生成部２２１と、第２種ループ以外の部分プログラムの分岐履歴ビット系列を生成する分岐履歴情報生成部１３ｂとを有する。
なお、第２種ループ回数系列生成部２２１および分岐履歴情報生成部１３ｂは、対象プログラム（ソースプログラム）の一部を所定の関数で書き換え、書き換えられた対象プログラムをプログラム実行履歴情報生成部２２が実行することによって、具現化する（詳細は、図１５を参照して後記する）。
【００８１】
なお、図９に示す各部１１，１２，１３ｂ，１４ｂ，１５ｂ，２１，２２，２３，２１１，２１２，２２１は、図２の記憶装置１７０などに記憶されている実行時間推定プログラムが、ＲＡＭ１５３に展開され、ＣＰＵ１５１が実行することによって具現化する。
【００８２】
まず、具体的な処理の説明を行う前に、図４の対象プログラムを参照しつつ第２実施形態における処理の原理および概略を説明する。
ループ（繰り返し処理）内の条件分岐命令は、以下に示す条件Ｚ１〜Ｚ３が、Ｚ１∩（Ｚ２∪Ｚ３）を満たすとき、その部分の分岐履歴情報を保存せずに正確な実行トレース再生を行うことができる。
【００８３】
条件Ｚ１：ループ内部においてループ継続条件命令以外にｉｆ−ｅｌｓｅ分岐命令などの条件分岐命令を含まない。ここで、ループ継続条件命令とは、ループを抜けるか否かの条件分岐命令である。
条件Ｚ２：ループの繰り返し回数が定数回である。
条件Ｚ３：ループの繰り返し回数が固定回である。
【００８４】
ここで、「ループの繰り返し回数が定数回である」とは、特定のループ回数が対象プログラム全体を通して、不変である（定数である）ことをいう。
また、「ループの繰り返し回数が固定回」であるとは、特定のループ回数が変数で規定されており、ループ内では不変であるが、ループ外において変化する可能性があることをいう。
【００８５】
図４に示す対象プログラムの例において、「ｍａｉｎ」関数の「ループ１」に該当するループ（以下、「ループｎ」に該当する「ループ」を「ループｎ」と記載する）は、条件Ｚ１を満たしていない（ループ内にｉｆ−ｅｌｓｅ分岐命令が存在する）。なお、「ｆｕｎｃ１」関数の「ループ２」は、条件Ｚ１を満たしている。
条件Ｚ２については、「ループ２」の「Ｄ＝ｉ＜Ｍ」において「Ｍ」が定数値である場合、すなわち、「Ｍ」が対象プログラム全体において不変である場合に成り立つ。
条件Ｚ３については、「ループ２」の「Ｄ＝ｉ＜Ｍ」において「Ｍ」が変数であっても、ループ処理中に変化せずに固定されている場合（固定回数：ループ不変）である場合に成り立つ。
特に条件Ｚ３は、画像処理のように画像の高さや幅を変数として与えられる場合に用いられることが多く、これらの変数とループの繰り返し数が直接対応するケースが多く存在する。
【００８６】
図４に示す対象プログラムから導出された分岐履歴ビット系列（第１実施形態参照）を参照すると、「ループ２」のループ回数は、２回である（条件変数「Ｄ」を参照）。
このとき「ループ２」において、Ｚ１∩Ｚ２が成り立つ場合、（以降「第１種ループ」と記載する）、Ｍ＝２は定数であり、図５に示す部分プログラムテーブルから「ｂｒａｎｃｈ（Ｄ）」に到達した状態で必ず「Ｄ（１）  →［Ｔ９］  →Ｄ（１）  →［Ｔ９］  →Ｄ（０）  →［Ｔ１０］  →Ｅ」の実行をすることが明らかである。従って、ループ２の実行時間は式（２．１）で示されることが可能である。このため、分岐履歴情報生成部１３ｂは、分岐履歴ビット系列において「ｂｒａｎｃｈ（Ｄ）」に関するビット系列を記録する必要がない。
【００８７】
Ｔ＿Ｌ２＝Ｔ９×２＋Ｔ１０・・・（２．１）
【００８８】
また、Ｚ１∩Ｚ３が成り立つ場合（以降「第２種ループ」と記載する）、例えば、変数「Ｍ」は「ループ２」の実行直前で「Ｍ＝２」の値を取り、「ループ２」の実行中は変化しない場合、第２種ループ回数データ系列生成部２２１は、第２種ループＩＤ（第１種・第２種ループ判別処理部２１１によって発行されるＩＤ）とその時の第２種ループ回数を第２種ループ回数データ系列として保存する。そして、この第２種ループ回数データ系列を基に、第２種ループ実行時間推定算出部２３が、例えば第２種ループの処理時間を式（２．２）によって推定する（詳細な処理は後記して説明する）。
【００８９】
Ｔ＿Ｌ２＝Ｔ９×Ｍ＋Ｔ１０・・・（２．２）
【００９０】
このとき「Ｍ」は、第２種ループ回数データ系列で記録されている第２種ループ回数である。この場合も同様に、分岐履歴情報生成部１３ｂは、分岐履歴ビット系列において第２種ループに関する条件分岐命令である「ｂｒａｎｃｈ（Ｄ）」の分岐履歴を記録する必要はない。
【００９１】
前記した２通りのケースにおいては、ループ内の分岐履歴情報を分岐履歴ビット系列に記録する必要がないため、このような条件を満たすループ（第１種ループおよび第２種ループ）が多数存在するプログラムでは、分岐履歴ビット系列長を大幅に削減できることが期待できる。従って、第１種ループおよび第２種ループはそれぞれ一つの命令に縮退し、内部の条件分岐命令（ループ継続条件命令）は部分プログラムのプログラム分割境界点から除くことができる。
【００９２】
次に、図９を参照しつつ、図１０に沿って第２実施形態に係るプログラム実行時間推定方法を説明する。
図１０は、第２実施形態に係るプログラム実行時間推定方法の処理の流れを示すフローチャートである。
【００９３】
（ループ情報抽出処理）
次に、ループ情報抽出部２１が、ループ情報抽出処理を行う（Ｓ２０１）。ループ情報抽出部２１は、ステップＳ２０１の結果、生成した第１種ループ情報と、第２種ループ情報とをプログラム実行履歴情報生成部２２へ送る。さらに、ループ情報抽出部２１は、ステップＳ２０１の結果、第１種ループが縮退済であり、第２種ループＩＤが書き込まれた部分プログラムテーブルを実行トレース再生部１４ｂ、第２種ループ実行時間推定算出部２３および実行時間推定算出部１５ｂへ送る。第１種ループ情報および第２種ループ情報については、後記するが第１種ループ情報は、第１種ループに該当する条件分岐命令（ループ継続条件命令）であり、第２種ループ情報は、第２種ループＩＤと部分プログラムＩＤとの対の情報である。
【００９４】
ここで、図９を参照しつつ、図１１に沿ってループ情報抽出処理の詳細を記載する。
図１１は、第２実施形態に係るループ情報抽出処理の流れを示すフローチャートである。
【００９５】
まず、ループ情報抽出部２１のプログラム分割部１１が、プログラム分割処理を行い（Ｓ１０１）、部分プログラム実行時間推定算出部１２が、部分プログラム実行時間推定算出処理を行う（Ｓ１０２）。これらの処理は、前記した実施形態と同様の処理であるため、同一のステップ番号を付して説明を省略する。
【００９６】
＜第１種ループ・第２種ループ判別処理＞
次に、ループ情報抽出部２１の第１種・第２種ループ判別処理部２１１が、ステップＳ１０１，Ｓ１０２において生成された部分プログラムテーブルにおけるループが第１種ループであるか、第２種ループであるかの判別を行う第１種ループ・第２種ループ判別処理を行う（Ｓ２０１１）。
【００９７】
ここで、図１２を参照しつつ第１種ループ・第２種ループ判別処理を説明する。
図１２は、ある対象プログラムにおけるループに関する図であり、（ａ）は、あるループの構造を模式化した図であり、（ｂ）は、（ａ）に示すような構造を有するループから生成される部分プログラムの構成の例を示す表である。
【００９８】
ここで、図１２（ｂ）における「ＷＷ」および「ＹＹ」は、適当な処理を示している。条件「Ｘ」は、ループを継続するか否かの条件（ループ継続条件命令）を示している。また、「ｃ１」、「ｃ２」、「ｃ３」、「ｃ４」および「ｃ５」は、それぞれ処理コードを示し、条件分岐命令や、合流点（ｇｏｔｏ文やループなどによって複数のコード箇所から到達可能なコード地点）や、関数呼出し命令を含まないコードブロックである。ここで、コードブロック「ｃ１」、「ｃ２」、「ｃ３」、「ｃ４」および「ｃ５」は，命令を一つも含まない「空」のコードブロックでもよい。なお、「ＩＤ」や、部分プログラム先頭命令や、部分プログラム終端命令は、前記した実施形態における部分プログラムテーブルにおけるものと同様であるため説明を省略する。
【００９９】
図１２（ｂ）における部分プログラム「１４」において部分プログラム先頭命令と、部分プログラム終端命令とが同じ「ｂｒａｎｃｈ（Ｘ）」となっているが、これはループであるため同じ条件分岐命令が繰り返されることを意味している。すなわち、第１種・第２種ループ判別処理部２１１は、「部分プログラム先頭命令」と、「部分プログラム終端命令」とにおいて同一の条件分岐命令があるか否かでループを識別することができる。
【０１００】
ここで、第１種・第２種ループ判別処理部２１１は、後記して説明する入力依存変数が後記するループ不変変数であるか、帰納変数であるかを判別することにより第１種ループおよび第２種ループの判別を行う。
ここで、入力依存変数は、例えばループ継続条件命令が「Ｄ＝ｉ＜Ｍ」であったとき「ｉ」および「Ｍ」が入力依存変数である。
また、ループ不変変数は、図１２（ａ）における対象プログラムの構造を例として説明すると、ループ内におけるコード「ｃ２」および「ｃ４」によって値が更新されない変数である。つまり、前記した変数「Ｍ」に対し「Ｍ＝・・・」といったＭに対する代入式がコード「ｃ２」および「ｃ４」の中に存在しないとき、第１種・第２種ループ判別処理部２１１は、変数「Ｍ」をループ不変変数であると判別する。
【０１０１】
さらに、帰納変数は、変数がループの開始前に定数値に初期化され、かつ「変数＝変数  ｏｐ  （定数値）」（ｏｐ：２項演算子）の形式の代入式だけがループ内のコードに存在するような変数である。例えば、図１２（ａ）のループで使用されている変数「ｇ」があるとして（図１２に図示せず）、この変数「ｇ」を例として説明すると、ループが始まる前のコード「ｃ１」において、この「ｇ」が定数値に初期化され、変数「ｇ」に関し「ｇ＝ｇ  ｏｐ  （定数値）」の形式の代入式だけがループ内のコード「ｃ２」や「ｃ４」に存在するとき、第１種・第２種ループ判別処理部２１１は、変数「ｇ」を帰納変数であると判別する。
入力依存変数、ループ不変変数および帰納変数は、対象プログラムを第１種・第２種ループ判別処理部２１１が検索することによって取得される変数である。
【０１０２】
そして、第１種・第２種ループ判別処理部２１１は、ループ内における入力依存変数のすべてが「帰納変数」または「定数」であるとき、該当するループを第１種ループであると判別し、ループ内における入力依存変数のすべてが「帰納変数」または「ループ不変変数」であるとき、該当するループを第２種ループであると判別する。なお、第１種ループにも、第２種ループにも該当しないループは、部分プログラムの繰り返しとして表現されることとなる。
【０１０３】
（第２種ループＩＤ追加処理）
図１１に戻り、ステップＳ２０１１の後、第１種・第２種ループ判別処理部２１１は、ステップＳ２０１１において第２種ループと判別された部分プログラムに第２種ループＩＤを発行し、部分プログラムテーブルの該当する部分プログラムの第２種ループＩＤのフィールドに発行した第２種ループＩＤを追加する第２種ループＩＤ追加処理を行う（Ｓ２０１２）。なお、第１種・第２種ループ判別処理部２１１は、第２種ループ以外の部分プログラムに関するループＩＤ番号を「０」とする。この段階での部分プログラムテーブルは、例えば図１３に示すようなテーブルとなる。
【０１０４】
ここで、図１３は、第２実施形態において用いられる部分プログラムテーブルの例である。
図１３における部分プログラムテーブルが、図５に示す部分プログラムテーブルと異なる点は、第２種ループＩＤを格納するためのフィールドを有する点である。
前記したように第２種ループＩＤのフィールドには、第２種ループに該当する箇所には第２種ループＩＤが格納され、それ以外の部分プログラム（第１種ループを含む）には、「０」が格納される。
【０１０５】
なお、第１種・第２種ループ判別処理部２１１（図９）は、第１種ループに該当する条件分岐命令である第１種ループ情報を、第１種ループ縮退部２１２（図９）および分岐履歴情報生成部１３ｂ（図９）へ送り、第２種ループＩＤと部分プログラムＩＤとの対の情報である第２種ループ情報を第２種ループ回数データ系列生成部２２１へ送る。
【０１０６】
＜第１種ループ縮退処理＞
図１１に戻り、ステップＳ２０１２の後、ループ情報抽出部２１の第１種ループ縮退部２１２は、第１種・第２種ループ判別処理部２１１から送られた部分プログラムテーブルにおける第１種ループを図１４に示すように縮退する（Ｓ２０１３）。なお、第２〜第６実施形態において、「縮退」とは、部分プログラムテーブルにおける２つの行を、所定のルールに基づいて１つの行にまとめることをいう。
図１４は、第１種ループの縮退を説明するための図であり、（ａ）は、縮退前の部分プログラムテーブルであり、（ｂ）は、縮退後の部分プログラムテーブルである。なお、図１４に示す部分プログラムテーブルは、図１３に示す部分プログラムと同様の構成をしているが、第１種ループの縮退を説明するため、「第２種ループＩＤ」のフィールドをすべて「０」にしてある。
【０１０７】
図１４（ａ）を参照すると、部分プログラム「９」の「部分プログラム先頭命令」と「部分プログラム終端命令」とが同一の条件命令を有している。前記したように、「部分プログラム先頭命令」と「部分プログラム終端命令」とが同一の条件命令である部分プログラムは、ループを形成していることを示している。従って、部分プログラム「９」は、ループであることが分かり、さらに第１種ループ情報における条件分岐命令（ここでは、ｂｒａｎｃｈ（Ｄ））から第１種ループであることが分かる。
そこで、第１種ループ縮退部２２２は、図１４（ａ）における部分プログラム「９」と、同じ条件分岐命令を「部分プログラム先頭命令」に有する部分プログラム「１０」とを、図１４（ｂ）における部分プログラム「９’」に縮約する。すなわち、プログラム実行履歴情報生成部２２は、図１４（ａ）における部分プログラム「９」における部分プログラム終端命令「ｂｒａｎｃｈ（Ｄ）」を「Ｒｅｄｕｃｅ＿Ｌ２」とし、、部分プログラム「１０」における部分プログラム先頭命令「ｂｒａｎｃｈ（Ｄ）［Ｆ］」を、Ｒｅｄｕｃｅ＿Ｌ２とする。そして、縮約された部分プログラムＩＤ「９’」の実行時間推定値は、式（２．１）に従った値が格納される。
【０１０８】
第１種ループ縮退部２１２は、ステップＳ２０１２で第２種ループＩＤが追加され、さらにステップＳ２０１３で第１種ループの縮退が行われた部分プログラムテーブルを実行トレース再生部１４および実行時間推定算出部１５へ送る。
【０１０９】
（プログラム実行履歴情報生成処理）
図１０に戻り、ステップＳ２０１の後、入力部１５６（図２）を介して入力された対象プログラムと、ループ情報抽出部２１から入力された第１種ループ情報および第２種ループ情報を使用してプログラム実行履歴情報生成処理を行う（Ｓ２０２）。
【０１１０】
ここで、図９を参照しつつ、図１５に沿ってプログラム実行履歴情報生成処理を説明する。
図１５は、第２実施形態に係るプログラム実行履歴情報生成処理の流れを示すフローチャートである。
【０１１１】
＜対象プログラム（ソースプログラム）書換処理＞
まず、プログラム実行履歴情報生成部２２は、図１６に示すような対象プログラムの書換処理を行う（Ｓ２０２１）。ここで、図１６は、第２種ループ回数データ系列を生成するための対象プログラムの書き換え例を示す図であり、（ａ）は書き換え前、（ｂ）は書き換え後、（ｃ）は第２種ループ回数データ系列および分岐履歴ビット系列を生成する関数を示す。
すなわち、プログラム実行履歴情報生成部２２は、図１６（ａ）における第２種ループのループ継続条件命令（下線部）を図１６（ｂ）の下線部のように書き換える。図１６（ｂ）の下線部の関数は、図１６（ｃ）に示す関数である。
【０１１２】
さらに、図１６（ｃ）に示す関数は、第２種ループのループ回数をカウントし、カウントされた第２種ループ回数が、すでに第２種ループ回数データ系列に記録されており、同じ第２種ループＩＤを有している直前の第２種ループ回数とが一致したとき（すなわち、ループ回数が変化しなかったとき）、カウントしたループ回数を第２種ループ回数データ系列に書き込まない機能を有する（詳細は後記して説明する）。
【０１１３】
ステップＳ２０３１の後、プログラム実行履歴情報生成部２２が、図１６（ｂ）に示すように書き換えられた対象プログラムを実行する（Ｓ２０３２）ことで、図９に示す第２種ループ回数データ系列生成部２２１が起動し、起動した第２種ループ回数データ系列生成部２２１は、第２種ループ回数データ系列を生成する。
ここで、第２種ループ回数データ系列には、例えば［０１，２５０］などのように、ループＩＤ（「０１」）と対の情報の系列として、対象となる第２種ループが繰り返される回数である第２種ループ繰り返し回数が記録される。［０１，２５０］は、第２種ループＩＤ「０１」を有する第２種ループが２５０回繰り返されたことを示している。
また、第２種ループ回数データ系列における第２種ループの繰り返し回数の初期値は、「−１」である。繰り返し回数の初期値を「−１」とする理由は、まだループの繰り返し回数をカウントしていないので、一時的にあり得ない値を入れておくためである。
【０１１４】
＜＜第２種ループ回数データ系列生成の実際＞＞
ここで、第２種ループ回数データ系列生成部２２１における第２種ループ回数データ系列生成の具体例を説明する。
まず、前提として３つの第２種ループ（第２種ループＩＤ：「０１」、「０２」、「０３」）が対象プログラム中に存在するとする。
そして、まず、第２種ループ回数データ系列生成部２２１は、［０１，５］，［０２，８］，［０２，８］，［０１，５］，［０３，１０］，［０３，１０］，［０１，５］，［０２，４］，［０３，２０］，［０１，５］，［０２，８］という第２種ループデータ系列を生成するとする。ここで、第２種ループ回数データ系列を構成するデータ（［０１，５］など）を第２種ループ回数データと記載する。各第２種ループ回数データの示す意味は、［第２種ループＩＤ，第２種ループ回数］である。
【０１１５】
次に、第２種ループ回数データ系列生成部２２１は、第２種ループ回数データ系列は、次のような処理を行うことで、第２種ループ回数データ系列の冗長性を減少させ、データ量を減少させる。つまり、第２種ループ回数データ系列生成部２２１は、第２種ループ回数データ系列において、同一の第２種ループＩＤに関し、直前の第２種ループ回数データ系列に登録された第２種ループ回数と、カウントされた第２種ループ回数との値が一致したとき（すなわち、第２種ループ回数が変化していないとき）、カウントした第２種ループ回数データを第２種ループ回数データ系列に書き込まない処理を行う。なお、ここでは、説明を簡便にするため、第２種ループ回数データ系列から該当する第２種ループ回数データを削除する手順を用いて説明する。
前記した第２種ループ回数データ系列を例に説明すると、以下のようになる。
【０１１６】
［０１，５］，［０２，８］，｛［０２，８］，［０１，５］｝，［０３，１０］，｛［０３，１０］，［０１，５］｝，［０２，４］，［０３，２０］，｛［０１，５］｝，［０２，８］
【０１１７】
ここで、中括弧で囲まれた第２種ループ回数データが、削除されるデータである。例えば、３番目の第２種ループ回数データ［０２，８］は、２番目の第２種ループ回数データ（第２種ループＩＤ「０２」に関し、直前の第２種ループ回数データ）と第２種ループ回数が一致するため、削除される。
また、４番目の第２種ループ回数データ［０１，５］は、１番目の第２種ループ回数データ（第２種ループＩＤ「０５」に関し、直前の第２種ループ回数データ）と第２種ループ回数が一致するため削除される。
なお、最後の第２種ループ回数データ［０２，８］は、第２種ループＩＤ「０２」に関し直前の第２種ループ回数データ［０２，２］（８番目のデータ）とは、第２種ループ回数が異なっているため削除されない。
【０１１８】
このような処理により、最終的に第２種ループ回数データ系列生成部２２１が出力する第２種ループ回数データ系列は、以下のようになる。
【０１１９】
［０１，５］，［０２，８］，［０３，１０］，［０２，４］，［０３，２０］，［０２，８］
【０１２０】
なお、前記したように、ここでは、説明のため、第２種ループ回数データ系列生成部２２１は、一度、第２種ループ回数データ系列を生成した後、直前の第２種ループＩＤに関し同一の第２種ループ回数が一致する第２種ループ回数データを削除しているが、第２種ループ回数データ系列を生成する過程で、第２種ループ回数データ系列生成部２２１は、直前の第２種ループＩＤに関し同一の第２種ループ回数が存在するか否かを判定し、存在する場合は、第２種ループ回数データ系列に書き込まないようする。
【０１２１】
さらに、図１６（ｃ）に示す関数は、第２種ループ回数データ系列を生成する機能に加えて、分岐履歴ビット系列も生成する機能も有する。このとき、図１６（ｃ）に示す関数は、第２種ループのループ継続条件命令の分岐履歴ビットを分岐履歴ビット系列として記録しない機能も有する。すなわち、プログラム実行履歴情報生成部２２が、図１６（ｂ）に示す書き換えられた対象プログラムを実行することにより、図９の分岐履歴情報生成部１３ｂをも起動する。起動された分岐履歴情報生成部１３ｂは第２種ループを除いた分岐履歴ビット系列を生成する。つまり、分岐履歴情報生成部１３ｂが生成する分岐履歴ビット系列は、第２種ループに関するビットが省略されているため、ビット数の少ない分岐履歴ビット系列となる。さらに、図１６（ｃ）に示す関数によって起動された分岐履歴情報生成部１３ｂは、第１種・第２種ループ判別処理部２１１から送られた第１種ループ情報に含まれる条件分岐命令に相当するビット（第１種ループに関するビット）を省略した分岐履歴ビット系列を生成する。
【０１２２】
ステップＳ２０２の結果、プログラム実行履歴情報生成部２２は、生成した分岐履歴ビット系列を実行トレース再生部１４ｂへ送り、第２種ループ回数データ系列を第２種ループ実行時間推定算出部２３へ送る。
【０１２３】
（実行トレース再生処理）
図１０の説明に戻り、ステップＳ２０２の後、実行トレース再生部１４ｂが、ループ情報抽出部２１から取得した部分プログラムテーブルと、分岐履歴情報生成部１３ｂから取得した分岐履歴ビット系列とを基に実行トレース再生処理とを行い（Ｓ１０４ｂ）、第２種ループ実行系列と部分プログラム実行系列とを生成する。
【０１２４】
以下に、第２実施形態における実行トレース再生部１４ｂで行われる第２種ループ実行系列生成処理を説明する。第２実施形態における実行トレース再生処理では、部分プログラム実行系列に加えて第２種ループ実行系列が生成される。
まず、実行トレース再生部１４ｂは、プログラム実行履歴情報生成部２２において生成された分岐履歴ビット系列を読み出しながら、前記した実施形態と同様の方法で部分プログラム実行系列を生成していく。なお、前記したように、実際には実行トレース再生部１４ｂは、部分プログラム実行系列を生成しつつ、部分プログラム実行時間推定値を逐次的に実行時間推定算出部１５ｂへおくることは、前記した実施形態と同様である。
【０１２５】
この際、実行トレース再生部１４ｂは、ループ情報抽出部２１で生成された部分プログラムテーブル（図１３）を上から順に参照して、第２種ループＩＤのフィールドに１以上の値がある部分プログラム（すなわち、第２種ループのループ継続条件命令を先頭命令に持つ部分プログラム）を抽出し、抽出した第２種ループＩＤを第２種ループ実行系列の末尾に追加していく。実行トレース再生部１４ｂは、第２種ループを示す部分プログラムの実行時間推定値を部分プログラム実行系列には追加せず（つまり、実行時間推定算出部１５ｂへ送らず）、第２種ループ終了後に到達する部分プログラムに自動的に遷移して、その部分プログラムを部分プログラム実行系列に追加する。
【０１２６】
図１３の例を参照して、第２実施形態に係る実行トレース再生処理の具体的な手順を説明する。なお、部分プログラム実行系列に関して、第１実施形態と同様であるため、説明を省略する。
例えば、実行トレース再生部１４ｂは、第１実施形態のステップＳ１０４と同様の手順で部分プログラムテーブルを上から順に参照する。そして、図１３の例において部分プログラム「９」に到達した時点で、実行トレース再生部１４ｂは、該当する第２種ループＩＤ「０２」を「第２種ループ実行系列」の末尾に追加し、第２種ループＩＤ「０２」の終了後に到達する部分プログラム「１１」または「１２」に遷移する。部分プログラム「１１」に遷移するか「１２」に遷移するかは，分岐履歴ビット系列から読み込まれている次の分岐履歴ビットによって判別される。
【０１２７】
具体的には、実行トレース再生部１４ｂは、第２種ループＩＤが「０２」である部分プログラム「９」に到達した時点で、部分プログラムテーブルにおける部分プログラム「９」が終了する条件（すなわち、部分プログラム「１０」（ｂｒａｎｃｈ（Ｄ）［Ｆ］）へ遷移する。このとき、実行トレース再生部１４ｂは、第２種ループ実行系列の末尾に部分プログラム「９」の第２種ループＩＤを追加する。なお、部分プログラム「９」のように部分プログラム先頭命令における条件と、部分プログラム終端命令における条件が同じである場合、前記したようにその部分プログラムは、ループを形成していることを示している。そして、実行トレース再生部１４ｂは、部分プログラム「１０」の部分プログラム終端命令（ｂｒａｎｃｈ（Ｅ））を部分プログラム先頭命令として有する部分プログラム「１１」もしくは「１２」へ遷移する。部分プログラム「１１」および「１２」のどちらへ遷移するかは、分岐履歴ビット系列を基に、実行トレース再生部１４ｂが決定する。
【０１２８】
このような処理により、以下に記載する効果を得ることができる。もし、分岐履歴情報生成部１３ｂが、第２種ループを認識せずに分岐履歴ビット系列を生成したとすると、この第２種ループに相当するビット系列は「１１１・・・０・・・」となる。このような分岐履歴ビット系列が生成された場合、実行トレース再生部１４ｂは、部分プログラム「９」への遷移を繰り返すことになる。第２実施形態による実行トレース再生処理（Ｓ１０４ｂ）によれば、実行トレース再生部１４ｂは、第２種ループに相当する部分プログラム（ここでは、部分プログラム「９」）のループ回数分の遷移を省略することによって、処理の高速化を実現することができる。
【０１２９】
（第２種ループ実行時間推定算出処理）
そして、図１０に戻り、ステップＳ１０４ｂの後、第２種ループ実行時間推定算出部２３が、第２種ループ回数データ系列生成部２２１から取得した第２種ループ回数データ系列と、実行トレース再生部１４ｂから取得した第２種ループ実行系列と、ループ情報抽出部２１から出力された部分プログラムテーブルの部分プログラム実行時間推定値とを基に第２種ループ実行時間推定算出処理を行う（Ｓ２０３）。このとき、該当する第２ループの部分プログラム実行時間推定値は、第２種ループ回数データ系列の第２種ループＩＤを参照して部分プログラムテーブルから抽出される。なお、第２種ループ実行時間推定算出処理は、ステップＳ１０５ｂのプログラム実行時間推定算出処理と並列に行われる処理である。
【０１３０】
ここで、第２種ループ実行時間推定算出処理について具体的に説明する。
まず、第２種ループ実行時間推定算出部２３は、第２種ループ回数データ系列生成部２２１から取得した第２種ループ回数データ系列を、先頭から逐次的に読み込む。ここで、そのときに読み込んでいる第２種ループ回数データを以下「現参照第２種ループ回数データ」とする。
次に、第２種ループ実行時間推定算出部２３は、実行トレース再生部１４ｂによって生成された第２種ループ実行系列（第２種ループＩＤ番号の実行順系列）を先頭から逐次的に読み込む。ここで、そのときに読み込んでいる第２種ループ実行系列中の第２種ループＩＤ番号をループ実行系列中の「現第２種ループＩＤ」とする。
第２種ループ実行時間推定算出部２３は、第２種ループ実行系列中の各ループの実行時間を算出するたびに、「現第２種ループＩＤ」は次の第２種ループＩＤに移動するが、「現参照第２種ループ回数データ」は、次の第２種ループ回数データに移動する場合と、移動せずに変化しない場合はある。具体的には、「現第２種ループＩＤ」と「現参照第２種ループ回数データ」の第２種ループＩＤが一致した場合は、次の第２種ループ回数データに移動するが、一致しない場合は移動しない。具体的な処理は、図１７を参照して後記する。
【０１３１】
「現参照第２種ループ回数データ」の第２種ループＩＤと「現第２種ループＩＤ」とが一致した場合、第２種ループ実行時間推定算出部２３は、部分プログラムテーブルにおける部分プログラム実行時間推定値を用いて、式（２．２）に従い第２種ループ実行時間推定値を算出し、この第２種ループ実行時間推定値と、対応する第２種ループＩＤとを対の情報として図示しない第２種ループ実行時間テーブルに格納し、実行時間推定算出部１５ｂへ算出した第２種ループ実行時間推定値を送る。ここで、第２種ループ実行時間テーブルとは、算出した第２種ループ実行時間をＲＡＭ１５３（図２）などに一時的に格納するためのテーブルである。図１３の例において第２種ループ回数を「２回」とすると、第２種ループ実行時間推定算出部２３は、第２種ループ実行時間推定値をＴ９×２＋Ｔ１０と計算する。
【０１３２】
「現参照第２種ループ回数データ」の第２種ループＩＤと「現第２種ループＩＤ」の第２種ループＩＤとが一致しない場合、第２種ループ実行時間推定算出部２３は、「第２種ループ実行時間テーブル」に記録されている値を第２種ループ実行時間とする。
【０１３３】
この後、第２種ループ実行時間推定算出部２３は、「現参照ループ回数データ」の第２種ループ回数データ系列内の参照位置を一つ後方にずらす、すなわち第２種ループ実行時間推定算出部２３は、第２種ループ回数データ系列において、「現参照ループ回数データ」の次の第２種ループ回数データを現参照ループ回数データとして読み込み、同様にして第２種ループ実行時間推定値を算出する。そして、第２種ループ実行時間推定算出部２３は、すべての第２種ループ回数データ系列を読み込むまで第２種ループ実行時間推定値の算出処理を繰り返す。以下に、第２種ループ実行時間推定算出処理の具体例を示す。
【０１３４】
＜＜第２種ループ実行時間推定算出処理の実際＞＞
次に、図１７を参照して、第２種ループ実行時間推定算出部２３（図９）の処理を具体的に説明する。
まず、第２種ループ実行時間推定算出部２３には、第２種ループ回数データ系列生成部２２１（図９）から、前記した第２種ループ回数データ系列［０１，５］，［０２，８］，［０３，１０］，［０２，４］，［０３，２０］，［０２，８］が入力され、実行トレース再生部１４ｂ（図９）からは、第２種ループ実行系列「０１，０２，０２，０１，０３，０３，０１，０２，０３，０１，０２」が入力されたものとする。
【０１３５】
ここで、第２種ループ回数データ系列では、前記したように第２種ループＩＤに関し、直前の第２種ループ回数データで第２種ループ回数が同じである場合は、第２種ループ回数データ系列に書き込まない処理を行っているが、第２種ループ実行系列では、そのような処理はなされていない。従って、第２種ループ回数データ系列と、第２種ループ実行系列における第２種ループＩＤの順番にはずれが生じている。
【０１３６】
そこで、第２種ループ実行時間推定算出部２３は、図１７に示すような処理を行うことで、第２種ループ実行時間推定値を算出する。
図１７では、左から順に、現第２種ループＩＤ、現参照第２種ループ回数データ、判定、第２種ループ実行時間推定値、および次の現参照第２種ループ回数データとなっている。ここで、判定とは、現第２種ループＩＤと、現参照第２種ループ回数データにおける第２種ループＩＤとが、一致しているか否かを示すものである。
まず、行６０１における一連の処理ついて説明すると、第２種ループ実行時間推定算出部２３は、第２種ループ実行系列「０１，０２，０２，０１，０３，０３，０１，０２，０３，０１，０２」における先頭の第２種ループＩＤ「０１」を取得し、これを現第２種ループＩＤとする。さらに、第２種ループ実行時間推定算出部２３は、第２種ループ回数データ系列［０１，５］，［０２，８］，［０３，１０］，［０２，４］，［０３，２０］，［０２，８］における先頭の第２種ループ回数データ［０１，５］を取得し、これを現参照第２種ループ回数データとする。
次に、現参照第２種ループ回数データにおける第２種ループＩＤ「０１」と、現第２種ループＩＤ「０１」とは一致するため（判定のフィールド）、第２種ループ実行時間推定算出部２３は、第２種ループ回数データ［０１，５］の第２種ループ回数「５」と、部分プログラムテーブルにおける第２種ループの部分プログラム実行時間推定値とを使用して、第２種ループ実行時間推定値「５×ｔ１」を算出する。ここで、「ｔ１」は、第２種ループＩＤ「０１」の部分プログラム実行時間推定値である。なお、本来、第２種ループ実行時間推定値は、式（２．２）に示すように、該当する部分プログラム先頭命令が「真」となったときの部分プログラム実行時間推定値と、部分プログラム先頭命令が「偽」となったときの部分プログラム実行時間推定値とを用いて計算する必要があるが、説明が煩雑になるのを避けるため図１７における説明では、Ｍ×ｔ（Ｍは、第２種ループ回数、ｔは、該当する部分プログラム実行時間推定値）とする。
【０１３７】
次に、第２種ループ実行時間推定算出部２３は、算出した第２種ループ実行時間推定値「５×ｔ１」を、現第２種ループＩＤ「０１」と対応付けて第２種ループ実行時間テーブルに書き込むと同時に、算出した第２種ループ実行時間推定値「５×ｔ１」を実行時間推定算出部１５ｂ（図９）へ送る。実行時間推定算出部１５ｂは、第２種ループ実行時間推定算出部２３から送られてきた第２種ループ実行時間推定値を送られてきた順に加算していく。
そして、現第２種ループＩＤ「０１」と、現参照第２種ループ回数データにおける第２種ループＩＤとが一致しているため、第２種ループ実行時間推定算出部２３は、次の現参照第２種ループ回数データを、次の第２種回数データである［０２，８］に更新する。
【０１３８】
そして、第２種ループ実行時間推定算出部２３は、行６０２における処理を行うが、この処理は、行６０１における処理を第２種ループＩＤ「０２」に適用したものであるため、説明を省略する。
【０１３９】
行６０２の処理において、現第２種ループＩＤ「０２」と、現参照第２種ループ回数データにおける第２種ループＩＤとが一致しているため、第２種ループ実行時間推定算出部２３は、現参照第２種ループ回数データを、次の第２種ループ回数データ［０３，１０］に更新する。
行６０３の処理において、第２種ループ実行時間推定算出部２３は、第２種ループ実行系列「０１，０２，０２，０１，０３，０３，０１，０２，０３，０１，０２」における３番目の第２種ループＩＤ「０２」を取得し、これを現第２種ループＩＤとする。
【０１４０】
すると、現第２種ループＩＤ「０２」と、現参照第２種ループ回数データ［０３，１０］における第２種ループＩＤ「０３」とは一致しないため、ここで、前記した第２種ループ回数データに書き込まない処理が行われていることがわかる。
そこで、第２種ループ実行時間推定算出部２３は、第２種ループ実行時間テーブルから、直近の第２種ループＩＤ「０２」の第２種ループ実行時間推定値（「８×ｔ２」）を読み出し、読み出した第２種ループ実行時間推定値「８×ｔ２」を実行時間推定算出部１５ｂへ送る。実行時間推定算出部１５ｂは、第２種ループ実行時間推定算出部２３から送られてきた第２種ループ実行時間推定値を送られてきた順に加算していく。
そして、現第２種ループＩＤ「０２」と、現参照第２種ループ回数データ［０３，１０］における第２種ループＩＤ「０３」とが一致していないため、第２種ループ実行時間推定算出部２３は、現第２種ループＩＤ「０２」を次の第２種ループＩＤ「０１」に更新するが、現参照第２種ループ回数データ［０３，１０］を更新しない。
【０１４１】
行６０４でも、現第２種ループＩＤ「０１」と、現参照第２種ループ回数データ［０３，１０］における第２種ループＩＤ「０３」とが一致していないため、第２種ループ実行時間推定算出部２３は、行６０３と同様の処理を、現第２種ループＩＤ「０１」に対して行うことによって、第２種ループ実行時間推定値「５×ｔ１」を第２種ループ実行時間テーブルから読み出し、読み出した第２種ループ実行時間推定値「５×ｔ１」を実行時間推定算出部１５ｂへ送る。
【０１４２】
行６０５において、現第２種ループＩＤ「０３」と、現参照第２種ループ回数データ［０３：１０］における第２種ループＩＤ「０３」とが一致するため、第２種ループ実行時間推定算出部２３は、行６０１，６０２と同様の処理を、第２種ループＩＤ「０３」に適用して行う。そして、現第２種ループＩＤ「０３」と、現参照第２種ループ回数データ［０３，１０］における第２種ループＩＤ「０３」とが一致しているため、第２種ループ実行時間推定算出部２３は、現参照第２種ループ回数データを、次の第２種ループ回数データ［０２，４］に更新する。
以下、行６０６〜６０７についても同様の処理を行い、第２種ループ実行時間推定算出部２３は、第２種ループ実行時間推定値を実行時間推定算出部１５ｂへ送る。
【０１４３】
（実行時間推定算出処理）
ステップＳ２０３の処理が終了すると、実行時間推定算出部１５ｂは、実行トレース再生部１４ｂから送られてくる第２種ループ回数系列以外の部分プログラム実行系列（実際には、部分プログラム実行系列の順に逐次的に送られてくる部分プログラム実行時間推定値）と、第２種ループ実行時間推定算出部２３から送られてくる第２種ループ実行時間推定値とを順次加算することによって、第２種ループを除いた対象プログラムの実行時間の推定値を算出する実行時間推定算出処理を行う（Ｓ１０５ｂ）。第２種ループ以外の実行時間推定算出処理は、第１実施形態と同様である。また、第２種ループに関する実行時間は、第２種ループ実行時間推定算出部２３から順次送られてくる第２種ループ実行時間推定値を、送られてきた順に加算していくことによって算出する。そして、実行時間推定算出部１５ｂは、加算した第２種ループ実行時間推定値と、第２種ループ以外の実行時間推定値とを加算して、最終的な対象プログラムの実行時間を算出する。なお、実行時間推定算出部１５ｂは、第２種ループ回数系列以外の部分プログラム実行時間推定値と、第２種ループ実行時間推定値とを個別に加算しておき、最後に両者を加算することで対象プログラムの実行時間の推定値を算出してもよい。
【０１４４】
（第２実施形態の効果）
プログラムの実行される総命令ステップ数と分岐履歴ビット系列長には強い相関関係があり、例えば非常に膨大な実行時間がかかる対象プログラムに対応する分岐履歴ビット系列長も膨大な長さになってしまうが、第２実施形態のステップＳ２０１、およびステップＳ２０２およびステップＳ２０３の処理により、分岐履歴ビット系列長の長さを削減することができる。従って、第１実施形態では不可能であったような長時間にわたり稼動するようなプログラムの完全な実行履歴を記録することが可能となる。
【０１４５】
なお、実行時間推定算出部１５ｂにおける計算量は、分岐履歴ビット系列長に基本的に比例する。従って、第２実施形態による分岐履歴ビット系列長の削減は、対象プログラムの実行時間推定算出処理における計算時間の削減に直結する。
すなわち、長時間に渡り稼動するような対象プログラムであっても、その対象プログラムの実行時間推定に要する時間を削減することができる。これより、プロセッサアーキテクチャの設計改良や専用コンパイラの改良の際に、対象プログラムの実行時間推定を時間を要することなく、かつ高精度で算出でき、その設計改良効果の評価を効率的に行うことができる。
【０１４６】
また、ある特定の第２種ループにおいて、そのループの処理区間が複数回出現しても第２種ループ回数自体は変化しない場合が多い。ここで、ループの処理区間とは、ループ回数分繰り返した後にループから抜け出すまでを指す。
例えばＭＰＥＧ（Motion Picture Experts Group）などの動画像処理では、同じ画像サイズに対する処理が、繰り返し実行される（ただし画像サイズデータは定数値でなく変数とする場合が多い）。第２実施形態によれば、このような動画像処理プログラムの実行時間推定にかかる時間を削減することが可能となる。
また、ループ外で繰り返し回数が変更されるおそれがあるために、１つの部分プログラムとしてまとめて扱うことが困難なループ（第２種ループ）も、繰り返し回数の系列などを基に他の部分プログラムとは別にループの実行時間を推定することで、１つの部分プログラムとして扱うことが可能となり、短い処理時間でプログラムの実行時間を推定することが可能となる。
【０１４７】
（第３実施形態：構成）
図１８は、第３実施形態に係る実行時間推定装置の構成例を示す図である。
図１８において、前記した他の実施形態と同様の要素については同一の符号を付して説明を省略する。
実行時間推定装置１ｃ（１）は、ｉｆ−ｅｌｓｅ分岐命令の分岐確率（後記）を算出する分岐確率情報抽出部３１、第３種ループ（後記）の縮退を行う第３種ループ縮退部３２を有する。また、プログラム実行履歴情報生成部２２、実行トレース再生部１４ｂ、実行時間推定算出部１５ｂおよび第２種ループ実行時間推定算出部２３は、前記した実施形態と同様の機能を有するため、同一の符号を付して説明を省略する。なお、分岐履歴情報生成部１３ｃは、前記した実施形態で記述した機能に加え、多重ｉｆ−ｅｌｓｅ縮退部３３から送られる縮退情報（後記）を基に、多重ｉｆ−ｅｌｓｅ縮退部３３によって縮退された部分プログラムに該当する分岐履歴ビットを分岐履歴ビット系列に追加しない機能を有する。
【０１４８】
分岐確率情報抽出部３１は、プログラム分割部１１、部分プログラム実行時間推定算出部１２、分岐履歴情報生成部１３および実行トレース再生部１４を有するが、これらの機能は前記した実施形態と同様の機能を有するため、同一の符号を付して説明を省略する。
また、分岐確率情報抽出部３１は、各ｉｆ−ｅｌｓｅ分岐命令が、「真」および「偽」となる確率である条件変数別分岐確率を算出する条件変数別確率算出部３１１をさらに有する。
【０１４９】
第３種ループ縮退部３２は、第１種・第２種ループ判別処理部２１１および第１種ループ縮退部２１２を含むがこれらは、前記した実施形態における機能と同様であるため説明を省略する。また、第３種ループ縮退部３２は、部分プログラムテーブルにおいてｉｆ−ｅｌｓｅ縮退処理（後記）を行い、ｉｆ−ｅｌｓｅ縮退済みの部分プログラムを第１種・第２種ループ判別処理部２１１や、第１種ループ縮退部２１２へ送ったり、縮退した部分プログラムＩＤと、該当するｉｆ−ｅｌｓｅ分岐命令との対の情報である縮退情報を分岐履歴情報生成部１３ｃへ送ったりする多重ｉｆ−ｅｌｓｅ縮退部３３をさらに有する。
多重ｉｆ−ｅｌｓｅ縮退部３３は、後記して説明するｉｆ−ｅｌｓｅ縮退処理を行うｉｆ−ｅｌｓｅ縮退部３３１と、やはり後記して説明する隣接縮退処理を行う隣接縮退部３３２とを有する。
【０１５０】
なお、図１８に示す各部１１，１２，１３，１３ｃ，１４，１４ｂ，１５ｂ，２２，２３，３１，３２，３３，２１１，２１２，２２１，３１１，３３１，３３２は、図２の記憶装置１７０などに記憶されている実行時間推定プログラムが、ＲＡＭ１５３に展開され、ＣＰＵ１５１が実行することによって具現化する。
【０１５１】
具体的な処理の説明を行う前に、第３実施形態における処理の概要を説明する。
対象プログラムにｉｆ−ｅｌｓｅ分岐命令を含むループが含まれている場合、このループは、第２実施形態で前記した条件Ｚ１を満たさないため、たとえループ回数が定数値（条件Ｚ２）または固定値（条件Ｚ３）であっても、第２実施形態における第１種ループ縮退処理および第２種ループ縮退処理を直接適用することができない。
しかし、後記して説明する方法によれば、各ｉｆ−ｅｌｓｅ分岐命令の分岐確率が計算できる。この分岐確率を用いてｉｆ−ｅｌｓｅ分岐ブロック全体の処理時間の統計的予測値を計算すれば、第２実施形態におけるループの分岐縮退処理を適用できる場合が生じ、第２実施形態における分岐履歴ビット系列長の削減効果を大きくすることができる。条件Ｚ１を満たさず、条件Ｚ２または条件Ｚ３を満たすループを、以降「第３種ループ」と記載する。以下に、具体的な実装方法を説明する。
【０１５２】
次に、図１８を参照しつつ、図１９に沿って第３実施形態に係るプログラム実行時間推定方法を説明する。
図１９は、第３実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。
【０１５３】
（分岐確率情報抽出処理）
まず、分岐確率情報抽出部３１が、すべてのｉｆ−ｅｌｓｅ分岐命令の分岐確率を算出する分岐確率情報抽出処理を行う（Ｓ３０１）。
【０１５４】
以下、図１８を参照しつつ図２０に沿って分岐確率情報抽出処理の具体的な処理を説明する。
図２０は、第３実施形態に係る分岐確率情報抽出処理の流れを示すフローチャートである。
まず、分岐確率情報抽出部３１のプログラム分割部１１がプログラム分割処理を行い（Ｓ１０１）、部分プログラム実行時間推定算出部１２が、部分プログラム実行時間推定算出処理を行う（Ｓ１０２）。そして、分岐確率情報抽出部３１の分岐履歴情報生成部１３が分岐履歴情報生成処理を行い（Ｓ１０３）、実行トレース再生部１４が、実行トレース再生処理を行う（Ｓ１０４）。ステップＳ１０１〜Ｓ１０４の各処理は、前記した実施形態と同様の処理であるため、同一のステップ番号を付して詳細な説明を省略する。ステップＳ１０４の実行トレース再生処理が行われた結果、部分プログラム実行系列が生成される。
ここでは、第１実施形態で用いた以下の部分プログラム実行系列が生成されたとする。
【０１５５】
ｍａｉｎ：ｓｔａｒｔ→［Ｔ１］→Ａ（１）→［Ｔ２］→Ｂ（１）→［Ｔ４］→Ａ（１）→［Ｔ２］→Ｂ（０）→［Ｔ５］→Ｃ（１）→［Ｔ６ａ］→ｆｕｎｃ１：ｓｔａｒｔ→［Ｔ８］→Ｄ（１）→［Ｔ９］→Ｄ（１）→［Ｔ９］→Ｄ（０）→［Ｔ１０］→Ｅ（１）→［Ｔ１１］→ｆｕｎｃ１：ｅｎｄ→［Ｔ６ｂ］→Ａ（０）→［Ｔ３］  →ｍａｉｎ：ｅｎｄ
【０１５６】
＜条件変数別確率算出処理＞
次に、条件変数別確率算出部３１１が、以下に記載する手順に従って、生成された部分プログラム実行系列を基に条件変数別確率を算出する条件変数別確率算出処理を行う（Ｓ３０１１）。
まず，条件変数別確率算出部３１１は、部分プログラム実行系列における各分岐履歴ビットと、これらに対応する条件変数を抜き出し、以下のような系列を生成する。
【０１５７】
Ａ（１）  Ｂ（１）  Ａ（１）  Ｂ（０）  Ｃ（１）  Ｄ（１）  Ｄ（１）  Ｄ（０）  Ｅ（１）  Ａ（０）
【０１５８】
そして、条件変数別確率算出部３１１は、各条件変数の真偽の頻度を条件変数別に個別積算することで分岐確率を求める。
前記した部分プログラム実行系列の例から算出される条件変数別分岐確率（すべての条件分岐命令の分岐確率）は以下の通りになる。
【０１５９】
ｐ（Ａ）＝２／３（「真」＝２回、「偽」＝１回）
ｐ（Ｂ）＝１／２（「真」＝１回、「偽」＝１回）
ｐ（Ｃ）＝１／１（「真」＝１回、「偽」＝０回）
ｐ（Ｄ）＝２／３（「真」＝２回、「偽」＝１回）
ｐ（Ｅ）＝１／１（「真」＝１回、「偽」＝０回）
【０１６０】
なお、このような構成以外にも分岐確率を直接計算する既知方法による計算部で代替してもよい。
【０１６１】
図２１は、第３種ループの他の例を含む対象プログラムを示す図であり、図２２は、図２１に示す対象プログラムから生成される部分プログラムテーブルの例を示す図である
ここでは、、ｂｒａｎｃｈ（Ｊ）とｂｒａｎｃｈ（Ｈ）に着目したとき、条件「Ｊ」が真（ｂｒａｎｃｈ（Ｊ）「Ｔ」）である確率を「ｐ（Ｊ）」（０≦ｐ（Ｊ）≦１）とし、条件「Ｈ」が真（ｂｒａｎｃｈ（Ｈ）「Ｔ」）である確率を「ｐ（Ｈ）」（０≦ｐ（Ｈ）≦１）とする。ここで示すような確率を条件変数別分岐確率情報という。
【０１６２】
（多重ｉｆ−ｅｌｓｅ縮退処理）
図１９に戻り、ステップＳ３０１の後、多重ｉｆ−ｅｌｓｅ縮退部３３が多重ｉｆ−ｅｌｓｅ縮退処理を行う（Ｓ３０２）。
【０１６３】
ここで、図１８を参照しつつ、図２３に沿って多重ｉｆ−ｅｌｓｅ縮退処理の詳細な処理を説明する。
図２３は、第３実施形態に係る多重ｉｆ−ｅｌｓｅ縮退処理の流れを示す図である。
ステップＳ３０２では、部分プログラムテーブルにおけるすべてのｉｆ−ｅｌｓｅブロックについてステップＳ３０２２およびステップＳ３０２３の処理が実行される（Ｓ３０２１）。
まず、ｉｆ−ｅｌｓｅ縮退部３３１が、ｉｆ−ｅｌｓｅ縮退処理を行うと（Ｓ３０２２）、隣接縮退部３３２が、隣接縮退処理を行う（Ｓ３０２３）。そして、前記したように、多重ｉｆ−ｅｌｓｅ縮退部３３は、部分プログラムテーブルにおけるすべてのｉｆ−ｅｌｓｅブロックについてステップＳ３０２２およびステップＳ３０２３を繰り返す（Ｓ３０２４）。ここで、詳細は後記するが、ｉｆ−ｅｌｓｅ縮退処理とは、同じｉｆ−ｅｌｓｅ分岐命令を「部分プログラム先頭命令」に有し、かつ「部分プログラム終端命令」が同じである行を１つにまとめることによりｉｆ−ｅｌｓｅブロックに係る部分プログラムを縮退する処理である。また、隣接縮退処理とは、部分プログラム終端命令がｉｆ−ｅｌｓｅ分岐命令でない部分プログラムについて、その部分プログラム終端命令を部分プログラム先頭命令として有する他の部分プログラムと縮退することによってｉｆ−ｅｌｓｅ分岐命令を含まない隣接する２つの部分プログラムを縮退する処理である。
多重ｉｆ−ｅｌｓｅ縮退部３３は、これらの縮退処理を行った部分プログラムテーブルを第１種・第２種ループ判別処理部２１１や、第１種ループ縮退部２１２へ送ると同時に、縮退した部分プログラムＩＤと、該当するｉｆ−ｅｌｓｅ分岐命令との対の情報である縮退情報をプログラム実行履歴情報生成部２２で起動される分岐履歴情報生成部１３ｃへ送る。
【０１６４】
図２４の対象プログラム例と、図２４の対象プログラム例に対応する図２５の部分プログラムテーブルで多重ｉｆ−ｅｌｓｅ縮退処理の具体的な説明を行う。
図２４は、第３種ループを含む対象プログラムの例を示す図であり、図２５は、図２４に示す対象プログラムから生成される部分プログラムテーブルの例を示す図である。
なお、図２５に示す部分プログラムテーブルは、分岐確率情報抽出部３１で生成されるテーブルである。
図２４における「ループ３」は、第３種ループに該当するループである（変数「Ｋ」は、定数値もしくは「ループ３」の実行最中は不変であるとする）。「ループ３」内部に位置するｉｆ−ｅｌｓｅ分岐命令における条件「Ｈ」が真（Ｔ）である確率がｈ（＝ｐ（Ｈ））（０≦ｈ≦１）であったとすると、ループ３の実行時間を以下の式（３．１）で近似する。確率ｈは、分岐確率情報抽出処理において前記した方法で求めることができる。
【０１６５】
Ｔ＿Ｌ３＝（Ｔ２１＋ｈ×Ｔ２３＋（１−ｈ）×Ｔ２４）×Ｋ＋Ｔ２２・・・（３．１）
【０１６６】
式（３．１）は、図２４における「ループ３」が繰り返されるたびに必ず実行される部分プログラムの実行時間「Ｔ２１」と、条件「Ｈ」が「真」（確率ｈ）であったときの実行時間「Ｔ２３」と、条件「Ｈ」が「偽」（確率１−ｈ）であったときの実行時間「Ｔ２４」との単純な確率重付和（ｈ×Ｔ２３＋（１−ｈ）×Ｔ２４）をもって、「ループ３」を１回実行したときの実行時間として推定している計算式である。ループ回数「Ｋ」が定数値であれば、ループ３のループ実行時間推定算出値はこの段階で定数値として扱うことができ（つまり、実行時間推定装置１ｃは、この処理以降当該ループを第１種ループとして扱う）、もし「Ｋ」がループ外では変数であるが、ループ内では固定した値であれば、第２実施形態における処理によってループ実行時間推定値を計算できる（つまり、実行時間推定装置１ｃは、この処理以降当該ループを第２種ループとして扱う）。
【０１６７】
具体的には、多重ｉｆ−ｅｌｓｅ縮退部３３は、ｉｆ−ｅｌｓｅ縮退処理および隣接縮退処理をそれぞれの条件（図２２における「Ｈ」，「Ｊ」）について行う。
まず、第３種ループ縮退部３２は、図２２の部分プログラムテーブルを参照し、同じ条件分岐命令を部分プログラム先頭命令として有し、さらに部分プログラムプログラム終端命令が同じである部分プログラムを検索する。例えば、ｉｆ−ｅｌｓｅ縮退部３３１は、条件「Ｊ」（ｂｒａｎｃｈ（Ｊ））を部分プログラム先頭命令に有し、条件「Ｇ」（ｂｒａｎｃｈ（Ｇ））を部分プログラム終端命令に有する部分プログラム「４５」と「４６」とを検出する。このとき、部分プログラム「４５」と「４６」との合計実行時間「Ｔ４５’」は、分岐確率情報抽出部３１から取得している条件「Ｊ」の確率「ｊ（＝ｐ（Ｊ））」と、部分プログラム「４５」の推定実行時間「Ｔ４５」と、部分プログラムＩＤ「４６」の実行時間「Ｔ４６」とを用いることにより式（３．１）を条件「Ｊ」に適用した次の式（３．２）で表すことができる。
【０１６８】
Ｔ４５’＝ｊ×Ｔ４５＋（１−ｊ）×Ｔ４６・・・（３．２）
【０１６９】
これを、部分プログラム「４５」と「４６」とを「４５’」に縮退した部分プログラムＩＤ「４５’」を新たに部分プログラム実行時間推定値の欄に格納することにより、ｉｆ−ｅｌｓｅ縮退部３３１は、図２６（ａ）に示す部分プログラム「４５」と「４６」とをｉｆ−ｅｌｓｅ縮退処理した部分プログラムテーブルを生成する。
そして、ｉｆ−ｅｌｓｅ縮退部３３１は、図２２において同時に部分プログラム終端命令が「ｂｒａｎｃｈ（Ｊ）」である部分プログラムＩＤ「４３」も図２６に示すように「ｂｒａｎｃｈ（Ｊ）」が縮退された命令であることを示す「Ｒｅｄｕｃｅ＿Ｂ＿Ｊ」に置換する。
【０１７０】
ここで、図２６は、縮退処理を行った部分プログラムテーブルの例であり、（ａ）は「Ｊ」に対するｉｆ−ｅｌｓｅ縮退処理を行った結果を示し、（ｂ）は（ａ）の結果に対して隣接縮退処理を行った結果であり、（ｃ）は「Ｈ」に対するｉｆ−ｅｌｓｅ縮退処理を行った結果であり、（ｄ）は（ｃ）の結果に対して隣接縮退処理を行った結果である。
【０１７１】
次に、隣接縮退部３３２は、隣接縮退処理を行う。隣接縮退処理とは、前記したように部分プログラム終端命令がｉｆ−ｅｌｓｅ分岐命令でない部分プログラムについて、その部分プログラム終端命令を部分プログラム先頭命令として有する他の部分プログラムと縮退する処理である。
【０１７２】
具体的には、図２６（ａ）における部分プログラムＩＤ「４３」の部分プログラム終端命令と、部分プログラムＩＤ「４５’」の部分プログラム先頭命令が同じであるので、第３種ループ縮退部３２は、これらを隣接縮退処理することにより、図２６（ｂ）の部分プログラム「４３’」のような形にする。
【０１７３】
以下、ｉｆ−ｅｌｓｅ縮退部３３１は、条件「Ｈ」に関しても同様に、ｉｆ−ｅｌｓｅ縮退処理を行って図２６（ｃ）に示す部分プログラムテーブルを生成し、さらに隣接縮退部３３２が、隣接縮退処理を行うことにより図２６（ｄ）に示す部分プログラムテーブルを生成する。
【０１７４】
この時点において、図２１における「ループ６」のループ継続条件命令における式「Ｇ＝ｉ＜Ｋ」の「Ｋ」が定数回であれば、図２６（ｄ）に示す部分プログラムテーブルは、第１種ループとして扱うことができ（第１種ループに縮退可能）、「Ｋ」が固定回であれば、図２６（ｄ）に示す部分プログラムテーブルは、第２種ループとして扱うことができる（第２種ループに縮退可能）。
【０１７５】
図１９に戻り、ステップＳ３０２以降の処理は、前記して説明した実施形態の処理と同様であるため説明を省略する。なお、ステップＳ２０２のプログラム実行履歴情報生成処理において、第２実施形態と同様に対象プログラムの書き換えが行われるが、このとき挿入される関数は、多重ｉｆ−ｅｌｓｅ縮退部３３から送られた縮退情報や、第１種・第２種ループ判別処理部２１１から送られた第１種ループ情報および第２種ループ情報を使用して、ステップＳ３０２や、ステップＳ２０１で縮退された部分プログラムに対応する分岐履歴ビットを出力しない関数が挿入される形で書き換えが行われる。
【０１７６】
（第３実施形態の効果）
第３実施形態によれば、各ｉｆ−ｅｌｓｅ分岐命令の分岐確率を用いてｉｆ−ｅｌｓｅブロック全体の処理時間の統計的予測値を計算することにより第２実施形態における分岐履歴ビット系列長の削減効果を大きくすることができる。
【０１７７】
（第４実施形態：構成）
図２７は、第４実施形態に係る実行時間推定装置の構成例を示す図である。
実行時間推定装置１ｄ（１）は、分岐履歴情報抽出部３１、実行トレース再生部１４ｃおよび実行時間推定算出部１５を有するが、これらの機能は、前記した実施形態と同様であるため同一の符号を付して説明を省略する。
実行時間推定装置１ｄは、多重ループの縮退処理を実行する多重ループ縮退部４１と、多重ループ縮退部４１で縮退された部分プログラム以外の分岐履歴ビット系列を生成する分岐履歴情報生成部１３ｄとをさらに有する。
【０１７８】
多重ループ縮退部４１は、ｉｆ−ｅｌｓｅ縮退部３３１と、隣接縮退部３３２とを有するが、これらは前記した実施形態における機能と同様であるため、同一の符号を付して説明を省略する。多重ループ縮退部４１は、第４種ループ（後記）の縮退処理を行う第４種ループ縮退部４１１をさらに有する。なお、多重ループ縮退部４１は、縮退した部分プログラムＩＤと、該当する条件分岐命令（縮退されたｉｆ−ｅｌｓｅ分岐命令と、ループ継続条件命令）との対の情報である縮退情報を分岐履歴情報生成部１３ｄへ送る機能を有する。
【０１７９】
なお、図２７に示す各部１１，１２，１３，１３ｄ，１４，１５，３１，４１，３１１，３３１，３３２，４１１は、図２の記憶装置１７０などに記憶されている実行時間推定プログラムが、ＲＡＭ１５３に展開され、ＣＰＵ１５１が実行することによって具現化する。
【０１８０】
まず、具体的な処理の説明を行う前に第４実施形態における処理の概要を説明する。
第３実施形態に記載の技術において、このままでは多重ループ構造の縮退ができない場合がある。
例えば、図２８に示す対象プログラムの例のように、「ループ４」の内部に第３種ループである「ループ５」が内包されている場合である。
ここで、図２８は、第４種ループ（後記）を含む対象プログラムの例を示す図である。
図２８に示すような対象プログラムのように「ループ５」の繰り返し数を決定する変数「Ｙ」がその直前で更新する（「ループ４」実行最中に「Ｙ」が変化する可能性がある）場合、「ループ４」の実行時間を推定するためには、それぞれの「Ｙ」の値の情報（「ループ５」の第２種ループ回数データ系列）が必要であるため、第１〜第３実施形態に記載の技術では、この２重ループ全体の縮退ができない。
【０１８１】
しかし、以下に示す条件下（条件Ｘ１∩条件Ｘ２）では、多重ループであっても、その「平均」実行時間を正確に推定することができる。
条件Ｘ１：ループ内部に「ループ継続条件命令」がちょうど一つだけ存在する。
条件Ｘ２：条件Ｘ１を満たさないループをループブロック内部に含まない。
【０１８２】
ここで、「ループ継続条件命令」とは、ループ処理を継続するか否かを決定する分岐を指す。例えば図２８において、「ループ４」では条件「Ｐ」が唯一のループ継続条件命令であり、「ループ５」では条件「Ｑ」が唯一のループ継続条件命令である。
条件Ｘ１に当てはまらない例としては、例えば終了条件を持つ「ｆｏｒ」ループや「ｗｈｉｌｅ」ループの内部に「ｂｒｅａｋ」文または「ｒｅｔｕｒｎ」文を含むケースが挙げられる。
また、条件Ｘ２は、ループ内部に条件Ｘ１を満たすループを内包することができることを指し、多重ループ構造を扱うための条件である。以降、（条件Ｘ１∩条件Ｘ２）を満たすループを「第４種ループ」と記載する。
【０１８３】
次に、図２７を参照しつつ、図２９に沿って第４実施形態に係るプログラム実行時間推定方法を説明する。
図２９は、第４実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。
【０１８４】
（確率情報抽出処理）
まず、分岐確率情報抽出部３１が、第３実施形態で説明した分岐確率情報抽出処理を行う（Ｓ３０１）。ステップＳ３０１は、第３実施形態で説明した処理と同様であるため、説明を省略する。次に、多重ループ縮退部４１が多重ループ縮退処理を行う（Ｓ４０１）。
【０１８５】
（多重ループ縮退処理）
ここで、図２７を参照しつつ、図３０に沿って多重ループ縮退処理の詳細な処理を説明
する。
図３０は、第４実施形態に係る多重ループ縮退処理の流れを示す図である。なお、図３０において前記した実施形態と同様の処理については、同一のステップ番号を付して説明を省略する。なお、多重ループ縮退部４１は、前記した第１種・第２種ループ判別処理部２１１（図９）と同様の機能を有しており、この機能によって、第２種ループと判別されたループに関して、多重ループ縮退部４１は、以下のステップＳ４０１１〜Ｓ４０１６の処理を行わない。
多重ループ縮退部４１は、部分プログラムテーブルにおけるすべての多重ループについてステップＳ３０２２〜Ｓ４０１５の処理を実行する（Ｓ４０１１）。
まず、多重ループ縮退部４１のｉｆ−ｅｌｓｅ縮退部３３１が、ｉｆ−ｅｌｓｅ縮退処理を行うと（Ｓ３０２２）、多重ループ縮退部４１の隣接縮退部３３２が、隣接縮退処理を行う（Ｓ３０２３）。ステップＳ３０２２およびステップＳ３０２３の処理は、第３実施形態で説明した処理と同様である。
【０１８６】
次に、多重ループ縮退部４１は、処理対象となっているループブロック内のすべてのループについて、内側のループから順にステップＳ４０１３およびステップＳ４０１４の処理を行う（Ｓ４０１２）。
まず、多重ループ縮退部４１の第４種ループ縮退部４１１が、前記して説明した第４種ループを縮退する第４種ループ縮退処理を行う（Ｓ４０１３）。そして、多重ループ縮退部４１の隣接縮退部３３２が、第４種縮退処理が行われた部分プログラムテーブルに対し、隣接縮退処理を行う（Ｓ４０１４）。ステップＳ４０１３，Ｓ４０１４の処理の詳細は、後記して説明する。前記したように、多重ループ縮退部４１は、ループブロック内のすべてのループについて、内側のループから順にステップＳ４０１３，Ｓ４０１４の処理を行う（Ｓ４０１５）。
【０１８７】
そして、ループブロック内のすべてのループについて、内側のループから順にステップＳ４０１３，Ｓ４０１４の処理が終了すると、多重ループ縮退部４１は、前記したように部分プログラムテーブルにおけるすべての多重ループについてステップＳ３０２２〜ステップＳ４０１５の処理を繰り返す（Ｓ４０１６）。
処理が終了すると、多重ループ縮退部４１は、縮退した部分プログラムＩＤと、該当するｉｆ−ｅｌｓｅ分岐命令や、ループ継続条件命令との対の情報である縮退情報を分岐履歴情報生成部１３ｃへ送る。
【０１８８】
＜＜多重ループ縮退処理の実際＞＞
図２８に示す対象プログラムと、図３１に示す、図２８の対象プログラムに対応する部分プログラムテーブルを用いて多重ループ縮退処理の実際を説明する。
前記したように、変数「Ｘ」はループ４実行中は不変であり、変数「Ｙ」はループ５実行中は不変である。
このときの条件「Ｓ」、「Ｑ」および「Ｒ」の分岐確率を表にしたものを図３２に示す。このとき、図２８の「ループ４」および「ループ５」の平均繰り返し回数は、以下の式（４．１）、（４．２）で計算できる。
【０１８９】
Ｃ＿Ｌ４ｍｅａｎ＝ｓ／（１−ｓ）・・・（４．１）
【０１９０】
Ｃ＿Ｌ５ｍｅａｎ＝ｑ／（１−ｑ）・・・（４．２）
【０１９１】
ここで、確率ｓ（＝ｐ（Ｓ））は、条件「Ｓ」が「真」となる確率であり、確率ｑ（＝ｐ（Ｑ））は、条件「Ｑ」が「真」となる確率である。
式（４．１）および式（４．２）の根拠は、条件「Ｐ」および「Ｑ」がループ継続条件命令であることによる。すなわち、あるループの継続条件が「真」であった頻度をＳＴ回とし、継続条件が「偽」であった頻度をＳＦ回としたとき、ＳＴはプログラム全体においてループが繰り返された総回数であり、ＳＦはプログラム全体においてループから抜け出た回数（つまりループの実行回数（繰り返し回数））であるので、ループの平均繰り返し回数はＳＴ／ＳＦとなり、これはループの継続条件の「真」確率と「偽」確率の比と同じである。従って、「ループ４」の平均実行時間推定値Ｔ＿Ｌ４（ループの平均実行時間）および「ループ５」の平均実行時間推定値Ｔ＿Ｌ５は、図３１に示す部分プログラム実行時間推定値の値を用いることにより、以下の式（４．３）および式（４．４）で計算できる。
【０１９２】
Ｔ＿Ｌ４＝（Ｔ３１＋Ｔ＿Ｌ５ｍｅａｎ）×Ｃ＿Ｌ４ｍｅａｎ・・・（４．３）
【０１９３】
Ｔ＿Ｌ５＝（Ｔ３３＋ｒ×Ｔ３５＋（１−ｒ）×Ｔ３６）×Ｃ＿Ｌ５ｍｅａｎ・・・（４．４）
【０１９４】
ここで、確率ｒ（＝ｐ（Ｒ））は、条件「Ｒ」が「真」となる確率である。
このような第４種ループ平均実行時間計算処理により、ｉｆ−ｅｌｓｅブロックを含む多重ループ全体を単一の部分プログラムに縮退することができる。
【０１９５】
＜＜多重ループ縮退処理の実際＞＞
以下、図３１〜図３４を参照しつつ多重ループ縮退処理（Ｓ４０１）をさらに詳細に説明する。
まず、前記したように多重ループ縮退部４１のｉｆ−ｅｌｓｅ縮退部３３１は、前記したｉｆ−ｅｌｓｅ縮退処理を行い、続いて隣接縮退部３３２が隣接縮退処理を行って部分プログラムテーブルの縮退を行う。
つまり、ｉｆ−ｅｌｓｅ縮退部３３１は、分岐確率情報抽出部３１から取得した図３１の部分プログラムテーブルの下から逐次的に「部分プログラム先頭命令」における条件変数が同一の部分プログラムを検出する（図３１の例では、まず部分プログラム「３５」，「３６」が検出される）。続いて、ｉｆ−ｅｌｓｅ縮退部３３１は、第３実施形態で前記した方法と同様の方法によって、部分プログラム「３５」，「３６」のｉｆ−ｅｌｓｅ縮退処理を行い図３３（ａ）に示す部分プログラムテーブルを生成する。
【０１９６】
ここで、図３３は、ｉｆ−ｅｌｓｅ縮退処理および隣接縮退処理が行われた部分プログラムテーブルの例を示す図であり、（ａ）はｉｆ−ｅｌｓｅ縮退処理が行われた例、（ｂ）は（ａ）の結果に隣接縮退処理を行った例を示す。
なお、図３３（ａ）において、部分プログラム「３５’」の実行時間推定値は、式（３．２）を適用した値である。
さらに、第４種ループ縮退部４１１は、図３３（ａ）において「部分プログラム終端命令」と「部分プログラム先頭命令」とが同一である部分プログラム「３３」，「３５’」に対して隣接縮退処理を行い、部分プログラム「３３」，「３５’」が縮退された部分プログラム「３３’」を有する部分プログラムテーブル（図３３（ｂ））を生成する。
【０１９７】
ここで、図３３（ｂ）に示す部分プログラムテーブルを参照すると、部分プログラム「３３’」は、「部分プログラム先頭命令」と「部分プログラム終端命令」との条件変数とが同一であるので、第２実施形態で前記したようにループであると判定できる。そして、部分プログラム「３３’」，「３４」（図２８の「ループ５」に相当）は、部分プログラム先頭命令の条件変数が同一であるので、ループ縮退できることが分かる。
そこで、第４種ループ縮退部４１１は、式（４．１），（４．２）と同様の方法で、部分プログラム「３３’」，「３４」に対応する「ループ５」の平均繰り返し回数を求め、式（４．３），（４．４）と同様の方法で「ループ５」の平均実行時間を求める。そして、第４種ループ縮退部４１１は、部分プログラム「３３’」，「３４」を縮退した部分プログラム「３３’’」の実行時間推定値のフィールドに算出した「ループ５」の平均実行時間を格納した図３４（ａ）に示す部分プログラムテーブルを生成する。
【０１９８】
ここで、図３４は、図３３（ｂ）に示す部分プログラムテーブルに対し各縮退処理を行った例であり、（ａ）は図３３（ｂ）の結果に第４種ループ縮退処理を行った例、（ｂ）は（ａ）の結果に隣接縮退処理を行った例、（ｃ）は（ｂ）の結果に第４種ループ縮退処理を行った例、（ｄ）は（ｃ）の結果に隣接縮退処理を行った例である。
さらに第４種ループ縮退部４１１は、図３４（ａ）において部分プログラム「３１」と「３３’’」とを隣接縮退した部分プログラムテーブル（図３４（ｂ））を生成する。なお、図３４（ａ）における「Ｃ＿Ｌ５」は、図２８の「ループ５」における平均繰り返し回数である（式（４．２））。
【０１９９】
同様に、第４種ループ縮退部４１１は、図３４（ｂ）における部分プログラム「３１’」，「３２」（図２８の「ループ４」に相当）にも同様にループ縮退処理を行って図３４（ｃ）に示す部分プログラムテーブルを生成する。さらに、第４種ループ縮退部４１１は、図３４（ｃ）に示す部分プログラムテーブルに対し、隣接縮退処理を行って図３４（ｄ）に示す部分プログラムテーブルを生成する。なお、図３４（ｃ）における「Ｃ＿Ｌ４」は、図２８の「ループ４」における平均繰り返し回数である（式（４．１））。
以上の処理により、図３１に示す部分プログラムテーブルを、図３４（ｄ）に示す部分プログラムテーブルまで縮退することができる。
ステップＳ４０１以降の処理は、ステップＳ３０１およびステップＳ４０１で生成した情報を使用する以外は、前記した実施形態と同様であるため、説明を省略する（Ｓ１０３ｄ，Ｓ１０４ｅ，Ｓ１０５）。
【０２００】
このように、第４種ループ縮退処理は、第１種ループ縮退処理と類似しているが、ループ回数が、第１種ループ縮退処理では定数であるのに対し、第４種ループ縮退処理では、ループ回数が分岐確率から求まる平均繰り返し回数である点が異なっている。
【０２０１】
（第４実施形態の効果）
第４実施形態によれば、多重ループ縮退部４１による多重ループ縮退により、「固定ループ回数系列」を生成することなく、分岐履歴ビット系列長の削減効果をさらにあげることができ、場合によってはプログラム全体をただひとつの部分プログラムに縮退できることもできる。
【０２０２】
（第５実施形態）
図３５は、第５実施形態に係る実行時間推定装置の構成例を示す図である。
実行時間推定装置１ｇ（１）は、プログラム分割部１１、部分プログラム実行時間推定算出部１２、分岐履歴情報生成部１３，１３ｄ、実行トレース再生部１４，１４ｃ、実行時間推定算出部１５を有するが、これらの機能は、前記した実施形態と同様であるため同一の符号を付して説明を省略する。
実行時間推定装置１ｇは、部分プログラム実行系列における各部分プログラムの出現頻度である部分プログラム実行頻度を算出する部分プログラム実行頻度算出部８１と、部分プログラム実行時間推定値および部分プログラム実行頻度を基に関数の縮退処理を行う関数縮退部８２とをさらに有する。
つまり、図３５に示す実行時間推定装置１ｇは、図２７に示す実行時間推定装置１ｄにおいて、条件変数別確率算出部３１１が部分プログラム実行頻度算出部８１に置き換わり、多重ループ縮退部４１が関数縮退部８２に置き換わった構成を有している。
また、分岐履歴情報生成部１３ｄは、関数縮退部８２から送られた縮退情報と、対象プログラムを用いて分岐履歴ビット系列を生成する機能を有している。
【０２０３】
なお、図３５に示す各部１１，１２，１３，１３ｄ，１４，１４ｃ，１５，８１，８２は、図２の記憶装置１７０などに記憶されている実行時間推定プログラムが、ＲＡＭ１５３に展開され、ＣＰＵ１５１が実行することによって具現化する。
【０２０４】
まず、具体的な処理の説明を行う前に第５実施形態における処理の概要を説明する。
ここで、ループ内に「ｂｒｅａｋ」文および「ｒｅｔｕｒｎ」文を含む対象プログラムの例を示す図である。
例えば、図３６に示す対象プログラムは、「ループ１０」の内部に「ｂｒｅａｋ」文があり、「ループ１１」の内部に「ｒｅｔｕｒｎ」文があるため、両者とも第４種ループではなく前記した実施形態に記載の技術では縮退できない。
このような対象プログラムに対しては、本実施形態に記載の技術によって図３６に示すような「ループ１０」および「ループ１１」を含む関数を縮退することができる。
【０２０５】
次に、図３５を参照しつつ、図３７に沿って第５実施形態に係るプログラム実行時間推定方法を説明する。
図３７は、第５実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。
図３７において、ステップＳ１０１〜Ｓ１０５は前記した実施形態と同様の処理であるため、説明を省略する。ステップＳ１０４の実行トレース再生処理の後、部分プログラム実行頻度算出部８１が部分プログラム実行頻度算出処理を行った後（Ｓ７０１）、関数縮退処理部７２が関数縮退処理を行う（Ｓ７０２）。
そして、分岐履歴情報生成部１３ｄが、関数縮退部８２から取得した縮退情報と、対象プログラムとを基に分岐履歴ビット系列を生成する分岐履歴情報生成処理を行う（Ｓ１０３ｅ）。以降の処理は、図２９と同様であるため説明を省略する。
【０２０６】
＜＜部分プログラム実行頻度算出処理の実際＞＞
次に、図３８に示す、図３６の対象プログラムに対応する部分プログラムテーブルを用いて部分プログラム実行頻度算出処理の実際を説明する。
図３８は、部分プログラム実行頻度の情報を記述した部分プログラムテーブルの例を示す図である。
ここで、「部分プログラム実行頻度」を「部分プログラム実行系列」における各部分プログラムの出現頻度と定義する。つまり、部分プログラム実行頻度は、部分プログラムにおける条件分岐において、「Ｔｒｕｅ」と「Ｆａｌｓｅ」の生起頻度から算出される。なお、部分プログラム実行頻度は、先頭が分岐命令である部分プログラムについては、第３実施形態において説明した分岐確率の計算式の「真偽の頻度」と同じである。
【０２０７】
条件Ｕ：Ｔｒｕｅ頻度＝Ｃ６１，Ｆａｌｓｅ頻度＝Ｃ６２
条件Ｖ：Ｔｒｕｅ頻度＝Ｃ６３，Ｆａｌｓｅ頻度＝Ｃ６４
条件Ｗ：Ｔｒｕｅ頻度＝Ｃ６６，Ｆａｌｓｅ頻度＝Ｃ６７
条件Ｚ：Ｔｒｕｅ頻度＝Ｃ６８，Ｆａｌｓｅ頻度＝Ｃ６９
【０２０８】
ここで、「Ｕ」、「Ｖ」、「Ｗ」、「Ｚ」は、図３６に示す対象プログラムにおける分岐条件である。
【０２０９】
このように算出した部分プログラム実行頻度を、部分プログラムＩＤに対応付けて部分プログラムテーブルに格納した例を図３８に示す。
【０２１０】
＜＜関数縮退処理＞＞
次に、図３９に示す、図３６の対象プログラムに対応する部分プログラムテーブルを用いて関数縮退処理の実際を説明する。
図３９は、図３８に示す部分プログラムテーブルに対し縮退処理を行った例であり、（ａ）は、関数ｆｕｎｃ４縮退処理を行った例、（ｂ）は、部分プログラム「６３」の縮退処理を行った例、（ｃ）は、縮退後の最終的な部分プログラムテーブルの例である。
「部分プログラム全実行時間推定値」を以下の式（５．１）で定義する。
【０２１１】
「部分プログラム全実行時間推定値」＝「部分プログラム実行時間推定値」×「部分プログラム実行頻度」・・・（５．１）
【０２１２】
すると、「関数の全実行時間推定値」は「関数内の部分プログラム全実行時間推定値の総和」として計算できる。ただし、ここでは「関数内の部分プログラム」は関数呼び出し命令を含まないものとする。例えば、この時点のｍａｉｎ関数は、ｆｕｎｃ４を呼び出す部分プログラムを含んでいるため、このままでは関数の全実行時間推定値を計算できない。
ここで、関数ｆｕｎｃ４の全実行時間推定値は、図３８から以下の式（５．２）となる。
【０２１３】
Ｔｏｔａｌ＿ｆｕｎｃ４＝Ｃ６５×Ｔ６５＋Ｃ６６×Ｔ６６＋Ｃ６７×Ｔ６７＋Ｃ６８×Ｔ６８＋Ｃ６９×Ｔ６９・・・（５．２）
【０２１４】
従って、「関数の平均実行時間推定値」は、以下の式（５．３）で計算できる。
【０２１５】
「関数の平均実行時間推定値」＝「関数の全実行時間推定値」／「関数実行頻度」・・・（５．３）
【０２１６】
ここで「関数実行頻度」は、その関数のｓｔａｒｔを先頭命令に持つ部分プログラムの実行頻度である。
例えば、図３６における関数ｆｕｎｃ４の平均実行時間推定値は、以下の式（５．４）で計算できる。
【０２１７】
Ｔ＿ｆｕｎｃ４＝Ｔｏｔａｌ＿ｆｕｎｃ４／Ｃ６５・・・（５．４）
【０２１８】
以上の計算方法により、関数ｆｕｎｃ４の平均実行時間推定値を算出した後に、部分プログラムテーブルは、関数ｆｕｎｃ４を縮退した図３９（ａ）のようにできる。
【０２１９】
次に、縮退された関数ｆｕｎｃ４の関数呼び出しを含む部分プログラム「６３」を縮退すると、図３９（ｂ）に示す部分プログラムテーブルとなる。
【０２２０】
すると、ｍａｉｎ関数の平均実行時間推定値も同様の方法（式（５．５））で計算できる。
【０２２１】
Ｔｏｔａｌ＿ｍａｉｎ＝Ｃ６０×Ｔ６０＋Ｃ６１×Ｔ６１＋Ｃ６２×Ｔ６２＋Ｃ６３’×Ｔ６３’＋Ｃ６４×Ｔ６４  ・・・  （５．５）
【０２２２】
従って、部分プログラムテーブルは最終的に、図３９（ｃ）のように縮退できる。
なお、ｍａｉｎ関数は１回だけ呼ばれるので、Ｃ６０＝１である。
関数縮退部８２は、関数を縮退した部分プログラムテーブル（図３９）を実行トレース再生部１４ｃへ送信する。
【０２２３】
また、縮退された関数に該当する部分プログラムに関する情報（縮退情報）は、関数縮退部８２から分岐履歴情報生成部１３ｅへ送られる。分岐履歴情報生成部１３ｄは、縮退情報に含まれる部分プログラムの分岐履歴ビットを記述していない分岐履歴ビット系列を生成する（Ｓ１０３ｄ）。
以降の処理は、前記した実施形態と同様の処理であるため説明を省略する。
【０２２４】
（第５実施形態の効果）
第５実施形態によれば、再帰関数呼び出し（例えば関数内で自分自身の関数を呼び出すケースなど）が存在しないプログラムであれば、必ず全プログラムを１つの部分プログラムに縮退することができる。
【０２２５】
（第６実施形態）
まず、図４０を参照して、第６実施形態における方法を説明する。
図４０は、対象プログラムにおけるコードを繰り返し実行した際のコード実行時間を示す模式図であり、（ａ）は、第２実施形態を適用した例、（ｂ）は、第４実施形態を適用した例である。
第２実施形態から第４実施形態に記載の技術のいずれも、対象プログラム全体の実行時間を正確に見積ることができる。従って、対象プログラム全体の実行時間の正確な推定だけが目的であれば、第４実施形態による実装が最も分岐履歴ビット系列長の削減効果が大きく、必要となるメモリ量や実行時間予測に要する計算時間の面で最適であるといえる。ただし、第４実施形態による実装では、すべてのループについて、平均処理時間を採用しているため、プログラム実行の最中に複雑な条件分岐に起因する局所的な実行時間のゆらぎを再現することができない。
【０２２６】
つまり、同じコード領域「Ａ」が繰り返し実行される場合、複雑な条件分岐により、コード領域「Ａ」の実行時間は、図４０（ａ）に示すように実行される毎にゆらぎが生じることになる。第２実施形態に記載の技術では、この実行時間のゆらぎを完全に再現して、対象プログラムの実行時間推定値に反映することができる。
これに対し、第４実施形態に記載の技術では、図４０（ｂ）に示すようにすべての処理を平均化して実行時間推定値を算出するため、局所的な実行時間（局所実行時間）のゆらぎを完全に再現できない。
【０２２７】
この局所実行時間の平均化作用は、例えばプロセッサと外部装置（メモリ、デバイスドライバ、ネットワークポート、マルチプロセッサシステムにおけるプロセッサ間通信など）を含めたシステム全体のシミュレーションを目的とした場合に問題になる。つまり、システム全体のシミュレーションのためには、システムバス上のデータトラフィックやメモリアクセストラフィックの局所的なタイミングの再現が重要となり、その観点からは、第４実施形態のみを適用した場合に、局所タイミング再生精度が低いといえる。
【０２２８】
ここで、局所タイミング再生精度とは、図４０（ａ）に示すような実際にコード領域を実行した場合におけるゆらぎの度合いを示したものである。図４０（ａ）のように、各実行時間のゆらぎを忠実に推定することができれば、局所タイミング再生精度は高く、逆に図４０（ｂ）に示すように各実行時間のゆらぎが消えてしまっている場合、局所タイミング再生精度が低いとする。
【０２２９】
ここで、第１実施形態から第４実施形態に係る技術を局所タイミング再生精度の観点から整理すると、第１実施形態および第２実施形態では、平均化作用がなく（平均を算出する処理がない）、厳密に局所的なタイミングを再生することができる。
また、第３実施形態では、第３種ループの実行時間を推定する際に、平均化処理を行っているため、局所タイミング再生精度は若干低下する。
そして、第４実施形態では、第４種ループの繰り返し回数算出や、実行時間推定の際に平均化処理が行われているため、局所タイミング再生精度は第１〜第４実施形態の中で最も低くなる。
【０２３０】
第６実施形態では、シミュレーションの目的（即ち局所タイミング再生精度の要求度）の違いに柔軟に対応する実行時間推定装置１ｅを提供する。
【０２３１】
（構成）
図４１は、第６実施形態に係る実行時間推定装置の構成例を示す図である。
図４１に示すように実行時間推定装置１ｅ（１）は、第１〜第４実施形態の要素を併せ持った構造に以下の構造を追加したものである。なお、図４１において前記した実施形態と同様の構成要素については、同一の符号を付し、その詳細な構成を省略する。
実行時間推定装置１ｅ（１）は、分岐確率情報抽出部３１、プログラム実行履歴情報生成部２２、実行トレース再生部１４ｂ、第２種ループ実行時間推定算出部２３および実行時間推定算出部１５ｂを有するが、これらの機能は前記した実施形態における機能と同様であるため、同一の符号を付して説明を省略する。なお、第２種ループ情報抽出部２１ｅは、前記した実施形態における第１種・第２種ループ判別処理部２１１の機能のうち、第２種ループ判別機能と、第２種ループＩＤの発行の機能を有する。
【０２３２】
また、実行時間推定装置１ｅは、ｉｆ−ｅｌｓｅブロック実行時間偏重度算出部５１、ｉｆ−ｅｌｓｅ縮退制御部５２、ループ実行時間偏重度算出部５３および第４種ループ縮退制御部５４をさらに有する。
ｉｆ−ｅｌｓｅブロック実行時間偏重度算出部５１は、ｉｆ−ｅｌｓｅブロック実行時間偏重度を算出する機能を有する。ｉｆ−ｅｌｓｅブロック実行時間偏重度については後記して説明する。
ｉｆ−ｅｌｓｅ縮退制御部５２は、算出したｉｆ−ｅｌｓｅブロック実行時間偏重度と、入力部１５６（図２）を介して入力されたｉｆ−ｅｌｓｅ偏重度閾値とを比較し、ｉｆ−ｅｌｓｅ縮退部３３１ｅが行うｉｆ−ｅｌｓｅ縮退処理を禁止するか否かの情報であるｉｆ−ｅｌｓｅ縮退禁止フラグを出力する。
ループ実行時間偏重度算出部５３は、ループ実行時間偏重度を算出する機能を有する。ループ実行時間偏重度については後記する。
第４種ループ縮退制御部５４は、ループ実行時間偏重度と、入力部１５６（図２）を介して入力されたループ偏重度閾値とを比較し、第４種ループ縮退部４１１ｅが行う第４種ループ縮退処理を禁止するか否かの情報である第４種ループ縮退禁止フラグを出力する。
【０２３３】
また、多重ループ縮退部４１ｅの各部３３１ｅ，３３２ｅ，４１１ｅは、前記した実施形態に記述した機能に加えて、ｉｆ−ｅｌｓｅ縮退制御部５２や、第４種ループ縮退制御部５４から送られたｉｆ−ｅｌｓｅ縮退禁止フラグや、第４種ループ縮退禁止フラグを基に、ｉｆ−ｅｌｓｅ縮退処理や、多重ループ縮退処理の実行を制御する機能を有する。
【０２３４】
なお、図４１に示す各部１４ｂ，１５ｂ，２２，２３，３１，４１ｅ，５１，２，５３，５４，２１１ｅ，３３１ｅ，３３２ｅ，４１１ｅは、図２の記憶装置１７０などに記憶されている実行時間推定プログラムが、ＲＡＭ１５３に展開され、ＣＰＵ１５１が実行することによって具現化する。
【０２３５】
次に、図４１を参照しつつ、図４２に沿って第６実施形態に係るプログラム実行時間推定方法を説明する。
図４２は、第６実施形態に係るプログラム実行時間推定方法の流れを示すフローチャートである。なお、図４２において、前記した実施形態と同様の処理については、同一のステップ番号を付して説明を省略する。
まず、ｉｆ−ｅｌｓｅブロック実行時間偏重度算出部５１が、すべてのｉｆ−ｅｌｓｅ分岐ブロックについて、ｉｆ−ｅｌｓｅブロック実行時間偏重度算出処理を行う（Ｓ５０１）。
第３実施形態では、ｉｆ−ｅｌｓｅ分岐命令の真偽それぞれの実行時間の偏りが大きく、かつ、実行頻度が高い場合、このようなｉｆ−ｅｌｓｅブロックを縮退した際に、実行時間の平均化作用により局所タイミング再生精度の低下を招く。そこで、条件の真偽の実行時間の絶対差とｉｆ−ｅｌｓｅブロック実行頻度の積をｉｆ−ｅｌｓｅブロックのｉｆ−ｅｌｓｅブロック実行時間偏重度と定義し、このｉｆ−ｅｌｓｅブロック実行時間偏重度をｉｆ−ｅｌｓｅブロック実行時間偏重度算出部５１が算出する。例えば、条件「Ｃ」が「真」の場合の実行時間「Ｔｔ」と「偽」の実行時間「Ｔｆ」と、条件「Ｃ」の実行頻度「Ｍｃ」を用いて、ｉｆ−ｅｌｓｅブロック実行時間偏重度算出部５１は、式（６．１）および式（６．２）の計算を行い、条件「Ｃ」の実行時間偏重度を算出する。実行時間偏重度が大きいほど、局所タイミング再生精度は、低くなる。
【０２３６】
ｇ（Ｃ）＝｜Ｔｔ−Ｔｆ｜×Ｍｃ・・・（６．１）
【０２３７】
ステップＳ５０１の後、ループ実行時間偏重度算出部５３が、すべてのループについてループ実行時間偏重度を算出するループ実行時間偏重度算出処理を行う（Ｓ５０２）。
第４実施形態に記載の技術では、縮退するループの繰り返し回数の偏りが大きく、かつループの実行頻度が高くループの平均実行時間が長い場合、このループを縮退した際に局所タイミング再生精度の低下を招く。そこで、ループの繰り返し回数の偏重度として、繰り返し回数分布の分散とループ実行頻度の積をループの「ループ実行時間偏重度」と定義する。例えば、ループＬがＮ回実行され、それぞれの繰り返し回数を（Ｌ１、Ｌ２、・・・Ｌｎ）とし、平均実行時間をＴｍｅａｎとしたとき、ループ実行時間偏重度算出部５３は、ループＬにおけるループ実行時間偏重度を式（６．２）より算出する。ループ実行時間偏重度が大きいほど、局所タイミング再生精度は、低くなる。
【０２３８】
【数１】
0005403760.tif 000002
【０２３９】
式（６．２）において、σ２はループＬの繰り返し回数の分散、ＬｍｅａｎはループＬ
の繰り返し回数の平均値である。
【０２４０】
ステップＳ５０２の後、分岐確率情報抽出部３１が、分岐確率情報抽出処理を行う（Ｓ３０１）。ステップＳ３０１の処理は、前記した実施形態と同様の処理であるため説明を省略する。
【０２４１】
次に、ｉｆ−ｅｌｓｅ縮退制御部５２が、局所タイミング再生精度の要求度に応じて予め入力され、設定されているｉｆ−ｅｌｓｅ偏重度閾値と、ステップＳ５０１で算出したｉｆ−ｅｌｓｅブロック偏重度とを、すべてのｉｆ−ｅｌｓｅブロック毎に比較する。そして、ｉｆ−ｅｌｓｅブロック偏重度がｉｆ−ｅｌｓｅ偏重度閾値よりも大きい場合に、ｉｆ−ｅｌｓｅ縮退制御部５２は、該当するｉｆ−ｅｌｓｅ縮退処理を禁止するフラグ（ｉｆ−ｅｌｓｅ縮退禁止フラグ）を部分プログラムテーブルに設定するｉｆ−ｅｌｓｅ縮退禁止フラグ設定処理を行う（Ｓ５０３）。ステップＳ５０３において、ｉｆ−ｅｌｓｅブロック偏重度がｉｆ−ｅｌｓｅ偏重度閾値よりも大きい場合、部分プログラムテーブルの該当する縮退禁止フラグのフィールドに「１」を登録する。また、ステップＳ５０３において、ｉｆ−ｅｌｓｅブロック偏重度がｉｆ−ｅｌｓｅ偏重度閾値以下である場合、部分プログラムテーブルの該当する縮退禁止フラグのフィールドに「０」を登録する。
【０２４２】
ステップＳ５０３の後、第４種ループ縮退制御部５４が、局所タイミング再生精度の要求度に応じて予め入力され、設定されているループ偏重度閾値と、ステップＳ５０２で算出されたループ実行時間偏重度とをすべてのループ毎に比較する。そして、ループ実行時間偏重度がループ偏重度閾値よりも大きい場合に、第４種ループ縮退制御部５４は、該当する第４種ループ縮退処理を禁止するフラグ（第４種縮退禁止フラグ）を部分プログラムテーブルに設定する第４種ループ縮退禁止フラグ設定処理を行う（Ｓ５０４）。なお、ステップＳ５０４では、第４種ループ縮退制御部５４は、前記した第１種・第２種ループ判別処理部２１１（図９）と同様の機能を有しており、この機能によって、第２種ループと判別された部分プログラムに対しては第４種縮退禁止フラグを設定しない。
ステップＳ５０４において、ループ実行時間偏重度がループ偏重度閾値よりも大きい場合、部分プログラムテーブルの該当する縮退禁止フラグのフィールドに「１」を登録する。また、ステップＳ５０４において、ループ実行時間偏重度がループ偏重度閾値以下である場合、部分プログラムテーブルの該当する縮退禁止フラグのフィールドに「０」を登録する。
【０２４３】
図４３は、ステップＳ５０３およびステップＳ５０４における処理の結果、生成される部分プログラムテーブルの例を示す図である。
図４３に示す部分プログラムテーブルは、図５に示す部分プログラムテーブルの構成に加え、縮退禁止フラグのフィールドが設けられている。なお、第４種ループ縮退制御部５４は、第４種ループ縮退禁止フラグ設定処理（図４２のステップＳ５０４）の終了後に、空欄となっている縮退禁止フラグのフィールドにはすべて「０」を登録する。
【０２４４】
次に、多重ループ縮退部４１ｅが、多重ループ縮退処理を実行する（Ｓ５０５）。ステップＳ５０５の処理については、図４４を参照して後記する。
【０２４５】
次に、図４１を参照しつつ、図４４に沿ってステップＳ５０５の処理の詳細を説明する。
図４４は、第６実施形態に係る多重ループ縮退処理の流れを示すフローチャートである。なお、図４４において、前記した実施形態と同様の処理については、同一のステップ番号を付して説明を省略する。なお、多重ループ縮退部４１ｅは、前記した第１種・第２種ループ判別処理部２１１（図９）と同様の機能を有しており、この機能によって、第２種ループと判別されたループに関して、多重ループ縮退部４１ｅは、以下のステップＳ５０５１〜Ｓ４０１６の処理を行わない。
ステップＳ３０２１の前に、ｉｆ−ｅｌｓｅ縮退部３３１ｅは、部分プログラムテーブルを参照して、検索したｉｆ−ｅｌｓｅブロックに相当する部分プログラムの縮退禁止フラグが「１」であるか否かを判定する（Ｓ５０５１）。
ステップＳ５０５１の判定の結果、「１」である場合（Ｓ５０５１→Ｙｅｓ）、ｉｆ−ｅｌｓｅ縮退部３３１ｅおよび隣接縮退部３３２ｅは、ステップＳ３０２２およびステップＳ３０２３を実行せず（つまり、ｉｆ−ｅｌｓｅ縮退処理を禁止して）、ステップＳ４０１２へ処理を進める。
ステップＳ５０５１の判定の結果、「１」でない場合（Ｓ５０５１→Ｎｏ）、ｉｆ−ｅｌｓｅ縮退部３３１ｅおよび隣接縮退部３３２ｅは、ステップＳ３０２１およびステップＳ３０２２の処理を実行する。
【０２４６】
そして、ステップＳ４０１３の前に、第４種ループ縮退部４１１ｅは、部分プログラムテーブルを参照して、検索した第４種ループに相当する部分プログラムの縮退禁止フラグが「１」であるか否かを判定する（Ｓ５０５２）。
ステップＳ５０５２の判定の結果、「１」である場合（Ｓ５０５２→Ｙｅｓ）、第４種ループ縮退部４１１ｅおよび隣接縮退部３３２ｅは、ステップＳ４０１３およびステップＳ４０１４を実行せず（つまり、第４種ループ縮退処理を禁止して）、ステップＳ４０１５へ処理を進める。
ステップＳ５０５２の判定の結果、「１」でない場合（Ｓ５０５２→Ｎｏ）、第４種ループ縮退部４１１ｅおよび隣接縮退部３３２ｅは、ステップＳ４０１３およびステップＳ４０１４の処理を実行する。
【０２４７】
ステップＳ４０１ａの後、第２種ループ情報抽出部２１ｅが第２種ループ情報抽出処理を行う（Ｓ２０１ａ）。ステップＳ２０１ａは、図１１のステップＳ２０１１と同様の手順で、第２種ループの判別を行い、ステップＳ２０１２と同様の手順で第２種ループＩＤを部分プログラムテーブルに登録する処理であるため、詳細な説明を省略する。
【０２４８】
なお、ステップＳ２０１ａにおいて、第１種ループに関する情報抽出の処理を行わない理由は、以下の通りである。第１種ループは、繰り返し回数が全対象プログラムに渡って不変（定数回）であるため、ループ実行時間偏重度は必ず「０」となる。つまり、平均繰り返し回数と実際の「定数回」繰り返し回数が一致することとなる。従って、第１種ループの縮退処理は、第４種ループ縮退処理においてすべて実行されるため、ステップＳ２０１ａの段階で未処理の第１種ループは原理的には存在しないためである。
以下の処理は、それぞれ前記した実施形態で説明した処理と同じであるため説明を省略する。
【０２４９】
（第６実施形態の効果）
第６実施形態によれば、第２〜第４実施形態を合わせた実行時間推定装置１ｅにおいて、第３実施形態および第４実施形態における過剰な局所タイミング再生精度の消去を制御することができる。
【０２５０】
（実験例）
次に、図４５から図４９を参照して、第１実施形態から第４実施形態、および第６実施形態において提供されている実行時間推定装置１における実験例を示す。
図４５から図４９の実験（シミュレーション）において用いたコンピュータは、クロック数３．２ＧＨｚのＣＰＵ、および１ＧＢの主メモリを用いる仕様とした。
そして、実験に供したテストプログラム（対象プログラム）は、５０００００未満の素数を列挙する素数計算プログラム（「Ｐｒｉｍｅ５０００００」）、英文ファイルの英文字出現頻度計算プログラム（「Ａｌｐｈａｂｅｔ」）、要素数１０個の順列組合せ列挙プログラム（「Ｐｅｒｍｕｔａｔｉｏｎ」）および画像サイズ８００×６００画素のＪＰＥＧエンコーダプログラム（「ＪＰＥＧ」）とした。
【０２５１】
図４５は、比較例として命令セットシミュレータを用いた実験結果を示す表である。
用いた命令セットシミュレータは、３２ビットＲＩＳＣ（Reduced Instruction Set Computer）プロセッサ上におけるプログラム実行処理時間をサイクル精度で推定する命令セットシミュレータを使用した（ただし、キャッシュシミュレーションは含まない）。
図４５において、前記４つの対象プログラムに対し、対象プログラムサイズは、対象プログラムにおける命令数を表し、プログラム実行時間は、対象プログラムを実行した際の総クロックサイクル数を表している。命令セットシミュレータ実行時間は、命令セットシミュレータにおいて各対象プログラムの実行時間を推定するときに要する時間であり、単位は「秒」である。命令セットシミュレータ処理速度は、各対象プログラムの実行時間を推定したときの処理速度であり、単位は「クロックサイクル／秒」である。
【０２５２】
図４６は、第１実施形態に係る実験結果を示す例である。
なお、図４６および図４７において、部分プログラムテーブルサイズは、部分プログラムテーブルの行数を示す。分岐履歴ビット系列長は、分岐履歴ビット系列の長さ（ビット数）である。部分プログラム平均実行時間は、各対象プログラムにおける部分プログラムの実行時間（分岐命令から分岐命令までの平均実行時間）であり、対象プログラム実行時間/（分岐履歴ビット系列長＋１)で算出される。実行時間推定算出時間は、対象プログラムの実行時間の算出にかかった時間であり、単位は「秒」である。対命令セットシミュレータ速度向上比は、（命令セットシミュレータにおける実行時間/実行時間推定装置１における実行時間）で算出される値である。
【０２５３】
図４５および図４６を参照し、特に図４６の対命令セットシミュレータ速度向上比を参照すると、第１実施形態に係る実行時間推定装置１ａ（図１）の実行時間は、命令セットシミュレータの実行時間に比べて、１６．１６倍から４５．７５倍の高速な実行時間見積もりが可能であることがわかる。ちなみに、得られた実行時間推定値は、いずれの対象プログラムの場合にも、命令セットシミュレータの結果と完全に一致する。
【０２５４】
図４７は、第４実施形態に係る実験結果を示す表である。なお、第２実施形態および第３実施形態に係る実験結果は、図４８において説明するため省略する。
図４７において、「Ｐｒｉｍｅ５０００００」は、縮退できないループが多重ループの内側に存在したため、第１実施形態（図４６）と比較して分岐履歴ビット系列長がほとんど削減されていない。「Ａｌｐｈａｂｅｔ」は、最外殻ループ以外の内部ループ以外はほとんど縮退されたため、第１実施形態（図４６）と比較して分岐履歴ビット系列長が激減している。「Ｐｅｒｍｕｔａｔｉｏｎ」に至っては、すべてのループおよびｉｆ−ｅｌｓｅブロックが縮退したため、分岐履歴ビット系列長が０になった。「ＪＰＥＧ」についても、ほとんどのループおよびｉｆ−ｅｌｓｅブロックが縮退したため、第１実施形態（図４６）と比較して分岐履歴ビット系列長は激減している。
また、図４７において「Ｐｅｒｍｕｔａｔｉｏｎ」および「ＪＰＥＧ」における対命令セットシミュレータ速度向上比は、「‐」となっているが、これは時間計測精度（０．００１秒）よりも少ない時間で見積もり計算を終了したことを意味している。
いずれの場合も、対象プログラムの実行時間推定値は、命令セットシミュレータの結果と完全に一致する。
【０２５５】
図４８は、第１〜第４，第６実施形態に係る実験結果をまとめた表である。
対象プログラムとして「ＪＰＥＧ」を用いたときの、部分プログラムテーブルサイズ、分岐履歴ビット系列長（ビット数）、プログラム実行時間推定計算時間（秒）、対命令セットシミュレータ向上比を各実施形態毎に記述してある。なお、第６実施形態におけるｉｆ−ｅｌｓｅ偏重度閾値（図４１）は、「４００．０００」であり、ループ偏重度閾値（図４１）は、「１０．０００」である。
図４８における横軸の各項目は、図４６および図４７の縦軸と同様であるため説明を省略する。対命令セットシミュレータ比の項目から、命令セットシミュレータに対し第３実施形態が最も良好な結果を示していることがわかる。
第１〜第４，第６実施形態のいずれも対象プログラムの実行時間推定値は、命令セットシミュレータの結果と完全に一致するが、前記したように第１〜第４，第６実施形態における「局所タイミング再生精度」がそれぞれ異なっている（図示せず）。
【０２５６】
図４９は、第１〜第４，第６実施形態における実験結果を示すグラフである。縦軸は、クロックサイクル数を示し、横軸は時間（秒）を示す。
図４９は、「局所タイミング再生精度」を評価するために、「ＪＰＥＧ」のプログラム内部で繰返し呼び出される関数を一つ選び、その関数が１００回呼び出される毎の時刻を記録し、記録される時刻の間隔をグラフ化したものである。
第１実施形態（「Ｎｏ＿Ｍｅｒｇｅ」）と、第２実施形態（「Ｌｏｏｐ＿Ｍｅｒｇｅ」）のグラフは、局所タイミングについても予測精度を犠牲にすることはないので、図示しない命令セットシミュレータで得られる結果と完全に一致する。
また、第３実施形態（「Ｂｒａｎｃｈ＿Ｍｅｒｇｅ」）では、ｉｆ−ｅｌｓｅブロックの縮退処理によってその部分の局所タイミング再生精度が失われるため「局所タイミング再生精度」に誤差は生じるものの、局所タイミングのゆらぎの傾向は概ね再生できているといえる。
さらに、第４実施形態（「Ｆｕｌｌ＿Ｍｅｒｇｅ」）では、平均化作用のために、局所タイミングのゆらぎは完全に消えている。
そして、第６実施形態（「Ｐａｒａｍ＿Ｍｅｒｇｅ」）では、局所タイミング再生精度の誤差はほとんど０であり（つまり、第１実施形態「Ｎｏ＿Ｍｅｒｇｅ」と一致している）、なおかつ「Ｌｏｏｐ＿Ｍｅｒｇｅ」（第２実施形態）に比べ少ない分岐履歴ビット系列長を実現できる。
【０２５７】
つまり、第６実施形態では、図４９に示すように「ｉｆ−ｅｌｓｅ偏重度閾値（図４１）」と「ループ偏重度閾値（図４１）」を調整することにより、局所タイミング再生精度の制御と、分岐履歴ビット系列長の長さの制御との間のトレードオフポイントを自由に設定することができる。
【０２５８】
（第７実施形態：マルチプロセッサ）
第１〜第６実施形態における実行時間推定装置１ａ〜１ｅ，１ｇ（図１、図９、図１８、図２７、図３５および図４１）に用いられるプロセッサは、シングルプロセッサであることを前提としていたが、これをマルチプロセッサとすることも可能である。以下、第７実施形態として、第１実施形態に係る実行時間推定装置１ａ（図１）をマルチプロセッサとした例を説明する。
【０２５９】
ここで、第７実施形態に用いられるマルチプロセッサについて説明する。
第７実施形態において、マルチプロセッサプログラムは、マルチプロセッサシステムを構成する各プロセッサ上で、個々に実行されるプログラム（対象プログラム）の集合（または「並列処理プログラム」）を指すこととする。このマルチプロセッサプログラムの中には、プロセッサ（プロセス）間通信処理や同期処理が明示的な命令として埋め込まれているものとする。
【０２６０】
マルチプロセッサプログラムの作成方法としては、逐次プログラムの自動並列コンパイラを用いた手法（岡本、合田、宮沢、本多、笠原、「OSCAR マルチグレインコンパイラにおける階層型マクロデータフロー処理」、情報処理学会論文誌、Vol. 35, No. 4, pp.513-521 (1994),Eigenmann, Hoeflinger, Padua, “On the Automatic Parallelization of the Perfect Benchmarks”, IEEE Trans. on Parallel and Distributed Systems, Vol. 9, No.1, pp.5-21 (1998)およびHall, Anderson, Amarasinghe, Murphy, Liao, Bugnion, Lam, “Maximizing Multiprocessor Performance with the SUIF Compiler”, IEEE Computer, Vol. 29, No.12, pp.84-89 (1996)参照）や,逐次処理言語を拡張した並列処理言語を用いた手法（岩下英俊,「HPF からみたVPP Fortran」,情報処理,38 巻2 号,pp.114-121,1997 年2 月,“HPF 推進協議会 (HPFPC)”,[online],[平成１７年８月１０日検索],インターネット＜URL : http://www.hpfpc.org/＞,Gehani, et al, “Concurrent C”, Software, Practice and Experience, Vol.16, No. 9, pp.821-844, 1986,“Message Passing Interface Forum”,[online],[平成１７年８月１０日検索],インターネット＜URL : http://www.mpi-forum.org/index.html＞, “PVM”,[online],[ 平成１７年８月１０ 日検索],インターネット＜ URL :http://www.csm.ornl.gov/pvm/pvm＿home.html＞参照）、並びに、逐次プログラム上に「スレッド記述」だけを追加したプログラムから通信同期命令を自動的に生成する並列処理コンパイラを用いた手法がある（特開２００７−１９３４２３号公報、特開２００７−１９３４３０号公報参照）。
【０２６１】
第７実施形態におけるマルチプロセッサ構成は、すべて同一種類のプロセッサである対称型マルチプロセッサシステムや、異種プロセッサが混合している非対称型マルチプロセッサシステムが考えられる。いずれの場合でも、第７実施形態では、部分プログラム実行時間推定算出部１２ｆ（図５２を参照して後記）において、それぞれのプログラム実行を担当する対象プロセッサモデルを、対象マルチプロセッサシステムを構成する各プロセッサに切り替えることで容易に対処できる。
【０２６２】
以下、図５０〜図５３を参照して、第７実施形態に係る実行時間推定装置１ｆの構成を説明する。
図５０は、第７実施形態に係る実行時間推定装置の構成例を示す図である。
実行時間推定装置１ｆ（１）は、図５２で後記する前処理部６１と、図５３で後記する後処理部６２とを有してなる。前処理部６１は、マルチプロセッサによる並列処理を行うことによって複数の対象プログラムから、部分プログラムテーブル、分岐履歴ビット系列および部分プログラム実行時間を対象プログラムごとに生成・算出し、後処理部６２に入力する機能を有する。後処理部６２は、マルチプロセッサによる並列処理を行うことによって前処理部６１が生成・算出した部分プログラムテーブルや、分岐履歴ビット系列や、部分プログラム実行時間を基に、各対象プログラムの実行時間推定値を算出する機能を有する。また、実行時間推定を行う対象プログラムがプロセスに相当し、複数のプロセスが集合した１つの親プログラムを形作っている場合、後処理部６２が各プロセス間の同期やデータ通信を忠実に再現しつつ、高精度の実行時間推定値を算出する。
【０２６３】
図５１は、第７実施形態に係る実行時間推定装置のハードウェア構成を示す図である。
図５１が、図２と異なる点は、ＣＰＵ１５１ｆが複数備わっているマルチプロセッサの構成となっている点である。これ以外の要素は、図２と同様であるため同一の符号を付して説明を省略する。
【０２６４】
図５２は、第７実施形態に係る前処理部の詳細な構成例を示す図である。
前処理部６１は、プログラム分割部１１ｆ、部分プログラム実行時間推定算出部１２ｆおよび分岐履歴情報生成部１３ｆを有する。
プログラム分割部１１ｆは、複数の対象プログラムから、マルチプロセッサによる並列処理を用いて対象プログラムごとの部分プログラムテーブルを生成する機能を有する。
第７実施形態に係るプログラム分割部１１ｆは、第１実施形態のプログラム分割部１１（図１）の機能（ここでは、各プロセッサが実行担当するプログラム毎に処理する）に、通信同期命令を扱う機能を追加することとする。通信同期命令は、プロセッサ実行状態を変化させる要因となり、マルチプロセッサシステムの実行時間を高精度に見積るためには、通信同期命令の正確な実行時刻の特定が必要となるためである。つまり、複数の対象プログラムがプロセスとして互いに同期しあいながら、１つのプログラムを実行する場合、個々の対象プログラム中に通信同期命令が存在させている。
【０２６５】
ここで、特開２００７−１９３４３０号公報の手法に基づいて生成されたマルチプロセッサプログラムの例では、以下の４種類の通信同期命令が挙げられる。
すなわち、データ送信命令、データ受信同期命令、スレッド起動命令およびスレッド終了命令である。このうち、スレッド終了命令とは、スレッド処理終了時の受信バッファ更新処理を起動し、次のスレッド処理実行を開始するための命令である。
これ以降の説明では、「通信同期命令」の具体例としてこの４種類の命令を扱うこととする。
【０２６６】
すなわち、各プロセッサが実行する対象プログラムをそれぞれ部分プログラムに分割する際に、第１実施形態におけるプログラム分割部１１（図１）では、条件分岐命令と関数呼出し命令をプログラム分割の境界点としたが、第７実施形態におけるプログラム分割部１１ｆでは、通信同期命令も境界点と見なして部分プログラム分割を行う。その結果、通信同期命令は必ず部分プログラムの先頭命令になる。このように、先頭命令が通信同期命令となる部分プログラムを、以降「通信同期部分プログラム」と記載する。
【０２６７】
部分プログラム実行時間推定算出部１２ｆは、プログラム分割部１１ｆが生成した部分プログラムテーブルと、予め入力されている個別プロセッサモデルとを基に、マルチプロセッサによる並列処理を用いて対象プログラムごとの部分プログラム実行時間を算出する。なお、算出した部分プログラム実行時間は、部分プログラムテーブルにおける「実行時間推定値」に書き込まれる。なお、非対称マルチプロセッサシステムの場合は、プロセッサ毎に複数種類の対象プログラムが存在してもよい。
ここで、個別プロセッサモデルとは、それぞれのプログラム実行を担当するプロセッサのモデルを指す。前記したように、マルチプロセッサシステムを構成するプロセッサは，すべて同一種類の場合（対称型）や複数種類の場合（非対称型）といったモデルがあるが、第７実施形態ではどちらを使用してもよい。個別プロセッサモデルは、各個別プログラムを処理するプロセッサのモデルに関する情報である。
【０２６８】
分岐履歴情報生成部１３ｆは、複数の対象プログラムから、マルチプロセッサによる並列処理を用いて対象プログラムごとの分岐履歴ビット系列を生成する機能を有する。
第７実施形態において、分岐履歴情報生成部１３ｆは、複数の対象プログラムを「実行可能な計算機環境」（例えばマルチプロセッサシミュレータ）で実行し、各プロセッサ別のプログラム実行中のすべての条件分岐命令の実行結果（「真」または「偽」：１ビット情報）を、各プロセッサ上において実行された順序で結合して生成される「分岐履歴ビット系列」をＲＡＭ１５３などの記憶装置１７０（図５１）に保存する。すなわち、Ｍ個の対象プログラムから、Ｍ個の独立した「分岐履歴ビット系列」が生成される。
【０２６９】
ここで、第７実施形態における部分プログラムテーブルについて説明する。
第７実施形態における部分プログラムテーブルは、図５における部分プログラムテーブルに格納された情報に加え、通信同期部分プログラムに関する情報（データ送信命令・スレッド起動命令、受信プロセッサＩＤ、受信バッファＩＤ、データ受信同期命令および受信バッファＩＤ）もまた格納される。なお、通信同期部分プログラムに関する情報は、先頭通信同期命令を実行した時のプロセッサ実行状態更新や通信同期リソース状態更新のために必要な情報である。
【０２７０】
前処理部６１において生成された、部分プログラム実行時間推定値追加済みの部分プログラムテーブル、分岐履歴ビット系列および部分プログラム実行時間は、後処理部６２へと入力される。
【０２７１】
図５３は、第７実施形態に係る後処理部の詳細な構成例を示す図である。
後処理部６２は、キュー指示部６３と、トレースシミュレーション制御部６４とを有してなる。
キュー指示部６３は、「実行可能状態」にあるプロセッサを、プロセッサクロック値７０の昇順並びを常に維持しながら格納する「プロセッサ待ち行列」であるプロセッサキュー（実際に格納するのはプロセッサＩＤ）の管理を行う機能を有する。また、キュー指示部６３は、この「プロセッサキュー」の先頭プロセッサを一時的にキューから削除してから、次のプロセッサキューが示すプロセッサに対してトレースシミュレーションを実行させる機能も有する（以降、この実行中のプロセッサを「現プロセッサ」と呼ぶ）。
【０２７２】
トレースシミュレーション制御部６４は、実行トレース再生部１４ｆと、実行時間推定算出部１５ｆと、通信同期命令シミュレーション実行部６５とを有してなる。
【０２７３】
トレースシミュレーション制御部６４は、実行トレース再生部１４ｆと、実行時間推定算出部１５ｆとで各プロセッサにおいて部分プログラム実行系列を生成したり、実行時間推定算出処理を行ったりし、この実行時間推定値をプロセッサクロック値７０とする更新を行う機能を有する。
すなわち、トレースシミュレーション制御部６４は、プロセッサの動作を擬似的にシミュレーションする機能を有している
【０２７４】
記憶部６６（図５１のリムーバブル記録媒体１５９に相当）には、分岐履歴ビット系列読み出し位置指定情報６７と、通信同期リソース状態情報６８と、プロセッサ実行状態情報６９（実行可能状態および実行待機状態）と、プロセッサクロック値７０とを有している。
【０２７５】
実行トレース再生部１４ｆは、前記した実施形態と同様に分岐履歴ビット系列読み出し位置指定情報６７を使用して、前処理部６１から入力された対象プログラムごとの部分プログラムテーブルと、分岐履歴ビット系列とを基に、部分プログラム実行系列を生成し、この部分プログラム実行系列に従って逐次的に部分プログラム実行時間推定値を実行時間推定算出部１５ｆへ送る機能を有する。
通信同期命令シミュレーション実行部６５は、通信同期リソース状態情報６８の更新やプロセッサ実行状態情報６９の更新の因果関係が正確に再現されることを保証するために、すべての通信同期命令のシミュレーションを時間的な順序に従って実行させる機能を有する。
【０２７６】
なお、図５０、図５２および図５３に示す各部１１ｆ〜１５ｆ，６１〜７０は、図５１に示す記憶装置１７０などに記憶されている実行時間推定プログラムが、ＲＡＭ１５３に展開され、ＣＰＵ１５１ｆが実行することによって具現化する。
【０２７７】
次に、図５３を参照しつつ、図５４に沿って第７実施形態に係る後処理部６２における処理の流れを説明する。
図５４は、第７実施形態に係る後処理部における処理の流れを示すフローチャートである。なお、前処理部６１における処理は、第１実施形態の図２のステップＳ１０１〜Ｓ１０３の処理を個々の対象プログラムに対して並列に行う処理であるため、説明を省略する。そして、実行トレース再生部１４ｆおよび実行時間推定算出部１５ｆにおける処理は、第１実施形態の図２のステップＳ１０４，Ｓ１０５の処理をプロセッサごとに並列に行う処理であるため、図５０では主として第７実施形態に特有の処理を中心に説明を行うこととする。
【０２７８】
まず、トレースシミュレーション制御部６４が、実行可能先頭プロセッサの取得処理を行う（Ｓ６０１）。この処理は、トレースシミュレーション制御部６４が、プロセッサキューの先頭プロセッサＩＤをキュー指示部６３から取得し、「現プロセッサ」に設定する処理である。さらに、キュー指示部６３は、現プロセッサをキューから削除する。つまり、キュー指示部６３は、現在シミュレーションの対象となっているプロセッサを別のプロセッサに換える。
【０２７９】
そして、トレースシミュレーション制御部６４は、プロセッサシミュレーション状態設定処理を行う（Ｓ６０２）。ここで、トレースシミュレーション制御部６４は、トレースシミュレーション制御部６４自身の内部状態の情報を、現プロセッサのプロセッサシミュレーション状態の情報に設定する。ここで、内部状態の情報とは、分岐履歴ビット系列の読み出し位置（分岐履歴ビット系列読み出し位置指定情報６７）や、プロセッサクロック値７０や、プロセッサ実行状態情報６９や、通信同期リソース状態情報６８などを指す。
【０２８０】
分岐履歴ビット系列読み出し位置指定情報６７は、プロセッサ毎の分岐履歴ビット系列の読み出し位置（つまり、次に読み出すビットの位置）に関する情報が格納されている。
ここで、プロセッサ実行状態情報６９とは、以下のように定義される。マルチプロセッサシステムを構成する各プロセッサは、通常の「実行可能状態」と、プロセッサ間通信処理や同期処理等の実行中に一時的に陥る「実行待機状態」のいずれかの状態をとる。この状態に関する情報が、プロセッサ実行状態情報６９であり、マルチプロセッサシステムにおいては、各プロセッサが常に「実行可能状態」である区間の実行時間見積り計算だけでなく、プロセッサ間の相互作用によって生じる「実行待機状態」を正確に再現しながら実行時間見積り計算を進める必要がある。
また、通信同期リソース状態情報６８とは、プロセッサ実行状態遷移を制御するための、各プロセッサ内で管理されている内部状態をさす。前記４種の通信同期命令の例では、受信バッファ状態（受信バッファに溜まっているデータ個数）が、この「通信同期リソース状態」に当る。
プロセッサクロック値７０とは、プロセッサが対象プログラムを実行するときに要する時間であり、具体的には算出された対象プログラムの実行時間推定値が格納される。
【０２８１】
ステップＳ６０２の後、実行トレース再生部１４ｆが、分岐履歴実行系列と部分プログラムテーブルとを基に部分プログラム実行系列を生成し（Ｓ６０３）、この部分プログラム実行系列に従って逐次的に部分プログラム実行時間推定値を実行時間推定算出部１５ｆへ送る。なお、実際には、実行トレース再生部１４ｆは、前記した実施形態と同様に部分プログラム実行系列を生成しながら、部分プログラムテーブルから該当する部分プログラム実行時間推定値を取得して、取得した順に部分プログラム実行時間推定値を実行時間推定算出部へ送る。ステップＳ６０３の処理は、第１実施形態における部分プログラム実行系列の生成処理を各対象プログラム毎に行うものである。複数の対象プログラムにおける部分プログラム実行系列を生成するため、実行トレース再生部１４ｆは、該当するプロセッサにおける分岐履歴ビット系列読み出し位置指定情報６７を取得し、この分岐履歴ビット系列読み出し位置指定情報６７が示すビットを分岐履歴ビット系列から読み出す。そして、実行トレース再生部１４ｆは、読み出したビットに従って部分プログラムテーブルから部分プログラム実行時間推定値を読み出し、部分プログラム実行系列に追加すると同時に、部分プログラム実行時間推定値を実行時間推定算出部１５ｆへ送る。部分プログラム実行系列への追加（部分プログラム実行時間推定値の送信）が終わると、実行トレース再生部１４ｆは、該当するプロセッサの分岐履歴ビット系列読み出し位置指定情報６７を１ビット後方へずらす。
【０２８２】
そして、通信同期命令シミュレーション実行部６５は、実行トレース再生部１４ｆからステップＳ６０３で部分プログラム実行系列に追加された部分プログラムＩＤを取得する。そして、通信同期命令シミュレーション実行部６５は、取得した部分プログラムＩＤが通信同期部分プログラムに関するＩＤであるか否かを判定することにより、現在処理している部分プログラムが通信同期部分プログラムであるか否かを判定する（Ｓ６０４）。前記したように部分プログラムテーブルには、図５に示すような情報に加えて、通信同期部分プログラムのＩＤ（データ送信命令・スレッド起動命令、受信プロセッサＩＤ、受信バッファＩＤ、データ受信同期命令および受信バッファＩＤ）も格納されているため、これらのＩＤを基に、通信同期命令シミュレーション実行部６５は判定を行う。
ステップＳ６０４の結果、通信同期部分プログラムではない場合（Ｓ６０４→Ｎｏ）、トレースシミュレーション制御部６４は、ステップＳ６１２へ処理を進める。
ステップＳ６０４の結果、通信同期部分プログラムである場合（Ｓ６０４→Ｙｅｓ）、通信同期命令シミュレーション実行部６５は、通信同期命令の時間順序性が違反であるか否かを判定する（Ｓ６０５）。この判定は、現プロセッサのプロセッサクロック値７０がシミュレーション同期時刻以下である場合、通信同期命令シミュレーション実行部６５は「時間順序性違反なし（ステップＳ６０５→Ｎｏ）」と判定し、それ以外の場合は、「時間順序性違反あり（ステップＳ６０５→Ｙｅｓ）」と通信同期命令シミュレーション実行部６５が判定することによって行われる。なお、「時間順序性違反あり」の場合、この通信同期命令実行時刻よりも前の時刻に実行可能な通信同期命令が存在する可能性がある。
ここで、シミュレーション同期時刻とは、プロセッサキューの先頭プロセッサ（現プロセッサ以外）のプロセッサクロック値７０をさす。「プロセッサキュー」が空の場合（すなわち、現プロセッサ以外に実行可能プロセッサが存在しない場合）は、「シミュレーション同期時刻」は無限大の値となる。
【０２８３】
ステップＳ６０５の結果、時間順序性違反ありと判定された場合（Ｓ６０５→Ｙｅｓ）、トレースシミュレーション制御部６４は、現プロセッサ状態を「プロセッサキュー」に再投入し（Ｓ６０６）、ステップＳ６０１の処理へ戻る。すなわち、トレースシミュレーション制御部６４は、通信同期命令の時間順序性が崩れる可能性を防ぐため、現プロセッサのトレースシミュレーション実行を後回しにする。
【０２８４】
ステップＳ６０５の結果、時間順序性違反なしと判定された場合（Ｓ６０５→Ｎｏ）、すなわち、通信同期命令の時間順序性が保証されると判定された場合、トレースシミュレーション制御部６４は、通信同期命令実行に起因するプロセッサのプロセッサ実行状態情報６９の更新を図５５に従って行う（Ｓ６０７）。
【０２８５】
ここで、図５５は、プロセッサの実行可能状態から実行待機状態へ遷移する条件を示した表である。図５５に示すように、プロセッサの実行可能状態から実行待機状態へ遷移する条件は、通信同期命令毎に予め設定されている。
【０２８６】
ステップＳ６０７の後、通信同期命令シミュレーション実行部６５は、プロセッサ実行状態情報６９を参照して現プロセッサが実行待機状態であるか否かを判定する（Ｓ６０８）。
ステップＳ６０８の結果、実行待機状態である場合（Ｓ６０８→Ｙｅｓ）、トレースシミュレーション制御部６４は、ステップＳ６０１へ処理を戻す。
【０２８７】
ステップＳ６０８の結果、実行待機状態ではない場合（Ｓ６０８→Ｎｏ）、通信同期命令シミュレーション実行部６５は、通信同期リソース状態情報６８を図５６に従って更新する（Ｓ６０９）。
図５６は、通信同期リソース状態情報の更新内容と、実行待機状態であるプロセッサの実行可能状態への復帰条件とを示した表である。図５６に示すように通信同期リソース状態情報６８の更新内容、および実行待機状態であるプロセッサの実行可能状態への復帰条件も通信同期命令毎に予め設定されている。
【０２８８】
そして、通信同期命令シミュレーション実行部６５は、ステップＳ６０９の結果、実行待機状態から実行可能状態に遷移した他のすべてのプロセッサについて、以下の処理を行う。
すなわち、通信同期命令シミュレーション実行部６５は、プロセッサ待機時間を反映するため、該当するプロセッサのプロセッサクロック値７０を現プロセッサのクロック値（プロセッサクロック値７０）に設定し（Ｓ６１０）、キュー指示部６３は、該当するプロセッサを「プロセッサキュー」に投入する（Ｓ６１１）。同時に実行時間推定算出部１５ｆは、実行トレース再生部１４ｆから取得した部分プログラム実行時間推定値をプロセッサ毎に加算する。
そして、通信同期命令シミュレーション実行部６５は、実行時間推定算出部１５ｆにおいて、算出された実行時間推定値を現プロセッサクロック値として、現プロセッサのプロセッサクロック値７０の更新を行い（Ｓ６１２）、トレースシミュレーション制御部６４は、処理をステップＳ６０３へ戻す。なお、ステップＳ６１２の段階で、部分プログラムテーブルにおけるすべての部分プログラムについて処理が終了している場合、トレースシミュレーション制御部６４は、処理を終了する。
【０２８９】
また、第７実施形態では、第１実施形態に係る処理をマルチプロセッサ処理したが、これに限らず第２〜第６実施形態に係る処理をマルチプロセッサ処理してもよい。この場合、図１０、図１１、図１５、図１９、図２０、図２３、図２９、図３０、、図３６、図４２および図４４における各処理がマルチプロセッサによる並列処理されることは当然である。
【０２９０】
（第７実施形態の効果）
第７実施形態によれば、マルチプロセッサを用いて複数の対象プログラムの実行時間を並列的に推定することができるため、効率的な実行時間の推定が可能となる。
【０２９１】
なお、特開２００７−１９３４３０号公報には、「プログラム処理部が現在のスレッド処理を終了した後にスレッド処理終了信号をデータ受信部に送信する」という記述があるが、第７実施形態では、「スレッド終了命令」が受信バッファ更新処理を起動する、としている。また、特開２００７−１９３４３０号公報には、「スレッド起動命令」の具体的実現方法の説明がなく、データ送信命令と同じ通信プロトコルで実装されているとする。すなわち、特開２００７−１９３４３０号公報において「スレッド起動命令」はデータの送信の代わりに「スレッド起動トークン」を送信し、受信プロセッサのデータ受信部にスレッド起動トークン用受信バッファが他のデータ受信バッファ同様に設けられているものとする。
【０２９２】
（実験例）
次に、図５７〜図５９を参照して、第７実施形態に係る実験結果を説明する。
図５７〜図５９において用いたコンピュータの仕様は、図４５から図４９において用いたコンピュータのＣＰＵをマルチプロセッサとした仕様であるため説明を省略する。
図５７は、比較例として命令セットシミュレータを用いた実験結果を示す表である。
用いた命令セットシミュレータは、３２ビットＲＩＳＣプロセッサを構成要素とするマルチプロセッサシステム上における並列プログラム実行処理時間を通信同期処理も含めてサイクル精度で推定する命令セットシミュレータを使用する（ただしキャッシュシミュレーションは含まない）。
また、図５７および図５８において使用するテストプログラム（対象プログラム）は、プロセッサ数５の６４タップＦＩＲ（Finite Impulse Response）フィルタプログラム（「ＦＩＲ」）と、プロセッサ数１９の画像サイズ８００×６００画素のＪＰＥＧエンコーダプログラム（「ＪＰＥＧ」）である。
【０２９３】
図５７において、前記２つの対象プログラムに対し、対象プログラムサイズは、対象プログラムにおける命令数である。プログラム逐次実行時間は、対象プログラムを実行した際のすべてのプロセッサにおける総クロックサイクル数を加算したものである。つまり、プログラム逐次実行時間は、対象プログラムを各プロセッサにおいて直列的に実行したときの実行時間を総クロック数で示したものである。プログラム並列実行時間は、対象プログラムをマルチプロセッサにおいて並列的に実行したときの実行時間を総クロックサイクル数で示したものである。並列処理速度向上率は、（プログラム逐次実行時間／プログラム並列実行時間）で算出される値である。マルチプロセッサ命令セットシミュレータ実行時間は、マルチプロセッサにおける命令セットシミュレータにおいて各対象プログラムの実行時間を推定するときに要する時間であり、単位は「秒」である。命令セットシミュレータ処理速度は、マルチプロセッサシステムにおいて各対象プログラムの実行時間を推定したときの処理速度をクロックサイクル数で示したものであり、単位は「クロックサイクル／秒」である。
【０２９４】
図５８は、第７実施形態に係る実験結果を示す例である。
なお、図５８において、部分プログラムテーブルサイズは、プログラム分割部１１ｆ（図５２）で生成される部分プログラムテーブルの行数の全プロセッサにおける合計値を示す。分岐履歴ビット系列長は、分岐履歴情報生成部１３ｆ（図５２）によって生成される分岐履歴ビット系列の長さ（ビット数）の全プロセッサにおける合計値である。対象プログラム並列実行時間推定値は、第７実施形態に係る実行時間推定装置１ｆ（図５０）によって算出される対象プログラムの並列実行時間推定値を総クロックサイクル数で示したものである。対象プログラム並列実行時間推定誤差は、算出された実行時間推定値と、実際の対象プログラムの実行時間との誤差であり、単位は「秒」である。実行時間推定算出時間は、第７実施形態に係る実行時間推定装置１ｆが対象プログラムの実行時間の算出にかかった時間であり、単位は「秒」である。対命令セットシミュレータ速度向上比は、（命令セットシミュレータにおける実行時間/実行時間推定装置１ｆにおける実行時間）で算出される値である。
【０２９５】
なお、図５８において「ＦＩＲ」については第２実施形態（「Ｌｏｏｐ＿Ｍｅｒｇｅ」）をマルチプロセッサに適用した結果を示し、「ＪＰＥＧ」については、第２実施形態（「Ｌｏｏｐ＿Ｍｅｒｇｅ」）と、第４実施形態（「Ｆｕｌｌ＿Ｍｅｒｇｅ」）をマルチプロセッサに適用した結果を示す。
図５８における対命令セットシミュレータ速度向上比を参照すると、いずれも場合も４１．２１〜１４９．９１となっており大幅な処理時間の改善がみられる。
【０２９６】
図５９は、局所タイミング再生精度の比較を示すグラフである。
図５９は、図５８におけるＪＰＥＧを、第２実施形態をマルチプロセッサに適用したとき（第２’実施形態とする）の局所タイミング再生精度と、第４実施形態をマルチプロセッサに適用したとき（第４’実施形態とする）の局所タイミング再生精度とを比較するグラフであり、縦軸は、対象プログラム中のコード処理におけるクロックサイクル数を示し、横軸は時間を示す。
第２’実施形態（「Ｌｏｏｐ＿Ｍｅｒｇｅ」）は、時間によってクロックサイクル数が変化している。これは、対象プログラム中のコード処理におけるクロックサイクル数を忠実に再現しており、局所タイミング再生精度が高いことを意味している。つまり、第２’実施形態（「Ｌｏｏｐ＿Ｍｅｒｇｅ」）は、局所タイミングについても予測精度を犠牲にすることはないので、局所的な処理負荷の変動を忠実に再現できている。また、第４’実施形態（「Ｆｕｌｌ＿Ｍｅｒｇｅ」）では、クロックサイクル数が平均化されているが、このようにコード処理におけるクロックサイクル数が平均化されていても、処理結果に与える影響は数％に留まるため、非特許文献７〜非特許文献１０に記載された方法などと比較して実行時間推定値の予測精度を高い状態に保つことができる。
【符号の説明】
【０２９７】
１，１ａ〜１ｇ  実行時間推定装置
１１，１１ｆ  プログラム分割部
１２，１２ｆ  部分プログラム実行時間推定算出部
１３，１３ｂ，１３ｃ，１３ｆ  分岐履歴情報生成部
１４，１４ｂ，１４ｃ，１４ｆ  実行トレース再生部
１５，１５ｂ，１５ｆ  実行時間推定算出部
２１    ループ情報抽出部
２１ｅ  第２種ループ情報抽出部
２２    プログラム実行履歴情報生成部
２３    第２種ループ実行時間推定算出部
３１    分岐確率情報抽出部
３２    第３種ループ縮退部
３３    多重ｉｆ−ｅｌｓｅ縮退部
４１    多重ループ縮退部
５１    ｉｆ−ｅｌｓｅブロック実行時間偏重度算出部
５２    ｉｆ−ｅｌｓｅ縮退制御部
５３    ループ実行時間偏重度算出部
５４    第４種ループ縮退制御部
６１    前処理部
６２    後処理部
６３    キュー指示部
６４    トレースシミュレーション制御部
６５    通信同期命令シミュレーション実行部
６６    記憶部
６７    位置指定情報
６８    通信同期リソース状態情報
６９    プロセッサ実行状態情報
７０    プロセッサクロック値
８１    部分プログラム実行頻度算出部
８２    関数縮退部
２１１  第１種・第２種ループ判別処理部
２１２  第１種ループ縮退部
２２１  第２種ループ回数データ系列生成部
３１１  条件変数別確率算出部
３３１  ｉｆ−ｅｌｓｅ縮退部
３３２  隣接縮退部
４１１  第４種ループ縮退部
【図１】
0005403760.tif 000003
【図２】
0005403760.tif 000004
【図３】
0005403760.tif 000005
【図４】
0005403760.tif 000006
【図５】
0005403760.tif 000007
【図６】
0005403760.tif 000008
【図７】
0005403760.tif 000009
【図８】
0005403760.tif 000010
【図９】
0005403760.tif 000011
【図１０】
0005403760.tif 000012
【図１１】
0005403760.tif 000013
【図１２】
0005403760.tif 000014
【図１３】
0005403760.tif 000015
【図１４】
0005403760.tif 000016
【図１５】
0005403760.tif 000017
【図１６】
0005403760.tif 000018
【図１７】
0005403760.tif 000019
【図１８】
0005403760.tif 000020
【図１９】
0005403760.tif 000021
【図２０】
0005403760.tif 000022
【図２１】
0005403760.tif 000023
【図２２】
0005403760.tif 000024
【図２３】
0005403760.tif 000025
【図２４】
0005403760.tif 000026
【図２５】
0005403760.tif 000027
【図２６】
0005403760.tif 000028
【図２７】
0005403760.tif 000029
【図２８】
0005403760.tif 000030
【図２９】
0005403760.tif 000031
【図３０】
0005403760.tif 000032
【図３１】
0005403760.tif 000033
【図３２】
0005403760.tif 000034
【図３３】
0005403760.tif 000035
【図３４】
0005403760.tif 000036
【図３５】
0005403760.tif 000037
【図３６】
0005403760.tif 000038
【図３７】
0005403760.tif 000039
【図３８】
0005403760.tif 000040
【図３９】
0005403760.tif 000041
【図４０】
0005403760.tif 000042
【図４１】
0005403760.tif 000043
【図４２】
0005403760.tif 000044
【図４３】
0005403760.tif 000045
【図４４】
0005403760.tif 000046
【図４５】
0005403760.tif 000047
【図４６】
0005403760.tif 000048
【図４７】
0005403760.tif 000049
【図４８】
0005403760.tif 000050
【図４９】
0005403760.tif 000051
【図５０】
0005403760.tif 000052
【図５１】
0005403760.tif 000053
【図５２】
0005403760.tif 000054
【図５３】
0005403760.tif 000055
【図５４】
0005403760.tif 000056
【図５５】
0005403760.tif 000057
【図５６】
0005403760.tif 000058
【図５７】
0005403760.tif 000059
【図５８】
0005403760.tif 000060
【図５９】
0005403760.tif 000061