چكيده
چكيده
هدف از اين رساله تخمين بيشترين زمان اجراي كدهاي تكرارپذير مي¬باشد. اين تخمين براي شناسايي وضعيتي از اجراي نرم¬افزار كه بيشترين استفاده از منابع را دارد،بسيار حائز اهميت مي¬باشد. بخصوص در سيستم¬هاي نهفته بي¬درنگ دانستن بيشترين زمان اجراي وظايف، براي زمانبندي ضروري است. يافتن تعداد تكرار حلقه¬ها و عمق فراخواني بازگشتي و وابستگي آنها به ورودي¬هاي برنامه از مهمترين چالش-هاي تخمين بيشترين زمان اجرا مي¬باشد.تعداد تكرارهاي حلقه، به مسير اجرايي در طول حلقه وابسته مي-باشد. انتخاب مسير اجرايي وابسته به شرايط موجود در داخل حلقه و شرايط نيز خود وابسته به متغيرهايي هستند كه مقدارشان در طول حلقه تغيير مي¬نمايد. با استفاده از راه¬كار تحليل نمادين مي¬توان شرايط اجرايي هر مسيردر بدنه حلقه را با يكديگر تركيب و به ابتداي حلقه انتقال داد. عبارت شاخص چگونگي تغيير مقدار هر متغير درون يك مسير اجرايي را نيز مي توان با تحليل نمادين بر روي آن مسير بدست آورد. مشكل، تعيين مقدار متغيرهاي تاثير¬گذار بر مسيرهاي اجرايي درون حلقه، در بدو ورود به حلقه است. با توجه به اين مساله مبادرت به ارايه مدل در قالب يك تابع پارامتري جهت تعيين تعداد تكرارهاي حلقه شد. پارامترهاي ورودي اين تابع متغيرهاي تاثير گذار بر تعداد تكرارهاي حلقه مي¬باشد. مبرهن است كه زمان اجراي برنامه¬ها وابسته به شرايط اجرايي و مقدار ورودي¬ها برنامه مي¬تواند بسيار متفاوت و متغير باشد. با تعيين بيشترين تعداد تكرار و طولاني¬ترين مدت زمان اجرا براي هر مسير مي توان با استفاده از يك راه¬كار برنامه ريزي خطي صحيح، بيشترين زمان اجراي حلقه را بدست آورد. بيشترين تعداد حالات برنامه مي¬تواند تخميني مطمئن براي بيشترين تعداد تكرارهاي حلقه باشد. مسلماً، با محدود كردن منطقي هر چه بيشتر تعداد حالات، مقدار تخميني به بيشترين زمان اجراي واقعي حلقه نزديكتر خواهد شد. ارزيابي¬هاي انجام شده در اين رساله شاخص پچيدگي محاسباتي كمتر و دقت نسبتاً بيشتر روش پيشنهادي در مقايسه با ساير روشها و بالاخص روشهاي متمركز بر تحليل بيشترين زمان اجراي حلقه¬هاي چند مسيري مي¬باشد.
واژه‌هاي كليدي:تحليل كران حلقه¬ها، بيشترين زمان اجرا، تحليل زماني، سيستم¬هاينهفته بي¬درنگ
