Вопрос 17. Ассоциативная память

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

В основе ассоциативной памяти (associative memory) лежит ассоциативная обработка.

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

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

Указание признаков содержимого памяти не обязательно подразумевает только выявление их полного наличия или отсутствия в отыскиваемых данных, может быть также задана степень совпадения или несовпадения этих признаков с признаками данных и более сложные зависимости, что позволяет реализовать достаточно сложные методы обращения к данным.

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

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

Типичная структура ассоциативного ЗУ (рис. 19) содержит запоминающий массив ЗМ, регистр ассоциативного признака РАП, регистр маски РМ, регистр информации РИ, блок сравнения БС, регистр совпадений РС и блок формирования результата ассоциативного обращения БР.

Рис. 19

ЗМ содержит N (n +1)-разрядных ячеек. Для указания занятости ячейки используется служебный n -й разряд (0 – ячейка свободна, 1 – в ячейке записано слово).

По входной информационной шине ШИ_ВХ в РАП поступает ассоциативный запрос (признак поиска), а в РМ – код маски поиска. Ассоциативный поиск производится только для тех разрядов РАП, которым соответствует 1 в РМ (незамаскированные разряды РАП). Блок сравнения БС состоит из N схем совпадения, которые используются для параллельного сравнения каждого бита всех хранимых слов с соответствующим битом признака поиска и выработки сигналов совпадения. В регистре совпадений РС каждой ячейке запоминающего массива соответствует один разряд. Для слов, в которых разряды совпадают с незамаскированными разрядами РАП, блок сравнения БС устанавливает 1 в соответствующих разрядах РС и 0 в остальных разрядах.

Значение j -го разряда в РС определяется следующим выражением

,

где РАП[ i ]. РМ[ i ] и ЗМ[ j, i ] – значения i -го разряда соответственно РАП, РМ и j- й ячейки ЗМ.

Блок формирования результата ассоциативного обращения БР формирует из слова, образовавшегося в РС, сигналы α ₀, α ₁, α ₂, соответствующие случаям:

α ₀ – отсутствие слов в ЗМ, удовлетворяющих ассоциативному признаку;

α ₁ – наличие одного слова в ЗМ, удовлетворяющего ассоциативному признаку;

α ₂ – наличие нескольких (более чем одного) слов в ЗМ, удовлетворяющих ассоциативному признаку.

Для этого БР реализует следующие логические функции:

;

;

.

Формирование содержимого РС и сигналов α ₀, α ₁, α ₂ по содержимому РАП, РМ и ЗМ называется операцией контроля ассоциации. Эта операция является составной частью операций чтения и записи.

При чтении:

1) производится контроль ассоциации по признаку поиска в РАП;

2) проверяются признаки α ₀, α ₁, α ₂. При α ₀ = 1 считывание не производится из-за отсутствия искомой информации, при α ₁ = 1 в РИ считывается найденное слово (слово, на которое указывает 1 в регистре совпадений), при α ₂ = 1 в РИ считывается слово из ячейки, имеющей наименьший номер среди ячеек, отмеченных 1 в РС. При этом соответствующий разряд в РС сбрасывается в 0. Повторяя эту операцию, можно последовательно считать все слова.

Запись производится в первую свободную ячейку. Для этого:

1) отыскиваются свободные ячейки. Для этого выполняется операция контроля ассоциации при РАП = ххх…х0 и РМ = 000…01. При этом свободные ячейки отмечаются 1 в РС;

2) для записи выбирается ячейка с наименьшим номером;

3) в выбранную ячейку записывается слово, поступившее в РИ с ШИВХ.

Для отыскания свободной ячейки могут использоваться служебные разряды, показывающие, как давно производилось обращение к данной ячейке. Свободной считается либо пустая ячейка, либо та, которая дольше всего не использовалась.

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

Для построения ассоциативной памяти необходимы ЗЭ, допускающие считывание без разрушения записанной в них информации. Это связано с тем, что при ассоциативном поиске считывание производится по всему ЗМ для всех незамаскированных разрядов и негде сохранять временно разрушаемую считыванием информацию.

Главное преимущество ассоциативных ЗУ определяется тем, что время поиска информации зависит только от числа разрядов в признаке поиска и скорости опроса разрядов и не зависит от числа ячеек в запоминающем массиве.

Различают два вида поиска информации в ассоциативных ЗУ:

· простой поиск;

· сложный поиск.

При простом поиске требуется полное совпадение всех разрядов признака поиска с одноименными разрядами слов, хранящихся в запоминающем массиве.

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

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

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

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

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