روشی مبتنی بر تطبیق الگو برای تخمین بیشترین زمان اجرای حلقه‌های یکنواخت چندمسیری
محورهای موضوعی : مهندسی برق و کامپیوترمهدی سخائی نیا 1 * , سعید پارسا 2
1 - دانشگاه بوعلی سینا
2 - دانشگاه علم و صنعت ايران
کلید واژه: تخمین بیشترین زمان اجراتحلیل حد حلقه‌های تکرارسامانه‌های نهفته بی‌درنگتحلیل ایستای برنامه,
چکیده مقاله :
روش تطبیق الگو یکی از روش‌هایی است که برای تخمین بیشترین زمان اجرای حلقه‌ها ارائه شده است. در این روش در صورتی که حلقه با الگوی ارائه‌شده تطبیق داشت با استفاده از یک معادله، بیشترین تعداد تکرار حلقه محاسبه می‌گردد. در حقیقت برای محاسبه تعداد تکرار نیازی نیست که مقدار متغیرهای کنترلی حلقه برای هر تکرار محاسبه گردد. نقص روش تطبیق الگو وابستگی زیاد آن به الگو است. این وابستگی به ساختار و محل شرط تست‌کننده متغیر کنترلی حلقه و از سوی دیگر به محل، نحوه و تعدد تغییر متغیر کنترلی حلقه مرتبط است. برای کاهش وابستگی به الگو می‌توان جریان اطلاعات برای حلقه‌های یکنواخت چندمسیری در قالب دو دسته عبارت نمادین، نشان‌دهنده شرط تکرار و نحوه تغییر متغیرهای کنترلی حلقه را مدل‌سازی کرد. بر اساس این عبارات، تعداد مقادیر ممکن که در زمان اجرا می‌توان به متغیرهای کنترلی حلقه تخصیص داد محاسبه و به عنوان تخمینی از بیشترین تعداد تکرار ارائه می‌گردد. اما تخمین ارائه‌شده در این روش بیشتر از مقدار واقعی است و در اصطلاح دارای بیش‌تخمین خواهد بود. در این مقاله، متغیرهایی که مقدارشان در مسیرهای تکرار مختلف یکسان هستند و در هر چند مسیر این مقدار به عنوان یک تکرار محاسبه گردیده است، شناسایی و در محاسبه‌ها لحاظ می‌گردند. این کار باعث می‌گردد که مقدار بیش‌تخمین کاهش یابد. ارزیابی‌ها نشان داد که روش ارائه‌شده در این مقاله روشی مؤثر و کارا بوده و بیش‌تخمین کمتری دارد.
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.