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

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

Иллюстрации

Показать все

Реферат

 

Сеоз Советских

Се (11) 608198

К А®ТОУСКОММ СВИДВТВДЬСТВУ (61) Дополнительное к авт. свид-ву—

2 (51) М. Кл, 11 С 11/О< (22) Заявлеио25.06.74 (21) 2037964/18-24 с присоединением заявки № (23) Приоритет (43) Опубликовано 25.05.78.Бюллетень № 19

Гаауда стаащей каматат

Соаата Макаатраа СССР аа делам азааратеаат в аткрмтка (53) УДК681,т>7 (088.8) (45) Дата опубликования описания 1, ® 1а (У2) Авт орьт изобретения

А. Ю. Гурьев и. Л. М. Метрттк (71) Заявитель (54) ACCOUHATHBHOE ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО

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

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

И н входу блока счетчика(11..

Однако увеличение длины кода поисковых образов влечет за собой увеличение разрядности матрицы ассоциативных признаков.

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

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

Целью изобретения является повышение быстродействия устройства.

Это достигается тем, что устройство содержит элементы ИЛИ, входы которых подключены к выходам элементов И, а выходы — ко

10 входам счетчиков, н дополнительные элементы И, одни входы которых соединены соответственно с выходами дешнфратора адреса, другие — с выходами блока управления, а выходы дополнительных элементов И подключены к адресным входам накопителя.

)3

При этом элементы И и дополнительные элементы И объединены соответственно в группы в количестве, определяемом коэффициентом объединения строк в накопителе, представляющем матрицу ассоциативныМ признаков.

На чертеже изображена структурная схема предложенного АЗУ.

Устройство содержит накопитель l. представляющий матрицу ассоциативных признаков,. регистр числа 2, регистр маски 3, элемен25 ты И 4, элементы ИЛИ 5, счетчики 6, дешнф608198

1Е

29

Формула изобретения ратор адреса 7, дополнительные элементы И 8, блок управления 9.

Блок 9 имеет выходы 10 синхрончзации выбора строк прн записи и выходы 1! синхрониацни выбора строк при ассоциативном поиске.

Входы элементов ИЛИ 5 подключены к выходам элементов И 4, а выходы — ко входам счетчиков 6.

Одни входы элементов И 8 соединены соответственно с выходами дешифратора 7, другие — с выходами блока 9, à выходы элементов И 8 подключены к адресным входам накопителя 1, Ассоциативное запоминающее устройство работает в режимах записи-считывания и ассоциативного поиска, Режим записи-считывания. Если принять разрядность накопителя l, равной m, а коэф; фнциейт объединения строк равным К, то за- пись одного mK — разрядного слова будет выполняться в течение К циклов записи поочередно в каждую из Km — разрядных строк накопителя l. В течение К циклов на входе дешифрато1ьв адреса 7 держится иод адреса слова и, следовательно, на соответствующий выход дешифратора подается сигнал выборки, поступающий на одни елоды К элементов И 8„соответствующих К строкам выбранного mK — разрядного слова.

В течение каждого иэ К циклов из блока управления 9 с выходов 10 синхронизации выбора строк (число которых равно К) последовательно с l-го по К-й подается сигнал синхронизации выбора строк, поступающий на другие входы К элементов И 8. На регистре числа.

2 в каждом из К циклов устанавливается соответствующий m-разрядный код. Таким образом, за К циклов производится запись аК-разрядного слова в Km-разрядных строк накопителя 1.

Считывание mK-разрядного слова производится также за К циклов, причем в каждом из К циклов в регистр числа считывается со ответствующий m-разрядный код.

Режим ассоциативного поиска. Рассмотрим два варианта ассоциативного поиска, определяемь1е методом кодирования поисковых образов, В первом варианте предполагается, что каждый из К ассоциативных признаков, составляющих поисковый образ, закодирован m-разрядным комбинационным кодом и, следовательно, при записи код каждого ассоциативного признака заносится в одну из Km-разрядных строк, составляющих одно mK,-разрядное слово, Тогда выходы каждой группы из К строк должны быть объединены таким образом, чтобы очи подсоединялись ко входу общего для этой группы строк счетчика 6.

С этой целью с выходов 11 блока управления 9 выдается сигнал на входы элементов

И 4, который обесчечивает выдачу сигналов с выходов i-строк, объединенных в группу, на вход соответствующей этой группе элемента

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

Результат. ассоциативного поиска считается положительным для тех mK-разрядных слов, для которых счетчик 6, соответствующий каждому из этих слов, устанавливается в результате поиска в нуль при условии, что перед началом ассоциативного поиска в каждый нз вычитающих счетчиков 6 было записано пороговое значение, соответствующее числу сравнений ассоциативных признаков, которое принимается достаточным для того, чтобы считать поисковый образ запроса соответствующем поисковому образу объекта.

Во втором варианте предполагается, что число ассоциативных признаков в системе не превышает mK и, следовательно, каждому признаку, ставится в соответствие один разряд в гпК-разрядном слове, Это определяет следующий алгоритм выполнения ассоциативного поиска. Соответствующее. поисковому образу запроса mK-разрядное слово разбивается на Ктразрядных полей, последовательно заносимых в каждом из К циклов в регистр числа 2, который может быть маскирован с помощью регистра маски 3, причем в i-м цикле (1 (i (К) производится сравнение только с i-ми строками каждой группы иэ К строк. Выделение 1-строк в группах обеспечивается подачей сигнала с

i-ro выхода 11 блока управления 9 на входы

i-х элементов И 4. В остальном процесс поиска аналогичен описанному.

Таким образом, описанное устройство обеспечивает существенное увеличение быстродействия АЗУ.

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

ИЛИ, входы которых подключены к выходам, элементов И, а выходы — ко входам счетчиков, и дополнительные элементы И, одни.входы которых соединены соответственно с выходами дешифратора адреса, другие — с выходами блока управления, а выходы дополнительных элементов И подключены к адресным входам накопителя.

Источники информации, принятые во внимание при экспертизе:

1. Авторское свидетельство СССР № 4.10462, М. кл; G !1 С 15)00, !972.

2. Авторское свидетельство СССР № 470862, М, кл. б 11 С 15 00, 1974.

Редактор Л. Народная

Заказ 2807 35

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

Техред О. Луговая Корректор К. Гаксич

Твраж 7! 7 Поди исиое

ЫНИИПИ Государственного .комитета Совета ..ииистров СССР но делам изобретений и открытий!!3035, Мос. за. Ж-35, Раун ская наб. д. 4/5

Филиал ППП <Патентэ, г. Ужгород, ул. Т!роектная. 4