Patent ID: 8448140
Filing Date: 2013-05-21
Classification: G06F

Abstract:
1. An execution time estimation method performed by an execution time estimation device which estimates an execution time of a program, comprising the steps, performed by the execution time estimation device, of: extracting, from the program, a plurality of partial programs which are obtained by partitioning the program using at least one of a conditional branch instruction and a function call instruction as a boundary point, wherein at least one partial program of the plurality of partial programs includes a loop which is repeated a constant number of times; calculating an execution time of each partial program and storing the calculated execution time in a storage section, wherein, for the at least one partial program, calculating an execution time includes performing a first partial program degeneration processing and a second partial program degeneration processing with respect to the loop; in the first partial program degeneration processing, in the second partial program degeneration processing, storing a leading instruction and an end instruction of the each partial program, and the calculated execution time of each of the partial programs, in the storage section, such that the leading instruction, the end instruction, and the execution time are associated with each other; if the program is executed, generating a branch history bit sequence which is a sequence of “True” and “False” on the conditional branch instruction, and storing the generated branch history bit sequence in the storage section but skipping a write of a sequence corresponding to the first loop and the second loop, in the branch history bit sequence; generating a partial program execution sequence in which an execution order of the partial programs is written, based on the branch history bit sequence; and adding up the execution times of the partial programs, based on the partial program execution sequence.