Последната актуализация на този раздел е от 2021 година.

6.3.2.2 Кохерентност на кеш паметта. Протокол MESI

Благодарение на съвременната многопроцесорност (под най-различни форми) и благодарение на това, че тези “работяги”, с цел да си улеснят и ускорят работата, гребат информация с “пълни шепи” от едно и също място – оперативната памет, възниква нов и комплексен проблем. Проблемът се състои в това, че този общ начин за организация (вече добре изяснен в предидущите пунктове) не може да гарантира достоверността (актуалността) на данните, с които работят отделните процесори едновременно, във всички точки, където тя се намира. За да поясним проблема, и тук ще си послужим с метафоричен пример: двама, седят на една маса, четат вестници и в същото време се хранят от една и съща паница, в която почти не поглеждат, тъй като са заети с четивата си. Единият обаче в един момент решава, че яденето е безсолно и го посолява. Представете си изненадата на другия след поредното загребване! Той от своя страна решава да овкуси допълнително храната и я полива обилно с оцет. Ако така продължат е ясно, че храната ще стане негодна за ядене, а господата вероятно ще се разболеят. А това наистина е проблем. Нещо такова става в системите със собствено (локално) буфериране. Тъй като по време на работа, локалните информационни копия на информацията от оперативната памет се обновява (модифицира, преработва) (чете се, обработва се и пак се записва), а връщането на обновените копия обратно в основната памет и вземането на нови е напълно несинхронизирано, то проблемът с кохерентността (съответствието) на информацията по място и по време е изключително актуален.

Решаването на този проблем изисква всички участници в изчислителния процес, протичащ върху общи данни, да спазват общи правила на поведение.

Първото, което следва да се определи в това поведение, е уеднаквяване във всички елементи на системата на така наречената политика на запис, която беше определена и изяснена в пункт 6.3.2 – едновременен запис (write through) и обратен запис (write back). Ще припомним, че в първия случай всеки запис на обновени данни се извършва по цялата йерархия на запомнящата система (отгоре надолу). Така във всеки един момент системата е осигурена с актуални данни в общия ресурс – оперативната памет. Алтернативният вариант изисква допълнителни признаци на данните (признаци за модификация, обновяване). От своя страна потребителите на тези данни са принудени да изискват значението на този признак за да са сигурни в актуалността на данните, които следва да копират. Естествено тази организация е значително по-сложна, но затова пък минимизира обръщенията към бавния общ ресурс.

Известни са три подхода за постигане на цялостна кохерентност на информацията:

1. Непрекъснато наблюдение на системната шина за изпълнение на едновременен запис. Всеки кеш-контролер трябва да следи адресните и управляващите линии на системната шина, с цел да открие запис на данни от друг източник, различен от процесора, на чието подчинение е самия той. Ако записваният в момента в оперативната памет блок е бил вече копиран и в подчинената му кеш памет, т.е. негово копие се съдържа в управляваната от него локална кеш памет, този кеш-контролер незабавно следва да вземе за себе си ново (актуално) копие ;

2. Прозрачност на апаратните средства. С допълнителни апаратни средства се осигурява абсолютна взаимна видимост между локалните кеш памети. С други думи ако в предидущия вариант всички “погледи” бяха фокусирани върху една точка, то сега всички са си вдигнали “завесите” и се наблюдават един друг. Естествено ако някой кеш обнови съдържанието си, всички останали, които имат интерес (копия) от обновявания блок, виждайки това, правят същото, като го копират директно от него ;

3. Използване на некешируема памет. Системи, които иска да използват този подход, отделят в оперативната памет един сегмент (област) за общ достъп и ползване. Този сегмент се маркира (отбелязва) като некешируем и в него всички процесори в системата разполагат онези данни, които не се съдържат в локалните им кеш памети. Тук обаче следва предварително да е известно това качество на данните. Това качество на данните много прилича на съответното им в подпрограмната техника, където говорим за локални и общи параметри.

