Если одному адресу соответствует более одного действительного слота, то это означает, что при выполнении предыдущего поиска по одному и тому же адресу не использовался либо действительный слот, который должен был соответствовать адресу (возможно, потому что он не был проверен впервое место) или несколько недопустимых слотов использовались для хранения строки, которой вообще не было в кэше.
Без сомнения, это следует считать ошибкой.
Но если бы мы просто решили не исправлять ошибку (возможно, мы бы не стали использовать такое оборудование для лучшей реализации).) наиболее очевидный вариант - выбрать один из слотов для аннулирования.Затем он будет доступен для других строк кэша.
Что касается того, как выбрать, какую из них сделать недействительной, если одна из повторяющихся строк чистая, то она станет недействительной по сравнению с грязной строкой кэша.Если грязная строка больше, чем кеш и они не согласны , вам нужно исправить еще большую ошибку, но в любом случае ваш кеш не синхронизирован и, вероятно, не имеет значения, какой вы выберете.
Редактировать: вот как я мог бы реализовать аппаратное обеспечение, чтобы сделать это:
Во-первых, не имеет большого смысла начинать с допущением дубликатов, скорее мы 'Обойдусь с этим в подходящее время позже.Есть несколько возможностей того, что должно произойти при кэшировании новой строки.
- Строка уже находится в кеше, никаких действий не требуется
- Строка не находится в кеше, но доступны недопустимые слоты: поместите новую строку в один из доступныхslots
- Строка не находится в кэше, но нет доступных недопустимых слотов.Другая действительная строка должна быть удалена, и новая строка занимает ее место.
- Выбор кандидата на выселение имеет последствия для производительности.Чистые строки кэша могут быть выселены бесплатно, но при неправильном выборе это может привести к очередной ошибке в кэше в ближайшем будущем.Подумайте, не загрязнена ли вся строка кэша, кроме одной.Если исключена только чистая строка кэша, то много последовательных чтений, чередующихся между двумя адресами, вызовут пропадание кэша при каждом чтении.Аннулирование кэша входит в число двух сложных проблем в Comp Sci (другое - «именование вещей») и выходит за рамки этого точного вопроса.
Я бы, вероятно, реализовал поиск, который проверяет правильность слота для каждого из них.Затем другой блок выберет первый из этого списка и будет действовать по нему.
Теперь вернемся к вопросу.Каковы условия, при которых дубликаты могут попасть в кеш.Если доступ к памяти строго упорядочен, а реализация (как указано выше) верна, я не думаю, что дублирование вообще возможно.И поэтому нет необходимости проверять их.
Теперь давайте рассмотрим более неправдоподобный случай, когда один кэш распределяется между двумя ядрами процессора.Мы собираемся просто сделать простейшую вещь, которая может работать, и дублировать все, кроме самой кэш-памяти для каждого ядра.Таким образом, оборудование для поиска слотов является не общим.Для поддержки этого дополнительный бит на слот используется как мьютекс.поисковое оборудование не может использовать слот, заблокированный другим ядром.в частности,
- Если адрес находится в кеше, попробуйте заблокировать слот и вернуть этот слот.Если слот уже заблокирован, останавливается до тех пор, пока он не освободится.
- Если адрес отсутствует в кэше, найдите разблокированный слот, который недействителен или действителен, ноevictable.
в этом случае мы фактически можем оказаться в положении, когда два слота имеют один и тот же адрес.Если оба ядра попытаются выполнить запись по адресу, которого нет в кэше, они получат разные слоты, и появится дублирующаяся строка.Сначала давайте подумаем о том, что может произойти:
- Обе строки были прочитаны из основной памяти.Они будут иметь одинаковую ценность и оба будут чистыми.Правильно также выселить.
- Обе строки были записаны. Оба будут грязными, но, вероятно, не будут равны. Это условие состязания, которое должно было быть разрешено приложением путем выдачи ограждений памяти или некоторых других инструкций по упорядочению памяти. Мы не можем угадать, какой из них следует использовать, если бы не было кеша, условие гонки сохранялось бы в ОЗУ. Правильно также выселить.
- Одна строка была прочитана, а другая - записью. Запись грязная, но чтение чистое. Еще раз это условие гонки сохранялось бы в ОЗУ, если бы не было промежуточного кэша, но читатель мог увидеть другое значение. высвобождение чистой строки правильно с помощью ОЗУ, а также побочным эффектом всегда в пользу упорядочения чтения, а затем записи.
Итак, теперь мы знаем, что с этим делать, но где эта логика принадлежит. Сначала давайте подумаем о том, что может произойти, если мы ничего не сделаем. Последующий доступ к кэшу для одного и того же адреса на любом ядре может вернуть любую строку. Даже если ни одно ядро не выдает записи, чтение может продолжаться по-разному, чередуя два значения. Это разрушает все мыслимые представления об упорядочении памяти.
Одним из решений может быть просто сказать, что грязные строки принадлежат только одному ядру, линия не грязная, а грязные и , принадлежащие другому ядру.
- В случае двух одновременных чтений обе строки идентичны, разблокированы и взаимозаменяемы. Не имеет значения, какую строку получает ядро для последующих операций.
- в случае одновременной записи обе строки не синхронизированы, но взаимно невидимы. Хотя создаваемое условие состязания вызывает сожаление, оно все же приводит к разумному упорядочению памяти, как если бы все операции, выполняемые на удаленной строке, выполнялись до выполнения какой-либо операции на очищенной строке.
- Если чтение и запись происходят одновременно, грязная строка невидима для ядра чтения. Тем не менее, чистая строка видна обоим ядрам, и это может привести к тому, что порядок записи будет нарушен для записывающего. будущие записи могут даже вызвать блокировку обоих (потому что оба будут грязными).
Этот последний случай в значительной степени побуждает отдавать предпочтение грязным линиям, а не чистым. Это вынуждает по крайней мере некоторое дополнительное оборудование сначала искать грязные линии, а чистые - только если не было найдено грязных линий. Так что теперь у нас есть новая реализация параллельного кэша:
- Если адрес находится в кэше и является грязным и принадлежит запрашивающему ядру, используйте этот слот
- если адрес в кеше но чистый
- для чтения, просто используйте этот слот
- для записи, пометьте слот как грязный и используйте этот слот
- , если адрес отсутствует в кеше и имеются недопустимые слоты, используйте недопустимый слот
- если нет недопустимых слотов, выселите линию и используйте этот слот.
Мы приближаемся, в реализации все еще есть дыра. Что если оба ядра имеют доступ к одному и тому же адресу, но не одновременно . Самое простое, наверное, просто сказать, что грязные строки действительно невидимы для других ядер. В кеше, но грязный - то же самое, что вообще не быть в кеше.
Теперь все, о чем мы должны думать, - это предоставить инструмент для синхронизации приложений. Я бы, вероятно, сделал инструмент, который просто сбрасывает строку, если она грязная. Это просто вызвало бы то же оборудование, которое используется во время выселения, но помечает строку как чистую, а не как недействительную.
Чтобы сделать длинный пост коротким, идея состоит в том, чтобы иметь дело с дубликатами, не удаляя их, а удостоверяясь, что они не могут привести к дальнейшим проблемам с упорядочиванием памяти, и оставляя дедупликационную работу для приложения или возможного выселения.