执行时间估计方法、执行时间估计程序以及执行时间估计装置

摘要

提供一种执行时间估计方法、执行时间估计程序以及执行时间估计装置，其特征在于具有：程序分割部(11)，其从对象程序中提取由条件分支命令、函数调用命令分割的部分程序；部分程序执行时间估计算出部(12)，其算出各部分程序的执行时间，使各部分程序的开始命令、终止命令、以及所算出的部分程序的执行时间对应；分支历史记录信息生成部(13)，其生成分支历史记录比特序列，该分支历史记录比特序列是执行对象程序时的条件分支命令的真假的序列；执行跟踪再生部(14)，其根据分支历史记录比特序列来生成部分程序的执行序列；以及执行时间估计算出部(15)，其根据部分程序的执行序列来对部分程序执行时间进行相加。

说明书

技术领域

本发明涉及一种估计程序的执行时间的执行时间估计方法、执行时间估计程序以及执行时间估计装置。

背景技术

提出了多个估计程序的执行时间的方法(例如参照非专利文献1)。

作为这种估计程序的执行时间的方法之一，存在一种命令集模拟器(例如参照非专利文献2～非专利文献6)。另外，还提出了以下方法：通过执行将预测执行时间信息嵌入到程序内的程序来算出执行时间的方法(例如参照非专利文献7)；以及仅执行程序的一部分，根据该一部分的执行时间估计程序整体的执行时间的方法(例如参照非专利文献8～非专利文献10)。

非专利文献1：J.J.Yi and D.J.Lilja.Simulation of Computer Architectures：Simulators，Benchmarks，Methodologies，and Recommendations.IEEE Trans.Comput.，55(3)，2006.

非专利文献2：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.

非专利文献3：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.

非专利文献4：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.

非专利文献5：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.

非专利文献6：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.

非专利文献7：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.

非专利文献8：T.Sherwood，E.Perelman，G.Hamerly，and B.Calder.Automatically Characterizing Large Scale Program Behavior.In ASPLOS-X：Procee dings of the 10th international conference on Architectural Support for Programming Languages and Operating Systems，New York，NY，USA，2002.ACM Press.

非专利文献9：T.Sherwood，E.Perelman，G.Hamerly，S.Sair，and B.Calder.Discovering and Exploiting Program Phases.IEEE Micro，December 2003.

非专利文献10：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.

发明内容

发明要解决的问题

在非专利文献2～非专利文献6中记载的命令集模拟器能算出正确的执行时间的估计值，但是存在模拟的执行时间变长这种问题。另外，在非专利文献7～非专利文献10中记载的方法中能够缩短模拟的执行时间，但是存在估计值的精度降低这种问题。

因此，本发明的目的在于在较短的处理时间内执行正确的程序的执行时间估计。

用于解决问题的方案

为了解决上述问题，执行时间估计方法利用对程序的执行时间进行估计的执行时间估计装置来执行，该执行时间估计方法的特征在于，上述执行时间估计装置进行以下步骤：从上述程序提取将条件分支命令和函数调用命令中的至少一个作为边界点分割出的部分程序；算出各部分程序的执行时间并保存到存储部；将上述各部分程序的开始命令、终止命令以及所算出的部分程序的上述执行时间相关联地保存到上述存储部；生成分支历史记录比特序列并保存到上述存储部，该分支历史记录比特序列是与执行上述程序时的上述条件分支命令有关的真假序列；根据上述分支历史记录比特序列来生成描述有上述部分程序的执行顺序的上述部分程序执行序列；以及根据上述部分程序执行序列来将上述部分程序的执行时间进行相加。

根据上述结构，所算出的执行时间估计值是将以较高精度算出的部分程序的执行时间进行相加而得到的值，因此能够以较高精度估计程序的执行时间。并且，所生成的分支历史记录比特序列与程序执行命令数相比明显少，因此能够在远远小于实际的程序执行时间的处理时间内进行执行时间的估计。

另外，上述执行时间估计方法的特征在于，进行以下步骤：上述部分程序反复进行规定次数的循环的情况下，在上述循环内部不包含上述条件分支命令并且上述循环中的部分程序的反复次数在上述程序中不变时，进行如下聚合：对上述循环内的部分程序的执行时间乘以上述反复次数来算出循环执行时间，并将所算出的上述循环执行时间设为一个上述部分程序的执行时间；以及在上述分支历史记录比特序列中，将与同进行了上述聚合的循环对应的部分程序相关联的上述真假序列概括为一个真假信息。

根据上述结构，能够将反复进行相同部分程序的循环作为一个部分程序而集中来进行处理，因此能够在较短处理时间内估计程序的执行时间。

另外，上述执行时间估计方法的特征在于，进行以下步骤：在上述部分程序反复进行规定次数的循环的情况下，在上述循环内部不包含上述条件分支命令并且上述循环中的部分程序的反复次数在各个上述程序中不变时，生成各循环的反复次数的序列；算出将上述循环内的部分程序的执行时间乘以上述反复次数的序列中的反复次数而得到的循环的执行时间；将所算出的上述各循环的执行时间进行相加；以及在上述分支历史记录比特序列中，不描述与对应于上述循环的部分程序相关联的上述真假序列。

根据上述结构，有可能在循环外变更反复次数，因此即使难以作为一个部分程序而集中来进行处理的循环也能够根据反复次数的序列等来与其它部分程序分开地估计循环的执行时间。由此，能够作为一个部分程序来进行处理，能够在较短处理时间内估计程序的执行时间。

另外，上述执行时间估计方法的特征在于，进行以下步骤：在上述部分程序反复进行规定次数的循环的情况下，在上述循环内部包含if-else分支命令时，算出上述if-else分支命令为真的概率以及上述if-else分支命令为假的概率；相加如下两个值：对上述if-else分支命令为真时执行的部分程序的执行时间乘以上述if-else分支命令为真的概率而得到的值；以及对上述if-else分支命令为假时执行的部分程序的执行时间乘以上述if-else分支命令为假的概率而得到的值；以及进行如下聚合：将上述if-else分支命令为真时执行的上述部分程序以及上述if-else分支命令为假时执行的上述部分程序设为一个部分程序。

根据上述结构，在循环内部包含if-else分支命令，因此即使在难以将循环集中为一个部分程序的情况下，也能够通过将随着if-else分支命令的真假而执行的部分程序集中为一个，来将内部包含if-else分支命令的循环集中为一个部分程序。

另外，上述执行时间估计方法的特征在于，进行以下步骤：上述部分程序是反复进行规定次数的循环的情况下，在上述循环是仅由包含一个作为决定是否继续上述循环的分支的循环继续条件命令的循环构成的多重循环时，该执行时间估计方法进行以下步骤：算出该循环内的if-else分支命令为真的概率以及上述if-else分支命令为假的概率；进行如下聚合：根据上述概率，从内侧的循环起依次算出上述循环的平均执行时间，将所算出的上述循环的平均执行时间作为一个上述部分程序的执行时间；以及在上述分支历史记录比特序列中，不描述与进行了上述聚合的循环对应的序列。

根据上述结构，是循环内部包含循环的多重循环，因此即使在难以将多重循环的块集中为一个部分程序的情况下，也能够通过从多重循环的内侧按循环顺序求出每个循环的平均执行时间，来将多重循环也集中为一个部分程序。

其特征在于，进行以下步骤：在具有多个上述部分程序的函数中，进行以下步骤：算出上述部分程序的出现频率；通过对所算出的上述部分程序的上述执行时间乘以上述部分程序的出现频率，来算出上述函数内的上述部分程序的全部执行时间估计值；关于上述函数内的上述部分程序，通过算出上述部分程序的全部执行时间估计值的总和来算出函数的全部执行时间估计值；以及在上述分支历史记录比特序列中，不描述与算出了上述全部执行时间估计值的函数对应的序列。

根据上述结构，如果是不存在递归函数调用(例如在函数内调用自己的函数的情形等)的程序，则一定能够将全部程序聚合为一个部分程序。

另外，上述执行时间估计方法的特征在于，上述部分程序反复进行规定次数的循环的情况下，对该循环进行第一部分程序聚合处理和第二部分程序聚合处理，该执行时间估计方法的特征在于，在上述第一部分程序聚合处理中，在上述循环中的第一循环为多重循环且在上述程序中至少存在一个上述第一循环的情况下，进行以下步骤，其中，该多重循环仅包含含有一个循环继续条件命令的循环，该循环继续条件命令是决定在上述第一循环内部是否继续进行反复处理的分支：在该第一循环内部含有if-else分支命令的情况下，算出上述if-else分支命令为真的概率以及上述if-else分支命令为假的概率；进行如下聚合：根据上述概率，从内侧的循环起依次算出上述第一循环的平均执行时间，将所算出的上述第一循环的平均执行时间设为一个上述部分程序的执行时间；以及在上述分支历史记录比特序列中，不描述与进行了上述聚合的部分程序对应的序列，在上述第二部分程序聚合处理中，第二循环为在上述第二循环内部不包含上述条件分支命令且反复次数在各个上述第二循环中不变的循环、并且在上述程序中至少存在一个上述第二循环的情况下，进行以下步骤：生成各上述第二循环中的部分程序的反复次数的序列；将对应于上述第二循环的部分程序的执行时间乘以上述反复次数的序列中的反复次数来算出循环的执行时间估计值；将所算出的各上述第二循环的执行时间估计值进行相加；以及在上述分支历史记录比特序列中，不描述对应于上述循环的序列。

根据上述结构，能够进行将if-else分支块集中为一个部分程序的处理，能够将循环集中为一个部分程序，从而能够在较短处理时间内估计程序的执行时间。

另外，上述执行时间估计方法的特征在于，进行以下步骤：算出if-else执行时间偏重度，该if-else执行时间偏重度是由if-else分支命令的真假而引起的上述部分程序的执行时间的偏重度；以及在上述if-else执行时间偏重度为规定值以上的情况下，不执行上述第一部分程序聚合处理。

根据上述结构，能够抑制由使用概率引起的部分程序的执行时间的波动的影响的消失，能够确认局部的程序执行时间。

另外，上述执行时间估计方法的特征在于，上述if-else执行时间偏重度为对如下两个执行时间的差的绝对值乘以上述if-else分支命令的执行次数而得到的值：上述if-else分支命令为真时的部分程序的执行时间；以及上述if-else分支命令为假时的部分程序的执行时间。

根据上述结构，能够正确地算出执行时间偏重度。

另外，上述执行时间估计方法的特征在于，进行以下步骤：根据各上述第一循环的反复次数的偏重度来算出循环执行时间偏重度；以及在上述循环执行时间偏重度大于规定值的情况下，不执行上述第二部分程序聚合处理。

根据上述结构，能够抑制由使用循环的平均执行时间引起的循环的执行时间的波动的影响的消失。

另外，特征在于，上述循环执行时间偏重度为将上述第一循环内的各循环中的反复次数的方差、上述循环的反复次数以及上述循环的平均执行时间进行相乘而得到的值。

根据上述结构，能够正确地算出循环执行时间偏重度。

另外，特征在于，上述执行时间估计装置为装载了单处理器的计算机。

根据上述结构，能够利用单一处理器来实现上述执行时间估计方法，从而能够提高通用性。

另外，上述执行时间估计方法的特征在于，上述执行时间估计装置为装载了多处理器的计算机，并行地算出多个程序的执行的估计时间。

根据上述结构，能够利用多处理器来实现上述执行时间估计方法，能够并行地处理多个程序的执行时间的估计，从而能够实现高速化。

另外，上述执行时间估计方法的特征在于，上述程序为通信同步并且与其它程序协同地被执行的程序，上述部分程序包含通信同步部分程序，该通信同步部分程序是指示与其它程序之间的通信同步的程序，上述执行时间估计装置在根据上述分支历史记录比特序列生成上述部分程序的执行序列时，在成为处理对象的上述部分程序为上述通信同步部分程序的情况下，根据上述通信同步部分程序的种类，来对构成上述多处理器的处理器的执行状态进行更新。

根据上述结构，能够在如实地再现工序之间的通信同步的同时进行包含多个工序的程序的执行时间的估计。

执行时间估计程序的特征在于，使计算机执行上述执行时间估计方法。

根据上述结构，能够提供一种使计算机执行上述执行时间估计方法的程序。

另外，执行时间估计装置估计程序的执行时间，其特征在于，具有：程序分割部，其从上述程序中提取将条件分支命令和函数调用命令中的至少一个作为边界点而分割出的部分程序；部分程序执行时间估计算出部，其算出各部分程序的执行时间，将上述各部分程序的开始命令、终止命令以及所算出的部分程序的上述执行时间相关联地保存到上述存储部；分支历史记录信息生成部，其生成分支历史记录比特序列并保存到上述存储部，该分支历史记录比特序列是与执行上述程序时的上述条件分支命令有关的真假序列；执行跟踪再生部，其根据上述分支历史记录比特序列来生成描述有上述部分程序的执行顺序的上述部分程序执行序列；以及执行时间估计算出部，其根据上述部分程序执行序列来将上述部分程序的执行时间进行相加。

根据上述结构，所算出的执行时间估计值是将以较高精度算出的部分程序的执行时间进行相加而得到的值，因此能够以较高精度估计程序的执行时间。并且，所生成的分支历史记录比特序列与程序执行命令数相比明显少，因此能够在远远小于实际的程序执行时间的处理时间内进行执行时间的估计。

发明的效果

根据本发明，能够在较短处理时间内实现正确的程序的执行时间估计。

附图说明

图1是示出第一实施方式所涉及的执行时间估计装置的结构例的图。

图2是示出本实施方式所涉及的执行时间估计装置的硬件结构的例子的图。

图3是示出第一实施方式所涉及的程序执行时间估计方法的流程的流程图。

图4是第一实施方式所涉及的对象程序的例子。

图5是示出第一实施方式所涉及的部分程序表的例子的图。

图6是示出用于输出分支历史记录比特序列的文件输入输出函数的例子的图。

图7是示出图4中的对象程序的一部分的图。

图8是示出覆盖图7示出的程序之后的程序的例子的图。

图9是示出第二实施方式所涉及的执行时间估计装置的结构例的图。

图10是示出第二实施方式所涉及的程序执行时间估计方法的处理的流程的流程图。

图11是示出第二实施方式所涉及的循环信息提取处理的流程的流程图。

图12是与某一个对象程序中的循环有关的图，(a)是某一个循环的结构示意图，(b)是表示由具有(a)示出的结构的循环生成的部分程序的结构的例子的表。

图13是在第二实施方式中使用的部分程序表的例子。

图14是用于说明第一种循环的聚合的图，(a)是聚合前的部分程序表，(b)是聚合后的部分程序表。

图15是示出第二实施方式所涉及的程序执行历史记录信息生成处理的流程的流程图。

图16是示出用于生成第二种循环次数数据序列的对象程序的覆盖例的图，(a)示出覆盖前、(b)示出覆盖后、(c)示出生成第二种循环次数数据序列和分支历史记录比特序列的函数。

图17是用于具体地说明第二种循环执行时间估计算出部的处理的图。

图18是示出第三实施方式所涉及的执行时间估计装置的结构例的图。

图19是示出第三实施方式所涉及的程序执行时间估计方法的流程的流程图。

图20是示出第三实施方式所涉及的分支概率信息提取处理的流程的流程图。

图21是示出包含第三种循环的其它例的对象程序的图。

图22是示出由图21示出的对象程序生成的部分程序表的例子的图。

图23是示出第三实施方式所涉及的多重if-else聚合处理的流程的图。

图24是示出包含第三种循环的对象程序的例子的图。

图25是示出由图24示出的对象程序生成的部分程序表的例子的图。

图26是进行了聚合处理的部分程序表的例子，(a)示出对“J”进行if-else聚合处理的结果，(b)是对(a)的结果进行相邻聚合处理的结果，(c)是对“H”进行if-else聚合处理的结果，(d)是对(c)的结果进行相邻聚合处理的结果。

图27是示出第四实施方式所涉及的执行时间估计装置的结构例的图。

图28是示出包含第四种循环的对象程序的例子的图。

图29是示出第四实施方式所涉及的程序执行时间估计方法的流程的流程图。

图30是示出第四实施方式所涉及的多重循环聚合处理的流程的图。

图31是示出由图28示出的对象程序生成的部分程序表的例子的图。

图32是示出条件变量的分支概率的表的图。

图33是示出进行了第四种循环聚合处理的部分程序表的例子的图，(a)示出进行了if-else聚合处理的例子，(b)示出对(a)的结果进行了相邻聚合处理的例子。

图34是对图33的(b)示出的部分程序表进行聚合处理的例子，(a)是对图33的(b)的结果进行循环聚合处理的例子，(b)是对(a)的结果进行相邻聚合处理的例子，(c)是对(b)的结果进行循环聚合处理的例子，(d)是对(c)的结果进行相邻聚合处理的例子。

图35是示出第五实施方式所涉及的执行时间估计装置的结构例的图。

图36是示出在循环内包含“break”语句和“return”语句的对象程序的例子的图。

图37是示出第五实施方式所涉及的程序执行时间估计方法的流程的流程图。

图38是示出描述了部分程序执行频率的信息的部分程序表的例子的图。

图39是对图38示出的部分程序表进行聚合处理的例子，(a)是进行了函数func4聚合处理的例子，(b)是进行了部分程序“63”的聚合处理的例子，(c)是聚合后的最终部分程序表的例子。

图40是示出反复执行对象程序中的代码时的代码执行时间的示意图，(a)是应用了第二实施方式的例子，(b)是应用了第四实施方式的例子。

图41是示出第六实施方式所涉及的执行时间估计装置的结构例的图。

图42是示出第六实施方式所涉及的程序执行时间估计方法的流程的流程图。

图43是示出步骤S503和步骤S504中的处理结果、所生成的部分程序表的例子的图。

图44是示出第六实施方式所涉及的多重循环聚合处理的流程的流程图。

图45是示出作为比较例使用命令集模拟器的试验结果的表。

