Преименовање регистара

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

Дефиниција проблема

У регистарској машини, програми су састављени од инструкција које оперишу над вредностима. Инструкције морају да именују вредности како би их разликовали једне од других. Типична инструкција би могла да гласи: сабери X и Y и смести резултат у Z. У овој интрукцији X, Y и Z су имена складишних локација.

Како би систем енкодирања инструкција постајао компактан, многи процесорски скупови инструкција имају мали скуп специјалних локација које се могу директно именовати. На пример, скуп инструкција x86 архитектуре има 8 целобројних регистара, x86-64 има 16, многи RISC процесори имају 32 и IA-64 има 128. У малим процесорима, имена ових локација одговарају елементима регистарског фајла.

Различите инструкције могу захтевати различито време извршавања (тј. CISC архитектура). На пример, процесор може бити у стању да изврши стотине инструкција док је у току један унос из главне меморије. Краће инструкције, које се извршавају док је унос учитан, ће се прве извршити, тако да се инструкције извршавају ванредно. Ванредно извршавање се користи у већини новијих процесора високих перформански како би се добило на брзини,

Посматрајмо овај део кода који се ванредно извршава на процесору:

1. `R1 = M[1024]`
2. `R1 = R1 + 2`
3. `M[1032] = R1`
4. `R1 = M[2048]`
5. `R1 = R1 + 4`
6. `M[2056] = R1`

Инструкције 4, 5 и 6 су зависне од инструкција 1, 2 и 3, али процесор не може да заврши 4. све док се 3. не изврши, зато што би 3. онда дала погрешан резултат.

Можемо избацити ово ограничење тако што би изменили имена неких регистара

1. `R1 = M[1024]`	4. `R2 = M[2048]`
2. `R1 = R1 + 2`	5. `R2 = R2 + 4`
3. `M[1032] = R1`	6. `M[2056] = R2`

Сада инструкције 4, 5 и 6 могу да буду извршене паралелно са инструкцијама 1, 2 и 3, тако да се програм брже извршава.

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

Конфликти података

Када више од једне инструкције референцира неку локацију за операнд, било при учитавању, било при испису, извршавање те инструкције може довести до три типа конфликта:

"Читај после писања" (RAW): Читање из регистра или меморијске локације мора да врати вредност која је тамо уписана приликом последњег уписа у програмском редоследу. Ово се назива "суштинска зависност" или "завиност тока" и захтева да се интрукције изврше у програмском редоследу.
"Пиши после писања" (WAW): Узастопни упис у одређени регистар или меморијску локацију морају резултовати тиме да та локација садржи садржај другог уписа. Ово може да се реши поништавањем првог уписа ако је потребно. WAW зависноти су још познате и као "зависности излазних података".
"Пиши после читања" (WAR): Читање из регистра или меморијске локације мора да вради последњу вредност уписану у ту локацију, а не ону уписану након читања. Ово је врста лажне зависности која може да се реши преименовањем. WAR зависности су још познате и као "анти-зависности".

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

Све што је учитано и исписано може бити преименовано. Док се највише дискутују регистри опште намене, флегови и статусни регистри или чак индивидуални статусни битови се такође често преименују.

Меморијске локација се могу такође преименовати иако се то не ради често. Transmeta Cruso процесоров бафер за складиштење представља форму преименовања меморије.

Ако се програми уздршавају од непосредног поновног коришћења регистара, преименовање регистара неће бити потребно. Неки скупови инструкција, као код IA-64, спецификују веома велике бројеве регистара специјално из овог разлога. Међутим, постоје ограничења овом приступу:

Компајлеру је веома тешко да избегне поновно коришћење регистара без великог повећања кода. На пример, у петљама, су узастопне итерације могу да користе различите регистре, што захтева прављење копија кода у процесу који се назива "одвијање петље".
Велики број регистара захтева пуно битова да би одредио те регистре, што чини код већим.
Доста скупова инструкција одређују мањи број регистара и раније и касније се ти бројеви не могу променити.

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

Архитектонски регистри или физички регистри

Програмски језици машина спецификују писања и читања на ограничен скуп регистара који одређује скуп инструкција (енгл instruction set architecture, ISA). На пример, Alpha ISA одређује 32 целобројних регистара, сваки широк по 64 бита и одређује 32 регистра са покретним зарезом, сваки по 64 бита широк. Ово су архитектонски регистри. Програми писани за процесоре који користе Alpha скуп инструкција могу одредити операције читања и писања тих 64 регистара. Ако програмер заустави програм дебаговањем, могу се посматрати садржај ових регистара да би се одредило напредовање машине.

