موضوع مقاله: بهینه سازی حلقه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بهینه سازی حلقه | مقدمه: بهینه‌سازی حلقه در تئوری کامپایلر، فرایند افزایش سرعت اجرا و کاهش سربارهای مربوط به حلقه‌ها است. | ## بخش 1: بهینه سازی حلقه | این فرایند نقش بسزایی در بهبود عملکرد حافظه نهان و استفاده مؤثر از قابلیت‌های پردازش موازی ایفا می‌کند. در واقع بیشترین زمان اجرای یک برنامه علمی در حلقه‌ها صرف می‌شود؛ و از این رو تکنیک‌های متعدد بهینه سازی کامپایلر برای اجرای سریعتر حلقه‌ها ایجاد شده‌اند. نمایش محاسبه‌ها و تبدیل‌ها از آنجا که دستورالعمل‌های داخل حلقه‌ها می‌توانند به‌طور مکرر اجرا شوند، در اغلب موارد ارائهٔ یک کران برای تعداد اجراهای متأثر از بهینه‌سازی حلقه غیرممکن است. بهینه سازی با انجام دنباله ای از تبدیل‌های حلقه درعمل فرایند بهینه‌سازی حلقه را می‌توان اعمال دنباله‌ای از تبدیل‌های حلقه روی بازنمایی میانی دانست که هریک دارای محکی برای سنجش درستی و به‌جابودن هستند. یک تبدیل (یا دنباله‌ای از تبدیل‌ها) برای اینکه بتواند تضمین کند که کد حاصلش، نتیجهٔ کد اولیه را تولید خواهد کرد، به صورت کلی باید دنبالهٔ تمام وابستگی‌هایی که در ابتدا در کد بوده را حفظ کند. علاوه بر آن بررسی مفید بودن یک تبدیل در این روش دشوار است چراکه ممکن است بکارگیری یک تبدیل نیازمند انجام چندین تبدیل دیگری باشد که خود آن‌ها سربار محاسباتی ایجاد کنند. ادغام یا ترکیب - ترکیب بدنهٔ دو حلقهٔ نزدیک به هم که به تعداد دفعه‌های یکسان تکرار می‌شوند (چه این تعداد تکرار در زمان کامپایل مشخص باشد یا نه) را باهم ادغام می‌کند. مبادله یا جایگیری - این بهینه‌سازی در حلقه‌های تودرتو، حلقهٔ درونی را با حلقهٔ بیرونی عوض می‌کند. اگرچه این امر تعداد خط‌های کد را زیاد می‌کند اما درکل اجرا سریع‌تر می‌شود چراکه هر jump باعث حباب می‌شود. علاوه‌بر آن اگر حاصل شرط if اولیه در زمان کامپایل مشخص باشد، از if اولیه می‌شود صرف نظر کرد. خارج کردن کد مستقل از حلقه- در این روش یک قطعه کد درون حلقه که هربار اجرایش نتیجه‌ای کاملاً یکسان و مستقل از پیمایشگر انجام می‌دهد، از حلقه بیرون می‌آید تا فقط یکبار اجرا شود. اهمیت این تبدیل بیشتر در محاسبهٔ آدرس در حلقه‌هایی که با آرایه سروکار دارند آشکار می‌شود و کارایی را بسیار بالا می‌برد. این تکنیک را باید همراه روش تبدیل استفاده کرد چراکه استخراج هر کدی از کل حلقه همواره کار مطمئنی نیست. | ## بخش 2: بهینه سازی حلقه | موازی‌سازی - این تبدیل حالت خاصی از موازی‌سازی خودکار است که روی حلقه‌ها انجام می‌شود و ساختار آن‌ها را به صورتی عوض می‌کند که روی پردازنده‌های چند هسته‌ای کاراتر اجرا شود. بازگشت- یک بهینه‌سازی ظریف که ترتیب پیمایش حلقه را برعکس می‌کند و متغیر پیمایش درجهت عکس پیمایش را انجام می‌دهد. این تکنیک می‌تواند موجب حذف وابستگی‌ها شود و امکان انجام بهینه‌سازی‌های دیگر را فراهم کند. کج‌پیمایی - هنگامی که در حلقه‌های تودرتو، هر مرحله از حلقهٔ داخلی وابسته به مراحل قبلیش است، با استفاده از این تبدیل ترتیب پیمایش را عوض می‌کنیم تا وابستگی مراحل فقط در حلقهٔ بیرونی باقی بماند. خط‌لولهٔ نرم‌افزاری - یک اجرای خارج از ترتیب دستورات حلقه است که تاخیرات بخش عملگر پردازه را کم می‌کند. تقسیم یا لایه برداری - هدف از این تبدیل ساده‌سازی و حذف وابستگی‌های یک حلقه است. در این تکنیک یک حلقه به چندین حلقه با بدنهٔ یکسان با حلقهٔ اولیه شکسته می‌شود اما هریک محدوده پیمایش متفاوتی دارند. کاشی‌کاری یا بلوک‌بندی - این تبدیل یک حلقه را به شکلی تغییر می‌دهد که روی بلوک‌هایی از داده پیمایش کند بطوریکه هر بلوک در حافظهٔ کش جا بشود. بردار سازی - تلاش می‌کند تا حداکثر تعداد اجراهای یک حلقه‌را روی یک سامانهٔ SIMD اجرا کند. بازکردن - این تبدیل بدنهٔ حلقه‌را چندین بار کپی می‌کند تا تعداد بارهایی که شرط حلقه و پرش انجام می‌شود کاهش یابد چراکه این دستورها به علت تغضیف پایپلاین، تأثیر شگرفی در کاهش سرعت اجرا دارند. اگرچه بازکردن کامل یک حلقه تقریباً تمام این هزینه‌های اضافی را ازبین می‌برد اما منوط به معلوم بودن تعداد دفعه‌های اجرای حلقه در زمان کامپایل است. درکل تبدیل بازکردن زمانی مفید است که محاسبه چندین بارهٔ متغیر پیمایش هزینهٔ بیشتری از جلوبردن آن در حلقهٔ اولیه نداشته باشد. این امر با کپی کردن بدنهٔ حلقه و قراردادن نسخه‌های آن هم در if و هم در else انجام می‌شود. | ## بخش 3: بهینه سازی حلقه | این امر بدین صورت محقق می‌شود که هر عملگر بردار حداکثر به اندازهٔ طول بردار بیشینه انجام می‌شود. از یک ماتریس تک پیمانه‌ای برای توصیف نتیجهٔ اعمال دنباله‌ای از تبدیل‌های مذکور استفاده می‌کند. ایدهٔ اصلی این روش توصیف مجموعهٔ تمام اجراهای یک دستور در حلقه به صورت یک مجموعه از نقاط با مختصات صحیح در فضای بعدی است که این نقاط به ترتیب الفبایی اجرا می‌شوند. به عنوان مثال اجراهای یک گزاره که در دو حلقهٔ تودرتو با متغیر پیمایندهٔ بیرونی i و درونی j به صورت دوتایی مدل می‌شود. به صورت کلی یک تبدیل تک پیمانه‌ای زمانی صحیح است که تمام دنباله وابستگی‌های زمانی را حفظ کند. به این دلایل حلقه‌های تودرتوی معیوب و تبدیل‌هایی مثل بخشبندی به راحتی در این چهارچوب قابل انجام نیستند. گسترهٔ وسیعتری از کدها و تبدیل‌ها را درمقایسه با چهارچوب تک پیمانه‌ای پوشش می‌دهد. در این چهارچوب مجموعه اجراهای یک دسته از دستورها داخل حلقه‌های تودرتوی معیوب به صورت اجتماعی از چندوجهی‌هایی مدل می‌شود که اجرای دستورها را نشان می‌دهند. در ادامه تبدیل‌های آفین، روی این چندوجهی‌ها اعمال می‌شود و توصیفی از ترتیب اجرای جدید بدست می‌آید. مرزهای چندوجهی‌ها، وابستگی‌های داده‌ای و تبدیل‌ها معمولاً توسط تعدادی شرط بیان می‌شوند و از این رو این چهارچوب را مبتنی بر شرط می‌نامند. برای مثال یک دستور در حلقهٔ تودرتو با حلقهٔ بیرونی '' و حلقهٔ داخلی '' را درنظر بگیرید که به ازای هر جفت که و اجرا شود. مجدداً تکرارمی‌شود که یک تبدیل زمانی به‌جا است که دنبالهٔ زمانی وابستگی‌ها را حفظ کند. | ## جمع‌بندی | همچنین تخمین بهره‌وری یک تبدیل یا یافتن بهترین تبدیل برای یک مجموعه کد روی یک کامپیوترکماکان موضوع پژوهش‌های امروزه است (زمان نوشتار متن ۲۰۱۰).