图46是示出第一实施方式所涉及的试验结果的例子。

图47是示出第四实施方式所涉及的试验结果的例子。

图48是汇总第一～第四、第六实施方式所涉及的试验结果的表。

图49是示出第一～第四、第六实施方式中的试验结果的图表。

图50是示出第七实施方式所涉及的执行时间估计装置的结构例的图。

图51是示出第七实施方式所涉及的执行时间估计装置的硬件结构的图。

图52是示出第七实施方式所涉及的前处理部的详细结构例的图。

图53是示出第七实施方式所涉及的后处理部的详细结构例的图。

图54是示出第七实施方式所涉及的后处理部中的处理流程的流程图。

图55是示出处理器从可执行状态转移到执行待机状态的条件的表。

图56是示出通信同步资源状态信息的更新内容以及处于执行待机状态的处理器变为可执行状态的恢复条件的表。

图57是示出作为比较例使用命令集模拟器的试验结果的表。

图58是示出第七实施方式所涉及的试验结果的例子。

图59是示出局部定时再生精度的比较的图表。

附图标记说明

1、1a～1g：执行时间估计装置；11、11f：程序分割部；12、12f：部分程序执行时间估计算出部；13、13b、13c、13f：分支历史记录信息生成部；14、14b、14c、14f：执行跟踪再生部；15、15b、15f：执行时间估计算出部；21：循环信息提取部；21e：第二种循环信息提取部；22：程序执行历史记录信息生成部；23：第二种循环执行时间估计算出部；31：分支概率信息提取部；32：第三种循环聚合部；33：多重if-else聚合部；41：多重循环聚合部；51：if-else块执行时间偏重度算出部；52：if-else聚合控制部；53：循环执行时间偏重度算出部；54：第四种循环聚合控制部；61：前处理部；62：后处理部；63：队列指示部；64：跟踪模拟控制部；65：通信同步命令模拟执行部；66：存储部；67：位置指定信息；68：通信同步资源状态信息；69：处理器执行状态信息；70：处理器时钟值；81：部分程序执行频率算出部；82：函数聚合部；211：第一种和第二种循环辨别处理部；212：第一种循环聚合部；221：第二种循环次数数据序列生成部；311：条件变量分类概率算出部；331：if-else聚合部；332：相邻聚合部；411：第四种循环聚合部。

具体实施方式

接着，适当地参照附图对用于实施本发明的优选方式(以下称为“实施方式”)进行详细说明。此外，在本实施方式中，块表示循环、if-else分支命令等支配的程序范围。例如在循环块中有时包含if-else命令、循环等，在if-else块中包含其它if-else命令等。下面，根据需要适当地使用“块”的词语。此外，if-else块包含if语句所支配的范围和else语句所支配的范围。

(第一实施方式：结构)

图1是表示第一实施方式所涉及的执行时间估计装置的结构例的图。

执行时间估计装置1a(1)具有程序分割部11、部分程序执行时间估计算出部12、分支历史记录信息生成部13、执行跟踪再生部14以及执行时间估计算出部15。下面，对执行时间估计装置1a中的各部的概要进行说明，详细的处理内容参照图3～图8来进行说明。

程序分割部11具有以下功能：将条件分支命令和函数调用命令作为边界点来将成为执行时间估计的对象的程序(下面记载为对象程序)分割为多个部分程序，生成在表内示出各个部分程序的部分程序表。参照图5来在后面说明部分程序表。此外，在本实施方式中，条件分支命令包含if-else分支命令、在for语句中作为是否继续进行循环的条件命令的循环继续条件命令。

部分程序执行时间估计算出部12具有以下功能：对于程序分割部11所生成的部分程序分别算出执行时间(部分程序执行时间估计值)，并将所算出的部分程序执行时间估计值追加到部分程序表中。并且，部分程序执行时间估计算出部12还具有以下功能：将追加部分程序执行时间估计值后的部分程序表发送到执行跟踪再生部14、执行时间估计算出部15。

分支历史记录信息生成部13具有以下功能：生成作为对象程序内的条件分支命令中的条件变量的真假值(“1”和“0”的二值表现)的序列的分支历史记录比特序列，并发送到执行时间估计算出部15。

执行跟踪再生部14具有以下功能：根据从部分程序执行时间估计算出部12发送的、追加部分程序执行时间估计值后的部分程序表以及分支历史记录信息生成部13所生成的分支历史记录比特序列，按部分程序的执行顺序从部分程序表中读取部分程序执行时间估计值，将读取到的部分程序执行时间估计值依次发送到执行时间估计算出部15。

执行时间估计算出部15具有以下功能：对由执行跟踪再生部14发送的部分程序执行时间估计值依次进行相加来估计对象程序整体的执行时间。

图2是表示本实施方式所涉及的执行时间估计装置的硬件结构的例子的图。

图2示出的硬件结构可以是图1示出的执行时间估计装置1a的硬件结构，也可以是图9、图18、图27、图35、图41示出的执行时间估计装置1b～1e、1g的硬件结构。

执行时间估计装置1具备CPU(Central Processing Unit：中央处理器)151、ROM(Read Only Memory：只读存储器)152、RAM(Random Access Memory：随机存取存储器)153以及EEPROM(Electrically Erasable and Programmable Read Only Memory：电可擦除只读存储器)154，它们通过总线161相互连接。并且，在执行时间估计装置1中，显示器等输出部155、键盘或鼠标等收入部156、NIC(Network Interface Card：网络接口卡)等作为通信接口的通信部157以及从可移动记录介质159读取信息的驱动器158与输入输出接口160相连接。输入输出接口160与总线161相连接，由此控制输出部155、输入部156、通信部157以及驱动器158与CPU 151、ROM 152、RAM 153以及EEPROM 154之间的信息流动。此外，在本实施方式中，将RAM 153、对驱动器158与可移动记录介质159进行组合的装置等记载为存储装置170。

图1示出的各部11～15将存储于存储装置170等中的执行时间估计程序加载到RAM 153中而由CPU 151执行来实现。

接着，参照图1并按照图3来说明本实施方式所涉及的程序执行时间估计方法。

图3是表示第一实施方式所涉及的程序执行时间估计方法的流程的流程图。

(程序分割处理)

首先，程序分割部11进行程序分割处理(S101)，将对象程序分割为部分程序。部分程序是指将条件分支命令和函数调用命令作为边界点、内部不包含条件分支命令、函数调用命令的执行命令序列。

程序分割的实际

图4是第一实施方式所涉及的对象程序的例子。

在图4示出的对象程序中存在与条件变量“A”、“B”、“C”、“D”以及“E”有关的五个条件分支命令。

程序分割部11对图4示出的对象程序进行图3的步骤S101的程序分割处理时输出图5示出的部分程序表。

<部分程序表>

下面，参照图4来说明图5中的部分程序表。

图5是表示第一实施方式所涉及的部分程序表的例子的图。

部分程序表具有“部分程序ID(Identification)”(下面，在部分程序表的附图内记载为“ID”)、“部分程序开始命令”、“部分程序终止命令”以及“部分程序执行时间估计值”而分别作为字段(列)。此外，部分程序表是当被程序分割部11生成时保存到RAM 153(图2)等存储装置170(图2)中的数据。

“部分程序ID”是由部分程序分割部11按每个部分程序唯一地附加的ID。

“部分程序开始命令”是描述各个部分程序中的开始命令的字段。

例如，对应于图5的部分程序ID“1”的部分程序(下面，将对应于部分程序ID“n”的部分程序记载为部分程序“n”)中的“main:start”以及部分程序“8”中的“func1:start”分别表示函数(main函数和func1函数)的初始命令。另外，部分程序“2”中的“branch(A)[T]”表示图4中的条件变量“A”为“真”的值时的条件分支命令，部分程序“3”中的“branch(A)[F]”表示图4中的条件变量“A”为“假”的值时的条件分支命令。

“部分程序终止命令”是描述各个部分程序的终止的命令的字段。

例如，当参照部分程序“1”时，可知“branch(A)”为部分程序的终止命令。即，可知部分程序“1”为从“main:start”(部分程序开始命令)至“branch(A)”(部分程序终止命令)。同样地，部分程序“2”为从“branch(A)”具有“真”的值时起至branch(B)。

此外，如部分程序“6”的“部分程序终止命令”中的“func1:start|branch(A)”那样，在记载有多个命令(以“|”标记分开)的情况下，表示如下内容：控制从记载于“部分程序开始命令”的函数转移到调用函数“func1”的初始命令“func1:start”，函数“func1”的执行结束之后(即，到达“func1:end”之后)最终到达branch(A)。

此外，图5中的“部分程序执行时间估计值”为由部分程序执行时间估计算出部12在步骤S102中算出的部分程序的执行时间的估计值，该字段在步骤S101的阶段中成为空栏。

(部分程序执行时间估计算出处理)

返回到图3，接着步骤S101之后，部分程序执行时间估计算出部12进行部分程序执行时间估计算出处理(S102)。

部分程序执行时间估计算出部12在步骤S102中算出在步骤S101中生成的各部分程序的对象处理器上的执行时间的估计值。此外，部分程序执行时间估计算出部12通过实际执行部分程序来算出部分程序的执行时间。在此，关于在对象程序中反复产生的部分程序，算出一次量的执行时间即可，因此与直接对对象程序估计执行时间的方法相比，能够在远远短的时间内结束步骤S102。例如，即使在“α”这种部分程序根据循环、条件分支命令等而多次执行的状态下，也只要在步骤S102中算出“α”一次量的执行时间即可。此外，在已经存在生成对象程序的执行机械代码的编译程序的情况下，各分割程序的处理时间在内部不包含条件分支命令、函数调用，因此能够高精度进行估计。另外，在未开发对象处理器专用的编译程序的情况下，关于各分割程序的处理时间，根据对象处理器的结构性特征算出各命令的执行时间的预测值(各计算命令的执行时间、存储器访问时间)，根据这些预测值来算出执行时间的估计值。

部分程序执行时间估计算出部12将所算出的部分程序执行时间估计值写入到图5的部分程序表的“部分程序执行时间估计值”的字段中。

在此，图5的“部分程序执行时间估计值”的字段表示从对应的部分程序的开始命令至终止命令的执行时间。例如，部分程序“1”中的“T1”表示从“main:start”至“branch(A)”的执行时间，其中，包含“代码区域1”、“i＝0”以及“i＜N”(图4)这种计算命令。

另外，部分程序“4”中的“T4”表示条件“B”为“真”的情况下的分支命令至“branch(A)”的执行时间，其中，包含“代码区域2”、“代码区域3”、“i++”以及“i＜N”(图4)这种计算命令。

此外，图5中的部分程序“6”中的“T6a”表示从条件“C”为“真”的情况下的分支命令至调用函数“func1”的开始命令“func1:start”的执行时间。

相同部分程序“6”中的“T6b”表示从控制从函数“func1”返回到“main”之后至“branch(A)”的执行时间，其中，包含“代码区域3”、“i++”以及“i＜N”(图4)这种计算命令。

(分支历史记录信息生成处理)

返回到图3，当步骤S102的处理结束时，分支历史记录信息生成部13进行分支历史记录信息生成处理(S103)。

分支历史记录信息生成部13在步骤S103中执行对象程序，以1比特信息来表现执行了对象程序时的所有条件分支命令中的“真”和“假”，将按执行该1比特信息的顺序结合而生成的分支历史记录比特序列保存到RAM 153等存储装置170。分支历史记录比特序列例如成为以“真”为“1”、“假”为“0”表现的“1110111010”这样的1比特信息的序列。

对象程序中的条件分支命令执行数为全部命令执行数中的百分之几左右，而且能够以1比特表现分支条件的执行结果，因此即使在执行非常长的对象程序的情况下也能够以比较少的数据容量表现分支历史记录比特序列。因此，即使保存到硬盘那样的具有非常大的延迟时间的信息存储介质，也存在大幅缩短用于保存程序执行历史记录信息的开销时间的效果。并且，分支历史记录信息生成部13并未将条件变量的真假值分别以1比特直接记录到硬盘等外部存储装置，而是通过内部寄存器、缓存存储器、主存储装置(main memory)等存储器层，最终将分支历史记录信息保存到外部存储装置(硬盘等)，因此与依次保存到硬盘的情况相比，能够缩短延迟时间。

分支历史记录信息生成处理的实际

在各部分程序的开始命令为条件分支命令的情况下，能够通过使将这些条件变量的真假值(“1”和“0”的二值表现的值)记录到存储装置170的命令程序附加到对象程序来实现分支历史记录信息生成部13。所附加的命令程序例如为图6示出那样的文件输出函数程序。也就是说，能够通过由执行时间估计装置1a调用图6示出的文件输出函数程序，来实现分支历史记录信息生成部13。

图6是表示用于输出分支历史记录比特序列的文件输入输出函数的例子的图，图7是表示图4中的对象程序的一部分的图，图8是表示覆盖图7示出的程序之后的程序的例子的图。

此外，图7示出图4的对象程序中的第三行和第四行。

分支历史记录信息生成部13在定义图5那样的文件输出函数之后，如图8所示那样将在图6中条件变量“A”和“B”出现在程序上的位置覆盖即可。并且，通过由执行时间估计装置1a执行图8那样覆盖后的对象程序来实现分支历史记录信息生成部13，由此能够获取分支历史记录比特序列。

(执行跟踪再生处理)

返回到图3，当结束步骤S103时，执行跟踪再生部14根据部分程序表和分支历史记录比特序列来进行执行跟踪再生处理(S104)。执行跟踪再生部14在步骤S104中依次读取在步骤S103中生成的分支历史记录比特序列的比特，根据在步骤S102中生成的部分程序表来再生程序执行跟踪，生成部分程序执行序列。

执行跟踪再生处理的实际

下面，参照图5说明分支历史记录比特序列为“1110111010”的情况下的执行跟踪再生处理的实际。

首先，执行跟踪再生部14读取部分程序表中的部分程序“1”，到达“部分程序终止命令”“branch(A)”。此时，执行跟踪再生部14读取部分程序“1”的部分程序执行时间估计值“T1”，将该部分程序执行时间发送到执行时间估计算出部15。

分支历史记录比特序列的开头比特“1”表示条件变量“A”为“真”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(A)[T]”的部分程序“2”，到达其“部分程序终止命令”“branch(B)”。然后，执行跟踪再生部14读取部分程序“2”的部分程序执行时间估计值“T2”，将该部分程序执行时间发送到执行时间估计算出部15。

分支历史记录比特序列的第二个比特“1”表示条件变量“B”为“真”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(B)[T]”的部分程序“4”，到达其“部分程序终止命令”“branch(A)”。然后，执行跟踪再生部14读取部分程序“4”的部分程序执行时间估计值“T4”，将该部分程序执行时间发送到执行时间估计算出部15。

下面，同样地，分支历史记录比特序列的第三个分支历史记录比特“1”表示条件变量“A”为“真”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(A)[T]”的部分程序“2”，到达作为其“部分程序终止命令”的“branch(B)”。然后，执行跟踪再生部14读取部分程序“2”的部分程序执行时间估计值“T2”，将该部分程序执行时间发送到执行时间估计算出部15。

接着，分支历史记录比特序列的第四个分支历史记录比特“0”表示条件变量“B”为“假”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(B)[F]”的部分程序“5”，到达作为其“部分程序终止命令”的“branch(C)”。然后，执行跟踪再生部14读取部分程序“5”的部分程序执行时间估计值“T5”，将该部分程序执行时间发送到执行时间估计算出部15。

然后，分支历史记录比特序列的第五个分支历史记录比特“1”表示条件变量“C”为“真”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(C)[T]”的部分程序“6”，到达作为第一终止命令的调用函数“func1:start”。此时，执行跟踪再生部14将部分程序压入到堆栈而调用，将原来的部分程序记录到RAM 153等存储装置170(图2)。然后，执行跟踪再生部14读取部分程序“6”的部分程序执行时间估计值“T6a”，将该部分程序执行时间发送到执行时间估计算出部15。之后，执行跟踪再生部14无条件转移到部分程序“8”，到达其“部分程序终止命令”“branch(D)”。

接着，分支历史记录比特序列的第六个分支历史记录比特“1”表示条件变量“D”为“真”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(D)[T]”的部分程序“9”，到达作为其“部分程序终止命令”的“branch(D)”。然后，执行跟踪再生部14读取部分程序“9”的部分程序执行时间估计值“T9”，将该部分程序执行时间发送到执行时间估计算出部15。

然后，分支历史记录比特序列的第七个分支历史记录比特“1”表示条件变量“D”为“真”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(D)[T]”的部分程序“9”，到达作为其“部分程序终止命令”的“branch(D)”。然后，执行跟踪再生部14读取部分程序“9”的部分程序执行时间估计值“T9”，将该部分程序执行时间发送到执行时间估计算出部15。

并且，分支历史记录比特序列的第八个分支历史记录比特“0”表示条件变量“D”为“假”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(D)[F]”的部分程序“10”，到达作为其“部分程序终止命令”的“branch(E)”。然后，执行跟踪再生部14读取部分程序“10”的部分程序执行时间估计值“T10”，将该部分程序执行时间发送到执行时间估计算出部15。

接着，分支历史记录比特序列的第九个分支历史记录比特“1”表示条件变量“E”为“真”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(E)[T]”的部分程序“11”，到达作为其“部分程序终止命令”的“func1:end”。之后，执行跟踪再生部14从堆栈取出部分程序“6”，到达作为该第二部分程序终止命令的“branch(A)”。然后，执行跟踪再生部14读取部分程序“6”的第二部分程序执行时间估计值“T6b”，将该部分程序执行时间发送到执行时间估计算出部15。

然后，分支历史记录比特序列的第十个分支历史记录比特“0”表示条件变量“A”为“假”的情况，因此执行跟踪再生部14转移到“部分程序开始命令”为“branch(A)[F]”的部分程序“3”，到达作为其“部分程序终止命令”的“main:end”。在该时刻结束程序执行。然后，执行跟踪再生部14读取部分程序“3”的部分程序执行时间估计值“T3”，将该部分程序执行时间发送到执行时间估计算出部15。