Осигуряването на на кохерентни данни в кеш паметите се постига както с апаратни, така и с програмни средства. В последния случай тази задача се възлага на компилатора и на операционната система. По време на компилация се извършва анализ на данните и се отделят онези, които не подлежат на кеширане. По време на изпълнение на програмата, операционната система заедно с апаратните средства следи за това, тези данни да не попадат в кеш паметта. В многопроцесорните системи, така се маркират общите съвместно използвани данни. Тук обаче има един нюанс, който се отнася до това, че съвместното използване може да се окаже последователно във времето. Така този подход може да доведе до твърде неефективно използване на кеш паметите и до висока интензивност на обръщенията към оперативната памет. Ето защо се разработени и изследвани различни методики на компилация, при които по време на компилация на програмите се изявяват “безопасните” участъци. Останалите се компилират като към тях се добавят специални машинни команди, предназначени за осигуряване на кохерентността на данните.

Апаратните методи реализират безопасното поведение под формата на протокол. Наименованието протокол може да се разбира като предписана норма на поведение, което не е далеч от понятието алгоритъм. Протоколите се реализират апаратно и се подчиняват на реалната динамика на данните, с което осигуряват по-ефективно използване на кеш паметите и по-високо бързодействие. Освен това той освобождава програмиста от грижите за тази задача. Протоколите се делят на два вида:

1. Централизирани протоколи. Характерното за тези протоколи е това, че информацията за състоянието на данните в отделните кеш памети се събира, съхранява и обработва в едно място, т.е. централизирано. Протоколът се реализира от специален контролер, който е част от структурата на контролера на главната памет, в която се поддържа специален за тази информация каталог. В този каталог се събират признаците на всички блокове, копирани във всеки отделен кеш. Когато локален кеш-контролер подаде заявка за трансфер, тя се обработва от контролера на протокола, който организира трансфера, като има задължението да актуализира данните (ако се налага) във всички точки, където има техни копия. Заедно с това този контролер има правата да обновява признаците за състоянието на блоковете в точките, където е извършил актуализация.

Когато един процесор поиска да записва (да обнови) данни в даден блок в своята локална памет (и в основната памет), той го прави само ако получи от контролерът на протокола право на изключителен достъп до заявения блок. Преди да издаде това разрешение контролерът на протокола изпраща до всички локални кеш контролери заповед, че те следва да установят признака на своето копие от същия блок, като недостоверно. Когато получи потвърждение за изпълнение на това действие от локалните кеш-контролери, тогава контролерът на протокола дава разрешение на процесора, подал заявката, да извърши запис на данните в заявения блок.

По-късно, ако някой процесор иска да прочете данни от блок, който е маркиран като недостоверен, той е длъжен най-напред да се обърне към контролера на протокола. Последният изпраща заповед към процесора, който е обновил дадения блок, да изпълни обратен запис на този блок в оперативната памет. След това така актуализираният блок може да бъде повторно изкопиран във всички точки, където е отбелязан като недостоверен. След това актуализиращо копиране за този блок се установява признак за достоверност ;

2. Разпределени отследяващи протоколи. Тези протоколи разпределят задачите за гарантиране на кохерентността между локалните кеш-контролери. Според тази уговорка, всеки отделен кеш-контролер трябва да следи за това, дали копираните от него блокове данни не се използват и в другите кеш памети. Ако се налага обновяване на данните в този блок, контролерът е длъжен да оповести за това всички останали, които съхраняват същото копие. За целта между кеш-контролерите се реализира специален диалогов механизъм, в основата на който стои общата магистрала на системата.

Разпределените протоколи се реализарат по два начина:

· Write-invalidate – запис с оповестяване за недостоверност ;

· Write-update – запис с обновяване.

