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

 

„„926717

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советсник

Социалистичесннк республик (61) Дополнительное к авт. свнд-ву (22) Заявлено 05. 05. 80 (21) 2919589/18-2ч с присоединением заявки М (23) Приоритет

Опубликовано 07. 05. 82. Бюллетень М

Дата опубликования описания 07.05.82 (5 3 ) М. Кл.

4 11 С 15/00

)Ьвударетвенный квмнтет

СССР пв делам нмбрвтеннй н вткрытнй (53) УД К681.327 (088. 8) (72) Автор изобретения

С.10. Баландин (7() Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЦЕЕ УСТРОЙСТВО

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

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

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

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

Из известных устройств наиболее близким техническим решением к предлагаемому является ассоциативное запоминающее устройство, состоящее из накопителя с ячейками памя1и, к которым подключены входной реги<-.-p, регистр маски, дополнительный сдвигающий регистр, o(.íoâ Hîé одви f ающий регистр, входы и выходы которого соединены с соответствующими выходами и входами ячеек памяти накопителя, дополнительного сдвигающего регистра, регистра занятости, регистра слов и блока извлечения многозначного ответа Е2 1.

В этом устройстве реализуются функции ассоциативного поиска по различным критериям "больше", "меньше", 10 равно, небольше", "неменьше", "неl! I! равно".

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

20 пересечения и/или объединения), что существенно сужает область применения устройства, Цель изобретения †. расширение области применения устройства за счет

92671

3 увеличения числа используемых крите. риев поиска.

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

4% входам блока извлечения многозначного ответа.

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

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

На фиг. 1 изображена функциональная схема ассоциативного запоминающего устройства; на фиг. 2 - структурная схема многофункционального накопителя, на фиг. 3 и фиг. 4 показаны структурные схемы блока предварительной обработки информации и логической схемы.

Ассоциативное запоминающее устройство (фиг. 1) содержит регистр 1 признака опроса, регистр 2 маски, ассоциативный накопитель 3, выполненный из ячеек 4 памяти, дополнительный 5 и основной 6 сдвигакй ие регистры, регистр 7 кодов занятости; регистр 8 числа, регистр 9 сегментов информации, буферный регистр 10 границ чисел блок-11 управления режимами.

Блок 11 содержит буферный регистр 12, дешифратор 13, счетчик 14, регистр

15 кодов операций, регистр 16 числа и шифратор 17. Кроме того, устройство содержит адресный накопитель 18, состоящий из регистров 19, многофункциональный накопитель 20, служащий для хранения и обработки информации и состоящий из логических ячеек 21, и блок 22 извлечения многозначного ответа.

Многофункциональный накопитель 20 (фиг. 2) содержит блоки 23 предварительной обработки информации, каждый . из которых (фиг. 3) состоит из дешифратора 24 и многофункционального модуля 25 УФМ- 1А, описанного в (3 ), и логические схемы 26; каждая из которых (фиг. 4) состоит из триггера 27 и ячейки 28 двумерной вычислительной среды, описанной в (4 $.

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

Для поиска документов в документальных информационно-поисковых системах могут быть использованы запросы двух типов.

Запрос первого типа состоит из поисковых признаков, соединенных

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

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

Запрос второго типа представляет собой перечень поисковых признаков.

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

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

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

Единичные сигналы регистра 9 поступают на управляющие входы регистра 10 и делят последний на части, ко- эв личество и размер которых определяется количеством и объемом описаний документов, записанных в накопителе 3.

Каждая часть регистра 10 представля) ет собой регистр сдвига с параллельной записью и последовательным считывзнием информации.

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

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

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

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

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

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

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

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

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

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

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

Полученные в регистре 6 сигналы сравнения признака запроса с призна9267 ками, хранимыми в накопителе 3, переписываются на регистр 10. В регистр сдвига, образованных на регистре

10, эти сигналы сдвигаются и переписываются на входы логических ячеек

21 отмеченных единичными разрядами регистра 9. На указанных логических ячейках 21 над поступившими с регистра 10 сигналами выполняется операция, определяемая кодом настройки, 10 поступившим с шифратора 17 на соответствующие регистры 19.

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

В результате, в процессе сравнения на логических ячейках 21 формируют частные результаты сравнения признаков в соответствии с логической формой запроса. 20

С помощью блока 22 выводятся номера документов, описания которых соответствуют запросу.

Использование предлагаемого устройства в структуре ЭВМ ЕС- 1050 поз- 25 воляет сократить время поиска информации в 10 .раз. При этом производительность машины на данных классах задач поиска возрастает не менее, чем на 603..

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

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

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

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

1, Заявка Франции М 2216645,. кл. G 11 С 15/00, опублик. 1974.

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

М 533989, кл. G 11 С 15/00, 1975 прототип).

3.Расчет и проектирование элементов ЭВМ. Под. ред. Г.Н. Соловьева.

М., Атомиздат, 1975, с. 226.

4. Микроэлектроника и однородные структуры для построения логических и вычислительных устройств. Под ред.

И.В. Прангишвили, М., "Наука", 1967, с. 41.

926717

Составитель ф; Рудаков

Редактор Е. Папп Техред Ж. Кастелевич Корректор Г. Решетник

Заказ 2990/44 Тираж 624 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Филиал ППП "Патент", г..ужгород, ул. Проектная, 4