Мултипроцесорски системи/Ослушкујући протоколи

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

Дијаграми

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

Елементи дијаграма јесу:

• Кружићи: представљају стања у којима се један податак у кешу може наћи. Унутар кружића налази се ознака стања.
• Пуне стрелице: представљају прелазе између стања као резултат акција тог процесора чији је кеш.
• Испрекидане стрелице: предствљају прелазе између стања као резултат акција на магистрали које контролер кеш меморије ослушкује. Обојене су црвеном бојом како би било јасније да су ове акције другачије од оних извршених од стране процесора.
• Ознаке изнад стрелица: описују узроке и последице преласка из једног у друго стање.
  • Могући формати ових ознака су:
    • Узрок/Последица
    • Узрок/Последица(Услов)
    • Узрок/Последица1; Последица2
    • Узрок/Последица1; Последица2(Услов).
  • Узроци могу бити:
    • PrRd: наш процесор је затражио читање датог податка.
    • PrWr: наш процесор је затражио упис у дати податак.
    • BusRd: контролер кеш меморије је приметио да неки други процесор на магистрали покушава да прочита дати податак.
    • BusWr: контролер кеш меморије је приметио да неки други процесор на магистрали покушава да упише у дати податак.
    • BusRdX: контролер кеш меморије је приметио да неки други процесор на магистрали покушава да прочита дати податак са намером да после тога пише у њега. Овај узрок се користи уместо BusWr у свим протоколима осим WTI.
    • BusUpgr: контролер кеш меморије је приметио да неки други процесор на магистрали инвалидира дати податак.
    • Replace: податак је замењен у кеш меморији неким другим податком.
    • PrRdMiss: десио се промашај при читању датог податка од стране процесора (податак није био у кешу претходно). Овај узрок је присутан само на дијаграмима ажурирајућих протокола, јер они немају специјално стање којим представљају да податак није у кешу.
    • PrWrMiss: десио се промашај при писању у дати податак од стране процесора (податак није био у кешу претходно). Овај узрок је присутан само на дијаграмима ажурирајућих протокола, јер они немају специјално стање којим представљају да податак није у кешу.
    • BusUpd: контролер кеш меморије је приметио да неки други процесор на магистрали покушава да свим осталим контролерима каже да ажурирају тај податак код себе. Овај узрок је присутан само на дијаграмима ажурирајућих протокола.
  • Последице могу бити:
    • --: без последице
    • BusRd: изазвано је читање податка из меморије
    • BusWr: изазван је упис податка у меморију
    • BusRdX: изазвано је читање податка из меморије са намером за упис
    • Flush: изазван је упис сачуваног податка у меморију, јер податак у меморији до тог тренутка није био ажуран
    • Transfer: изазван је пренос податка из кеш меморије на магистралу како би неки други контролер кеш меморије могао да га прочита (користи се када је тренутна кеш меморија једини ажуран извор податка)
    • BusUpgr: изазвано је поништење свих копија датог податка у осталим кеш меморијама
    • Update: изазвано је ажурирање датог податка у тренутној кеш меморији на основу податка са магистрале послатог од неког другог кеш контролера
    • BusUpd: изазвано је ажурирање датог података у свим осталим кеш контролерима на магистрали
  • Уколико Услов није испуњен, тај прелаз се не дешава. У свим дијаграмима испод услови ће бити S (shared бит је постављен на магистрали од барем једног контролера кеш меморије) или ¬S (shared бит није постављен на магистрали).

WTI

WTI протокол је најједноставнији протокол за кеш кохеренцију, јер има само два стања:

• V (valid): податак у кеш меморији је важећи
• I (invalid): податак у кеш меморији није важећи (или није у кеш меморији уопште)

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

Упис податка одмах издаје команду за упис у меморију (write-through техника) и свој податак у кеш меморији ажурира само уколико је валидан (write-no-allocate техника). Када остали кеш контролери примете упис податка, пребацују податак у невалидно стање. У овом протоколу, када контролери примете читање податка на магистрали они га једноставно игноришу.