进行这种处理，执行跟踪再生部14从部分程序表依次获取与部分程序ID对应的部分程序执行时间估计值，由此如下那样的部分程序执行序列被发送到执行时间估计算出部15。

main:start→[T1]→A(1)→[T2]→B(1)→[T4]→A(1)→[T2]→B(0)→[T5]→C(1)→[T6a]→func1:start→[T8]→D(1)→[T9]→D(1)→[T9]→D(0)→[T10]→E(1)→[T11]→func1:end→[T6b]→A(0)→[T3]→main:end

在此，[Tx]表示其部分程序执行时间(图5的部分程序表的“部分程序执行时间估计值”)，A(1)表示条件变量“A”为“真”的情况，A(0)表示条件变量“A”为“假”的情况。此外，实际上，执行跟踪再生部14每次从部分程序表读取部分程序执行时间估计值时，都依次发送到执行时间估计算出部15。

通过进行这样的执行跟踪再生处理(S104)，能够正确地再生实际执行对象程序时的所有执行命令序列。并且，还产生以下次要的效果：通过进行执行跟踪再生处理，能够正确地计算各种程序执行简档信息(各命令的执行频率、各函数调用的执行频率、各条件分支命令的分支概率等)。

(执行时间估计算出处理)

在步骤S104之后，执行时间估计算出部15进行执行时间估计算出处理，即通过将从执行跟踪再生部14依次发送过来的部分程序执行时间估计值按发送过来的顺序进行相加来算出对象程序整体的执行时间估计值(S105)。此外，执行时间估计算出部15也可以根据从执行跟踪再生部14发送的部分程序执行序列从部分程序表读取部分程序执行时间估计值，代入到执行序列，并进行相加，由此算出对象程序整体的执行时间估计值。

执行时间估计算出处理的实际

当再次记载步骤S104中生成的部分程序执行序列时，形成以下那样的序列。

main:start→[T1]→A(1)→[T2]→B(1)→[T4]→A(1)→[T2]→B(0)→[T5]→C(1)→[T6a]→func1:start→[T8]→D(1)→[T9]→D(1)→[T9]→D(0)→[T10]→E(1)→[T11]→func1:end→[T6b]→A(0)→[T3]→main:end

在此，执行时间估计算出部15对[Tx](部分程序执行时间估计值)依次进行相加，由此与部分程序执行序列对应的程序执行跟踪的执行时间(对象程序整体的执行时间估计值)形成以下式(1.1)。

TotalTime_1＝T1+T2+T4+T2+T5+T6a+T8+T9+T9+T10+T11+T6b+T3…(1.1)

接着，作为分支历史记录比特序列的其它例，示出以下的分支历史记录比特序列“1001011100”。

通过与上述分支历史记录比特序列同样的处理，来从该分支历史记录比特序列生成以下那样的部分程序执行序列。

main:start→[T1]→A(1)→[T2]→B(0)→[T5]→C(0)→[T7]→A(1)→[T2]→B(0)→[T5]→C(1)→[T6a]→func1:start→[T8]→D(1)→[T9]→D(1)→[T9]→D(0)→[T10]→E(0)→[T12]→main:end

因而，与该分支历史记录比特序列对应的程序执行跟踪的执行时间(执行时间估计值)形成以下式(1.2)。

TotalTime_2＝T1+T2+T5+T7+T2+T5+T6a+T8+T9+T9+T10+T12…(1.2)

(第一实施方式的效果)

通过第一实施方式算出的执行时间估计值具有与在步骤S102中算出的部分程序执行时间估计值相同高的精度。并且，在步骤S103中生成的分支历史记录比特序列与程序执行命令数相比明显少，因此能够在远远小于实际的程序执行时间的处理时间内算出执行时间估计。

另外，在步骤S102中估计部分程序的执行时间，即使是利用循环、条件分支命令等来多次执行相同部分程序那样的对象程序，也只要算出一次量的执行时间即可，因此与从开头起对对象程序进行执行时间估计的情况相比能够以短时间的处理完成该估计。

(第二实施方式)

图9是表示第二实施方式所涉及的执行时间估计装置的结构例的图。

在图9中，对与第一实施方式相同的要素附加相同的附图标记而省略说明。

执行时间估计装置1b(1)具有循环信息提取部21、程序执行历史记录信息生成部22以及估计算出后面所说明的第二种循环的执行时间的第二种循环执行时间估计算出部23。并且，执行时间估计装置1b除了具备第一实施方式中的上述部分程序执行序列以外还具备生成后面所说明的第二种循环执行序列的执行跟踪再生部14b、和执行时间估计算出部15b，该执行时间估计算出部15b根据部分程序执行序列、第二种循环以外的部分程序执行时间估计值和后述的第二种循环执行时间估计值来估计算出对象程序的执行时间。

循环信息提取部21具备具有与第一实施方式相同的功能的程序分割部11和部分程序执行时间估计算出部12。并且，循环信息提取部21具有第一种和第二种循环辨别处理部211，该第一种和第二种循环辨别处理部211根据对象程序来辨别后面所说明的第一种循环和第二种循环，将第二种循环ID追加到部分程序表，将辨别的结果生成的第一种循环信息(后面说明)发送到第一种循环聚合部212，或者将第二种循环信息(后面说明)发送到第二种循环次数数据序列生成部221。另外，循环信息提取部21具有第一种循环聚合部212，该第一种循环聚合部212根据第一种循环信息，在部分程序表中进行第一种循环的聚合处理，将第一种循环聚合后的、追加了第二种循环ID后的部分程序表发送到执行时间估计算出部15b。

程序执行历史记录信息生成部22具有第二种循环ID、生成作为与第二种循环的反复进行次数成对的信息的序列的第二种循环次数数据序列的第二种循环次数数据序列生成部221以及生成第二种循环以外的部分程序的分支历史记录比特序列的分支历史记录信息生成部13b。

此外，以规定函数覆盖对象程序(源程序)的一部分，程序执行历史记录信息生成部22执行所覆盖的对象程序，由此实现第二种循环次数序列生成部221和分支历史记录信息生成部13b(参照图15来后面详细说明)。

此外，将存储于图2的存储装置170等中的执行时间估计程序加载到RAM 153中而由CPU 151执行，从而实现图9示出的各部11、12、13b、14b、15b、21、22、23、211、212、221。

首先，在说明具体的处理之前，参照图4的对象程序来说明第二实施方式中的处理的原理以及概要。

在以下示出的条件Z1～Z3满足Z1∩(Z2∪Z3)时，循环(反复进行处理)内的条件分支命令不保存该部分的分支历史记录信息而能够进行正确的执行跟踪再生。

条件Z1：在循环内部除了循环继续条件命令以外不包含if-else分支命令等条件分支命令。在此，循环继续条件命令是指是否跳出循环的条件分支命令。

条件Z2：循环的反复进行次数为常数次。

条件Z3：循环的反复进行次数为固定次。

在此，“循环的反复进行次数为常数次”是指确定的循环次数在整个对象程序全体中不变(常数)的情况。

另外，“循环的反复进行次数为固定次”是指特定的循环次数利用变量进行规定而在循环内不变但是在循环外有可能发生变化的情况。

在图4示出的对象程序的例子中，对应于“main”函数的“循环1”的循环(下面，将对应于“循环n”的“循环”记载为“循环n”)没有满足条件Z1(在循环内存在if-else分支命令)。此外，“func1”函数的“循环2”满足条件Z1。

在“循环2”的“D＝i＜M”中“M”为常数值的情况下，即“M”在对象程序整体中不变的情况下，条件Z2成立。

在“循环2”的“D＝i＜M”中处于即使“M”为变量值也在循环处理中不变化而固定的情况(固定次数：循环不变)的情况下，条件Z3成立。

特别是，条件Z3往往被用于如图像处理那样将图像的高度、宽度作为变量而提供的情况，存在很多这些变量与循环的反复数直接对应的情况。

当参照从图4示出的对象程序导出的分支历史记录比特序列(参照第一实施方式)时，“循环2”的循环次数为两次(参照条件变量“D”)。

此时在“循环2”中Z1∩Z2成立的情况下(下面记载为“第一种循环”)，M＝2为常数，显然在图5示出的部分程序表中到达“branch(D)”的状态下必须执行“D(1)→[T9]→D(1)→[T9]→D(0)→[T10]→E”。因而，循环2的执行时间能够在式(2.1)中示出。因此，分支历史记录信息生成部13b在分支历史记录比特序列中不需要记录与“branch(D)”有关的比特序列。

T_L2＝T9×2+T10…(2.1)

另外，在Z1∩Z3成立的情况下(下面记载为“第二种循环”)，例如在执行“循环2”之前求得“M＝2”的值、且变量“M”在“循环2”的执行中不变化的情况下，第二种循环次数数据序列生成部221将第二种循环ID(由第一种和第二种循环辨别处理部211发出的ID)与此时的第二种循环次数作为第二种循环次数数据序列而进行保存。然后，第二种循环执行时间估计算出部23根据该第二种循环次数数据序列例如用式(2.2)来估计第二种循环的处理时间(后面说明详细处理)。

T_L2＝T9×M+T10…(2.2)

此时“M”为在第二种循环次数数据序列中记录的第二种循环次数。在这种情况下，也同样地，分支历史记录信息生成部13b在分支历史记录比特序列中不需要记录作为与第二种循环有关的条件分支命令的“branch(D)”的分支历史记录。

在上述两种情况中，不需要将循环内的分支历史记录信息记录到分支历史记录比特序列中，因此在存在多个满足这种条件的循环(第一种循环和第二种循环)的程序中，能够期望能够大幅减少分支历史记录比特序列长度。因而，第一种循环和第二种循环各自聚合为一个命令，能够从部分程序的程序分割边界点去除内部的条件分支命令(循环继续条件命令)。

接着，参照图9按照图10来说明第二实施方式所涉及的程序执行时间估计方法。

图10是表示第二实施方式所涉及的程序执行时间估计方法的处理的流程的流程图。

(循环信息提取处理)

接着，循环信息提取部21进行循环信息提取处理(S201)。循环信息提取部21将步骤S201的结果、即生成的第一种循环信息和第二种循环信息发送到程序执行历史记录信息生成部22。并且，循环信息提取部21将步骤S201的结果、即第一种循环聚合后的、被写入第二种循环ID的部分程序表发送到执行跟踪再生部14b、第二种循环执行时间估计算出部23以及执行时间估计算出部15b。后面说明第一种循环信息和第二种循环信息，第一种循环信息为对应于第一种循环的条件分支命令(循环继续条件命令)，第二种循环信息为第二种循环ID与部分程序ID成对的信息。

在此，参照图9按照图11记载循环信息提取处理的详细。

图11是表示第二实施方式所涉及的循环信息提取处理的流程的流程图。

首先，循环信息提取部21的程序分割部11进行程序分割处理(S101)，部分程序执行时间估计算出部12进行部分程序执行时间估计算出处理(S102)。这些处理是与上述实施方式相同的处理，因此附加相同的步骤编号而省略说明。

<第一种循环和第二种循环辨别处理>

接着，循环信息提取部21的第一种和第二种循环辨别处理部211进行第一种循环和第二种循环辨别处理、即辨别在步骤S101、S102中生成的部分程序表中的循环为第一种循环还是第二种循环(S2011)。

在此，参照图12来说明第一种循环和第二种循环辨别处理。

图12是与某一个对象程序中的循环有关的图，(a)是某一个循环的结构示意图，(b)是表示从具有(a)示出的结构的循环生成的部分程序的结构的例子的表。

在此，图12的(b)中的“WW”和“YY”表示适当的处理。条件“X”表示是否继续循环的条件(循环继续条件命令)。另外，“c1”、“c2”、“c3”、“c4”以及“c5”分别表示处理代码，是不包含条件分支命令、连接点(通过goto语句、循环等能够从多个代码位置到达的代码地点)、函数调用命令的代码块。在此，代码块“c1”、“c2”、“c3”、“c4”以及“c5”也可以是不包含任何命令的“空”的代码块。此外，“ID”、部分程序开始命令、部分程序终止命令与上述实施方式中的部分程序表中的命令相同，因此省略说明。

在图12的(b)中的部分程序“14”中部分程序开始命令与部分程序终止命令成为相同“branch(X)”，但是这些是循环，因此指相同条件分支命令反复进行的情况。即，第一种和第二种循环辨别处理部211能够根据在“部分程序开始命令”与“部分程序终止命令”中是否存在相同的条件分支命令来识别循环。

在此，第一种和第二种循环辨别处理部211通过辨别后面所说明的输入依赖变量是后面所说明的循环不变变量还是归纳变量来辨别第一种循环和第二种循环。

在此，输入依赖变量例如在循环继续条件命令为“D＝i＜M”时“i”和“M”为输入依赖变量。

另外，循环不变变量在以图12的(a)中的对象程序的结构为例进行说明时，是指值不被循环内的代码“c2”和“c4”变更的变量。也就是说，在针对上述变量“M”的“M＝…”这种对于M的代入式不存在于代码“c2”和“c4”中时，第一种和第二种循环辨别处理部211将变量“M”辨别为循环不变变量。

并且，归纳变量为以下变量：变量在循环的开始前被初始化为常数值，并且仅“变量＝变量op(常数值)”(op：两项计算符)的形式的代入式存在于循环内的代码。例如，作为存在图12的(a)的循环中使用的变量“g”(在图12中未图示)，当以该变量“g”为例进行说明时，在循环开始前的代码“c1”中，该“g”被初始化为常数值，关于变量“g”仅“g＝gop(常数值)”的形式的代入式存在于循环内的代码“c2”和“c4”时，第一种和第二种循环辨别处理部211将变量“g”辨别为归纳变量。

输入依赖变量、循环不变变量以及归纳变量是通过由第一种和第二种循环辨别处理部211检索对象程序来获取的变量。

并且，第一种和第二种循环辨别处理部211在循环内的输入依赖变量全部为“归纳变量”或者“常数”时将对应的循环辨别为第一种循环，在循环内的输入依赖变量全部为“归纳变量”或者“循环不变变量”时将对应的循环辨别为第二种循环。此外，不与第一种循环或者第二种循环对应的循环被表现为部分程序的反复。

(第二种循环ID追加处理)

返回到图11，在步骤S2011之后，第一种和第二种循环辨别处理部211进行第二种循环ID追加处理、即对在步骤S2011中辨别为第二种循环的部分程序发布第二种循环ID，并对部分程序表的对应的部分程序的第二种循环ID的字段追加发布的第二种循环ID(S2012)。此外，第一种和第二种循环辨别处理部211将与第二种循环以外的部分程序有关的循环ID号设为“0”。该阶段的部分程序表例如为图13示出的表。

在此，图13是在第二实施方式中使用的部分程序表的例子。

图13中的部分程序表与图5示出的部分程序表不同点是具有用于保存第二种循环ID的字段这点。

如上所述，在第二种循环ID的字段中，在对应于第二种循环的位置保存第二种循环ID，在除此以外的部分程序(包括第一种循环)中保存“0”。

此外，第一种和第二种循环辨别处理部211(图9)将作为对应于第一种循环的条件分支命令的第一种循环信息发送到第一种循环聚合部212(图9)和分支历史记录信息生成部13b(图9)，将作为第二种循环ID与部分程序ID成对的信息的第二种循环信息发送到第二种循环次数数据序列生成部221。

<第一种循环聚合处理>

返回到图11，在步骤S2012之后，如图14所示，循环信息提取部21的第一种循环聚合部212聚合从第一种和第二种循环辨别处理部211发送过来的部分程序表中的第一种循环(S2013)。此外，在第二～第六实施方式中，“聚合”是指将部分程序表中的两个行根据规定的规则来集中为一个行。

图14是用于说明第一种循环的聚合的图，(a)是聚合前的部分程序表，(b)是聚合后的部分程序表。此外，图14示出的部分程序表具有与图13示出的部分程序表相同的结构，为了说明第一种循环的聚合，将“第二种循环ID”的字段全部设为“0”。

参照图14的(a)，部分程序“9”的“部分程序开始命令”与“部分程序终止命令”具有相同的条件命令。如上所述，“部分程序开始命令”与“部分程序终止命令”为相同的条件命令的部分程序表示形成循环的情况。因而，可知部分程序“9”为循环，并且根据第一种循环信息中的条件分支命令(在此，branch(D))可知是第一种循环。

因此，第一种循环聚合部222将图14的(a)中的部分程序“9”与“部分程序开始命令”具有相同的条件分支命令的部分程序“10”聚合为图14的(b)中的部分程序“9’”。即，程序执行历史记录信息生成部22将图14的(a)中的部分程序“9”中的部分程序终止命令“branch(D)”设为“Reduce_L2”，将部分程序“10”中的部分程序开始命令“branch(D)[F]”设为Reduce_L2。并且，按照式(2.1)的值保存聚合的部分程序ID“9’”的执行时间估计值。

第一种循环聚合部212将在步骤S2012中追加第二种循环ID并且在步骤S2013中进行了第一种循环的聚合的部分程序表发送到执行跟踪再生部14和执行时间估计算出部15。

(程序执行历史记录信息生成处理)

返回到图10，步骤S201之后，使用通过输入部156(图2)输入的对象程序以及从循环信息提取部21输入的第一种循环信息和第二种循环信息来进行程序执行历史记录信息生成处理(S202)。

在此，参照图9按照图15来说明程序执行历史记录信息生成处理。

图15是表示第二实施方式所涉及的程序执行历史记录信息生成处理的流程的流程图。

<对象程序(源程序)覆盖处理>

首先，程序执行历史记录信息生成部22进行图16示出的对象程序的覆盖处理(S2021)。在此，图16是表示用于生成第二种循环次数数据序列的对象程序的覆盖例的图，(a)示出覆盖前、(b)示出覆盖后、(c)示出生成第二种循环次数数据序列和分支历史记录比特序列的函数。

