Cited By
View all- Bielecki JŚmiałek M(2023)Estimation of execution time for computing tasksCluster Computing10.1007/s10586-022-03774-126:6(3943-3956)Online publication date: 1-Dec-2023
Nonlinear approach for estimating WCET during programming phase
Abstract
For the safety of real-time systems, it is very important that the execution time of programs must meet all time constraints, even under the worst case. To expose timeliness defects which may cause an execution timeout as early as possible, we have studied a novel nonlinear approach for estimating worst case execution time (WCET) during programming phase, called NL-WCET. In this paper, we propose a program features model, based on which NL-WCET employs least square support vector machine (LSSVM) to learn the program features, and then estimates WCET. To improve the accuracy of NL-WCET, we develop an algorithm for training samples optimization. The experimental results show that both the model and the algorithm have distinct effects on the accuracy of NL-WCET. When static similarity is $$\ge $$ź80 %, cosine similarity is $$\ge $$ź99.5 % and max quotient between corresponding items is $$\le $$≤50, the average error of NL-WCET is merely 0.82 %, quite lower than conventional WCET measurement. Meanwhile it also has higher efficiency than conventional WCET analysis. Thus NL-WCET is suitable for being used during programming phase, and can help programmers to discover timeliness defects as early as possible.
References
[1]
Asensio, E., Lafoz, I., Coombes, A.: Worst-case execution time analysis approach for safety-critical airborne software. In: International Conference on Reliable Software Technologies, pp. 161---176. Springer, Heidelberg (2013)
[2]
Huang, Y., Zhao, M., XueChun, J.: Joint WCET and update activity minimization for cyber---physical systems. ACM Trans Embed. Comput. Syst. 14(1), 6---33 (2015)
[3]
Černý, P., Henzinger, T.A., Kovács, L.: Segment abstraction for worst-case execution time analysis. In: European Symposium on Programming Languages and Systems, pp. 105---131. Springer, Heidelberg (2015)
[4]
Biondi, A., Buttazzo, G.C., Bertogna, M.: Schedulability analysis of hierarchical real-time systems under shared resources. IEEE Trans. Comput. 65(5), 1593---1605 (2016)
[5]
Lee, A.: Cyber physical systems: design challenges. In: IEEE ISORC'2008, pp. 363---369 (2008)
[6]
Kozyrev, P.: Estimation of the execution time in real-time systems. Program. Comput. Softw. 42(1), 41---48 (2016)
[7]
Andalam, S., Roop, S., Girault, A.: A predictable framework for safety-critical embedded systems. IEEE Trans. Comput. 63(7), 1600---1612 (2014)
[8]
Moy, Y., Ledinot, E., Delseny, H.: Testing or formal verification: Do-178c alternatives and industrial experience. IEEE Softw. 30(3), 50---57 (2013)
[9]
Kästner, D., Ferdinand, C.: Static verification of non-functional software requirements in the ISO-26262. Automot. Saf. Secur. 14(1), 39---53 (2012)
[10]
Perez, J., Gonzalez, D., Trujillo, S.: A safety concept for an IEC-61508 compliant fail-safe wind power mixed-criticality system based on multicore and partitioning. In: International Conference on Reliable Software Technologies, pp. 3---17 Springer, Heidelberg (2015)
[11]
Wilhelm, R., Grund, D.: Computation takes time, but how much? Commun. ACM 57(2), 94---103 (2014)
[12]
Sahuquillo, J., Hassan, H., Petit, S.: A dynamic execution time estimation model to save energy in heterogeneous multicores running periodic tasks. Future Gener. Comput. Syst. 56, 211---219 (2016)
[13]
Wilhelm, R., Engblom, J., Ermedahl, A.: The worst-case execution-time problem--overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst. 7(3), 36---89 (2008)
[14]
Altmeyer, S., Douma, R., Lunniss, W.: On the effectiveness of cache partitioning in hard real-time systems. Real-Time Syst. 52(5), 598---643 (2016)
[15]
Hardy, D., Puaut, I.: Static probabilistic worst case execution time estimation for architectures with faulty instruction caches. Real-Time Syst. 51(2), 128---152 (2015)
[16]
Guan, N., Lv, M., Yi, W.: WCET analysis with MRU cache: challenging LRU for predictability. ACM Trans. Embed. Comput. Syst. 13(4s), 123---131 (2014)
[17]
Zolda, M., Kirner, R.: Calculating WCET estimates from timed traces. Real-Time Syst. 52(1), 38---87 (2016)
[18]
Li, X., Liang, Y., Mitra, T.: Chronos: a timing analyzer for embedded software. Sci. Comput. Program. 69(1), 56---67 (2007)
[19]
Huber, B., Prokesch, D., Puschner, P.: Combined WCET analysis of bitcode and machine code using control-flow relation graphs. ACM SIGPLAN Notices 48(5), 163---172 (2013)
[20]
Henry, J., Asavoae, M., Monniaux, D.: How to compute worst-case execution time by optimization modulo theory and a clever encoding of program semantics. ACM SIGPLAN Notices 49(5), 43---52 (2014)
[21]
Theiling, H.: Extracting safe and precise control flow from binaries. In: IEEE RTCSA'2000, pp. 23---30 (2000)
[22]
Parsa, S., Sakhaei-Nia, M.: PLEA: parametric loop bound estimation in WCET analysis. Turk. J. Electr. Eng. Comput. Sci. 24(4), 2135---2149 (2016)
[23]
Blackham, B., Liffiton, M., Heiser, G.: Trickle: automated infeasible path detection using all minimal unsatisfiable subsets. In: IEEE RTAS'2014, pp. 169---178 (2014)
[24]
Harmon, T., Schoeberl, M., Kirner, R.: Fast, interactive worst-case execution time analysis with back-annotation. IEEE Trans. Ind. Inf. 8(2), 366---377 (2012)
[25]
Schoeberl, M.: JOP: a Java optimized processor. In: International Conferences on "On the Move to Meaningful Internet Systems", pp. 346---359. Springer, Heidelberg (2003)
[26]
Rios, R., Schoeberl, M.: An evaluation of safety-critical Java on a Java processor. In: IEEE ISORC'2014, pp. 276---283 (2014)
[27]
Ghaedi, M., Ghaedi, A.M., Hossainpour, M.: Least square-support vector (LS-SVM) method for modeling of methylene blue dye adsorption using copper oxide loaded on activated carbon: Kinetic and isotherm study. J. Ind. Eng. Chem. 20(4), 1641---1649 (2014)
[28]
Mahmoodi, N.M., Arabloo, M., Abdi, J.: Laccase immobilized manganese ferrite nanoparticle: synthesis and LSSVM intelligent modeling of decolorization. Water Res. 67, 216---226 (2014)
[29]
Ahmadi, M.A., Bahadori, A.: A LSSVM approach for determining well placement and conning phenomena in horizontal wells. Fuel 153, 276---283 (2015)
[30]
Xuan, J., Luo, X., Zhang, G., Lu, J., Xu, Z.: Uncertainty analysis for the keyword system of web events. IEEE Trans. Syst. Man Cybern. Syst. 46(6), 829---842 (2016)
[31]
Xu, Z., Mei, L., Hu, C., Liu, Y.: The big data analytics and applications of the surveillance system using video structured description technology. Cluster Comput.
[32]
Zhou, W., Zhou, Y., Jiang, X.: Detecting repackaged smartphone applications in third-party android marketplaces. In: ACM CODASPY'2012, pp. 317---326 (2012)
[33]
Healy, J., Chambers, D.: Approximate k-mer matching using fuzzy hash maps. IEEE/ACM Trans. Comput. Biol. Bioinf. 11(1), 258---264 (2014)
[34]
Liangliang, K., Jianhui, J., Jie, X.: Simulation-based non-linear methods for the estimation of execution cycles of ARM programs. J. Comput. Res. Dev. 49(2), 392---401 (2012)
[35]
Liao, H., Xu, Z.: Approaches to manage hesitant fuzzy linguistic information based on the cosine distance and similarity measures for HFLTSs and their application in qualitative decision making. Expert Syst. Appl. 42(12), 5328---5336 (2015)
[36]
Ye, J.: Improved cosine similarity measures of simplified neutrosophic sets for medical diagnoses. Artif. Intell. Med. 63(3), 171---179 (2015)
[37]
Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv. (CSUR) 33(1), 31---88 (2001)
[38]
Schulz, U., Mihov, S.: Fast string correction with Levenshtein automata. Int. J. Doc. Anal. Recogn. 5(1), 67---85 (2002)
[39]
Zhou, S.: Sparse LSSVM in primal using Cholesky factorization for large-scale problems. IEEE Trans. Neural Netw. Learn. Syst. 27(4), 783---795 (2016)
[40]
Ying, Z., Keong, C.: Fast leave-one-out evaluation and improvement on inference for LS-SVMs. In : IEEE ICPR'2004, pp. 494---497 (2004)
[41]
Yoo, J., Lee, J., Hong, S.: Petri net-based FTL architecture for parametric WCET estimation via FTL operation sequence derivation. IEEE Trans. Comput. 62(11), 2238---2251 (2013)
[42]
Burns, F., Koelmans, A., Yakovlev, A.: Wcet analysis of superscalar processors using simulation with coloured petri nets. Real-Time Syst. 18(2), 275---288 (2000)
[43]
Rust, C., Stappert, F., Bernhardi-Grisson, R.: Petri net based design of reconfigurable embedded real-time systems. In: Design and Analysis of Distributed Embedded Systems, pp. 41---50. Springer New York (2002)
[44]
Stappert, F., Rust, C.: Worst case execution time analysis for petri net models of embedded systems. In: Embedded Systems and Applications, pp. 176---182 (2003)
[45]
Coffman, J., Healy, C., Mueller, F.: Generalizing parametric timing analysis. ACM SIGPLAN Notices 42(7), 152---154 (2007)
[46]
Mohan, S., Mueller, F., Root, M.: Parametric timing analysis and its application to dynamic voltage scaling. ACM Trans. Embed. Comput. Syst. 10(2), 25---51 (2010)
[47]
Altmeyer, S., Humbert, C., Lisper, B.: Parametric timing analysis for complex architectures. In: IEEE RTCSA'2008, pp. 367---376 (2008)
[48]
Sarkar, M., Mondal, T., Roy, S.: Resource requirement prediction using clone detection technique. Future Gener. Comput. Syst. 29(4), 936---952 (2013)
Recommendations
Optimization of Multi-core Interconnection for WCET Analysis in Automotive Application
CICN '12: Proceedings of the 2012 Fourth International Conference on Computational Intelligence and Communication NetworksWith the increasing demand for computing power and performance in automotive, multi-core ECUs (Electronic Control Unit) are introduced. And hard real-time embedded systems in automotive require timing analyzability. But multi-core systems are less ...
WCET squeezing: on-demand feasibility refinement for proven precise WCET-bounds
RTNS '13: Proceedings of the 21st International conference on Real-Time Networks and SystemsThe Worst-Case Execution Time (WCET) computed by a WCET analyzer is usually not tight, leaving a gap between the actual and the computed WCET of a program. In this article we present a novel on-demand WCET feasibility refinement technique, called WCET ...
WCET analysis for a Java processor
JTRES '06: Proceedings of the 4th international workshop on Java technologies for real-time and embedded systemsIn this paper we propose a solution for a worst-case execution time (WCET) analyzable Java system: a combination of a time predictable Java processor and a tool that performs WCET analysis of Java bytecode. We present a Java processor, called JOP, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2016 Springer Science+Business Media New York.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 September 2016
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
Cited By
View all- Bielecki JŚmiałek M(2023)Estimation of execution time for computing tasksCluster Computing10.1007/s10586-022-03774-126:6(3943-3956)Online publication date: 1-Dec-2023
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in