Оптимизација петље

У теорији компајлера, оптимизација петљe је процес повећања брзине извршења и смањења трошкова везаних за петљу. Он игра важну улогу у побољшању кеш перформансе и ефективном коришћењу паралелног процеса могућности. Већи део времена извршења рачунарскe наукe се троши на петље ; многе технике оптимизације компилатора су развијене да их праве брже.

Представљање обрачуна и трансформација

Пошто се инструкције унутар петље могу поново извршавати , често није могуће дати границу о броју инструкција извршења која ће бити под утицајем од стране оптимизације петље. Ово представља изазове када се разматра исправност и бенефиције оптимизације петље, посебно представе израчунавања које се оптимизирају и оптимизација (е) које се обављају.

Оптимизација преко низа петљи трансформација

Оптимизација петље може да се посматра као примена низа специфичних петљи трансформације (наведено испод или у ) изворног кода или међујезика, са сваком трансформацијом која има упитни тест за законитост. Трансформација (или низ трансформација) генерално мора да чува временску секвенцу свих зависности података ако је очување резултат програма (тј. да буде исправна трансформација). Процена користи од трансформације или низа трансформација може бити прилично тешка у оквиру овог приступа, као и примена једне корисне трансформације може захтевати претходно коришћење једне или више других трансформација које, саме по себи, могу довести до пада перформанси.

Заједничке трансформације петљи

• фисија / расподела : фисија петље покушава да подели петљу у више петљи у истом опсегу индекса али тако да свака узима само део тела главне петље. Ово може побољшати локалност референце, оба података који приступају петљи и коду у телу главне петље. 
• фузија / комбиновање: Друга техника која покушава да смањи петље изнад главе. Када би два суседна петље поновити исти број пута (без обзира да ли тај број је позната по компајлирања), њихова тела могу се комбиновати све док се не помињу једни друге податке.
• размена / пермутација: Ове оптимизације размењују унутрашње петље са спољним петљама. Када је индекс променљиве петље у низу, таква трансформација може да побољша локалност референци, у зависности од распореда низа целине.
• инверзија: Ова техника мења стандард док петља у do/while (такође познато и као repeat/until) петљу умотану као if условно, смањење броја скокова са два за случајеве у којима се извршава петља. На тај начин дуплира проверу стања (повећање величине кода), али је ефикаснија, јер скокови обично узрокују губитак брзине цевовода . Поред тога, ако је почетно стање познато у компајлирању времену и зна се да нема нуспојава, if стражар може бити прескочен.
• кретање инваријантне петље :  Ако се количина рачуна унутар петље током сваког понављања, а њена вредност је иста за сваку итерацију, то много може побољшати ефикасност да га избаци испред петље и израчуна његову вредност само једном пре него што почне петља. Ово је посебно важно са адресом-прорачуна израза које генеришу петље преко низова. За правилну имплементацију, ова техника се мора користити помоћу инверзне петље, јер нису сви кодови сигурни да могу бити истицани изван петље.
• паралелизација: Посебан случај за аутоматску паралелизацију фокусирања на петљама, реструктурирање истих како би ефикасно радиле на мултипроцесорским системима. То може бити аутоматски урађено помоћу компајлера (названо аутоматска паралелизација) или ручно (убацивање паралелних задатака као OpenMP ).
• Преокрет: Преокрет петље обрће редослед којим су вредности додељене индексима променљивих. То је суптилна оптимизација што може да помогне елиминацији зависности и на тај начин омогући друге оптимизације. Такође, поједине архитектуре користе петље конструкције на нивоу Асемблера који рачуна у једном правцу (нпр. декрементирани скок ако није нула (ДСНО)).
• распоред петљи : Паспоред петље дели петљу у више делова који се могу истовремено радити на више процесора.
• кривљење медијума : Кривљење медијума петље узима груписање петљи по корену итерације преко мултидимензионалног низа, где сваки низ итерација унутрашњe петљe зависи од ранијих итерација, и уређује његов низ приступа, тако да су само зависности између понављања спољашње петље.
• деоба софтвера : Тип ванредног извршавања итерација петље како би се сакрила кашњења у функцији процесорских јединица.
• цепање / пилинг : Раздвајање петље покушава да поједностави петљу или елиминише анализу зависности од разбијања петље у више петљи које имају исто тело, али понавља више различитих и суседних делова опсега индекса. Користан и посебан случај је пилинг петља, која може поједноставити петље са проблематичном првом итерацији вршећи ту итерацију одвојено пре уласка у петљу.
• плочице / блокирање : Плочице петље реорганизују петљу да понавља више блокова података такве величине да се уклапају у кеш.
• векторизација : Векторизација покушава да покрене што више итерација петље што је могуће у исто време на систему са више процесора.
• одмотавање петље: Дуплира тело петље више пута, како би се смањио број пута колико је услов петље тестиран и број скокова, што може смањити перформансе и угрозити инструкције цеви. Потпуно одмотавање петље елиминише све изнад врха петље (осим ако више упутстава нађу и повећају време учитавања програма), али захтева да број итерација буде познат у  времену компајлирања (осим у случају JIT компајлера). Мора се водити рачуна да вишеструко поновно израчунавање индексираних променљивих није веће од напредовање показивача у оригиналу петље.
• пребацивање: Пребацивање помера условно унутар петље ван ње умножавањем тела петље, и стављањем верзије тога унутар сваког од if и else клаузула кондиционала.

