بهینه سازی حلقه

بهینه‌سازی حلقه در تئوری کامپایلر، فرایند افزایش سرعت اجرا و کاهش سربارهای مربوط به حلقه‌ها است. این فرایند نقش بسزایی در بهبود عملکرد حافظه نهان و استفاده مؤثر از قابلیت‌های پردازش موازی ایفا می‌کند. در واقع بیشترین زمان اجرای یک برنامه علمی در حلقه‌ها صرف می‌شود؛ و از این رو تکنیک‌های متعدد بهینه سازی کامپایلر برای اجرای سریعتر حلقه‌ها ایجاد شده‌اند.

نمایش محاسبه‌ها و تبدیل‌ها

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

بهینه سازی با انجام دنباله ای از تبدیل‌های حلقه

درعمل فرایند بهینه‌سازی حلقه را می‌توان اعمال دنباله‌ای از تبدیل‌های حلقه روی بازنمایی میانی دانست که هریک دارای محکی برای سنجش درستی و به‌جابودن هستند. یک تبدیل (یا دنباله‌ای از تبدیل‌ها) برای اینکه بتواند تضمین کند که کد حاصلش، نتیجهٔ کد اولیه را تولید خواهد کرد، به صورت کلی باید دنبالهٔ تمام وابستگی‌هایی که در ابتدا در کد بوده را حفظ کند. علاوه بر آن بررسی مفید بودن یک تبدیل در این روش دشوار است چراکه ممکن است بکارگیری یک تبدیل نیازمند انجام چندین تبدیل دیگری باشد که خود آن‌ها سربار محاسباتی ایجاد کنند.

در ادامه تبدیل‌های متداول حلقه به صورت فهرست‌وار آمده‌اند.[2]

