Abstract:
An apparatus for evaluating a performance of a program includes: a storage unit for storing the program embedded with a plurality of trace statements; a processor executes a process including: executing the program embedded with a plurality of trace statements cyclically; calculating each time intervals of each cycle of execution of the program from a start test program till an end program; and evaluating the performance of the program on the basis of information of the time intervals.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2008-260389 filed on Oct. 7, 2008, the entire contents of which are incorporated herein by reference. 
     FIELD 
     A certain aspect of the embodiments discussed herein relates to an evaluation of a program performance. 
     BACKGROUND 
     In the case of measuring a performance of a computer or a program, a trace method and a profiler method have been know as a method for investigating bottle necks in a computer or a program. 
     In the trace system, trace statements (a kind of print statements) are embedded before and after an interval in the program that the user wants to measure (hereinafter, measurement interval). By execution of the trace statement, executed times are obtained and a time lag of the execution time of each of the trace statement is calculated. 
     In the profiler method, an event interrupt is periodically generated during execution of the program. By the interruption, a value of a program counter at the point is obtained, and a ratio of the value of the program counter included in the measurement interval is calculated. 
     Note that a technique has been proposed in which an interruption is generated for every one order in a firmware that evaluates a performance of the program, the execution state of the order is simulated by the firmware, and performance information is collected. 
     Further, a technique has been proposed in which a transaction which should be processed is selected and state information is stored during when the transaction is processed by a function unit. 
     Further, a technique has been proposed in which order addresses for starting and finishing of measurement are set, and an execution time of the program is measured by integrating the vale obtained by subtracting an index time from the execution time for every one order of the interval. 
     Above techniques are disclosed in Japanese Laid-open Patent Publication No. 1-145736, Japanese Laid-open Patent Publication No. 11-272519, and Japanese Patent No. 3389745. 
     SUMMARY 
     According to an aspect of an embodiment, an apparatus for evaluating a performance of a program by embedding a plurality of trace statements, the apparatus including: a storage unit for storing the program embedded with the plurality of trace statements, each of the trace statements including a instruction for outputting trace records which identify time when and portions where the trace statements are executed in the program; a processor for evaluating the performance of the program in accordance with a process including: executing the program embedded with the plurality of trace statements cyclically and iteratively while selecting one or two of the trace statements at random for each cycle of executing the program wherein the instruction in the trace statements is activated so as to output a trace record and the instruction in the rest of the trace statements is deactivated so as not to output another trace record; calculating each time intervals required by the program to run through the section between adjacent two trace statements by statistically analyzing the outputted trace records; and evaluating the performance of the program on the basis of the time intervals. 
     The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
     It is to be understood that both the forgoing general description and the following detailed description are exemplary and explanatory and are not respective of the invention, as claimed. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a configuration diagram showing an example of a program performance measurement device according to an embodiment of the invention. 
         FIG. 2  is an illustration diagram of a program performance measurement processing that is executed in the program performance measurement device of  FIG. 1 . 
         FIGS. 3A ,  3 B and  3 C are illustration diagrams of the program performance measurement processing that is executed in the program performance measurement device of  FIG. 1 . 
         FIGS. 4A ,  4 B and  4 C are illustration diagrams of the program performance measurement processing. 
         FIGS. 5A and 5B  are illustration diagrams of the program performance measurement processing in the case of using a trace counter. 
         FIG. 6  is a flowchart of the program performance measurement processing executed in the program performance measurement device of  FIG. 1 . 
         FIG. 7  is a flowchart of a trace data output processing that is executed in step S 11  of  FIG. 6 . 
         FIG. 8  is a flowchart of a learning data generation processing that is executed in step S 12  of  FIG. 6 . 
         FIG. 9  is a flowchart of a learning data generation processing that is executed in step S 12  of  FIG. 6 . 
         FIG. 10  is a process flowchart of a hidden trace estimation processing that is executed in step S 13  and an estimation processing of a processing time of a measurement interval that is executed in step S 14  of  FIG. 6 . 
         FIG. 11  is an illustration diagram of the program performance measurement processing of  FIG. 10 . 
         FIGS. 12A ,  12 B,  12 C and  12 D are illustration diagrams of the program performance measurement processing of  FIG. 10 . 
         FIG. 13  is an illustration diagram of the program performance measurement processing of  FIG. 10 . 
         FIGS. 14A ,  14 B,  14 C,  14 D,  14 E and  14 F are illustration diagrams of the program performance measurement processing of  FIG. 10 . 
         FIG. 15  is a process flowchart of the estimation processing of a processing time of a measurement interval that is executed in step S 14  of  FIG. 6  in the case of using a trace counter. 
         FIG. 16  is an illustration diagram of the program performance measurement processing of  FIG. 15 . 
         FIGS. 17A ,  17 B,  17 C and  17 D are illustration diagrams of the program performance estimation measurement processing of  FIG. 15 . 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
       FIG. 1  is a configuration diagram showing an example of a program performance measurement device according to an embodiment of the present invention. 
     The program performance measurement device  1  of the embodiment is equipped with a measurement object server  1  and an analysis server  2 . The measurement object sever  1  is a computer that is a measuring object or a computer in which a program as a measurement object is executed. The analysis server  2  is a computer that analyzes a measurement result of the measurement object server  1 . 
     The measurement object server  1  is equipped with a benchmark program  11 , a measured program  12 , a file system  15 , a random number generation unit  13 , and a trace output unit  14 . The file system  15  is equipped with a trace data accumulation unit  16 . Note that as concrete examples of the measured program, there are included an OS (operating system), a middleware, an application program, and the like. 
     The analysis server  2  is equipped with a parameter estimation unit  21 , a learning data generation unit  22 , and a learning data accumulation unit  23 . The parameter estimation unit  21  is equipped with a hidden trace estimation unit  24  and an interval time estimation unit  25 . 
     Note that the hidden trace unit  24  can be eliminated in the case where the execution number of a trace statement (a kind of print statement) is measured. 
     Further, the measurement object server  1  and the analysis server  2  may be provided as one server or computer. 
     The measurement object sever  1  generates a set of trace data. The measurement object server  1  generates a set of trace data by executing the benchmark program  11 . 
     The benchmark program  11  is a program that is executed for applying the load a load for performance measurement. For example, the benchmark program  11  starts the execution when an instruction for executing the program (execution # 1 ) is inputted. 
     A plurality of trace statements are preliminarily embedded in the measured program  12  as described below. By executing the trace statement, the trace data obtained by the execution of the measured program  12  is outputted to the file system  15 . 
     The random number generation unit  13  is instructs the trace output unit  14  to output the trace data at random. The random number generation unit  13  generates a random number every time when executing the trace statement, and inputs the generated random number in the trace output unit  14 . The random number will be described below with reference to  FIG. 3A  and  FIG. 3B . 
     The trace output unit  14  outputs the trace data to the file system  15  in accordance with the output of the random number generation unit  13 . The trace output unit  14  once writes the trace data in a memory when output of the trace data is required, and outputs the trace data to the file system  15  later as a whole. Herewith, a measurement result is to be not influenced by the output to the file system  15  as far as possible. The trace data will be described below with reference to  FIG. 4A  and  FIG. 5A . 
     In the file system  15 , the trace data is stored in the trace data accumulation unit  16  and is transmitted to the learning data generation unit  22  of the analysis server  2 . Note that, when an instruction (execution # 2 ) for generating learning data is input in the learning data generation unit  22 , the learning data generation unit  22  reads out the trace data from the trace data accumulation unit  16  in response thereto. 
     The analysis server  2  calculates a necessary time for execution for a plurality of measurement intervals based on the set of the trace data from the measurement object server  1 . The measurement interval is determined by a plurality of trace statements as describe below. The analysis server  2  calculates the necessary time by executing a predetermined statistical processing as for the set of the trace data. 
     The learning data generation unit  22  generates a set of the learning data based on the set of the trace data read from the trace data accumulation unit  16 , and stores in the learning data accumulation unit  23 . The learning data will be described below with reference to  FIG. 4B  and  FIG. 5B . 
     Further, the learning data generation unit  22  generates a set of pair data from the set of the generated learning data and stores in the learning data accumulation unit  23 . The pair data is generated by selecting two learning data having a predetermined relationship in the positions of the corresponding trace statements from the set of the learning data as described below with reference to  FIG. 4C . Note that in the case of using a trace counter, it is not necessary to generate the pair data. 
     The learning data and the pair data is data for calculating a processing time of the measured program by a statistical processing described below. The learning data and the pair data of the learning data accumulation unit  23  is read by the parameter estimation unit  21 . 
     When an instruction (execution # 3 ) for calculating the processing time by the statistical processing is inputted, the parameter estimation unit  21  causes the hidden estimation unit  24  to execute a predetermined statistical processing by using the set of the pair data in response thereto. That is, the hidden trace estimation unit  24  reads out the learning data and the pair data from the learning data accumulation unit  23 , estimates a hidden trace by the statistical processing, and transmits the estimated hidden trace to the interval time estimation unit  25 . The statistical processing is executed by using the probability of not sequentially outputting the trace data as described below. Note that the processing in the hidden trace estimation unit  24  is not necessary when a trace counter is used. 
     The interval time estimation unit  25  estimates the processing time as for a processing interval in the measured program  12  which is a measurement object based on the learning data. When a trace counter is not used, the total processing time for all measurement intervals that is an output of the hidden trace estimation unit  24  is used in addition to the learning data. When a trace counter is used, only the learning data is used. 
       FIG. 2  and  FIG. 3  are each an illustration diagram of a program performance measurement processing that is executed in the program performance measurement device of  FIG. 1 . 
     For example, assuming that the trace statements are embedded in the measured program  12  as shown in  FIG. 12 . Further, assuming that a function foo( ) is repeatedly called in the measured program  12  by execution of the benchmark program  11 . When the function foo( ) is called, a function bar( ) and a function baz( ) are called. At this time, the time required for executing the function bar( ) is measured, and the time required for executing the function baz( ) called from the function bar( ) is also measured. Accordingly, trace statements are embedded at the positions shown by the labels of MO, M 1 , M 2 , M 3  of  FIG. 2 . In this case, the trance sentences distinguished by the labels are executed in the order of MO, M 1 , M 2 , M 3  for every calling of the function foo( ). At this time, a measurement interval W 1  is determined as an interval in which a processor is passed through the program between the label M 0  and label M 1 , and W 1  shall be written as W 1 ←(M 0 , M 1 ). In the same manner, written as measurement interval W 2 ←(M 1 , M 2 ), measurement interval W 3 ←(M 2 , M 3 ). Further, a measurement interval W 0  is an interval from the last label M 3  to M 0  that appears in the second time by calling of the subsequent function foo( ). That is, written as measurement interval W 0 ←(M 3 , M 0 ). 
     The above mentioned matters are formally defined. Any position of the measured program  12  shall be expressed by label Ms (s is integer from 0 to S). However, when the benchmark program  11  is executed, in the measured program  12 , the processor shall be passed through the label Ms in the order of suffix s. At this time, the measurement interval is determined as Ws←(M(s−1), Ms) (in the case of 1≦s≦S), and WO←(MS, M 0 ). Further, it is determined that when two labels u=Mi, v=Mj are ascending order, i&lt;j is satisfied, and when descending order, i&gt;j is satisfied. 
       FIG. 3A  and  FIG. 3B  are diagrams in which the labels on the program through which a processor is passed are plotted on a time axis when the measured program  12  is repeatedly driven by executing the benchmark program  11 . Now, since measuring of the time required for executing the function bar( ) is the object, the measurement interval W in which the measurement intervals W 1 , W 2 , W 3  are coupled and the interval W 0  excluding the measurement interval Wi constitute one driving of the measured program  12 . Since a trace statement is embedded at the position of each label, each trace statement shall be expressed by using the label. In the example, four trace statements are executed at the positions of the labels M 0  to M 3  in the measurement interval W. In the example, in the measurement interval W, four trace statements at the positions of the labels M 0  to M 3  are executed. Note that the labels M 01  to M 3  (that is, the trace statements at the positions) shall be expressed by triangles. 
     For example, in  FIG. 3A , when the measured program  12  is driven and the trace statements are executed, the random number generation unit  13  generates a random number r and inputs the random number r in the trace output unit  14 . 
     The value of the random number r shall be within the range of, for example, non negative integer N−1. For example, when the value of the random number r is 0, the trace output unit  14  outputs the trace data, and when the random number r is not 0, the trace output unit  14  does not output the trace data. When the random number r is a uniform random number and occurrence of each non negative integer N−1 is equally possible, trace data is to be randomly outputted only once every N times. 
     In  FIG. 3A , when the trace statement is executed, the random number r is always generated. Among the random numbers generated when each trace statement (that is, portion of label) is executed in the first measurement interval W, assuming that only the random number of the trance sentence of the label M 2  is “0”, and the random numbers of the other labels such as M 0  are “non-0” values that are not 0. In this case, the trace output unit  14  outputs only the trace data of the label M 2  in the first measurement interval W, and does not output other trace data. In  FIG. 3A  and  FIG. 3B , the trace statement (output trace) from which trace data is outputted is shown by a black triangle, and the trace statement from which trace data is not outputted (defective trace or hidden trace) is shown by a white triangle. In the case of not using a trace counter, the trace output unit  14  obtains the execution time t 1  of the trace statement with the label M 2  as a result of executing the trace statement of the label M 2 , and outputs t 1  as output # 1 . In the case of using a trace counter, the trace output unit  14  further obtains the count value h 1  (h 2 ) of the trace counter (shown by trace counter h 1  (h 2 ) in  FIG. 3B ), and further includes this in outputted # 1 . 
     Then, assuming that the random number is “non 0” value except 0 as for every trace statement in the second measurement interval W. In this case, in the measurement interval W, any trace data is not output, and output # 2  can not be obtained (or, made to blank). 
     Further, then, assuming that only the trace statement of label M 1  is “0”, and “non 0” value except 0 as for other label M 0  and the like among the random numbers generated when executing each trace statement in the third measurement interval W. In this case, the trace output unit  14  outputs only the trace data of the label M 1  in the measurement interval W. In the case of not using a trace counter, the trace output unit  14  obtains execution time t 2  of the trace statement with the label M 1 , and outputs t 2  as output # 3 . In the case of using a trace counter, the trace output unit  14  further obtains the count value h 2  of the trace counter and also includes n 2  in output # 3 . 
     Herein, the trace counter will be described. The trace counter is a counter in which a count value is increased by +1 for every time the trance sentence is executed. For example, in  FIG. 3B , since the trance sentence is executed by 7 times during between output # 1  and output # 3 , the count value is increased by h 2 −h 1 =7. 
     The case where trace data is not outputted or one trace data is outputted in one measurement interval W is described above. However, note that there is a case that plurality of trace data is outputted in one measurement interval W. 
     When the measurement program  12  is driven only once, the obtained trace data is not sufficient to estimate the measurement interval. For example, in  FIG. 3A  and  FIG. 3B , only the trace data of the label M 2  is obtained for the first measurement interval W. However, the measured program  12  is repeatedly driven, and in the process, the trace data output in accordance with the random number r is randomly selected. Then, by performing a statistical processing on the imperfect trace data, the defect of the trace data can be complemented. 
     Note that, in order to output the trace data, a certain time is required as shown in  FIG. 3C . Accordingly, it can not be avoided that error times ε are added to the actual processing time of the measurement interval. However, according to the method of the embodiment, the amount that the error caused by the execution of the trace statement is added to the processing time of the measurement interval can be reduced. For example, as shown in  FIG. 3A , assuming that the trace data is output by two times when the measurement interval W including four trace statements is executed by three times, the influence of the error ε can be reduced to 2/12. 
     Herewith, even when the segmented measurement interval W 1  or the like is microscopic, the time for the execution can be measured with a high accuracy. Accordingly, a time for the microscopic (high speed) processing such as, for example, switching of processes, switching of a user application and kernel, or the like can be measured with a high accuracy. Further, since it is not necessary to always output the trace data when executing the trace statement, the time required for the high speed processing in a processor can be measured by using a low speed external device. 
       FIG. 4A  shows an example of a set of the trace data outputted from the trace output unit  14  and accumulated in the trace data accumulation unit  16  in the case of not using a trace counter.  FIG. 5A  shows an example of a set of the trace data that is similarly accumulated in the case of using a trace counter. 
     The set of the trace data includes plurality of trance data. The trace data includes a time when the trace statement is executed and a label showing the position of the executed trace statement as shown in  FIG. 4A  and  FIG. 5A . The time is expressed by an elapsed time from a reference point (time  0 ) (for example, nano second unit). Since only a time lag is concerned in the learning data, it does not mater that when the reference point of the time is. The label is information for specifying the executed trace statement. 
     When using a trance counter, in addition to the time and label as shown in  FIG. 5A , the trace data includes a counter value by the trace counter (in the drawing, simply referred to as “trace counter”). The trace counter value is expressed by the execution number of the trace statement from the reference point as a certain time. Since only the hidden trace number is concerned in the learning data, it does not matter that when the reference point of the trace counter value is. 
     For example, as shown in  FIG. 4A , at the time “1200”, it can be understood that the trace statement of the label M 2  is executed. In the case of using a trance counter, as shown in  FIG. 5A , it can be understood that the trace counter value at the time was “1000”. It can be similarly understood as for the other labels. 
       FIG. 4B  shows an example of the set of the learning data output from the learning data generation unit  22  and accumulated in the learning data accumulation unit  23  in the case of not using a trace counter.  FIG. 5B  shows an example of the set of the learning data similarly accumulated in the case of using a trace counter. 
     The set of the learning data includes plurality of learning data. The learning data shows a time lag between the trace data. That is, in the case of not using a trace counter, the learning data includes a time lag Ti, a start label Bi, and an end label Ei as shown in  FIG. 4B . In the case of using a trace counter, as shown in  FIG. 5B , the learning data further includes a hidden trace number ki. The time lag Ti is a time lag between two trace data that are basis for generating the learning data. The start label Bi is a label formally executed among the two trace data (old execution time). The end label Ei is a label latterly executed among the two trace data (new execution time). Note that the number i is applied in arbitrary order. The hidden trace number ki is a difference of the trace counter values between two trace data that are basis for generating the learning data. 
     For example, the learning data of number 1 is generated from the first and second trace data of the set of the trace data of  FIG. 4A  and  FIG. 5A . Accordingly, the time lag Ti is “120”, the stat label Bi is M 2 , the end label Ei is M 3 , and the hidden trace number ki is “49”. It can be similarly understood as for the other numbers. 
       FIG. 4C  shows an example of the set of the pair data output from the learning data generation unit  22  and accumulated in the learning data accumulation unit  23  in the case of not using a trace counter. Note that the pair data is not accumulated in the case of using a trace counter. 
     The pair data is data which is constituted by pair of learning data in which the start label Bi and the end label Ei are mutually reversed in the set of the learning data of  FIG. 4B . For example, in the set of the learning data of  FIG. 4B , each of the leaning data of i=1 and the learning data of i=5, and the leaning data of i=6 and the learning data of i=7 is pair data. Note that in the case where the start label Bi and the end label Ei are the same, the learning data independently constitutes pair data. For example, when the learning data of i=3 independently constitute pair data. 
     The set of the pair data includes plurality of pair data. The pair data includes an index+, an index−, a time lag Ti±, a label v, and a label u as shown in  FIG. 4C . Note that number i± is arbitrarily applied. The label v and the label u are two labels commonly owned by the pair of the learning data, and the label v and the label u are in ascending order. The index+ shows the number of  FIG. 4B  or  FIG. 5B  of the learning data whose start label is the label u and whose end label is the label v, and in the same manner, the index− shows the number of the learning data whose start label is the label v and whose end label is the label u. The pair data of the number i± shall be described as (i+, i−), and the index+ shall be described as i+, and the index− shall be described as i−. 
     Note that when a pair contains only a single learning data, the index− is defined as blank (nil). Further, the start label Bi and the end label Ei do not lose generality even when handled as descending order. In other words, even when the index+ is defined as blank (nil) and the start label Bi and the end label Ei are handled as ascending order, the same result is obtained. Since the number i in  FIG. 4B  and the number i± of  FIG. 4C  are arbitrarily applied, and the index+ and the index− are introduced for convenience of illustration, it may not be necessary to create the indexes. The time lag (Ti±) is the sum of time lag Ti of the two learning data constituting a pair. 
     For example, the pair data of number 4± is constituted by the learning data of i=6 and the learning data of i=7, and the time lag Ti± is “220”, the label v and the label u are respectively M 0  and M 2 , the index+ is number 6 of the learning data whose start label is label u (M 2 ) and whose end label is the label v (M 0 ), and the index− is number 7 of the learning data whose start label is label v (M 0 ) and whose end label is the label u (M 2 ). 
     Hereinafter, a program performance measurement processing in the program performance measurement device of  FIG. 1  will be described in detail in accordance with a processing flowchart shown in  FIGS. 6 to 10 . 
       FIG. 6  is a flowchart of the program performance measurement processing that is executed in the program performance measurement device of  FIG. 1 . 
     When execution # 1  is input by the user, execution of the benchmark program  11  is started. Herewith, the measured program  12  is repeatedly driven. In the process, a trace data is obtained, and the trace output unit  14  accumulates the trace data in the trace data accumulation unit  16  in accordance with a value of the random number (step S 11 ). Herewith, the set of the trace data shown in  FIG. 4A  or  FIG. 5A  can be obtained. Step S 11  will be described in detail with reference to  FIG. 7 . 
     When execution # 2  is input by the user, the learning data generation unit  22  reads the set of the trace data from the trace data accumulation unit  16 , and generates the learning data having the time lag Ti, start label Bi, end label Ei, between the successive trace data, and accumulates the learning data in the learning data accumulation unit  23  (step S 12 ). Herewith, the set of the learning data shown in  FIG. 4B  or  FIG. 5B  can be obtained. Step S 12  will be described in detail with reference to  FIG. 8 . 
     Next, in the case of not using a trace counter, the learning data generation unit  22  creates pair data from the learning data (step S 13 ). Herewith, the set of pair data shown in  FIG. 4C  can be obtained. Step S 13  will be described in detail with reference to  FIG. 9 . Note that step S 13  is omitted in the case of using a trance counter. 
     When execution # 3  is input by the user, the interval time estimation unit  25  calls the hidden trace estimation unit  24  and causes the hidden trace estimation unit  24  to execute a predetermined processing. That is, in the case of not using a trace counter, the hidden trace estimation unit  24  reads the set of the pair data from the learning data accumulation unit  23 , and calculates the sum of the processing time required for the measuring interval and the processing time required for the interval except the measuring interval from these pair data (step S 14 ). The sum can be calculated by using an expected value of the length of the successive traces which are not output due to using a random number. 
     Step S 14  in the case of not using a trace counter will be described in detail with reference to  FIG. 10 . 
     Then, the interval time estimation unit  25  reads the set of the learning data from the learning data accumulation unit  23 , and estimates the measurement interval and the interval except the measurement interval (step S 15 ). Step S 15  will be described in detail with reference to  FIG. 10  and  FIG. 15 . 
       FIG. 7  is a flowchart of a trace data output processing that is executed in step S 11  of  FIG. 6 . 
     The random number generation unit  13  generates the random number r (hereinafter, referred to as uniform random number r) (step S 21 ). At the time, the value of the uniform random number r shall be an integer of not less than 0 and less than 1/q. Herein, q is a constant number within the interval of [0,1). For example, assuming that q=0.25, 1/q=4. That is, the random number r generates any of {0, 1, 2, 3} at the equivalent probability q=0.25. By using the uniform random number r, the trace can be output by the probability of once every 4 times. 
     The trace output unit  14  examines whether or not the uniform random number=0 (step S 22 ). When the uniform random number=0, the trace output unit  14  outputs the trace data. That is, in the case of not using a trace counter, the trace output unit  14  records the present time and the label M of the executed trace statement in the trace data accumulation unit  16  as shown in  FIG. 4A . On the other hand, in the case of using a trace counter, the trance output unit  14  also records the count value of the trace counter in addition thereto (step S 23 ). Step S 23  is omitted in the case where the uniform random number r=non-0 in step S 22 . 
     In the case of using a trace counter, the parameter estimation unit  21  increments the trace counter (step S 24 ). In the case of not using a trace counter, S 24  is not executed. 
       FIG. 8  is a flowchart of a learning data generation processing that is executed in step S 12  of  FIG. 6 . 
     In  FIG. 8 , the learning data generation unit  22  initializes the sequence number (i), that is, number (i) in the learning data shown in  FIG. 4B  (step S 31 ). That is, i=1. 
     Then, the learning data generation unit  22  takes out the initial (number 0) record (trace data) from the set of the trace data shown in  FIG. 4A  and  FIG. 5A , and sets the record as R 1  (step S 32 ). In the case of not using a trace counter, R 1 =(t 1 , m 1 ), and in the case of using a trace counter, R 1 =(t 1 , m 1 , h 1 ). Further, the learning data generation unit  22  takes out the next (number 1) record from the set of the trace data, and sets the record as R 2  (step S 33 ). In the case of not using a trace counter, R 2 =(t 2 , m 2 ), and in the case of using a trace counter, R 2 =(t 2 , m 2 , h 2 ). Herein, t 1  and t 2  denote time, m 1  and m 2  denote the label M, and h 1  and h 2  denote the count values of the trace counter. 
     Then, the learning data generation unit  22  examines whether or not another record exists in the set of the trace data (step S 34 ). 
     When there is another record (S 34  Yes), the learning data generation unit  22  obtains the time lag Ti=t 2 −t 1  and the hidden trace number ki=h 2 −h 1  as for the taken out record R 1  and record R 2  (step S 35 ), and writes the generated learning data in the learning data accumulation unit  23  as shown in  FIG. 4  B and  FIG. 5B  (step S 36 ). The generated learning data is (i, Ti, m 1 , m 2 ) in the case of not using a trace counter, and is (i, Ti, m 1 , m 2 , Ki) in the case of using a trance counter. Note that m 1  is Bi and m 2  is Ei in  FIG. 4B  and  FIG. 5B . 
     Then, the learning data generation unit  22  sets the sequence number as i+1, and sets the record R 2  as the new record R 1  (step S 37 ). Then, step S 33  and the flowing steps are repeated. 
     Since the aforementioned processing of steps S 33  to S 37  is a generation processing of the learning data, the processing is common for the both of when not using a trace counter and when using a trace counter. 
       FIG. 9  is a flowchart of a pair data generation processing that is executed in step S 13  of  FIG. 6 , and is executed only in the case of not using a trace counter, and is a processing that is not executed in the case of using a trace counter. 
     In the case where there is no another record in step S 34  (S 34  No), the learning data generation unit  22  takes out one learning data (i, Ti, Bi, Ei). However, in the example of  FIG. 9 , it is limited to the learning data whose Bi, Ei are descending order. (step S 38 ). Then, the learning data generation unit  22  examines whether or not the learning data is absence (step S 39 ). In the case where there is no such learning data, (S 39  No) the processing is finished. 
     When there is another learning data (S 39  Yes), the learning data generation unit  22  examines whether or not Bi=Ei as for the taken out learning data i (step S 310 ). 
     In the case of Bi=Ei (S 310  Yes), the learning data generation unit  22  sets the taken out learning data i as the pair data (i, nil) shown in  FIG. 4C , and registers the pair data in the set of the pair data of the learning data accumulation unit  23  (step S 311 ). This corresponds to the pair data which is the pair (3, nil) in the example of  FIG. 4C . 
     In the case of not Bi!=Ei (S 310  No), the learning data generation unit  22  searches the set of the learning data of  FIG. 4B  by using Bi and Ei of the taken out learning data, and finds the learning data (j, Tj, Bj, Ej) that satisfies Bi=Ej and Ei=Bj (step S 312 ). 
     Then, the learning data generation unit  22  examines whether or not the learning data j matched with the conditions of step S 312  is found (step S 313 ). When the learning data is not found (S 313  No), step S 38  and the following steps are repeated. On the other hand, in the case where the learning data matched with the conditions of S 312  is found (S 313  Yes), the learning data generation unit  22  registers the learning data i and the found learning data j in the set of the pair data of the learning data accumulation unit  23  as the pair data (i, j) shown in  FIG. 4C  (step S 314 ). The registered pair data corresponds to the par data except the par data which is the pair ( 5 ,  1 ) in the example of  FIG. 4C . 
       FIG. 10  is a processing flowchart of a hidden trace estimation processing that is executed in step S 13 , a sum calculation processing of the processing time executed in step S 14 , and an estimation processing of the processing time of the measuring interval that is executed in step S 15  of  FIG. 6  in the case of not using a trace counter. 
     Before describing  FIG. 10 , a method for calculating the processing time of the measurement interval in the case of not using a trace counter will be described by using  FIGS. 11 to 13 . 
     First,  FIG. 11  will be described. Assuming that there are (S+1) types of labels Ms (however, s is integer of 0 to S) of {M 0 , M 1 , . . . MS} in the measured program  12 . Assuming that the processing time of the measuring interval (interval time) between the label M(s−1) and the label Ms is Ws (in the case of 1≦s≦S), the interval time between the label MS and the label M 0  is W 0 . Accordingly, the purpose of the hidden trace estimation processing and the estimation processing of the processing time of the measurement interval described in  FIG. 10  is to estimate the processing time Ws. 
     The learning data indicated by the index+ and the index− of the pair data of the number i± is (i+, Ti+, Bi+, Ei+) and (i−, T− Bi−, Ei−). Note that there are relations of u=Bi+=Ei− and v=Ei+=Bi− from the definition of the index. Herein, the time lags Ti+ and Ti− can be described as in  FIG. 11  by using the processing time Ws of the measurement interval. However, in the case of not using a trace counter, the hidden trace numbers k+ and k− are unknown. 
     Since the hidden trance numbers k+ and k− are unknown, a device for obtaining the processing time Ws of the measurement interval is required without using the hidden trace numbers. Consequently, Z=W 0 +W 1 + . . . +WS which is the total processing time of every measurement interval is estimated by adding the sum Ti±=(Ti+)+(Ti−) of the time lag in the pair data to set π of every pair data as shown by calculation (i) and calculation (ii) of  FIG. 11 . The detail method is as shown in  FIG. 11 . As the conclusion, in order to calculate the total processing time Z of every measurement interval, the number of the types of the label (S+1), the size of the pair data set σ, the sum of the time lag of every pair data ΣTi±, the expected value of the hidden trace number E[k] are required. The values can be easily calculated from the pair data except the expected value E[k] of the hidden trace number. 
       FIG. 12  is a calculation example of the expected value [k] of the hidden trace number in the case where a uniform random number r is used in the random number generation unit. 
     For example, as shown in  FIGS. 12A and 12B , by using the provability p(k) of not sequentially outputting k number of traces, the expected value E[k] of the trace number can be theoretically calculated as shown in  FIG. 12C . In this manner, the expected value E[k] of the trace number is expressed by using a parameter which is the provability q of outputting the trace.  FIG. 12D  shows a result of E[k] in accordance with the concrete values of q. 
     As described above, since the expected value E[k] of the hidden trance number can be calculated, the total processing time Z of every measurement interval can be estimated. Herein, the definition of the time lags Ti+ and Ti− of  FIG. 11  will be described again. 
       FIG. 13  shows the definitional formulas shown in  FIG. 11  again. Hereinafter, description is made in accordance with  FIG. 13 . As shown in  FIG. 13 , when the right sides thereof is ordered, it can be described so as to be divided into a constant term which is an integral multiple of the total processing time Z of every measurement interval and terms comprising variables Ws. What is import as the result is that the hidden trace numbers k+ and k− are not included any more. The row vector xi+ and xi− whose element is 0 or 1 showing presence or absence of the variable Ws in the right side can be created one by one from every learning data. Herewith, the regression formulas whose number is corresponding to the number of the learning data can be obtained, and by solving the regression formulas, Ws which is the processing time of the measurement interval can be calculated. 
     In  FIG. 10 , the hidden trace estimation unit  24  adds Ti± to S for every pair (i+, i−) after initializing the value S to 0, (step S 41 ). Further, Z=S/E[k] is obtained by the hidden trace estimation unit  24  (step S 41 ). The processing is a processing for estimating Z which is the total processing time of every measurement interval described in  FIG. 11  and  FIG. 12 . 
     The interval time estimation unit  25  takes out the learning data (i, Ti, Bi, Ei) (step S 43 ), and searches whether or not there is no unprocessed learning data in the set of the learning data of the learning data accumulation unit  23  (step S 44 ). 
     When there is unprocessed learning data (S 44  No), the interval time estimation unit  25  obtains the values xi, yi, bi based on the aforementioned value Z for the taken out learning data (step S 45 ), and thereafter repeats step S 43  and the following steps. The processing is a processing for introducing the regression formula described in  FIG. 13 . 
     When there is no unprocessed learning data (S 44  Yes), the interval time estimation unit  25  performs a multivariate regression analysis on yi=(xi·w)+bi, and calculates the necessary time in the measurement interval (step S 46 ). Herewith, the total processing time of every measurement interval of the measured program  12  can obtain and the necessary time for every measurement interval can be calculated based on the expected value of the number the trace data that is not sequentially output. 
       FIG. 14  is an illustration diagram showing a real processing shown in  FIG. 10 . Note that  FIG. 14  shows an example of the processing of the data shown in  FIG. 4 . 
     As shown in  FIG. 14A , in the case of q= 1/24, E[k]=120 (calculated by  FIG. 12C ). Then, in step S 41 , as shown in  FIG. 14B , the sum S of the time lag is obtained for the four pair data shown in  FIG. 4C . Further, in step S 42 , as shown in  FIG. 14B , total processing time Z of every measurement interval is obtained. 
     Then, in step S 45 , for example, the interval time estimation unit  25  obtains the regression formula y1=(x1·w)+b1 for the learning data of number 1 as shown in  FIG. 14C . Similarly, as shown in  FIG. 14D , the regression formula y2=(x2·w)+b2 for the learning data of number 2 is obtained, and as shown in  FIG. 14E , the regression formula y3=(x3·w)+b3 for the learning data of number 3 is obtained. The regression formula is similarly obtained for other pair data. 
     Then, the interval time estimation unit  25  obtains the result as shown in  FIG. 14F  based on the result of the processing shown in  FIGS. 14C  to E. Note that in  FIG. 14F , as is understood from the comparing of the value y and  FIG. 4B , the result is rearranged in the order of the learning data. 
     Then finally, the interval time estimation unit  25  performs a multivariate regression analysis on the result shown in  FIG. 14F . Herewith, for example, a result such as W 0 =6 (unit time, same in the following) W 1 =1, W 2 =5, W 3 =2 can be obtained. 
       FIG. 15  is a processing flowchart of the estimation processing of the processing time of the measurement interval executed in step S 15 . Note that, as described above, in the case of using a trace counter, step S 13  (hidden trace estimation processing) of  FIG. 6  is omitted. 
     Before illustrating  FIG. 15 , a method for calculating the processing time of the measurement interval in the case of using a trace counter will be described by using  FIG. 16 . 
     In  FIG. 16 , the definition of the process time Ws of the measurement interval is the same as  FIG. 11  and  FIG. 13 . The purpose of the estimation processing of the processing time of the measurement interval illustrated in  FIG. 15  is to estimate the processing time Ws also in the case of using a trace counter. 
     The point that time lags Ti+ and Ti− in the learning data (i+, Ti+, Bi+, Ei+, ki+) and (i−, Ti−, Bi−, Ei−, ki−) are written by using the processing time Ws of the measurement interval is also similar to  FIG. 11 . However, in the case of using a trace counter, the hidden trace numbers k+ and k− are known. 
     Since the hidden trace is known, the regression formula can be created by using the hidden trace. As shown in  FIG. 11 , row vectors xi+ and xi− showing the number of times that each variable Ws appears in the right side of the former formula can be created one by one from every learning data by using the hidden trace numbers ki+ and ki−. Herewith, the regression formula whose number is corresponding to the number of the leaning data is obtained, and the processing time Ws of the measurement interval can be calculated by solving the regression formula. 
     In  FIG. 15 , the interval time estimation unit  25  takes out the learning data (i, Ti, Bi, Ei, ki) (step S 51 ), and examines whether or not there is no unprocessed learning data in the set of the learning data of the learning data accumulation unit  23  (step S 52 ). 
     When there is unprocessed learning data, the interval time estimation unit  25  obtains the values xi, yi, bi for the taken out learning data (step S 53 ), and then, repeats the step S 51  and the following steps. 
     When there is no unprocessed data, the interval estimation unit  25  performs a multivariate regression analysis on yi=(xi·w) and calculates the necessary time in the measurement interval (step S 54 ). Herewith, the necessary time for every measurement interval of the measured program  12  can be calculated based on the hidden trace number that is the number of the trace data that is not sequentially output. 
       FIG. 17  is an illustration diagram showing a real processing shown in  FIG. 15 . Note that  FIG. 17  shows an example of a processing of the data shown in  FIG. 5 . 
     In step S 53  of  FIG. 15 , the interval time estimation unit  25  obtains the regression formula y1=(x1·w) for the learning data of number 1 as shown in  FIG. 17A . Similarly, the regression formula y2=(x2·w) for the learning data of number 2 is obtained as shown in  FIG. 17B , and the value y3=(x3·w) for the learning data of number 3 is obtained as shown in  FIG. 17C . The regression formula for other pair data is similarly obtained. 
     Then, finally, the interval time estimation unit  25  obtains the result such as, for example, W 0 =6, W 1 =1, W 2 =5, W 3 =2 by performing a regression analysis on the result shown in  FIG. 17D . 
     All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and condition, nor does the organization of such examples in the specification relate to a showing of superiority and inferiority of the invention. Although the embodiment of the present inventions have been described in detail, it should be understood that the various changes, substitutions, and alternations could be made hereto without departing from the spirit and scope of the invention.