В първия случай из между всички притежатели на даден блок, в отделен момент от времето само един от тях може да има право на запис на нови данни, а всички останали – само за четене. Този притежател на блока, който има намерение да записва в него обновени данни, съобщава на всички останали за това, че за в бъдеще техните копия ще бъдат недостоверни. В резултат на това той става изключителен притежател на този обновен блок. Когато някой от останалите направи обръщение към своето копие на този блок, той ще установи недостоверността му и ще трябва да направи ново актуално копие преди да използва данните му.

Във втория случай могат едновременно да съществуват няколко притежателя с право на запис. Когато някой от тях направи запис и по този начин обнови даден блок, то той има право да разпространи този запис в останалите притежатели. Така всички процесори имат възможност да работят с достоверна информация.

В заключение следва да се каже, че нито един от горе описаните подходи няма решаващи предимства във всички ситуации, за да бъде предпочетен категорично. Все пак подходът, който при запис съобщава на останалите за недостоверност на техните данни е предпочетен в болшинството мултипроцесорни системи, реализирани на базата на процесори Intel и IBM. Състоянието на отделните кеш-линии в кеш паметите на тези процесори се маркира от 2 допълнителни бита в управляващото поле. С четирите комбинации, които те определят, се дефинират четири състояния в които може да се намира кеш-линията:

1. Modified - (променена). Съдържанието на кеш-линията е обновено, при това измененията не са отразени в оперативната памет – тази кеш-линия е достоверна само в рамките на тази кеш памет. При нейното изхвърляне тя се копира във всички по-ниски нива в йерархията на запомнящата система ;

2. Exclusive - (изключителна). Тази кеш-линия съдържа точно копие на данните от съответния блок в оперативната памет, като той съществува само в тази кеш памет и отсъства във всички останали. Признакът се присвоява автоматично при първоначално зареждане на кеш-линията от по-ниските нива или от оперативната памет. Обновяването на кеш-линия с този признак води до смяната му с Modified.

При изхвърляне на кеш-линия с признак Exclusive, в зависимост от архитектурата на кеш паметта, нейното съдържание или просто се унищожава (inclusive-кеш архитектура), или се разменя с това на съответната кеш-линия в кеш паметта от по-ниските нива (exclusive-кеш архитектура) ;

3. Shared - (разделяема, съвместно притежавана). Кеш-линията съдържа копие на блок от оперативната памет, но същият се съдържа и в някои от останалите кеш памети. Признакът може да се разбира в смисъл на това, че данните в тази кеш-линия са кохерентни с тези в оперативната памет.

4. Invalid - (недостоверна). Данните в тази кеш-линия са недостоверни.

Спазването на едно или друго поведение при използване на така определените признаци е известно в литературата като протокол MESI.

Кеш паметите на първо и на второ ниво в процесорите на Intel и на AMD поддържат всичките 4 състояния на кеш-линиите. Кеш паметта за команди обаче поддържа само две – Shared и Invalid. Останалите състояния не се поддържат по простата причина, че кеша за команди не допуска обновяване на кеш-линиите си. Ако това е възможно, то значи че става дума за самомодифицираща се програма, а това е проблематика, която не е обект на нашето внимание.

Таблица 6.2.2.2.1 Състояния и съответствия на данните

Състояние	Modified	Exclusive	Shared	Invalid
Тази кеш-линия действителна ли е?	да	да	да	не
Блокът в оперативната памет действителен ли е?	остарял	Действителен	Действителен	На тази линия не съответства никаква памет
Другите процесори съдържат ли копие на тази кеш-линия?	не	не	Може би	Може би
Запис в тази кеш-линия се осъществява ……	Само в тази линия, без обръщение към шината	Само в тази линия, без обръщение към шината	Едновременен запис в паметта с анулиране на блока в кешовете на останалите процесори	Непосредствено чрез шината

Преминаването от едно състояние в друго се причинява от определени събития, които ще разгледаме по-долу.

Кеш-пропуск при четене