شکافت یا توزیع - در این نوع تبدیل یک حلقه به چندین حلقهٔ کوچکتر که روی همان پیمایندهٔ اولیه پیمایش می‌کنند، تجزیه می‌شود. این تبدیل باعث افزایش محلیت ارجاع حافظه (locality of refrence) می‌شود.
ادغام یا ترکیب - ترکیب بدنهٔ دو حلقهٔ نزدیک به هم که به تعداد دفعه‌های یکسان تکرار می‌شوند (چه این تعداد تکرار در زمان کامپایل مشخص باشد یا نه) را باهم ادغام می‌کند. لازم است ذکر شود که این دو حلقه نباید به یکدیگر ارجاع داشته باشند.
مبادله یا جایگیری - این بهینه‌سازی در حلقه‌های تودرتو، حلقهٔ درونی را با حلقهٔ بیرونی عوض می‌کند. مبادله در آرایه‌های چندبعدی می‌تواند موجب افزایش محلیت ارجاع حافظه شود.
وارونگی - یک حلقهٔ while استاندارد را به یک حلقهٔ do/while که درون یک if هست تبدیل می‌کند و تعداد دفعه‌های jump را در زمان اجرای حلقه به ۲ بار کاهش می‌دهد. اگرچه این امر تعداد خط‌های کد را زیاد می‌کند اما درکل اجرا سریع‌تر می‌شود چراکه هر jump باعث حباب می‌شود. علاوه‌بر آن اگر حاصل شرط if اولیه در زمان کامپایل مشخص باشد، از if اولیه می‌شود صرف نظر کرد.
خارج کردن کد مستقل از حلقه- در این روش یک قطعه کد درون حلقه که هربار اجرایش نتیجه‌ای کاملاً یکسان و مستقل از پیمایشگر انجام می‌دهد، از حلقه بیرون می‌آید تا فقط یکبار اجرا شود. اهمیت این تبدیل بیشتر در محاسبهٔ آدرس در حلقه‌هایی که با آرایه سروکار دارند آشکار می‌شود و کارایی را بسیار بالا می‌برد. این تکنیک را باید همراه روش تبدیل استفاده کرد چراکه استخراج هر کدی از کل حلقه همواره کار مطمئنی نیست.
موازی‌سازی - این تبدیل حالت خاصی از موازی‌سازی خودکار است که روی حلقه‌ها انجام می‌شود و ساختار آن‌ها را به صورتی عوض می‌کند که روی پردازنده‌های چند هسته‌ای کاراتر اجرا شود. این امر را هم به صورت خوکار(automatic parallelization) و هم به صورت دستی (درج دستورها موازی مثل OpenMP) می‌توان انجام داد.
بازگشت- یک بهینه‌سازی ظریف که ترتیب پیمایش حلقه را برعکس می‌کند و متغیر پیمایش درجهت عکس پیمایش را انجام می‌دهد. این تکنیک می‌تواند موجب حذف وابستگی‌ها شود و امکان انجام بهینه‌سازی‌های دیگر را فراهم کند. در ساختارهایی از حلقه‌هایی در سطح اسمبلی استفاده شود که فقط دریک جهت پیمایش انجام می‌دهد (مثلاً decrement-(jump-if-not-zero[3])
زمانبندی - یک حلقه را به چندین قسمت تجزیه‌می‌کند تا به صورت همزمان روی پردازه‌های چندهسته‌ای اجرا شود.
کج‌پیمایی - هنگامی که در حلقه‌های تودرتو، هر مرحله از حلقهٔ داخلی وابسته به مراحل قبلیش است، با استفاده از این تبدیل ترتیب پیمایش را عوض می‌کنیم تا وابستگی مراحل فقط در حلقهٔ بیرونی باقی بماند.
خط‌لولهٔ نرم‌افزاری - یک اجرای خارج از ترتیب دستورات حلقه است که تاخیرات بخش عملگر پردازه را کم می‌کند.
تقسیم یا لایه برداری - هدف از این تبدیل ساده‌سازی و حذف وابستگی‌های یک حلقه است. در این تکنیک یک حلقه به چندین حلقه با بدنهٔ یکسان با حلقهٔ اولیه شکسته می‌شود اما هریک محدوده پیمایش متفاوتی دارند. یک کاربرد این تبدیل برای حلقه‌ای است که چند پیمای اولش دشوار و مشکل است. بعد از لایه‌برداری بخش دشوار به صورت جدا قبل از حلقهٔ اولیه اجرا می‌شود.
کاشی‌کاری یا بلوک‌بندی - این تبدیل یک حلقه را به شکلی تغییر می‌دهد که روی بلوک‌هایی از داده پیمایش کند بطوریکه هر بلوک در حافظهٔ کش جا بشود.
بردار سازی - تلاش می‌کند تا حداکثر تعداد اجراهای یک حلقه‌را روی یک سامانهٔ SIMD اجرا کند.
بازکردن - این تبدیل بدنهٔ حلقه‌را چندین بار کپی می‌کند تا تعداد بارهایی که شرط حلقه و پرش انجام می‌شود کاهش یابد چراکه این دستورها به علت تغضیف پایپلاین، تأثیر شگرفی در کاهش سرعت اجرا دارند. اگرچه بازکردن کامل یک حلقه تقریباً تمام این هزینه‌های اضافی را ازبین می‌برد اما منوط به معلوم بودن تعداد دفعه‌های اجرای حلقه در زمان کامپایل است. (به جز در حالت Just-in-time compilation). درکل تبدیل بازکردن زمانی مفید است که محاسبه چندین بارهٔ متغیر پیمایش هزینهٔ بیشتری از جلوبردن آن در حلقهٔ اولیه نداشته باشد.
شرط‌زدایی - یک دستور شرطی درون حلقه‌را به بیرون منتقل می‌کند. این امر با کپی کردن بدنهٔ حلقه و قراردادن نسخه‌های آن هم در if و هم در else انجام می‌شود.
بخشبندی - این تبدیل برای پردازنده‌های برداری معرفی شد. بخشبندی حلقه نوعی تبدیل است که قابلیت رمزی کردن (SIMD (single instruction multiple data را ممکن می‌سازد و کارایی حافظه را افزایش می‌دهد. این امر بدین صورت محقق می‌شود که هر عملگر بردار حداکثر به اندازهٔ طول بردار بیشینه انجام می‌شود.[4][5]

چهارچوب تبدیل تکپیمانه‌ای

روش تبدیل تکپیمانه‌ای[6] از یک ماتریس تک پیمانه‌ای برای توصیف نتیجهٔ اعمال دنباله‌ای از تبدیل‌های مذکور استفاده می‌کند. ایدهٔ اصلی این روش توصیف مجموعهٔ تمام اجراهای یک دستور در $n$ حلقه به صورت یک مجموعه از نقاط با مختصات صحیح در فضای $n$ بعدی است که این نقاط به ترتیب الفبایی اجرا می‌شوند. به عنوان مثال اجراهای یک گزاره که در دو حلقهٔ تودرتو با متغیر پیمایندهٔ بیرونی i و درونی j به صورت دوتایی $(i,j)$ مدل می‌شود. یک تبدیل تک پیمانه‌ای متناظر با ضرب نقاط این فضا توسط ماتریس‌های تبدیل است. مثلاً ماتریس مربوط به جابه‌جایی حلقهٔ بیرونی با درونی ${\begin{bmatrix}0&1\\1&0\end{bmatrix}}$ است. به صورت کلی یک تبدیل تک پیمانه‌ای زمانی صحیح است که تمام دنباله وابستگی‌های زمانی را حفظ کند. دشوارتر از آن، بررسی تأثیر تبدیل تک پیمانه‌ای را روی کارایی است. به این دلایل حلقه‌های تودرتوی معیوب و تبدیل‌هایی مثل بخشبندی به راحتی در این چهارچوب قابل انجام نیستند.

چهارچوب چندوجهی یا مبتنی بر شرط

مدل چندوجهی[7] گسترهٔ وسیعتری از کدها و تبدیل‌ها را درمقایسه با چهارچوب تک پیمانه‌ای پوشش می‌دهد. در این چهارچوب مجموعه اجراهای یک دسته از دستورها داخل حلقه‌های تودرتوی معیوب به صورت اجتماعی از چندوجهی‌هایی مدل می‌شود که اجرای دستورها را نشان می‌دهند. در ادامه تبدیل‌های آفین، روی این چندوجهی‌ها اعمال می‌شود و توصیفی از ترتیب اجرای جدید بدست می‌آید. مرزهای چندوجهی‌ها، وابستگی‌های داده‌ای و تبدیل‌ها معمولاً توسط تعدادی شرط بیان می‌شوند و از این رو این چهارچوب را مبتنی بر شرط می‌نامند. برای مثال یک دستور در حلقهٔ تودرتو با حلقهٔ بیرونی 'for i := 0 to n' و حلقهٔ داخلی 'for j := 0 to i+۲' را درنظر بگیرید که به ازای هر جفت $(i,j)$ که $0\leq i\leq n$ و $0\leq j\leq i+2$ اجرا شود.

مجدداً تکرارمی‌شود که یک تبدیل زمانی به‌جا است که دنبالهٔ زمانی وابستگی‌ها را حفظ کند. همچنین تخمین بهره‌وری یک تبدیل یا یافتن بهترین تبدیل برای یک مجموعه کد روی یک کامپیوترکماکان موضوع پژوهش‌های امروزه است (زمان نوشتار متن ۲۰۱۰).

جستارهای وابسته

منابع

In the book Reasoning About Program Transformations, Jean-Francois Collard discusses in depth the general question of representing executions of programs rather than program text in the context of static optimization.
David F. Bacon, Susan L. Graham, and Oliver J. Sharp. Compiler transformations for high-performance computing. Report No. UCB/CSD 93/781, Computer Science Division-EECS, University of California, Berkeley, Berkeley, California 94720, November 1993 (available at CiteSeer). Introduces compiler analysis such as data dependence analysis and interprocedural analysis, as well as a very complete list of loop transformations
"8051 Instruction Set". www.win.tue.nl. Archived from the original on 6 January 2015. Retrieved 2019-12-09.
Steven S. Muchnick, Advanced Compiler Design and Implementation, 1997 Morgan Kaufmann. Section 20.4.2 discusses loop optimization.
R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann, 2002.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Collard-1] In the book Reasoning About Program Transformations, Jean-Francois Collard discusses in depth the general question of representing executions of programs rather than program text in the context of static optimization.

[UCB2-2] David F. Bacon, Susan L. Graham, and Oliver J. Sharp. Compiler transformations for high-performance computing. Report No. UCB/CSD 93/781, Computer Science Division-EECS, University of California, Berkeley, Berkeley, California 94720, November 1993 (available at CiteSeer). Introduces compiler analysis such as data dependence analysis and interprocedural analysis, as well as a very complete list of loop transformations

[3] "8051 Instruction Set". www.win.tue.nl. Archived from the original on 6 January 2015. Retrieved 2019-12-09.

[Muchnick-6] Steven S. Muchnick, Advanced Compiler Design and Implementation, 1997 Morgan Kaufmann. Section 20.4.2 discusses loop optimization.

[AK3-7] R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann, 2002.