<<
>>

Согласованность кэшей

Предположим, что память секвенциально состоятельна. Что происходит, когда процессор 1 содержит в своем кэше некую строку, а процессор 2 пытается считать слово, соответствующее той же строке кэша? При отсутствии специальных правил процессор 2 получит копию этой строки в свой кэш.
В принципе двойное кэширование одной и той же строки вполне приемлемо. А теперь предположим, что процессор 1 изменяет строку, и сразу после этого процессор 2 считывает копию этой строки из своей кэш-памяти. В результате он получает устаревшие данные, нарушая контракт между программным обеспечением и памятью. Ни к чему хорошему для программы, выполняемой процессором 2, это не приведет.

Данная проблема, которая носит название проблемы согласованности кэшей, очень важна. Если ее не разрешить, нельзя будет использовать кэш-память, и число мультипроцессоров, подсоединенных к одной шине, придется сократить до двух-трех. Специалистами было предложено множество различных решений (см., например, [77, 159]). Хотя все эти алгоритмы, называемые протоколами согласования кэшей, в некоторых деталях различаются, все они не допускают одновременного появления разных версий одной и той же строки в двух или более кэшах.

Во всех решениях контроллер кэш-памяти разрабатывается так, чтобы кэш мог обеспечивать мониторинг запросов, идущих по шине от других процессоров и других кэшей, в каждом конкретном случае предпринимая те или иные действия.

Указанное устройство получило название следящего кэша (snooping cache), поскольку кэш как бы «следит» за шиной. Набор правил, которым следуют кэш, процессоры и основная память, чтобы предотвратить появление различных версий данных в нескольких кэшах, и называют протоколом согласования кэшей. Единицей передачи и хранения для кэша является строка кэша. Обычно длина строки кэша составляет 32 или 64 байт.

Самый простой протокол согласования кэшей называется сквозной записью (write through).

Чтобы лучше понять механизм работы этого протокола, рассмотрим 4 случая, перечисленные в табл. 8.5. Если процессор пытается считать слово, которого нет в кэш-памяти, контроллер кэш-памяти загружает в кэш строку, содержащую это слово. Строку предоставляет основная память, которая в этом протоколе всегда должна хранить обновленные данные. В дальнейшем информация может считываться из кэша.
Таблица 8.5. Сквозная запись (пустые графы означают, что никакого действия не происходит)
Действие Локальный запрос Удаленный запрос
Кэш-промах чтения Вызов данных из памяти
Кэш-попадание чтения Использование данных из локального кэша
Кэш-промах записи Обновление данных в памяти
Кэш-попадание записи Обновление кэша и памяти Объявление элемента в кэше недействительным

В случае кэш-промаха записи модифицированное слово записывается в основную память. Строка, содержащая нужное слово, не загружается в кэш. В случае кэш-попадания записи кэш обновляется, а слово к тому же записывается в основную память. Суть протокола состоит в том, что в результате всех операций записи записываемое слово обязательно проходит через основную память, чтобы данные в основной памяти всегда были «свежими».

Рассмотрим все эти действия снова, но теперь с позиции следящего кэша (крайняя правая колонка в табл. 8.5). Назовем кэш, который выполняет действия, кэшем 1, а следящий кэш — кэшем 2. Если происходит кэш-промах чтения кэша 1, кэш 1 обращается к шине, чтобы получить нужную строку из основной памяти. Кэш 2 видит это, но ничего не делает.

Если же происходит кэш-попадание чтения кэша 1 (то есть нужная строка уже содержится в кэше 1), обращение к шине не выполняется, поэтому кэш 2 ничего не знает о кэш-попаданиях чтения кэша 1.

