Ассоциативные ЗУ

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

 

 

 

Рисунок 3.9.1- Принцип ассоциативного поиска информации

С целью ускорения поиска данных используется адресация по содержанию, которая осуществляется путем одновременного доступа ко всем ячейкам памяти. Сущность принципа адресации по содержанию заключается в следующем (см. рисунок 3.9.1). Имеется массив данных емкостью N слов. Требуется найти в массиве все слова, которые начинаются с символа "А" и кончаются символом "Н". В этом случае аргументом поиска (ключевым словом, компарандом) является слово А***Н, где значком * отмечены разряды, не влияющие на результат поиска. Запоминающий массив на аппаратном уровне строится таким образом, что бы на выходе ячеек памяти, содержимое которых совпадает со значением поступившего аргумента поиска, появлялся сигнал - указатель совпадений. В дальнейшем по выработанным сигналам выполняется выборка содержимого тех ячеек памяти, в которых произошло совпадение.

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

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

Каждая строка модуля памяти такого АЗУ содержит (см. рис. 3.9.2) регистр для хранения слова данных (как в обычных ОЗУ) и специальные комбинационные логические схемы для сравнения текущего содержимого регистра с ключевым словом, которое поступает одновременно на все ячейки. При поиске формируется сигнал чтения из всех ячеек строки АЗУ с одновременным сравнением прочитанного слова с ключевым словом (аргументом поиска). Сигнал опроса появится на выходе ячейки, содержимое которой совпадает с ключевым словом.

Рисунок 3.9.2- Устройство ячейки АЗУ

Рисунок 3.9.3- Структура АЗУ

 

При построении АЗУ с маскированием, в операции сравнения участвуют не все разряды ключевого слова, а только та их часть, которая активизируется управляющим вектором-маской. Ячейка памяти переводится в активное состояние, если соответствующий ей разряд маски единичный, в противном случае она в операции сравнения не участвует.

 

Аппаратная реализация ассоциативного поиска должна обеспечить, как минимум, следующие функции:

- обеспечивать запись исходных данных в модуль памяти;

- осуществлять операцию поиска элемента по некоторому ключевому слову;

- выполнять занесение ключевого слова в регистр компаранда и код маски в регистр маски;

- возвращать в исходное состояние память отклика (регистр признаков);

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

При выборке данных из АЗУ в регистр компаранда (см. рис. 3.9.3) вводится аргумент поиска, в регистр маски – код вектора управления. Содержимое всех разрядов регистра компаранда (если не применяется маска) параллельно поступают в ячейки всех строк модуля памяти АЗУ и выполняется операция сравнения. По окончании переходных процессов на выходах тех строк модуля памяти АЗУ, в которых произошло совпадение с заданным аргументом поиска, устанавливаются сигналы совпадения. Каждая ячейка модуля памяти связана с памятью отклика (регистром признаков) с помощью тегового разряда T_i.Перед началом работы все разряды регистра признаков устанавливаются в состояние “0”. По команде процессора “Сравнить” любая ячейка, содержащая слово, которое совпадает с компарандом, формирует сигнал, устанавливающий соответствующий разряд Т_i в состояние “1”. Эта информация является адресной для линейной выборки. В анализаторе многократных совпадений (АМС) выполняется приоритетный разбор теговых разрядов и по его результатам последовательное формирование сигналов для шифратора. В принципе сигналы с АМС можно подавать непосредственно на адресные шины модуля памяти АЗУ, что обеспечило бы доступ ко всем "откликнувшимся" ячейкам одновременно. Однако на практике модули памяти АЗУ изготовляются из микросхем с встроенными дешифраторами адреса. Это позволяет использовать АЗУ в режиме прямо адресуемой памяти, что необходимо для занесения исходного массива данных перед началом операции ассоциативного поиска.

Ввод данных в АЗУ выполняется после предварительного поиска в модуле памяти АЗУ свободных строк. С этой целью в каждой строке модуля памяти предусматривают специальный бит занятости, который устанавливается в единицу при вводе слова данных в АЗУ и обнуляется при выводе соответствующего слова.