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

I

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

Известны ассоциативные запоминающие устройства 1 и 2.

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

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

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

В этом устройстве реализуются Функции ассоциативного поиска по различным критериям больше, меньше,

10 равно

небольше, неменьше,

неравно .

Недостатком этого устройства является отсутствие возможности поиска информации по сложному запросу,пред15ставленному, например, в виде логической формы поисковых признаков (запрос состоит из поисковых признаков, соединенных между собой операциями пересечения и/или объединения), что

20 существенно сужает область применения устройства.

Цель изобретения - расширение области применения устройства за счет 39 увеличения числа используемых критериев поиска. Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее ассоциати ный накопитель, регистр признака опроса, регистр маски, дополнительный и основной сдвигающие регистры, регистр кодов занятости, регистр гра ниц чисел, блок извлечения много-;значного ответа, причем входы ассоциативного накопитеоя подключены к выходам регистра признака опроса, ре гистра маски и основного сдвигающего регистра, а выходы - к входам допрлн -тельного сдвигающего регистра, входы основного сдвигающего регистра соединены с выходами блока извлечения многозначного ответа, регистра границ чисел, регистра кодов занятое ти и дополнительного сдвигающего ре;; гистра ,а выходы - с входами регистров кода занятости и регистра границ чисел введены регистр сегментов информации, адресный накопитель, многофункциональный накопитель, буферный регистр и блок управления режимами, вход которого подключен к выходу регистра признака опрока, входы многофункционального накопителя подключены соответственно к одному из выходов блока управления режимами, к выходам адресного накопителя, буферного р§гистра и регистра сегментов информации, входы буферного регистра и регистра сегментов информации соединены с выходами основного сдвигающего регистра, входы адресного накопителя подключены к выходам регистра сегментов информации и другону выходу блока управления режимами, управляющие входы буферного регистра соединены с выходами регистра сегмен тов информации, выходы многофункционального накопителя подключены к входам блока извлечения многозначного ответа. При этом блок управления режимами целесообразно выполнить в виде блока содержащего буферный регистр, счетчи дешифратор, регистр числа, шифратор и регистр кодов операций, причем выход буферного регистра подключен к входу дешифратора и одному из входов счетчика,, одни из выходов дешифратора соединены с входами регистра кодов операций, другими входами счет чика и одними из входов регистре числа, другие входы которого подклю74чены к выходам счетчика и регистра кодов операций, а выход - к входу шифратора, выход которого, а также другой выход дешифратора являются выходами блока, входом которого является вход буферного регистра. На фиг. 1 изображена функциональная схема ассоциативного запоминающего устройства; на фиг. 2 - структурная схема многофункционального накопителя, на фиг. 3 и фиг. k показаны структурные схемы блока предварительной обработки информации и логической схемы. Ассоциативное запоминающее устройство (фиг. 1) содержит регистр 1 признака опро.са, регистр 2 маски, ассоциативный накопитель 3, выполненный из ячеек Ц памяти, дополнительный 5 и основной 6 сдвигакЯцие регистры, регистр 7 кодов занятостиj регистр 8 числа, регистр 9 сегментов информации, буферный регистр 10 границ чисел блок 11 управления режимами. Блок 11 содержит буферный регистр 12, дешифратор 13 счетчик Т, регистр 15 кодов операций, регистр 16 числа и шифратор 17. Кроме того, устройство содержит адресный накопитель 18, состоящий из регистров 19 многофункциональный накопитель 20, служащий для хранения и обработки информации и состоящий из логических ячеек 21, и блок 22 извлечения многозначного ответа. Многофункциональный накопитель 20 (фиг. 2) содержит блоки 23 предварительной обработки информации, каждый из которых (фиг. 3) состоит из дешифратора 2 и многофункционального модуля 25 УФМ-1А, описанного в З, и логические схемы 26, каждая из которых (фиг. k) состоит из триггера 27 и ячейки 28 двумерной вычислительной среды, описанной в f+lПредлагаемое устройство предназначено для сопоставления формализованных описаний документов и запросов в информационно-поисковых системах дескрипторного типа, а также для проведения многоаспектного поиска информации среды данных, представленных а табличном виде. Для поиска документов в документальных информационно-поисковых системах могут быть использованы запросы двух типов. Запрос первого типа состоит из поисковых признаков, соединенных

59

булевыми операциями пересечения (И)i дополнения (НЕ) и объединения (ИЛИ).

В процессе сопоставления запроса и описаний документов.каждый признак запроса сравнивается с признаками описаний документов.

Запрос второго типа представляет собой перечень поисковых признаков. В заготовке запроса указывается чис ло, которое определяет минимальное количество вхождений признаков запроса в описания документов. Релевантным по отношению к запросу данного типа является документ, в описании которого содержится не менее указанного числа признаков запроса.

Работа устройства осуществляется следующим образом.

При сопоставлении запросов с описаниями документов, последние хранят ся в накопителе 3. Единичные разряды регистра 7 указывают на занятые ячейки k памяти. Единичные разряды регистра 8 и регистра 9 указывают соответственно на начала признаков описа

.НИИ документов и на начала описаний документов.Единичные сигналы регистра 9 поступают на управляющие входы регистра 10 и делят последний на части, количество и размер которых определяется количеством и объемом описаний документов, записанных в накопителе 3Каждая часть регистра 10 представляет собой регистр сдвига с параллельной записью и последовательным считыванием информации.

Регистры 19, отмеченные единичными разрядами регистра 9 воспринимают информацию только с выходов шифраторё 17 блока 11.

Работа устройства на примереиспользования запросов первого типа.

