Что такое проблема согласованности кеша?
Согласованность кэша - это проблема, возникающая в многоядерных системах с распределенными кэшами L1 и L2. Каждое ядро имеет свои собственные кеши L1 и L2, и они всегда должны быть синхронизированы друг с другом, чтобы иметь самую последнюю версию данных.
Проблема согласованности кэша - это проблема поддержания синхронизации нескольких локальных кешей, когда один из процессоров обновляет свою локальную копию данных, которая совместно используется несколькими кешами.
Представьте себе сценарий, в котором несколько копий одних и тех же данных существуют в разных кэшах одновременно, и если процессорам разрешено свободно обновлять свои собственные копии, это может привести к противоречивому представлению о памяти.
Например, представьте себе двухъядерный процессор, в котором каждое ядро помещает блок памяти в свой частный кеш, а затем одно ядро записывает значение в определенное место. Когда второе ядро пытается прочитать это значение из своего кеша, у него не будет самой последней версии, если только его запись в кеше не станет недействительной и не произойдет промах в кеше. Этот промах в кэше приводит к обновлению записи в кэше второго ядра. Чтобы вызвать недействительность кеша, нам нужны политики согласованности кеша. Если на месте нет политики согласованности кеша, будут считаны неверные данные и будут получены недопустимые результаты, что может привести к сбою программы.
Политики записи в кэш
Существуют две основные политики записи в кэш.
- Обратная запись: операции записи обычно выполняются только в кэш. Основная память обновляется только тогда, когда соответствующая строка кэша удаляется из кеша.
- Сквозная запись: все операции записи выполняются как в основную память, так и в кэш, обеспечивая постоянную работу основной памяти.
Из приведенного выше описания ясно, что политика обратной записи приводит к несогласованности. Если два кэша содержат одну и ту же строку, и строка обновляется в одном кэше, другой кеш будет бессознательно иметь недопустимое значение. Последующее чтение этой недопустимой строки приводит к неверным результатам.
Но если подумать глубже, даже в политике сквозной записи также есть проблемы с согласованностью. Даже если память обновляется, может возникнуть несогласованность, если другой кэш не отслеживает трафик памяти или не получает какое-либо прямое уведомление об обновлении.
Чтобы решить эту проблему, мы вводим протоколы согласования кэша. Цель любого протокола согласованности кеша - загрузить недавно использованные локальные переменные в соответствующие кеши и сохранить их во время многочисленных операций чтения и записи, при этом используя протокол для поддержания согласованности общих переменных, которые могут находиться в нескольких кэшах одновременно.
Прежде чем перейти к решениям проблемы согласованности кэша, сначала давайте посмотрим, каковы распространенные способы записи в кэш.
Протокол сквозной записи (WT)
Есть две основные реализации протокола WT.
- Завершить запись с протоколом обновления
- Полная запись с признанием копий недействительными
Завершить запись с протоколом обновления
Когда процессор записывает новое значение в свой кэш, новое значение также записывается в модуль памяти, который содержит изменяемый блок кеша. Некоторые копии этого блока могут существовать в других кэшах, эти копии необходимо обновить, чтобы отразить изменение, вызванное операцией записи.
Мы обновляем другие копии кеша, выполняя широковещательную рассылку обновленных данных всем процессорным модулям в системе. Каждый процессорный модуль получает широковещательные данные, он обновляет содержимое затронутого блока кэша, если этот блок присутствует в его кэше.
Полная запись с признанием копий недействительными
Когда процессор записывает новое значение в свой кэш, это значение записывается в память, а все другие копии в других кэшах становятся недействительными. Это также делается путем широковещательной рассылки запроса на признание недействительности через систему. Все кеши получают этот запрос на аннулирование, и кеш, содержащий обновленные данные, очищает свою строку кэша.
Протокол обратной записи (WB)
В протоколе WB может существовать несколько копий блока кэша, если разные процессоры загрузили (прочитали) блок в свои кэши.
В этом подходе, если какой-либо процессор хочет изменить этот блок, он должен сначала стать исключительным владельцем блока.
Когда право собственности на этот процессор передается модулем памяти, который является исходным местоположением блока. Все остальные копии, в том числе в модуле памяти, становятся недействительными.
Теперь владелец блока может изменить содержимое памяти.
Когда другой процессор хочет прочитать этот блок, данные отправляются этому процессору текущим владельцем. Данные также отправляются в домашний модуль памяти, который требует владения и обновляет блок, чтобы он содержал последнее значение.
Существуют программные и аппаратные решения проблемы согласованности кеша.
Решение на уровне программного обеспечения - механизм согласования кэша на основе компилятора
При программном подходе мы пытаемся обнаружить потенциальные сегменты кода, которые могут вызвать проблемы с согласованностью кеша, и обработать их отдельно.
Потенциальная проблема согласованности кеша передается из среды выполнения во время компиляции, а сложность проекта передается от оборудования к программному обеспечению.
Обратной стороной этого подхода является время компиляции; программные подходы обычно принимают консервативные решения. что приводит к неэффективному использованию кеша.
Механизм согласованности кэша на основе компилятора выполняет анализ кода, чтобы определить, какие элементы данных могут стать небезопасными для кэширования, и они соответствующим образом маркируют эти элементы.
Итак, есть еще несколько элементов с возможностью кеширования, и операционная система или оборудование не кэшируют эти элементы. Это самый простой способ предотвратить кэширование любых переменных общих данных.
Но это не оптимальный подход и слишком консервативный, потому что общая структура данных может использоваться исключительно в течение некоторых периодов и может быть эффективно доступна только для чтения в другие периоды. Проблема с согласованностью кеша возникает только в периоды монопольного доступа.
Более эффективные подходы анализируют код для определения безопасных периодов для общих переменных. Затем компилятор вставляет инструкции в сгенерированный код, чтобы обеспечить согласованность кеша в критические периоды.
Решения аппаратного уровня
Решения на аппаратном уровне намного лучше, чем решения на программном уровне, поскольку они обеспечивают динамическое распознавание возможных состояний несогласованности во время выполнения. Поскольку проблема решается только тогда, когда она действительно возникает, кеши используются более эффективно, что приводит к повышению производительности по сравнению с программным подходом.
Схему оборудования можно разделить на две категории:
- Протоколы каталогов
- Протоколы Snoopy
Протоколы каталогов
В этом подходе мы собираем и поддерживаем информацию о том, где находятся копии строк в каждом кэше.
Типичная реализация имеет централизованный контроллер, который является частью контроллера основной памяти. В основной памяти хранится каталог, содержащий информацию о глобальном состоянии содержимого различных локальных кешей.
Когда отдельный контроллер кеша делает запрос, централизованный контроллер проверяет и выдает необходимые команды для передачи данных между памятью и кешами или между самими кэшами.
Он также отвечает за поддержание актуальности информации о состоянии, поэтому о каждом локальном действии, которое может повлиять на глобальное состояние линии, необходимо сообщать центральному контроллеру. Контроллер хранит информацию о том, какие процессоры имеют копию каких строк.
Прежде чем процессор сможет записать в локальную копию строки, он должен запросить монопольный доступ к строке у контроллера.
Давайте посмотрим, как отдельный контроллер кеша пытается обновить свою локальную копию строки кеша.
- Запрос контроллера локального кеша на монопольный доступ к строке от централизованного контроллера кеша
- Перед предоставлением монопольного доступа контроллер отправляет сообщение всем процессорам с кэшированной копией этого времени, вынуждая каждый процессор сделать свою копию недействительной.
- Централизованный контроллер получает подтверждение от каждого процессора
- Контроллер предоставляет эксклюзивный доступ запрашивающему процессору.
- Когда другой процессор пытается прочитать строку, которая предоставлена исключительно другим процессорам, это приводит к промаху в кэше, он отправляет уведомление о промахе на контроллер.
- После получения уведомления о промахе кэш-памяти контроллер выдает команду процессору, имеющему монопольный доступ, на обратную запись в основную память.
Недостатки схемы каталогов:
- Узкое место в центральном контроллере кеш-памяти
- Накладные расходы на связь между различными контроллерами кэш-памяти и центральным контроллером.
Протоколы Snoopy
Протоколы Snoopy распределяют ответственность за поддержание согласованности кэша между всеми контроллерами кеша в многопроцессорной системе.
Кэш должен распознавать, когда содержащаяся в нем строка используется совместно с другими кешами. Когда действие обновления выполняется в строке общего кэша, оно должно быть объявлено всем другим кешам с помощью механизма широковещательной рассылки.
Каждый контроллер кеша может «отслеживать» в сети, чтобы отслеживать эти широковещательные уведомления и реагировать соответствующим образом.
Протоколы Snoopy идеально подходят для мультипроцессоров на базе шины, поскольку общая шина предоставляет простые средства для широковещательной передачи и отслеживания.
Исследованы два основных подхода к протоколам отслеживания:
- Отмена записи протокола отслеживания
- Протокол отслеживания записи-обновления (записи-широковещательной рассылки)
Протокол аннулирования записи
Может быть несколько читателей, но только один пишет за раз.
Первоначально строка может быть разделена между несколькими кешами для целей чтения.
Когда один из кешей хочет выполнить запись в строку, он сначала выдает уведомление, которое делает недействительным этот зубец в других кешах, делая строку эксклюзивной для кэш записи.
Как только линия является эксклюзивной, процессор-владелец может производить локальные записи до тех пор, пока какой-либо другой процессор не потребует ту же строку.
Запись с протоколом обновления
Может быть несколько писателей, а также несколько читателей.
Когда процессор желает обновить общую строку, слово, которое нужно обновить, передается всем остальным, и кеши, содержащие эту строку, могут его обновить.
Ссылки:
