Statistically based estimate of embedded software execution time

• US 7,007,270 B2
• Filed: 03/05/2001
• Issued: 02/28/2006
• Est. Priority Date: 03/05/2001
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Giusto, Paolo, Martin, Grant Edmund
• Primary Examiner(s): Ingberg, Todd
• Application Number:
  US09/799,643
• Publication Number:
  US 20020166112A1
• Time in Patent Office: 1,821 Days
• Field of Search: 717/127, 717/131, 717/135, 717/148, 717/154, 703/13, 703/22, 702/186, 702/119, 702/123, 702176-178, 718/1, 709223-226, 714/39
• US Class Current: 717/131
• CPC Class Codes: G06F 11/3428 Benchmarking
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3457 Performance evaluation by simulation
• CPC Class Codes: G06F 2201/815 Virtual
• CPC Class Codes: G06F 2201/865 Monitoring of software

Abstract

A statistical approach to estimating software execution times is implemented by preparing a model of a target processing device, correlating the software to be estimated to benchmark programs used in the preparation of the model, and then applying the software to be estimated to the model. The model is developed by determining the actual execution times of the benchmark programs, determining a number of virtual instructions in the benchmark programs and determining a predictor equation that correlates the virtual instructions to the actual execution time. The predictor equation is determined by a linear regression technique that includes a correlation analysis of the virtual instructions, removal of highly correlated instructions, and a combination of stepwise linear regression and multiple linear regression to determine the predictor equation.

Claims

1. A method of estimating the execution time of software, comprising the steps of:

preparing a model of a target processor based on a set of benchmark programs;

correlating the software to be estimated with the benchmark programs; and

applying the correlated software to the model to determine an estimate of the execution time of the software;

wherein;

the step of preparing a model comprises,

determining a frequency of virtual instructions in the benchmark programs,

determining actual execution times of the benchmark programs,

determining at least one of a predictor equation, error of estimation, and cycles per virtual instruction of the benchmark programs;

said method is embodied in a set of computer instructions stored on a computer readable media; and

said computer instructions, when loaded into a computer, cause the computer to perform the steps of said method.

2. The method according to claim 1, wherein said model comprises a linear model that correlates instructions to execution time.

3. The method according to claim 1, wherein said step of preparing a model comprises the steps of:

selecting a set of benchmark programs from a same domain as the software to be estimated;

determining a set of virtual instructions in the set of benchmark programs;

measuring actual execution times of the set of benchmark programs; and

determining a predictor equation by correlating the virtual instructions to the actual execution times.

4. The method according to claim 1, wherein said step of correlating comprises applying a 2-sample t-test between the software to be estimated and the benchmark programs.

5. The method according to claim 4, wherein said computer instruction are compiled computer instructions stored as an executable program on said computer readable media.

6. A method of estimating the execution time of software, comprising the steps of:

preparing a model of a target processor based on a set of benchmark programs;

correlating the software to be estimated with the benchmark programs; and

applying the correlated software to the model to determine an estimate of the execution time of the software;

wherein;

said step of preparing a model comprises the steps of;

selecting a set of benchmark programs from a same domain as the software to be estimated;

determining a set of virtual instructions in the set of benchmark programs;

measuring actual execution times of the set of benchmark programs; and

determining a predictor equation by correlating the virtual instructions to the actual execution times;

said step of determining a predictor equation comprises the steps of,

performing a correlation analysis between virtual instructions contained in the benchmark programs to determine which virtual instructions are highly correlated to other virtual instructions,

removing one or more elements from each set of highly correlated virtual instructions until one of the highly correlated elements remains to produce a pruned virtual instruction set,

performing linear regression on the pruned virtual instruction set to derive a predictor equation having a set of predictor variables,

reducing the set of predictor variables to a predetermined threshold, and

applying the reduced variable predictor equation to a 2nd set of benchmark programs to measure an amount of error in the reduced variable predictor equation.

7. The method according to claim 6, wherein:

said step of measuring actual execution times comprises determining a total cycle count for each of the benchmark programs; and

said step of performing linear regression comprises the steps of,

applying stepwise multiple linear regression to the pruned virtual instruction set and total cycle counts to determine a statistically significant set of predictor variables, and

applying multiple linear regression to the set of predictor variable to determine a predictor equation.

8. The method according to claim 7, wherein:

said method is embodied in a set of computer instructions stored on a computer readable media;

said computer instructions, when loaded into a computer, cause the computer to perform the steps of said method.

9. The method according to claim 6, wherein said step of reducing, comprises reducing the set of predictor variables until a quality of prediction over the benchmark programs reaches a predetermined threshold.

10. The method according to claim 9, wherein said quality of prediction is measured via an R-squared function that measures an amount of variance in a number of cycles are explained by a variance in the predictor variables which are being regressed upon.

11. The method according to claim 10, wherein said threshold is approximately 0.35 result of said R-squared function.

12. A device for estimating execution times of software, comprising:

modeling means for modeling a target processor;

correlation means for correlating software to be estimated to a set of benchmark software programs that were used as a basis in said modeling means; and

an estimation device configured to apply the correlated software to said modeling means to determine an estimated execution time of the software

wherein said modeling means comprises;

means for determining a frequency of virtual instructions in the benchmark programs;

means for determining actual execution times of the benchmark programs; and

means for determining at least one of a predictor equation, error of estimation, and cycles per virtual instruction of the benchmark programs.

13. The device according to claim 12, wherein said means for determining comprises:

means for performing a correlation analysis on the virtual instructions;

means for removing highly correlated instructions;

means for deriving a predictor equation based on the non-highly correlated virtual instructions and the actual execution times of the benchmark programs; and

means for reducing a set of variables in the derived predictor equation to a predetermined threshold.

14. The device according to claim 13, wherein said means for determining further comprises:

means for applying the derived predictor equation to a 2nd set of benchmark programs to measure a quality of the estimation capability of the predictor equation.

15. The device according to claim 13, wherein said means for deriving a predictor equation comprises a linear regression tool applied to said virtual instructions.

16. The device according to claim 13, wherein said means for deriving a predictor equation comprises:

means for performing stepwise linear regression to determine a set of predictor variables; and

means for performing linear regression on said predictor values to derive said predictor equation.

17. The device according to claim 13, wherein said threshold comprises an R-squared function value that measures an amount of variance in a number of cycles caused by a variance in the predictor variables which are being regressed upon.

18. The device according to claim 17, wherein said threshold is approximately 0.35.

19. A device for performing estimates of software execution times, comprising:

a model of a target processor based on execution time of a set of at least one benchmark program;

a correlating device configured to correlate a software program to be estimated to the set of at least one benchmark program; and

an estimation device configured to apply the software program to be estimated to the model to determine an estimated execution time of the software;

wherein the model comprises,

determining a frequency of virtual instructions in the benchmark programs;

determining actual execution times of the benchmark programs; and

determining at least one of a predictor equation, error of estimation, and cycles per virtual instruction of the benchmark programs.

20. The device according to claim 19, wherein said model of a target processor is a predictor equation constructed by linear regression of non-highly correlated virtual instructions of the set of benchmark programs and the execution times of the benchmark programs.