Запоминающие устройства с ассоциативной организацией

Ассоциативные ЗУ (АЗУ) относятся к ЗУ безадресного типа. В них доступ к ячейкам памяти осуществляется не по адресу, а по ассоциативному признаку. В качестве ассоциативного признака (АП) используются содержимое ячейки или её части. АЗУ состоит из трех частей: 1) запоминающей части, которая организована в виде совокупности ячеек с номерами 0, 1, …, Е-1; 2) блока ассоциативного поиска (доступа), т.е. схемы ассоциативного селектора и 3) блока замещения слов, который используется для записи информации в условиях, когда все ячейки АЗУ заняты. Схема АЗУ представлена на рисунке 6.11.

Ячейки запоминающей части состоят из двух полей: поля ассоциативного признака АП и информационного поля ИП.

Поиск информации (т.е. доступ к ячейкам ИП) осуществляется по ассоциативному признаку АП, который подается на вход АП ассоциативного селектора, и ведется путем сравнения входного признака АП со всеми АП, которые хранятся в полях АП всех ячеек запоминающей части:

АП=АП_i, i=0, 1, …Е-1. (6.3)

Выбранной считается та (или те) ячейка (и), для которой (ых) совпали ассоциативные признаки в (6.3). Если совпадений нет ни для одной ячейки, то это означает отсутствие в АЗУ той информации, обращение к которой производится по данному АП.

Таким образом, схема селекции в АЗУ организована на основе схем сравнения, а не дешифраторов, как в ЗУ с адресной организацией.

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

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

Основной недостаток АЗУ – большие (колоссальные) затраты оборудования на реализацию ассоциативного селектора. В случае, если запоминающая часть устройства организована по принципу 2D, то сложность селектора определяется количеством схем сравнения: 2^k=E_АЗУ (количество которых совпадает с количеством ячеек устройства).

Сложность одной схемы сравнения m элементов сравнения (однобитных). Общая сложность селектора: N_2D=m2^k (6.4)

Пример: m=26, k=16, N_2D=26*2¹⁶

Как уменьшить сложность селектора? Использовать ЗУ типа 3D:

N_3D=m*2^k/2 (6.5)

В нашем примере: N_3D=26*2⁸, т.е. в 256 раз меньше (в общем случае в 2^k/2 раз меньше).

6.7 Организация кэш–памяти на основе ассоциативного запоминающего устройства (кэш с ассоциативной организацией)

В этом случае всё пространство ОП разделяется на блоки (строки кэша) размером Е_стр=2ⁿ, n<<m, которые принимаются за единицу обмена кэша с ОП. Пример: m=26, n=5 (строка длиной 32 байта).

Всё пространство кэш–памяти также разделяется на строки ёмкостью 2ⁿ. В результате адреса ячеек ОП и кэша разделяются на поля:

Пример: m=36, n=5, l=21, k=16, h=11.

Структура кэш с ассоциативной организацией типа 3D представлена на рисунке 6.12.

Если ассоциативный признак Р=Р’, то обращение осуществляется к выбранной по ‘да’ строке кэша. Выбор ячейки в строке осуществляется при помощи дешифратора DСВ (в примере В=1), т.е. по адресному принципу.

Если Р≠Р’, то производится замещение: адресуемый блок Р извлекается из ОП и переписывается в свободную или специально освобождённую строку кэша. Освобождение строки кэша осуществляется путём её переписи обратно в ОП по старому адресу Р.

Основной недостаток – большие затраты оборудования на селектор. Пример: m=26, n=5, l=21, k=16, h=11, N_сел=l*2^h=21*2¹¹=42K (K=2¹⁰) элементов сравнения.

В силу указанного недостатка кэш с чисто ассоциативной организацией обычно не применяется. С целью экономии оборудования используется более простая организация – кэш с наборно–ассоциативной организацией (архитектурой) (рисунок 6.13). В этом случае адрес А ячейки ОП делится на 3 поля: в третьем (старшем) поле G указывается номер группы строк (в нашем примере t=10). В группу объединяются две (четыре,...) строки.

Экономия оборудования достигается за счёт того, что ассоциативный поиск остаётся только в группе из r строк (в примере r = 2). Выбор же группы строк осуществляется по адресному принципу при помощи дешифратора DСР. Таким образом, количество схем сравнения уменьшается до r, т.е. до количества строк в группе, а разрядность схем сравнения уменьшается до t. В результате затраты оборудования на ассоциативный поиск сокращаются до величины: N_асс = rt (пример: r=2, t=10, N=20).

Кроме того, сокращается длина ячеек поля АП до t разрядов, что также экономит оборудование. Правда, появляется дополнительный дешифратор DСР с количеством входов 2^h’, где h’=h-log₂r (в примере h’=h-1=10). Количество строк в группе определяется уровнем мультипрограммирования: r = M.

Кэш с наборно–ассоциативной архитектурой широко используется в IBM PC. Другие особенности организации кэш–буфера в IBM PC. Двухуровневая организация кэша: кэш первого уровня встраивается в процессор (конструктивно), а кэш второго уровня – вне ЦП, причём кэш второго уровня имеет большую ёмкость, чем кэш первого уровня. Кэш первого уровня работает на более высокой частоте – частоте ЦП, а второго – на частоте интерфейса ЭВМ (например, PCI). Вторая особенность (начиная с процессора Pentium): внутренний кэш делится на две части по назначению – кэш команд и кэш данных (т.н. Гарвардская архитектура ЭВМ).

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