بخشی از مقاله
چکیده
برای یافتن یک زمانبندی ممکن در سیستم های بی درنگ باید بیشترین زمان اجرای هر وظیفه مشخص باشد تا تضمین گردد اجرای وظیفه قبل از پایان زمان اختصاص یافته به آن خاتمه می پذیرد. اجرای حلقه های تکرار بیشترین مدت زمان اجرای یک وظیفه یا برنامه را به خود اختصاص می دهند. این امر اهمیت تخمین بیشترین زمان اجرای حلقه ها را نشان می دهد. روش تطبیق الگو یکی از روشهایی است که برای تخمین بیشترین زمان اجرای حلقه ها ارائه شده است.
در این روش در صورتیکه حلقه با الگوی ارائه شده تطبیق داشت با استفاده از یک معادله تعداد تکرار محاسبه می گردد. در حقیقت از تولید مقدار شمارنده برای تمامی تکرارها جلوگیری می گردد. نقص روش تطبیق الگو وابستگی زیاد آن به الگو می باشد. این وابستگی به ساختار و محل شرط تست کننده شمارنده، محل، نحوه و تعدد تغییر شمارنده مرتبط می باشد. در این مقاله با مدلسازی جریان اطلاعات حلقه در قالب دو دسته عبارت نمادین نشاندهنده شرط تکرار و نحوه تغییر شمارنده از وابستگی به الگو کاسته شده است. با یک مثال توانایی روش ارائه شده نشان داده شده است.
-1 مقدمه
در این مقاله روشی نوینی ارائه شده است که تاثیری پذیری کمتری از محدودیت های فوق داشته باشد. برای حل این مشکل در این مقاله اطلاعات جریان کنترلی و داده ای حلقه تکرار استخراج گردیده و در قالب دو د سته عبارت نمادین مدل شده ا ست. بدین منظور م سیرهای تکرار در بدنه حلقه که در هر تکرار، حلقه از یکی از آنها اجرا می شود شنا سایی می گردد. برای هر مسیر تکرار یک عبارت شرط تکرار و یک عبارت چگونگی تغییر متغیرهای حلقه - شمارنده - ایجاد می گردد.
عبارت شرط م سیر تکرار نشان می دهد با چه مقادیری از متغیرها حلقه از این مسیر اجرا خواهد شد و عبارت چگونگی تغییر متغیرهای حلقه نشان می دهد که در این مسیر به مقدار هر یک از متغیرهای حلقه چه مقداری اضافه یا کم میگردد. سپس بر اساس این عبارات تعداد تکرار هر مسیر تکرار را بدست آورده و نهایتاً بیشترین زمان اجرای حلقه تکرار را محاسبه نمود. در ادامه مقاله، در بخش دوم به نحوه مدل سازی جریان اطلاعاتی حلقه در قالب عبارت نمادین پرداخته شده است. در بخش سوم چگونگی محاسبه بی شترین زمان اجرا ارائه گردیده ا ست. تخمین تعداد تکرار هر م سیر تکرار در بخش چهارم شرح داده شده ا ست. بخش پنجم به بیان کارهای مرتبط پرداخته است. در بخش ششم مثالی ارائه شده است. توانایی روش ارائه شده در بخش هفتم ارزیابی گردیده است و در نهایت در بخش هشتم نتیجه گیری و کارهای آینده شرح داده شده است.
-2 مدلسازی اطلاعات جریانی حلقه
تعداد تکرار حلقه های مبتنی بر شمارنده وابسته به مقادیری است که در طی تکرار حلقه به شمارنده انت ساب می گردد. معمولا در اینگونه حلقه ها، شمارنده با یک مقدار اولیه مقداردهی شده و در بدنه حلقه تکرار شمانده ا ضافه یا کم می گردد. پس از اینکه شرطی مبتنی بر مقدار این شمارنده درست گردد، حلقه خاتمه می یابد. بنابراین چگونگی تغییر شمارنده در بد نه حل قه تکرار بر روی ت عداد تکرار ها تاثیر خوا هد داشت. میزان کاهش/افزایش شمارنده وابسته به دستوراتی است که در بدنه حلقه شمارنده را مقداردهی می کنند و ممکن ا ست در هر تکرار حلقه واب سته به مسیری که حلقه اجرا می گردد، متفاوت باشد.
در بدنه یک حلقه تکرار، مسیرهای مختلفی وجود دارد که در هر تکرار، حلقه از یکی از این مسیرها، م سیر تکرار ، اجرا می گردد و در نهایت از یکی از این م سیرها، م سیر پایان، اجرای خود را خاتمه می دهد. در حقیقت دستورات انشعاب شرطی در بدنه حلقه تکرار سبب ایجاد مسیرهای اجرایی متفاوت می گردد. انتخاب دستور بعد از دستورات انشعاب شرطی وابسته به مقدار عبارت شرطی این دستورات خواهد بود. هر عبارت شرطی ترکیب فصلی یا عطفی عبارت رابطه ای می باشد که عملوندهای یک عبارت رابطه ای می توانند متغیرها و ثوابت باشند. بنابراین مقدار عبارت شرطی یک دستور انشعاب شرطی، bc، به مقدار متغیرها، v، در نقطه ای از برنامه،w، که دستور بکار رفته وابسته می باشد و با bc - v,w - آنرا می توان نمایش داد.
در ست یا نادر ست بودن این شرطها واب سته به مقدار متغیرهای ظاهر شده در عبارات شرطی آن می با شد. تعدادی از این متغیرها در بدنه حلقه تکرار تغییر می نمایند که به آن شمارنده گفته می شود. در این مقاله این نوع متغیرها متغیرهای کنترلی حلقه نامیده شده است. انتخاب هر یک از این م سیرها به مقدار متغیرهای کنترلی حلقه در ابتدای حلقه تکرار واب سته می با شد که مقدار آنها از تکرار قبلی بد ست آمده ا ست.
همچنین در تکرار بعدی مسیر تکرار بر اساس مقدار متغیرهای کنترلی در پایان این تکرار تعیین می گردد. بنابراین باید مشخص گردد که در هر مسیر تکرار نحوه تغییر متغیرهای کنترلی حلقه به چه صورت می باشد. عبارت نمادین نشان ده نده نحوه تغییر متغیر های کنترلی حل قه تابعی خوا هد بود که م قدار متغیرهای کنترلی را در انتهای مسیر تکرار فعلی cve - یا ابتدای مسیر تکرار بعدی - بر اساس مقدار متغیرهای کنترلی در ابتدای مسیر تکرار cvs محاسبه میکند.
-4 تخمین بیشترین تکرار برای هر مسیر
در بی شتر حلقه های تکرار عبارات شرطی - - bc یک نامعادله خطی می باشد. مجموعه جوابهای یک نامعادله خطی برابر یک نیم فضا از فضای n بعدی ا ست که تو سط معادله خطی متناظر با نامعادله تعریف می گردد. n تعداد متغیرهای کنترلی حلقه می باشد. یک شرط مسیر تکرار یا پایان یک دستگاه نامعادلات خطی از عبارات شرطی می باشد. پاسخ این دستگاه نامعادلات خطی تقاطع - اشتراک - نیم فضاهای تعریف شده توسط هر یک از نامعادلات خطی مربوط به عبارت شرطی میباشد. اگر هر یک از نیم فضا ها محدب باشد پاسخ دستگاه که اشتراک این نیم فضاها می باشد یک چندوجهی محدب خواهد بود. این چندوجهی میتواند بسته یا باز باشد.
برای حلقه هایی که شرط مسیر تکرار یک چند وجهی بسته باشد، هر نقطه درون این چند وجهی یک پاسخ برای دستگاه نامعادلات نشان دهنده شرط تکرار می با شد. به عبارتی دیگر هر پا سخ د ستگاه معادل چندتایی از مقدار متغیرهای کنترلی خواهد بود که عبارت شرط مسیر را به درست ارزیابی می کند. بنابراین تعداد نقاط درون چند وجهی برابر تعداد تمام حالات مقداردهی متغیرهای کنترلی خواهد بود. پس با محاسبه تعداد این پا سخ ها می توان حداکثر تعداد که حلقه می تواند از این م سیر اجرا گردد را محا سبه نمود .[6] با توجه به نحوه تغییر متغیرهای کنترلی وا ضح ا ست که بعضی از این نقاط هرگز انتخاب نخواهند شد و تخمین حاضر از حداکثر تکرار یک بیش تخمین4 خواهد بود.
برای اینکه مقدار تخمینی برای تعداد تکرار هر مسیر به مقدار واقعی آن نزدیک تر شود، تلاش می گردد که فضای n بعدی کاهش پیدا کند. بعبارت دیگر ت صویری از چند وجهی در ف ضای m بعدی - m<n - را بد ست می آوریم - شکل . - 1 واضح است نقاط درون چند وجهی بدست آمده به مراتب کمتر از چند وجهی اصلی خواهد بود. بنابراین برای تخمین تعداد تکرار هر مسیر مراحل زیر باید انجام گردد: با استفاده از یک حل کننده محدودیت[7] شرط مسیر را تست کرده و اگر شرط به نادر ست ارزیابی گردید، تعداد تکرار آنها صفر لحاظ می گردد. بدین ترتیب مسیرهای اجرا نشدنی5 شناسایی می گردد که در نزدیک بودن تخمین به مقدار واقعی بیشترین تعداد تکرار تاثیر بسزایی دارد.[1]
