Одмотавање петље
Одмотавање петље или одвијање петље је техника трансформације петље која покушава да оптимизује брзину извршења програма науштрб бинарне величине. Трансформације се може извршити ручно од програмера или преко оптимизирајућег комајлера.
Циљ одмотавања петље је увећање брзине програма смањењем или елиминисањем инструкција које контролишу петљу, као што су аритметички показивач и "end of loop" тестови за сваку итерацију;[1] смањење грешака грањања; као и "скривене латенције, посебно, кашњење читања података из меморије".[2] Да би елиминисале ове трошкове, петље могу бити поново написане као поновљена секвенца сличних независних исказа.[3]
Предности
уредиТрошкови у "тесним" петљама се често састоје из инструкција за инкрементирање показивача или индекса до следећег елемента у низу (аритметички показивач), као и "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 : ; /* није остао ниједан */
}
}
Референце
уреди- ^ Ullman, Jeffrey D.; Aho, Alfred V. (1977). Principles of compiler design. Reading, Mass: Addison-Wesley Pub. Co. стр. 471–2. ISBN 0-201-10073-8.
- ^ Petersen, W.P.; Arbenz, P. (2004). Introduction to Parallel Computing. Oxford University Press. стр. 10.
- ^ Nicolau, Alexandru (1985). „Loop Quantization: Unwinding for Fine-Grain Parallelism Exploitation”. Dept. of Computer Science Technical Report. Ithaca, NY: Cornell University. OCLC 14638257.
Литаратура
уреди- Kennedy, Ken; Allen, Randy (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 978-1-55860-286-1.
Спољашње везе
уреди- Chapter 7, pages 8 to 10, of Michael Abrash's Graphics Programming Black Book is about loop unrolling, with an example in x86 assembly.
- Generalized Loop Unrolling Архивирано на сајту Wayback Machine (25. новембар 2020), gives a concise introduction.
- Optimizing subroutines in assembly language Agner Fog's optimizations handbook with the loop unrolling technique (2012)