即，程序执行历史记录信息生成部22如图16的(b)的下划线所示那样对图16的(a)中的第二种循环的循环继续条件命令(下划线部)进行覆盖。图16的(b)的下划线的函数为图16的(c)示出的函数。

并且，图16的(c)示出的函数具有以下功能：对第二种循环的循环次数进行计数，所计数的第二种循环次数已经被记录在第二种循环次数数据序列中，当与具有相同第二种循环ID的近前的第二种循环次数一致时(即，在循环次数没有变化时)，不将所计数的循环次数写入到第二种循环次数数据序列(后面详细进行说明)。

在步骤S2031之后，程序执行历史记录信息生成部22执行图16的(b)所示那样覆盖的对象程序(S2032)，由此图9示出的第二种循环次数数据序列生成部221启动，所启动的第二种循环次数数据序列生成部221生成第二种循环次数数据序列。

在此，将成为对象的第二种循环反复进行的次数、即第二种循环反复次数作为例如[01，250]等那样的、与循环ID(“01”)成对的信息的序列记录到第二种循环次数数据序列中。[01，250]表示具有第二种循环ID“01”的第二种循环反复进行250次的情况。

另外，第二种循环次数数据序列中的第二种循环的反复次数的初始值为“-1”。将反复次数的初始值设为“-1”的理由如下：还没有对循环的反复次数进行计数，因此先临时放入不可能的值。

第二种循环次数数据序列生成的实际

在此，说明第二种循环次数数据序列生成部221中的第二种循环次数数据序列生成的具体例。

首先，作为前提设为三个第二种循环(第二种循环ID：“01”、“02”、“03”)存在于对象程序中。

然后，首先，设为第二种循环次数数据序列生成部221生成[01，5]、[02，8]、[02，8]、[01，5]、[03，10]、[03，10]、[01，5]、[02，4]、[03，20]、[01，5]、[02，8]这种第二种循环数据序列。在此，将构成第二种循环次数数据序列的数据([01，5]等)记载为第二种循环次数数据。各第二种循环次数数据所表示的意义是[第二种循环ID、第二种循环次数]。

接着，第二种循环次数数据序列生成部221通过对第二种循环次数数据序列进行如下的处理，来减少第二种循环次数数据序列的冗余性，从而减少数据量。也就是说，第二种循环次数数据序列生成部221在第二种循环次数数据序列中对相同的第二种循环ID进行处理，即在登记到近前的第二种循环次数数据序列中的第二种循环次数与所计数的第二种循环次数的值一致时(即，在第二种循环次数没有变化时)，不将所计数的第二种循环次数数据写入到第二种循环次数数据序列。此外，在此为了便于说明，使用从第二种循环次数数据序列删除对应的第二种循环次数数据的过程来进行说明。

当以上述第二种循环次数数据序列为例进行说明时，形成以下那样的序列。

[01，5]、[02，8]、{[02，8]、[01，5]}、[03，10]、{[03，10]、[01，5]}、[02，4]、[03，20]、{[01，5]}、[02，8]

在此，以中括号包围的第二种循环次数数据为被删除的数据。例如，关于第三个第二种循环次数数据[02，8]，由于第二个第二种循环次数数据(第二种循环ID为“02”之前与它最近的第二种循环次数数据)与其第二种循环次数一致，因此将其删除。

另外，关于第四个第二种循环次数数据[01，5]，由于第一个第二种循环次数数据(第二种循环ID为“05”之前与它最近的的第二种循环次数数据)与其第二种循环次数一致，因此将其删除。

此外，关于最后的第二种循环次数数据[02，8]，由于其第二种循环次数与第二种循环ID为“02”之前与它最近的第二种循环次数数据[02，2](第八个数据)不同，因此不将其删除。

通过这种处理，第二种循环次数数据序列生成部221所输出的第二种循环次数数据序列最终形成如下的序列。

[01，5]、[02，8]、[03，10]、[02，4]、[03，20]、[02，8]

此外，如上所述，在此，为了说明，第二种循环次数数据序列生成部221生成一次第二种循环次数数据序列之后，删除之前与它最近的第二种循环ID相同且第二种循环次数一致的第二种循环次数数据，但是在生成第二种循环次数数据序列过程中，第二种循环次数数据序列生成部221是进行以下操作的：判断是否存在之前与它最近的第二种循环ID相同的第二种循环次数，在存在的情况下，不写入到第二种循环次数数据序列。

并且，图16的(c)示出的函数除了具有生成第二种循环次数数据序列的功能以外还具有生成分支历史记录比特的功能。此时，图16的(c)示出的函数还具有不将第二种循环的循环继续条件命令的分支历史记录比特作为分支历史记录比特而记录的功能。即，程序执行历史记录信息生成部22执行图16的(b)示出的覆盖的对象程序，由此将图9的分支历史记录信息生成部13b也启动。被启动的分支历史记录信息生成部13b生成除了第二种循环以外的分支历史记录比特序列。也就是说，分支历史记录信息生成部13b所生成的分支历史记录比特序列由于省略了与第二种循环有关的比特，因此形成比特数较少的分支历史记录比特序列。并且，利用图16的(c)示出的函数启动的分支历史记录信息生成部13b生成省略了从第一种和第二种循环辨别处理部211发送过来的第一种循环信息所含的相当于条件分支命令的比特(与第一种循环有关的比特)的分支历史记录比特序列。

步骤S202的结果是，程序执行历史记录信息生成部22将所生成的分支历史记录比特序列发送到执行跟踪再生部14b，将第二种循环次数数据序列发送到第二种循环执行时间估计算出部23。

(执行跟踪再生处理)

返回到图10的说明，在步骤S202之后，执行跟踪再生部14b根据从循环信息提取部21获取到的部分程序表以及从分支历史记录信息生成部13b获取到的分支历史记录比特序列来进行执行跟踪再生处理(S104b)，生成第二种循环执行序列和部分程序执行序列。

下面，说明由第二实施方式中的执行跟踪再生部14b进行的第二种循环执行序列生成处理。在第二实施方式中的执行跟踪再生处理中除了生成部分程序执行序列以外还生成第二种循环执行序列。

首先，执行跟踪再生部14b一边读出在程序执行历史记录信息生成部22中生成的分支历史记录比特序列一边通过与上述实施方式相同的方法生成部分程序执行序列。此外，如上所述，实际上执行跟踪再生部14b与上述实施方式相同地进行以下动作：一边生成部分程序执行序列一边将部分程序执行时间估计值依次发送到执行时间估计算出部15b。

此时，执行跟踪再生部14b从上起依次参照在循环信息提取部21中生成的部分程序表(图13)，提取在第二种循环ID的字段中存在1以上的值的部分程序(即，在开始命令中具有第二种循环的循环继续条件命令的部分程序)，将所提取的第二种循环ID追加到第二种循环执行序列的末端。执行跟踪再生部14b不将表示第二种循环的部分程序的执行时间估计值追加到部分程序执行序列(即，不发送到执行时间估计算出部15b)，而是自动地转移到第二种循环结束之后到达的部分程序，将该部分程序追加到部分程序执行序列。

参照图13的例子，说明第二实施方式所涉及的执行跟踪再生处理的具体过程。此外，部分程序执行序列与第一实施方式相同，因此省略说明。

例如，执行跟踪再生部14b以与第一实施方式的步骤S 104相同的过程来从上起依次参照部分程序表。然后，在图13的例子中到达部分程序“9”的时刻，执行跟踪再生部14b将对应的第二种循环ID“02”追加到“第二种循环执行序列”的末端，转移到第二种循环ID“02”结束之后到达的部分程序“11”或者“12”。根据从分支历史记录比特序列读取到的下一个分支历史记录比特来辨别转移到部分程序“11”还是“12”。

具体地说，执行跟踪再生部14b在第二种循环ID到达作为“02”的部分程序“9”的时刻转移到部分程序表中的部分程序“9”结束的条件(即，转移到部分程序“10”(branch(D)[F]))。此时，执行跟踪再生部14b在第二种循环执行序列的末端追加部分程序“9”的第二种循环ID。此外，在如部分程序“9”那样部分程序开始命令中的条件与部分程序终止命令中的条件相同的情况下，如上所述那样该部分程序表示形成循环的情况。然后，执行跟踪再生部14b转移到具有部分程序“10”的部分程序终止命令(branch(E))作为部分程序开始命令的部分程序“11”或者“12”。执行跟踪再生部14b根据分支历史记录比特序列来决定转移到部分程序“11”和“12”中的哪一个。

通过这样的处理，能够得到下面所记载的效果。如果设为分支历史记录信息生成部13b不识别第二种循环而生成了分支历史记录比特序列，则相当于该第二种循环的比特序列成为“111…0…”。在生成了这样的分支历史记录比特序列的情况下，执行跟踪再生部14b反复转移到部分程序“9”。根据第二实施方式的执行跟踪再生处理(S104b)，执行跟踪再生部14b能够通过省略与相当于第二种循环的部分程序(在此，部分程序“9”)的循环次数相当的转移，来实现处理的高速化。

(第二种循环执行时间估计算出处理)

然后，返回到图10，在步骤S104b之后，第二种循环执行时间估计算出部23根据从第二种循环次数数据序列生成部221获取到的第二种循环次数数据序列、从执行跟踪再生部14b获取到的第二种循环执行序列以及从循环信息提取部21输出的部分程序表的部分程序执行时间估计值来进行第二种循环执行时间估计算出处理(S203)。此时，参照第二种循环次数数据序列的第二种循环ID来从部分程序表提取对应的第二种循环的部分程序执行时间估计值。此外，第二种循环执行时间估计算出处理为与步骤S105b的程序执行时间估计算出处理并行地进行的处理。

在此，具体地说明第二种循环执行时间估计算出处理。

首先，第二种循环执行时间估计算出部23从开头起依次读取从第二种循环次数数据序列生成部221获取到的第二种循环次数数据序列。在此，下面将此时读取的第二种循环次数数据设为“当前参照第二种循环次数数据”。

接着，第二种循环执行时间估计算出部23从开头起依次读取由执行跟踪再生部14b生成的第二种循环执行序列(第二种循环ID号的执行顺序序列)。在此，将此时读取的第二种循环执行序列中的第二种循环ID号设为循环执行序列中的“当前第二种循环ID”。

第二种循环执行时间估计算出部23在每次算出第二种循环执行序列中的各循环的执行时间时，“当前第二种循环ID”移动到下一个第二种循环ID，但是在“当前参照第二种循环次数数据”移动到下一个第二种循环次数数据的情况下，存在不移动而不变化的情况。具体地说，在“当前第二种循环ID”与“当前参照第二种循环次数数据”的第二种循环ID一致的情况下，移动到下一个第二种循环次数数据，但是在不一致的情况下不移动。后面参照图17来说明具体的处理。

在“当前参照第二种循环次数数据”的第二种循环ID与“当前第二种循环ID”一致的情况下，第二种循环执行时间估计算出部23使用部分程序表中的部分程序执行时间估计值来用式(2.2)算出第二种循环执行时间估计值，将该第二种循环执行时间估计值与对应的第二种循环ID作为成对的信息保存到未图示的第二种循环执行时间表，将所算出的第二种循环执行时间估计值发送到执行时间估计算出部15b。在此，第二种循环执行时间表是指用于将所算出的第二种循环执行时间临时保存到RAM153(图2)等的表。当在图13的例子中将第二种循环次数设为“两次”时，第二种循环执行时间估计算出部23将第二种循环执行时间估计值计算为T9×2+T10。

在“当前参照第二种循环次数数据”的第二种循环ID与“当前第二种循环ID”的第二种循环ID不一致的情况下，第二种循环执行时间估计算出部23将记录在“第二种循环执行时间表”中的值设为第二种循环执行时间。

之后，第二种循环执行时间估计算出部23后移一个“当前参照循环次数数据”的第二种循环次数数据序列内的参照位置、即第二种循环执行时间估计算出部23在第二种循环次数数据序列中将“当前参照循环次数数据”的下一个第二种循环次数数据作为当前参照循环次数数据而读取，同样地算出第二种循环执行时间估计值。然后，第二种循环执行时间估计算出部23反复进行第二种循环执行时间估计值的算出处理直到读取所有第二种循环次数数据序列。下面，示出第二种循环执行时间估计算出处理的具体例。

第二种循环执行时间估计算出处理的实际

接着，参照图17来具体地说明第二种循环执行时间估计算出部23(图9)的处理。

首先，从第二种循环次数数据序列生成部221(图9)对第二种循环执行时间估计算出部23输入上述第二种循环次数数据序列[01，5]、[02，8]、[03，10]、[02，4]、[03，20]、[02，8]，从执行跟踪再生部14b(图9)对第二种循环执行时间估计算出部23输入第二种循环执行序列“01，02，02，01，03，03，01，02，03，01，02”。

在此，在第二种循环次数数据序列中，在如上所述那样第二种循环ID之前最近的第二种循环次数数据之间第二种循环次数相同的情况下，进行不写入到第二种循环次数数据序列的处理，但是在第二种循环执行序列中，不进行这样的处理。因而，第二种循环次数数据序列与第二种循环执行序列中的第二种循环ID的顺序产生偏差。

因此，第二种循环执行时间估计算出部23通过进行图17示出的处理来算出第二种循环执行时间估计值。

在图17中从左起依次形成当前第二种循环ID、当前参照第二种循环次数数据、判断、第二种循环执行时间估计值以及下一个当前参照第二种循环次数数据。在此，判断表示当前第二种循环ID与当前参照第二种循环次数数据中的第二种循环ID是否一致。

首先，说明行601中的一系列处理，第二种循环执行时间估计算出部23获取第二种循环执行序列“01，02，02，01，03，03，01，02，03，01，02”中的开头的第二种循环ID“01”，将该第二种循环ID“01”设为当前第二种循环ID。并且，第二种循环执行时间估计算出部23获取第二种循环次数数据序列[01，5]、[02，8]、[03，10]、[02，4]、[03，20]、[02，8]中的开头的第二种循环次数数据[01，5]，将该第二种循环次数数据[01，5]设为当前参照第二种循环次数数据。

接着，当前参照第二种循环次数数据中的第二种循环ID“01”与当前第二种循环ID“01”一致(判断的字段)，因此，第二种循环执行时间估计算出部23使用第二种循环次数数据[01，5]的第二种循环次数“5”以及部分程序表中的第二种循环的部分程序执行时间估计值来算出第二种循环执行时间估计值“5×t1”。在此，“t1”是第二种循环ID“01”的部分程序执行时间估计值。此外，如式(2.2)所示，原本需要使用对应的部分程序开始命令为“真”时的部分程序执行时间估计值以及部分程序开始命令为“假”时的部分程序执行时间估计值来计算第二种循环执行时间估计值，但是为了避免说明变得复杂，在图17中的说明中，设为M×t(M是第二种循环次数，t是对应的部分程序执行时间估计值)。

接着，第二种循环执行时间估计算出部23将所算出的第二种循环执行时间估计值“5×t1”与当前第二种循环ID“01”对应地写入到第二种循环执行时间表，同时将所算出的第二种循环执行时间估计值“5×t1”发送到执行时间估计算出部15b(图9)。执行时间估计算出部15b将从第二种循环执行时间估计算出部23发送过来的第二种循环执行时间估计值按发送的顺序进行相加。

然后，当前第二种循环ID“01”与当前参照第二种循环次数数据中的第二种循环ID一致，因此，第二种循环执行时间估计算出部23将下一个当前参照第二种循环次数数据更新为作为下一个第二种循环次数数据的[02，8]。

然后，第二种循环执行时间估计算出部23进行行602中的处理，但是该处理是将行601中的处理应用于第二种循环ID“02”的处理，因此省略说明。

在行602的处理中，当前第二种循环ID“02”与当前参照第二种循环次数数据中的第二种循环ID一致，因此，第二种循环执行时间估计算出部23将当前参照第二种循环次数数据更新为下一个第二种循环次数数据[03，10]。

在行603的处理中，第二种循环执行时间估计算出部23获取第二种循环执行序列“01，02，02，01，03，03，01，02，03，01，02”中的第三个第二种循环ID“02”，将该第三个第二种循环ID“02”设为当前第二种循环ID。

于是可知，当前第二种循环ID“02”与当前参照第二种循环次数数据[03，10]中的第二种循环ID“03”不一致，因此，在此进行着不写入到上述第二种循环次数数据的处理。

因此，第二种循环执行时间估计算出部23从第二种循环执行时间表读取最近的第二种循环ID“02”的第二种循环执行时间估计值(“8×t2”)，将所读取的第二种循环执行时间估计值(“8×t2”)发送到执行时间估计算出部15b。执行时间估计算出部15b将从第二种循环执行时间估计算出部23发送过来的第二种循环执行时间估计值按发送的顺序进行相加。

然后，当前第二种循环ID“02”与当前参照第二种循环次数数据[03，10]中的第二种循环ID“03”不一致，因此，第二种循环执行时间估计算出部23将当前第二种循环ID“02”更新为下一个第二种循环ID“01”，但是不更新当前参照第二种循环次数数据[03，10]。

行604中，当前第二种循环ID“01”与当前参照第二种循环次数数据[03，10]中的第二种循环ID“03”也不一致，因此，第二种循环执行时间估计算出部23对当前第二种循环ID“01”进行与行603相同的处理，由此从第二种循环执行时间表读取第二种循环执行时间估计值“5×t1”，将读取到的第二种循环执行时间估计值“5×t1”发送到执行时间估计算出部15b。

行605中，当前第二种循环ID“03”与当前参照第二种循环次数数据[03:10]中的第二种循环ID“03”一致，因此，第二种循环执行时间估计算出部23将与行601、602相同的处理应用到第二种循环ID“03”来进行该处理。然后，当前第二种循环ID“03”与当前参照第二种循环次数数据[03，10]中的第二种循环ID“03”一致，因此，第二种循环执行时间估计算出部23将当前参照第二种循环次数数据更新为下一个第二种循环次数数据[02，4]。

