Моделирование ассоциативного кэша — работа с ошибочной схемой

Question

Во время работы над моделированием полностью ассоциативного кэша (в сборке MIPS) на ум пришла пара вопросов, основанных на некоторой информации, прочитанной в Интернете;

Согласно некоторым заметкам Университета Мэриленда

Находим слот:Максимум один слот должен совпадать.Если соответствует более одного слота, то у вас есть неисправная полностью ассоциативная схема кэша.У вас никогда не должно быть более одной копии линии кэша ни в одном слоте полностью ассоциативного кэша.Трудно поддерживает несколько копий и не Смысл.Слоты можно использовать для других строк кэша.

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

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

Answer 1

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

Без сомнения, это следует считать ошибкой.

Но если мы просто решили не исправлять ошибку (возможно, нам не хотелось бы выделять столько аппаратного обеспечения для лучшей реализации), наиболее очевидным вариантом будет выбрать один из слотов, который нужно объявить недействительным.Затем он будет доступен для других строк кэша.

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

Редактировать:вот как я мог бы реализовать аппаратное обеспечение для этого:

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

• Строка уже есть в кеше, никаких действий не требуется.
• Строки нет в кеше, но имеются недопустимые слоты:Поместите новую линию в один из доступных слотов.
• Строки нет в кеше, но недопустимых слотов нет.Другая допустимая строка должна быть исключена, и ее место займет новая строка.
  
  • Выбор кандидата на выселение имеет последствия для производительности.Очистить строки кэша можно выселен бесплатно, но если выбрано неправильно, это может привести к еще одному промаху кеша в ближайшем будущем.Учтите, что все строки кэша, кроме одной, загрязнены.Если вытесняется только чистая строка кэша, то множество последовательных операций чтения, чередующихся между двумя адресами, приведут к промаху кэша при каждом чтении.Инвалидация кэша входит в число двух жесткий проблемы в Comp Sci (второй из которых - «именование вещей») и выходит за рамки этого конкретного вопроса.

Я бы, вероятно, реализовал поиск, который проверяет правильный слот для каждого из них.Затем другой блок выбирал первый из этого списка и действовал в соответствии с ним.

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

Теперь давайте рассмотрим более неправдоподобный случай, когда один кэш используется двумя ядрами ЦП.Мы просто сделаем самую простую вещь, которая может сработать, и продублируем все, кроме самой кэш-памяти для каждого ядра.Таким образом, аппаратное обеспечение поиска слотов нет общий.Для этого в качестве мьютекса используется дополнительный бит на слот.оборудование поиска не может использовать слот, заблокированный другим ядром.конкретно,

• Если адрес находится в кеше, попробуйте заблокировать слот и вернуть его.Если слот уже заблокирован, ларек пока он не станет бесплатным.
• Если адреса нет в кеше, найдите разблокировано слот, который недействителен или действителен, но может быть исключен.

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

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

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

одним из решений может быть просто сказать, что грязные линии принадлежат только одному ядру, линия не грязная, а грязная и принадлежит другому ядру.

• В случае двух одновременных чтений обе линии идентичны, разблокированы и взаимозаменяемы.Не имеет значения, какую строку получит ядро ​​для последующих операций.
• в случае одновременной записи обе строки не синхронизированы, но взаимно невидимы.Хотя состояние гонки, которое это создает, является неудачным, оно все же приводит к разумному упорядочиванию памяти, как если бы все операции, происходящие в отброшенной строке, происходили раньше любых операций в очищенной строке.
• Если чтение и запись происходят одновременно, грязная линия невидима для ядра чтения.Однако чистая линия видна обоим ядрам и может привести к нарушению порядка памяти для записывающего устройства.будущие записи могут даже привести к блокировке обоих (потому что оба будут грязными).

Последний случай в значительной степени свидетельствует о том, что грязным линиям отдается предпочтение перед чистыми.Это заставляет по крайней мере некоторый дополнительное оборудование для поиска грязных линий в первую очередь и чистых линий только в том случае, если грязные линии не обнаружены.Итак, теперь у нас есть новая реализация параллельного кэша:

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

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

Теперь все, о чем нам нужно думать, — это предоставить инструмент для синхронизации приложений.Я бы, вероятно, создал инструмент, который просто очищает строку, если она грязная.Это просто вызовет то же оборудование, которое используется во время выселения, но пометит строку как чистую, а не недействительную.

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