Вопрос 20. Кэш-память. Принципы кэширования памяти

Кэш-память предназначена для повышения быстродействия процесса обращения к основной памяти.

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

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

Известно, что 90% обращений в основную память производится в ограниченную область адресов. Эта область называется рабочим множеством, которое медленно перемещается в памяти по мере выполнения программы. Для рабочего множества можно сделать промежуточную память небольшого размера, а значит, более быструю, чем основная память.Уилкс назвал рассматриваемую буферную память подчиненной (slave memory). Позже распространение получил термин кэш-память (от английского слова cache –- убежище, тайник), поскольку такая память обычно скрыта от программиста в том смысле, что он не может ее адресовать и может даже вообще не знать о ее существовании, т. е. адресуемой области памяти для процессора кэш-память не добавляет. Кэш является дополнительным быстродействующим хранилищем копий блоков информации из основной памяти, вероятность обращения к которым в ближайшее время велика. Кэш не может хранить копию всей основной памяти, поскольку его объем во много раз меньше основной памяти. Он хранит только ограниченное количество блоков данных. Кроме того, кэшироваться может не вся память, доступная процессору. Впервые кэш-память появилась в машинах модели 85 семейства IBM 360.

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

Кэш-память состоит из (рис. 25):

· массива данных;

· справочника или каталога (cache directory);

· контроллера (устройства управления).

Рис. 25

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

ОП состоит из 2 ^m адресуемых слов, где каждое слово имеет уникальный m -разрядный адрес. При взаимодействии с кэшем эта память рассматривается как N_m блоков фиксированной длины по k слов в каждом N_m = 2 ^m / k. Кэш-память состоит из N_c блоков аналогичного размера. Блоки в кэш-памяти принято называть строками, причем их число значительно меньше числа блоков в основной памяти N_c «N_m. При считывании слова из какого-либо блока ОП этот блок копируется в одну из строк кэша. Поскольку число блоков ОП больше числа строк, отдельная строка не может быть выделена постоянно одному и тому же блоку ОП. С каждой строкой кэша связана информация об адресе скопированного в нее блока основной памяти и ее состоянии. Информация о том, какой именно блок основной памяти занимает данную строку называется тегом (tag) и хранится в связанной с данной строкой ячейке памяти тегов. В качестве тега обычно используется часть адреса ОП. Здесь же хранится и информация о состоянии строки. Строка может быть действительной (valid), если в ней в текущий момент времени хранится (присутствует) копия соответствующего блока основной памяти, или недействительной. Строка может достоверно отражать соответствующий блок основной памяти ил быть модифицированной (говорят строка грязная – dirty). Таким образом, кроме адресной части тега с каждой строкой кэша связаны биты биты признаков действительности (присутствия) V и модифицированности M данных. Память тегов представляет собой каталог или справочник кэш-памяти. В операциях обмена с основной памятью строка участвует целиком. Такой кэш называется несекторированным. Возможен вариант секторированного кэша, при котором одна строка содержит несколько смежных секторов, размер которых соответствует минимальной порции обмена данных кэша с основной памятью. При этом в записи каталога, соответствующей каждой строке, должны храниться биты действительности для каждого сектора данной строки. Секторирование позволяет экономить память, необходимую для хранения каталога при увеличении объема кэша, так как при этом увеличивается количество разрядов каждого элемента каталога, а не количество самих элементов (размер каталога).

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

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

Наиболее распространенными алгоритмами замещения являются следующие.

1. Наиболее эффективным является алгоритм замещения на основе наиболее давнего использования (LRU — Least Recently Used), при котором замещается та строка кэш-памяти, к которой дольше всего не было обращения.

Наиболее известны два способа аппаратурной реализации этого алгоритма.

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

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

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

3. Алгоритм замены наименее часто использовавшейся строки (LFU – Least Frequently Used). Заменяется та строка в кэш-памяти, к которой было меньше всего обращений. Аппаратная реализация: каждая строка связывается со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик которой содержит наименьшее число.

4. Простейший алгоритм – произвольный выбор строки для замены. Замещаемая строка выбирается случайным образом.

Среди известных в настоящее время систем с кэш-памятью наиболее часто используется алгоритм LRU.

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

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

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

Дата добавления: 2014-01-13