С.В. Герасимов, И.В. Машечкин, М.И. Петровский, И.С. Попов, А.Н. Терехин, А.В. Чернов - Организация кэширования (1114662), страница 4
Текст из файла (страница 4)
Их тэги в локальных кэш проставляют специальный флаг, а при попытке обратиться с операцией чтения или записи к данному блоку другим процессом произойдет промах кэш, и данный блок будет заново подгружен из оперативной памяти после освобождения эксклюзивного захвата. Нетрудно проверить, что все правила когерентности при таком протоколе выполняются.Альтернативой рассмотренного протокола является протокол,при котором происходит непосредственная запись обновленногоблока данных в кэш всех процессоров, где он используется. Такоедействие называется широковещательной записью. Этот протоколиспользуется достаточно редко, поскольку он сложен в реализации иобладает существенным недостатком.
В случае последовательныхопераций записи одним процессором в один блок памяти без одновременного чтения другими процессорами данных протокол широковещательной записи потребует обновления всех кэш после каждой операции, в то время как протокол инвалидации просто проставит соответствующий флаг.
С другой стороны, время реального обновления данных в кэш всех процессоров, использующих измененный блок памяти, естественно меньше при использовании широковещательной записи, поскольку операция обновления кэш работаетбыстрее, чем последовательность операций: инвалидация, промах,замещение.При использовании протоколов когерентности кэш на основеотслеживания в UMA системах все процессоры постоянно просматривают появляющиеся операции работы с памятью через общуюшину и проверяют, происходит ли работа с теми же блоками памяти,что находятся у них в локальных кэш, проставляя соответствующийпризнак невалидности или обновляя данные в кэш.
В случае использования кэш с сквозной записью функционирование таких системочевидно. В случае же кэш с отложенной записью ситуация сложнее, поскольку результаты самого последнего изменения могут находиться не в оперативной памяти, а в локальном кэш одного изпроцессоров, к которому нет доступа у других процессоров. В этомслучае обращение к памяти будет прервано до тех пор, пока не произойдет выгрузка соответствующего блока кэш, владеющим им процессором. Вся информация о валидности, эксклюзивном захвате суказанием процессора-владельца и разделяемом доступе на чтениебез захвата хранится в тэг кэш каждого процессора и обновляется взависимости от действий ЦПУ или сигналов из шины.
Модельное19представление переходов состояния отдельного блока кэш в отдельном локальном процессоре показано на диаграмме состояний.ОТ ЦП: попадание чтенияINVALID(информация вблоке не актуальна)ОТ ЦП: промах чтенияВ ШИНУ: промах по чтениюОТ ЦП: чтение блокаВ ШИНУ: чтение блокаОТ ШИНЫ: промах по чтениюОТ ЦП: промах по чтениюВ ШИНУ: промах по чтениюОТ ЦП: запись блока,В ШИНУ: запись блокаОТ ЦП: запись блока,В ШИНУ: запись блокаОТ ШИНЫ: промах записиОТ ЦП: попадание записиили чтенияSHARED(блок в режимеобщего доступа начтение)EXCLUSIVE(блок в режимезахвата на чтение изапись)Для каждого перехода:в разделе «ОТ» указано, кто (ЦП или ШИНА) инициировалпереход (от кого пришел сигнал) и за счет какого именно действия (запись, чтение, промах записи, промах чтения);в разделе «В» указано, какое сообщение посылается в шинупри переходе в целевое состояние.Примерно такой конечный автомат реализован в кэш контроллере для каждого из кэш блоков.
Следует заметить, что смена состояний, в том числе выход из эксклюзивного состояния, происходит автоматически при появлении соответствующих событий от шины или ЦП и не требует «разрешения» у ЦП – «владельца блока».Если два процессора одновременно пишут в один и тот же блок памяти, то они будут конкурировать за «эксклюзивное» состояние этого блока, перехватывая его друг у друга, поскольку «удержать» егоневозможно.
Атомарность операций и переходов обеспечивается засчет общей шины.Кэширование в NUMA системахИной подход к реализации систем с общей оперативной памятью предлагает архитектура систем с неоднородным доступом кпамяти (NUMA - non-uniform memory access). Такие архитектуры20также называют системами с распределенной памятью (Distributedmemory systems).ЦПЦПЦПЦПодин или болееуровней кэшодин или болееуровней кэшодин или болееуровней кэшодин или болееуровней кэшЛокальнаяоперативнаяпамятьЛокальнаяоперативнаяпамятьЛокальнаяоперативнаяпамятьЛокальнаяоперативнаяпамятьЛогически общаяоперативная памятьВысокоскоростная сетьМасштабируемость и степень параллелизма в NUMAсистемах выше, чем в UMA.
Для NUMA-систем характерны следующие свойства:процессорные элементы физически являются отдельнымивычислительными модулями со своими ЦП, кэш, ОП, контроллером ввода-вывода и т.д., но работают на общем адресном пространстве;характеристики доступа процессора к области оперативнойпамяти зависят от того, к каким областям идет обращение (клокальной или нелокальной памяти).Контроллер памяти позволяет осуществлять взаимодействиемежду вычислительными узлами. Доступ процессора к своей ОПосуществляется через свой контроллер, к чужой – через два контроллера, свой и чужой. При обращении не к своей памяти контроллер выбрасывает запрос на общую шину, целевой контроллер егопринимает и возвращает результат.В NUMA-системах остается проблема синхронизации кэш.Существует несколько способов ее решения:не использовать кэширование (процессоры без кэш);использовать модель ccNUMA (Cache coherent NUMA).Для синхронизации кэш в ссNUMA системах, как правило, используется подход на основе словарей, согласно которому с каждымблоком физически распределенной оперативной памяти связана отдельная запись в словаре.
При этом каждый блок и, соответственно,запись в словаре уникальны в рамках системы, а сам словарь можетхраниться и обрабатываться распределено. Как и в подходе с отслеживанием, подход на основе словарей должен обрабатывать двеосновные ситуации, требующие синхронизации: запись в общую область памяти и промах по чтению.21Упрощенная модель протокола поддержания когерентностиопределяет для каждого блока памяти в словаре три состояния:Общий доступ (на чтение) - один или более процессоровзагрузили блок к себе в кэш, и данные в этом блоке и вовсех кэш консистентны;Не закеширован – ни один процессор не использует данныйблок;Эксклюзивный захват – один из процессоров захватил блокс целью записи данных, остальные копии в кэш другихпроцессоров неактуальны.Суть протокола состоит в организации корректных переходовв рамках перечисленных состояний и передачи актуальной информации (копии) блоков память в локальные кэш.
Для этого используется механизм передачи сообщений. Рассмотрим, какие типы сообщений могут передаваться. В этом процессе могут участвовать дотрех физически отдельных вычислительных узлов: узел Q - физический владелец блока ОП А, узел P, на котором потребовалось изменить данные D в блоке A, и узел R – физический владелец записи всловаре о блоке А.Тип сообщения ОтправительПолучательЛокальныйУзел R с запиRead Miss промах чтения узел процессо- сью словаряпроцессораP ра Pдля Аблока AУзел R с запиWrit Miss - ЛокальныйПромах записи узел процессо- сью словаряпроцессораP ра Pдля Аблока AInvalidateИнвалидацияблока A в узлевладельце QFetchВыборка A уузла владельцаQУзел R с запи- Узел Q, храсьюсловаря нящий блок Aдля АУзел R с запи- Узел Q, храсьюсловаря нящий блок Aдля АFetch/Invalidate Узел R с запи- Узел Q, храВыборка с ин- сьюсловаря нящий блок Aвалидацией A у для Аузла владельцаQ22ДействияЗапросить данные блока Aдля P; Прописать в словаре у R статус для A «общий доступ» с процессором PЗапросить данные блока Aдля P;Прописать в словаре у Rстатус для A «эксклюзивный захват» процессоромPПроставить признак инвалидации блока A, которыйбыл в разделяемом доступе у узла владельца QВыбрать содержимое Dблока A и переслать актуальное содержимое из узлаQ в узел R с его записьюсловаряВыбрать содержимое Dблока A, проставить емустатус не валидного и переслать актуальное содержимое из узла Q в узел R сData reply Получение данных D блока AData write back-Запись данныхD блока AУзел R с записьюсловарядля АУзел Q, хранящий блок AЛокальныйузел процессора PУзел R с записью словарядля Аего записью словаряПереслать данные D блокаA запросившему процессору P из RЗаписать данные D блокаA в оперативную памятьпроцессора Q владельца AВ терминах приведенных в таблице сообщений можно описать диаграмму состояний блока памяти A, которую реализует узел-владелецQ.ОТ ЦП: попадание чтенияINVALID(информация вблоке не актуальна)ОТ СЛОВАРЯ: инвалидацияОТ ЦП: чтение блокаВ СЛОВАРЬ: промах чтенияОТ ЦП: промах по чтениюВ СЛОВАРЬ: промах чтенияОТ СЛОВАРЯ: выборкаОТ ЦП: запись блока,В СЛОВАРЬ: промах записиОТ ЦП: запись блока,В СЛОВАРЬ: промах по записиОТ СЛОВАРЯ: выборка с инвалидациейОТ ЦП: попадание записиили чтенияSHARED(блок в режимеобщего доступа начтение)EXCLUSIVE(блок в режимезахвата на чтение изапись)Аналогичную схему для отслеживания состояния записи словаряреализует узел R, владелец записи словаря для блока памяти A.23Промах чтения; получение данных;«Пользователи» = «Пользователи»+{P}UNCACHED(блок не находитсяв кэш ни у кого)чтения; получение данных;«Пользователи» = {P}Промах записи; инвалидация«Пользователи» = {P}Промах чтения ; получение данных;EXCLUSIVE(блок в режимезахвата на чтение изапись)«Пользователи»= «Пользователи» + {P}«Пользователи» = {P}Промах записи; получение данныхЗапись данных«Пользователи» = {}Промах записи; Выборка с инвалидацией;получение данных;«Пользователи» = {P}SHARED(блок в режимеобщего доступа начтение)Следует отметить, что поскольку все события инициируютсяизвне, и сам владелец записи словаря не инициирует никаких событий, кроме обновления статуса записи в словаре, то в диаграмме переходов отсутствуют атрибуты «ОТ» и «В».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
