A Pattern-Matching Method for Estimating WCET of Multi-Path Monotonic Loops
Subject Areas : electrical and computer engineeringMehdi Sakhaei-nia 1 * , S. parsa 2
1 -
2 - University of Science and Technology
Keywords: WCET estimationloop bound analysisreal-time embedded systemsstatic program analysis,
Abstract :
Pattern matching is one of possible methods proposed for estimating the WCET of the loops. If the loop matches with the proposed pattern, the number of iterations is calculated using an equation. In fact, the derivation of counter values for all iterations is thus avoided. A shortcoming of pattern matching methods is its excessive dependence upon patterns. It is dependent upon location, frequency and how to change in value of the counter and structure and place of counter tester. In order to reduce dependence upon patterns, loop flow can be modeled in two sets of symbolic expressions indicating iteration conditions and changes in value of counters. Based upon these expressions, the number of possible values that could be assigned to the loop control variables during the loop execution is computed as the worst-case estimation of the number of loop iterations. But the estimate presented in this method is greater than the actual value and there is overestimation. In this paper, the variables whose values are equal on the different paths and this value is accounted as an iteration, are detected and are considered in the estimations. This will reduce the overestimation. The evaluations are showed that the proposed method is effective and efficient and has less overestimation.
[1] R. Wilhelm, et al., "The worst-case execution time problem-overview of approaches and survey of tools," Trans. on Embedded Computing Sys., vol. 7, no. 3, Article No. 36, Apr. 2008.
[2] R. Chapman, Static Timing Analysis and Program Proof, Ph.D. Dissertation, Univ. of York, 1995.
[3] J. Gustafsson, A. Ermedahl, C. Sandberg, and B. Lisper, "Automatic derivation of loop bounds and infeasible paths for WCET analysis using abstract execution," in Proc. 27th IEEE Real-Time Systems Symp., RTSS'06, pp. 57-66, Rio de Janeiro, Brazil, 5-8 Dec. 2006.
[4] M. Michiel, A. Bonenfant, H. Casse, and P. Sainrat, "Static loop bound analysis of C programs based on flow analysis and abstract interpretation," in Proc. IEEE Int. Conf. on Embedded and Real-Time Computing Systems and Applications, RTCSA'08, pp. 161-166, Kaohsiung, Taiwan, 25-27 Aug. 2008.
[5] پ. سخائینیا، "روشی مبتنی بر تطبیق الگو برای تخمین بیشترین زمان اجرای حلقهها،" هشتمین کنفرانس بینالمللی فناوری اطلاعات و دانش، صص. 766-760، همدان، شهريور 1395.
[6] C. Healy, M. Sjodin, V. Rustagi, D. Whalley, and R. Engelen, "Supporting timing analysis by automatic bounding of loop iterations," J. of Real-Time Systems, vol. 18, no. 2-3, pp. 129-156, May 2000.
[7] Tidorum Bound-T tool homepage. www.tidorum.fi/bound-t, 2008.
[8] N. Holsti, L. Thomas, and S. Saarinen, "Worst-case execution-time analysis for digital signal processors," in Proc. of 10th European Signal Processing Conf., EUSIPCO'00, 14 pp., Tampere, Finland, 4-8 Sept. 2000.
[9] A. Prantl, M. Schordan, and J. Knoop, "TuBound-a conceptually new tool for worst-case execution time analysis," in Proc. 8th Int. Workshop on Worst-Case Execution Time Analysis, WCET'08, volpp. 141-148, Prague, Czech Republic, 2008.
[10] -, aiT Tool: The Industry Standard for Static Timing Analysis, 2007. http://www.absint.com/ait/
[11] C. Cullmann and F. Martin, "Data-flow based detection of loop bounds," in Proc. 7th Int. Workshop on Worst-Case Execution Time Analysis, WCET'07, 6 pp., Italy, Jul. 2007.
[12] J. Knoop, L. Kovacs, and J. Zwirchmayr, "Symbolic loop bound computation for WCET analysis, in Perspectives of Systems Informatics, E. Clarke, I. Virbitskaite, and A. Voronkov, Eds. Springer Berlin Heidelberg, pp. 227-242, 2012.
[13] A. Biere, J. Knoop, L. Kovacs, and J. Zwirchmayr, "The auspicious couple: symbolic execution and WCET analysis," in Proc. of the 13th International Workshop on Worst-Case Execution Time Analysis, vol. 30, pp. 53-63, 9-9 Jul. 2013.
[14] S. Parsa and M. Sakhaei-Nia, "Modeling flow information of loops using compositional condition of controls," The J. of Supercomputing, vol. 71, no. 2, pp. 508-536, Feb. 2015.
[15] S. Bygde, A. Ermedahl, and B. Lisper, "An efficient algorithm for parametric WCET calculation," J. of Systems Architecture, vol. 57, no. 6, pp. 614-624, Jun. 2011.
[16] S. Parsa and M. Sakhaei-Nia, "PLEA: parametric loop bound estimation in WCET analysis," Turkish J. of Electrical Engineering & Computer Sciences, vol. 24, no. 4, pp. 2135-2149, Apr. 2016.
[17] L. N. D. Moura and N. Bjorner, "Z3: an efficient SMT solver," TACAS, vol. 4963, pp. 337-340, Springer, 2008.
[18] D. Kebbal and P. Sainrat, "Combining symbolic execution and path enumeration in worst-case execution time analysis," in Proc. 6th Int. Workshop on Worst-Case Execution Time Analysis, WCET'06, vol. 4, 6 pp., Jul. 2006.
[19] J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper, "The malardalen WCET benchmarks: past, present and future," in Proc. 10th Int. Workshop on Worst-Case Execution Time Analysis, WCET'10, vol. 15, pp. 136-146, 2010.