روشی مبتنی بر تطبیق الگو برای تخمین بیشترین زمان اجرای حلقه‌های یکنواخت چندمسیری

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