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