Одмотавање петљеОдмотавање петље или одвијање петље је техника трансформације петље која покушава да оптимизује брзину извршења програма науштрб бинарне величине. Трансформације се може извршити ручно од програмера или преко оптимизирајућег комајлера. Циљ одмотавања петље је увећање брзине програма смањењем или елиминисањем инструкција које контролишу петљу, као што су аритметички показивач и "end of loop" тестови за сваку итерацију;[1] смањење грешака грањања; као и "скривене латенције, посебно, кашњење читања података из меморије".[2] Да би елиминисале ове трошкове, петље могу бити поново написане као поновљена секвенца сличних независних исказа.[3] ПредностиТрошкови у "тесним" петљама се често састоје из инструкција за инкрементирање показивача или индекса до следећег елемента у низу (аритметички показивач), као и "end of loop" тестова. Ако је оптимизирајући компајлер или асеблер у могућности да израчуна офсете за сваку индивидуално референцирану промењиву из низа, оне се могу уградити у инструкције машинског кода директно, па не захтевају додатне аритметичке операције током извршења (ово није случај у примеру доле).
Оптимизирајући компајлери ће понекад извршити одмотавање аутоматски или по захтеву. Мане
Ручно – мануелно одмотавање петљеРучно (или статичко) одмотавање укључује програмера који алализира петљу и интерпретира итерације у секвенције инструкција које ће смањити трошкове петље. Ово је супротно динамичком одмотавању које одрађује компајлер. Једноставни ручни пример у CСледи процедура у програму која брише 100 ствари из скупа. Ово се нормално ради преко for – петље која позива функцију delete(item_number). Ако је ово део програма који треба оптимизирати, и трошкови петље захтевају озбиљне ресурсе у поређењу са оним у delete(x) петљи, одмотавање га може убрзати.
Као резултат ове модификације, новом програму треба само 20 итерација уместо 100. После, само 20% скокова и кондиционалног гранања морају се обавити, и репрезентују, преко много итерација, потенцијално значајно увећање у администрацији трошкова петље. Да би направили оптималне бенефиције, ниједна промењива се не сме спецификовати у одмотаном коду који захтева аритметику показивача. Ово обично захтева "base plus offset" адресирање уместо индексираног референцирања. Са друге стране, ово одмотавање шири изворни код са 3 на 7 линија које морају да се направе, провере и дебагују, и компајлер можда мора да алоцира више регистра за чување промењивих у проширеној итерацији петље. Додатно, промењиве контроле петље и број операција у структури одмотаное петље морају се одабрати пажљиво тако да резултат буде исти као и оригинални код. На пример, импликације ће бити велике ако укупан број итерација није дељив са 5. Ручне поправке постају компликованије ако су промењиви тест услови. Рана комплексностУ простом случају, контрола петље је административни трошак који уређује продуктивне исказе. Сама петља не доприноси жељеним резултатима, што олакшава програмеру да не мора да рециплира код стотине пута што се могло урадити помоћу генерација репликација или текст едитора. Слично, if искази и други искази контроле тока се могу заменити кодном репликацијом. Програми лако прате комбинације, али програмерима је ово понављање досадно и праве грешке. Имајмо у виду:
Али наравно, извршени код не мора да буде буђење процедуре, и следећи пример укључује индексну промењиву у рачунању:
што, ако се компајлира, може направити много кода (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 петље – сличан следећем:
Одмотавање је брже јер ENDWHILE (који ће се компајлирати у jump на почетку петље) ће бити извршено 66% мање. Још боље, сређени псеудокод, који се може извршити аутоматски некоим опримизујучим компајлерима, елиминишући безусловне скокове потпуно. Динамичко одмотавањеПошто су бенефити одмотавања петље често зависни од величине низа који се можда и не зна до почетка извршења, JIT компајлери (на пример) могу да одреде да ли да пробуде стандардну секвенцу петље или да уместо тога генеришу релативно кратку секвенцу индивнидуалних инструкција за сваки елемент. Ова флексибилност је једна од предности JIT техника у контрасту са статичким или ручним оптимизацијама. У овој ситуацији, често су мале вредности 'n' где су добици корисни, резултујући у веома малом или никаквном повећању програма. Програмери асемблерског језика (укључујући писце оптимизујућих компајлера) су у бенефицији и од технике динамичког одмотавања петље, користећи метод сличан коришћеном у ефикасним таблама гранања. Овде је предност највећа где је максимум офсета који се може специфирати машинском инструкцијом (који ће бити означени заставом ако је асемблер превазиђен). Пример испод је за IBM/360 или Z/Architecture асембелере и заузима поље од 100 бајтова (на офсету 0) и који треба копирати из низа 'FROM' у низ 'TO' – оба имају дужине елемената од 256 бајта са 50 улаза
У овом примеру ће оптрилике 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 : ; /* није остао ниједан */
}
}
Референце
Литаратура
Спољашње везе
|
Portal di Ensiklopedia Dunia
