Fast Estimation And Optimization Of Worst-case Execution Time For Early Stage Of Software Development

Software safety in real-time systems is not only related to the fact whether software functions can reach all expectations,but also depends on the fact whether execution time of the software can meet all deadlines.With its roles in real-time systems becoming more and more critical,the scale and structure of programs become more huge and complex,resulting in an escalation of timeout risks and harms.Since predicting failure-prone modules at the early stage of software development can greatly improve the quality of software and reduce the repair cost of defects,program's worst-case execution time(WCET)should be estimated quickly at the early stage of software development,and then the WCET needs to be immediately mapped onto source code for locating performance bottleneck.On this basis,the bottleneck is eliminated through source code refactoring so as to prevent and control the timeout risks with a lower cost.However,though the existing static WCET estimation methods can guarantee the valuation security,they generally have lower efficiency.In order to avoid waiting or frequently switching interfaces,programmers often postpone the WCET estimation to the later stage of the system development.In addition,the existing static WCET estimation methods may result in other problems,such as: the difficulty in mapping the estimation to the source level since the estimation is taken from object code;the ineffectiveness of traditional performance optimization based on object code to reduce WCET.Therefore,it is difficult to warn and prevent early timeout risks.To solve these problems,this dissertation studies fast estimation and optimization of WCET for early stage of software development.The studies have important theoretical significance and application value in early warning and prevention of timeout risks,reducing the cost of developing real-time systems,as well as enhancing the system reliability and ensuring the software safety.Aiming at the problem that existing methods can't offer programs' WCET valuation in real time,it is difficult to synchronize with the development proc ess and carry out real-time warning of timeout risks,a WCET fast estimation method based on instruction profile is proposed.A program feature model for WCET nonlinear estimation is designed by combining the simulation execution time,dynamic instruction type number and fuzzy hash value of the object code.On this basis,a training sample optimization algorithm is developed,which combines static similarity and dynamic similarity.When the WCET analysis method based on IPET(hereinafter referred to as "IPET method")is available,the static and dynamic characteristics of the program are extracted and stored in the sample library with its WCET valuation.If the IPET method fails to give the analysis results within a predetermined time,training samples are selectively chosen from the sample library in terms of static similarity and dynamic similarity,and the least squares support vector machine is used to learn and predict nonlinearly.The experimental results show that the average efficiency of the proposed method is high and it can quickly estimate the WCET of the program in the compiling process with little influence on the estimation accuracy.Thus,it suits for detecting and warning timeout risks in real time during an initial stage of system development.Aiming at the problem that the existing methods do not support WCET to display the functions or statements at the source level,which often result in overestimation,it is difficult to locate code performance bottleneck quickly.Control flow tree is used to calculate WCET with functions or statements and WCET is fed back to source code by using the hierarchical structure information retained by the bytecode.The reasons for overestimation of the existing methods have been analyzed.On this basis,the condition of unreasonable overestimation is proposed,which is combined with WCET estimation algorithm based on control flow tree to quickly estimate WCET and count the overestimated risk data.Then the WCET feedback and timeout risk warning mechanism is designed and then determines whether the code is timeout based on the time budget.Once the timeout is found,the corresponding warning will be triggered.The experimental results show that our method can not only quickly estimate the WCET with functions or stat ements shown at the source level,and it can also automatically determine unreasonable overestimation and further reduce time cost in confirming timeliness defects and improve the location efficiency of code performance bottleneck.Aiming at the problem that the existing methods do not take it into account that local maximum iterations of non-orthogonal nested loops in complex programs is indivisible in transforming into relative constraints between inner and outer layer circulation,which will result in WCET overestimation and mislead programmers to blindly optimize program codes,a modified WCET overestimation method based on local relative constraints is proposed.From two aspects of processor behavior analysis and control flow analysis,the reasons for overestimation of existing methods have been analyzed.On this basis,the necessary conditions for determining WCET overestimation with non-orthogonal nested loop programs are given.In order to deal with such special overestimation,a WCET overestimation c orrection algorithm based on local relative constraints is designed,which corrects relative constraints of non-orthogonal nested loops in the non-branch part of WCEP layer by layer from inside to outside.The experimental results show that our method can effectively reduce WCET overestimation in the presence of non-orthogonal nested loop procedures and avoid unnecessary cost of code optimization on the premise of ensuring WCET security estimation.Aiming at the problem that WCET optimization in the existin g methods has great influence on the maintainability of codes at the later stage and the existing methods have poor portability,which cannot effectively prevent and control timeout risks at a relatively low cost,a source-code refactoring WCET optimization based on invariant path is proposed.This method uses annotation feedback technology to identify the WCEP and the invariant path in the source code.Then,according to the influence of invariant path and the loop on the WCET optimization,the optimized hot spots of source code are divided.Concerning that WCET optimization may produce clone code,which affects the later maintenance of software,the maintenance cost is calculated in terms of the number of clone elements and the distance between clone codes,and the optimization strategy of WCET source code refactoring is designed.The experimental results show that this method can reduce programs' WCET with lower maintainability cost,thus preventing and controlling software's timeout risks.Moreover,the WCET optimizations are portable.To sum up,this paper provides new ideas and methods to solve the scientific problems such as how to quickly estimate and optimize WCET,and then detect and prevent timeout risks hidden in source code at the initial period o f software development so as to ensure that software meets execution time constraints.It is conducive to hardware-software co-design in the process of real-time system development and beneficial to reduce development costs of real-time system and improve its software safety.