Как политика записи-недействительности работает с ассоциативными кэшами?

TL: DR: для неблокирующего кеша, использующего функцию write-invalidate, изменение его с прямого сопоставления на ассоциативное множество может повредить частоту совпадений, если записи не происходят очень редко, или означают, что вы вводите возможность необходимости блокировки.

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

В документе 1993 года, на который вы ссылаетесь, этот термин используется для обозначения чего-то другого, кроме современного механизма согласованности кеша, означающего < / а>. В статье:

Да, реальные кеши в наши дни в основном всегда ассоциативны по множеству; более сложная логика компаратора тегов стоит увеличения частоты совпадений для того же размера данных. Какой метод сопоставления кэша используется в Intel Core i7 процессор? есть кое-что общее, а не только x86. Современные примеры кэшей с прямым отображением включают кэш DRAM, когда часть постоянной памяти на платформе Intel работает в режиме памяти. Также многие процессоры серверного уровня от разных производителей поддерживают разделение на разделы L3, поэтому вы можете, например, выделить один путь для потока, который в основном будет вести себя как кэш с прямым отображением.

Политика записи для современных кэшей ЦП обычно такая: запись-распределение + выборка при записи + запрет записи до попадания; некоторые ISA предлагают такие методы, как специальные инструкции для обхода кеша для невременных хранилищ, которые не будут перечитаны в ближайшее время, чтобы избежать загрязнения кеша в таких случаях. Большинство рабочих нагрузок перезагружают свои хранилища с достаточной временной локальностью, поэтому запись-выделение - единственный разумный выбор, особенно когда кеши больше и / или более ассоциативны, поэтому они с большей вероятностью смогут зависнуть в строке до следующего чтения. или напишите.

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

Но есть ли польза от использования write-invalidate для ассоциативных кешей?

Похоже, что это не так.

Единственное преимущество, которое он имеет, заключается в том, что он не останавливает простой конвейер, в котором отсутствует буфер хранения (буфер записи в документе). Это позволяет писать параллельно с проверкой тегов, поэтому вы узнаете после изменения строки, нажали вы или нет. (Современные процессоры действительно используют буфер хранилища для отделить фиксацию хранилища до L1d от выполнения хранилища и скрыть задержку отсутствия сохранения. Даже у ЦП в порядке обычно есть буфер хранилища, чтобы обеспечить параллелизм RFO на уровне памяти (чтение для владения) . (например, ARM Cortex-A53 в телефонах).

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

Слепое написание случайным образом может привести к ситуации, когда попадание произойдет не так, как вы предполагали. Прогнозирование пути - это вещь (и может работать лучше, чем случайное), но обратная сторона неправильного предсказания для такой записи будет излишне недействительной строкой, а не просто небольшой дополнительной задержкой. Прогнозирование пути в современном кэше. Я не знаю, какого рода успешное предсказание пути обычно достигается. Думаю, не очень хорошо, в лучшем случае от 80 до 90%. Наверное, лучше потратить транзисторы на предсказание пути, потратить на что-то другое, на что-то менее отстойное, чем запись-недействительность! Буфер хранилища с переадресацией хранилища, вероятно, стоит дороже, но он намного лучше.

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

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

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

Вы не хотите победить это, снося линии, которым не нужно было умирать.

Кроме того, write-invalidate подразумевает сквозную запись даже для попаданий записи, потому что это может привести к потере данных, если строка когда-либо станет грязной. Но обратная запись также очень хороша в современных кэшах L1d, чтобы изолировать большие / более медленные кеши от пропускной способности записи. (Особенно, если нет частного L2 для каждого ядра, чтобы отдельно уменьшить общий трафик к общим кэшам.) Однако в семействе AMD Bulldozer был L1d со сквозной записью с небольшим буфером записи 4k между ним и L2 с обратной записью. Обычно это считалось неудачным экспериментом или слабым местом конструкции, и они отказались от него в пользу стандартного L1d с обратной записью и выделением памяти для Zen. При использовании политики сквозного кеширования для страниц.

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

• запись-выделить политику записи
• обратная запись (не сквозная запись). https://en.wikipedia.org/wiki/Cache_ (вычисления) #Writing_policies < / а>
• ассоциативный набор (огромные недостатки, которые могут быть только частично смягчены путем предсказания пути)
• буфер хранения, чтобы отделить промах от выполнения и обеспечить параллелизм памяти. (Не совсем несовместимо, но буфер хранилища делает его бессмысленным. Необходим для OoO exec и широко используется для упорядочивания)

Конечно, вам нужно поставить в очередь сквозную запись для L2 и, в конечном итоге, остановиться, когда он не успеет, так что вы просто добавляете сложность. Механизм сквозной записи в L2 также должен иметь дело с ожиданием, пока L2 получит исключительное право собственности на строку перед записью (MESI Исключительное или измененное состояние). Так что это просто неупорядоченный буфер хранилища.

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

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

Возможно, все еще можно выполнить эту работу: если доступ к кешу представляет собой обмен чтением + записью, который сохраняет предыдущее значение в буфере из одного слова (или независимо от максимального размера записи), у вас все еще есть все данные. Остановите все (включая обратную запись этой строки, чтобы вы не сделали неправильные данные глобально видимыми в согласованном кэше L2). Затем обменяйтесь обратно, дождитесь, пока старое состояние этой строки L0d действительно обратится к этому адресу, затем сохраните буфер tmp в L0d и обновите теги и биты обратной записи, чтобы отразить это хранилище. Таким образом, псевдонимы между ближайшими магазинами становятся более дорогостоящими и останавливают конвейер. Или, может быть, вы можете позволить инструкциям, не относящимся к памяти, продолжаться и останавливать выполнение только при следующей загрузке или сохранении. (Если у вас есть бюджет транзисторов, чтобы избежать срывов, вы, вероятно, можете просто использовать совершенно другую стратегию, например, иметь буфер хранения и нормальный L1d.)

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