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

Ослушкујући (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

Dragon

Firefly