Друге оптимизације петљи

• секционисање: Први пут представљено за векторске процесоре, петља-секционисање (такође позната као отворено копање) је техника петља-трансформација за омогућавање SIMD-кодирања петљи и побољшања перформанси меморије. Ова техника подразумева сваки вектор операција који се направи за величину мању или једнаку са максималним трајањем векторске дужине на датој векторској машини.[2] [3]

Унимодуларна трансформација оквира

Унимодуларни приступ трансформација користи једну унимодуларну матрицу да опише комбиновани резултат једне секвенце од многих горњих трансформација. У центру овог приступа је поглед на скуп свих погубљења једног успеха у оквиру петље n као скуп целих бодова у n-димензионалном простору, са тачке која се врши у циљу лексикографског реда. На пример, погубљења у саопштењу смештена унутар спољашње петље са индексом i  и унутрашње петље са индексом ј може бити повезана са паровима бројева ( i, ј). Примена унимодуларне трансформације одговара умножавању тачака у оквиру овог простора од стране матрице. На пример, размена две петље одговара матрици $\left[{\begin{array}{cc}0&1\\1&0\end{array}}\right]$.

Унимодуларна трансформација је исправна ако чува временски редослед свих зависности података; мерење утицаја на перформансе од стране унимодуларне трансформације је теже. Несавршено угнежђене петље и неке трансформације (као што је плочица) се не уклопају лако у том оквиру.

Полиедар или ограничење засновано на оквиру

Модел многограника рукује широм класом програма и трансформација него унимодуларни оквир. Скуп извршења скупа исказа у оквиру евентуално несавршено уметнутог скупа петљи се види као заједница скупа полиедра и представља извршење изјава. Трансформација пресликавања се примењује на ове полиедре, производећи опис новог извршења налога. Границе полиедара, зависност података, као и трансформације често описане коришћењем система ограничења, и овај приступ се често назива као ограничење приступа заснованог на оптимизацији петље. На пример, један исказ унутар спољашње петље  'for i := 0 to n' и једна унутрашња петља 'for j := 0 to i+2' се извршава једном за сваки (i, j) пар као да је 0 <= i <= n   и   0 <= j <= i+2.

Још једном, трансформација је исправна ако чува временски редослед свих зависности података. Процена предности трансформације, или проналажење најбоље трансформације за дати код на датом рачунару, и даље је предмет у току истраживања, као у време писања овог текста.

Види још

• Оптимизација гнезда петље
• Модел полиедра
• Скалабилни паралелизам
• Скалабилна локалност