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

Изобретение относитсл к вычислительной технике и может быть испольт /зовано при построении зaпo шнaюIциx устройств. Известно ассощ1ативное запоминающее устройство, содержащее наколитес регистр опроса, блок управления, группы элементой И, блоки местного управления, дополш:тельные накопители и блоки вывода результата. В этом устройстве осуществляется поиск в массиве чисел, ближайших к заданному Ci3. Недостатком известного устройства является повьшенная сложность, в частности большое количество межсловарных логических связей, Наиболее близким техническим решением к изобретению является ассоциативное запоминающее устройство, содержащее накопитель, регистр опроса, элементы ИЛИ, счетчики идетекто - ры по числу хранимых признаков, до. полнительный злемент ШШ, динамический триггер и блок управления, причем выходы элементов ИЛИ подключены к первым входам соответствуки их счет чиков, выходы которых подключены к входам детекторов и входам дополни тельного элемента ИШ, выход кбторого подключен к входу динамического триггера, выход которого подключен к входам элементов ИЛИ 2 J. Данное устройство позволяет произ водить поиск хранимых признаков, максимальное количество разрядов которых совпадает с разряда признака опроса (поиск по минимуму расстояния Хэмминга). Однако поиск по числовой близости в указанном устройстве не выполняется, что сужает область его применения. Цель изобретения - расширение области гфименения устройства за сче увеличения числа критериев поиска, в частности поиска по числовой бли- зости. Поставленная цель достигается тем что в ассоциативное запоминающее уст ройство, содержащее накопитель, регистр опроса, группу элементов ШШ, счетчики, индикаторы результата поис ка, элемент ИЛИ, динамический триггер и блок управления, причем выходы элементов ИЖ группы подключены к первым входам счетчиков, выходы кото рых подключены к входам индикаторов результата поиска и входам элемента ШШ, в.ыход которого подключен к вхо ду динамического триггера, выход ко торого подключен к первым входам элементов ШШ группы, выходы блока управления соединены с управляющими входами динаьмческого триггера, накопителя и регистра опроса, один из выходов которого подключен к входу накопителя, введены коммутаторы и блоки сравнения, первые входы которых соединены с выходами накопителя, вторые входы подключены к другому выходу регистра опроса, а выходы соединены с входами коммутаторов, первые и вторые выходы которых подютючены к вторым входам счетчиков и элементов ИЛИ группы.. На фиг. 1 показана структурная схема предлагаемого устройства; на фиг. 2, 3 и 4 - примеры выполнения соответственно блока сравнения, коммутатора и блока управления. Устройство содержит (фиг. 1) нако-, питель t, регистр 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 устанавливаются в начальное состоятше.

31

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

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

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

Если хранимый признак в целом больше признака опроса, то на выходе 14 коммутатора 4 дублируются сигналы на входе 12, а на выходе 15 - все сигналы на входе 13; если меньше, то наоборот.

Сигналы с выхода 14 коммутатора 4 поступают на один из входов (например, суммирующий) соответствующего счетчика 6, а с выхода 15 через элемент ИЛИ 5 - на другой вход соответ ственно вычитающий) счетчика 6.

27008л

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

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

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

прекращая генерируемую им последовательность.

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

5 реализа1щя блоков 3 сравнения и отпадает необходимость в наличии связи между накопителем 1 и регистром 2 опроса.

I Следует отметить, что, занося в

0 исходное состоян.1в различные значения в счетчики 6, меняя местами суммирующие и вычитаюи И.е. входы счетчиков, а также упрощая схему(используя более простые коммутаторы 4), можно

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

0

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

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

Фиг. 2

12 13