Организация и функционирование кэш-памяти

Как уже отмечалось, кэш-память строится на базе быстродействующих микросхем статической памяти SRAM. В процессе работы машины в буферную кэш-память копируются те участки ОЗУ, к которым производится обращение со стороны процессора. В обще­принятой терминологии – производится отображение участков ОЗУ на кэш-память. Выигрыш достигается за счет ранее рассмотренного свойства локальнос­ти – если отобразить участок ОЗУ в более быстродействующую буферную кэш-память и переадресовать на нее все обращения в пределах скопированного участка, мож­но добиться существенного повышения производительности ВМ в целом.

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

Подсистема памяти, включающая ОЗУ и кэш-память, представляет собой следующую структуру. ОЗУ со­стоит из набора адресуемых слов (в количестве 2 в степени n), где каждое слово имеет уникальный n-разрядный ад­рес. При взаимодействии с кэш-памятью ОЗУ рассматривается как М блоков фик­сированной длины по К слов в каждом. Кэш-память состоит из С блоков аналогичного размера (блоки в кэш-памяти принято называть строками), причем их число значительно меньше числа блоков в основной памяти (С « М). При счи­тывании слова из какого-либо блока ОЗУ этот блок копируется в одну из строк кэш-памяти. Поскольку число блоков ОЗУ больше числа строк, отдельная строка не мо­жет быть выделена постоянно одному и тому же блоку ОЗУ. По этой причине каж­дой строке кэш-памяти соответствует тег (признак), содержащий сведения о том, копия какого блока ОЗУ в данный момент хранится в данной строке. В качестве тега обычно используется часть адреса ОЗУ.

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

Выбор емкости кэш-памяти – это всегда определенный компромисс. С одной сторо­ны, кэш-память должна быть достаточно мала, чтобы ее стоимостные показатели были близки к величине, характерной для ОЗУ. С другой – она должна быть достаточно большой, чтобы среднее время доступа в подсистеме, состоящей из ОЗУ и кэш-па­мяти, определялось временем доступа к кэш-памяти. В пользу уменьшения размера кэш-памяти имеется больше мотивировок. Так, чем вместительнее кэш-память, тем больше логических схем должно участвовать в ее адресации. Как следствие, микросхемы кэш-памяти повышенной емкости работают медленнее по сравнению с микросхема­ми меньшей емкости, даже если они выполнены по одной и той же технологии. Реальная эффективность использования кэш-памяти зависит от характера ре­шаемых задач, и невозможно заранее определить, какая емкость кэш-памяти будет дей­ствительно оптимальной. В общем случае, по мере увеличения емкости кэш-памяти вероятность промахов сначала существенно снижается, но при достижении определенного значения эффект сглаживается и становится не­существенным.

Размер строки является важным фактором, влияющим на эффективность использования кэш­-памяти. Когда в кэш-память помещается строка, вместе с требуемым словом туда попадают и соседние слова. По мере увеличения размера строки вероятность промахов сначала падает, так как в кэш-память, согласно принципу локальности, попадает все больше данных, которые понадобятся в ближайшее время. Однако вероятность промахов начинает расти, когда размер строки стано­вится излишне большим. Это объясняется тем, что, во-первых, большие размеры строки уменьшают общее количество строк, которые можно загрузить в кэш-память, а малое число строк приводит к необходимости частой их смены; во-вторых, по мере увеличения размера строки каждое дополнительное слово оказывается дальше от запрошенного, поэтому такое дополнительное слово менее вероятно понадобится в ближайшем будущем. Зависимость между размером строки и вероятностью промахов во многом оп­ределяется характеристиками конкретной исполняемой программы. На практике размер стро­ки обычно выбирают равным ширине шины данных, связывающей кэш-память с основной памятью.

Сущность способов отображения блока ОЗУ на кэш-память состоит в копиро­вании этого блока в какую-то строку кэш-памяти, после чего все обращения к бло­ку в ОЗУ должны переадресовываться на соответствующую строку кэш-памяти. Удачным может быть признан лишь такой способ отображения, который одновре­менно отвечает трем требованиям: обеспечивает быструю проверку кэш-памяти на наличие в ней копии блока основной памяти; обеспечивает быстрое преобразо­вание адреса блока ОЗУ в адрес строки кэш-памяти; реализует достижение первых двух требований наиболее экономными средствами.

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

