Ванредно извршавање

У рачунарству, ванредно извршавање (енгл. out-of-order execution, OoOE или OOE) је парадигма која се користи код процесора високих перформанси да би искористили инструкцијске циклусе који би, у супротном, били неискоришћени због неког одређеног типа кашњења. У овој парадигми процесор извршава инструкције у редоследу који одређује доступност улазних података, за разлику од њиховог оригиналног редоследа у програму. Радећи тако, процесор може да избегне да буде незапослен док се подаци враћају за следећу инструкцију у програму, уместо обрађивањем следећих инструкција које су у стању да се изврше одмах.

Историја

Ванредно озвршавање је ограничена форма рачунања тока података, који је био велика област истраживања у рачунарској архитектури 70-их година и раних 80-их. Битна академска истраживања у овој тему је водио Јејл Пет (Yale Patt) и његов HPSm симулатор.^[1] Лист који су Џејмс Е. Смит и А. Р. Плезкун објавили 1985. допуњава шему описујући како одређена понашања изузетака могу бити одржавана у машинама са ванредним извршавањем.

Убедљиво прва машина која користи ванредно извршавање је била CDC 6600 (1964), која је користила scoreboarding да би решила конфликте. Данас се у употреби, такав scoreboarding се сматра "редним" извршавањем а не ванредним, пошто такве машине одуговлаче на првом RAW конфликту ("читај после писања", енгл. Read After Write). Стриктно говорећи, такве машине покрећу редно извршавање, иако могу да употпуне ванредно извршавање.

Око три године касније, IBM 360/91 (1966) је увео Томасуло алгоритам, који подржава потпуно ванредно извршавање.

IBM је, 1990., увео први ванредни микропроцесор, POWER1, иако је ванредно извршавање било ограничено само на инструкције са покретним зарезом.

Кроз 90-е године, ванредно извршавање је постало учесталије и било је истакнуто у следећим машинама: IBM/Motorola PowerPC 601 (1993), Fujitsu/HAL SPARC64 (1995), Intel Pentium Pro (1995), MIPS R10000 (1996), HP PA-8000 (1996), AMD K5 (1996) и DEC Alpha 21264 (1998). Значајни изизеци у овом тренду су биле машине: Sun UltraSPARC, HP/Intel Itanium, Transmeta Crusoe, Intel Atom, и IBM POWER6.

Логичка комплексност шема ванредног извршавања је била разлог због кога ова техника није достигла мејнстрим машине до средине 90-их година. Много "low-end" процесора намењених тржиштима са осетљивим ценама и данас не користе ову парадигму због велике силиконске области која је потребна да се направи ова класа машина. Мала потрошња је још један циљ дизајна који је теже постићи са OoOE дизајном.

Основни концепт

Редни процесори

У ранијим процесорима, обрада инструкицја се обично извршавала следећим корацима:

Инструкцијско хватање.
Ако су улазни операнди доступни (на пример у регистрима), инструкција се шаље прикладној функционалној јединици Ако један или више операнада нису доступни за време тренутног циклуса клока (обично зато што их хвата меморија у том тренутку), процесор одуговлачи док не постану доступни.
Интрукцију извршава прикладна функционална јединица.
Функционална јединица пише резултат назад у регистарски фајл.

Ванредни процесори

Ова нова парадигма се дели на обрађивање инструкција следећим корацима:

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

Кључ за концепт OoO обраде је да се дозволи процесору да може да избегне класу одуговлачења до којих долази када је потребан податак недоступан. У шеми горе, OoO процесор избегава одуговлачења која де дешавају у кораку (2) редног процесора када инструкција није потпуно спремна да се обради због недостатака података.

OoO процесори попуњавају ове прорезе у времену са другим инструкцијама које јесу спремне, и онда реорганизују резултат на крају тако да би изгледало као да су се инструкције обрадиле најобичније. Начин на који се инструкције распоређују у оригиналном коду је познат под термином редослед програма. У процесору са њима се барата у редоследу података, у редоследу у коме подаци тј. операнди, постају доступни у просеровоим регистрима. Доста комплексна кола су потребна да се конвертује из једног редоследа у други и да се одржи логички редослед излазних подака. Чини се као да сам процесор покреће инструкције у насумичном редоследу.

