Одмотавање петље

Из Википедије, слободне енциклопедије
Emblem-important-yellow.svg Ова страница би требало да спада у једну или више категорија.
Молимо вас да је категоришете како би могла да се повеже са сличним страницама.
Уклоните ову поруку након категоризације странице.

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

Циљ одмотавања петље је увећање брзине програма смањењем или елиминисањем инструкција које контролишу петљу, као што су аритметички показивач и "end of loop" тестови за сваку итерацију; смањење грешака грањања; као и "скривене латенције, посебно, кашњење читања података из меморије". Да би елиминисале ове трошкове, петље могу бити поново написане као поновљена секвенца сличних независних исказа.

Предности[уреди]

Трошкови у "тесним" петљама се често састоје из инструкција за инкрементирање показивача или индекса до следећег елемента у низу (аритметички показивач), као и "end of loop" тестова. Ако је оптимизирајући компајлер или асеблер у могућности да израчуна офсете за сваку индивидуално референцирану промењиву из низа, оне се могу уградити у инструкције машинског кода директно, па не захтевају додатне аритметичке операције током извршења (ово није случај у примеру доле).

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

Оптимизирајући компајлери ће понекад извршити одмотавање аутоматски или по захтеву.

Мане[уреди]

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

Ручно – мануелно одмотавање петље[уреди]

Ручно (или статичко) одмотавање укључује програмера који алализира петљу и интерпретира итерације у секвенције инструкција које ће смањити трошкове петље. Ово је супротно динамичком одмотавању које одрађује компајлер.

Једноставни ручни пример у C[уреди]

Следи процедура у програму која брише 100 ствари из скупа. Ово се нормално ради преко for – петље која позива функцију delete(item_number). Ако је ово део програма који треба оптимизирати, и трошкови петље захтевају озбиљне ресурсе у поређењу са оним у delete(x) петљи, одмотавање га може убрзати.

Нормална пеља Након одмотавања петље
 int x;
 for (x = 0; x < 100; x++)
 {
     delete(x);
 }
 int x; 
 for (x = 0; x < 100; x+=5)
 {
     delete(x);
     delete(x+1);
     delete(x+2);
     delete(x+3);
     delete(x+4);
 }

Као резултат ове модификације, новом програму треба само 20 итерација уместо 100. После, само 20% скокова и кондиционалног гранања морају се обавити, и репрезентују, преко много итерација, потенцијално значајно увећање у администрацији трошкова петље. Да би направили оптималне бенефиције, ниједна промењива се не сме спецификовати у одмотаном коду који захтева аритметику показивача. Ово обично захтева "base plus offset" адресирање уместо индексираног референцирања.

Са друге стране, ово одмотавање шири изворни код са 3 на 7 линија које морају да се направе, провере и дебагују, и компајлер можда мора да алоцира више регистра за чување промењивих у проширеној итерацији петље. Додатно, промењиве контроле петље и број операција у структури одмотаное петље морају се одабрати пажљиво тако да резултат буде исти као и оригинални код. На пример, импликације ће бити велике ако укупан број итерација није дељив са 5. Ручне поправке постају компликованије ако су промењиви тест услови.

Рана комплексност[уреди]

У простом случају, контрола петље је административни трошак који уређује продуктивне исказе. Сама петља не доприноси жељеним резултатима, што олакшава програмеру да не мора да рециплира код стотине пута што се могло урадити помоћу генерација репликација или текст едитора. Слично, if искази и други искази контроле тока се могу заменити кодном репликацијом. Програми лако прате комбинације, али програмерима је ово понављање досадно и праве грешке. Имајмо у виду:

Нормална петља Након одмотавања петље
for i := 1:8 do
    if i mod 2 = 0 then do_evenstuff(i) 
                   else do_oddstuff(i);
    next i;
do_oddstuff(1); do_evenstuff(2);
do_oddstuff(3); do_evenstuff(4);
do_oddstuff(5); do_evenstuff(6);
do_oddstuff(7); do_evenstuff(8);

Али наравно, извршени код не мора да буде буђење процедуре, и следећи пример укључује индексну промењиву у рачунању:

Нормална петља Након одмотавања петље
x(1) := 1;
For i := 2:9 do
    x(i) := x(i - 1)*i;
    print i,x(i);
    next i;