Један одређени процесор који имплементира овај ISA, Alpha 21264, има 80 целобројних и 72 са покретним зарезом физичких регистара. На Alpha 21264 чипу постоји 80 физички одвојених локација на којима се може складиштити резултат целобројних операција и 72 локације које могу садржати резултате операција са покретним зарезом. У ствари, постоји и више локација од тога, али се те локације не повезују са регистрима са операцијама за преименовање.

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

У свим шемама за преименовање, машине конвертују архитектонске регистре (са кијима се ради у стриму инструкција) у ознаке. Архитектонски регистри могу бити одређени са 3 до 5 битова, док су ознаке обично дужине 6 до 8 битова. Фајл који се преименује мора имати порт за читање за сваки улазни података за сваку инструкцију која се преименује у сваком циклусу. Мора имати и порт за писање за сваки излазни податак сваке инструкције која се преименује у сваком циклусу. Зато што величина регистарског фајла обично расте као квадрат броја портова, фајл преименовања је обично физички велик и захтева значајну количину енергије.

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

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

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

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

Архитектонски регистарски фајл или регистарски фајл пензионисања (енгл. Retirement Register File, RRF): Посвећено регистарско стање машине. Логички регистарски број индексира RAM. Типично уписан када се резултати пензионишу из бафера за промену редоследа.
Будући фајл: Најспекулативније стање машине. Логички број регистара индексира RAM.
Активан регистарски фајл: термин за "будући фајл" Intel P6 група.; Бафер историје: Углавном се користи у комбинацији са будућим фајлом. Садржи старе вредности регистара преко којих је писано. Ако је произвођач и даље у лету, овај бафер може индексирати RAM. Пошто лоша предикција гранања мора да користи резултате из овог бафера, или се они копирају, или се тражење будућег фајла забрањује и бафер је CAM индексиран од странје броја регистара.
Бафер за промену редоследа (енгл. Reorder Buffer, ROB): структура која је секвенцијално индексирана на бази "по операцији" за инструкције у лету. Разликује се од бафера историје зато што овај бафер обично долази после будућег фајла (ако овај постоји) и пр еархитектонског регистарског фајла.

Бафер за промену редоследа долази у верзијама без података и са подацима.

У Виламетовом (Willamette) ROB-у, улазни подаци указују на регистре у физичком регистарском фајлу (енгл physical register file, PRF) и такође садрже други механизам за резервисано чување. Ово је такође био први ванредни дизајн који је урадио Енди Глу (Andy Glew) у Илиноису са HaRRM-ом.

Улазни подаци код P6-овог ROB-а садрже податке. Нема одвојеног PRF-а. Вредности података из ROB-а се копирају из ROB-а у RRF при пензионисању.

Један мали детаљ: ако постоји привремена локалност на ROB улазима (тј., ако се инструкције које су близу једна другој у фон Нојмановој секвенци инструкција испишу заједно на време, могуће је извести операцију писања комбиновањем ROB улаза и тако имати мање портова него што има одвојени ROB/PRF). Не зна се да ли ово прави неку разлику пошто би PRF требало да буде пун.

ROB-ови обично немају асоцијативну логику а и ни један од Енди Глуових ROB-ова немају CAM-ове. Кит Дифендорф (Keith Diefendorff) је инсистирао да ROB-ови имају комплексни асоцијативну логику већ годинама. Први ROB предлози су можда имали CAM-ове.

Детаљи: регистарски фајлови који су идексирани по ознакама

Ово је начин преименовања који се користе у MIPS-у R10000, Alpha 21264 и у FP секцији AMD Athlon-а.

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

Инструкције се онда смештају у разне редове извршавања.

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

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

Позване инструкције прочитане од стране физичког регистра индексираног ознаком се онда извршавају.

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

Пензионисање ставља претходну ознаку за написани архитектонски регистар у празан ред тако да се може поново искористити за новодекодовану инструкцију.

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

Детаљи: резервационе станице

Ово је начин који се користи у целобројној секцији AMD-ових K7 и K8 дизајна.