Write-allocate

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

MSI

Највећи недостатак WTI протокола је што сваки упис иде директно у меморију (write-through). Зато су наредни протоколи направљени са одложеним уписом (write-back) у виду, тако да кеш контролери уписују податак у меморију само када је то заиста неопходно. Овом приликом уводе се два нова концепта:

• Власништво: контролер има валидну вредност податка и задужен је за њен упис у меморију уколико се дешава замена податка из кеша и прослеђивање податка осталим контролерима кеша уколико га захтевају BusRd или BusRdX операцијом
• Ексклузивност: контролер је једини који у целом систему држи тај податак у кешу, па зато може да обавља одређене операције над њим без изласка на магистралу

Први write-back протокол који се обрађује је MSI, са следећим стањима:

• M (modified): контролер има валидан податак и власништво и екслузивност над њим
• S (shared): контролер има валидан податак али ни власништво ни екслузивност над њим
• I (invalid): исто као у WTI

Када се покуша читање податка који није у кешу, иде се у shared стање (иако податак не мора нужно бити дељен, што је решено каснијим протоколима). Други контролери на магистрали могу детектовати ово читање, и уколико је неки од њих у modified стању, он ради упис свог податка у меморију (flush) а затим прелази у shared стање (више нема ни власништво, јер је податак већ уписао, а ни екслузивност, јер постоји други кеш контролер са тим податком код себе). Читање податка који јесте у кешу не резултује никаквим изласком на магистралу или променом стања.

Када се покуша упис у податак, без обзира на претходно стање, прелази се у modified стање. Процесор који уписује излази на магистралу само уколико није у modified стању (јер у том случају има власништво над податком). Овом приликом сви остали кеш контролери детектују упис и прелазе у невалидно стање, а уколико је неки од њих имао власништво над податком пре преласка ради flush податка у меморију.

MESI

Као што је раније поменуто, један проблем са MSI протоколом је што се након читања податка иде у shared стање без обзира да ли остали кеш контролери имају или немају тај податак код себе. Овај проблем решен са два механизма:

• На магистралу додат је S (shared) бит, тако да кеш контролери могу да пусте логичку јединицу на њега уколико поседују податак који се чита или уписује. На овај начин други контролери могу да примете да ли имају ексклузивност над податком.
• У протокол додато је E (exclusive) стање, које значи да контролер има екслузивност али не и власништво над податком. Разлика овог стања од M стања је, дакле, у томе да ли је податак измењен (прљав, dirty) или није.

Тиме смо дошли до MESI протокола. Приликом читања податка који није у кешу у том протоколу се иде у стање S уколико је S бит постављен на магистрали, или стање E уколико није. Контролери такође морају да детектују читање од стране других контролера док су у стању E, како би прешли у стање S (али, за разлику од стања M, без уписа тог податка назад у меморију).

Приликом уписа податка, једина разлика од MSI протокола се тиче E стања. Уколико процесор у E стању уписује податак, потребно је једино да пређе у M стање јер сада има и власништво над тим податком (односно упрљао је тај податак).

Још једна нова ствар коју уводи MESI протокол је кеш-кеш трансфер података. Уколико контролер види да други контролер захтева податак који има у свом кешу, може да иницира трансфер свог податка другом контролеру, чиме убрзава читање. Један од проблема који се овде може приметити јесте што на прелазима из S стања са BusRd или BusRdX као узроком, контролери ће морати да раде арбитрацију како би одредили који од њих ће да ради трансфер. Тако долазимо до...

MESIF

Неки кеш контролери имају додатно стање F (forward) које одређује да су они контролер који треба да прослеђује податак уколико има више контролера са истим податком. У овом стању је последњи контролер којем је вршен трансфер тог податка. На пример:

• Контролер А захтева податак, ниједан од кеш контролера га нема па га он зато добија из меморије и улази у стање E
• Контролер Б захтева податак, контролер А има тај податак, па контролер А улази у S стање док контролер Б улази у F стање.
• Контролер В захтева податак, контролери А и Б имају тај податак, контролер Б врши трансфер податка контролеру В па контролер Б улази у S стање а контролер В у F стање.
• и тако даље...

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

MOESI

Логичан след протокола који уводи стање које подразумева само екслузивност јесте протокол који додаје стање који подразумева само власништво. Тако настаје MOESI протокол, са додатним O стањем. Ово је уједно и најкомпликованији ослушкујући протокол.

Читање се у овом протоколу генерално није мењало. Читање из O стања, интуитивно, не излази на магистралу. Детекција читања док је податак у O стању иницира трансфер између кешева. Оно што се јесте променило јесте што се у S стању више не врши трансфер при детекцији читања, само у M, O и E стањима. Разлог за ово је вероватно што новоуведено стање врши сличне дужности као F стање у MESIF протоколу, па нема потребе за трансфером из S стања, које је и претходно било недефинисано.

Циљ MOESI протокола је да додатно смањи број излазака на магистралу (и време проведено на магистрали) због уписа. Из овог разлога, ново стање O нам служи како бисмо у њега могли да пређемо из M стања када детектујемо да још неко на магистрали користи наш податак. Тиме губимо екслузивност, али не и власништво, па тиме може да постоји више контролера у S стању у исто време као један у O стању.

Додатна функционалност уведена овим протоколом јесте BusUpgr узрок и последица на дијаграмима. Наиме, уколико се у неком дељеном (не-екслузивном, односно S или O) стању врши упис, уместо уписа у меморију коришћењем BusRdX, сада се шаље сигнал на магистралу како би остали контролери у својим кешевима поништили дати податак. Остали контролери реагују на ово тако што из својих дељених стања прелазе у I. Овиме тренутни контролер постаје власник податка, а не мора да чека на меморију за упис тог податка.

Dragon

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

Стања су другачије названа:

• E и M стања одговарају истоименим из MOESI протокола
• Sm стање одговара O стању из MOESI
• Sc стање одговара S стању из MOESI

Поред читања, S бит се у овом протоколу користи и приликом писања. Уколико се податак који није у кешу уписује (write miss), проверава се S бит и одлази у Sm уколико је податак дељен, односно M уколико није. Такође, уколико се у Sm стању приликом уписа детектује да је тај контролер једини који користи тај податак на магистрали, прелази се у M стање.

Уместо BusUpgr сада се користи BusUpd које каже свим контролерима на магистрали да ажурирају дати податак, на шта они реагују са Update. Упис податка сада што више избегава меморију, тако да је коришћење BusRdX замењено са BusUpd. Уколико податак при упису није раније био у кешу, а остали контролери поседују тај податак, прво мора бити послата BusRd команда како би контролер који је раније држао ексклузивност и власништво над тим податком из свог M стања прешао у Sm, а тек затим урађен BusUpd. Упис у меморију се врши тек уколико контролер са власништвом над податком мора да изврши замену тог податка из свог кеша, приликом чега врши flush операцију.

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

Firefly

Неко се некада запитао да ли је стање Sm у Dragon протоколу заиста неопходно, и дошао је до закључка да није уколико би BusUpd ажурирало и меморију. Тако је настао Firefly протокол. Поред ове измене у BusUpd, Flush акција функционише као Transfer са уписом у меморију.

Стања су названа по томе да ли су дељена (shared, односно да ли не подразумевају екслузивност) и да ли подразумевају власништво (односно да ли је податак у њима прљав, dirty). Стога су креативна имена за ова стања sd (није дељено, није прљаво, еквивалент E), sD (није дељено, јесте прљаво, еквивалент M) и Sd (јесте дељено, није прљаво, еквивалент S и Sc).