Бенефиција OoO обарде расте како се проточне обрада продубљује и како се брзина разликује између главне меморије (или кеш меморије) и како се процесор шири. На модерним машинама, процесор ради доста брже него меморија, тако да, за време које редни процесор проведе чекајући на податке, он може да обради велики број инструкција.

Отпремање и питање изолације омогућавају OoO исход

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

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

Извршавање и писање изолације омогућава програмско поновно покретање

Ред за резултате је неопходан да би се решила питања као што су лоша предвиђања грана и изузеци односно замке. Резлутовани ред омогућава програму да се поново покрене после изузетка, што захтева да се инструкција заврши у програмском редоследу. Ред омогућава резулатима да се одбаце због лошег предвиђања на основу старији грана инструкција и изузетака који су узети из старијих инструкција.

Способност да се изда инструкција протеклих грана, која се још није разрешила, се назива спекулативно извршавање.

Микроархитектонски избори

Да ли су инструкције одбачене на централизован ред или на више дистрибуираних редова?

IBM PowerPC процесори користе редове који се дистрибуирају на различите функционалне јединице док други ОоО процесори користе централизовани ред. IBM користи термин станице резервације за њихове дистрибуиране редове.

Да ли постоји стваран резултат редова или су се сви резултати пишу директно на регистарски фајл? За доцнији, функцијом за чекање у реду рукују регистарске мапе које држе информације преименовања регистара за сваку инструкцију у лету.

Рани Intel ОоО процесори користе резултујуће редове зване бафери за промену редоследа, док многи каснији ОоО процесори користе регистарске мапе.

Прецизније: Intel-ова P6 породица микропроцесора има и бафере за промену редоследа (енгл. re-order buffers, ROB) и табелу за преименовање регистара (енгл. register alias table, RAT). ROB је углавном мотивисан опоравком од лошег предвиђања грана.

Intel-ова P6 породица је међу најранијим ОоО процесорима, али је замењена NetBurst архитектуром. Годинама касније се доказала као ћорсокак због своје дугачке проточне обраде, која је подразумевала много више фреквенције рада. Материјали нису били у могућности да се поклопе са дизајнерским амбиционим метама клока због проблема са топлотом. Каснији дизајни, базирани на NetBurst-у, поготово Tejas и Jayhawk су били отказани. Intel се вратио P6 дизајну у облику основа Core-а, Core-а 2 и Nehalem микроархитекруре. Sandy Bridge, Ivy Bridge и Haswell микроархитектуре представљају полазак од техника промене редоследа које је користио P6 и запошљавају технике промене редоследа које су користили EV6 и P4 без дугачке проточне обраде.^[2]

Види још

Референце

^ W. Hwu; Y. N. Patt (1986). HPSm, a high performance restricted data flow architecture having minimal functionality. ISCA '86 Proceedings of the 13th annual international symposium on Computer architecture. ACM. стр. 297—306. ISBN 978-0-8186-0719-6. Приступљено 6. 12. 2013.
^ Kanter, David (25. 9. 2010). „Intel's Sandy Bridge Microarchitecture”.

Додатна литература

Smith, James E.; Pleszkun, Andrew R. (1985). „Implementation of precise interrupts in pipelined processors”. ACM Sigarch Computer Architecture News. 13 (3): 36—44. doi:10.1145/327070.327125.
Smith, J.E.; Pleszkun, A.R. (1988). „Implementing precise interrupts in pipelined processors”. IEEE Transactions on Computers. 37 (5): 562—573. doi:10.1109/12.4607.
Smith, James E.; Pleszkun, Andrew R. (1998). „Implementation of precise interrupts in pipelined processors”. 25 years of the international symposia on Computer architecture (Selected papers). стр. 291–299. ISBN 1581130589. S2CID 6616701. doi:10.1145/285930.285988.

[1] W. Hwu; Y. N. Patt (1986). HPSm, a high performance restricted data flow architecture having minimal functionality. ISCA '86 Proceedings of the 13th annual international symposium on Computer architecture. ACM. стр. 297—306. ISBN 978-0-8186-0719-6. Приступљено 6. 12. 2013.

[2] Kanter, David (25. 9. 2010). „Intel's Sandy Bridge Microarchitecture”.

[1]

[2]