下面，对行606～607也进行相同的处理，第二种循环执行时间估计算出部23将第二种循环执行时间估计值发送到执行时间估计算出部15b。

(执行时间估计算出处理)

当结束步骤S203的处理时，执行时间估计算出部15b将从执行跟踪再生部14b发送过来的第二种循环次数序列以外的部分程序执行序列(实际上，按部分程序执行序列的顺序依次发送过来的部分程序执行时间估计值)与从第二种循环执行时间估计算出部23发送过来的第二种循环执行时间估计值依次进行相加，由此进行执行时间估计算出处理、即算出除了第二种循环以外的对象程序的执行时间的估计值(S105b)。第二种循环以外的执行时间估计算出处理与第一实施方式相同。另外，将从第二种循环执行时间估计算出部23依次发送过来的第二种循环执行时间估计值按发送的顺序进行相加来算出与第二种循环有关的执行时间。然后，执行时间估计算出部15b将相加后的第二种循环执行时间估计值与第二种循环以外的执行时间估计值进行相加，来算出最终的对象程序的执行时间。此外，执行时间估计算出部15b也可以将第二种循环次数序列以外的部分程序执行时间估计值与第二种循环执行时间估计值分开地进行相加，最后将两者进行相加，由此算出对象程序的执行时间的估计值。

(第二实施方式的效果)

程序所执行的总命令步骤数与分支历史记录比特序列长度具有较强的相关关系，例如与需要非常庞大的执行时间的对象程序对应的分支历史记录比特序列长度也变为庞大的长度，但是能够通过第二实施方式的步骤S201、步骤S202以及步骤S203的处理来缩减分支历史记录比特序列的长度。因而，能够记录需运转第一实施方式中不可能的长时间的程序的完全的执行历史记录。

此外，执行时间估计算出部15b中的计算量基本上与分支历史记录比特序列长度成正比。因而，第二实施方式中的分支历史记录比特序列长度的缩减与对象程序的执行时间估计算出处理中的计算时间的缩减直接关联。

即，即使是需运转长时间的对象程序，也能够缩减其对象程序的执行时间估计所需的时间。由此，在进行处理器结构的设计改进或专用编译程序的改进时，进行对象程序的执行时间估计不需要时间且能够高精度地算出，从而能够有效地对其设计改进效果进行评价。

另外，存在很多在某一个特定的第二种循环中、即使其循环的处理区间多次出现、第二种循环次数本身也不会变化的情况。在此，循环的处理区间是指在反复进行循环次数量之后到跳出循环为止。

例如在MPEG(Motion Picture Experts Group：运动图像专家组)等运动图像处理中，反复执行对于相同图像大小的处理(其中，图像大小数据不是常数值而是变量的情况较多)。根据第二实施方式，能够缩减这样的运动图像处理程序的执行时间估计所需的时间。

另外，对于有可能在循环外变更反复次数而难以作为一个部分程序而集中处理的循环(第二种循环)，也根据反复次数的序列等与其它部分程序分开地估计循环的执行时间，由此能够作为一个部分程序而进行处理，能够在较短的处理时间内估计程序的执行时间。

(第三实施方式：结构)

图18是表示第三实施方式所涉及的执行时间估计装置的结构例的图。

在图18中，对与上述其它实施方式相同的要素附加相同的附图标记而省略说明。

执行时间估计装置1c(1)具有算出if-else分支命令的分支概率(后述)的分支概率信息提取部31以及进行第三种循环(后述)的聚合的第三种循环聚合部32。另外，程序执行历史记录信息生成部22、执行跟踪再生部14b、执行时间估计算出部15b以及第二种循环执行时间估计算出部23具有与上述实施方式相同的功能，因此附加相同的附图标记而省略说明。此外，分支历史记录信息生成部13c除了具有在上述实施方式中说明的功能以外还具有以下功能：根据从多重if-else聚合部33发送过来的聚合信息(后述)，不将与由多重if-else聚合部33聚合的部分程序对应的分支历史记录比特追加到分支历史记录比特序列。

分支概率信息提取部31具有程序分割部11、部分程序执行时间估计算出部12、分支历史记录信息生成部13以及执行跟踪再生部14，它们的功能与上述实施方式的功能相同，因此附加相同的附图标记而省略说明。

另外，分支概率信息提取部31还具有条件变量分类概率算出部311，该条件变量分类概率算出部311算出各if-else分支命令为“真”和“假”的概率、即条件变量分类分支概率。

第三种循环聚合部32包含第一种和第二种循环辨别处理部211和第一种循环聚合部212，它们的功能与上述实施方式相同，因此省略说明。另外，第三种循环聚合部32还具有多重if-else聚合部33，该多重if-else聚合部33在部分程序表中进行if-else聚合处理(后述)，将if-else聚合后的部分程序发送到第一种和第二种循环辨别处理部211、第一种循环聚合部212，或者将作为聚合后的部分程序ID与对应的if-else分支命令成对的信息的聚合信息发送到分支历史记录信息生成部13c。

多重if-else聚合部33具有进行后面所说明的if-else聚合处理的if-else聚合部331、仍然进行后面所说明的相邻聚合处理的相邻聚合部332。

此外，将存储于图2的存储装置170等中的执行时间估计程序加载到RAM 153中而由CPU 151执行，由此实现图18示出的各部11、12、13、13c、14、14b、15b、22、23、31、32、33、211、212、221、311、331、332。

在说明具体的处理之前，说明第三实施方式中的处理的概要。

在对象程序中包含含有if-else分支命令的循环的情况下，该循环不满足第二实施方式中的上述条件Z1，因此即使循环次数为常数值(条件Z2)或者固定值(条件Z3)，也无法直接应用第二实施方式中的第一种循环聚合处理和第二种循环聚合处理。

但是，根据后面所说明的方法，能够计算各if-else分支命令的分支概率。如果使用该分支概率来计算if-else分支块整体的处理时间的统计性预测值，则产生能够应用第二实施方式中的循环的分支聚合处理的情况，从而能够增加第二实施方式中的分支历史记录比特序列长度的缩减效果。下面，将不满足条件Z 1而满足条件Z2或者条件Z3的循环记载为“第三种循环”。下面，说明具体的安装方法。

接着，参照图18按照图19来说明第三实施方式所涉及的程序执行时间估计方法。

图19是表示第三实施方式所涉及的程序执行时间估计方法的流程的流程图。

(分支概率信息提取处理)

首先，分支概率信息提取部31进行分支概率信息提取处理，即算出所有if-else分支命令的分支概率(S301)。

下面，参照图18按照图20来说明分支概率信息提取处理的具体的处理。

图20是表示第三实施方式所涉及的分支概率信息提取处理的流程的流程图。

首先，分支概率信息提取部31的程序分割部11进行程序分割(S101)，部分程序执行时间估计算出部12进行部分程序执行时间估计算出处理(S102)。然后，分支概率信息提取部31的分支历史记录信息生成部13进行分支历史记录信息生成处理(S103)，执行跟踪再生部14进行执行跟踪再生处理(S104)。步骤S101～S104的各处理与上述实施方式的处理相同，因此附加相同的步骤编号而省略详细说明。进行步骤S104的执行跟踪再生处理的结果是，生成部分程序执行序列。

在此，设为生成在第一实施方式中使用过的以下部分程序执行序列。

main:start→[T1]→A(1)→[T2]→B(1)→[T4]→A(1)→[T2]→B(0)→[T5]→C(1)→[T6a]→func1:start→[T8]→D(1)→[T9]→D(1)→[T9]→D(0)→[T10]→E(1)→[T11]→func1:end→[T6b]→A(0)→[T3]→main:end

<条件变量分类概率算出处理>

接着，条件变量分类概率算出部311按以下所记载的过程，进行条件变量分类概率算出处理，即根据所生成的部分程序执行序列来算出条件变量分类概率(S3011)。

首先，条件变量分类概率算出部311脱离部分程序执行序列中的各分支历史记录比特以及与该各分支历史记录比特对应的条件变量，生成如下的序列。

A(1)B(1)A(1)B(0)C(1)D(1)D(1)D(0)E(1)A(0)

然后，条件变量分类概率算出部311通过按条件变量分类来分开地乘以各条件变量的真假的频率来求出分支概率。

从上述部分程序执行序列的例子算出的条件变量分类分支概率(所有条件分支命令的分支概率)成为以下那样的序列。

p(A)＝2/3(“真”＝两次、“假”＝一次)

p(B)＝1/2(“真”＝一次、“假”＝一次)

p(C)＝1/1(“真”＝一次、“假”＝零次)

p(D)＝2/3(“真”＝两次、“假”＝一次)

p(E)＝1/1(“真”＝一次、“假”＝零次)

此外，除了这种结构以外也可以利用使用直接计算分支概率的现有方法的计算部来代替这种结构。

图21是表示包含第三种循环的其它例的对象程序的图，图22是表示从图21示出的对象程序生成的部分程序表的例子的图。

在此，当关注branch(J)与branch(H)时，将条件“J”为真(branch(J)“T”)的概率设为“p(J)”(0≤p(J)≤1)，将条件“H”为真(branch(H)“T”)的概率设为“p(H)”(0≤p(H)≤1)。将在此所示的概率称为条件变量分类分支概率信息。

(多重if-else聚合处理)

返回到图19，在步骤S301之后，多重if-else聚合部33进行多重if-else聚合处理(S302)。

在此，参照图18按照图23来说明多重if-else聚合处理的详细处理。

图23是表示第三实施方式所涉及的多重if-else聚合处理的流程的图。

在步骤S302中，对部分程序表中的所有if-else块执行步骤S3022和步骤S3023的处理(S3021)。

首先，当if-else聚合部331进行if-else聚合处理时(S3022)，相邻聚合部332进行相邻聚合处理(S3023)。然后，如上所述，多重if-else聚合部33对部分程序表中的所有if-else块反复进行步骤S3022和步骤S3023(S3024)。在此，if-else聚合处理为以下处理：使“部分程序开始命令”具有相同的if-else分支命令，并且将“部分程序终止命令”相同的行汇总为一个，由此聚合与if-else块有关的部分程序，这一点在后面详细进行说明。另外，相邻聚合处理为以下处理：对于部分程序终止命令不是if-else分支命令的部分程序，将其与具有该部分程序终止命令作为部分程序开始命令的其它部分程序进行聚合，由此聚合不包含if-else分支命令的相邻的两个部分程序。

多重if-else聚合部33将进行了这些聚合处理的部分程序表发送到第一种和第二种循环辨别处理部211、第一种循环聚合部212，同时将聚合的部分程序ID与对应的if-else分支命令成对的信息、即聚合信息发送到由程序执行历史记录信息生成部22启动的分支历史记录信息生成部13c。

根据图24的对象程序例以及与图24的对象程序例对应的图25的部分程序表，来具体地说明多重if-else聚合处理。

图24是表示包含第三种循环的对象程序的例子的图，图25是表示从图24示出的对象程序生成的部分程序表的例子的图。

此外，图25示出的部分程序表为由分支概率信息提取部31生成的表。

图24中的“循环3”为与第三种循环对应的循环(变量“K”为常数值或者在“循环3”的执行中不变)。当位于“循环3”内部的if-else分支命令中的条件“H”为真(T)的概率为h(＝p(H))(0≤h≤1)时，用以下式(3.1)来近似循环3的执行时间。在分支概率信息提取处理中能够通过上述方法来求出概率h。

T_L3＝(T21+h×T23+(1-h)×T24)×K+T22…(3.1)

式(3.1)是以下计算式：根据每次反复图24中的“循环3”时必须执行的部分程序的执行时间“T21”、条件“H”为“真”(概率h)时的执行时间“T23”以及条件“H”为“假”(概率1-h)时的执行时间“T24”的简单的概率加权之和(h×T23+(1-h)×T24)，来估计出执行一次“循环3”时的执行时间。如果循环次数“K”为常数值，则循环3的循环执行时间估计算出值在该阶段中能够作为常数值进行处理(即，执行时间估计装置1c在该处理之后将该循环作为第一种循环进行处理)，如果“K”在循环外为变量而在循环内为固定的值，则能够通过第二实施方式中的处理来算出循环执行时间估计值(即，执行时间估计装置1c在该处理之后将该循环作为第二种循环进行处理)。

具体地说，多重if-else聚合部33对if-else聚合处理和相邻聚合处理附加各自的条件(图22中的“H”、“J”)来进行处理。

首先，第三种循环聚合部32参照图22的部分程序表，检索具有相同条件分支命令作为部分程序开始命令、并且部分程序终止命令相同的部分程序。例如，if-else聚合部331检索在部分程序开始命令中具有条件“J”(branch(J))而在部分程序终止命令中具有条件“G”(branch(G))的部分程序“45”和“46”。此时，能够使用从分支概率信息提取部31获取的条件“J”的概率“j(＝p(J))”、部分程序“45”的估计执行时间“T45”以及部分程序ID“46”的执行时间“T46”，从而利用对式(3.1)应用条件“J”而得到的下一个式(3.2)来表示部分程序“45”和“46”的合计执行时间“T45’”。

T45’＝j×T45+(1-j)×T46…(3.2)

将使部分程序“45”和“46”聚合为“45’”的部分程序ID“45’”新保存到部分程序执行时间估计值一栏内，由此if-else聚合部331生成图26的(a)示出的对部分程序“45”和“46”进行if-else聚合处理而得到的部分程序表。

并且，如图26所示，if-else聚合部331同时将图22中部分程序终止命令为“branch(J)”的部分程序ID“43”也替换为“Reduce_B_J”，该“Reduce_B_J”表示是“branch(J)”已被聚合的命令。

在此，图26是进行了聚合处理的部分程序表的例子，(a)表示对“J”进行if-else聚合处理而得到的结果，(b)表示对(a)的结果进行相邻聚合处理而得到的结果，(c)表示对“H”进行if-else聚合处理而得到的结果，(d)表示对(c)的结果进行相邻聚合处理而得到的结果。

接着，相邻聚合部332进行相邻聚合处理。相邻聚合处理是指以下处理：将上述那样部分程序终止命令不是if-else分支命令的部分程序与作为部分程序开始命令而具有该部分程序终止命令的其它部分程序进行聚合。

具体地说，图26的(a)中的部分程序ID“43”的部分程序终止命令与部分程序ID“45’”的部分程序开始命令相同，因此第三种循环聚合部32对它们进行相邻聚合处理，由此形成图26的(b)的部分程序“43’”那样的形式。

下面，if-else聚合部331对条件“H”也同样地进行if-else聚合处理来生成图26的(c)示出的部分程序表，并且相邻聚合部332通过进行相邻聚合处理来生成图26的(d)示出的部分程序表。

在该时刻中，如果图21中的“循环6”的循环继续条件命令中的式“G＝i＜K”的“K”为常数次，则能够作为第一种循环对图26的(d)示出的部分程序表进行处理(能够聚合为第一种循环)，如果“K”为固定次，则能够作为第二种循环对图26的(d)示出的部分程序表进行处理(能够聚合为第二种循环)。

返回到图19，步骤S302之后的处理与上述说明的实施方式的处理相同，因此省略说明。此外，在步骤S202的程序执行历史记录信息生成处理中与第二实施方式同样地进行对象程序的覆盖，但此时插入的函数使用从多重if-else聚合部33发送过来的聚合信息、从第一种和第二种循环辨别处理部211发送过来的第一种循环信息以及第二种循环信息，以插入不输出与在步骤S 302、步骤S201中进行聚合而成的部分程序对应的分支历史记录比特的函数的形式来进行覆盖。

(第三实施方式的效果)

根据第三实施方式，使用各if-else分支命令的分支概率来计算if-else块整体的处理时间的统计预测值，由此能够加大第二实施方式中的分支历史记录比特序列长度的缩减效果。

(第四实施方式：结构)

图27是表示第四实施方式所涉及的执行时间估计装置的结构例的图。

执行时间估计装置1d(1)具有分支历史记录信息提取部31、执行跟踪再生部14c以及执行时间估计算出部15，但是它们的功能与上述实施方式相同，因此附加相同的附图标记来省略说明。

执行时间估计装置1d还具有多重循环聚合部41和分支历史记录信息生成部13d，其中，该多重循环聚合部41执行多重循环的聚合处理，该分支历史记录信息生成部13d生成在多重循环聚合部41中聚合的部分程序以外的分支历史记录比特序列。

多重循环聚合部41具有if-else聚合部331和相邻聚合部332，它们的功能与上述实施方式中的功能相同，因此附加相同的附图标记来省略说明。多重循环聚合部41还具有进行第四种循环(后述)的聚合处理的第四种循环聚合部411。此外，多重循环聚合部41具有以下功能：将作为所聚合的部分程序ID与对应的条件分支命令(所聚合的if-else分支命令、循环继续条件命令)成对的信息的聚合信息发送到分支历史记录信息生成部13d。

此外，将存储于图2的存储装置170等中的执行时间估计程序加载到RAM 153中而由CPU 151执行，由此实现图27示出的各部11、12、13、13d、14、15、31、41、311、331、332、411。

首先，在说明具体的处理之前说明第四实施方式中的处理的概要。

在记载于第三实施方式中的技术中，以该技术有时无法进行多重循环结构的聚合。

例如，如图28示出的对象程序的例子那样，有时在“循环4”内部包含作为第三种循环的“循环5”。

在此，图28是表示包含第四种循环(后述)的对象程序的例子的图。

在决定“循环5”的反复数的变量“Y”如图28示出的对象程序那样在近前的循环中进行更新(存在在执行“循环4”时“Y”发生变化的可能性)的情况下，为了估计“循环4”的执行时间，需要各个“Y”的值的信息(“循环5”的第二种循环次数数据序列)，因此以记载于第一～第三实施方式中的技术无法进行该双重循环整体的聚合。

但是，在以下示出的条件下(条件X1∩条件X2)，即使是多重循环，也能够正确地估计其“平均”执行时间。

