نمایش مبدأ برای بهینه سازی حلقه

'''بهینه‌سازی حلقه''' در [[کامپایلر|تئوری کامپایلر]]، فرایند افزایش سرعت اجرا و کاهش سربارهای مربوط به [[:en:LOOP_(programming_language)|حلقه‌ها]] است. این فرایند نقش بسزایی در بهبود عملکرد [[حافظه نهان (رایانش)|حافظه نهان]] و استفاده مؤثر از قابلیت‌های [[رایانش موازی|پردازش موازی]] ایفا می‌کند. در واقع بیشترین زمان اجرای یک [[علم محاسبه|برنامه علمی]] در حلقه‌ها صرف می‌شود؛ و از این رو تکنیک‌های متعدد [[بهینه‌سازی کامپایلر|بهینه سازی کامپایلر]] برای اجرای سریعتر [[:en:LOOP_(programming_language)|حلقه‌ها]] ایجاد شده‌اند.

== نمایش محاسبه‌ها و تبدیل‌ها ==
از آنجا که دستورالعمل‌های داخل حلقه‌ها می‌توانند به‌طور مکرر اجرا شوند، در اغلب موارد ارائهٔ یک کران برای تعداد اجراهای متأثر از بهینه‌سازی حلقه غیرممکن است. این مشکل بررسی به‌جا بودن و درستی بهینه‌سازی حلقه و مزایای آن را در سناریوهای مختلف، چالش‌برانگیز کرده‌است.<ref name="Collard">In the book ''[https://books.google.com/books?id=8FbTZc4pa-cC&printsec=frontcover#v=snippet&q=%22loop%20optimization%22&f=false 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.</ref>

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

در ادامه تبدیل‌های متداول حلقه به صورت فهرست‌وار آمده‌اند.<ref name="UCB2">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</ref>
* [[Loop fission|شکافت]] یا توزیع - در این نوع تبدیل یک حلقه به چندین حلقهٔ کوچکتر که روی همان پیمایندهٔ اولیه پیمایش می‌کنند، تجزیه می‌شود. این تبدیل باعث افزایش [[Locality of reference|محلیت ارجاع حافظه]] (locality of refrence) می‌شود.
* [[Loop fusion|ادغام]] یا ترکیب - ترکیب بدنهٔ دو حلقهٔ نزدیک به هم که به تعداد دفعه‌های یکسان تکرار می‌شوند (چه این تعداد تکرار در زمان کامپایل مشخص باشد یا نه) را باهم ادغام می‌کند. لازم است ذکر شود که این دو حلقه نباید به یکدیگر ارجاع داشته باشند.
* [[Loop interchange|مبادله]] یا جایگیری - این بهینه‌سازی در حلقه‌های تودرتو، حلقهٔ درونی را با حلقهٔ بیرونی عوض می‌کند. مبادله در آرایه‌های چندبعدی می‌تواند موجب افزایش [[Locality of reference|محلیت ارجاع حافظه]] شود.
* [[Loop inversion|وارونگی]] - یک حلقهٔ while استاندارد را به یک حلقهٔ do/while که درون یک if هست تبدیل می‌کند و تعداد دفعه‌های jump را در زمان اجرای حلقه به ۲ بار کاهش می‌دهد. اگرچه این امر تعداد خط‌های کد را زیاد می‌کند اما درکل اجرا سریع‌تر می‌شود چراکه هر jump باعث '''[[حباب (رایانه)|حباب]]''' می‌شود. علاوه‌بر آن اگر حاصل شرط if اولیه در زمان کامپایل مشخص باشد، از if اولیه می‌شود صرف نظر کرد.
* [[Loop-invariant code motion|خارج کردن کد مستقل از حلقه]]- در این روش یک قطعه کد درون حلقه که هربار اجرایش نتیجه‌ای کاملاً یکسان و مستقل از پیمایشگر انجام می‌دهد، از حلقه بیرون می‌آید تا فقط یکبار اجرا شود. اهمیت این تبدیل بیشتر در محاسبهٔ آدرس در حلقه‌هایی که با آرایه سروکار دارند آشکار می‌شود و کارایی را بسیار بالا می‌برد. این تکنیک را باید همراه روش تبدیل استفاده کرد چراکه استخراج هر کدی از کل حلقه همواره کار مطمئنی نیست.
* [[Loop-level parallelism|موازی‌سازی]] - این تبدیل حالت خاصی از [[Automatic parallelization|موازی‌سازی خودکار]] است که روی حلقه‌ها انجام می‌شود و ساختار آن‌ها را به صورتی عوض می‌کند که روی پردازنده‌های چند هسته‌ای کاراتر اجرا شود. این امر را هم به صورت خوکار([[automatic parallelization]]) و هم به صورت دستی (درج دستورها موازی مثل [[اپن ام‌پی|OpenMP]]) می‌توان انجام داد.
* [[Loop reversal|بازگشت]]- یک بهینه‌سازی ظریف که ترتیب پیمایش حلقه را برعکس می‌کند و متغیر پیمایش درجهت عکس پیمایش را انجام می‌دهد. این تکنیک می‌تواند موجب حذف [[Dependence analysis|وابستگی‌ها]] شود و امکان انجام بهینه‌سازی‌های دیگر را فراهم کند. در ساختارهایی از حلقه‌هایی در سطح [[زبان اسمبلی|اسمبلی]] استفاده شود که فقط دریک جهت پیمایش انجام می‌دهد (مثلاً decrement-(jump-if-not-zero<ref>{{Cite web|url=https://www.win.tue.nl/~aeb/comp/8051/set8051.html-orig#51djnz|title=8051 Instruction Set|website=www.win.tue.nl|access-date=2019-12-09|archiveurl=https://web.archive.org/web/20150106064743/http://www.win.tue.nl/~aeb/comp/8051/set8051.html-orig#51djnz|archivedate=۶ ژانویه ۲۰۱۵|dead-url=yes}}</ref>)
* [[Loop scheduling|زمانبندی]] - یک حلقه را به چندین قسمت تجزیه‌می‌کند تا به صورت همزمان روی پردازه‌های چندهسته‌ای اجرا شود.
*  کج‌پیمایی  - هنگامی که در حلقه‌های تودرتو، هر مرحله از حلقهٔ داخلی وابسته به مراحل قبلیش است، با استفاده از این تبدیل ترتیب پیمایش را عوض می‌کنیم تا وابستگی مراحل فقط در حلقهٔ بیرونی باقی بماند.
* [[Software pipelining|خط‌لولهٔ نرم‌افزاری]] - یک اجرای [[خروج از دستور در حال اجرا|خارج از ترتیب]] دستورات حلقه است که تاخیرات بخش عملگر پردازه را کم می‌کند.
* [[Loop splitting|تقسیم]] یا لایه برداری - هدف از این تبدیل ساده‌سازی و حذف وابستگی‌های یک حلقه است. در این تکنیک یک حلقه به چندین حلقه با بدنهٔ یکسان با حلقهٔ اولیه شکسته می‌شود اما هریک محدوده پیمایش متفاوتی دارند. یک کاربرد این تبدیل برای حلقه‌ای است که چند پیمای اولش دشوار و مشکل است. بعد از لایه‌برداری بخش دشوار به صورت جدا قبل از حلقهٔ اولیه اجرا می‌شود.
* [[Loop tiling|کاشی‌کاری]] یا بلوک‌بندی - این تبدیل یک حلقه را به شکلی تغییر می‌دهد که روی بلوک‌هایی از داده پیمایش کند بطوریکه هر بلوک در حافظهٔ کش جا بشود.
* [[برداری‌سازی خودکار|بردار سازی]] - تلاش می‌کند تا حداکثر تعداد اجراهای یک حلقه‌را روی یک سامانهٔ [[یک دستور چند داده|SIMD]] اجرا کند.
* [[بازکردن حلقه|بازکردن]] - این تبدیل بدنهٔ حلقه‌را چندین بار کپی می‌کند تا تعداد بارهایی که شرط حلقه و پرش انجام می‌شود کاهش یابد چراکه این دستورها به علت تغضیف پایپلاین، تأثیر شگرفی در کاهش سرعت اجرا دارند. اگرچه بازکردن کامل یک حلقه تقریباً تمام این هزینه‌های اضافی را ازبین می‌برد اما منوط به معلوم بودن تعداد دفعه‌های اجرای حلقه در زمان کامپایل است. (به جز در حالت [[Just-in-time compilation]]). درکل تبدیل بازکردن زمانی مفید است که محاسبه چندین بارهٔ متغیر پیمایش هزینهٔ بیشتری از جلوبردن آن در حلقهٔ اولیه نداشته باشد.
* [[Loop unswitching|شرط‌زدایی]] - یک دستور شرطی درون حلقه‌را به بیرون منتقل می‌کند. این امر با کپی کردن بدنهٔ حلقه و قراردادن نسخه‌های آن هم در if و هم در else انجام می‌شود.
* [[Loop sectioning|بخشبندی]] - این تبدیل برای [[پردازنده برداری|پردازنده‌های برداری]] معرفی شد. بخشبندی حلقه نوعی تبدیل است که قابلیت رمزی کردن [[یک دستور چند داده|(SIMD]] (single instruction multiple data را ممکن می‌سازد و کارایی حافظه را افزایش می‌دهد. این امر بدین صورت محقق می‌شود که هر عملگر بردار حداکثر به اندازهٔ طول بردار بیشینه انجام می‌شود.<ref>[http://software.intel.com/en-us/articles/strip-mining-to-optimize-memory-use-on-32-bit-intel-architecture/]</ref><ref>[http://download.oracle.com/docs/cd/E19205-01/819-5262/aeugr/index.html]</ref>

=== چهارچوب تبدیل تکپیمانه‌ای ===
روش تبدیل تکپیمانه‌ای<ref name="Muchnick">Steven S. Muchnick, ''[https://books.google.com/books?id=Pq7pHwG1_OkC&printsec=frontcover#v=snippet&q=%22unimodular%20transformation%22&f=false Advanced Compiler Design and Implementation],'' 1997 Morgan Kaufmann. Section 20.4.2 discusses loop optimization.</ref> از یک ماتریس تک پیمانه‌ای برای توصیف نتیجهٔ اعمال دنباله‌ای از تبدیل‌های مذکور استفاده می‌کند. ایدهٔ اصلی این روش توصیف مجموعهٔ تمام اجراهای یک دستور در <math>n</math> حلقه به صورت یک مجموعه از نقاط با مختصات صحیح در فضای <math>n</math> بعدی است که این نقاط به [[Lexicographical order|ترتیب الفبایی]] اجرا می‌شوند. به عنوان مثال اجراهای یک گزاره که در دو حلقهٔ تودرتو با متغیر پیمایندهٔ بیرونی i و درونی j به صورت دوتایی<math>(i,j)</math> مدل می‌شود. یک تبدیل تک پیمانه‌ای متناظر با ضرب نقاط این فضا توسط ماتریس‌های تبدیل است. مثلاً ماتریس مربوط به جابه‌جایی حلقهٔ بیرونی با درونی <math>\begin{bmatrix}0&1\\1&0\end{bmatrix}</math> است. به صورت کلی یک تبدیل تک پیمانه‌ای زمانی صحیح است که تمام دنباله [[Data dependency|وابستگی‌های]] زمانی را حفظ کند. دشوارتر از آن، بررسی تأثیر تبدیل تک پیمانه‌ای را روی کارایی است. به این دلایل حلقه‌های تودرتوی معیوب و تبدیل‌هایی مثل بخشبندی به راحتی در این چهارچوب قابل انجام نیستند.

=== چهارچوب چندوجهی یا مبتنی بر شرط ===
[[Polytope model|مدل چندوجهی]]<ref name="AK3">R. Allen and K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann, 2002.</ref> گسترهٔ وسیعتری از کدها و تبدیل‌ها را درمقایسه با چهارچوب تک پیمانه‌ای پوشش می‌دهد. در این چهارچوب مجموعه اجراهای یک دسته از دستورها داخل حلقه‌های تودرتوی معیوب به صورت اجتماعی از چندوجهی‌هایی مدل می‌شود که اجرای دستورها را نشان می‌دهند. در ادامه [[Affine transformation|تبدیل‌های آفین]]، روی این چندوجهی‌ها اعمال می‌شود و توصیفی از ترتیب اجرای جدید بدست می‌آید. مرزهای چندوجهی‌ها، وابستگی‌های داده‌ای و تبدیل‌ها معمولاً توسط تعدادی شرط بیان می‌شوند و از این رو این چهارچوب را مبتنی بر شرط می‌نامند. برای مثال یک دستور در حلقهٔ تودرتو با حلقهٔ بیرونی '{{mono|1=for i := 0 to n}}' و حلقهٔ داخلی '{{mono|1=for j := 0 to i+۲}}' را درنظر بگیرید که به ازای هر جفت <math>(i,j)</math>  که  <math>0 \leq i \leq n</math> و <math>0 \leq j \leq i+2</math> اجرا شود.

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

== جستارهای وابسته ==
* [[:en:Loop_nest_optimization|بهینه سازی حلقهٔ تودرتو]]
* [[:en:Polytope_model|مدل پولیپ]]
* [[:en:Scalable_parallelism|موازی سازی مقیاس پذیر]]
* [[:en:Scalable_locality|محلیت ارجاع مقیاس پذیر]]

== منابع ==
{{پانویس|30em|۲}}
[[رده:بهینه‌سازی کامپایلر]]