Хотя кэш и невидим для операционной системы, он взаимодействует с аппаратным обеспечением, связанным с памятью. Более того, многие из принципов, используемых в схемах виртуальной памяти, применимы также к кеш-памяти.
Обоснование
При выполнении каждого цикла команды процессор по крайней мере один раз обращается к памяти, чтобы произвести выборку команды. Часто это происходит повторно, причем возможны случаи нескольких повторных обращений, при которых извлекаются операнды и/или сохраняются результаты. Частота, с которой процессор исполняет команды, ограничена временем обращения к памяти. Годами это ограничение было существенной проблемой из-за постоянного несоответствия между скоростью процессора и скоростью доступа к основной памяти — скорость процессора возрастала быстрее, чем скорость доступа к памяти. Постоянно нужно было искать компромисс между скоростью, стоимостью и емкостью. В идеале основная память должна была бы производиться по той же технологии, что и регистры процессора, чтобы время цикла памяти было сравнимо со временем цикла процессора. Однако эта стратегия приводит к слишком большим затратам. Решением проблемы стало использование принципа локализации, при котором между процессором и основной памятью помещается память с небольшой емкостью и быстрым временем доступа, а именно — кэш.
Принципы работы кэша
Кэш предназначен для того, чтобы приблизить скорость доступа к памяти к максимально возможной, и в то же время обеспечить большой объем памяти по цене более дешевых типов полупроводниковой памяти. Эта концепция представлена на рис. 1.16. Итак, наряду с относительно большой и более медленной основной памятью у нас есть кэш, обладающий меньшей емкостью, но и меньшим временем доступа. В КЭШе хранится копия фрагмента основной памяти. Когда процессор пытается прочесть слово из памяти, выполняется проверка на наличие этого слова в КЭШе. Если оно там есть, слово передается процессору. Если же его там нет, в кэш считывается блок основной памяти, состоящий из слов с определенными адресами. Вследствие локализации обращений при считывании в кеш блока данных, содержащего одно из требуемых слов, последующие обращения к данным с высокой вероятностью тоже будут выполняться к словам из этого блока.
Рис. 1.16. Кэш и основная память
На рис. 1.17 показана структура основной памяти и КЭШа. Основная память состоит из 2" адресуемых слов, каждое из которых характеризуется своим уникальным re-битовым адресом. Предполагается, что вся память состоит из определенного количества блоков фиксированной длины, в каждый из которых входит К слов. Таким образом, всего имеется М =2"/К блоков. Кеш состоит из С слотов, по К слов в каждом. При этом количество слотов намного меньше количества блоков (С«йГ)4. Некоторое подмножество блоков основной памяти хранится в слотах кэша. Если нужно прочесть из памяти слово из какого-то блока, которого нет в кэше, то этот блок передается в один из слотов Кэша. Из-за того, что блоков больше, чем слотов, нельзя закрепить за каждым блоком свой слот. Поэтому каждый слот должен содержать дескриптор, идентифицирующий хранящийся в нем блок. В роли дескриптора обычно выступает число, состоящее из старших битов адреса, и по нему происходит обращение ко всем адресам, которые начинаются этой последовательностью битов.
Рассмотрим простой пример, в котором адреса состоят из шести битов, а дескрипторы — из двух. Дескриптор 01 указывает на то, что в слоте находится блок, в который входят следующие адреса: 010000, 010001, 010010, 010011, 010100, 010101, 010110, 010111, 011000, 011001, 011010, 011011, 011100, 011101, 011110, 011111.
На рис. 1.18 показана блок-схема операции чтения слова из памяти. Процессор генерирует адрес слова, которое нужно прочесть. Если это слово хранится в КЭШе, оно передается процессору. В противном случае блок, содержащий это слово, загружается в кэш, и слово передается процессору после загрузки блока в кэш.
Рис. 1.17. Структура кэша и основной памяти
Рис. 1.18. Операция чтения из кэша
Внутреннее устройство кеша
В данной книге внутреннее устройство кэша подробно не рассматривается. В этом разделе кратко перечислены лишь основные его элементы. В дальнейшем читатель сможет убедиться, что при изучении устройства виртуальной памяти и дискового кэша мы имеем дело с похожими вопросами. Все их можно разбить на следующие категории:
- размер кэша;
- размер блока;
- функция отображения;
- алгоритм замещения;
- стратегия записи.
С такой характеристикой, как размер кэша, мы уже знакомы. Оказывается, что даже сравнительно маленький кэш может оказать значительное влияние на производительность компьютера. Другим важным параметром является размер блока, задающий величину порции данных, которая передается из основной памяти в кэш. При увеличении размера блока в соответствии с принципом локализации обращений растет результативность поиска, поскольку в кэш попадает больше полезных данных. Однако есть некое предельное значение, при превышении которого результативность поиска начинает уменьшаться. Это происходит тогда, когда вероятность использования вновь считанных данных становится меньше, чем вероятность повторного использования данных, которые необходимо удалить из кэша, чтобы освободить место для нового блока.
При считывании в кэш нового блока данных функция отображения определяет, какое место будет отведено для этого блока. Разрабатывая эту функцию, необходимо учитывать два фактора, накладывающих на нее определенные ограничения. Во-первых, при считывании блока, вероятно, он заменит другой блок в кэше. Хотелось бы сделать это таким образом, чтобы свести к минимуму вероятность того, что заменяемый блок понадобится в ближайшем будущем. Чем более гибкой является функция отображения, тем больше возможностей для разработки такого алгоритма замены, который бы позволил увеличить результативность поиска. Во-вторых, с увеличением гибкости функции отображения должны усложняться схемы, позволяющие определить наличие в кэше требуемой информации и обеспечить ее поиск.
При загрузке блоков в кэш в конце концов наступает момент, когда все слоты заполняются и новый блок нужно записывать на место, занятое каким-то другим блоком. Выбор этого блока осуществляется в соответствии с алгоритмом замещения, на который накладывает ограничения отображающая функция. При этом желательно было бы убрать именно тот блок, который, скорее всего, не понадобится в ближайшем будущем. Хотя достоверно определить его невозможно, достаточно эффективной стратегией является замена блока, к которому дольше всего не было обращений. Такая стратегия называется политикой недавнего использования блока (least-recently-used — LRU). Для определения используемости блоков необходим соответствующий аппаратно реализованный механизм.
Перед изменением содержимого слота кэша его старое содержимое необходимо записать в основную память. Случаи, когда нужно выполнять операции записи, определяются стратегией записи. Одним из предельных случаев является такой, когда запись производится при каждом обновлении блока. В другом случае запись производится только при замене данного блока новым. Такая стратегия сводит к минимуму количество операций записи в память, но при этом в блоках основной памяти содержится устаревшая информация, что может привести к ошибкам при многопроцессорной работе, а также при прямом доступе к памяти со стороны модулей ввода-вывода.
