Материалы

Алгоритмы обеспечения когерентности системы памяти

Рейтинг:   / 0
ПлохоОтлично 

Проблема когерентности состоит в том, что при наличии в системе КЭШ-памяти одному исполнительному адресу соответствует более чем одно место хранения данных. Проблема возникает тогда, когда имеется более, чем одно устройство, способное модифицировать содержимое памяти. В этом случае одно устройство может изменить значение элемента (например, контроллер ПДП записывает блок данных в основную память), в то время как другое устройство (процессор), работая с другим экземпляром того же элемента данных, находящимся в КЭШе, будет использовать старое (неизмененное) значение. Понятно, что такие ситуации недопустимы.

Рассмотрим, что следует сделать, если когерентность нарушается при модификации КЭШ-строки. В этом случае требуется:

  • записать (может быть с некоторой задержкой) измененное значение в основную память;
  • сбросить признаки достоверности в прочих копиях (КЭШ-памяти других процессоров системы, если таковые имеются).

Для записи модифицированного данным процессором значения из его КЭШа в основную память используются две стратегии: сквозная запись (write-through) и обратная запись (write-back).

При сквозной записи перенос модифицируемого значения из КЭШа в ОЗУ происходит одновременно с изменением в КЭШе. Достоинство этой стратегии состоит в автоматическом обеспечении когерентности данного КЭШа и ОЗУ, а недостаток - в заметном снижении скорости (каждая запись безусловно идет в ОЗУ, даже если следующая команда снова будет модифицировать тот же элемент данных). На время обращения к ОЗУ дальнейшее выполнение программы приостанавливается.

Существует модификация этой стратегии, называемая буферизованной сквозной записью, при которой копирование модифицированной КЭШ- строки в ОЗУ происходит не сразу, а через промежуточный буфер, работающий по схеме FIFO. Копирование в этот буфер происходит так же быстро, как и в КЭШ. При этом в многопроцессорной системе сразу же происходит сброс битов достоверности в КЭШ-памяти других процессоров. Перенос содержимого буфера в ОЗУ осуществляется затем параллельно с продолжением выполнения программы в те промежутки, когда данный процессор освобождает шину, связывающую его с основной памятью. В этом случае также возможны задержки (например, если следующее обращение к КЭШу тоже вызовет КЭШ-промах), однако это будет происходить реже, чем в отсутствие буфера.

Существуют определенные правила работа с указанным буфером. В частности, если буфер занят и идет чтение ячейки ОЗУ, то чтение происходит в обход буфера (изменяется последовательность обращения к памяти).

При использовании стратегии обратной записи перенос модифицированной КЭШ-строки в ОЗУ происходит только при ее замене, что в среднем случается реже, чем обращения к ней (в КЭШ). Как следствие, эта стратегия обеспечивает меньшую по сравнению со сквозной записью, долю обращений к ОЗУ, т.е. более высокую эффективность кэширования.

Недостатки обратной записи:

  • более сложная аппаратная реализация,
  • сложнее обеспечить когерентность,
  • при замене модифицированной строки возникает задержка, обусловленная необходимостью обращения к ОЗУ.

Последний недостаток можно частично устранить, используя упреждающую обратную запись: строка-кандидат на замену определяется заранее, переносится из КЭШа в ОЗУ в интервалах, когда шина свободна, и затем объявляется в данном КЭШе недостоверной. В результате в КЭШ-памяти почти всегда имеется свободная строка, которую можно без задержки использовать при КЭШ-промахе. Для обеспечения когерентности в сложных системах с несколькими КЭШами разработан и стандартизован протокол обеспечения когерентности, называемый MESI по названиям состояний, в которых может находиться КЭШ-строка: Modified, Exclusive, Shared, Invalid.

•Invalid. Это состояние означает, что строка недостоверна в данном КЭШе. При обращении к этому элементу будет зафиксирован КЭШ-промах и произойдет внешнее обращение в память следующего уровня (в КЭШ L2 или в основную память).

•Shared. Строка в КЭШе содержит достоверные данные и совпадает с содержимым основной памяти. Обращение будет внутренним (в данный КЭШ) и не приведет к активизации внешней шины.

•Exclusive. Строка достоверна, находится в КЭШе, совпадает с содержимым основной памяти, а экземпляры этой строки, находящиеся в других КЭШах, являются недостоверными.

•Modified. Строка находится в КЭШе, достоверна, но содержит более поздний (модифицированный) экземпляр данных, нежели остальные экземпляры в основной памяти и в других КЭШах.

Замечание 1: Строка достоверна, если она находится в состояниях S, E или M.
Замечание 2: Если строка находится в состоянии I, это означает, что она свободна.

Собственно протокол состоит из набора правил, по которым меняется состояние КЭШ-строки в результате возникновения разных событий, могущих быть причинами нарушения когерентности. В основе этих правил лежит принцип объявления строки недостоверной в случае подозрения в нарушении когерентности, что при обращении к этой строке вызовет КЭШ-промах и обновление содержимого этой строки новым значением из основной памяти. Таблица(см. ниже)  и рисунок (см. ниже), взятые из технического описания процессора Pentium, показывают эти правила.

Basic MESI State Transitions

 

Схема изменения MESI-состояний
Яндекс.Метрика