[發(fā)明專利]執(zhí)行時間估計方法、執(zhí)行時間估計程序以及執(zhí)行時間估計裝置

有效

• 申請?zhí)枺?/td>: 200980134349.1
• 申請日: 2009-06-23
• 公開（公告）號: CN102144222A
• 公開（公告）日: 2011-08-03
• 發(fā)明（設計）人: 一色剛;國枝博昭;小林直人
• 申請（專利權）人: 國立大學法人東京工業(yè)大學
• 主分類號: G06F11/34
• 分類號: G06F11/34;G06F11/28
• 代理公司: 北京林達劉知識產(chǎn)權代理事務所(普通合伙) 11277
• 代理人: 劉新宇

1.一種執(zhí)行時間估計方法，利用對程序的執(zhí)行時間進行估計的執(zhí)行時間估計裝置來執(zhí)行，該執(zhí)行時間估計方法的特征在于，

上述執(zhí)行時間估計裝置進行以下步驟：

從上述程序提取將條件分支命令和函數(shù)調(diào)用命令中的至少一個作為邊界點分割出的部分程序；

算出各部分程序的執(zhí)行時間并保存到存儲部；

將上述各部分程序的開始命令、終止命令以及所算出的部分程序的上述執(zhí)行時間相關聯(lián)地保存到上述存儲部；

生成分支歷史記錄比特序列并保存到上述存儲部，該分支歷史記錄比特序列是與執(zhí)行上述程序時的上述條件分支命令有關的真假序列；

根據(jù)上述分支歷史記錄比特序列來生成描述有上述部分程序的執(zhí)行順序的上述部分程序執(zhí)行序列；以及

根據(jù)上述部分程序執(zhí)行序列來將上述部分程序的執(zhí)行時間進行相加。

2.一種執(zhí)行時間估計方法，其特征在于，進行以下步驟：

在權利要求1中的上述部分程序反復進行規(guī)定次數(shù)的循環(huán)的情況下，在上述循環(huán)內(nèi)部不包含上述條件分支命令并且上述循環(huán)中的部分程序的反復次數(shù)在上述程序中不變時，進行如下聚合：對上述循環(huán)內(nèi)的部分程序的執(zhí)行時間乘以上述反復次數(shù)來算出循環(huán)執(zhí)行時間，并將所算出的上述循環(huán)執(zhí)行時間設為一個上述部分程序的執(zhí)行時間；以及

在上述分支歷史記錄比特序列中，將與同進行了上述聚合的循環(huán)對應的部分程序相關聯(lián)的上述真假序列概括為一個真假信息。

3.一種執(zhí)行時間估計方法，其特征在于，

在權利要求1中的上述部分程序反復進行規(guī)定次數(shù)的循環(huán)的情況下，在上述循環(huán)內(nèi)部不包含上述條件分支命令并且上述循環(huán)中的部分程序的反復次數(shù)在各個上述循環(huán)中不變時，進行以下步驟：

生成各循環(huán)的反復次數(shù)的序列；

對上述循環(huán)內(nèi)的部分程序的執(zhí)行時間乘以上述反復次數(shù)的序列中的反復次數(shù)來算出循環(huán)的執(zhí)行時間；

將所算出的各上述循環(huán)的執(zhí)行時間進行相加；以及

在上述分支歷史記錄比特序列中，不描述與對應于上述循環(huán)的部分程序相關聯(lián)的上述真假序列。

4.根據(jù)權利要求2或者3所述的執(zhí)行時間估計方法，其特征在于，

進行以下步驟：

在權利要求1中的上述部分程序反復進行規(guī)定次數(shù)的循環(huán)的情況下，在上述循環(huán)內(nèi)部包含if-else分支命令時，算出上述if-else分支命令為真的概率以及上述if-else分支命令為假的概率；

相加如下兩個值：對上述if-else分支命令為真時執(zhí)行的部分程序的執(zhí)行時間乘以上述if-else分支命令為真的概率而得到的值；以及對上述if-else分支命令為假時執(zhí)行的部分程序的執(zhí)行時間乘以上述if-else分支命令為假的概率而得到的值；以及

進行如下聚合：將上述if-else分支命令為真時執(zhí)行的上述部分程序以及上述if-else分支命令為假時執(zhí)行的上述部分程序設為一個部分程序。

5.一種執(zhí)行時間估計方法，其特征在于，

在權利要求1中的上述部分程序是反復進行規(guī)定次數(shù)的循環(huán)的情況下，在上述循環(huán)是僅由包含一個作為決定是否繼續(xù)上述循環(huán)的分支的循環(huán)繼續(xù)條件命令的循環(huán)構成的多重循環(huán)時，該執(zhí)行時間估計方法進行以下步驟：

算出該循環(huán)內(nèi)的if-else分支命令為真的概率以及上述if-else分支命令為假的概率；

進行如下聚合：根據(jù)上述概率，從內(nèi)側(cè)的循環(huán)起依次算出上述循環(huán)的平均執(zhí)行時間，將所算出的上述循環(huán)的平均執(zhí)行時間作為一個上述部分程序的執(zhí)行時間；以及

在上述分支歷史記錄比特序列中，不描述與進行了上述聚合的循環(huán)對應的序列。

6.根據(jù)權利要求1所述的執(zhí)行時間估計方法，其特征在于，

在具有多個上述部分程序的函數(shù)中，進行以下步驟：

算出上述部分程序的出現(xiàn)頻率；

通過對所算出的上述部分程序的上述執(zhí)行時間乘以上述部分程序的出現(xiàn)頻率，來算出上述函數(shù)內(nèi)的上述部分程序的全部執(zhí)行時間估計值；

關于上述函數(shù)內(nèi)的上述部分程序，通過算出上述部分程序的全部執(zhí)行時間估計值的總和來算出函數(shù)的全部執(zhí)行時間估計值；以及

在上述分支歷史記錄比特序列中，不描述與算出了上述全部執(zhí)行時間估計值的函數(shù)對應的序列。