条件X1：在循环内部恰好存在一个“循环继续条件命令”。

条件X2：在循环块内部不包含不满足条件X1的循环。

在此，“循环继续条件命令”是指决定是否继续循环处理的分支。例如在图28中，在“循环4”中条件“P”为唯一的循环继续条件命令，在“循环5”中条件“Q”为唯一的循环继续条件命令。

作为不适合条件X1的例子，例如可举出在具有结束条件的“for”循环、“while”循环的内部包含“break”语句或者“return”语句的情况。

另外，条件X2是指能够在循环内部包含满足条件X1的循环的情况，是用于处理多重循环结构的条件。下面，将满足(条件X1∩条件X2)的循环记载为“第四种循环”。

接着，参照图27按照图29来说明第四实施方式所涉及的程序执行时间估计方法。

图29是表示第四实施方式所涉及的程序执行时间估计方法的流程的流程图。

(概率信息提取处理)

首先，分支概率信息提取部31进行在第三实施方式3中说明的分支概率信息提取处理(S301)。步骤S301与第三实施方式中说明的处理相同，因此省略说明。接着，多重循环聚合部41进行多重循环聚合处理(S401)。

(多重循环聚合处理)

在此，参照图27按照图30来说明多重循环聚合处理的详细的处理。

图30是表示第四实施方式所涉及的多重循环聚合处理的流程的图。此外，在图30中对与上述实施方式相同的处理附加相同的步骤编号来省略说明。此外，多重循环聚合部41具有与上述第一种和第二种循环辨别处理部211(图9)相同的功能，由于具有该功能，因此多重循环聚合部41不对被辨别为第二种循环的循环进行以下步骤S4011～S4016的处理。

多重循环聚合部41对部分程序表中的所有多重循环执行步骤S3022～S4015的处理(S4011)。

首先，当多重循环聚合部41的if-else聚合部331进行if-else聚合处理时(S3022)，多重循环聚合部41的相邻聚合部332进行相邻聚合处理(S3023)。步骤S3022以及步骤S3023的处理与在第三实施方式中说明的处理相同。

接着，多重循环聚合部41从内侧的循环起依次对成为处理对象的循环块内的所有循环进行步骤S4013以及步骤S4014的处理(S4012)。

首先，多重循环聚合部41的第四种循环聚合部411进行第四种循环聚合处理来聚合上述说明的第四种循环(S4013)。然后，多重循环聚合部41的相邻聚合部332对进行了第四种聚合处理的部分程序表进行相邻聚合处理(S4014)。后面详细说明步骤S4013、S4014的处理。如上所述，多重循环聚合部41从内侧的循环起依次对循环块内的所有循环进行步骤S4013、S4014的处理(S4015)。

然后，当从内侧的循环起依次对循环块内的所有循环进行步骤S4013、S4014的处理结束时，多重循环聚合部41如上述那样对部分程序表中的所有多重循环反复进行步骤S3022～步骤S4015的处理(S4016)。

当处理结束时，多重循环聚合部41将作为所聚合的部分程序ID与对应的if-else分支命令或循环继续条件命令成对的信息的聚合信息发送到分支历史记录信息生成部13c。

多重循环聚合处理的实际

使用图28示出的对象程序以及图31示出的与图28的对象程序对应的部分程序表来说明多重循环聚合处理的实际。

如上所述，变量“X”在循环4的执行中不变，变量“Y”在循环5的执行中不变。

图32示出表示此时的条件“S”、“Q”以及“R”的分支概率的表。此时，能够用以下式(4.1)、(4.2)来计算图28的“循环4”以及“循环5”的平均反复次数。

C_L4mean＝s/(1-s)…(4.1)

C_L5mean＝q/(1-q)…(4.2)

在此，概率s(＝p(S))是条件“S”为“真”的概率，概率q(＝p(Q))是条件“Q”为“真”的概率。

式(4.1)以及式(4.2)的依据基于条件“P”以及“Q”为循环继续条件命令。即，在将某一循环的继续条件为“真”时的频率设为ST次而将继续条件为“假”时的频率设为SF次时，ST是循环在程序整体中反复进行的总次数，SF是在程序整体中从循环跳出的次数(即循环的执行次数(反复次数))，因此循环的平均反复次数为ST/SF，这与循环的继续条件的“真”概率与“假”概率之比相同。因而，通过使用图31示出的部分程序执行时间估计值的值，能够用以下式(4.3)以及式(4.4)来计算“循环4”的平均执行时间估计值T_L4(循环的平均执行时间)以及“循环5”的平均执行时间估计值T_L5。

T_L4＝(T31+T_L5mean)×C_L4mean…(4.3)

T_L5＝(T33+r×T35+(1-r)×T36)×C_L5mean…(4.4)

在此，概率r(＝p(R))是条件“R”为“真”的概率。

通过这种第四种循环平均执行时间计算处理，能够将包含if-else块的多重循环整体与单一的部分程序进行聚合。

多重循环聚合处理的实际

下面，参照图31～图34来进一步详细说明多重循环聚合处理(S401)。

首先，如上所述，多重循环聚合部41的if-else聚合部331进行上述if-else聚合处理，接着相邻聚合部332进行相邻聚合处理来进行部分程序表的聚合。

也就是说，if-else聚合部331从由分支概率信息提取部31获取到的图31的部分程序表的下面起依次检测“部分程序开始命令”中的条件变量相同的部分程序(在图31的例子中，首先检测出部分程序“35”、“36”)。接着，if-else聚合部331使用与第三实施方式中的上述方法相同的方法来进行部分程序“35”、“36”的if-else聚合处理，从而生成图33的(a)示出的部分程序表。

在此，图33是表示进行if-else聚合处理以及相邻聚合处理而得到的部分程序表的例子的图，(a)示出进行if-else聚合处理而得到的例子，(b)示出对(a)的结果进行相邻聚合处理而得到的例子。

此外，在图33的(a)中，部分程序“35’”的执行时间估计值是应用式(3.2)而得到的值。

并且，第四种循环聚合部411对在图33的(a)中“部分程序终止命令”与“部分程序开始命令”相同的部分程序“33”、“35’”进行相邻聚合处理，从而生成具有聚合部分程序“33”、“35’”而得到的部分程序“33’”的部分程序表(图33的(b))。

在此，当参照图33的(b)示出的部分程序表时，部分程序“33’”的“部分程序开始命令”与“部分程序终止命令”的条件变量相同，因此能够如上述第二实施方式中说明那样判断为循环。并且，部分程序“33’”、“34”(相当于图28的“循环5”)的部分程序开始命令的条件变量相同，因此可知能够进行循环聚合。

因此，第四种循环聚合部411使用与式(4.1)、(4.2)相同的方法求出与部分程序“33’”、“34”对应的“循环5”的平均反复次数，使用与式(4.3)、(4.4)相同的方法求出“循环5”的平均执行时间。然后，第四种循环聚合部411生成图34的(a)示出的部分程序表，该部分程序表在聚合部分程序“33’”、“34”而得到的部分程序“33””的执行时间估计值的字段中存储了所算出的“循环5”的平均执行时间。

在此，图34是对图33的(b)示出的部分程序表进行各聚合处理而得到的例子，(a)是对图33的(b)的结果进行第四种循环聚合处理而得到的例子，(b)是对(a)的结果进行相邻聚合处理而得到的例子，(c)是对(b)的结果进行第四种循环聚合处理而得到的例子，(d)是对(c)的结果进行相邻聚合处理而得到的例子。

并且，第四种循环聚合部411生成在图34的(a)中对部分程序“31”、“33””进行相邻聚合而得到的的部分程序表(图34的(b))。此外，图34的(a)中的“C_L5”是图28的“循环5”中的平均反复次数(式(4.2))。

同样地，第四种循环聚合部411也同样地对图34的(b)中的部分程序“31’”、“32”(相当于图28的“循环4”)进行循环聚合处理来生成图34的(c)示出的部分程序表。并且，第四种循环聚合部411对图34的(c)示出的部分程序表进行相邻聚合处理来生成图34的(d)示出的部分程序表。此外，图34的(c)中的“C_L4”是图28的“循环4”中的平均反复次数(式(4.1))。

通过上述处理，能够将图31示出的部分程序表聚合到图34的(d)示出的部分程序表。

步骤S401以后的处理除了使用步骤S301以及步骤S401中生成的信息以外与上述实施方式相同，因此省略说明(S103d、S104e、S105)。

这样，第四种循环聚合处理与第一种循环聚合处理相似，但是在第一种循环聚合处理中循环次数为常数这一点与在第四种循环聚合处理中循环次数为根据分支概率求出的平均反复次数这一点不同。

(第四实施方式的效果)

根据第四实施方式，通过由多重循环聚合部41进行的多重循环聚合，不生成“固定循环次数序列”就能够进一步增加分支历史记录比特序列长度的缩减效果，有时还能够将程序整体聚合为仅一个部分程序。

(第五实施方式)

图35是表示第五实施方式所涉及的执行时间估计装置的结构例的图。

执行时间估计装置1g(1)具有程序分割部11、部分程序执行时间估计算出部12、分支历史记录信息生成部13、13b、执行跟踪再生部14、14c以及执行时间估计算出部15，它们的功能与上述实施方式相同，因此附加相同的附图标记来省略说明。

执行时间估计装置1g还具有部分程序执行频率算出部81和函数聚合部82，其中，该部分程序执行频率算出部81算出作为部分程序执行序列中的各部分程序的出现频率的部分程序执行频率，该函数聚合部82根据部分程序执行时间估计值以及部分程序执行频率来进行函数的聚合处理。

也就是说，图35示出的执行时间估计装置1g具有以下结构：在图27示出的执行时间估计装置1d中，条件变量分类概率算出部311被替换为部分程序执行频率算出部81，多重循环聚合部41被替换为函数聚合部82。

另外，分支历史记录信息生成部13d具有以下功能：使用从函数聚合部82发送过来的聚合信息和对象程序来生成分支历史记录比特序列。

此外，将存储于图2的存储装置170等中的执行时间估计程序加载到RAM 153中而由CPU 151执行，由此实现图35示出的各部11、12、13、13d、14、14c、15、81、82。

首先，在说明具体的处理之前说明第五实施方式中的处理的概要。

在此，图36是示出在循环内包含“break”语句以及“return”语句的对象程序的例子的图。

例如，图36示出的对象程序在“循环10”内部存在“break”语句，在“循环11”内部存在“return”语句，因此两者都不是第四种循环，无法使用记载于上述实施方式中的技术来进行聚合。

针对这种对象程序，能够使用记载于本实施方式中的技术来聚合包含图36示出的“循环10”和“循环11”的函数。

接着，参照图35按照图37来说明第五实施方式所涉及的程序执行时间估计方法。

图37是表示第五实施方式所涉及的程序执行时间估计方法的流程的流程图。

在图37中，步骤S101～S105的处理与上述实施方式相同，因此省略说明。在步骤S104的执行跟踪再生处理之后，部分程序执行频率算出部81进行部分程序执行频率算出处理之后(S701)，函数聚合处理部72进行函数聚合处理(S702)。

然后，分支历史记录信息生成部13d根据从函数聚合部82获取到的聚合信息以及对象程序来进行生成分支历史记录比特序列的分支历史记录信息生成处理(S103e)。以后的处理与图29相同，因此省略说明。

部分程序执行频率算出处理的实际

接着，使用图38示出的与图36的对象程序对应的部分程序表来说明部分程序执行频率算出处理的实际。

图38是表示描述了部分程序执行频率的信息的部分程序表的例子的图。

在此，将“部分程序执行频率”定义为“部分程序执行序列”中的各部分程序的出现频率。也就是说，在部分程序的条件分支中根据“True”和“False”的发生频率算出部分程序执行频率。此外，开头为分支命令的部分程序的部分程序执行频率与第三实施方式中说明的分支概率的计算式的“真假的频率”相同。

条件U：True频率＝C61、False频率＝C62

条件V：True频率＝C63、False频率＝C64

条件W：True频率＝C66、False频率＝C67

条件Z：True频率＝C68、False频率＝C69

在此，“U”、“V”、“W”、“Z”是图36示出的对象程序中的分支条件。

图38示出将这样算出的部分程序执行频率与部分程序ID对应地存储到部分程序表的例子。

函数聚合处理

接着，使用图39示出的与图36的对象程序对应的部分程序表来说明函数聚合处理的实际。

图39是对图38示出的部分程序表进行聚合处理而得到的例子，(a)是进行了函数func4聚合处理的例子，(b)是进行了部分程序“63”的聚合处理的例子，(c)是聚合后的最终部分程序表的例子。

用以下式(5.1)来定义“部分程序全执行时间估计值”。

“部分程序全执行时间估计值”＝“部分程序执行时间估计值”ד部分程序执行频率”…(5.1)

于是，能够作为“函数内的部分程序全执行时间估计值的总和”来计算“函数的全执行时间估计值”。但是，在此设为“函数内的部分程序”不包含函数调用命令。例如，该时刻的main函数包含调用func4的部分程序，因此在这种状态下无法计算函数的全执行时间估计值。

在此，根据图38，函数func4的全执行时间估计值为以下式(5.2)。

Total_func4＝C65×T65+C66×T66+C67×T67+C68×T68+C69×T69…(5.2)

因而，能够用以下式(5.3)来计算“函数的平均执行时间估计值”。

“函数的平均执行时间估计值”＝“函数的全执行时间估计值”/“函数执行频率”…(5.3)

在此，“函数执行频率”是在开始命令中具备该函数的start的部分程序的执行频率。

例如，能够用以下式(5.4)来计算图36中的函数func4的平均执行时间估计值。

T_func4＝Total_func4/C65…(5.4)

在使用上述计算方法算出函数func4的平均执行时间估计值之后，部分程序表能够如聚合了函数func4的图39的(a)那样。

接着，当对包含所聚合的函数func4的函数调用的部分程序“63”进行聚合时，成为图39的(b)示出的部分程序表。

于是，main函数的平均执行时间估计值也能够使用同样的方法(式(5.5))来计算。

Total_main＝C60×T60+C61×T61+C62×T62+C63’×T63’+C64×T64…(5.5)

因而，最终，能够将部分程序表聚合为图39的(c)示出的表。

此外，main函数仅被调用一次，因此C60＝1。

函数聚合部82将聚合函数而得到的部分程序表(图39)发送到执行跟踪再生部14c。

另外，将关于与所聚合的函数对应的部分程序的信息(聚合信息)从函数聚合部82发送到分支历史记录信息生成部13e。分支历史记录信息生成部13d生成没有描述聚合信息所包含的部分程序的分支历史记录比特的分支历史记录比特序列(S103d)。

以后的处理与上述实施方式相同，因此省略说明。

(第五实施方式的效果)

根据第五实施方式，如果是不存在递归函数调用(例如在函数内调用自己的函数的情况等)的程序，则一定能够将全程序聚合为一个部分程序。

(第六实施方式)

首先，参照图40来说明第六实施方式中的方法。

图40是表示反复执行对象程序中的代码时的代码执行时间的示意图，(a)是应用了第二实施方式的例子，(b)是应用了第四实施方式的例子。

记载于第二实施方式至第四实施方式中的任一个技术都能够正确地估计对象程序整体的执行时间。因而，如果仅以正确地估计对象程序整体的执行时间为目的，则第四实施方式的安装可以说是分支历史记录比特序列长度的缩减效果最大，在所需的存储量、执行时间预测所需的计算时间方面最佳的。但是，在第四实施方式的安装中，在所有循环中采用平均处理时间，因此在程序执行中无法再现由复杂的条件分支引起的局部的执行时间的波动。

也就是说，在反复执行相同代码区域“A”的情况下，如图40的(a)所示，代码区域“A”的执行时间由于复杂的条件分支而在每次执行时产生波动。利用记载于第二实施方式的技术，能够完全再现该执行时间的波动，而反映到对象程序的执行时间估计值中。

与此相对，在记载于第四实施方式的技术中，如图40的(b)所示，使所有的处理平均化来算出执行时间估计值，因此无法完全再现局部的执行时间(局部执行时间)的波动。

该局部执行时间的平均化作用例如在以包含处理器和外部装置(存储器、设备驱动器、网络端口、多处理器系统中的处理器之间通信等)的系统整体的模拟为目的的情况下成为问题。也就是说，为了系统整体的模拟，系统总线上的数据流量、存储器存取流量的局部的定时的再现变得较重要，基于该观点，在仅应用第四实施方式的情况下，可以说局部定时再生精度较低。

在此，局部定时再生精度是指表示如图40的(a)所示那样实际上执行代码区域的情况下的波动程度的精度。如图40的(a)所示，如果能够准确地估计各执行时间的波动，则局部定时再生精度较高，相反地，如图40的(b)所示，在各执行时间的波动消失的情况下，局部定时再生精度较低。

在此，当基于局部定时再生精度的观点来整理第一实施方式至第四实施方式所涉及的技术时，在第一实施方式以及第二实施方式中，没有平均化作用(没有算出平均的处理)而能够严格地再生局部定时。

另外，在第三实施方式中，在估计第三种循环的执行时间时，由于进行平均化处理，因此局部定时再生精度降低一些。

并且，在第四实施方式中，由于在算出第四种循环的反复次数、估计执行时间时进行平均化处理，因此局部定时再生精度在第一～第四实施方式中变得最低。

在第六实施方式中，提供灵活应对模拟的目的(即局部定时再生精度的要求度)的差异的执行时间估计装置1e。

(结构)

图41是表示第六实施方式所涉及的执行时间估计装置的结构例的图。

如图41所示，执行时间估计装置1e(1)是将以下结构追加到兼备第一～第四实施方式的要素的结构的装置。此外，在图41中对与上述实施方式相同的结构要素附加相同的附图标记并省略其详细说明。