x(1) := 1;
x(2) := x(1)*2; print 2,x(2);
x(3) := x(2)*3; print 3,x(3);
x(4) := x(3)*4; print 4,x(4);
...etc.

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

print 2,2;
print 3,6;
print 4,24;
...etc.

Било би прави изненађење ако компајлер препозна да је x(n) = Factorial(n).

Генерално, садржај петље може бити велики, укључујући запетљано индексирање низа. Ове случајеве је вероватно најбоље оставити за оптимизујуће компајлере. Реплицирање унутрашњих петљи може дозволити много могућих оптимизација а да добитак буде мали осим ако је n велико.

Одмотавање WHILE петљи[уреди]

Псеудокод WHILE петље – сличан следећем:

Нормална петља Након одмотавања петље Одмотана и сређена петља
  WHILE (condition) DO
         action
  ENDWHILE
.
.
.
.
.
.
  WHILE (condition) DO
         action
         IF NOT(condition) THEN GOTO break
         action
         IF NOT(condition) THEN GOTO break
         action
 ENDWHILE
 LABEL break:
.
 IF (condition) THEN
  REPEAT {
         action
         IF NOT(condition) THEN GOTO break
         action
         IF NOT(condition) THEN GOTO break
          action
         } WHILE (condition)
 LABEL break:

Одмотавање је брже јер ENDWHILE (који ће се компајлирати у jump на почетку петље) ће бити извршено 66% мање.

Још боље, сређени псеудокод, који се може извршити аутоматски некоим опримизујучим компајлерима, елиминишући безусловне скокове потпуно.

Динамичко одмотавање[уреди]

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

Програмери асемблерског језика (укључујући писце оптимизујућих компајлера) су у бенефицији и од технике динамичког одмотавања петље, користећи метод сличан коришћеном у ефикасним таблама гранања. Овде је предност највећа где је максимум офсета који се може специфирати машинском инструкцијом (који ће бити означени заставом ако је асемблер превазиђен). Пример испод је за IBM/360 или Z/Architecture асембелере и заузима поље од 100 бајтова (на офсету 0) и који треба копирати из низа 'FROM' у низ 'TO' – оба имају дужине елемената од 256 бајта са 50 улаза

* иницијализовати све регистре да показују на низове (R14 је адреса за повраћај)
         LM    R15,R2,INIT                       load R15= '16', R0=number in array, R1--> 'FROM array', R2--> 'TO array'
LOOP     EQU   *
         SR    R15,R0                            узми 16 минус број у низу
         BNP   ALL                               ако је n > 16 треба урадити целу секвенцу, онда поновити
