آقای مهدی سخائی نیا دانشجوی دکترای جناب آقای دکتر سعید پارسا روز شنبه مورخ 94/1/22 ساعت 17:00 در دانشکده مهندسی کامپیوتر از رساله دکترای خود تحت عنوان تخمین بیشترین زمان اجرای کدهای تکرار پذیر دفاع خواهند نمود چکیده هدف از این رساله تخمین بیشترین
زمان اجرای کدهای تکرارپذیر میباشد. این تخمین برای شناسایی وضعیتی از اجرای نرمافزار
که بیشترین استفاده از منابع را دارد، بسیار حائز اهمیت میباشد. بخصوص در سیستمهای
نهفته بیدرنگ دانستن بیشترین زمان اجرای وظایف، برای زمانبندی ضروری است. یافتن
تعداد تکرار حلقهها و عمق فراخوانی بازگشتی و وابستگی آنها به ورودیهای برنامه
از مهمترین چالشهای تخمین بیشترین زمان اجرا میباشد. تعداد تکرارها حلقهها، به
مسیر اجرایی در طول حلقه وابسته میباشد. انتخاب مسیر اجرایی وابسته به شرایط
موجود در داخل حلقه و شرایط نیز خود وابسته به متغیرهایی هستند که مقدارشان در طول
حلقه تغییر مینماید. با استفاده از راهکار تحلیل نمادین میتوان شرایط اجرایی هر
مسیر در بدنه حلقه را با یکدیگر ترکیب و به ابتدای حلقه انتقال داد. عبارت شاخص
چگونگی تغییر مقدار هر متغیر درون یک مسیر اجرایی را نیز می توان با تحلیل نمادین
بر روی آن مسیر بدست آورد. مشکل، تعیین مقدار متغیرهای تاثیرگذار بر مسیرهای
اجرایی درون حلقه، در بدو ورود به حلقه است. با توجه به این مساله مبادرت به ارایه
مدل در قالب یک تابع پارامتریک جهت تعیین تعداد تکرارهای حلقه شد. پارامترهای
ورودی این تابع متغیرهای تاثیر گذار بر تعداد تکرارهای حلقه میباشد. مبرهن است که
زمان اجرای برنامهها وابسته به شرایط اجرایی و مقدار ورودیها برنامه میتواند
بسیار متفاوت و متغیر باشد. با تعیین بیشترین تعداد تکرار و طولانیترین مدت زمان
اجرا برای هر مسیر می توان با استفاده از یک راهکار برنامه ریزی خطی صحیح،
بیشترین زمان اجرای حلقه را بدست آورد. بیشترین تعداد حالات برنامه میتواند
تخمینی مطمئن برای بیشترین تعداد تکرارهای حلقه باشد. مسلماً، با محدود کردن منطقی
هر چه بیشتر تعداد حالات، مقدار تخمینی به بیشترین زمان اجرای واقعی حلقه نزدیکتر
خواهد شد. ارزیابیهای انجام شده در این رساله شاخص پچیدگی محاسباتی کمتر و دقت
نسبتاً بیشتر روش پیشنهادی در مقایسه با سایر روشها و بالاخص روشهای متمرکز بر
تحلیل بیشترین زمان اجرای حلقههای چند مسیری میباشد. :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 ارائه دهنده: مهدی سخائی نیا رشته مهندسی کامپیوتر-گرایش نرم افزار استاد راهنما: دکتر سعید پارسا هیات داوران: دکتر سعید جلیلی،دکتر عباس حیدر نوری دکتر محسن شریفی، دکتر محمد عبداللهی ازگمی،دکتر عین ا... خنجری زمان : شنبه 22فروردین ماه 1394 ساعت 17:00 مکان: دانشکده مهندسی کامپیوتر- طبقه دوم- اتاق دفاعیه دکتری دانشکده مهندسی کامپیوتر مدیریت تحصیلات تکمیلی |