Тук ще уточним, че под кеш-пропуск освен дефинираната в предидущите пунктове ситуация при асоциативно търсене на подадения от процесора тег, сега разбирането за кеш-пропуск се допълва със ситуацията, в която кеш-линията присъства в кеша, но се намира в състояние invalid.

Когато в една локална кеш памет при операция четене се получи кеш-пропуск, кеш-контролерът заявява операция четене от по-ниските нива, включително и от оперативната памет. При това той известява с помощта на специална линия от системната магистрала останалите процесори за необходимостта да проследят дадения трансфер. Възможни са няколко варианта на изхода от тази операция:

· Ако в някоя от локалните кеш памети съществува “чисто” необновявано копие на данните от този блок, при което той е маркиран като exclusive, съответния кеш-контролер, притежател на този блок, отвръща със сигнал, че той също използва този блок. След това той заменя своя признак exclusive на shared. Процесорът, заявил операцията, прочита данните от оперативната памет и променя състоянието на кеш-линията, в която поставя извлечения блок, от invalid на shared ;

· Ако се окаже, че няколко процесора притежават “чисто” копие на съответния блок, то кеш-линиите, които го съдържат ще бъдат в състояние shared. Така всеки от тези процесори ще отговори със сигнал, че притежава това копие. Процесорът, заявил операцията, прочита данните от оперативната памет и променя състоянието на кеш-линията, в която поставя извлечения блок, от invalid на shared ;

· Всяка кеш-линия след обновяване се маркира като modified. В резултат на това кеш-контролерът чрез системната магистрала временно блокира оперативната памет за операция четене, записва обновения блок в оперативната памет и променя състоянието на кеш-линията на shared. Така прочетеният от оперативната памет блок се поставя в кеш-линия, която се маркира с признак shared ;

· Ако в нито една от останалите кеш памети не се съдържа копие от заявения блок, никакви сигнали не се изпращат. Заявеният блок се прочита от оперативната памет, записва се в кеша, а кеш-линията в която се поставя, променя състоянието си от invalid на exclusive.

Кеш-попадение при четене

Ако необходимите данни се намират в кеш паметта, те се четат от там, без да се променя състоянието на съответната кеш-линия.

Кеш-пропуск при запис

Когато в локалната кеш памет при опит за запис не се намери съответният блок и възникне кеш-пропуск, кеш-контролерът стартира алгоритъма за извличането му от по-ниското ниво или от оперативната памет. Следва да различаваме това четене, от предидущото, тъй като данните се четат и отпращат в кеша, където ще бъдат обновени. За да се различава това четене от обикновеното, по системната магистрала се разпространява сигналът RWITM (read-whit-intent-to-modify), което означава четене с намерение за модифициране. След изпълнение на основната операция запис, кеш-линията е в състояние modified. Останалите участници в системата имат две възможности.

1. В един от останалите процесори вече се съдържа модифицирано копие (modified) на този блок. Процесорът, притежаващ това копие, отговаря със сигнал, предупреждаващ заявителя на основната операция, че и друг процесор разполага с модифицирано копие на същия блок. Предупреденият по този начин процесор прекратява своята инициатива по системната магистрала и изчаква следващите действия от страна на предупредилия го процесор. Докато заявителят изчаква, притежателят на модифицираното копие заема системната магистрала и прекопирва свето копие в оперативната памет, след което в своята кеш памет променя състоянието на съответната кеш-линия на , тъй като е разбрал, че процесорът, заявил основната операция запис има намерение да модифицира този блок. След възстановяване на спокойствието, така да се каже, инициаторът отново подава сигнала RWITM, извлича необходимия му блок от паметта, записва го в своя кеш, където след това го обновява и му установява състоянието modified ;

