برنامهریزی اثر محور
برنامهریزی اثرمحور یک روش بهینهسازی است که توسط جاش فیشر طراحی شده و توسعه یافته و در کامپایلرها برای برنامههای کامپیوتری استفاده میشود.
تعریف[ویرایش]
برنامهریزی اثر محور، یک راه حل برای «مشکل جهانی بهینهسازی ریزکد» است. این مشکل، تبدیل یک میکروکد عمودی(vertical) (متوالی(sequential))نوشته شده برای دستگاهی با میکروکد افقی به به یک میکروکد افقی(horizontal) (موازی(parallel)) کارآمد است و به همین دلیل این روند به جای «بهینه سازی» با عنوان «فشرده سازی» شناخته میشود.
فشردهسازی دارای انواع مختلفی از جمله فشردهسازی محلی(local) و جهانی(global) است. هر کدام از این انواع دارای متدهای زمانبندی و برنامهریزی مربوط به خود هستند. به صورت کلی برنامهریزی اثرمحور از فشردهسازی محلی به عنوان یکی از گامهای خوذ استفاده میکند. در فرایند استفاده برنامهریزی اثرمحور برای فشردهسازی جهانی سادهترین الگوریتم ممکن یک برنامه را به بلوکهای اولیه آن تقسیم کرده و فشردهسازی محلی را به هر کدام اعمال میکند. اگرچه آزمایشها نشان میدهند که عمده موازی گرایی در فراتر از مرزهای بلوکهای مختلف پیدا میشود، زیرا بلوکهای میکروکدتولید شده کوتاه هستند و فشرده سازیهایی که به دست میآیند پر از «سوراخ» و مشکل هستند.
روش[ویرایش]
یک کامپایلر اغلب میتواند با چینش دوباره دستورالعملهای ماشین تولید شده اش به منظور اجرای سریع تر، عملکرد برنامه را بهبود ببخشد. کامپایلر میزان موازیسازی سطح دستورها ((ILP(Instruction Level Parallelism) را در امتداد مسیرهای اجرایی مهم به وسیله پیشبینی استاتیک مسیرهای اجرایی پرتکرار افزایش میدهد. برنامهریزی اثر محور یکی از بسیاری از روشهای شناخته شده برای انجام این کار است.
در این روش از فرایند پیشبینی استاتیک شاخهها استفاده میکنیم تا بلوکهای اساسی بزرگتری به وسیله انتخاب دستورالعملها از بهترین جریان کنترل درست کنیم. به این روند، «اثر»(trace)میگویند. «اثر» دنبالهای از دستورالعملها است که شامل شاخه خواهد شد اما شامل حلقه نمیشود که برای مقداری داده ورودی اجرا میشود. برنامهریزی اثر محور از یک روش زمانبندی بلوک محور برای زمانبندی دستورالعملها در هر یک از «اثر» ها، با شروع از «اثر» با بالاترین فرکانس، استفاده میکند. سپس یک کد تضمین را در مرحله ورودی و خروجی هر «اثر» اضافه میکند تا هر گونه تأثیری که ممکن است اجرای خارج از عرف کد داشته باشد را برطرف کند.
این مسئله میتواند موجب افزایش زیاد حجم کد و عملکرد ضعیف یا نامنظم برنامه بشود اگر رفتار برنامه نسبت به ورودیهای مختلف بهطور قابل توجهی تغییر کند.
برنامهریزی اثرمحور در ابتدا برای دستورالعملهای بسیار طولانی یا ماشینهای VLIW طراحی شده بود و یک شکل از حرکت کد جهانی است. این فرایند به وسیله تبدیل حلقه به دنباله طولانی و مستقیمی از کد با استفاده از باز کردن حلقه و پیشبینی شاخههای استاتیک کار میکند. این فرایند، کد «غیرمحتمل» (از نظر اجرا شدن) را از کد اصلی جدا میکند و برای قسمتهای خروجی «اثر» سامانه مدیریت قرار میدهد. هدف از این قسمت آن است که مختملترین قسمت و بهترین مورد به عنوان مجموعهای از دستورالعملهای بدون شاخه اجرا شود.
منابع[ویرایش]
- جوزف آ. فیشر : Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Trans. Computers, 1981
- نویسندگان ویکیپدیا: Trace Scheduling.
- سایت دانشگاه مهندسی برق داشنگاه هاوایی : Trace_sched بایگانیشده در ۹ اوت ۲۰۱۶ توسط Wayback Machine.