执行时间估计装置1e(1)具有分支概率信息提取部31、程序执行历史记录信息生成部22、执行跟踪再生部14b、第二种循环执行时间估计算出部23以及执行时间估计算出部15b，但是它们的功能与上述实施方式中的功能相同，因此附加相同的附图标记并省略说明。此外，第二种循环信息提取部21e具有上述实施方式中的第一种和第二种循环辨别处理211的功能中的第二种循环辨别功能以及第二种循环ID的发出功能。

另外，执行时间估计装置1e还具有if-else块执行时间偏重度算出部51、if-else聚合控制部52、循环执行时间偏重度算出部53以及第四种循环聚合控制部54。

if-else块执行时间偏重度算出部51具有算出if-else块执行时间偏重度的功能。后面说明if-else块执行时间偏重度。

if-else聚合控制部52将所算出的if-else块执行时间偏重度与通过输入部156(图2)输入的if-else偏重度阈值进行比较，输出if-else聚合禁止标志，该if-else聚合禁止标志为是否禁止if-else聚合部331e所进行的if-else聚合处理的信息。

循环执行时间偏重度算出部53具有算出循环执行时间偏重度的功能。后面说明循环执行时间偏重度。

第四种循环聚合控制部54将循环执行时间偏重度与通过输入部156(图2)输入的循环偏重度阈值进行比较，输出第四种循环聚合禁止标志，该第四种循环聚合禁止标志为是否禁止第四种循环聚合部411e所进行的第四种循环聚合处理的信息。

另外，多重循环聚合部41e的各部331e、332e、411e除了具有上述实施方式所述的功能以外还具有以下功能：根据从if-else聚合控制部52、第四种循环聚合控制部54发送过来的if-else聚合禁止标志、第四种循环聚合禁止标志来控制if-else聚合处理、多重循环聚合处理的执行。

此外，将存储于图2的存储装置170等中的执行时间估计程序加载到RAM 153中而由CPU 151执行，由此实现图41示出的各部14b、15b、22、23、31、41e、51、2、53、54、211e、331e、332e、411e。

接着，参照图41按照42来说明第六实施方式所涉及的程序执行时间估计方法。

图42是表示第六实施方式所涉及的程序执行时间估计方法的流程的流程图。此外，在图42中，对与上述实施方式相同的处理附加相同的步骤编号并省略说明。

首先，if-else块执行时间偏重度算出部51对所有if-else分支块进行if-else块执行时间偏重度算出处理(S501)。

在第三实施方式中，在if-else分支命令的真假各自的执行时间的偏差较大并且执行频率较高的情况下，在聚合这种if-else块时，由于执行时间的平均化作用而招致局部定时再生精度的降低。因此，将条件的真假的执行时间的绝对差与if-else块执行频率的积定义为if-else块的if-else块执行时间偏重度，由if-else块执行时间偏重度算出部51算出该if-else块执行时间偏重度。例如，if-else块执行时间偏重度算出部51使用条件“C”为“真”的情况下的执行时间“Tt”与“假”的执行时间“Tf”以及条件“C”的执行频率“Mc”来进行式(6.1)以及式(6.2)的计算，算出条件“C”的执行时间偏重度。执行时间偏重度越大局部定时再生精度变得越低。

g(C)＝|Tt-Tf|×Mc…(6.1)

在步骤S501之后，循环执行时间偏重度算出部53对所有循环进行算出循环执行时间偏重度的循环执行时间偏重度算出处理(S502)。

在第四实施方式所述的技术中，在聚合的循环的反复次数的偏差较大并且循环的执行频率较高且循环的平均执行时间较长的情况下，在聚合该循环时，招致局部定时再生精度的降低。因此，作为循环的反复次数的偏重度，将反复次数分布的方差与循环执行频率的积定义为循环的“循环执行时间偏重度”。例如，将循环L执行N次，在将各自的反复次数设为(L1、L2、…Ln)而将平均执行时间设为Tmean时，循环执行时间偏重度算出部53通过式(6.2)来算出循环L中的循环执行时间偏重度。循环执行时间偏重度越大局部定时再生精度变得越低。

[式1]

$g\left(L\right)={\sigma }^2\times N\times T_{\mathrm{Lmean}}=T_{\mathrm{Lmean}}\times \underset{n=1}{\overset{N}{\Sigma }}{(L_n-L_{\mathrm{mean}})}^2···\left(6.2\right)$

在式(6.2)中，σ2是循环L的反复次数的方差，Lmean是循环L的反复次数的平均值。

在步骤S502之后，分支概率信息提取部31进行分支概率信息提取处理(S301)。步骤S301的处理是与上述实施方式相同的处理，因此省略说明。

接着，if-else聚合控制部52按照所有if-else块中的每个if-else块来将根据局部定时再生精度的要求度来预先输入并设定的if-else偏重度阈值与在步骤S501中算出的if-else块偏重度进行比较。然后，在if-else块偏重度大于if-else偏重度阈值的情况下，if-else聚合控制部52进行if-else聚合禁止标志设定处理，即，将禁止对应的if-else聚合处理的标志(if-else聚合禁止标志)设定到部分程序表(S503)。在步骤S503中，在if-else块偏重度大于if-else偏重度阈值的情况下，在部分程序表的对应的聚合禁止标志的字段中登记“1”。另外，在步骤S503中，在if-else块偏重度小于等于if-else偏重度阈值的情况下，在部分程序表的对应的聚合禁止标志的字段中登记“0”。

在步骤S503之后，第四种循环聚合控制部54按照所有循环中的每个循环来将根据局部定时再生精度的要求度来预先输入并设定的循环偏重度阈值与在步骤S502中算出的循环执行时间偏重度进行比较。然后，在循环执行时间偏重度大于循环偏重度阈值的情况下，第四种循环聚合控制部54进行第四种循环聚合禁止标志设定处理，即、将禁止对应的第四种循环聚合处理的标志(第四种聚合禁止标志)设定到部分程序表(S504)。此外，在步骤S504中，第四种循环聚合控制部54具有与上述第一种和第二种循环辨别处理部211(图9)相同的功能，根据该功能，不对辨别为第二种循环的部分程序设定第四种聚合禁止标志。

在步骤S504中，在循环执行时间偏重度大于循环偏重度阈值的情况下，在部分程序表的对应的聚合禁止标志的字段中登记“1”。另外，在步骤S504中，在循环执行时间偏重度小于等于循环偏重度阈值的情况下，在部分程序表的对应的聚合禁止标志的字段中登记“0”。

图43是表示步骤S503和步骤S504中的处理结果、所生成的部分程序表的例子的图。

图43示出的部分程序表除了图5示出的部分程序表的结构以外，还设置有聚合禁止标志的字段。此外，第四种循环聚合控制部54在第四种循环聚合禁止标志设定处理(图42的步骤S504)结束之后在空栏的聚合禁止标志的字段中全部登记“0”。

接着，多重循环聚合部41e执行多重循环聚合处理(S505)。参照图44后面说明步骤S505的处理。

接着，参照图41按照图44来详细说明步骤S505的处理。

图44是表示第六实施方式所涉及的多重循环聚合处理的流程的流程图。此外，在图44中，对与上述实施方式相同的处理附加相同的步骤编号并省略说明。此外，多重循环聚合部41e具有与上述第一种和第二种循环辨别处理部211(图9)相同的功能，根据该功能，多重循环聚合部41e不对被辨别为第二种循环的循环进行以下步骤S5051～S4016的处理。

在步骤S3021之前，if-else聚合部331e参照部分程序表来判断与检索到的if-else块相当的部分程序的聚合禁止标志是否为“1”(S5051)。

在步骤S5051的判断结果是为“1”的情况下(S5051→Yes)，if-else聚合部331e和相邻聚合部332e不执行步骤S3022和步骤S3023(即，禁止if-else聚合处理)，处理进入到步骤S4012。

在步骤S5051的判断结果是不为“1”的情况下(S5051→No)，if-else聚合部331e和相邻聚合部332e执行步骤S3021和步骤S3022的处理。

然后，在步骤S4013之前，第四种循环聚合部411e参照部分程序表来判断与检索到的第四种循环相当的部分程序的聚合禁止标志是否为“1”(S5052)。

在步骤S5052的判断结果是为“1”的情况下(S5052→Yes)，第四种循环聚合部411e和相邻聚合部332e不执行步骤S4013和步骤S4014(即，禁止第四种循环聚合处理)，处理进入到步骤S4015。

在步骤S5052的判断结果是不为“1”的情况下(S5052→No)，第四种循环聚合部411e和相邻聚合部332e执行步骤S4013和步骤S4014的处理。

在步骤S401a之后，第二种循环信息提取部21e进行第二种循环信息提取处理(S201a)。在步骤S201a中进行以下处理：通过与图11的步骤S2011相同的过程进行第二种循环的辨别，通过与步骤S2012相同的过程将第二种循环ID登记到部分程序表，因此省略详细说明。

此外，在步骤S201a中，不进行与第一种循环有关的信息提取的处理的理由如下。第一循环的反复次数在整个对象程序中不变(常数次)，因此循环执行时间偏重度一定为“0”。也就是说，平均反复次数与实际的“常数次”反复次数一致。因而，第一种循环的聚合处理在第四种循环聚合处理中全部执行，因此原理上在步骤S201a的阶段中不存在未处理的第一种循环。

以下的处理分别与在上述实施方式中说明的处理相同，因此省略说明。

(第六实施方式的效果)

根据第六实施方式，在组合第二～第四实施方式的执行时间估计装置1e中，能够控制第三实施方式以及第四实施方式中的过剩的局部定时再生精度的消除。

(试验例)

接着，参照图45至图49，示出第一实施方式至第四实施方式以及第六实施方式中提供的执行时间估计装置1中的试验例。

在图45至图49的试验(模拟)中使用的计算机的配置为使用时钟数3.2GHz的CPU以及1GB的主存储器。

并且，将供给试验的测试程序(对象程序)设为例举小于500000的素数的素数计算程序(“Prime500000”)、英文文件的英文字出现频率计算程序(“Alphabet”)、要素数十个的排列组合例举程序(“Permutation”)以及像素尺寸800×600像素的JPEG编码程序(“JPEG”)。

图45是表示作为比较例使用命令集模拟器的试验结果的表。

所使用的命令集模拟器使用以循环精度估计32比特RISC(Reduced Instruction Set Computer：简化指令集计算机)处理器上的程序执行处理时间的命令集模拟器(其中，不包含缓存模拟)。

在图45中，针对上述四个对象程序，对象程序大小表示对象程序中的命令数，程序执行时间表示执行了对象程序时的总时钟周期数。命令集模拟器执行时间是在命令集模拟器中估计各对象程序的执行时间时所需的时间，单位为“秒钟”。命令集模拟器处理速度是估计各对象程序的执行时间时的处理速度，单位为“时钟周期/秒钟”。

图46是表示第一实施方式所涉及的试验结果的例子。

此外，在图46以及图47中，部分程序表大小表示部分程序表的行数。分支历史记录比特序列长度是分支历史记录比特序列的长度(比特数)。部分程序平均执行时间是各对象程序中的部分程序的执行时间(从分支命令至分支命令为止的平均执行时间)，通过对象程序执行时间/(分支历史记录比特序列长度+1)来算出。执行时间估计算出时间是算出对象程序的执行时间时所用的时间，单位为“秒钟”。对命令集模拟器速度提高比是通过(命令集模拟器中的执行时间/执行时间估计装置1中的执行时间)算出的值。

参照图45以及图46、特别是参照图46的对命令集模拟器速度提高比可知，第一实施方式所涉及的执行时间估计装置1a(图1)的执行时间与命令集模拟器的执行时间相比，能够估计16.16倍至45.75倍的高速的执行时间。另外，所得到的执行时间估计值在任一个对象程序的情况下都与命令集模拟器的结果完全一致。

图47是表示第四实施方式所涉及的试验结果的表。此外，在图48中说明第二实施方式以及第三实施方式所涉及的试验结果，因此在此省略。

在图47中，“Prime500000”的无法聚合的循环存在于多重循环的内侧，因此分支历史记录比特序列长度与第一实施方式(图46)相比几乎不会被缩减。“Alphabet”的最外壳循环以外的内部循环以外几乎都聚合了，因此分支历史记录比特序列长度与第一实施方式(图46)相比锐减。至于“Permutation”，因为所有循环和if-else块进行聚合，所以分支历史记录比特序列长度变为0。关于“JPEG”，也是几乎所有循环和if-else块进行聚合，因此分支历史记录比特序列长度与第一实施方式(图46)相比锐减。

另外，在图47中“Permutation”和“JPEG”中的对命令集模拟器速度提高比变为“-”，但是这指以小于时间测量精度(0.001秒钟)的时间结束了估计计算的情况。

在任一种情况下，对象程序的执行时间估计值都与命令集模拟器的结果完全一致。

图48是汇总第一～第四、第六实施方式所涉及的试验结果的表。

按照每个实施方式来描述使用“JPEG”作为对象程序时的部分程序表大小、分支历史记录比特序列长度(比特数)、程序执行时间估计计算时间(秒钟)以及对命令集模拟器比。此外，第六实施方式中的if-else偏重度阈值(图41)设定为“400.000”，循环偏重度阈值(图41)设定为“10.000”。

图48中的横轴的各项目与图46以及图47的纵轴相同，因此省略说明。从对命令集模拟器速度提高比的项目可知，在第三实施方式中示出命令集模拟器的最佳结果。

在第一～第四、第六实施方式中的任一个中对象程序的执行时间估计值都与命令集模拟器的结果完全一致，但是，如上所述，第一～第四、第六实施方式中的“局部定时再生精度”分别不同(未图示)。

图49是表示第一～第四、第六实施方式中的试验结果的图表。纵轴表示时钟周期数，横轴表示时间(秒钟)。

图49是以下的图表：为了评价“局部定时再生精度”，选择一个在“JPEG”的程序内部反复调用的函数，记录每调用该函数100次时的时刻，将所记录的时刻的间隔图表化。

第一实施方式(“No_Merge”)与第二实施方式(“Loop_Merge”)的图表因为即使针对局部定时也不会牺牲预测精度，所以与由未图示的命令集模拟器得到的结果完全一致。

另外，在第三实施方式(“Branch_Merge”)中，由于if-else块的聚合处理而失去了该部分的局部定时再生精度，因此“局部定时再生精度”产生误差，但是可以说大致能够再生局部定时的波动的趋势。

并且，在第四实施方式(“Full_Merge”)中，由于平均化作用而局部定时的波动完全消失。

并且，在第六实施方式(“Param_Merge”)中，局部定时再生精度的误差几乎为0(即，与第一实施方式“No_Merge”一致)，并且与“Loop_Merge”(第二实施方式)相比能够实现较小分支历史记录比特序列长度。

也就是说，在第六实施方式中，如图49所示，通过调整“if-else偏重度阈值(图41)”与“循环偏重度阈值(图41)”，能够自由地设定局部定时再生精度的控制与分支历史记录比特序列长度的长度的控制之间的折衷点。

(第七实施方式：多处理器)

使用于第一～第六实施方式中的执行时间估计装置1a～1e、1g(图1、图9、图18、图27、图35以及图41)的处理器以单一处理器为前提，但是还能够将其设为多处理器。下面，作为第七实施方式说明将第一实施方式所涉及的执行时间估计装置1a(图1)设为多处理器的例子。

在此，说明使用于第七实施方式的多处理器。

在第七实施方式中，多处理器程序是指在构成多处理器系统的各处理器上分别执行的程序(对象程序)的集合(或者“并行处理程序”)。在该多处理器程序中，作为明确的命令嵌入有处理器(过程)之间通信处理、同步处理。

作为多处理器程序的制作方法，存在依次使用程序的自动并行编译程序的方法(参照岡本、合田、宮沢、本多、笠原、“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]，[平成17年8月10日検索]，インタ一ネツト<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]，[平成17年8月10日検索]，インタ一ネツト<URL：http://www.mpi-forum.org/index.html>，“PVM”，[online]，[平成17年8月10日検索]，インタ一ネツト<URL：http://www.csm.ornl.gov/pvm/pvm_home.html>)、以及使用从依次在程序上仅追加“线程描述”的程序自动地生成通信同步命令的并行处理编译程序的方法(参照日本特开2007-193423号公报、日本特开2007-193430号公报)。

第七实施方式中的多处理器结构可考虑全部为相同种类的处理器的对称型多处理器系统以及异种处理器进行混合的非对称型多处理器系统。不论是哪一个系统，在第七实施方式中，在部分程序执行时间估计算出部12f(参照图52来后面说明)中，都能够通过将负责执行各个程序的对象处理器模型切换为构成对象多处理器系统的各处理器而容易地应对。

下面，参照图50～图53来说明第七实施方式所涉及的执行时间估计装置1f的结构。

图50是表示第七实施方式所涉及的执行时间估计装置的结构例的图。

执行时间估计装置1f(1)具有后面在图52中说明的前处理部61以及后面在图53中说明的后处理部62。前处理部61具有以下功能：由多处理器进行并行处理，由此从多个对象程序按照每个对象程序生成和算出部分程序表、分支历史记录比特序列以及部分程序执行时间并输入到后处理部62。后处理部62具有以下功能：根据由多处理器进行并行处理而由前处理部61生成和算出的部分程序表、分支历史记录比特序列、部分程序执行时间，算出各对象程序的执行时间估计值。另外，进行执行时间估计的对象程序相当于过程，在形成集合了多个过程而得到的一个父程序的情况下，后处理部62一边如实地再现各过程之间的同步和数据通信一边算出高精度的执行时间估计值。

图51是表示第七实施方式所涉及的执行时间估计装置的硬件结构的图。

在图51中形成具备多个CPU 151f的多处理器的结构这一点与图2不同。除此以外的要素与图2相同，因此附加相同的附图标记来省略说明。

图52是表示第七实施方式所涉及的前处理部的详细的结构例的图。

前处理部61具有程序分割部11f、部分程序执行时间估计算出部12f以及分支历史记录信息生成部13f。

