執行時間估計方法、執行時間估計程序以及執行時間估計裝置的製作方法

2023-04-26 00:10:11

專利名稱：：執行時間估計方法、執行時間估計程序以及執行時間估計裝置的製作方法
技術領域：
：本發明涉及一種估計程序的執行時間的執行時間估計方法、執行時間估計程序以及執行時間估計裝置。
背景技術：
：提出了多個估計程序的執行時間的方法(例如參照非專利文獻1)。作為這種估計程序的執行時間的方法之一，存在一種命令集模擬器(例如參照非專利文獻2非專利文獻6)。另外，還提出了以下方法通過執行將預測執行時間信息嵌入到程序內的程序來算出執行時間的方法(例如參照非專利文獻7)；以及僅執行程序的一部分，根據該一部分的執行時間估計程序整體的執行時間的方法(例如參照非專利文獻8非專利文獻10)。非專利文獻1；J.J.YiandD.J.Lilja.SimulationofComputerArchitecturesSimulators，Benchmarks，Methodologies，andRecommendations.IEEETrans.Comput.，55(3),2006.非專禾U文獻2:A.Nohl,G.Braun,0.Schliebusch,R.Leupers,H.Meyr,andA.Hoffmann.AUniversalTechniqueforFastandFlexibleInstruction-SetArchitectureSimulation.InDAC^02ConferenceonDesignautomation,NewYork,NY,USA，2002.ACMPress.非專利文獻3；Μ.PoncinoandJ.Zhu.DynamoSim:ATrace-basedDynamicallyCompiledInstructionSetSimulator.InICCAD'04-Proceedingsofthe2004IEEE/ACMInternationalconferenceonComputer-aideddesign,Washington,DC,USA,2004.IEEEComputerSociety.非專禾Ij文獻4Qin，J.D，Errico，andX.Zhu.AMultiprocessingApproachtoAccelerateRetargetableandPortableDynamic-compiledInstruction-setSimulation.InCODES+ISSS*06ConferenceonHardware/SoftwareCodesignandSystemSynthesis,NewYork，NY，USA，2006.ACMPress.非專利文獻5Reshadi，P.Mishra，andN.Dutt.InstructionSetCompiledSimulation:ATechniqueforFastandFlexibleInstructionSetSimulation.InDACT03!ConferenceonDesignAutomation,NewYork,NY,USA,2003.ACMPress.非專禾丨J文獻6:HySim:AFastSimulationFrameworkforEmbeddedSoftwareDevelopmentStefanKraemer,LeiGao,JanWeinstock,RainerLeupers,GerdAscheidandHeinrichMeyrInCODES+ISSS'07ConferenceonHardware/SoftwareCodesignandSystemSynthesis,NewYork，NY，USA，2007.ACMPress.非專利文獻7；Τ.Kempf,K.Karuri,S.Wallentowitz,G.Ascheid,R.Leupers,andH.Meyr.ASWPerformanceEstimationFrameworkforEarlySystem-Leve!-DesignusingFine-GrainedInstrumentation.InDATE'06ConferenceonDesign,AutomationandTestinEurope,3001Leuven,Belgium,Belgium,2006.EuropeanDesignandAutomationAssociation.非專利文獻8:T.Sherwood,Ε.Perelman,G.HamerIy,andB.Calder.AutomaticallyCharacterizingLargeScaleProgramBehavior.InASPLOS-XProceedingsofthe10thinternationalconferenceonArchitecturalSupportforProgrammingLanguagesandOperatingSystems,NewYork,NY,USA,2002.ACMPress.非專利文獻9:T.Sherwood,Ε.Perelman,G.HamerIy,S.Sair,andB.Calder.DiscoveringandExploitingProgramPhases.IEEEMicro,December2003.非專利文獻10:R.Wunderlich,Τ.ffenisch,B.Falsafi,andJ.Hoe.SMARTSAcceleratingMicroarchitectureSimulationviaRigorousStatisticalSampling.In30thAnnualInternationalSymposiumonComputerArchitecture,June2003.
發明內容發明要解決的問題在非專利文獻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聚合處理的流程的圖。圖M是示出包含第三種循環的對象程序的例子的圖。圖25是示出由圖M示出的對象程序生成的部分程序表的例子的圖。圖沈是進行了聚合處理的部分程序表的例子，(a)示出對「J」進行if-else聚合處理的結果，(b)是對(a)的結果進行相鄰聚合處理的結果，(c)是對「H」進行if-else聚合處理的結果，(d)是對(c)的結果進行相鄰聚合處理的結果。圖27是示出第四實施方式所涉及的執行時間估計裝置的結構例的圖。圖觀是示出包含第四種循環的對象程序的例子的圖。圖四是示出第四實施方式所涉及的程序執行時間估計方法的流程的流程圖。圖30是示出第四實施方式所涉及的多重循環聚合處理的流程的圖。圖31是示出由圖觀示出的對象程序生成的部分程序表的例子的圖。圖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是示出第七實施方式所涉及的後處理部的詳細結構例的圖。圖M是示出第七實施方式所涉及的後處理部中的處理流程的流程圖。圖55是示出處理器從可執行狀態轉移到執行待機狀態的條件的表。圖56是示出通信同步資源狀態信息的更新內容以及處於執行待機狀態的處理器變為可執行狀態的恢復條件的表。圖57是示出作為比較例使用命令集模擬器的試驗結果的表。圖58是示出第七實施方式所涉及的試驗結果的例子。圖59是示出局部定時再生精度的比較的圖表。附圖標記說明UlaIg執行時間估計裝置；ll、llf程序分割部；12、12f部分程序執行時間估計算出部；13、13b、13c、13f分支歷史記錄信息生成部；14、14b、14c、14f執行跟蹤再生部；15、15b、15f執行時間估計算出部；21循環信息提取部；21e第二種循環信息提取部；22程序執行歷史記錄信息生成部；23第二種循環執行時間估計算出部；31分支概率信息提取部；32第三種循環聚合部；33多重if-else聚合部；41多重循環聚合部；51if-else塊執行時間偏重度算出部；52df-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是表示第一實施方式所涉及的執行時間估計裝置的結構例的圖。執行時間估計裝置Ia(I)具有程序分割部11、部分程序執行時間估計算出部12、分支歷史記錄信息生成部13、執行跟蹤再生部14以及執行時間估計算出部15。下面，對執行時間估計裝置Ia中的各部的概要進行說明，詳細的處理內容參照圖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示出的執行時間估計裝置Ia的硬體結構，也可以是圖9、圖18、圖27、圖35、圖41示出的執行時間估計裝置Ible、Ig的硬體結構。執行時間估計裝置1具備CPU(CentralProcessingUnit中央處理器)151、ROM(ReadOnlyMemory只讀存儲器)152、RAM(RandomAccessMemory:隨機存取存儲器)153以及EEPROM(ElectricallyErasableandProgrammableReadOnlyMemory:電可擦除只讀存儲器)154，它們通過總線161相互連接。並且，在執行時間估計裝置1中，顯示器等輸出部155、鍵盤或滑鼠等收入部156、NIC(NetworkInterfaceCard:網絡接口卡)等作為通信接口的通信部157以及從可移動記錄介質159讀取信息的驅動器158與輸入輸出接口160相連接。輸入輸出接口160與總線161相連接，由此控制輸出部155、輸入部156、通信部157以及驅動器158與CPU151、ROM152、RAM153以及EEPROM巧4之間的信息流動。此外，在本實施方式中，將RAM153、對驅動器158與可移動記錄介質159進行組合的裝置等記載為存儲裝置170。圖1示出的各部1115將存儲於存儲裝置170等中的執行時間估計程序加載到RAM153中而由CPU151執行來實現。接著，參照圖1並按照圖3來說明本實施方式所涉及的程序執行時間估計方法。圖3是表示第一實施方式所涉及的程序執行時間估計方法的流程的流程圖。(程序分割處理)首先，程序分割部11進行程序分割處理(S101)，將對象程序分割為部分程序。部分程序是指將條件分支命令和函數調用命令作為邊界點、內部不包含條件分支命令、函數調用命令的執行命令序列。程序分割的實際圖4是第一實施方式所涉及的對象程序的例子。在圖4示出的對象程序中存在與條件變量「A」、「B」、「C」、「D」以及「E」有關的五個條件分支命令。程序分割部11對圖4示出的對象程序進行圖3的步驟SlOl的程序分割處理時輸出圖5示出的部分程序表。〈部分程序表〉下面，參照圖4來說明圖5中的部分程序表。圖5是表示第一實施方式所涉及的部分程序表的例子的圖。部分程序表具有「部分程序ID(Identificati0n)」(下面，在部分程序表的附圖內記載為「ID」)、「部分程序開始命令」、「部分程序終止命令」以及「部分程序執行時間估計值」而分別作為欄位(列)。此外，部分程序表是當被程序分割部11生成時保存到RAM153(圖2)等存儲裝置170(圖2)中的數據。「部分程序ID」是由部分程序分割部11按每個部分程序唯一地附加的ID。「部分程序開始命令」是描述各個部分程序中的開始命令的欄位。例如，對應於圖5的部分程序ID「1」的部分程序(下面，將對應於部分程序ID「n」的部分程序記載為部分程序「η」)中的「main:start」以及部分程序「8」中的「fimcl:start」分別表示函數(main函數和fimcl函數)的初始命令。另外，部分程序「2」中的「branch㈧[T]」表示圖4中的條件變量「A」為「真」的值時的條件分支命令，部分程序「3」中的"branch(A)[F]」表示圖4中的條件變量「A」為「假」的值時的條件分支命令。「部分程序終止命令」是描述各個部分程序的終止的命令的欄位。例如，當參照部分程序「1」時，可知「branch(A)」為部分程序的終止命令。即，可知部分程序「1」為從「maiiKstart」(部分程序開始命令)至「branch(A)」(部分程序終止命令)。同樣地，部分程序「2」為從「branch(A)」具有「真」的值時起至branch⑶。此外，如部分程序「6」的「部分程序終止命令」中的「funcl=StartIbranch(A)」那樣，在記載有多個命令(以「I」標記分開)的情況下，表示如下內容控制從記載於「部分程序開始命令」的函數轉移到調用函數「fimcl」的初始命令「funcLstart」，函數「fimcl」的執行結束之後(即，到達「funcLend」之後)最終到達branch(A)。此外，圖5中的「部分程序執行時間估計值」為由部分程序執行時間估計算出部12在步驟S102中算出的部分程序的執行時間的估計值，該欄位在步驟SlOl的階段中成為空欄。(部分程序執行時間估計算出處理)返回到圖3，接著步驟SlOl之後，部分程序執行時間估計算出部12進行部分程序執行時間估計算出處理(S102)。部分程序執行時間估計算出部12在步驟S102中算出在步驟SlOl中生成的各部分程序的對象處理器上的執行時間的估計值。此外，部分程序執行時間估計算出部12通過實際執行部分程序來算出部分程序的執行時間。在此，關於在對象程序中反覆產生的部分程序，算出一次量的執行時間即可，因此與直接對對象程序估計執行時間的方法相比，能夠在遠遠短的時間內結束步驟S102。例如，即使在「α」這種部分程序根據循環、條件分支命令等而多次執行的狀態下，也只要在步驟S102中算出「α」一次量的執行時間即可。此外，在已經存在生成對象程序的執行機械代碼的編譯程序的情況下，各分割程序的處理時間在內部不包含條件分支命令、函數調用，因此能夠高精度進行估計。另外，在未開發對象處理器專用的編譯程序的情況下，關於各分割程序的處理時間，根據對象處理器的結構性特徵算出各命令的執行時間的預測值(各計算命令的執行時間、存儲器訪問時間)，根據這些預測值來算出執行時間的估計值。部分程序執行時間估計算出部12將所算出的部分程序執行時間估計值寫入到圖5的部分程序表的「部分程序執行時間估計值」的欄位中。在此，圖5的「部分程序執行時間估計值」的欄位表示從對應的部分程序的開始命令至終止命令的執行時間。例如，部分程序「1」中的「Tl」表示從「maiiKstart」至「branch(A)」的執行時間，其中，包含「代碼區域l」、「i=0」以及「i<N」(圖4)這種計算命令。另外，部分程序「4」中的「T4」表示條件「B」為「真」的情況下的分支命令至"branch(A)，，的執行時間，其中，包含「代碼區域2」、「代碼區域3」、「i++」以及「i<N」(圖4)這種計算命令。此外，圖5中的部分程序「6」中的「T6a」表示從條件「C」為「真」的情況下的分支命令至調用函數「func1」的開始命令「fimc1start」的執行時間。相同部分程序「6」中的「T6b」表示從控制從函數「fimcl」返回到「main」之後至"branch(A)，，的執行時間，其中，包含「代碼區域3」、「i++」以及「i<N」(圖4)這種計算命令。(分支歷史記錄信息生成處理)返回到圖3，當步驟S102的處理結束時，分支歷史記錄信息生成部13進行分支歷史記錄信息生成處理(S103)。分支歷史記錄信息生成部13在步驟S103中執行對象程序，以1比特信息來表現執行了對象程序時的所有條件分支命令中的「真」和「假」，將按執行該1比特信息的順序結合而生成的分支歷史記錄比特序列保存到RAM153等存儲裝置170。分支歷史記錄比特序列例如成為以「真」為「1」、「假」為「0」表現的「1110111010」這樣的1比特信息的序列。對象程序中的條件分支命令執行數為全部命令執行數中的百分之幾左右，而且能夠以1比特表現分支條件的執行結果，因此即使在執行非常長的對象程序的情況下也能夠以比較少的數據容量表現分支歷史記錄比特序列。因此，即使保存到硬碟那樣的具有非常大的延遲時間的信息存儲介質，也存在大幅縮短用於保存程序執行歷史記錄信息的開銷時間的效果。並且，分支歷史記錄信息生成部13並未將條件變量的真假值分別以1比特直接記錄到硬碟等外部存儲裝置，而是通過內部寄存器、緩存存儲器、主存儲裝置(mainmemory)等存儲器層，最終將分支歷史記錄信息保存到外部存儲裝置(硬碟等)，因此與依次保存到硬碟的情況相比，能夠縮短延遲時間。分支歷Φ記錄信息牛成處理的實際在各部分程序的開始命令為條件分支命令的情況下，能夠通過使將這些條件變量的真假值(「1」和「0」的二值表現的值)記錄到存儲裝置170的命令程序附加到對象程序來實現分支歷史記錄信息生成部13。所附加的命令程序例如為圖6示出那樣的文件輸出函數程序。也就是說，能夠通過由執行時間估計裝置Ia調用圖6示出的文件輸出函數程序，來實現分支歷史記錄信息生成部13。圖6是表示用於輸出分支歷史記錄比特序列的文件輸入輸出函數的例子的圖，圖7是表示圖4中的對象程序的一部分的圖，圖8是表示覆蓋圖7示出的程序之後的程序的例子的圖。此外，圖7示出圖4的對象程序中的第三行和第四行。分支歷史記錄信息生成部13在定義圖5那樣的文件輸出函數之後，如圖8所示那樣將在圖6中條件變量「Α」和「B」出現在程序上的位置覆蓋即可。並且，通過由執行時間估計裝置Ia執行圖8那樣覆蓋後的對象程序來實現分支歷史記錄信息生成部13，由此能夠獲取分支歷史記錄比特序列。(執行跟蹤再生處理)返回到圖3，當結束步驟S103時，執行跟蹤再生部14根據部分程序表和分支歷史記錄比特序列來進行執行跟蹤再生處理(S104)。執行跟蹤再生部14在步驟S104中依次讀取在步驟S103中生成的分支歷史記錄比特序列的比特，根據在步驟S102中生成的部分程序表來再生程序執行跟蹤，生成部分程序執行序列。執行跟蹤再生處理的實際下面，參照圖5說明分支歷史記錄比特序列為「1110111010」的情況下的執行跟蹤再生處理的實際。首先，執行跟蹤再生部14讀取部分程序表中的部分程序「1」，到達「部分程序終止命令」「branch(A)」。此時，執行跟蹤再生部14讀取部分程序「1」的部分程序執行時間估計值「Tl」，將該部分程序執行時間發送到執行時間估計算出部15。分支歷史記錄比特序列的開頭比特「1」表示條件變量「A」為「真」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(A)[Τ]，，的部分程序「2」，到達其「部分程序終止命令」「branch(B)」。然後，執行跟蹤再生部14讀取部分程序「2」的部分程序執行時間估計值「T2」，將該部分程序執行時間發送到執行時間估計算出部15。分支歷史記錄比特序列的第二個比特「1」表示條件變量「B」為「真」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(B)[Τ]，，的部分程序「4」，到達其「部分程序終止命令」「branch(A)」。然後，執行跟蹤再生部14讀取部分程序「4」的部分程序執行時間估計值「T4」，將該部分程序執行時間發送到執行時間估計算出部15。下面，同樣地，分支歷史記錄比特序列的第三個分支歷史記錄比特「1」表示條件變量「A」為「真」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(A)[Τ]，，的部分程序「2」，到達作為其「部分程序終止命令」的「branch⑶」。然後，執行跟蹤再生部14讀取部分程序「2」的部分程序執行時間估計值「T2」，將該部分程序執行時間發送到執行時間估計算出部15。接著，分支歷史記錄比特序列的第四個分支歷史記錄比特「0」表示條件變量「B」為「假」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(B)[F]，，的部分程序「5」，到達作為其「部分程序終止命令」的「branch(C)」。然後，執行跟蹤再生部14讀取部分程序「5」的部分程序執行時間估計值「T5」，將該部分程序執行時間發送到執行時間估計算出部15。然後，分支歷史記錄比特序列的第五個分支歷史記錄比特「1」表示條件變量「C」為「真」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(C)[Τ]，，的部分程序「6」，到達作為第一終止命令的調用函數「fimcl:start」。此時，執行跟蹤再生部14將部分程序壓入到堆棧而調用，將原來的部分程序記錄到RAM153等存儲裝置170(圖2)。然後，執行跟蹤再生部14讀取部分程序「6」的部分程序執行時間估計值「T6a」，將該部分程序執行時間發送到執行時間估計算出部15。之後，執行跟蹤再生部14無條件轉移到部分程序「8」，到達其「部分程序終止命令」「branch⑶」。接著，分支歷史記錄比特序列的第六個分支歷史記錄比特「1」表示條件變量「D」為「真」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(D)[Τ]，，的部分程序「9」，到達作為其「部分程序終止命令」的「branch⑶」。然後，執行跟蹤再生部14讀取部分程序「9」的部分程序執行時間估計值「T9」，將該部分程序執行時間發送到執行時間估計算出部15。然後，分支歷史記錄比特序列的第七個分支歷史記錄比特「1」表示條件變量「D」為「真」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(D)[Τ]，，的部分程序「9」，到達作為其「部分程序終止命令」的「branch⑶」。然後，執行跟蹤再生部14讀取部分程序「9」的部分程序執行時間估計值「T9」，將該部分程序執行時間發送到執行時間估計算出部15。並且，分支歷史記錄比特序列的第八個分支歷史記錄比特「0」表示條件變量「D」為「假」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(D)[F]，，的部分程序「10」，到達作為其「部分程序終止命令」的「branch(E)」。然後，執行跟蹤再生部14讀取部分程序「10」的部分程序執行時間估計值「T10」，將該部分程序執行時間發送到執行時間估計算出部15。接著，分支歷史記錄比特序列的第九個分支歷史記錄比特「1」表示條件變量「E」為「真」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(E)[Τ]，，的部分程序「11」，到達作為其「部分程序終止命令」的「funcLend」。之後，執行跟蹤再生部14從堆棧取出部分程序「6」，到達作為該第二部分程序終止命令的「branch(A)」。然後，執行跟蹤再生部14讀取部分程序「6」的第二部分程序執行時間估計值「T6b」，將該部分程序執行時間發送到執行時間估計算出部15。然後，分支歷史記錄比特序列的第十個分支歷史記錄比特「0」表示條件變量「A」為「假」的情況，因此執行跟蹤再生部14轉移到「部分程序開始命令」為「branch(A)[F]，，的部分程序「3」，到達作為其「部分程序終止命令」的「maiiKend」。在該時刻結束程序執行。然後，執行跟蹤再生部14讀取部分程序「3」的部分程序執行時間估計值「T3」，將該部分程序執行時間發送到執行時間估計算出部15。進行這種處理，執行跟蹤再生部14從部分程序表依次獲取與部分程序ID對應的部分程序執行時間估計值，由此如下那樣的部分程序執行序列被發送到執行時間估計算出部15。mainstart—[Tl]—A(1)—[T2]-B(I)^[T4]-A(I)^[T2]-B(O)^[T5]—C(1)—[&]—flrcl:start—[8]—D(I)—[9]—D(I)—[9]—D(O)—[10]—E(I)—[Til]—flrcl:arl—閲一A(O)—[T3]—main:end在此，[Tx]表示其部分程序執行時間(圖5的部分程序表的「部分程序執行時間估計值」)，A(I)表示條件變量「Α」為「真」的情況，A(O)表示條件變量「Α」為「假」的情況。此外，實際上，執行跟蹤再生部14每次從部分程序表讀取部分程序執行時間估計值時，都依次發送到執行時間估計算出部15。通過進行這樣的執行跟蹤再生處理(S104)，能夠正確地再生實際執行對象程序時的所有執行命令序列。並且，還產生以下次要的效果通過進行執行跟蹤再生處理，能夠正確地計算各種程序執行簡檔信息(各命令的執行頻率、各函數調用的執行頻率、各條件分支命令的分支概率等)。(執行時間估計算出處理)在步驟S104之後，執行時間估計算出部15進行執行時間估計算出處理，即通過將從執行跟蹤再生部14依次發送過來的部分程序執行時間估計值按發送過來的順序進行相加來算出對象程序整體的執行時間估計值610。此外，執行時間估計算出部15也可以根據從執行跟蹤再生部14發送的部分程序執行序列從部分程序表讀取部分程序執行時間估計值，代入到執行序列，並進行相加，由此算出對象程序整體的執行時間估計值。執行時間估計算出處理的實際當再次記載步驟S104中生成的部分程序執行序列時，形成以下那樣的序列。mainstart—[Tl]—A(1)—[T2]-B(I)^[T4]-A(I)^[T2]-B(O)^[T5]—C(1)—[&]—flrcl:start—[8]—D(I)—[9]—D(I)—[9]—D(O)—[10]—E(I)—[Til]—flrcl:arl—閲一A(O)—[T3]—main:end在此，執行時間估計算出部15對[Tx](部分程序執行時間估計值)依次進行相加，由此與部分程序執行序列對應的程序執行跟蹤的執行時間(對象程序整體的執行時間估計值)形成以下式(1.1)。TotalTime_l=Tl+T2+T4+T2+T5+T6a+T8+T9+T9+T10+Tll+T6b+T3…(1.1)接著，作為分支歷史記錄比特序列的其它例，示出以下的分支歷史記錄比特序列「1001011100」。通過與上述分支歷史記錄比特序列同樣的處理，來從該分支歷史記錄比特序列生成以下那樣的部分程序執行序列。mainstart—[Tl]—A(1)—[T2]-B(O)^[T5]-C(O)^[T7]-A(I)^[T2]—B(0)—[5]—C(l)—[&]—flrclistart^[8]—D①一[9]—D①一[9]—D(O)—[T10]—E(O)—[12]—nain:aid因而，與該分支歷史記錄比特序列對應的程序執行跟蹤的執行時間(執行時間估計值)形成以下式(1.2)。TotalTime_2=Tl+T2+T5+T7+T2+T5+T6a+T8+T9+T9+T10+T12—(1.2)(第一實施方式的效果)通過第一實施方式算出的執行時間估計值具有與在步驟S102中算出的部分程序執行時間估計值相同高的精度。並且，在步驟S103中生成的分支歷史記錄比特序列與程序執行命令數相比明顯少，因此能夠在遠遠小於實際的程序執行時間的處理時間內算出執行時間估計。另外，在步驟S102中估計部分程序的執行時間，即使是利用循環、條件分支命令等來多次執行相同部分程序那樣的對象程序，也只要算出一次量的執行時間即可，因此與從開頭起對對象程序進行執行時間估計的情況相比能夠以短時間的處理完成該估計。(第二實施方式)圖9是表示第二實施方式所涉及的執行時間估計裝置的結構例的圖。在圖9中，對與第一實施方式相同的要素附加相同的附圖標記而省略說明。執行時間估計裝置Ib(I)具有循環信息提取部21、程序執行歷史記錄信息生成部22以及估計算出後面所說明的第二種循環的執行時間的第二種循環執行時間估計算出部23。並且，執行時間估計裝置Ib除了具備第一實施方式中的上述部分程序執行序列以外還具備生成後面所說明的第二種循環執行序列的執行跟蹤再生部14b、和執行時間估計算出部15b，該執行時間估計算出部1根據部分程序執行序列、第二種循環以外的部分程序執行時間估計值和後述的第二種循環執行時間估計值來估計算出對象程序的執行時間。循環信息提取部21具備具有與第一實施方式相同的功能的程序分割部11和部分程序執行時間估計算出部12。並且，循環信息提取部21具有第一種和第二種循環辨別處理部211，該第一種和第二種循環辨別處理部211根據對象程序來辨別後面所說明的第一種循環和第二種循環，將第二種循環ID追加到部分程序表，將辨別的結果生成的第一種循環信息(後面說明)發送到第一種循環聚合部212，或者將第二種循環信息(後面說明)發送到第二種循環次數數據序列生成部221。另外，循環信息提取部21具有第一種循環聚合部212，該第一種循環聚合部212根據第一種循環信息，在部分程序表中進行第一種循環的聚合處理，將第一種循環聚合後的、追加了第二種循環ID後的部分程序表發送到執行時間估計算出部15b。程序執行歷史記錄信息生成部22具有第二種循環ID、生成作為與第二種循環的反覆進行次數成對的信息的序列的第二種循環次數數據序列的第二種循環次數數據序列生成部221以及生成第二種循環以外的部分程序的分支歷史記錄比特序列的分支歷史記錄信息生成部13b。此外，以規定函數覆蓋對象程序(源程序)的一部分，程序執行歷史記錄信息生成部22執行所覆蓋的對象程序，由此實現第二種循環次數序列生成部221和分支歷史記錄信息生成部13b(參照圖15來後面詳細說明)。此外，將存儲於圖2的存儲裝置170等中的執行時間估計程序加載到RAM153中而由CPU151執行，從而實現圖9示出的各部ll、12、13b、14b、15b、21、22、23、211、212、221。首先，在說明具體的處理之前，參照圖4的對象程序來說明第二實施方式中的處理的原理以及概要。在以下示出的條件ZlD滿足Zlη(Ζ2UΖ3)時，循環(反覆進行處理)內的條件分支命令不保存該部分的分支歷史記錄信息而能夠進行正確的執行跟蹤再生。條件Zl在循環內部除了循環繼續條件命令以外不包含if-else分支命令等條件分支命令。在此，循環繼續條件命令是指是否跳出循環的條件分支命令。條件Z2循環的反覆進行次數為常數次。條件循環的反覆進行次數為固定次。在此，「循環的反覆進行次數為常數次」是指確定的循環次數在整個對象程序全體中不變(常數)的情況。另外，「循環的反覆進行次數為固定次」是指特定的循環次數利用變量進行規定而在循環內不變但是在循環外有可能發生變化的情況。在圖4示出的對象程序的例子中，對應於「main」函數的「循環1」的循環(下面，將對應於「循環η」的「循環」記載為「循環n」)沒有滿足條件Zl(在循環內存在if-else分支命令)。此外，"fund"函數的「循環2」滿足條件Zl0在「循環2」的「D=i<M」中「M」為常數值的情況下，即「M」在對象程序整體中不變的情況下，條件Z2成立。在「循環2」的「D=i<M」中處於即使「M」為變量值也在循環處理中不變化而固定的情況(固定次數循環不變)的情況下，條件Z3成立。特別是，條件往往被用於如圖像處理那樣將圖像的高度、寬度作為變量而提供的情況，存在很多這些變量與循環的反覆數直接對應的情況。當參照從圖4示出的對象程序導出的分支歷史記錄比特序列(參照第一實施方式)時，「循環2」的循環次數為兩次(參照條件變量「D」)。此時在「循環2」中ZlηΖ2成立的情況下(下面記載為「第一種循環」)，M=2為常數，顯然在圖5示出的部分程序表中到達「branch(D)」的狀態下必須執行「D(1)—[T9]—D(I)—[T9]—D(O)—[T10]—E」。因而，循環2的執行時間能夠在式(2.1)中示出。因此，分支歷史記錄信息生成部Hb在分支歷史記錄比特序列中不需要記錄與「branch(D)」有關的比特序列。T_L2=T9X2+T10—(2.1)另外，在ZlΠD成立的情況下(下面記載為「第二種循環」)，例如在執行「循環202」之前求得「M=2」的值、且變量「M」在「循環2」的執行中不變化的情況下，第二種循環次數數據序列生成部221將第二種循環ID(由第一種和第二種循環辨別處理部211發出的ID)與此時的第二種循環次數作為第二種循環次數數據序列而進行保存。然後，第二種循環執行時間估計算出部23根據該第二種循環次數數據序列例如用式(2.2)來估計第二種循環的處理時間(後面說明詳細處理)。T_L2=T9XM+T10...(2.2)此時「Μ」為在第二種循環次數數據序列中記錄的第二種循環次數。在這種情況下，也同樣地，分支歷史記錄信息生成部1在分支歷史記錄比特序列中不需要記錄作為與第二種循環有關的條件分支命令的「branch(D)，，的分支歷史記錄。在上述兩種情況中，不需要將循環內的分支歷史記錄信息記錄到分支歷史記錄比特序列中，因此在存在多個滿足這種條件的循環(第一種循環和第二種循環)的程序中，能夠期望能夠大幅減少分支歷史記錄比特序列長度。因而，第一種循環和第二種循環各自聚合為一個命令，能夠從部分程序的程序分割邊界點去除內部的條件分支命令(循環繼續條件命令)。接著，參照圖9按照圖10來說明第二實施方式所涉及的程序執行時間估計方法。圖10是表示第二實施方式所涉及的程序執行時間估計方法的處理的流程的流程圖。(循環信息提取處理)接著，循環信息提取部21進行循環信息提取處理(S201)。循環信息提取部21將步驟S201的結果、即生成的第一種循環信息和第二種循環信息發送到程序執行歷史記錄信息生成部22。並且，循環信息提取部21將步驟S201的結果、即第一種循環聚合後的、被寫入第二種循環ID的部分程序表發送到執行跟蹤再生部14b、第二種循環執行時間估計算出部23以及執行時間估計算出部15b。後面說明第一種循環信息和第二種循環信息，第一種循環信息為對應於第一種循環的條件分支命令(循環繼續條件命令)，第二種循環信息為第二種循環ID與部分程序ID成對的信息。在此，參照圖9按照圖11記載循環信息提取處理的詳細。圖11是表示第二實施方式所涉及的循環信息提取處理的流程的流程圖。首先，循環信息提取部21的程序分割部11進行程序分割處理(SlOl)，部分程序執行時間估計算出部12進行部分程序執行時間估計算出處理610。這些處理是與上述實施方式相同的處理，因此附加相同的步驟編號而省略說明。接著，循環信息提取部21的第一種和第二種循環辨別處理部211進行第一種循環和第二種循環辨別處理、即辨別在步驟S101、S102中生成的部分程序表中的循環為第一種循環還是第二種循環(S2011)。在此，參照圖12來說明第一種循環和第二種循環辨別處理。圖12是與某一個對象程序中的循環有關的圖，(a)是某一個循環的結構示意圖，(b)是表示從具有(a)示出的結構的循環生成的部分程序的結構的例子的表。在此，圖12的(b)中的「WW」和「YY」表示適當的處理。條件「X」表示是否繼續循環的條件(循環繼續條件命令)。另外，「cl」、「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」為例進行說明時，在循環開始前的代碼「Cl」中，該「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」。22此外，第一種和第二種循環辨別處理部211(圖9)將作為對應於第一種循環的條件分支命令的第一種循環信息發送到第一種循環聚合部212(圖9)和分支歷史記錄信息生成部1(圖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_L20並且，按照式(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)示出生成第二種循環次數數據序列和分支歷史記錄比特序列的函數。S卩，程序執行歷史記錄信息生成部22如圖16的(b)的下劃線所示那樣對圖16的(a)中的第二種循環的循環繼續條件命令(下劃線部)進行覆蓋。圖16的(b)的下劃線的函數為圖16的(C)示出的函數。並且，圖16的(C)示出的函數具有以下功能對第二種循環的循環次數進行計數，所計數的第二種循環次數已經被記錄在第二種循環次數數據序列中，當與具有相同第二種循環ID的近前的第二種循環次數一致時(即，在循環次數沒有變化時)，不將所計數的循環次數寫入到第二種循環次數數據序列(後面詳細進行說明)。在步驟S2031之後，程序執行歷史記錄信息生成部22執行圖16的(b)所示那樣覆蓋的對象程序(S203》，由此圖9示出的第二種循環次數數據序列生成部221啟動，所啟動的第二種循環次數數據序列生成部221生成第二種循環次數數據序列。在此，將成為對象的第二種循環反覆進行的次數、即第二種循環反覆次數作為例如Wl，250]等那樣的、與循環ID(「01」)成對的信息的序列記錄到第二種循環次數數據序列中。Wl，250]表示具有第二種循環ID「01」的第二種循環反覆進行250次的情況。另外，第二種循環次數數據序列中的第二種循環的反覆次數的初始值為「_1」。將反覆次數的初始值設為「_1」的理由如下還沒有對循環的反覆次數進行計數，因此先臨時放入不可能的值。第二種循環次數數據序列牛成的實際在此，說明第二種循環次數數據序列生成部221中的第二種循環次數數據序列生成的具體例。首先，作為前提設為三個第二種循環(第二種循環ID:「01」、「02」、「03」)存在於對象程序中。然後，首先，設為第二種循環次數數據序列生成部221生成Wl，5]、,、,、、,、、、這種第二種循環數據序列。在此，將構成第二種循環次數數據序列的數據(Wl，5]等)記載為第二種循環次數數據。各第二種循環次數數據所表示的意義是[第二種循環ID、第二種循環次數]。接著，第二種循環次數數據序列生成部221通過對第二種循環次數數據序列進行如下的處理，來減少第二種循環次數數據序列的冗餘性，從而減少數據量。也就是說，第二種循環次數數據序列生成部221在第二種循環次數數據序列中對相同的第二種循環ID進行處理，即在登記到近前的第二種循環次數數據序列中的第二種循環次數與所計數的第二種循環次數的值一致時(即，在第二種循環次數沒有變化時)，不將所計數的第二種循環次數數據寫入到第二種循環次數數據序列。此外，在此為了便於說明，使用從第二種循環次數數據序列刪除對應的第二種循環次數數據的過程來進行說明。當以上述第二種循環次數數據序列為例進行說明時，形成以下那樣的序列。,,{,},、{、},,、{},在此，以中括號包圍的第二種循環次數數據為被刪除的數據。例如，關於第三個第二種循環次數數據，由於第二個第二種循環次數數據(第二種循環ID為「02」之前與它最近的第二種循環次數數據)與其第二種循環次數一致，因此將其刪除。另外，關於第四個第二種循環次數數據，由於第一個第二種循環次數數據(第二種循環ID為「05」之前與它最近的的第二種循環次數數據)與其第二種循環次數一致，因此將其刪除。此外，關於最後的第二種循環次數數據，由於其第二種循環次數與第二種循環ID為「02」之前與它最近的第二種循環次數數據W2，2](第八個數據)不同，因此不將其刪除。通過這種處理，第二種循環次數數據序列生成部221所輸出的第二種循環次數數據序列最終形成如下的序列。、、、、、此外，如上所述，在此，為了說明，第二種循環次數數據序列生成部221生成一次第二種循環次數數據序列之後，刪除之前與它最近的第二種循環ID相同且第二種循環次數一致的第二種循環次數數據，但是在生成第二種循環次數數據序列過程中，第二種循環次數數據序列生成部221是進行以下操作的判斷是否存在之前與它最近的第二種循環ID相同的第二種循環次數，在存在的情況下，不寫入到第二種循環次數數據序列。並且，圖16的(C)示出的函數除了具有生成第二種循環次數數據序列的功能以外還具有生成分支歷史記錄比特的功能。此時，圖16的(c)示出的函數還具有不將第二種循環的循環繼續條件命令的分支歷史記錄比特作為分支歷史記錄比特而記錄的功能。艮口，程序執行歷史記錄信息生成部22執行圖16的(b)示出的覆蓋的對象程序，由此將圖9的分支歷史記錄信息生成部1也啟動。被啟動的分支歷史記錄信息生成部1生成除了第二種循環以外的分支歷史記錄比特序列。也就是說，分支歷史記錄信息生成部1所生成的分支歷史記錄比特序列由於省略了與第二種循環有關的比特，因此形成比特數較少的分支歷史記錄比特序列。並且，利用圖16的(c)示出的函數啟動的分支歷史記錄信息生成部13b生成省略了從第一種和第二種循環辨別處理部211發送過來的第一種循環信息所含的相當於條件分支命令的比特(與第一種循環有關的比特)的分支歷史記錄比特序列。步驟S202的結果是，程序執行歷史記錄信息生成部22將所生成的分支歷史記錄比特序列發送到執行跟蹤再生部14b，將第二種循環次數數據序列發送到第二種循環執行時間估計算出部23。(執行跟蹤再生處理)返回到圖10的說明，在步驟S202之後，執行跟蹤再生部14b根據從循環信息提取部21獲取到的部分程序表以及從分支歷史記錄信息生成部1獲取到的分支歷史記錄比特序列來進行執行跟蹤再生處理(S104b)，生成第二種循環執行序列和部分程序執行序列。下面，說明由第二實施方式中的執行跟蹤再生部14b進行的第二種循環執行序列生成處理。在第二實施方式中的執行跟蹤再生處理中除了生成部分程序執行序列以外還生成第二種循環執行序列。首先，執行跟蹤再生部14b—邊讀出在程序執行歷史記錄信息生成部22中生成的分支歷史記錄比特序列一邊通過與上述實施方式相同的方法生成部分程序執行序列。此外，如上所述，實際上執行跟蹤再生部14b與上述實施方式相同地進行以下動作一邊生成部分程序執行序列一邊將部分程序執行時間估計值依次發送到執行時間估計算出部15b。此時，執行跟蹤再生部14b從上起依次參照在循環信息提取部21中生成的部分程序表(圖13)，提取在第二種循環ID的欄位中存在1以上的值的部分程序(即，在開始命令中具有第二種循環的循環繼續條件命令的部分程序)，將所提取的第二種循環ID追加到第二種循環執行序列的末端。執行跟蹤再生部14b不將表示第二種循環的部分程序的執行時間估計值追加到部分程序執行序列(即，不發送到執行時間估計算出部1)，而是自動地轉移到第二種循環結束之後到達的部分程序，將該部分程序追加到部分程序執行序列。參照圖13的例子，說明第二實施方式所涉及的執行跟蹤再生處理的具體過程。此外，部分程序執行序列與第一實施方式相同，因此省略說明。例如，執行跟蹤再生部14b以與第一實施方式的步驟S104相同的過程來從上起依次參照部分程序表。然後，在圖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))作為部分程序開始命令的部分程序「11」或者「12」。執行跟蹤再生部14b根據分支歷史記錄比特序列來決定轉移到部分程序「11」和「12」中的哪一個。通過這樣的處理，能夠得到下面所記載的效果。如果設為分支歷史記錄信息生成部1不識別第二種循環而生成了分支歷史記錄比特序列，則相當於該第二種循環的比特序列成為「111…0···」。在生成了這樣的分支歷史記錄比特序列的情況下，執行跟蹤再生部14b反覆轉移到部分程序「9」。根據第二實施方式的執行跟蹤再生處理(S104b)，執行跟蹤再生部14b能夠通過省略與相當於第二種循環的部分程序(在此，部分程序「9」)的循環次數相當的轉移，來實現處理的高速化。(第二種循環執行時間估計算出處理)然後，返回到圖10，在步驟S104b之後，第二種循環執行時間估計算出部23根據從第二種循環次數數據序列生成部221獲取到的第二種循環次數數據序列、從執行跟蹤再生部14b獲取到的第二種循環執行序列以及從循環信息提取部21輸出的部分程序表的部分程序執行時間估計值來進行第二種循環執行時間估計算出處理(S20;3)。此時，參照第二種循環次數數據序列的第二種循環ID來從部分程序表提取對應的第二種循環的部分程序執行時間估計值。此外，第二種循環執行時間估計算出處理為與步驟Sl(^b的程序執行時間估計算出處理並行地進行的處理。在此，具體地說明第二種循環執行時間估計算出處理。首先，第二種循環執行時間估計算出部23從開頭起依次讀取從第二種循環次數數據序列生成部221獲取到的第二種循環次數數據序列。在此，下面將此時讀取的第二種循環次數數據設為「當前參照第二種循環次數數據」。接著，第二種循環執行時間估計算出部23從開頭起依次讀取由執行跟蹤再生部14b生成的第二種循環執行序列(第二種循環ID號的執行順序序列)。在此，將此時讀取的第二種循環執行序列中的第二種循環ID號設為循環執行序列中的「當前第二種循環ID」。第二種循環執行時間估計算出部23在每次算出第二種循環執行序列中的各循環的執行時間時，「當前第二種循環ID」移動到下一個第二種循環ID，但是在「當前參照第二種循環次數數據」移動到下一個第二種循環次數數據的情況下，存在不移動而不變化的情況。具體地說，在「當前第二種循環ID」與「當前參照第二種循環次數數據」的第二種循環ID一致的情況下，移動到下一個第二種循環次數數據，但是在不一致的情況下不移動。後面參照圖17來說明具體的處理。在「當前參照第二種循環次數數據」的第二種循環ID與「當前第二種循環ID」一致的情況下，第二種循環執行時間估計算出部23使用部分程序表中的部分程序執行時間估計值來用式(2.2)算出第二種循環執行時間估計值，將該第二種循環執行時間估計值與對應的第二種循環ID作為成對的信息保存到未圖示的第二種循環執行時間表，將所算出的第二種循環執行時間估計值發送到執行時間估計算出部15b。在此，第二種循環執行時間表是指用於將所算出的第二種循環執行時間臨時保存到RAM153(圖2)等的表。當在圖13的例子中將第二種循環次數設為「兩次」時，第二種循環執行時間估計算出部23將第二種循環執行時間估計值計算為T9X2+T10。在「當前參照第二種循環次數數據」的第二種循環ID與「當前第二種循環ID」的第二種循環ID不一致的情況下，第二種循環執行時間估計算出部23將記錄在「第二種循環執行時間表」中的值設為第二種循環執行時間。之後，第二種循環執行時間估計算出部23後移一個「當前參照循環次數數據」的第二種循環次數數據序列內的參照位置、即第二種循環執行時間估計算出部23在第二種循環次數數據序列中將「當前參照循環次數數據」的下一個第二種循環次數數據作為當前參照循環次數數據而讀取，同樣地算出第二種循環執行時間估計值。然後，第二種循環執行時間估計算出部23反覆進行第二種循環執行時間估計值的算出處理直到讀取所有第二種循環次數數據序列。下面，示出第二種循環執行時間估計算出處理的具體例。第二種循環執行時間估計算出處理的實際接著，參照圖17來具體地說明第二種循環執行時間估計算出部23(圖9)的處理。首先，從第二種循環次數數據序列生成部221(圖9)對第二種循環執行時間估計算出部23輸入上述第二種循環次數數據序列,,,,,，從執行跟蹤再生部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獲取第二種循環次數數據序列,,,,,中的開頭的第二種循環次數數據，將該第二種循環次數數據Wl，5]設為當前參照第二種循環次數數據。接著，當前參照第二種循環次數數據中的第二種循環ID「01」與當前第二種循環ID「01」一致(判斷的欄位)，因此，第二種循環執行時間估計算出部23使用第二種循環次數數據Wl，5]的第二種循環次數「5」以及部分程序表中的第二種循環的部分程序執行時間估計值來算出第二種循環執行時間估計值「5Xtl」。在此，「tl」是第二種循環ID「01」的部分程序執行時間估計值。此外，如式(2.2)所示，原本需要使用對應的部分程序開始命令為「真」時的部分程序執行時間估計值以及部分程序開始命令為「假」時的部分程序執行時間估計值來計算第二種循環執行時間估計值，但是為了避免說明變得複雜，在圖17中的說明中，設為MXt(M是第二種循環次數，t是對應的部分程序執行時間估計值)。接著，第二種循環執行時間估計算出部23將所算出的第二種循環執行時間估計值「5Xtl」與當前第二種循環ID「01」對應地寫入到第二種循環執行時間表，同時將所算出的第二種循環執行時間估計值「5Xtl」發送到執行時間估計算出部15b(圖9)。執行時間估計算出部1將從第二種循環執行時間估計算出部23發送過來的第二種循環執行時間估計值按發送的順序進行相加。然後，當前第二種循環ID「01」與當前參照第二種循環次數數據中的第二種循環ID一致，因此，第二種循環執行時間估計算出部23將下一個當前參照第二種循環次數數據更新為作為下一個第二種循環次數數據的W2，8]。然後，第二種循環執行時間估計算出部23進行行602中的處理，但是該處理是將行601中的處理應用於第二種循環ID「02」的處理，因此省略說明。在行602的處理中，當前第二種循環ID「02」與當前參照第二種循環次數數據中的第二種循環ID—致，因此，第二種循環執行時間估計算出部23將當前參照第二種循環次數數據更新為下一個第二種循環次數數據W3，10]。在行603的處理中，第二種循環執行時間估計算出部23獲取第二種循環執行序列「01，02，02，01，03，03，01，02，03，01，02」中的第三個第二種循環ID「02」，將該第三個第二種循環ID「02」設為當前第二種循環ID。於是可知，當前第二種循環ID「02」與當前參照第二種循環次數數據W3，10]中的第二種循環ID「03」不一致，因此，在此進行著不寫入到上述第二種循環次數數據的處理。因此，第二種循環執行時間估計算出部23從第二種循環執行時間表讀取最近的第二種循環ID「02」的第二種循環執行時間估計值(「8Xt2」)，將所讀取的第二種循環執行時間估計值(「8Xt2」)發送到執行時間估計算出部15b。執行時間估計算出部1將從第二種循環執行時間估計算出部23發送過來的第二種循環執行時間估計值按發送的順序進行相加。然後，當前第二種循環ID「02」與當前參照第二種循環次數數據W3，10]中的第二種循環ID「03」不一致，因此，第二種循環執行時間估計算出部23將當前第二種循環ID「02」更新為下一個第二種循環ID「01」，但是不更新當前參照第二種循環次數數據W3，10]。28行604中，當前第二種循環ID「01」與當前參照第二種循環次數數據W3，10]中的第二種循環ID「03」也不一致，因此，第二種循環執行時間估計算出部23對當前第二種循環ID「01」進行與行603相同的處理，由此從第二種循環執行時間表讀取第二種循環執行時間估計值「5Xtl」，將讀取到的第二種循環執行時間估計值「5Xtl」發送到執行時間估計算出部15b。行605中，當前第二種循環ID「03」與當前參照第二種循環次數數據W3:10]中的第二種循環ID「03」一致，因此，第二種循環執行時間估計算出部23將與行601、602相同的處理應用到第二種循環ID「03」來進行該處理。然後，當前第二種循環ID「03」與當前參照第二種循環次數數據W3，10]中的第二種循環ID「03」一致，因此，第二種循環執行時間估計算出部23將當前參照第二種循環次數數據更新為下一個第二種循環次數數據W2，4]。下面，對行606607也進行相同的處理，第二種循環執行時間估計算出部23將第二種循環執行時間估計值發送到執行時間估計算出部15b。(執行時間估計算出處理)當結束步驟S203的處理時，執行時間估計算出部1將從執行跟蹤再生部14b發送過來的第二種循環次數序列以外的部分程序執行序列(實際上，按部分程序執行序列的順序依次發送過來的部分程序執行時間估計值)與從第二種循環執行時間估計算出部23發送過來的第二種循環執行時間估計值依次進行相加，由此進行執行時間估計算出處理、即算出除了第二種循環以外的對象程序的執行時間的估計值610)。第二種循環以外的執行時間估計算出處理與第一實施方式相同。另外，將從第二種循環執行時間估計算出部23依次發送過來的第二種循環執行時間估計值按發送的順序進行相加來算出與第二種循環有關的執行時間。然後，執行時間估計算出部1將相加後的第二種循環執行時間估計值與第二種循環以外的執行時間估計值進行相加，來算出最終的對象程序的執行時間。此外，執行時間估計算出部15b也可以將第二種循環次數序列以外的部分程序執行時間估計值與第二種循環執行時間估計值分開地進行相加，最後將兩者進行相加，由此算出對象程序的執行時間的估計值。(第二實施方式的效果)程序所執行的總命令步驟數與分支歷史記錄比特序列長度具有較強的相關關係，例如與需要非常龐大的執行時間的對象程序對應的分支歷史記錄比特序列長度也變為龐大的長度，但是能夠通過第二實施方式的步驟S201、步驟S202以及步驟S203的處理來縮減分支歷史記錄比特序列的長度。因而，能夠記錄需運轉第一實施方式中不可能的長時間的程序的完全的執行歷史記錄。此外，執行時間估計算出部15b中的計算量基本上與分支歷史記錄比特序列長度成正比。因而，第二實施方式中的分支歷史記錄比特序列長度的縮減與對象程序的執行時間估計算出處理中的計算時間的縮減直接關聯。S卩，即使是需運轉長時間的對象程序，也能夠縮減其對象程序的執行時間估計所需的時間。由此，在進行處理器結構的設計改進或專用編譯程序的改進時，進行對象程序的執行時間估計不需要時間且能夠高精度地算出，從而能夠有效地對其設計改進效果進行評價。另外，存在很多在某一個特定的第二種循環中、即使其循環的處理區間多次出現、第二種循環次數本身也不會變化的情況。在此，循環的處理區間是指在反覆進行循環次數量之後到跳出循環為止。例如在MPEG(MotionPictureExpertsGroup運動圖像專家組)等運動圖像處理中，反覆執行對於相同圖像大小的處理(其中，圖像大小數據不是常數值而是變量的情況較多)。根據第二實施方式，能夠縮減這樣的運動圖像處理程序的執行時間估計所需的時間。另外，對於有可能在循環外變更反覆次數而難以作為一個部分程序而集中處理的循環(第二種循環)，也根據反覆次數的序列等與其它部分程序分開地估計循環的執行時間，由此能夠作為一個部分程序而進行處理，能夠在較短的處理時間內估計程序的執行時間。(第三實施方式結構)圖18是表示第三實施方式所涉及的執行時間估計裝置的結構例的圖。在圖18中，對與上述其它實施方式相同的要素附加相同的附圖標記而省略說明。執行時間估計裝置Ic(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等中的執行時間估計程序加載到RAM153中而由CPU151執行，由此實現圖18示出的各部ll、12、13、13c、14、14b、15b、22、23、31、32、33、211、212、221、311、331、332。在說明具體的處理之前，說明第三實施方式中的處理的概要。在對象程序中包含含有if-else分支命令的循環的情況下，該循環不滿足第二實施方式中的上述條件Z1，因此即使循環次數為常數值(條件U)或者固定值(條件^3)，也無法直接應用第二實施方式中的第一種循環聚合處理和第二種循環聚合處理。但是，根據後面所說明的方法，能夠計算各if-else分支命令的分支概率。如果使用該分支概率來計算if-else分支塊整體的處理時間的統計性預測值，則產生能夠應用第二實施方式中的循環的分支聚合處理的情況，從而能夠增加第二實施方式中的分支歷史記錄比特序列長度的縮減效果。下面，將不滿足條件Z1而滿足條件Z2或者條件的循環記載為「第三種循環」。下面，說明具體的安裝方法。接著，參照圖18按照圖19來說明第三實施方式所涉及的程序執行時間估計方法。圖19是表示第三實施方式所涉及的程序執行時間估計方法的流程的流程圖。(分支概率信息提取處理)首先，分支概率信息提取部31進行分支概率信息提取處理，即算出所有if-else分支命令的分支概率(S301)。下面，參照圖18按照圖20來說明分支概率信息提取處理的具體的處理。圖20是表示第三實施方式所涉及的分支概率信息提取處理的流程的流程圖。首先，分支概率信息提取部31的程序分割部11進行程序分割(SlOl)，部分程序執行時間估計算出部12進行部分程序執行時間估計算出處理610。然後，分支概率信息提取部31的分支歷史記錄信息生成部13進行分支歷史記錄信息生成處理(S103)，執行跟蹤再生部14進行執行跟蹤再生處理(S104)。步驟SlOlS104的各處理與上述實施方式的處理相同，因此附加相同的步驟編號而省略詳細說明。進行步驟S104的執行跟蹤再生處理的結果是，生成部分程序執行序列。在此，設為生成在第一實施方式中使用過的以下部分程序執行序列。mainstart—[Tl]—A(1)—[T2]-B(I)^[T4]-A(I)^[T2]-B(O)^[T5]—C(1)—[&]—flrcl:start—[8]—D(I)—[9]—D(I)—[9]—D(O)—[10]—E(I)—[Til]—flrcl:arl—閲一A(O)—[T3]—main:end<條件變量分類概率算出處理〉接著，條件變量分類概率算出部311按以下所記載的過程，進行條件變量分類概率算出處理，即根據所生成的部分程序執行序列來算出條件變量分類概率(S3011)。首先，條件變量分類概率算出部311脫離部分程序執行序列中的各分支歷史記錄比特以及與該各分支歷史記錄比特對應的條件變量，生成如下的序列。A(I)B(I)A(I)B(O)C(I)D(I)D(I)D(O)E(I)A(O)然後，條件變量分類概率算出部311通過按條件變量分類來分開地乘以各條件變量的真假的頻率來求出分支概率。從上述部分程序執行序列的例子算出的條件變量分類分支概率(所有條件分支命令的分支概率)成為以下那樣的序列。P(A)=2/3(「直」=兩次、『『假」=一次)P⑶=1/2(「直」=一次、『『假」=一次)P(C)=1/1(「直」=一次、『『假」=零次)p(D)=2/3(「真」=兩次、「假」=一次)p(E)=1/1(「真」=一次、「假」=零次)此外，除了這種結構以外也可以利用使用直接計算分支概率的現有方法的計算部來代替這種結構。圖21是表示包含第三種循環的其它例的對象程序的圖，圖22是表示從圖21示出的對象程序生成的部分程序表的例子的圖。在此，當關注branchCJ)與branch(H)時，將條件「J」為真(branch(J)「Τ」)的概率設為「P(J)」(0彡P(J)彡1)，將條件「H」為真(branch(H)「Τ」)的概率設為"P(H)，，(0彡ρ(Η)彡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。根據圖M的對象程序例以及與圖M的對象程序例對應的圖25的部分程序表，來具體地說明多重if-else聚合處理。圖M是表示包含第三種循環的對象程序的例子的圖，圖25是表示從圖M示出的對象程序生成的部分程序表的例子的圖。此外，圖25示出的部分程序表為由分支概率信息提取部31生成的表。圖M中的「循環3」為與第三種循環對應的循環(變量「K」為常數值或者在「循環3」的執行中不變)。當位於「循環3」內部的if-else分支命令中的條件「H」為真(T)的概率為h(=ρ(Η))(0彡h彡1)時，用以下式(3.1)來近似循環3的執行時間。在分支概率信息提取處理中能夠通過上述方法來求出概率h。T_L3=(T21+hXT23+(l-h)XT24)XK+T22...(3.1)式(3.1)是以下計算式根據每次反覆圖M中的「循環3」時必須執行的部分程序的執行時間「T21」、條件「H」為「真」(概率h)時的執行時間「T23」以及條件「H」為「假」(概率l_h)時的執行時間「T24」的簡單的概率加權之和(hXT23+(l-h)XT24)，來估計出執行一次「循環3」時的執行時間。如果循環次數「K」為常數值，則循環3的循環執行時間估計算出值在該階段中能夠作為常數值進行處理(即，執行時間估計裝置Ic在該處理之後將該循環作為第一種循環進行處理)，如果「K」在循環外為變量而在循環內為固定的值，則能夠通過第二實施方式中的處理來算出循環執行時間估計值(即，執行時間估計裝置Ic在該處理之後將該循環作為第二種循環進行處理)。具體地說，多重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，=jXT45+(l-j)XT46...(3.2)將使部分程序「45」和「46」聚合為「45』」的部分程序ID「45』」新保存到部分程序執行時間估計值一欄內，由此if-else聚合部331生成圖沈的(a)示出的對部分程序「45」和「46」進行if-else聚合處理而得到的部分程序表。並且，如圖沈所示，if-else聚合部331同時將圖22中部分程序終止命令為「branch(J)，，的部分程序ID「43」也替換為「ReduCe_B_J」，該「ReduCe_B_J，，表示是"branch(J)」已被聚合的命令。在此，圖沈是進行了聚合處理的部分程序表的例子，(a)表示對「J」進行if-else聚合處理而得到的結果，(b)表示對(a)的結果進行相鄰聚合處理而得到的結果，(c)表示對「H」進行if-else聚合處理而得到的結果，(d)表示對(c)的結果進行相鄰聚合處理而得到的結果。接著，相鄰聚合部332進行相鄰聚合處理。相鄰聚合處理是指以下處理將上述那樣部分程序終止命令不是if-else分支命令的部分程序與作為部分程序開始命令而具有該部分程序終止命令的其它部分程序進行聚合。具體地說，圖沈的(a)中的部分程序ID「43」的部分程序終止命令與部分程序ID「45』，，的部分程序開始命令相同，因此第三種循環聚合部32對它們進行相鄰聚合處理，由此形成圖沈的(b)的部分程序「43』」那樣的形式。下面，if-else聚合部331對條件「H」也同樣地進行if-else聚合處理來生成圖26的(c)示出的部分程序表，並且相鄰聚合部332通過進行相鄰聚合處理來生成圖沈的(d)示出的部分程序表。在該時刻中，如果圖21中的「循環6」的循環繼續條件命令中的式「G=i<K」的「K」為常數次，則能夠作為第一種循環對圖沈的(d)示出的部分程序表進行處理(能夠聚合為第一種循環)，如果「K」為固定次，則能夠作為第二種循環對圖沈的(d)示出的部分程序表進行處理(能夠聚合為第二種循環)。返回到圖19，步驟S302之後的處理與上述說明的實施方式的處理相同，因此省略說明。此外，在步驟S202的程序執行歷史記錄信息生成處理中與第二實施方式同樣地進行對象程序的覆蓋，但此時插入的函數使用從多重if-else聚合部33發送過來的聚合信息、從第一種和第二種循環辨別處理部211發送過來的第一種循環信息以及第二種循環信息，以插入不輸出與在步驟S302、步驟S201中進行聚合而成的部分程序對應的分支歷史記錄比特的函數的形式來進行覆蓋。(第三實施方式的效果)根據第三實施方式，使用各if-else分支命令的分支概率來計算if-else塊整體的處理時間的統計預測值，由此能夠加大第二實施方式中的分支歷史記錄比特序列長度的縮減效果。(第四實施方式結構)圖27是表示第四實施方式所涉及的執行時間估計裝置的結構例的圖。執行時間估計裝置Id(I)具有分支歷史記錄信息提取部31、執行跟蹤再生部Hc以及執行時間估計算出部15，但是它們的功能與上述實施方式相同，因此附加相同的附圖標記來省略說明。執行時間估計裝置Id還具有多重循環聚合部41和分支歷史記錄信息生成部13d，其中，該多重循環聚合部41執行多重循環的聚合處理，該分支歷史記錄信息生成部13d生成在多重循環聚合部41中聚合的部分程序以外的分支歷史記錄比特序列。多重循環聚合部41具有if-else聚合部331和相鄰聚合部332，它們的功能與上述實施方式中的功能相同，因此附加相同的附圖標記來省略說明。多重循環聚合部41還具有進行第四種循環(後述)的聚合處理的第四種循環聚合部411。此外，多重循環聚合部41具有以下功能將作為所聚合的部分程序ID與對應的條件分支命令(所聚合的if-else分支命令、循環繼續條件命令)成對的信息的聚合信息發送到分支歷史記錄信息生成部13d。此外，將存儲於圖2的存儲裝置170等中的執行時間估計程序加載到RAM153中而由CPU151執行，由此實現圖27示出的各部ll、12、13、13d、14、15、31、41、311、331、332、411。首先，在說明具體的處理之前說明第四實施方式中的處理的概要。在記載於第三實施方式中的技術中，以該技術有時無法進行多重循環結構的聚I=IO例如，如圖觀示出的對象程序的例子那樣，有時在「循環4」內部包含作為第三種循環的「循環5」。在此，圖觀是表示包含第四種循環(後述)的對象程序的例子的圖。在決定「循環5」的反覆數的變量「Y」如圖觀示出的對象程序那樣在近前的循環中進行更新(存在在執行「循環4」時「Y」發生變化的可能性)的情況下，為了估計「循環4」的執行時間，需要各個「Y」的值的信息(「循環5」的第二種循環次數數據序列)，因此以記載於第一第三實施方式中的技術無法進行該雙重循環整體的聚合。但是，在以下示出的條件下(條件Xlη條件X2)，即使是多重循環，也能夠正確地估計其「平均」執行時間。條件Xl在循環內部恰好存在一個「循環繼續條件命令」。條件X2在循環塊內部不包含不滿足條件Xl的循環。在此，「循環繼續條件命令」是指決定是否繼續循環處理的分支。例如在圖觀中，在「循環4」中條件「P」為唯一的循環繼續條件命令，在「循環5」中條件「Q」為唯一的循環繼續條件命令。作為不適合條件Xl的例子，例如可舉出在具有結束條件的「for」循環、「while」循環的內部包含「break」語句或者「return」語句的情況。另外，條件X2是指能夠在循環內部包含滿足條件Xl的循環的情況，是用於處理多重循環結構的條件。下面，將滿足(條件Xiη條件似)的循環記載為「第四種循環」。接著，參照圖27按照圖四來說明第四實施方式所涉及的程序執行時間估計方法。圖四是表示第四實施方式所涉及的程序執行時間估計方法的流程的流程圖。(概率信息提取處理)首先，分支概率信息提取部31進行在第三實施方式3中說明的分支概率信息提取處理(S301)。步驟S301與第三實施方式中說明的處理相同，因此省略說明。接著，多重循環聚合部41進行多重循環聚合處理(S401)。(多重循環聚合處理)在此，參照圖27按照圖30來說明多重循環聚合處理的詳細的處理。圖30是表示第四實施方式所涉及的多重循環聚合處理的流程的圖。此外，在圖30中對與上述實施方式相同的處理附加相同的步驟編號來省略說明。此外，多重循環聚合部41具有與上述第一種和第二種循環辨別處理部211(圖9)相同的功能，由於具有該功能，因此多重循環聚合部41不對被辨別為第二種循環的循環進行以下步驟S4011S4016的處理。多重循環聚合部41對部分程序表中的所有多重循環執行步驟S3022S4015的處理(S4011)。首先，當多重循環聚合部41的if-else聚合部331進行if-else聚合處理時(S3022)，多重循環聚合部41的相鄰聚合部332進行相鄰聚合處理(S302!3)。步驟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。多重循環聚合處理的實際使用圖觀示出的對象程序以及圖31示出的與圖28的對象程序對應的部分程序表來說明多重循環聚合處理的實際。如上所述，變量「X」在循環4的執行中不變，變量「Y」在循環5的執行中不變。圖32示出表示此時的條件「S」、「Q」以及「R」的分支概率的表。此時，能夠用以下式(4.1)、(4.2)來計算圖觀的「循環4」以及「循環5」的平均反覆次數。C_L4mean=s/(l_s)...(4.1)C_L5mean=q/(l_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)XC_L4mean—(4.3)T_L5=(T33+rXT35+(l-r)XT36)XC_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」(相當於圖觀的「循環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」是圖觀的「循環5」中的平均反覆次數(式2))。同樣地，第四種循環聚合部411也同樣地對圖34的(b)中的部分程序「31』」、「32」(相當於圖觀的「循環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是表示第五實施方式所涉及的執行時間估計裝置的結構例的圖。執行時間估計裝置Ig(I)具有程序分割部11、部分程序執行時間估計算出部12、分支歷史記錄信息生成部13、1北、執行跟蹤再生部14、Hc以及執行時間估計算出部15，它們的功能與上述實施方式相同，因此附加相同的附圖標記來省略說明。執行時間估計裝置Ig還具有部分程序執行頻率算出部81和函數聚合部82，其中，該部分程序執行頻率算出部81算出作為部分程序執行序列中的各部分程序的出現頻率的部分程序執行頻率，該函數聚合部82根據部分程序執行時間估計值以及部分程序執行頻率來進行函數的聚合處理。也就是說，圖35示出的執行時間估計裝置Ig具有以下結構在圖27示出的執行時間估計裝置Id中，條件變量分類概率算出部311被替換為部分程序執行頻率算出部81，多重循環聚合部41被替換為函數聚合部82。另外，分支歷史記錄信息生成部13d具有以下功能使用從函數聚合部82發送過來的聚合信息和對象程序來生成分支歷史記錄比特序列。此外，將存儲於圖2的存儲裝置170等中的執行時間估計程序加載到RAM153中而由CPU151執行，由此實現圖35示出的各部ll、12、13、13d、14、14c、15、81、82。首先，在說明具體的處理之前說明第五實施方式中的處理的概要。在此，圖36是示出在循環內包含「break」語句以及「return」語句的對象程序的例子的圖。例如，圖36示出的對象程序在「循環10」內部存在「break」語句，在「循環11」內部存在「return」語句，因此兩者都不是第四種循環，無法使用記載於上述實施方式中的技術來進行聚合。針對這種對象程序，能夠使用記載於本實施方式中的技術來聚合包含圖36示出的「循環10」和「循環11」的函數。接著，參照圖35按照圖37來說明第五實施方式所涉及的程序執行時間估計方法。圖37是表示第五實施方式所涉及的程序執行時間估計方法的流程的流程圖。在圖37中，步驟SlOlS105的處理與上述實施方式相同，因此省略說明。在步驟S104的執行跟蹤再生處理之後，部分程序執行頻率算出部81進行部分程序執行頻率算出處理之後(S701)，函數聚合處理部72進行函數聚合處理(S702)。然後，分支歷史記錄信息生成部13d根據從函數聚合部82獲取到的聚合信息以及對象程序來進行生成分支歷史記錄比特序列的分支歷史記錄信息生成處理(S10;3e)。以後的處理與圖四相同，因此省略說明。部分程序執行頻率算出處理的實際接著，使用圖38示出的與圖36的對象程序對應的部分程序表來說明部分程序執行頻率算出處理的實際。圖38是表示描述了部分程序執行頻率的信息的部分程序表的例子的圖。在此，將「部分程序執行頻率」定義為「部分程序執行序列，，中的各部分程序的出現頻率。也就是說，在部分程序的條件分支中根據「True」和「i^alse」的發生頻率算出部分程序執行頻率。此外，開頭為分支命令的部分程序的部分程序執行頻率與第三實施方式中說明的分支概率的計算式的「真假的頻率」相同。條件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)是進行了函數fimc4聚合處理的例子，(b)是進行了部分程序「63」的聚合處理的例子，(c)是聚合後的最終部分程序表的例子。用以下式(5.1)來定義「部分程序全執行時間估計值」。「部分程序全執行時間估計值」=「部分程序執行時間估計值」X「部分程序執行頻率」…(5.1)於是，能夠作為「函數內的部分程序全執行時間估計值的總和」來計算「函數的全執行時間估計值」。但是，在此設為「函數內的部分程序」不包含函數調用命令。例如，該時刻的main函數包含調用fimc4的部分程序，因此在這種狀態下無法計算函數的全執行時間估計值。在此，根據圖38，函數fimc4的全執行時間估計值為以下式(5.2)。Total_func4=C65XT65+C66XT66+C67XT67+C68XT68+C69XT69···(5.2)因而，能夠用以下式(5.3)來計算「函數的平均執行時間估計值」。「函數的平均執行時間估計值」=「函數的全執行時間估計值」/「函數執行頻率」…(5.3)在此，「函數執行頻率」是在開始命令中具備該函數的start的部分程序的執行頻率。例如，能夠用以下式(5.4)來計算圖36中的函數func4的平均執行時間估計值。T_func4=Total_func4/C65—(5.4)在使用上述計算方法算出函數fimc4的平均執行時間估計值之後，部分程序表能夠如聚合了函數func4的圖39的(a)那樣。接著，當對包含所聚合的函數fimc4的函數調用的部分程序「63」進行聚合時，成為圖39的(b)示出的部分程序表。於是，main函數的平均執行時間估計值也能夠使用同樣的方法(式(5.5))來計笪弁。Total_main=C60XT60+C61XT61+C62XT62+C63，XT63，+C64XT64...(5.5)因而，最終，能夠將部分程序表聚合為圖39的(c)示出的表。此外，main函數僅被調用一次，因此C60=1。函數聚合部82將聚合函數而得到的部分程序表(圖39)發送到執行跟蹤再生部14c。另外，將關於與所聚合的函數對應的部分程序的信息(聚合信息)從函數聚合部82發送到分支歷史記錄信息生成部13e。分支歷史記錄信息生成部13d生成沒有描述聚合信息所包含的部分程序的分支歷史記錄比特的分支歷史記錄比特序列(S103d)。以後的處理與上述實施方式相同，因此省略說明。39(第五實施方式的效果)根據第五實施方式，如果是不存在遞歸函數調用(例如在函數內調用自己的函數的情況等)的程序，則一定能夠將全程序聚合為一個部分程序。(第六實施方式)首先，參照圖40來說明第六實施方式中的方法。圖40是表示反覆執行對象程序中的代碼時的代碼執行時間的示意圖，(a)是應用了第二實施方式的例子，(b)是應用了第四實施方式的例子。記載於第二實施方式至第四實施方式中的任一個技術都能夠正確地估計對象程序整體的執行時間。因而，如果僅以正確地估計對象程序整體的執行時間為目的，則第四實施方式的安裝可以說是分支歷史記錄比特序列長度的縮減效果最大，在所需的存儲量、執行時間預測所需的計算時間方面最佳的。但是，在第四實施方式的安裝中，在所有循環中採用平均處理時間，因此在程序執行中無法再現由複雜的條件分支引起的局部的執行時間的波動。也就是說，在反覆執行相同代碼區域「A」的情況下，如圖40的(a)所示，代碼區域「A」的執行時間由於複雜的條件分支而在每次執行時產生波動。利用記載於第二實施方式的技術，能夠完全再現該執行時間的波動，而反映到對象程序的執行時間估計值中。與此相對，在記載於第四實施方式的技術中，如圖40的(b)所示，使所有的處理平均化來算出執行時間估計值，因此無法完全再現局部的執行時間(局部執行時間)的波動。該局部執行時間的平均化作用例如在以包含處理器和外部裝置(存儲器、設備驅動器、網絡埠、多處理器系統中的處理器之間通信等)的系統整體的模擬為目的的情況下成為問題。也就是說，為了系統整體的模擬，系統總線上的數據流量、存儲器存取流量的局部的定時的再現變得較重要，基於該觀點，在僅應用第四實施方式的情況下，可以說局部定時再生精度較低。在此，局部定時再生精度是指表示如圖40的(a)所示那樣實際上執行代碼區域的情況下的波動程度的精度。如圖40的(a)所示，如果能夠準確地估計各執行時間的波動，則局部定時再生精度較高，相反地，如圖40的(b)所示，在各執行時間的波動消失的情況下，局部定時再生精度較低。在此，當基於局部定時再生精度的觀點來整理第一實施方式至第四實施方式所涉及的技術時，在第一實施方式以及第二實施方式中，沒有平均化作用(沒有算出平均的處理)而能夠嚴格地再生局部定時。另外，在第三實施方式中，在估計第三種循環的執行時間時，由於進行平均化處理，因此局部定時再生精度降低一些。並且，在第四實施方式中，由於在算出第四種循環的反覆次數、估計執行時間時進行平均化處理，因此局部定時再生精度在第一第四實施方式中變得最低。在第六實施方式中，提供靈活應對模擬的目的(即局部定時再生精度的要求度)的差異的執行時間估計裝置le。(結構)圖41是表示第六實施方式所涉及的執行時間估計裝置的結構例的圖。如圖41所示，執行時間估計裝置Ie(I)是將以下結構追加到兼備第一第四實施40方式的要素的結構的裝置。此外，在圖41中對與上述實施方式相同的結構要素附加相同的附圖標記並省略其詳細說明。執行時間估計裝置Ie(1)具有分支概率信息提取部31、程序執行歷史記錄信息生成部22、執行跟蹤再生部14b、第二種循環執行時間估計算出部23以及執行時間估計算出部15b，但是它們的功能與上述實施方式中的功能相同，因此附加相同的附圖標記並省略說明。此外，第二種循環信息提取部21e具有上述實施方式中的第一種和第二種循環辨別處理211的功能中的第二種循環辨別功能以及第二種循環ID的發出功能。另外，執行時間估計裝置1e還具有if-e1se塊執行時間偏重度算出部51、if_e1se聚合控制部52、循環執行時間偏重度算出部53以及第四種循環聚合控制部M。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具有算出循環執行時間偏重度的功能。後面說明循環執行時間偏重度。第四種循環聚合控制部M將循環執行時間偏重度與通過輸入部156(圖2、輸入的循環偏重度閾值進行比較，輸出第四種循環聚合禁止標誌，該第四種循環聚合禁止標誌為是否禁止第四種循環聚合部411e所進行的第四種循環聚合處理的信息。另外，多重循環聚合部41e的各部331e、332e、411e除了具有上述實施方式所述的功能以外還具有以下功能根據從if-else聚合控制部52、第四種循環聚合控制部M發送過來的if-else聚合禁止標誌、第四種循環聚合禁止標誌來控制if-else聚合處理、多重循環聚合處理的執行。此外，將存儲於圖2的存儲裝置170等中的執行時間估計程序加載到RAM153中而由CPU151執行，由此實現圖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-TfXMc...(6.1)在步驟S501之後，循環執行時間偏重度算出部53對所有循環進行算出循環執行時間偏重度的循環執行時間偏重度算出處理(S502)。在第四實施方式所述的技術中，在聚合的循環的反覆次數的偏差較大並且循環的執行頻率較高且循環的平均執行時間較長的情況下，在聚合該循環時，招致局部定時再生精度的降低。因此，作為循環的反覆次數的偏重度，將反覆次數分布的方差與循環執行頻率的積定義為循環的「循環執行時間偏重度」。例如，將循環L執行N次，在將各自的反覆次數設為(L1、L2、…Ln)而將平均執行時間設為Tmean時，循環執行時間偏重度算出部53通過式(6.2)來算出循環L中的循環執行時間偏重度。循環執行時間偏重度越大局部定時再生精度變得越低。[式1]權利要求1.一種執行時間估計方法，利用對程序的執行時間進行估計的執行時間估計裝置來執行，該執行時間估計方法的特徵在於，上述執行時間估計裝置進行以下步驟從上述程序提取將條件分支命令和函數調用命令中的至少一個作為邊界點分割出的部分程序；算出各部分程序的執行時間並保存到存儲部；將上述各部分程序的開始命令、終止命令以及所算出的部分程序的上述執行時間相關聯地保存到上述存儲部；生成分支歷史記錄比特序列並保存到上述存儲部，該分支歷史記錄比特序列是與執行上述程序時的上述條件分支命令有關的真假序列；根據上述分支歷史記錄比特序列來生成描述有上述部分程序的執行順序的上述部分程序執行序列；以及根據上述部分程序執行序列來將上述部分程序的執行時間進行相加。2.一種執行時間估計方法，其特徵在於，進行以下步驟在權利要求1中的上述部分程序反覆進行規定次數的循環的情況下，在上述循環內部不包含上述條件分支命令並且上述循環中的部分程序的反覆次數在上述程序中不變時，進行如下聚合對上述循環內的部分程序的執行時間乘以上述反覆次數來算出循環執行時間，並將所算出的上述循環執行時間設為一個上述部分程序的執行時間；以及在上述分支歷史記錄比特序列中，將與同進行了上述聚合的循環對應的部分程序相關聯的上述真假序列概括為一個真假信息。3.一種執行時間估計方法，其特徵在於，在權利要求1中的上述部分程序反覆進行規定次數的循環的情況下，在上述循環內部不包含上述條件分支命令並且上述循環中的部分程序的反覆次數在各個上述循環中不變時，進行以下步驟生成各循環的反覆次數的序列；對上述循環內的部分程序的執行時間乘以上述反覆次數的序列中的反覆次數來算出循環的執行時間；將所算出的各上述循環的執行時間進行相加；以及在上述分支歷史記錄比特序列中，不描述與對應於上述循環的部分程序相關聯的上述真假序列。4.根據權利要求2或者3所述的執行時間估計方法，其特徵在於，進行以下步驟在權利要求1中的上述部分程序反覆進行規定次數的循環的情況下，在上述循環內部包含if-else分支命令時，算出上述if-else分支命令為真的概率以及上述if-else分支命令為假的概率；相加如下兩個值對上述if-else分支命令為真時執行的部分程序的執行時間乘以上述if-else分支命令為真的概率而得到的值；以及對上述if-else分支命令為假時執行的部分程序的執行時間乘以上述if-else分支命令為假的概率而得到的值；以及進行如下聚合將上述if-else分支命令為真時執行的上述部分程序以及上述if-else分支命令為假時執行的上述部分程序設為一個部分程序。5.一種執行時間估計方法，其特徵在於，在權利要求1中的上述部分程序是反覆進行規定次數的循環的情況下，在上述循環是僅由包含一個作為決定是否繼續上述循環的分支的循環繼續條件命令的循環構成的多重循環時，該執行時間估計方法進行以下步驟算出該循環內的if-else分支命令為真的概率以及上述if-else分支命令為假的概率；進行如下聚合根據上述概率，從內側的循環起依次算出上述循環的平均執行時間，將所算出的上述循環的平均執行時間作為一個上述部分程序的執行時間；以及在上述分支歷史記錄比特序列中，不描述與進行了上述聚合的循環對應的序列。6.根據權利要求1所述的執行時間估計方法，其特徵在於，在具有多個上述部分程序的函數中，進行以下步驟算出上述部分程序的出現頻率；通過對所算出的上述部分程序的上述執行時間乘以上述部分程序的出現頻率，來算出上述函數內的上述部分程序的全部執行時間估計值；關於上述函數內的上述部分程序，通過算出上述部分程序的全部執行時間估計值的總和來算出函數的全部執行時間估計值；以及在上述分支歷史記錄比特序列中，不描述與算出了上述全部執行時間估計值的函數對應的序列。7.一種執行時間估計方法，在權利要求1所述的上述部分程序反覆進行規定次數的循環的情況下，對該循環進行第一部分程序聚合處理和第二部分程序聚合處理，該執行時間估計方法的特徵在於，在上述第一部分程序聚合處理中，在上述循環中的第一循環為多重循環且在上述程序中至少存在一個上述第一循環的情況下，進行以下步驟，其中，該多重循環僅包含含有一個循環繼續條件命令的循環，該循環繼續條件命令是決定在上述第一循環內部是否繼續進行反覆處理的分支在該第一循環內部含有if-else分支命令的情況下，算出上述if-else分支命令為真的概率以及上述if-else分支命令為假的概率；進行如下聚合根據上述概率，從內側的循環起依次算出上述第一循環的平均執行時間，將所算出的上述第一循環的平均執行時間設為一個上述部分程序的執行時間；以及在上述分支歷史記錄比特序列中，不描述與進行了上述聚合的部分程序對應的序列，在上述第二部分程序聚合處理中，第二循環為在上述第二循環內部不包含上述條件分支命令且反覆次數在各個上述第二循環中不變的循環、並且在上述程序中至少存在一個上述第二循環的情況下，進行以下步驟生成各上述第二循環中的部分程序的反覆次數的序列；將對應於上述第二循環的部分程序的執行時間乘以上述反覆次數的序列中的反覆次數來算出循環的執行時間估計值；將所算出的各上述第二循環的執行時間估計值進行相加；以及在上述分支歷史記錄比特序列中，不描述對應於上述循環的序列。8.根據權利要求7所述的執行時間估計方法，其特徵在於，進行以下步驟算出if-else執行時間偏重度，該if-else執行時間偏重度是由if-else分支命令的真假而引起的上述部分程序的執行時間的偏重度；以及在上述if-else執行時間偏重度為規定值以上的情況下，不執行上述第一部分程序聚合處理。9.根據權利要求8所述的執行時間估計方法，其特徵在於，上述if-else執行時間偏重度為對如下兩個執行時間的差的絕對值乘以上述if-else分支命令的執行次數而得到的值上述if-else分支命令為真時的部分程序的執行時間；以及上述if-else分支命令為假時的部分程序的執行時間。10.根據權利要求7所述的執行時間估計方法，其特徵在於，進行以下步驟根據各上述第一循環的反覆次數的偏重度來算出循環執行時間偏重度；以及在上述循環執行時間偏重度大於規定值的情況下，不執行上述第二部分程序聚合處理。11.根據權利要求10所述的執行時間估計方法，其特徵在於，上述循環執行時間偏重度為將上述第一循環內的各循環中的反覆次數的方差、上述循環的反覆次數以及上述循環的平均執行時間進行相乘而得到的值。12.根據權利要求1至11中的任一項所述的執行時間估計方法，其特徵在於，上述執行時間估計裝置為裝載了單處理器的計算機。13.根據權利要求1至11中的任一項所述的執行時間估計方法，其特徵在於，上述執行時間估計裝置為裝載了多處理器的計算機，並行地算出多個程序的執行的估計時間。14.根據權利要求13所述的執行時間估計方法，其特徵在於，上述程序為通信同步並且與其它程序協同地被執行的程序，上述部分程序包含通信同步部分程序，該通信同步部分程序是指示與其它程序之間的通信同步的程序，上述執行時間估計裝置在根據上述分支歷史記錄比特序列生成上述部分程序的執行序列時，在成為處理對象的上述部分程序為上述通信同步部分程序的情況下，根據上述通信同步部分程序的種類，來對構成上述多處理器的處理器的執行狀態進行更新。15.一種執行時間估計程序，使計算機執行權利要求1至11中的任一項所述的執行時間估計方法。16.一種執行時間估計程序，使計算機執行權利要求12所述的執行時間估計方法。17.一種執行時間估計程序，使計算機執行權利要求13所述的執行時間估計方法。18.一種執行時間估計裝置，估計程序的執行時間，其特徵在於，具有程序分割部，其從上述程序中提取將條件分支命令和函數調用命令中的至少一個作為邊界點而分割出的部分程序；部分程序執行時間估計算出部，其算出各部分程序的執行時間，將上述各部分程序的開始命令、終止命令以及所算出的部分程序的上述執行時間相關聯地保存到上述存儲部；分支歷史記錄信息生成部，其生成分支歷史記錄比特序列並保存到上述存儲部，該分支歷史記錄比特序列是與執行上述程序時的上述條件分支命令有關的真假序列；執行跟蹤再生部，其根據上述分支歷史記錄比特序列來生成描述有上述部分程序的執行順序的上述部分程序執行序列；以及執行時間估計算出部，其根據上述部分程序執行序列來將上述部分程序的執行時間進行相加。全文摘要提供一種執行時間估計方法、執行時間估計程序以及執行時間估計裝置，其特徵在於具有程序分割部(11)，其從對象程序中提取由條件分支命令、函數調用命令分割的部分程序；部分程序執行時間估計算出部(12)，其算出各部分程序的執行時間，使各部分程序的開始命令、終止命令、以及所算出的部分程序的執行時間對應；分支歷史記錄信息生成部(13)，其生成分支歷史記錄比特序列，該分支歷史記錄比特序列是執行對象程序時的條件分支命令的真假的序列；執行跟蹤再生部(14)，其根據分支歷史記錄比特序列來生成部分程序的執行序列；以及執行時間估計算出部(15)，其根據部分程序的執行序列來對部分程序執行時間進行相加。文檔編號G06F11/28GK102144222SQ200980134349公開日2011年8月3日申請日期2009年6月23日優先權日2008年7月2日發明者一色剛,國枝博昭,小林直人申請人:國立大學法人東京工業大學