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

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

Иллюстрации

Показать все

Реферат

 

1п1 450 232

ОПИСАН И Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ бонз Оеийтскйй

Социалистических

Реелублнк (61) Зависимое от авт. свидетельства (22) Заявлено 12.06.73 (21) 1931423/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 15.11.74. Бюллетень ¹ 42

Дата опубликования описания 11.06.75 (51) М. Кл. G 11с 15 00

Государственный комитет

Совета Министров СССР ло делам изобретений и OTKpbtTHH (53) УДК 681.327.6 (72) Авторы изобретения

Л. М. Метрик и А. Ю. Гурьев (71) Заявитель

Qp(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВ "" т ;т .т

Изобретение относится к области запоминающих устройств.

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

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

Известное устройство также обладает невысоким быстродействием.

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

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

На чертеже изображена блок-схема ассоци10 ативного запоминающего устройства.

Оно содержит матрицу 1 ассоциативных признаков, первичные индикаторы совпадения

2, схемы 3 фиксации режима по числу запоминающих ячеек матрицы 1, счетчики 4, осу15 ществляющие вычитание до нуля и суммирование, дополнительную матрицу 5 ассоциативных признаков, дополнительный регистр маски 6, дополнительный регистр опроса 7, вторичные индикаторы совпадения 8, триггер

20 знака 9, блок 10 формирования режима, блок управления 11, регистр опроса 12, регистр маски 13, вход 14 для записи кодовых последовательностей в регистр опроса, вход 15 установки режима, входы 16 схем фиксации

25 режима, входы 17, 18 счетчиков.

Входы 19 и 20 болка 10 формирования режима подключены соответственно к триггеру знака 9 и к первичным индикаторам совпадения 2, а выходы — ко входам 16 схем 3 фик30 сации режима и ко входу 17 счетчиков 4. Вхо450232

10

65 ды 18 счетчиков подсоединены к блоку управления 11, входы 21 — к выходам схем 3 фиксации режима, а выходы — к одним входам дополнительной матрицы 5 ассоциативных признаков, выходы которой связаны со входами индикаторов 8. Входы 22 схем 3 подключены к соответствующим выходам первичных индикаторов совпадения 2, Выходы регистра б соединены с другими входами матрицы 5, а входы — с выходами регистра 7, связанного с блоком управления 11. стройство раоотает следующим образом.

Ассоцнативныи поиск IIO запросу, представляющему сооой булевую функцию от входящих i3 него ассоциативных признаков, выполняетс51 за несколько циклов> причем числО циклов равно числу ассоциативных признаков, в: одящих в запрос, 11оисковые ооразы закодированы сжатой двоичной кодовой последовательностью, полученной посредством логического сложения двоичных кодовых последовательностей ассоциативных признаков, определяющих поисковые образы объектов поиска.

11еред началом каждого цикла ассоциативного поиска в массиве поисковых образов на вход триггера знака 9 записывается 0 или 1 в зависимости от того, входит ли в поисковый образ запроса ассоциативный признак или его инверсия, а на вход 15 установки режима блока 10 формирования режима подается признак первого или второго режима формирования ответа, выбираемого для запроса в целом.

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

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

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

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

При ассоциативном поиске на входы 14 регистра опроса 12 засылается двоичная кодовая последовательность, соответствующая одному из признаков, входящих в запрос, и одновременно в триггер знака 9 засылается признак наличия или отсутствия знака инверсии у соответствующего ассоциативного признака.

Признаки опроса из регистра опроса 12 через регистр маски 13 подаются на входы матрицы 1 ассоциативных признаков, причем маскируются те разряды, в которых в признаке опроса записаны нули.

Если ассоциативный признак входит в поисковый образ без знака инверсии, то выдается импульс на входы 18 тех счетчиков 4, которым соответствуют возбужденные индикаторы совпадения 2, и содержимое счетчиков увеличивается на единицу. Затем в регистр, опроса 12 засылается кодовая последовательность очередного ассоциативного признака, входящего в текущий запрос, и цикл ассоциативного поиска повторяется.

Таким образом, в результате, полного цикла ассоциативного поиска в каждом счетчике 4 устанавливается некоторое число.

Рассмотрим режим извлечения многозначного ответа после окончания цикла ассоциативного поиска по заданному запросу.

Содержимое счетчиков 4 переписывается в дополнительную матрицу 5 ассоциативных признаков, после чего с помощью блока управления 11, дополнительного регистра опроса 7, дополнительного регистра маски 6 и вторичных индикаторов совпадения 8 может быть выполнен ассоциативный поиск уже в массиве результатов ассоциативного поиска в заданном диапазоне допустимых значений результата с использованием одного из известных алгоритмов упорядоченной выборки.

Предмет изобретения

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

Составитель В. Рудаков

Техред О. Гуменюк

Корректор Л Орлова

Редактор Б. Капкина

Заказ 1328/20 Изд. Ко 1238 Тираж 591 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, Ж-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2 тельный регистр маски, выходы которого подключены к другим входам дополнительной матрицы ассоциативных признаков, а входы — к выходам введенного в устройство дополнительного регистра опроса, подключенного к блоку управления.