* (ако # уноса = 0, R15 ће и даље бити 16, па ће сви MVCови бити заобиђени)
* израчунај офсет (почни од MVC секвенце) за некондиционо гранање 
         MH    R15,=AL2(ILEN)                    помножи дужином (MVC..) инструкције (= 6 у овом примеру)
         B     ALL(R15)                          индексирана инструкција гранања(до MVC са испуштањем)
ALL      MVC   15*256(100,R2),15*256(R1)         * помери 100 бајта 16ог уноса од низа 1 до низа 2
ILEN     EQU   *-ALL                                         дужина (MVC...) инструкционе секвенце; у овом случају = 6
         MVC   14*256(100,R2),14*256(R1)         *
         MVC   13*256(100,R2),13*256(R1)         *
         MVC   12*256(100,R2),12*256(R1)         * свих 16 покретачких карактера инструкције користе base plus offset адресирање
         MVC   11*256(100,R2),11*256(R1)         * и сваки од-до офсета смањује за дужину једног елемента низа (256).
         MVC   10*256(100,R2),10*256(R1)         * овим се избегава да аритметика тражи да сваки елемет буде 
         MVC   09*256(100,R2),09*256(R1)         * дозвољени максимални офсет унутар инструкције X'FFF'. Инструкције
         MVC   08*256(100,R2),08*256(R1)         * су у реду смањујућег офсета, па је први елемент у скупу померен на крај
         MVC   07*256(100,R2),07*256(R1)         * 
         MVC   06*256(100,R2),06*256(R1)         *
         MVC   05*256(100,R2),05*256(R1)         *
         MVC   04*256(100,R2),04*256(R1)         *
         MVC   03*256(100,R2),03*256(R1)         *
         MVC   02*256(100,R2),02*256(R1)         *
         MVC   01*256(100,R2),01*256(R1)         помери 100 бајта другог уноса
         MVC   00*256(100,R2),00*256(R1)         помери 100 бајта првог уноса
*
         S     R0,MAXM1                          смањи Count = остали уноси за процесуирање
         BNPR  R14                               ... нема више, врати адресу на R14
         AH    R1,=AL2(16*256)                   повећај 'FROM' показивач регистра после првог скупа
         AH    R2,=AL2(16*256)                   повећај 'TO' показивач регистра после првог скупа
         L     R15,MAXM1                         поново увези (макс MVCа) у R15 (који је уништен пређашњим рачунањем)
         B     LOOP                              изврши петљу поново
*
* ----- Дефиниши статичке константе и промењиве (они могу да прођу као параметри) ---------------------------------  *
INIT     DS    0A                                4 адресе (показивача) за пре вађење са 'LM' инструкцијом
MAXM1    DC    A(16)                             максимум MVCа
N        DC    A(50)                             број стварних уноса у низ (промењива постављена другде)
         DC    A(FROM)                           адреса почетка првог низа ("pointer")
         DC    A(TO)                             адреса почетка другог низа ("pointer")
* -----Дефиниши статичке низове (они могу бити динамички стечени) --------------------------------------------------  *
FROM     DS    50CL256                          низ од макс 50 уноса од којих је сваки 256 бајта
TO       DS    50CL256                          низ од макс 50 уноса од којих је сваки 256 бајта

У овом примеру ће оптрилике 202 инструкције захтевати конвенционалну петљу (50 итерација) а горњи динамички код захтева само око 89 инструкција (или чување отприлике 56%). Ако се низ састојао од само 2 уноса, и даље би се извршавао у исто време као и оригинална неодмотана петља. Повећање величине кода од само 108 бајта чак иако су хиљаде уноса у низу. Сличне технике се могу користити и ако се користе више инструкција, све док се комбиноване дужине инструкција мењају према томе. На пример у истом промеру, ако се захтева да се очисти остатак сваког уноса низа на нулу одмах након што је поље од 100 бајта копирано, додатна инструкција за чишћење, 'XC xx*256+100(156,R1),xx*256+100(R2)', се може додати одмах након сваке MVC у секвенци (где 'xx' одговара вредности у MVC изнад њега).

Наравно, могуће је генерисати горњи код у једној линији користећи асемблерски макро исказ, специфирајући само 4 или 5 операнада, што чини оптимизацију спремном за неискусне програмере.

C пример[уреди]

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

#include<stdio.h>
 
#define TOGETHER (8)
 
int main(void)
{ 
 int i = 0; 
 int entries = 50;                                 /* укупан број за процесуирање     */
 int repeat;                                       /* број понављања.. */
 int left = 0;                                     /* подсетник (process later)   */ 
 repeat = (entries / TOGETHER);                    /* број понављања */
 left  =  (entries % TOGETHER);                    /* израчунај остатак         */
 
 /* одмотај петљу у осмице                                             */ 
 while( repeat-- > 0 ) 
  { 
    printf("process(%d)\n", i    );
    printf("process(%d)\n", i + 1); 
    printf("process(%d)\n", i + 2); 
    printf("process(%d)\n", i + 3); 
    printf("process(%d)\n", i + 4); 
    printf("process(%d)\n", i + 5); 
    printf("process(%d)\n", i + 6); 
    printf("process(%d)\n", i + 7);
 
    /* аптедјтуј индекс за количину процесуирану одједном  */ 
    i += TOGETHER; 
  }
 
switch (left) 
  {
     case 7 : printf("process(%d)\n", i + 6);      /* процесуирај и ослони се на пропуштање  */
     case 6 : printf("process(%d)\n", i + 5); 
     case 5 : printf("process(%d)\n", i + 4);  
     case 4 : printf("process(%d)\n", i + 3);  
     case 3 : printf("process(%d)\n", i + 2); 
     case 2 : printf("process(%d)\n", i + 1);      /* још два                                     */
     case 1 : printf("process(%d)\n", i    );      /* још један                      */ 
     case 0 :                               ;      /* није остао ниједан */
  } 
}

Даље читање[уреди]

  • Kennedy, Ken; Allen, Randy (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 978-1-55860-286-1. 

Спољашње везе[уреди]