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

СОЮЗ СОВЕТСКИХоапцншикнипРЕСПУБЛИК 09) (и)ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬ ИЕ ИЗОБРЕ му. спицвтвльстви ПИСА(21), Зб 21075/24-24 подключены к входам индикаторов (22) 13.07.83 зультата поиска и входам элемента (4 б) 30.11.84. Бюл, У 44 выход которого подключен к вхо- (72) В.Б.Матвеев ду динамического триггера, выход ко- (71) Казанский ордена ного Крас- тоРого подключен к пеРвым входам эленого Знамени и.ордена ы народов .ментов ИЛИ группы, выходы блока упавиационный институт и Н.Тупопева Равления соединены с управляющими (53) 681,327(088.8)входами динамического триггера, на- (56) 1. Авторское свид тво СССР . копителЯ и РегистРа опРоса, один из В 780043, кл, С 11 С 1 1980. выходов которого подключен к входунакопителя, о т л и ч а ю щ е е с я2. Авторское;свидетел во СССР тем, что, с целью расширения облас- В 332502, кл, С 11 С 15/00, 1972ти применения устройства за счет уве(прототип).личения числа критериев поиска, в него введены коммутаторы и блоки срав- (54)(57) АССОЦИАТИВНОЕ .ЗАПОМИНАЮЩЕЕ аления, первые входы которых соедине-УСТРОЙСТВО, содержащее накопитель,ны с выходами накопителя, вторые вхорегистр опроса, группу элементов ИЛИ,ды подключены к другому выходу ресчетчики, индикаторы результата поис- гистра опроса, а выходы соединены ка, элемент ИЛИ, дийамический триг- с входами коммутаторов, первые и вто. Ъвеввгер и блок управления, причем выходы рые выходы которых подключены к втоэлементов ИЛИ группы подключены к . рым входам счетчиков и .элементов ИЛИ первым входам счетчиков, выходы кото- . группы. рыхреИЛИ Трудо Дружб м. А. етельс5/00,ьст, зовано при построении запоминающихустройств.Известно ассоциативное запоминающее устройство, содержащее накопитеЛь,регистр опроса, блок управления,группы элементов И, блоки местногоуправления, дополнительные накопители и блоки вывода результата. В этом 16устройстве осуществляется поиск вмассиве чисел, ближайших к заданному 13Недостатком известного устройстваявляется повьппенная сложность, в 13частности большое количество межсловарных логических связей,Наиболее близким техническим решением к изобретению является ассоциативйое запоминающее устройство,содержащее накопитель, регистр опроса, элементы ИЛИ, счетчики и детекто-.ры по числу хранимых признаков, до.полнительный элемент ИЛИ, динамический триггер и блок управления, причем выходы элементов ИЛИ подключенык первым входам соответствующих счет.чиков, выходы которых подключены квходам детекторов и входам дополни-тельного элемента ИЛИ, выход кдторо"го подключен к входу динамическогоТриггера, выход которого подключенк входам элементов ИЛИ 1 2 .Данное устройство позволяет производить поиск хранимьпс признаков,максимальное количество разрядов ко- З 5торых совпадает с разрядами признакаопроса (поиск по минимуму расстоянияХэмминга), Однако поиск по числовойблизости в укаэанном устройстве невыполняется что сужает область его40УФприменения.Цель изобретения врасширение области применения устройства за счетувеличенкя числа критериев поиска,в частности поиска по числовой бли-45 зости.Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее накопитель, регистр опроса, группу элементов ИЛИ, О счетчики, индикаторы результата поис- ка, элемент ИЛИ, динамический триггер и блок управления, причем выходы элементов ИЛИ группы подключены к первым входам счетчиков, выходы котоэ рых подключены к входам индикаторов результата поиска и входам элемента ИЛИ, выход которого подключен к вхо 2ду динамйческого триггера, выход ко торого подключен к первым входам элементов ИЛИ группы, выходы блока управления соединены с управляющими входами динамического триггера, накопителя и регистра опроса, один из вьпсодов которого подключен к входу накопителя, введены коммутаторы и блоки сравнения, первые входы которых соединены с выходами накопителя, вторые входы подключены к другому выходу регистра опроса, а выходы соединены с входами коммутаторов, первые и вторые выходы которых подкпючены к вторым входам счетчиков и элементов ИЛИ группы,.На фиг, 1 показана структурная схема предлагаемого устройства; на фиг, 2, 3 .и 4 - примеры выполнения соответственно блока сравнения, коммутатора и блока управления. Устройство содержит (фиг. 1) нако-,питель 1, регистр 2 опроса, блоки 3сравнения, коммутаторы 4, группу элементов ИЛИ 5, счетчики 6, индикаторы7 результата поиска, элемент ИЛИ 8 идинамический триггер 9, Кроме того,на фиг, 1 отмечены первые 10 и вторы11 входы блоков 3 сравнения, первые12 и вторые 13 входы и первые 14 ивторые 15 выходы коммутаторов 4. Устройство также содержит блок Ж управления, входы 17 запуска. Блок 16 име-,ет вьпсоды 18-20.Блок 3 сравнения содержит (фиг.2)элементы И 21 и 22 и элемент НЕ 23.Коммутатор 4 содержит (фиг. 3)первый 24 и второй 25 триггеры, элементы И 26-29, элементы ИЛИ 30 и 31.Блок 16 управления содержит(фиг. 4) К-разрядный счетчик 32,группу элементов И 33, сдвиговый регистр 34, генератор 35 тактовых импульсов, элемент НЕ 36 и элементИЛИ 37. На фиг. 4 отмечены также вычитающий вход 38 счетчика 32 и вход39 сдвига регистра 34.С целью упрощения схемы на фиг.1не показаны цепи записи и считывания информации, выполнение которыхизвестно и несущественно для данногоизобретения.. Устройство работает следующим образом.Перед ассоциативным поиском коммутаторы 4, счетчики 6, индикаторы 7и динамический триггер 9 устанавливаются в начальное состояние,1127008 3Накопитель 1 представляет собой,например, ассоциативную матрицу, реализующую простой поиск по равенству.Опрос накопителя 1 производится поразрядно начиная со старшего и в.по. рядке убывания разрядных весов, причем на каждом разряде опрос повторяется столько раз, сколько составляетвес данного разряда.,По сигналу апуска на.входах 17устанавливается единица в старшийразряд регистра 34 (фиг, 4) и счет-,чика 32, в,остальные разряды которыхустанавливаются нули. Далее на К-йразрядный срез накопителя 1 (и К-йразряд регистра 2) поступают 2" сиг-налов опроса. Затем по сигналуобнуления счетчика 32 единица в регистре 34 сдвигается на один разряд в7сторону младших и через открытыеэлементы И 33 содержимое регистра34 дублируется в счетчик 32, т.е. выбирается следующий разрядный срези т.д.В случае несовпадения текущегоразряда некотдрого хранимого признака и признака опроса на соответствующем выходе накопителя 1 и, соответственно,на входе 11 соответствующего блока 3 сравнения появляютсясигналы несовпадения, повторяющиеся,как быпо сказано, столько раз, скопько составляет вес данного разряда,Одновременно на вход 10 блоков 3сравнения подается значение данногоразряда признака опроса. При этомсигналы на входе 11 дублируются навыходе 12 блока 3 сравнения, еслиданный разряд данного хранимого признака больше одноименного разряда40признака опроса, или на выходе 13 -. если меньшеЕсли хранимый признак в целомбольше признака опроса, то на выходе14 .оммутатора 4 дублируются сигналы45на входе 12, а на выходе 15 . - всесигналы на входе 13; если меньше, тонаоборот.Сигналы с выхода 14 коммутатора 4поступают на один из входов (например, суммирующий) соответствующего50счетчика 6, а с выхода 15 через элемент ИЛИ 5 - на другой вход соответственно вычитающий) счетчика 6. 1Таким образом, после окончания опроса накопителя 1 в каждом счетчике 6 оказывается записано число, равное модулю разности между соответствующим хранимым признаком и призна" ком опроса.После того, как ассоциативный опрос накопителя 1 закончен, выявляются счетчики (или один счетчик) 6 с минимальным, например, записанным кодом. Для этого запускается динамический триггер 9, который генерирует последовательность импульсов до тех пор, пока не произойдет обнуление хотя бы одного из счетчиков 6. Сигналы обнуления, счетчиков 6 фиксируются в соответствующих индикаторах , отмечая выбранные хранимыепризнаки, и через элемент ИЛИ 8 выключают динамический триггер 9,прекращая генерируемую им последовательность.В качестве накопителя 1 может быть использован любой накопитель, допускающий одновременное считывание всеходноименных разрядов разных слов(разрядного среза). В частности, может использоваться ортогональный накопитель, применяемый в некоторыхассоциативных процессорах и построенный на микросхемах оперативной памяти размерностью один разряд К слов или накопитель на последовательносоединенных регистрах; соответственно при этом изменится конкретнаяреализация блоков 3 сравнения и отпадает необходимость в наличии связимежду накопителем 1 и регистром 2опроса. Следует отметить, что, занося в исходное состоян.е различные значения в счетчики 6, меняя местами суммирующие и вычитающие. входы счетчиков, а также упрощая схему(используя более простые коммутаторы 4), можно реализовать в устройстве поиск храни-, мых признаков, наиболее удаленных от признака опроса, и более простые виды поиска (поиск ближайщего большего, меньшего и т.д.).Таким образом, -в предложенном устройстве выполняется поиск по числовой близости, т.е. область применения устройства расширена.1127008 574енного ко П 747/40 ТиражВНИИПИ Государстпо делам иэобр113035, Москва,сно к итета СС крытий