Типы организации кэш-памяти

Принципы размещения блоков в кэш-памяти определяют три основных типа их организации:

Если каждый блок оперативной памяти имеет только одно фиксированное место, на котором он может появиться в кэш-памяти, то такая кэш-память называется кэш-памятью с прямым отображением (direct mapped). Это наиболее простая организация кэш-памяти, при которой, для отображения адресов блоков оперативной памяти на адреса кэш-памяти просто используются младшие разряды адреса блока. Таким образом, все блоки оперативной памяти, имеющие одинаковые младшие разряды в своем адресе, попадают в один блок кэш-памяти.

Если некоторый блок оперативной памяти может располагаться на любом месте кэш-памяти, то кэш-память называется полностью ассоциативной (fully associative).

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

Каждая запись в кэш-памяти об элементе данных включает в себя (рис. 6.1):

значение элемента данных;

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

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

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

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

Рис. 6.3. Ассоциативный поиск в кэш-памяти со случайным отображением

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

При совпадении адреса элемента данных из запроса к памяти i-го уровня иерархии подсистемы памяти с одним из адресов в памяти этого уровня иерархии подсистемы памяти, фиксируется попадание, и требуемый элемент данных выдается из памяти i-го уровня иерархии подсистемы памяти в память (i-1)-го уровня иерархии или источнику запроса, если это был верхний уровень иерархии подсистемы памяти.

При несовпадении фиксируется промах и выполняется обращение в (i-1)-й уровень иерархии или оперативную память, если в подсистеме памяти только один уровень кэш-памяти.

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

Каждый уровень иерархии кэш-памяти с детерминированным (прямым) отображением разделен на блоки (строки), каждый из которых предназначен для хранения одной записи об одном элементе данных и имеет свой номер. Между номерами блоков (строк) уровня иерархии кэш-памяти и адресами оперативной памяти устанавливается соответствие «один ко многим»: одному номеру строки соответствует несколько (обычно достаточно много) адресов оперативной памяти. В качестве отображающей функции может использоваться простое выделение части младших разрядов из адреса оперативной памяти, которые интерпретируются как номер строки кэш-памяти. Например, пусть в первом уровне иерархии кэш-памяти может храниться 64К блоков (К=1024), то есть, это уровень иерархии кэш-памяти имеет 65536 блоков (строк), с номерами 0 до 65535. Тогда любой адрес оперативной памяти может быть отображен на адрес уровня кэш-памяти простым отделением младших 16 двоичных разрядов. В действительности блок в памяти уровня кэш-памяти обычно содержит несколько элементов данных.

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

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

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

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

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

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

При промахе данные копируются по любому свободному адресу из однозначно заданной группы. Если свободных адресов в группе нет, то выполняется вытеснение данных. Поскольку кандидатов на выгрузку несколько — все записи из данной группы — алгоритм замещения может учесть интенсивность обращений к данным и тем самым повысить вероятность попаданий в будущем. Таким образом, в данном способе комбинируется прямое отображение на группу и случайное отображение в пределах группы.

Хотя диапазон возможных организаций кэш-памяти очень широк в современных процессорах, как правило, используется n канальная множественно-ассоциативная кэш-память (n может принимать значения 2, 4, 8 и более). Значительно реже можно встретить кэш-память с прямым отображением.

Выбор размера блока

Размер блоков, пересылаемых между памятями соседних уровней иерархии подсистемы памяти, может изменяться в широких пределах, например, 32, 64, 128, 256 байт. Не существует закономерности в виде функциональной зависимости между эффективностью иерархической подсистемы памяти и размерами пересылаемых блоков. Интуитивно очевидно, что: очень маленький размер блока (например, равный запрашиваемым данным) будет вызывать повышенное количество обращений к более медленным памятям более низких уровней иерархии; большой размер блока также может вызывать повышенное количество обращений к более медленным памятям более низких уровней иерархии, если данные из этих блоков будут использоваться не эффективно.

В современных процессорах для высокопроизводительных персональных компьютеров размер блока для всех уровней иерархии равен 64 байтам.

В некоторых процессорах для мультипроцессорных систем фирм IBM, Intel размеры блоков могут быть и больше 64 байтов. Например, в процессорах линии POWER 7 (и последующих) данные между оперативной памятью и кэш-памятью последнего уровня передаются блоками 256 байт.