Наиболее эффективным является алгоритм замещения на основе «наиболее дав­него использования» (Least Recently Used – LRU), при котором замещается та стро­ка кэш-памяти, к которой дольше всего не было обращения. Наиболее известны два способа аппаратурной реализации этого алгоритма. В первом из них с каждой строкой кэш-памяти ассоциируют счетчик. К содер­жимому всех счетчиков через определенные интервалы времени добавляется еди­ница. При обращении к строке ее счетчик обнуляется. Таким образом, наибольшее число будет в счетчике той строки, к которой дольше всего не было обращений, и эта строка замещается первой. Второй способ реализуется с помощью очереди, куда в порядке заполнения строк кэш-памяти заносятся ссылки на эти строки. При каждом обращении к строке ссыл­ка на нее перемещается в конец очереди. В итоге первой в очереди каждый раз оказывается ссылка на строку, к которой дольше всего не было обращений. Имен­но эта строка прежде всего и заменяется.

Другой возможный алгоритм замещения – алгоритм, работающий по принци­пу очереди типа «первый вошел, первый вышел» (First In First Out – FIFO). Здесь заменяется строка, дольше всего находившаяся в кэш-памяти. Алгоритм легко реализуется с помощью рассмотренной ранее очереди, с той лишь разницей, что после обраще­ния к строке положение соответствующей ссылки в очереди не меняется.

Еще один алгоритм – алгоритм замены «наименее часто использовавшейся строки» (Least Frequently Used – LFU). При реализации этого алгоритма каждая стро­ка связывается со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Первой заменяется та строка в кэш-памяти, счет­чик которой содержит наименьшее число.

Самым простым алгоритмом является реализация произвольного выбора строки для замены случайным образом. Однако этот алгоритм наименее эффективен.

Важную роль играют алгоритмы согласования содержимого кэш-памяти и ОЗУ. В процессе вычислений процессор может не только считывать имеющуюся информацию, но и записывать новую, обновляя тем самым содержимое кэш-памяти. С другой стороны, многие устройства ввода/вывода могут напрямую обмениваться инфор­мацией с ОЗУ. В обоих вариантах возникает ситуация, когда содер­жимое строки кэш-памяти и соответствующего блока ОЗУ перестают совпадать. В резуль­тате на связанное с ОЗУ устройство вывода может быть выдана «устаревшая» информация, поскольку все изменения в ней, сделанные процессо­ром, фиксируются только в кэш-памяти, а процессор будет использовать старое содержимое кэш-памяти вместо новых данных, загруженных в ОЗУ из устройства ввода.

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

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

В современных ВМ применяется многоуровневая иерархия кэш-памяти. Так простейшая двухуровневая система включает кэш-память первого уровня (L1), расположенную между процессором и кэш-памятью второго уровня (L2), которая в свою очередь расположена между L1 и ОЗУ. При доступе к памяти процессор сначала обращается к кэш-памяти первого уровня. В слу­чае промаха производится обращение к кэш-памяти второго уровня. Если информа­ция отсутствует и в L2, выполняется обращение к ОЗУ и соответствующий блок зано­сится сначала в L2, а затем и в L1. Благодаря такой процедуре часто запрашиваемая информация может быть быстро восстановлена из кэш-памяти второго уровня. Потенциальная экономия за счет применения L2 зависит от вероятности попа­даний как в L1, так и в L2. В целом практическое использование кэш­-памяти второго уровня существенно повышает производительность работы ВМ. Для ускорения обмена информацией процессора с кэш­-памятью второго уровня их часто соединяют специальной шиной, так называемой шиной заднего плана, в отличие от шины переднего плана, связывающую процессор с ОЗУ. Дальнейшее увеличение эффективности работы системы памяти достигается введением кэш-памяти третьего (L3) и даже четвертого (L4) уровней. Характер взаимо­действия очередного уровня с предшествующим аналогичен описанному для L1 и L2.

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

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