روشی مبتنی بر تطبیق الگو برای تخمین بیشترین زمان اجرای حلقه‌های یکنواخت چندمسیری
محورهای موضوعی : مهندسی برق و کامپیوترمهدی سخائی نیا 1 , سعید پارسا 2
1 - دانشگاه بوعلی سینا
2 - دانشگاه علم و صنعت ايران
کلید واژه:
چکیده مقاله :
روش تطبیق الگو یکی از روش‌هایی است که برای تخمین بیشترین زمان اجرای حلقه‌ها ارائه شده است. در این روش در صورتی که حلقه با الگوی ارائه‌شده تطبیق داشت با استفاده از یک معادله، بیشترین تعداد تکرار حلقه محاسبه می‌گردد. در حقیقت برای محاسبه تعداد تکرار نیازی نیست که مقدار متغیرهای کنترلی حلقه برای هر تکرار محاسبه گردد. نقص روش تطبیق الگو وابستگی زیاد آن به الگو است. این وابستگی به ساختار و محل شرط تست‌کننده متغیر کنترلی حلقه و از سوی دیگر به محل، نحوه و تعدد تغییر متغیر کنترلی حلقه مرتبط است. برای کاهش وابستگی به الگو می‌توان جریان اطلاعات برای حلقه‌های یکنواخت چندمسیری در قالب دو دسته عبارت نمادین، نشان‌دهنده شرط تکرار و نحوه تغییر متغیرهای کنترلی حلقه را مدل‌سازی کرد. بر اساس این عبارات، تعداد مقادیر ممکن که در زمان اجرا می‌توان به متغیرهای کنترلی حلقه تخصیص داد محاسبه و به عنوان تخمینی از بیشترین تعداد تکرار ارائه می‌گردد. اما تخمین ارائه‌شده در این روش بیشتر از مقدار واقعی است و در اصطلاح دارای بیش‌تخمین خواهد بود. در این مقاله، متغیرهایی که مقدارشان در مسیرهای تکرار مختلف یکسان هستند و در هر چند مسیر این مقدار به عنوان یک تکرار محاسبه گردیده است، شناسایی و در محاسبه‌ها لحاظ می‌گردند. این کار باعث می‌گردد که مقدار بیش‌تخمین کاهش یابد. ارزیابی‌ها نشان داد که روش ارائه‌شده در این مقاله روشی مؤثر و کارا بوده و بیش‌تخمین کمتری دارد.
Pattern matching is one of possible methods proposed for estimating the WCET of the loops. If the loop matches with the proposed pattern, the number of iterations is calculated using an equation. In fact, the derivation of counter values for all iterations is thus avoided. A shortcoming of pattern matching methods is its excessive dependence upon patterns. It is dependent upon location, frequency and how to change in value of the counter and structure and place of counter tester. In order to reduce dependence upon patterns, loop flow can be modeled in two sets of symbolic expressions indicating iteration conditions and changes in value of counters. Based upon these expressions, the number of possible values that could be assigned to the loop control variables during the loop execution is computed as the worst-case estimation of the number of loop iterations. But the estimate presented in this method is greater than the actual value and there is overestimation. In this paper, the variables whose values are equal on the different paths and this value is accounted as an iteration, are detected and are considered in the estimations. This will reduce the overestimation. The evaluations are showed that the proposed method is effective and efficient and has less overestimation.
