Принципы кэширования

Основная память компьютеров реализуется на относительно медленной динами­ческой памяти (DRAM), обращение к ней приводит к простою процессора – по­являются такты ожидания (wait states). Статическая память (SRAM), построен­ная, как и процессор, на триггерных ячейках, по своей природе способна догнать современные процессоры по быстродействию и сделать ненужными такты ожи­дания (или хотя бы сократить их количество). Разумным компромиссом для по­строения экономичных и производительных систем явился иерархический спо­соб организации оперативной памяти. Идея заключается в сочетании основной памяти большого объема на DRAM с относительно небольшой кэш-памятью на быстродействующих микросхемах SRAM.

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

При каждом обращении к памяти контроллер кэш-памяти по каталогу проверяет, есть ли действительная копия затребованных данных в кэше. Если она там есть, то это случай кэш-попадания (cache hit), и данные берутся из кэш-памяти. Если действительной копии там нет, это случай кэш-промаха (cache miss), и данные берутся из основной памяти. В соответствии с алгоритмом кэширования блок данных, считанный из основной памяти, при определенных условиях заместит один из блоков кэша. От интеллектуальности алгоритма замещения зависит про­цент попаданий и, следовательно, эффективность кэширования. Поиск блока в списке должен производиться достаточно быстро, чтобы «задумчивостью» в при­нятии решения не свести «на нет» выигрыш от применения быстродействующей памяти. Обращение к основной памяти может начинаться одновременно с поис­ком в каталоге, а в случае попадания – прерываться (архитектура Look aside). Это экономит время, но лишние обращения к основной памяти ведут к увеличе­нию энергопотребления. Другой вариант: обращение к внешней памяти начина­ется только после фиксации промаха (архитектура Look Through), при этом теря­ется, по крайней мере, один такт процессора, зато экономится энергия.

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

Информация о том, какой именно блок занимает данную строку (т.е. старшая часть адреса или номер страницы), и о ее состоянии называется тегом (tag) и хра­нится в связанной с данной строкой ячейке специальной памяти тегов (tag RAM). В операциях обмена с основной памятью обычно строка участвует целиком (несекторированный кэш), для процессоров 486 и выше длина строки совпадает с объ­емом данных, передаваемых за один пакетный цикл (для 486 – это 4х4=16 байт, для Pentium – 4х8=32 байт). Возможен и вариант секторированного (sectored) кэша, при котором одна строка содержит несколько смежных ячеек – секторов, размер которых соответствует минимальной порции обмена данных кэша с основ­ной памятью. При этом в записи каталога, соответствующей каждой строке, дол­жны храниться биты действительности для каждого сектора данной строки. Секторирование позволяет экономить память, необходимую для хранения каталога при увеличении объема кэша, поскольку большее количество бит каталога отводится под тег, и выгоднее использовать дополнительные биты действительности, чем увеличивать глубину индекса (количество элементов) каталога.

Строки кэша под отображение блока памяти выделяются при промахах операций чтения, в Р6 строки заполняются и при записи. Запись блока, не имеющего копии в кэше, производится в основную память (для повышения быстродействия запись может производиться через буфер отложенной записи). Поведение кэш-контрол­лера при операции записи в память, когда копия затребованной области находит­ся в некоторой строке кэша, определяется его алгоритмом, или политикой записи (Write Policy). Существует две основных политики записи данных из кэша в основную память: сквозная запись WT (Write Through) и обратная запись WB (Write Back).

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

Политика WB позволяет уменьшить количество операций записи на шине основ­ной памяти. Если блок памяти, в который должна производиться запись, отобра­жен в кэше, то физическая запись сначала будет произведена в эту действительную строку кэша, которая отмечается как грязная (dirty), или модифицированная, т.е. требующая выгрузки в основную память. Только после этой выгрузки (запи­си в основную память) строка станет чистой (clean), и ее можно будет использо­вать для кэширования других блоков без потери целостности данных. В основную память данные переписываются только целой строкой. Эта выгрузка контролле­ром может откладываться до наступления крайней необходимости (обращение к кэшированной памяти другим абонентом, замещение в кэше новыми данными) или выполняться в свободное время после модификации всей строки. Данный алгоритм сложнее в реализации, но существенно эффективнее, чем WT. Поддерж­ка системной платой кэширования с обратной записью требует обработки до­полнительных интерфейсных сигналов для выгрузки модифицированных строк в основную память, если к этой области производится обращение со стороны таких контроллеров шины, как другие процессоры, графические адаптеры, кон­троллеры дисков, сетевые адаптеры и т. п.

В зависимости от способа определения взаимного соответствия строки кэша и обла­сти основной памяти различают три архитектуры кэш-памяти: кэш прямого ото­бражения (direct-mapped cache), полностью ассоциативный кэш (fully associative cache) и их комбинация – частично или наборно-ассоциативный кэш (set-associative cache).