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

 

) АССОЦИАТИВНОЕ ЗАПОМИНАЙ1ДЁЕ УСТрСЖСТВО, содержащее накопитель, регистр опроса, группу элементов ИЛИ, счетчикиi индикаторы результата поиска , элемент ИЛИ, дийамическнй триггер и блок управления, причем выхо элементов ИЖ группы подключены к первым входам счетчиков, выходы которых подключены к входам индикаторов результата поиска и входам элемента ИЛИ, выход которого подключен к входу динамического триггера, выход которого подключен к первым входам эле .ментов ИЛИ группы, выходы блока управления соединены с управляю1цими входами динамического триггера, накопителя и регистра опроса, один из выходов которого подключён к входу накопителя, о т л и ч а ю щ ее с я тем, что, с целью расширения области применения устройства за счет увеличения числа критериев поиска, в него введены коммутаторы и блоки срав цения, первые входы которых соедине- g ны с выходами накопителя, вторые вхо (Л ды подключены к другому выходу регистра опроса,а выходы соединены с входами коммутаторов, первые и вторые выходы которых подключены к вторым входам счетчиков и элементов ИЛИ группы. ,

СОЮЗ СОВЕТСКИХ

ОЮ

РЕСПУБЛИК аа <И) з

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕ к AelnaCNOMy, СЕИДВтВЛьстви (21) . 3621075/24-24 (22) 13.07.83 (46) 30. 1 1 . 84. Бюл. У 44 (72) В.Б.Матвеев (71) Казанский ордена Трудового Красного Знамени и.ордена Дружбы народов авиационный институт им. А.Н.Туполева (53) 681. 327(088.8) (56) 1. Авторское свидетельство СССР

9 780043, кл. G 11 С 15/00, 1980.

2. Авторское;свидетельство СССР

В 332502, кл. G 11 С 15/00, 1972 (прототип). (54)(57) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО, содержащее накопитель, регистр опроса, группу элементов ИЛИ, счетчики, индикаторы результата поиска, элемент ИЛИ, динамический триг гер и блок управления, причем выходы элементов ИЛИ группы подключены к первым входам счетчиков, выходы которых подключены к входам индикаторов результата поиска и входам элемента

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

4 11270

Изобретение относится к вычислительной технике и может быть исполь-. ,.зовано при построении запоминающих устройств.

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

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

Триггера, выход которого подключен к входам элементов ИЛИ (2 ).

Данное устройство позволяет производить поиск хранимых признаков, максимальное количество разрядов ко- З5 торых совпадает с разрядами признака опроса (поиск по минимуму расстояния

Хзмминга). Однако поиск по числовой близости в укаэанном устройстве не выполняется что сужает область его

Ф применения.

Цель изобретения - расширение о6ласти применения устройства за счет увеличенкя числа критериев поиска, в частности поиска по числовой бли- .i

45 з ости е

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

ИЛИ, выход которого подключен к вхо

2 ду динамического триггера, выход Kð торого подключен z первым входам элементов KIH группы, выходы блока управления соединены с управляющими входами динамического триггера,- накопителя и регистра опроса, один из выходов которого подключен к входу накопителя, введены коммутаторы и блоки сравнения, первые входы которых соединены с выходами накопителя, вторые входы подключены к другому выходу регистра опроса, а выходы соединены с входами коммутаторов, первые и вторые выходы которых подI кпючены к вторым входам счетчиков и элементов ИЛИ группы, На фиг. 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 тактовых импульсов, элемент HE 36 и элемент

ИЛИ 37. На фиг. 4 отмечены также вычитающий вход 38 счетчика 32 и вход

39 сдвига регистра 34.

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

Перед ассоциативным поиском коммутаторы 4, счетчики 6, индикаторы 7

H динамический триггер 9 устанавливаются в начальное состояние.

112?008

Накопитель 1 представляет собой, например, ассоциативную матрицу, реа лизующую простой поиск по равенству.

Опрос накопителя 1 производится поразрядно, начиная со старшего и в.по- 5 . рядке убывания разрядных весов, причем на каждом разряде опрос повторяется столько pas, сколько составляет вес данного разряда., По сигналу .апуска на.входах 1? устанавливается единица в старший разряд регистра 34 (фиг. 4) и счет-. чика 32, в,остальные разряды которых устанавливаются нули. Далее на К-й разрядный срез накопителя 1 (и К и разряд регистра 2) поступают 2" сиг-налов опроса. Затем по сигналу обнуления счетчика 32 единица в регистре 34 сдвигается на один разряд в

7 сторону младших и через открытые элементы И 33 содержимое регистра

34 дублируется в счетчик 32, т.е. выбирается следующий разрядный срез и т.д.

В случае несовпадения текущего разряда некотдрого хранимого признаjxa и признака опроса на соответствующем выходе накопителя t и, соответственно,на входе 11 соответствующего блока 3 сравнения появляются сигналы несовпадения, повторяющиеся, как быпо сказано, столько раз, сколько составляет вес данного разряда.

Одновременно на вход 10 блоков 3 сравнения подается значение данного разряда признака опроса. При этом сигналы на входе 11 дублируются на выходе 12 блока 3 сравнения, если данный разряд данного хранимого признака больше одноименного разряда

40 признака опроса, или на выходе 13— . если меньше..

Если хранимый признак в целом больше признака опроса, то на выходе

14 .<оммутатора 4 дублируются сигналы

45 на входе 12, а на выходе 15 .— все сигналы на входе 13; если меньше, то наоборот.

Сигналы с выхода 14 коммутатора 4 поступают на один из входов (например, суммирующий) соответствующего

50 счетчика 6, а с выхода 15 через элемент ИЛИ 5 — на другой вход соответ ственно вычитающий) счетчика 6.

Таким образом, после окончания опроса накопителя 1 в каждом счетчике 6 оказывается записано число, равное модулю разности между соответствующим хранимым признаком и призна" ком опроса.

После того, как ассоциативный опрос накопителя 1 закончен, выявляются счетчики (или один счетчик) 6 с минимальным, например, записанным кодом. Для этого запускается динамический триггер 9, который генерирует последовательность импульсов до тех пор, пока не произойдет обнуление хотя бы одного из счетчиков 6.

Сигналы обнуления, счетчиков 6 фиксируются в соответствующих индикаторах ?, отмечая выбранные хранимые признаки, и через элемент ИЛИ 8 выключают динамический триггер 9, прекращая генерируемую им последовательность.

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

Следует отметить, что, занося в исходное состоян. е различные значения в счетчики 6, меняя местами суммирующие и вычитающие. входы счетчиков, а также упрощая схему(используя более простые коммутаторы 4), можно . реализовать в устройстве поиск храни-, мых признаков, наиболее удаленных от признака опроса, и более простые виды поиска (поиск ближайщего большего, меньшего и т.д.).

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

1127008

Фиг. 1

Фиг. 2

1127008

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

Редактор М. Келемеш Техред Т.Дубинчак КоРРектоР О.Тигор

Закаэ 8747/40 Тираж 574 Подписное .ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Филиал ППП "Патент", r.Óæãoðîä, ул.Проектная, 4