Ассоциативное запоминающее устройство Советский патент 1978 года по МПК G11C15/00 

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

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

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

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

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

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

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

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

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

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

Устройство содержит накопитель 1. представляющий матрицу ассоциативных признаков, регистр числа 2, регистр маски 3, элсменты И 4, элементы ИЛИ 5, счетчики б, депгифpatop адреса 7, дополнительные элементы И 8, блок управления 9.

Блок 9 имеет выходы 10 синхрончзации выбора строк при записи и выходы 1 синхронизации выбора строк при ассоциативном поиске. Входы элементов ИЛИ 5 подключены к выходам элементов И 4, а выходы - ко входам счетчиков 6.

Одни входы элементов И 8 соединены соответственно с выходами дешифратора 7, другне - с выходами блока 9, а выходы элементов И 8 подключены к адресным входам накопителя I.

Ассоциативное запоминающее устройство работает в режима1Х записи-считывания и ассоцнативнога поиска..

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

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

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

Режим ассоциативного поиска. Рассмотрим два варианта ассоциативного поиска, определяемые методом кодирования поисковых образов.

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

С этой целью с выходов 11 блока управления 9 выдается снгнал на входы элементов И 4, который обеспечивает выдачу сигналов с выходов i-строк, объединенных в группу, на вход соответствующей этой группе элемента ИЛИ 5 н, таким образом, обеспечнвает подклю. чение выходов всех стро«, входящих в группу, к соответствующому счетчику 6. Ассоциативный поиск выполняется для одного поискового образа запроса за количество циклов, соотнетствующее числу ассоцнативных признаков, сое тавляющнх поисковый образ запроса.

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

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

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

Формула изобретения

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

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

2.Авторское свидетельство СССРК 470862, М. кл. G II С 15/00, 1974.