US 8,302,085 B2 · Method for developing software code and estimating processor execution time

Abstract

A method (1) of developing software code for executing on a target digital processor uses a memory in which it maintains data structures having elements, each of the elements storing data which is represented by a label, and at least some links between the elements are created by the target processor as data is being processed. The method comprises the step (3) of writing the software code with data structure processing operations which comply with random structure preservation rules (2). A static analysis timing tool automatically parses (4) the code developed in step (2) to identify all operations. It determines (7) from an operation and all possible input states for that operation an average time value for execution of the operation by a target data processor, and stores (9) said average time value. It determines (8) from the operation and all possible input states all possible output states for that operation. The timing tool repeats steps (7 and 8) for each next operation, using the all possible output states determined in step (8) as all possible input states. It generates (11) an output total average time which is a sum of all average times stored in step (9).

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims21

Dependent claims

A method of developing software code for executing on a target digital processor using a memory in which it maintains data structures having elements, each of the elements storing data which is represented by a label, and at least some links between the elements being created by the target processor as data is being processed, the method comprising the steps of:

(a) writing the software code with data structure processing operations which comply with random structure preservation rules, and
(b) a static analysis timing tool automatically:
(i) parsing the code developed in step (a) to identify all operations,
(ii) determining from an operation and all possible input states for that operation an average time value for execution of the operation by a target data processor, and storing said average time value,
(iii) determining from the operation and all possible input states all possible output states for that operation,
(iv) repeating steps (ii) and (iii) for each next operation, using the all possible output states determined in step (iii) as all possible input states, and
(v) generating an output total average time which is a sum of all average times stored in step (ii);
and
wherein said rules require the labels to be comparable;
wherein the rules require directionality in links between elements and labels are assigned to elements to respect directionality of the links;
and
wherein all directions of links of a data structure indicate the same label comparison ordering.

9 more elements

(a) writing the software code with data structure processing operations which comply with random structure preservation rules, and
(b) a static analysis timing tool automatically:
(i) parsing the code developed in step (a) to identify all operations,
(ii) determining from an operation and all possible input states for that operation an average time value for execution of the operation by a target data processor, and storing said average time value,
(iii) determining from the operation and all possible input states all possible output states for that operation,
(iv) repeating steps (ii) and (iii) for each next operation, using the all possible output states determined in step (iii) as all possible input states, and
(v) generating an output total average time which is a sum of all average times stored in step (ii);
and
wherein an operation is a delete operation, in which a label is deleted from a data structure, and wherein in case the label to be deleted is stored in a maximal element of the data structure or in a minimal element of the data structure, the label and the element at which it is stored can be outright deleted;
wherein in case a label is not attached to a minimal or to a maximal element, then the label, throughout the remainder of the delete operation, will be regarded as the smallest label or the largest label of the data structure;
and wherein the delete operation then performs a push-down operation or a push-up operation on the altered label until the label reaches a minimal element or a maximal element;
wherein after that the label is restored to its original value at which it no longer is regarded as the smallest or largest label and the label and the maximal element or minimal element at which it is stored are deleted.

9 more elements

Dependencies are inferred from the claim text.

Description30,366 words

Summary560 words

#The invention relates to control of data processor activity and utilization of memory.

#There are many software code applications which involve a large number of comparison operations and for which it would be very advantageous to be able to predict the processor time to execute the code. This is particularly true for real time applications such as are flight control systems in aircraft or vehicle cruise control applications.

#An example of the source code language which is used for development of comparison-based programs is Java Libraries™. It would be very advantageous to be able to accurately predict the processor execution time for a program developed in this language as execution of the programs involves many cycles of retrieving libraries and processing their data. If accurate prediction were possible, it would in turn be possible to correctly deploy the correct hardware resources for optimum trade-off between performance and cost, to plan the timing of interactions between tasks, and to allocate tasks to processing units.

Brief description of the drawings3 figures

#The invention will be more clearly understood from the following description of some embodiments thereof, given by way of example only with reference to the accompanying drawings in which:

#FIG. 1 is a flow diagram of the major steps of a method of the invention;

#FIG. 2 is a plot of illustrating random structures before and after operations of software code developed according to the invention; and

Detailed description29,718 words

#The invention provides a method of developing software code, called MOQA (MOdular Quantitative Analysis), the method involving use of a static analysis timing tool called “Distri Track” after software development to automatically estimate the actual times for execution of the code. The MOQA method allows knowledge about the data to be derived by the Distri Track tool, i.e. all possible states of data are known at any given point of the code execution, and to keep track of all states during the execution.

#This method of developing software code is based on a specific body of rules. Any programmer or automatic development tool which adheres to these rules of how data is created and manipulated can apply the Distri Track tool to statically analyze the code and determine the average-case time of the computation.

#The Distri Track tool extracts the data distribution information at any given point of the computation. By using this information in a way described further below, the average number of basic steps a computation performs (for example, comparisons, swaps, and assignments) in order to manipulate the data can be calculated by Distri Track. This information in turn enables Distri Track to statically predict the average-case time of the computation, simply by multiplying the number of computation steps by the time it takes to compute such a step (or an upper bound of this time) on the particular processor used and summing up the resulting times.

Facts

Application

11/883,938Filed 16 Feb 2006 · us provisional application

Priority

IE 2005/010428 Feb 2005

Published

US 2008/0295071 A127 Nov 2008

Granted

30 Oct 2012

Term ends

10 Dec 2029

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 1,393 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification5 codes

G06F 11/3419
For performance assessment: by assessing time
G06F 11/3447
Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of…:…
G06F 11/3612
Analysis of software for verifying properties of programs: by runtime analysis
G06F 2201/865
Indexing scheme relating to error detection, to error correction, and to monitoring: monitoring of software

Timeline

16 Feb 2005Priority claimedIE 2005/0104
16 Feb 2006Application filedUS 11/883,938
8 Aug 2007Assigned to University College Cork - National University of Ireland, Corkassignment of assignor's interest
27 Nov 2008PublishedUS 2008/0295071 A1
30 Oct 2012GrantedUS 8,302,085 B2
12 Oct 2026TodayWithin its term
10 Dec 2029Term endsEstimated, includes 1,393 days of adjustment

Method for developing software code and estimating processor execution time

Life of this patent

Method for developing software code and estimating processor execution time

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims21

Description30,366 words

Drawings

Classification5 codes

Life of this patent

Description30,366 words