Кэширование. Множественно-ассоциативное отображение

Множественно-ассоциативное отображение

Технологии прямого и ассоциативного отображения могут использоваться со­вместно. В этом случае блоки кэша объединяются в множества, и каждый блок основной памяти может располагаться в любом из блоков определенного множе­ства. Причем вероятность конфликтов, являющихся одним из недостатков пря­мого отображения, значительно снижается. Такой кэш, получивший название множественно-ассоциативного, дешевле полностью ассоциативного кэша, по­скольку в нем уменьшена область ассоциативного поиска. Рассмотрим принцип множественно-ассоциативного отображения на примере кэша с 64 множествами по два блока в каждом (рис. 8.6). Блоки памяти 0,64,128,..., 4032 отображаются на множество 0 и могут занимать любую из двух позиций в этом множестве. На­личие 64 множеств блоков означает, что 6-разрядное поле множества в составе адреса слова определяет, какое множество кэша может содержать это слово. Поле тега адреса ассоциативным путем сравнивается с тегами двух блоков найденного множества, и если оно совпадет с одним из тегов, значит, соответствующий блок уже находится в кэше. Реализовать такой поиск очень просто.

Количество блоков во множестве задается в соответствии с требованиями кон­кретного компьютера. В случае основной памяти и кэша, показанных на рис. 8.6, для четырех блоков в множестве потребуется 5-разрядное поле множества, для восьми блоков — 4-разрядное и т. д. Граничное значение 128 блоков в множестве не требует поля множества и соответствует полностью ассоциативному кэшу с 12 те­говыми битами. Другое граничное значение — один блок в множестве — соответ­ствует методу прямого отображения. Кэш сkблоками во множестве называется k-канальным множественно-ассоциативным кэшем.

Для каждого блока в кэше должен храниться еще один управляющий бит, на­зываемый битом достоверности. Он указывает, содержит ли блок достоверные данные. Его не следует путать с упоминавшимся ранее битом изменения, указы­вающим, был ли блок модифицирован за то время, пока он находится в кэше. Бит модификации нужен только в тех системах, в которых не используется сквозная запись. При включении питания системы и при загрузке с диска в основную па­мять новой программы и данных все биты достоверности устанавливаются в 0. Пересылка данных между диском и основной памятью управляется механизмом прямого доступа к памяти ПДП (DMA). Обычно эти данные минуют кэш, что вызвано соображениями стоимости и производительности. Когда блок кэша в первый раз загружается из основной памяти, его бит достоверности устанавливается в 1. Ес­ли блок основной памяти обновляется из другого источника, минуя кэш, система проверяет, находится ли загружаемый блок в кэше. Если да, его бит достоверно­сти устанавливается в 0, чтобы в кэше не оказалосьустаревшихданных.

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

 

Кэширование. Алгоритмы замещения

Для использования алгоритма LRU контроллер кэша должен отслеживать об­ращения ко всем блокам кэша. Предположим, что ему нужно следить за обраще­ниями к блоку LRU из четырехблочного множества множественно-ассоциатив­ного кэша. Для каждого блока может использоваться 2-разрядный счетчик. При попадании в кэш счетчик соответствующего блока устанавливается в 0. Счетчи­ки, значения которых были больше значения данного счетчика, увеличиваются на 1. Когда в кэше не оказывается нужного блока, а в множестве еще есть место, счетчик нового блока устанавливается в 0, а значения других счетчиков увеличи­ваются на 1. Если же множество заполнено, блок, счетчик которого равен 3, уда­ляется, а на его место помещается новый блок. Значения остальных трех счетчи­ков увеличиваются на 1. Нетрудно убедиться, что при использовании такого ал­горитма значения счетчиков четырех блоков всегда будут разными.

Алгоритм LRU очень популярен. В большинстве случаев он работает прекрас­но, но иногда его применение может привести к снижению производительности, например, при обращении к последовательным элементам массива, который слишком велик и не помещается в кэше целиком. Для того чтобы повысить производительность алгоритма, можно вне­сти в него некоторую долю случайного выбора.

На практике используются и некоторые другие алгоритмы замещения. Прави­ло замены самого «старого» блока кажется наиболее логичным, но оно не прини­мает в расчет частоту обращений к хранящимся в кэше блокам. Поэтому оно не так эффективно, как алгоритм LRU. Самым простым решением является случай­ный выбор перезаписываемого блока, и, что интересно, практика показывает его эффективность.