Содержимое регистра 8 переписывается на регистр 6. В регистр 1 вводится первое машинное слово (число) запроса. Распознавая код начала запроса дешифратор 13 выдает сигнал, по которому осуществляется сброс состояния счетчика 1, регистров 15 и 16. Затем в регистр 1 вводится следующее машинное слово запроса. Если дешифратор 13 фиксирует в поступившем слове наличие кода открывающей скобки то на его выходе возника.ет сигнал который поступает на счетчик 14. При этом содержимое счетчика I увеличивается на единицу. Если в запросе имеется несколько подряд идущих откры76

вающих скобок, их количество записывается на счетчике k,

Если маш.инное слово запроса является машинным словом первого признака то он сравнивается с машинными словами, хранящимися в ячейках k памяти накопителя Зр отмеченными единичными разрядами регистра 6. Результаты сравнения машинных слов поступают на регистр 5- Содержимое регистров 5 и 6 сдвигается на один разряд.

В регистр 1 вводится следующее машинное слово запроса.

Если оно является продолжением признака запроса, то опять происходит его сравнение с машинными словами ячеек Ц памяти накопителя 3. отмеченными единичными разрядами регистра 6. Результаты сравнения поступа- ют на регистр 5 и корректируют содержимое последнего. Далее выполняется однотактный сдвиг информации регистров 5 и 6. Эти операции продолжаются для всех машинных слов первого признака запроса.

В результате сравнения первого признака запроса с признаками описаний документов единичные разряды регистра 5 указывают на те признаки описаний документов, которые удовлетворяют условиям поиска (больше, меньше

и т.д.).

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

Если дешифратор 13 распознает код операции связи, то по его выходу выдается сигнал, по которому на регистр 16 переписывается содержимое счетчика 14, регистра 15 и информация из дешифратора 13. Кроме того, информация из дешифратора 13 переписывается на регистр 15Содержимое регистра 16 поступает на шифратор 17. который преобразует поступившую информацию в код настройки для логических ячеек 21 .

Если дешифратор 13 распознает код конца запроса, то он выдает сигнал, по которому начинается параллельная обработка информации в накопителе 20.

Полученные в регистре 6 сигналы сравнения признака запроса с призна79нами, хранимыми в накопителе 3 пере писываются на регистр 10. В регистр сдвига, образованных на регистре 10, эти сигналы сдвигаются и переписываются на входы логических ячеек 2Ц отмеченных единичными разрядами регистра Э- На указанных логических ячейках 21 над поступившими с регистра 10 сигналами выполняется операция, определяемая кодом настройки, поступившим с шифратора 17 на соответствующие регистры 19. .Таким же образом выполняется срав нение последующих признаков запроса с признаками описаний документов. , В результате, в процессе сравнения на Логических ячейках 21 формиру ют частные результаты сравнения приз наков в соответствии с логической формой запроса. С помощью блока 22 выводятся номе ра документов, описания которых соот ветствуют запросу. Использование предлагаемого устройства в структуре ЭВМ ЕС-1050 позволяет сократить время поиска информации в 10 раз. При этом производительность машины на данных классах задач поиска возрастает не менее, чем на 6Q%. Формула изобретения 1. Ассоциативное запоминающее уст ройство, содержащее ассоциативный на копитель, регистр признака опроса, регистр маски, дополнительный и основной сдвигающие регистры, регистр кодов зайятости, регистр границ чисел, блок извлечения многозначного ответа, причем входы ассоциативного накопителя подключены к выходам регистра признака опроса, регистра маски и основного сдвигающего регист ра, а выходы - к входам дополнительного сдвигающего регистра, входы основного сдвигающего регистра соединены с выходами блока извлечения мно гозначного ответа, регистра границ чисел, регистра кодов занятости и до полнительного сдвигающего регистра, а выходы - с входами регистров кода занятости и регистра границ -чисел, отличающееся тем, что, с целью расширения области применения устройства за счет увеличения числа используемых критериев поиска, оно содержит регистр сегментов информации, адресный накопитель, многофункциональный накопитель, буферный регистр и блок управления режимами, вход которого подключен к выходу регистра признака опроса, входы многофункционального накопителя подключены соответственно к одному из выходов блока управления режимами, к выходам адресного накопителя, буферного регистра и регистра сегментов информации, входы буферного регистра и регистра сегментов информации соединены с выходами основного сдвигающего регистра., входы адресного накопителя подключены к выходам регистра сегментов информации и другому выходу блока управления режима ми, управляющие входы буферного регистра соединены с выходами регистра сегментов информации. 2. Устройство по п. 1, о т л и чающееся тем, что блок управления режимами содержит буферный регистр, счетчик, дешифратор, регистр числа, шифратор и регистр кодов операций, причем выход буферного регистра подключен к входу дешифратора и одному .из входов счетчика, одни из выходов дешифратора соединены с входами регистра кодов операций, другими входами счетчика - и одними из входов регистра числа, другие входы которого подключены к выходам счетчика и регистра кодов операций, а выход - к входу шифратора, выход которого, а также другой выход дешифратора являются выходами блока, входом которого является вход буферного регистра. Источники информации, принятые во внимание при экспертизе 1.Заявка Франции N2216645 кл. G 11 С 15/00, опублик. 197. 2.Авторское свидетельство СССР tf 533989. кл. G 11 С 15/00, 1975 (прототип). 3.Расчет и проектирование элементов ЭВМ. Под. ред. Г.Н. Соловьева. М., Атомиздат, 1975, с. 226. . Микроэлектроника и однородные структуры для построения логических и вычислительных устройств. Под ред. И.В. Прангишвили, М., Наука, 19б7, с. k}.

Ф1/г.7

С регистрег /

С pfzt/cmpffS /

Ф&г.г

f (

f f

f