چکیده

 هدف از این رساله تخمین بیشترین زمان اجرای کدهای تکرارپذیر می­باشد. این تخمین برای شناسایی وضعیتی از اجرای نرم­افزار که بیشترین استفاده از منابع را دارد، بسیار حائز اهمیت می­باشد. بخصوص در سیستم­های نهفته بی­درنگ دانستن بیشترین زمان اجرای وظایف، برای زمانبندی ضروری است. یافتن تعداد تکرار حلقه­ها و عمق فراخوانی بازگشتی و وابستگی آنها به ورودی­های برنامه از مهمترین چالش­های تخمین بیشترین زمان اجرا می­باشد. تعداد تکرارها حلقه­ها، به مسیر اجرایی در طول حلقه وابسته می­باشد. انتخاب مسیر اجرایی وابسته به شرایط موجود در داخل حلقه و شرایط نیز خود وابسته به متغیرهایی هستند که مقدارشان در طول حلقه تغییر می­نماید. با استفاده از راه­کار تحلیل نمادین می­توان شرایط اجرایی هر مسیر در بدنه حلقه را با یکدیگر ترکیب و به ابتدای حلقه انتقال داد. عبارت شاخص چگونگی تغییر مقدار هر متغیر درون یک مسیر اجرایی را نیز می توان با تحلیل نمادین بر روی آن مسیر بدست آورد. مشکل، تعیین مقدار متغیرهای تاثیر­گذار بر مسیرهای اجرایی درون حلقه، در بدو ورود به حلقه است. با توجه به این مساله مبادرت به ارایه مدل در قالب یک تابع پارامتریک جهت تعیین تعداد تکرارهای حلقه شد. پارامترهای ورودی این تابع متغیرهای تاثیر گذار بر تعداد تکرارهای حلقه می­باشد. مبرهن است که زمان اجرای برنامه­ها وابسته به شرایط اجرایی و مقدار ورودی­ها برنامه می­تواند بسیار متفاوت و متغیر باشد. با تعیین بیشترین تعداد تکرار و طولانی­ترین مدت زمان اجرا برای هر مسیر می توان با استفاده از یک راه­کار برنامه ریزی خطی صحیح، بیشترین زمان اجرای حلقه را بدست آورد. بیشترین تعداد حالات برنامه می­تواند تخمینی مطمئن برای بیشترین تعداد تکرارهای حلقه باشد. مسلماً، با محدود کردن منطقی هر چه بیشتر تعداد حالات، مقدار تخمینی به بیشترین زمان اجرای واقعی حلقه نزدیکتر خواهد شد. ارزیابی­های انجام شده در این رساله شاخص پچیدگی محاسباتی کمتر و دقت نسبتاً بیشتر روش پیشنهادی در مقایسه با سایر روشها و بالاخص روشهای متمرکز بر تحلیل بیشترین زمان اجرای حلقه­های چند مسیری می­باشد.

    :Abstract

  The aim of this thesis is to estimate worst-case execution time of iterative program codes. This estimation is very important to determine the state of software execution that makes the worst use of resources. Especially in real-time embedded systems, knowing Worst-Case Exaction Time (WCET) of tasks is necessary for task scheduling. Finding the number of loop iterations and depth of recursive calls and their dependence on the program input are the main challenges for WCET estimation. The number of loop iterations depends on the execution paths within the loop body. The selected path for execution depends on the conditions within the loop body, affected by variables whose values are altered within the loop body. Using symbolic analysis, for each execution path the execution condition is extracted within the loop body by combination of the branch conditions based on the values of variable at the loop entry point. Symbolic expression representing change in the value of each variable on an execution path within the loop body is extracted via symbolic analysis on that path. One problem is to determine the value of variables at loop entry point affecting execution paths within the loop body. With respect to this problem, a parametric function is presented to determine the number of loop iterations. The parameters of this function are the variables affecting the number of loop iterations. It is clear that the execution time of programs can be varied depending on the execution conditions and program inputs. The loop WCET can be derived based on determining the maximum number of iterations and the WCET of each execution path by an integer linear programming solver. The maximum number of possible program states at a point can be a safe estimate of the number of iterations for that point. Surely, the number of iterations will be close to actual value by reasonable limitation of the possible program states. Evaluation results showed that the proposed approach has a lower computational complexity and higher accuracy in comparison with other approaches especially those that estimate the WCET for multi-path loops