Ассоциативный по множеству кэш

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

Рассмотрим пример организации 4-х входового кэш.

Кэш разбивается на 4 части. Для каждой части вводится определитель, по которому производится поиск данных (ассоциативный признак). Выделяется байт, который фиксирует обращение к блоку данных. Фиксируется активность каждого блока для выявления и удаления неактивного блока. Когда данные не обнаруживаются в кэш памяти, происходит обращение к ОЗУ, неактивный блок заменяется новым.

При обращении к 4-х входовому кэш наличие информации определяется одновременно в 4-х блоках.
При обращении к многовходовому кэшадрес делится на две части. Одна часть содержит поле индекса и выбирает строку кэш, вторая содержит поле признаков, которое сравнивается с ассоциативным признаком ячейки памяти, используемым при поиске информации.
Сегодня разработчики высокопроизводительных микропроцессоров часто предпочитают этот тип кэш. Это обусловлено тем, что обычно частично-ассоциативный кэш обеспечивает более высокую вероятность нахождения в нем данных по сравнению с прямоадресуемым (прямого отображения) кэш той же емкости. Когда прямоадресуемый кэш заполняется, возникают проблемы, куда положить очередную порцию запрошенных данных. В n-канальном частично-ассоциативном кэш (n-way set-associative) имеется до n мест, куда можно положить запрошенные данные. Для более ясного понимания ситуации полезно рассмотреть гипотетический пример, предложенный на одной из телеконференций Usenet.
Пусть вероятность попадания в прямоадресуемый кэш L2 составляет 80%, а в частично-ассоциативный кэш L1 - порядка 85-90%, скажем 87%. Пусть попаданию в кэш отвечает задержка 20 нс для прямоадресуемого кэша и 24 нс - для частично-ассоциативного кэша, а непопаданию в кэш - 100 нс. Тогда средние задержки будут составлять:

0,80 * 20 + 0,20 * 100 = 36 нс. (для прямоадресуемого кэш)

0,87 * 24 + 0,13 * 100 = 34 нс. (для частично-ассоциативного кэш).

Для управления работой кэш памяти используется конвейер данных. Работа конвейеров кэш-памяти данных тесно координирована. Например, команды загрузки могут выполнять проверку тегов и чтение данных в том же такте, что и преобразование адреса. Команды записи сразу же начинают проверку тегов, чтобы в случае необходимости как можно раньше инициировать заполнение требуемой строки из кэш-памяти второго уровня, но непосредственная запись данных в кэш задерживается до тех пор, пока сама команда записи не станет самой старой командой в общей очереди выполняемых команд и ей не будет позволено зафиксировать свой результат. Промах при обращении к кэш памяти данных первого уровня инициирует процесс заполнения строки из кэш памяти второго уровня. При выполнении команд загрузки одновременно с заполнением строки кэш-памяти данные могут поступать по цепям обхода в регистровый файл. При обнаружении промаха при обращении к кэш-памяти данных ее работа не блокируется, т.е. она может продолжать обслуживание следующих запросов.
Для обеспечения целостности данных в кэш-памяти большой емкости обычной практикой является использование кодов, исправляющих одиночные ошибки (ЕСС-кодов).
Любой внутренний запрос процессора на обращение к памяти направляется во внутренний кэш. Теги строк [кэш-памяти] сравниваются со старшими битами запрошенного физического адреса. Если адресуемая область представлена в строке кэш-памяти - случай попадания (Cache Hit), запрос на чтение обслуживается только кэш-памятью, не выходя на внешнюю шину. Запрос на запись модифицирует данную строку и в зависимости от политики записи на внешнюю шину выходит либо сразу (при сквозной записи), либо несколько позже при использовании алгоритма обратной записи.
В случае промаха (Cache Miss) запрос на запись направляется только на внешнюю шину, а запрос на чтение обслуживается сложнее. Если этот запрос относится к кэшируемой области памяти, выполняется цикл заполнения целой строки кэша. Данные читаются из оперативной памяти и помещаются в одну из строк набора кэша. Если затребованные данные не укладываются в одной строке, заполняется и соседняя.
Внутренний запрос на данные удовлетворяется сразу, как только затребованные данные считываются из ОЗУ - заполнение стоки до конца может происходить параллельно с обработкой полученных данных. Если имеется свободная строка (с нулевым битом достоверности), заполнена будет именно она и для нее установится бит достоверности. Если свободных строк в наборе нет, будет замещена строка, к которой дольше всех не было обращений. Выбор строки для замещения выполняется на основе анализа бит LRU (Least Recently Used) по алгоритму "псевдо-LRU". Эти биты модифицируются при каждом обращении к строке данного набора (кэш-попадании или замещении).Таким образом, выделение и замещение строк выполняется только для кэш-промахов чтения, при промахах записи заполнение строк не производится.... Кроме того, существует возможность их аннулирования - объявления недостоверными и очистки всей кэш-памяти. Управление заполнением кэш возможно и на аппаратном, и на программном уровнях.