Процесс записи более интересен. Если процессор 1 записывает слово, кэш 1 обращается к шине как в случае кэш-промаха, так и в случае кэш-попадания. При любой записи кэш 2 проверяет наличие записываемого слова у себя. Если слово отсутствует, кэш 2 рассматривает это как кэш-промах удаленной памяти и ничего не делает. (Отметим, что, согласно табл. 8.5, кэш-промах удаленной памяти означает, что слово отсутствует в следящем кэше, а есть оно в кэше-инициаторе или нет, значения не имеет. Таким образом, один и тот же запрос может дать локальное кэш-попадание и кэш-промах для следящего кэша, и наоборот.)

А теперь предположим, что кэш 1 записывает слово, которое есть в кэше 2. Если кэш 2 ничего не предпримет, он будет содержать устаревшие данные, поэтому кэш 2 помечает как недействительный тот элемент кэш-памяти, который содержит измененное слово. В результате элемент просто удаляется из кэша. Поскольку все кэши следят за всеми обращениями к шине, запись любого слова ведет к обновлению его в кэше-инициаторе и в основной памяти, а также к удалению его из всех других кэшей. Таким образом предотвращается появление несогласованных версий.

Естественно, процессор кэша 2 вправе прочитать то же самое слово на следующем цикле. В этом случае кэш 2 получает слово из основной памяти, которая уже обновилась. В этот момент кэш 1, кэш 2 и основная память содержат идентичные копии этого слова. Если же какой-нибудь процессор произведет запись, то кэши других процессоров будут очищены, а основная память опять обновится.

Возможны различные вариации этого основного протокола. Например, в случае кэш-попадания записи следящий кэш обычно объявляет недействительным элемент, содержащий записываемое слово. Однако вместо того чтобы объявлять слово недействительным, можно принять новое значение и обновить кэш.

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

Еще один вариант — загрузка следящего кэша при кэш-промахах записи. Такая загрузка никак не сказывается на правильности алгоритма; она влияет только на производительность. Возникает вопрос: какова вероятность, что только что записанное слово вскоре опять будет записано? Когда вероятность высока, можно говорить в пользу загрузки кэша при кэш-промахах записи (политика заполнения по записи). Когда вероятность мала, то в случае кэш-промаха записи лучше не обновлять кэш-память. Если данное слово вскоре должно быть считано, после кэш-промаха чтения оно все равно окажется загруженным, поэтому нет смысла загружать его при кэш-промахе записи.

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

<< | >>
Источник: Таненбаум Э.. Архитектура компьютера. 5-е изд. 2007

Еще по теме Согласованность кэшей:

  1. 1.1.7.6. Необходимость согласования увольнения с профсоюзной организацией
  2. 4.4.3. Согласование ответов, не связанных со стимульной ситуацией
  3. 4.4.3. Согласование ответов, не связанных со стимульной ситуацией
  4. У журналистов существует неписаный запрет на интервью с детьми без согласования со взрослыми. Интервьюируя детей, надо помнить о заповеди «Не навреди!».
  5. СМИ как институт демократии. Плюрализм и толерантность в сфере массовой информации, СМИ как канал выражения и согласования социальных интересов. Социальный диалог в СМИ, как средство достижения целей социального консенсуса, согласия, социального партнерства.
  6. Права студенческих профсоюзов:
  7. СОВМЕСТИМОСТЬ ГРУППОВАЯ
  8. КООРДИНАЦИЯ СЕНСОМОТОРНАЯ
  9. 2. Заключение договора поставки.
  10. КООРДИНАЦИЯ
  11. СОВМЕСТИМОСТЬ
  12. Основные компоненты.
  13. 5. Ассоциация книгоиздателей, Всероссийская ассоциация издателей и редакторов газет.
  14. Акустика передачи
  15. Основания
  16. Статья 1136. Право участника на информацию
  17. Статья 871. Выполнение работы по договору бытового подряда из материала заказчика
  18. СОЕДИНЕНИЕ НА ПЯТОЙ СТАДИИ
  19. Статья 873. Размер оплаты по договору бытового подряда
  20. Статья 986. Сострахование