Ассоциативная память

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

1) поиск максимального или минимального числа в ЗУ;

2) поиск слов, заключенных в определенные границы;

3) поиск слов, ближайших к ассоциативному признаку, как с большей, так и с меньшей стороны и т.д.

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

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

По входной ШD в регистр ассоциативного признака RGП поступает n-разрядный признак, а в регистр маски RGМ – код маски поиска. При этом n-ый разряд регистра RGМ устанавливается в 0. Ассоциативный поиск производится лишь по тем разрядам признака, которым соответствует «1» в регистре маски, то есть по так называемым незамаскированным разрядам RGМ. Таким образом, задавая код маски М, можно произвольно выбирать те разряды признака, по которым ведется поиск.

Для слов из ЗМ, в которых все цифры совпали с незамаскированными разрядами RGП, комбинированная схема КС 1 устанавливает «1» в соответствующие разряды регистра совпадения RGC. Таким образом, если произошло совпадение цифры j-го слова с незамаскируемыми разрядами признака, то в j-ом разряде регистра RGC будет записана «1», в противном случае «0». Запись «1» в j-ом разряде RGC означает, что j-ое слово соответствует признаку, т.е. является тем словом, которое собственно и ищется в ЗМ. КС 1 реализует следующую систему М булевых уравнений:

_{n-1 ________ _________}

RGC(j) = /\ [RGП(i)~ЗМ(j,i) V RGM(i)] j = 0,N-1

ⁱ⁼⁰

~ - операция равнозначности;

/\- знак конъюнкции.

RGП(i)~ЗМ(j,i) = 1, если i-ые разряды слов совпадают.

Выходы регистра RGC соединены со входами КС2, которая формирует выходы α₀, α₁, α₂. Символ α₀=1, если во всех разрядах RGC находятся «Æ», что соответствует случаю отсутствия искомых слов в ЗМ.

Символ α₁=1, если имеется одно слово в ЗМ, удовлетворяющее ассоциативному поиску. Символ α₂=1, если таких слов больше одного. При α₁=1 найденное слово из ЗМ записывается в RGI, а оттуда в выходную шину ШД. При α₂=1 обычно читается слово из ячейки, имеющей наименьший номер среди ячеек, отмеченных «1»-цей в RGC.

При записи информации сначала находится свободная ячейка. Для этого выполняется операция ассоциативного поиска по признаку, имеющему во всех разрядах «0», а в регистре маски «0» записаны во всех разрядах, кроме младшего n-го разряда.

Таким образом, определяются те ячейки ЗМ, у которых в n-ом разряде записан «0», что означает незанятость ячейки. В свободную ячейку с наименьшим номером записывается слово из регистра информации RGI.

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