程序分割部11f具有以下功能：从多个对象程序使用多处理器的并行处理来生成每个对象程序的部分程序表。

第七实施方式所涉及的程序分割部11f是对第一实施方式的程序分割部11(图1)的功能(在此，按照各处理器负责执行的每个程序进行处理)追加处理通信同步命令的功能而得到的。通信同步命令为使处理器执行状态变化的原因，为了高精度地估计多处理器系统的执行时间，需要确定通信同步命令的正确的执行时刻。也就是说，在多个对象程序作为过程而相互同步时执行一个程序的情况下，通信同步命令存在于每个对象程序中。

在此，在根据日本特开2007-193430号公报的方法生成的多处理器程序的例子中，可举出以下四种通信同步命令。

即，存在数据发送命令、数据接收同步命令、线程启动命令以及线程结束命令。其中，线程结束命令是用于启动线程处理结束时的接收缓冲区更新处理而开始执行下一个线程处理的命令。

在随后的说明中，作为“通信同步命令”的具体例，对该四种命令进行处理。

即，在将各处理器所执行的对象程序分别分割为部分程序时，在第一实施方式中的程序分割部11(图1)中，将条件分支命令与函数调用命令设为程序分割的边界点，但是在第七实施方式中的程序分割部11f中，将通信同步命令也视作边界点来进行部分程序分割。其结果是，通信同步命令一定成为部分程序的开始命令。这样，下面将开始命令为通信同步命令的部分程序记载为“通信同步部分程序”。

部分程序执行时间估计算出部12f根据程序分割部11f所生成的部分程序表和预先输入的独立处理器模型，使用多处理器的并行处理来算出每个对象程序的部分程序执行时间。此外，将所算出的部分程序执行时间写入到部分程序表中的“执行时间估计值”中。此外，在非对称多处理器系统的情况下，也可以按照每个处理器存在多种对象程序。

在此，独立处理器模型是指各个负责执行程序的处理器的模型。如上所述，关于构成多处理器系统的处理器，存在种类全部相同的情况(对称型)下的模型和多个种类的情况(非对称型)下的模型，在第七实施方式中可以使用任一个。独立处理器模型是与对各独立程序进行处理的处理器的模型有关的信息。

分支历史记录信息生成部13f具有以下功能：从多个对象程序使用多处理器的并行处理来生成每个对象程序的分支历史记录比特序列。

在第七实施方式中，分支历史记录信息生成部13f在“可执行的计算机环境”(例如多处理器模拟器)中执行多个对象程序，将使每个处理器的程序执行中的所有条件分支命令的执行结果(“真”或者“假”：1比特信息)按照在各处理器上执行的顺序进行结合并生成的“分支历史记录比特序列”保存到RAM 153等存储装置170(图51)。即，从M个对象程序生成M个独立的“分支历史记录比特序列”。

在此，说明第七实施方式中的部分程序表。

在第七实施方式中的部分程序表中除了存储存储在图5中的部分程序表中的信息以外还存储与通信同步部分程序有关的信息(数据发送命令、线程启动命令、接收处理器ID、接收缓冲器ID、数据接收同步命令以及接收缓冲器ID)。此外，与通信同步部分程序有关的信息是执行了开始通信同步命令时的处理器执行状态更新、通信同步资源状态更新所需的信息。

在前处理部61中生成的、追加部分程序执行时间估计值后的部分程序表、分支历史记录比特序列以及部分程序执行时间被输入到后处理部62。

图53是表示第七实施方式所涉及的后处理部的详细结构例的图。

后处理部62具有队列指示部63和跟踪模拟控制部64。

队列指示部63具有以下功能：对始终维持处理器时钟值70的上升排序顺序状态下存储处于“可执行状态”的处理器的“处理器等待矩阵”、即处理器队列(实际存储的是处理器ID)进行管理。另外，队列指示部63还具有以下功能：临时从队列中删除该“处理器队列”的开头处理器之后，使处理器队列所示的下一个处理器执行跟踪模拟(下面将该执行中的处理器称为“当前处理器”)。

跟踪模拟控制部64具有执行跟踪再生部14f、执行时间估计算出部15f以及通信同步命令模拟执行部65。

跟踪模拟控制部64具有以下功能：利用执行跟踪再生部14f和执行时间估计算出部15f在各处理器中生成部分程序执行序列或者进行执行时间估计算出处理等，并进行将其执行时间估计值设为处理器时钟值70的更新。

即，跟踪模拟控制部64具有对处理器的动作进行伪模拟的功能。

在存储部66(相当于图51的可移动记录介质159)中具有分支历史记录比特序列读出位置指定信息67、通信同步资源状态信息68、处理器执行状态信息69(可执行状态和执行待机状态)以及处理器时钟值70。

执行跟踪再生部14f具有以下功能：与上述实施方式同样地，使用分支历史记录比特序列读出位置指定信息67，根据从前处理部61输入的每个对象程序的部分程序表和分支历史记录比特序列来生成部分程序执行序列，按照该部分程序执行序列将部分程序执行时间估计值依次发送到执行时间估计算出部15f。

通信同步命令模拟执行部65具有以下功能：为了保证正确地再现通信同步资源状态信息68的更新、处理器执行状态信息69的更新的因果关系，按照时间性顺序执行所有通信同步命令的模拟。

此外，将存储于图51示出的存储装置170等中的执行时间估计程序加载到RAM 153中而由CPU 151f执行，由此实现图50、图52以及图53示出的各部11f～15f、61～70。

接着，参照图53按照54来说明第七实施方式所涉及的后处理部62中的处理的流程。

图54是表示第七实施方式所涉及的后处理部中的处理的流程的流程图。此外，前处理部61中的处理是对各个对象程序并行进行第一实施方式的图2的步骤S101～S103的处理的处理，因此省略说明。并且，执行跟踪再生部14f和执行时间估计算出部15f中的处理是对每个处理器并行进行第一实施方式的图2的步骤S104、S105的处理的处理，因此在图50中主要以第七实施方式特有的处理为中心进行说明。

首先，跟踪模拟控制部64进行可执行开头处理器的获取处理(S601)。该处理是以下处理：跟踪模拟控制部64从队列指示部63获取处理器队列的开头处理器ID，并设定为“当前处理器”。并且，队列指示部63从队列中删除当前处理器。也就是说，队列指示部63将成为当前模拟的对象的处理器更换为其它处理器。

然后，跟踪模拟控制部64进行处理器模拟状态设定处理(S602)。在此，跟踪模拟控制部64将跟踪模拟控制部64本身的内部状态的信息设定为当前处理器的处理器模拟状态的信息。在此，内部状态的信息是指分支历史记录比特序列的读出位置(分支历史记录比特序列读出位置指定信息67)、处理器时钟值70、处理器执行状态信息69、通信同步资源状态信息68等。

分支历史记录比特序列读出位置指定信息67保存有与每个处理器的分支历史记录比特序列的读出位置(即，接着读出的比特的位置)有关的信息。

在此，如下定义处理器执行状态信息69。构成多处理器系统的各处理器采用一般的“可执行状态”以及临时陷入执行处理器间通信处理、同步处理等中的“执行待机状态”中的任一个状态。与该状态有关的信息为处理器执行状态信息69，在多处理器系统中，各处理器不仅始终估计计算作为“可执行状态”的区间的执行时间，还需要一边正确地再现由于处理器间的相互作用而产生的“执行待机状态”一边估计计算执行时间。

另外，通信同步资源状态信息68是指用于控制处理器执行状态转移的在各处理器内管理的内部状态。在上述四种通信同步命令的例子中，接收缓冲状态(积存在接收缓冲器中的数据个数)相当于该“通信同步资源状态”。

处理器时钟值70是指处理器执行对象程序时所需的时间，具体地说存储所算出的对象程序的执行时间估计值。

在步骤S602之后，执行跟踪再生部14f根据分支历史记录执行序列和部分程序表来生成部分程序执行序列(S603)，按照该部分程序执行序列将部分程序执行时间估计值依次发送到执行时间估计算出部15f。此外，实际上，执行跟踪再生部14f与上述实施方式同样地一边生成部分程序执行序列一边从部分程序表获取对应的部分程序执行时间估计值，按照所获取到的顺序将部分程序执行时间估计值发送到执行时间估计算出部。步骤S603的处理是按照每个对象程序来进行第一实施方式中的部分程序执行序列的生成处理的处理。执行跟踪再生部14f为了生成多个对象程序中的部分程序执行序列而获取对应的处理器中的分支历史记录比特序列读出位置指定信息67，从分支历史记录比特序列中读出该分支历史记录比特序列读出位置指定信息67所示的比特。然后，执行跟踪再生部14f按照所读出的比特从部分程序表读出部分程序执行时间估计值，追加到部分程序执行序列，同时将部分程序执行时间估计值发送到执行时间估计算出部15f。当向部分程序执行序列的追加(部分程序执行时间估计值的发送)结束时，执行跟踪再生部14f将对应的处理器的分支历史记录比特序列读出位置指定信息67后移1比特。

然后，通信同步命令模拟执行部65获取在步骤S603中从执行跟踪再生部14f追加到部分程序执行序列的部分程序ID。然后，通信同步命令模拟执行部65通过判断所获取到的部分程序ID是否为与通信同步部分程序有关的ID来判断当前进行处理的部分程序是否为通信同步部分程序(S604)。如上所述，在部分程序表中除了存储图5示出的信息以外还存储有通信同步部分程序的ID(数据发送命令和线程启动命令、接收处理器ID、接收缓冲器ID、数据接收同步命令以及接收缓冲器ID)，因此通信同步命令模拟执行部65根据这些ID来进行判断。

在步骤S604的结果为不是通信同步部分程序的情况下(S604→No)，跟踪模拟控制部64进入到步骤S612进行处理。

在步骤S604的结果为是通信同步部分程序的情况下(S604→Yes)，通信同步命令模拟执行部65判断是否违反通信同步命令的时间顺序性(S605)。在当前处理器的处理器时钟值70在模拟同步时刻以下的情况下，通信同步命令模拟执行部65判断为“没有违反时间顺序性(步骤S605→No)”，在除此以外的情况下，通信同步命令模拟执行部65判断为“违反时间顺序性(步骤S605→Yes)”，由此进行该判断。此外，在“违反时间顺序性”的情况下，有可能比该通信同步命令执行时刻提前的时刻存在可执行的通信同步命令。

在此，模拟同步时刻是指处理器队列的开头处理器(当前处理器以外)的处理器时钟值70。在“处理器队列”为空的情况下(即，不存在当前处理器以外可执行的处理器的情况)，“模拟同步时刻”成为无限大的值。

在步骤S605的结果是判断为违反时间顺序性的情况下(S605→Yes)，跟踪模拟控制部64将当前处理器状态再次投入到“处理器队列”(S606)，返回到步骤S601的处理。即，跟踪模拟控制部64为了防止通信同步命令的时间顺序性走样的可能性，推迟执行当前处理器的跟踪模拟。

步骤S605的结果是判断为没有违反时间顺序性的情况下(S605→No)，即判断为保证了通信同步命令的时间顺序性的情况下，跟踪模拟控制部64按照图55来进行由执行通信同步命令引起的处理器的处理器执行状态信息69的更新(S607)。

在此，图55是表示处理器从可执行状态转移到执行待机状态的条件的表。如图55所示，按照每个通信同步命令来预先设定处理器从可执行状态转移到执行待机状态的条件。

步骤S607之后，通信同步命令模拟执行部65参照处理器执行状态信息69来判断当前处理器是否为执行待机状态(S608)。

在步骤S608的结果为是执行待机状态的情况下(S608→Yes)，跟踪模拟控制部64返回到步骤S601进行处理。

在步骤S608的结果为不是执行待机状态的情况下(S608→No)，通信同步命令模拟执行部65按照图56来更新通信同步资源状态信息68(S609)。

图56是表示通信同步资源状态信息的更新内容以及作为执行待机状态的处理器向可执行状态恢复的条件的表。如图56所示，也按照每个通信同步命令来预先设定通信同步资源状态信息68的更新内容以及作为执行待机状态的处理器向可执行状态恢复的条件。

然后，步骤S609的结果是，通信同步命令模拟执行部65对从执行待机状态转移到可执行状态的其它所有的处理器进行以下处理。

即，通信同步命令模拟执行部65为了反映处理器待机时间，而将对应的处理器的处理器时钟值70设定为当前处理器的时钟值(处理器时钟值70)(S610)，队列指示部63将对应的处理器投入到“处理器队列”(S611)。同时，执行时间估计算出部15f按照每个处理器对从执行跟踪再生部14f获取到的部分程序执行时间估计值进行相加。

然后，通信同步命令模拟执行部65在执行时间估计算出部15f中将所算出的执行时间估计值设为当前处理器时钟值，对当前处理器的处理器时钟值70进行更新(S612)，跟踪模拟控制部64返回到步骤S603进行处理。此外，在步骤S612的阶段中，在结束对部分程序表中的所有部分程序进行处理的情况下，跟踪模拟控制部64结束处理。

另外，在第七实施方式中，将第一实施方式所涉及的处理设为多处理器处理，但是并不限于此，也可以将第二～第六实施方式所涉及的处理设为多处理器处理。在这种情况下，当然对图10、图11、图15、图19、图20、图23、图29、图30、图36、图42以及图44中的各处理进行多处理器的并行处理。

(第七实施方式的效果)

根据第七实施方式，能够使用多处理器并行地估计多个对象程序的执行时间，因此能够有效地估计执行时间。

此外，在日本特开2007-193430号公报中存在“程序处理部结束当前的线程处理之后向数据接收部发送线程处理结束信号”这种描述，但是在第七实施方式中，设置为“线程结束命令”启动接收缓冲区更新处理。另外，在日本特开2007-193430号公报中没有说明“线程启动命令”的具体的实现方法，而通过与数据发送命令相同的通信协议进行安装。即，在日本特开2007-193430号公报中“线程启动命令”发送“线程启动标记”代替发送数据，在接收处理器的数据接收部中与其它数据接收缓冲器同样地设置有线程启动标记用接收缓冲器。

(试验例)

接着，参照图57～图59来说明第七实施方式所涉及的试验结果。

在图57～图59中使用的计算机的配置是将在图45至图49中使用的计算机的CPU设为多处理器的配置，因此省略说明。

图57是表示作为比较例使用命令集模拟器的试验结果的表。

作为所使用的命令集模拟器，使用以下命令集模拟器：以循环精度对通信同步处理也包含在内的多处理器系统上的并行程序执行处理时间进行估计(其中不包含高速缓冲模拟)，上述多处理器系统以32比特RISC处理器为构成要素。

另外，在图57以及图58中使用的测试程序(对象程序)是处理器数量五个的64抽头FIR(Finite Impulse Response：数字滤波器)过滤程序(“FIR”)以及处理器数量十九个的像素大小800×600像素的JPEG编码程序(“JPEG”)。

在图57中，对于上述两个对象程序，对象程序大小为对象程序中的命令数。程序依次执行时间是将执行对象程序时的所有处理器中的总时钟周期数相加而得到的。也就是说，程序依次执行时间是以总时钟数来表示在各处理器中串行地执行对象程序时的执行时间的时间。程序并行执行时间是以总时钟周期数来表示在多处理器中并行地执行对象程序时的执行时间的时间。并行处理速度提高率是通过(程序依次执行时间/程序并行执行时间)算出的值。多处理器命令集模拟器执行时间是在多处理器中的命令集模拟器中估计各对象程序的执行时间时所需的时间，单位为“秒钟”。命令集模拟器处理速度是以时钟周期数表示在多处理器系统中估计各对象程序的执行时间时的处理速度的速度，单位为“时钟周期/秒钟”。

图58是表示第七实施方式所涉及的试验结果的例子。

此外，在图58中，部分程序表大小表示由程序分割部11f(图52)生成的部分程序表的行数在全处理器中的合计值。分支历史记录比特序列长度是由分支历史记录信息生成部13f(图52)生成的分支历史记录比特序列的长度(比特数)在全处理器中的合计值。对象程序并行执行时间估计值是以总时钟周期数表示由第七实施方式所涉及的执行时间估计装置1f(图50)算出的对象程序的并行执行时间估计值的值。对象程序并行执行时间估计误差是所算出的执行时间估计值与实际的对象程序的执行时间之间的误差，单位为“秒钟”。执行时间估计算出时间是第七实施方式所涉及的执行时间估计装置1f算出对象程序的执行时间所需的时间，单位为“秒钟”。对命令集模拟器速度提高比是通过(命令集模拟器中的执行时间/执行时间估计装置1f中的执行时间)算出的值。

此外，在图58中，对于“FIR”，示出了将第二实施方式(“Loop_Merge”)应用于多处理器而得到的结果，对于“JPEG”，示出了将第二实施方式(“Loop_Merge”)与第四实施方式(“Full_Merge”)应用于多处理器而得到的结果。

参照图58中的对命令集模拟器速度提高比，在任一情况下，都为41.21～149.91，能看出处理时间的大幅的改善。

图59是表示局部定时再生精度的比较的图表。

图59是对于图58中的JPEG对将第二实施方式应用于多处理器时(称为第二’实施方式)的局部定时再生精度与将第四实施方式应用于多处理器时(称为第四’实施方式)的局部定时再生精度进行比较的图表，纵轴表示对象程序中的代码处理中的时钟周期数，横轴表示时间。

在第二’实施方式(“Loop_Merge”)中时钟周期数随着时间发生变化。这意味着如实地再现对象程序中的代码处理中的时钟周期数且局部定时再生精度较高。也就是说，在第二’实施方式(“Loop_Merge”)中，也不会牺牲局部定时的预测精度，因此能够如实地再现局部的处理负载的变动。另外，在第四’实施方式(“Full_Merge”)中，使时钟周期数平均化，但是即使这样使代码处理中的时钟周期数平均化，对处理结果的影响也止于百分之几，因此与非专利文献7～非专利文献10所记载的方法等相比，能够将执行时间估计值的预测精度保持为较高状态。