У фази ремапирања, сваки референцирани архитектонски регистар за читање се закључава у оба архитектонски индексирана фајла (будућу фајл и фајл преименовања). Читање будућег фајла даје вредност тог регистра, ако још увек не постоји истакнута инструкција на коју треба да се пише (тј. ако још увек није спремна). Када се интрукција смести у ред извршавања, вредности прочитане из будућег фајла се пишу у одговарајуће улазе у резервационим станицама. Регистар бележи нову, неспремну ознаку за инструкцију која ће се писати у фајл преименовања. Број ознаке се обично серијски алоцира у инструкцијском редоследу. Није потребан free tag FIFO,

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

Позване инструкције читају своје аргументе из резервационих станица, заобилазе just-broadcast операнде и онда се извршавају. Као што је поменуто раније, регистарски фајлови резервационих станица су обично мали са можда 8 улаза.

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

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

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

Поређење шема

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

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

Станице резервације такође имају мање кашњење од инструкција које се користе за ивршавање, зато што је сваки локални регистарски фајл мањи од великог централног фајла шеме са означеним индексирањем. Генерација са овим индексирањем и обрада изузетака су такође једноставини у шеми резервације станица.

Физички регистарски фајлови (које користе резервационе станице) обично уклањају улазе који се не користе, са редом извршавања коме служе, што чини ове регистрарске фајлове укупно већима и такође троше више енергије и више су компликованији од једноставних регистарских фајлова које користе резервационе станице у шеми са означеним индексирањем. Што је још горе, сваки улаз у свакој станици може бити исписан сваким резултатом магистрале, тако да машина са резервационим станицама са, нпр. 8 улаза (за редове извршавања) по функционалној јединици ће имати 9 пута више заобилазака мреже као и машина са означеним индексирањем са истим карактеристикама. Као резултат тога имамо много већу потрошњу енергије и области него код дизајна са означеним индексирањем.

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

Историја

IBM System/360 Model 91 је била машина која је требало да подржи ванредно извршавање инструкција. Користила је Томасулио алгоритам који користи преименовање регистара.

POWER1 је први микропроцесор који је користио преименовање регистара и ванредно извршавање (1990).

Оригинални дизајн R10000 машине није имао ни проблем рушења нити кодирање приоритета променљивих, а патио је од проблема изгладњивања. Као резултат тога, најстарија инструкцција у реду понекад ни би била извршена док се обе инструкције декодирања не стану потпуно збох недостатка преименованих регистара и док се свака друга инструкција не покрене. Касније ревизије дизајна, почевши од R12000 су користиле делимично кодирање приоритета променљивих да би избегле овај проблем.

Раније машине са ванредним извршавањем нису раздвајале функције за преименовање и ROB/PRF функције за складиштење. Због тога, неке од најранијих, као што је Sohi RUU или Metaflow DCAF, су комбиновале заказивање, преименовање и складиштење све у једној истој структури.

Већина модерних машина врше преименовање тако што RAM индексира табелу мапа са логичким регистарским бројевима. P6 је ово радио - његови будући фајлови су ово радили и сви подаци за складиштење су били у истој структури.

Међутим, раније машине су користиле CAM (енгл. content-addressable memory, тип хардвера који је омогућавао функционалност неког асоцијативног низа у преименивачу). CAM је користио HPSM RAT (Register Alias Table) на логичком броју регистара у комбинацији са различитим верзијама регистара.

У већини случајева, прича микроархитектуре ванредног извршавања је била како да се ови CAM-ови прогресивно елеминишу. Мали CAM-ови су корисни. Велики су непрактични.

P6 микроархитектура је била прва Intel-ова микроархитектура која је имплементирала и ванредно извршавање и преименовање регистара. Користила се у Pentium Pro, Pentium II, Pentium III, Pentium M, Core, и Core 2 процесорима.^[1]^[2]

Референце

^ „Cyrix 6x86 Processor”. Архивирано из оригинала 02. 05. 2016. г. Приступљено 15. 01. 2017.
^ „NexGen Nx686”. , „PC Mag Dec 6, 1994”.

Литература

Smith, J. E.; Pleszkun, A. 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 Trans. Comput. 37 (5): 562—573. doi:10.1109/12.4607.
Smith, J. E.; Pleszkun, A. R. (1998). „Implementation of precise interrupts in pipelined processors”. 25 years of the international symposia on Computer architecture (selected papers) - ISCA '98. стр. 291—299. ISBN 1581130589. doi:10.1145/285930.285988.

[1] „Cyrix 6x86 Processor”. Архивирано из оригинала 02. 05. 2016. г. Приступљено 15. 01. 2017.

[2] „NexGen Nx686”. , „PC Mag Dec 6, 1994”.

[1]

[2]