2. Никой от останалите процесори не притежава модифицирано копие на заявения блок и процесорът инициатор не получава никакви ответни сигнали на подадения от него сигнал RWITM. При това спокойствие той прочита от оперативната памет съответния блок и го записва в своя кеш, където го модифицира, след което го маркира в състояние modified. В същото време, останалите процесори (ако има такива), които притежават немодифицирано копие на този блок, променят състоянието на съответните си кеш-линии от shared на invalid. Ако от останалите процесори само един е притежавал немодифицирано копие на блока, сега той променя неговото състояние от exclusive на invalid.

Кеш-попадение при запис

Когато клетката, чието съдържание се променя в следствие на операцията запис се намира в локалната кеш памет, следващите събития при самото изпълнение на операцията зависят от текущото състояние на кеш-линията, в която се съдържа клетката.

· Ако текущото състояние на кеш-линията е shared. Преди да внесе изменения в съответната кеш-линия, кеш-контролерът следва да получи право за изключителното й притежаване. Това означава, че всички останали процесори, разполагащи с копие от тази кеш-линия, трябва в своите локално кеш памети да променят състоянието на съответните кеш-линии на invalid. Това те правят след като са получили от инициатора сигнала RWITM. Инициаторът на операцията обновява кеш-линията и променя състоянието й от shared на modified ;

· Ако текущото състояние на кеш-линията е exclusive. Това състояние означава, че кеш-контролерът има изключително право да притежава тази кеш-линия и има право незабавно да обнови съдържанието й и да промени състоянието й от exclusive на modified ;

· Ако текущото състояние на кеш-линията е modified. Кеш-контролерът притежава изключително тази кеш-линия и има право незабавно да обнови съдържанието й. В този случай не се налага промяна в състоянието й – то остава modified.

Описаните действия се представят компактно със следните граф-схеми:

Фиг. 6.3.2.2.1. Изменения на състоянието на кеш-линията при реализация на протокола MESI

В горните рисунки са употребени следните означения:

RH - кеш-попадение при операция четене ;

RMS - кеш-пропуск при операция четене, shared ;

RME - кеш-пропуск при операция четене, exclusive ;

WH - кеш-попадение при операция запис ;

WM - кеш-пропуск при операция запис ;

SHR - кеш-попадение при операция четене, отследяващ процесор ;

SHW - кеш-попадение при операция запис или четене с намерение за модификация ;

Кохерентност на данните в системата L1-L2

Въпреки, че по-горе се споменаваше, тук отделно се спираме на структура с йерархична кеш памет (от две нива), която е типична за съвременните процесори. Като правило в тази структура кеш паметта на първо ниво няма директна връзка със системната магистрала на системата, а такава има кеш паметта на второ ниво. Освен това тя е различна от тази между двата кеша. От тук се появява необходимост за съгласуване на данните между двете нива.

Средствата за това съгласуване представляват някакво разширение на протокола. Предполага се, че и в двата кеша, всяка кеш-линия притежава битовете за признака на състоянието. За всяка кеш-линия, която се съдържа и в двете нива, съгласуващият механизъм (алгоритъм) трябва да осигурява отследяване на изменението в състоянието на кеш-линията в кеша L1 до нейното копие в кеша L2. Най-лесно това би се постигнало с техниката на едновременния запис между двете нива. В резултат измененията на състоянието стават видими за останалите процесори на ниво кеш L2.

Ако кеш паметта на първо ниво използва техниката на обратния запис, то взаимодействието между двете нива се усложнява значително. Разработеното за тази техника поведение за съгласуване е реализирано още в процесора Pentium II.

С изложеното дотук приемаме, че главните, принципните положения, отнасящи се до проблемите на съгласуването (кохерентността) на информацията в йерархичните запомнящи системи, са изяснени. Анализът, проектирането, изграждането и изследването на реалните многопроцесорни системи, ще изискват от читателя детайлно изучаване на реализираните в съответните процесори техники и протоколи.

Следващият раздел е:

6.3.2.3. Съображения за оптимално използване на системи с кеш памет