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

,926717 ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветсникСоциалистичесннкреспублик(22) Заявлено 05. 05. 80 (21) 2919589/18-2 Йс присоединением заявки М(23) ПриоритетОпубликовано 07. 05. 82, Бюллетень ЮвДата опубликования описания 07.05.82пв делам нмбретеннй н вткрытнй(5 Й) АССОЦИАТИВНОЕ ЗАПОМИНАЮ"ЕЕ УСТРОЙСТВ тся к запоми вные запоминаюГ 2 ).устройств содеропроса, блок признаков, индиок памяти осегистр числа 1,устройства явля нных выполняетщие устроиства 113 иОдно из известных жит регистр признака памяти ассоциативных каторы совпадения, б новной информации иНедостатком этого тся то, что поис я только по одно признаку и не мо по сложному запро ескольких, опреязанных между сожет осуществлятьсясу, состоящему из, нделенным образом свбой признаков.Из известных устройств наиболее близким техническим решением к предлагаемому является ассоциативное запоминающее устройство, состоящее из накопителя с ячейками памя 1 и, к кото рым подключены входной регистр, регистр маски, дополнительный сдвигающий регистр, основной :яви"юций рерасширеройства з Изобретение относющкм устройствам. Известны ассоциат гистр, входы и выходы которого соединены с соответствующими выходами ивходами ячеек памяти накопителя, дополнительного сдвигающего регистра,регистра занятости, регистра слов иблока извлечения многозначного ответа Г 21,В этом устройстве реализуютсяФункции ассоциативного поиска по различным критериям "больше", "меньше",1 Оравно , небольше", "неменьшем, "неравно".Недостатком этого устройства является отсутствие возможности поискаинформации по сложному запросу, пред 15ставленному, например, в виде логической Формы поисковых признаков (запрос состоит из поисковых признаков,соединенных между собой операциями20пересечения и/или объединения), чтосущественно сужает область применения устройства,Цель изобретения ние области применения уст а счет926713увеличения числа используемых крите риев поиска.Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее ассоциатив- ный накопитель, регистр признака опроса регистр маски, дополнительный и основной сдвигающие регистры, регистр кодов занятости, регистр границ чисел, блок извлечейия много-. 1 в эначного ответа, причем входы ассоциативного накопитеоя подключены к выходам регистра признака опроса, регистра маски и основного сдвигающего регистра, а выходы - к входам дополни-д тельного сдвигающего регистра, входы основного сдвигающего регистра соединены с выходами блока извлечения многозначного ответа, регистра . границ чисел, регистра кодов занятос ти и дополнительного сдвигающего регистра,а выходы - с входами регистров кода занятости и регистра границ чисел, введены регистр сегментов информации, адресный накопитель, многофункциональный накопитель, буферный регистр и блок управления режимами, вход которого подключен к выходу регистра признака опрока входы многоФуНкционального накопителя подключены соответственно к одному из выходов блока управления режимами, к вы- ходам адресного накопителя, буферного регистра и регистра сегментов информации, входы буферного регист 33 ра и регистра сегментов информации соединены с выходами основного сдвигающего регистра, входы адресного накопителя подключены к выходам регистра сегментов информации и другому выходу блока управления режимами, управляющие входы буферного регистра соединены с выходами регистра сегмен= тов информации, выходы многофункционального накопителя подключены к4% входам блока извлечения многозначного ответа.При этом блок управления режимами целесообразно выполнить в виде блока, содержащего буферный регистр, счетчик, дешифратор, регистр числа, шифратор56 и регистр кодов операций, причем выход буферного регистра подключен к входу дешифратора и одному иэ входов счетчика, одни иэ выходов дешифратора соединены с входами регистра кодов операций, другими входами счетчика и одними из входов регистра числа, другие входы которого подклю. чены к выходам счетчика и регистракодов операций, а выход - к входушифратора, выход которого, а такжедругой выход дешифратора являютсявыходами блока, входом которого является вход буферного регистра,На фиг, 1 изображена функциональная схема ассоциативного запоминающего устройства; на фиг. 2 - структурная схема многофункционального накопителя 1 на фиг. 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 УФМ А, описанного в 3 1, илогические схемы 26; каждая из которых (фиг. 4) состоит из триггера 27и ячейки 28 двумерной вычислительной среды, описанной вПредлагаемое устройство предназначено для сопоставления формализованных описаний документов и запросов в информационно-поисковых системах дескрипторного типа, а также дляпроведения многоаспектного поискаинформации среды данных, представленных в табличном виде.Для поиска документов в документальных информационно-поисковыхсистемах могут быть использованы запросы двух типов.Запрос первого типа состоит изпоисковых признаков, соединенных5 9267булевыми операциями пересечения (И),дополнения (НЕ) и объединения ИЛИ),В процессе сопоставления запросаи описаний документов. каждый признакзапроса сравнивается с признаками 5описаний документов.Запрос второго типа представляетсобой перечень поисковых признаков.В заготовке запроса указывается число, которое определяет минимальное 10количество вхождений признаков запроса в описания документов. Релевантным по отношению к запросу данноготипа является документ, в описаниикоторого содержится не менее указанного числа признаков запроса,Работа устройства осуществляетсяследующим образом,При сопоставлении запросов с описаниями документов, последние хранят. 20ся в накопителе 3. Единичные разрядырегистра 7 указывают на занятые ячейки 4 памяти. Единичные разряды регистра 8 и регистра 9 указывают соответственно на начала признаков описа.ний документов и на начала описанийдокументов.Единичные сигналы регистра 9 поступают на управляющие входы регистра 10 и делят последний на части, ко- З 0лицество и размер которых определяется количеством и объемом описаний документов, записанных в накопителе 3.Каждая часть регистра 10 представля)ет собой регистр сдвига с параллельной записью и последовательным считывзнием информации.Регистры 19, отмеченные единичными разрядами регистра 9, воспринимают информацию только с выходов шифратора 17 блока 11.Работа устройства на примере использования запросов первого типа,Содержимое регистра 8 переписывается на регистр 6. В регистр 1 вводится первое машинное слово (число)запроса, Распознавая код начала запроса дешиФратор 13 выдает сигнал,по которому осуществляется сброссостояния счетчика 14, регистров .15и 16. Затем в регистр 1 вводится следующее машинное слово запроса. Еслидешифратор 13 фиксирует в поступившемслове наличие кода открывающей скобки то на его выходе возникает сигнал,.55который поступает на счетчик 14. Приэтом содержимое счетчика 14 увеличивается на единицу. Если в запросеимеется несколько подряд идущих откры 17 6вающих скобок, их количество записывается на счетчике 14.Если машинное слово запроса является машинным словом первого признака,то он сравнивается с машинными словами, хранящимися в ячейках 4 памятинакопителя 3, отмеченными единичнымиразрядами регистра 6. Результаты срав"нения машинных .слов поступают на ре-.гистр 5, Содержимое регистров 5 и 6сдвигается на один разряд.В регистр 1 вводится следующеемашинное слово запроса,Если оно является продолжениемпризнака запроса, то опять происходит его сравнение с машинными словами ячеек 4 памяти накопителя 7, отмеченными единичными разрядами регистра 6. Результаты сравнения поступа- "ют на регистр 5 и корректируют содержимое последнего. Далее выполняетсяоднотактнь 1 й сдвиг информации регистров 5 и 6. Эти операции продолжаются для всех машинных слов первого признака запроса.В результате сравнения первогопризнака запроса с признаками описаний документов единичные разряды регистра 5 указывают на те признаки описаний документов, которые удовлетворяют условиям поиска (" больше", "меньше",и т.д.),Содержимое регистра 5 переписыва-.ется на регистр 6. Далее в регистр 1вводится машинное слово, которое содержит либо код операции связи (дополнения, пересечения, обьединения)только что просмотренного признакас последующим, либо код открывающейили закрывающей скобки, либо кодконца запроса.Если дешифратор 13 распознаеткод операции связи, то по его выходувыдается сигнал, по которому на регистр 16 переписывается содержимоесчетчика 14, регистра 15 и информация из дешифратора 13, Кроме того,информация из дешифратора 13 переписывается на регистр 15.Содержимое регистра 16 поступаетна шифратор 17, который преобразуетпоступившую информацию в код настройки для логических ячеек 21.Если дешифратор 13 распознает кодконца запроса, то он выдает сигнал,по которому начинается параллельнаяобработка информации в накопителе 20.Полуценные в регистре 6 сигналысравнения признака запроса с призна 7 9267 ками, хранимыми в накопителе 3, переписываются на регистр 10. В регистр сдвига, образованных на регистре 10, эти сигналы сдвигаются и переписываются на входы логических ячеек 21 отмеченных единичными разрядами регистра 9. На указанных логических ячейках 21 над поступившими с регистра 10 сигналами выполняется операция, определяемая кодом настройки, 1 а поступившим с шифратора 17 на соответствующие регистры 19.Таким же образом выполняется сравнение последующих признаков запроса с признаками описаний документов. 15В результате, в процессе сравнения на логических ячейках 21 формируют частные результаты сравнения признаков в соответствии с логической Формой запроса. 2 аС помощью блока 22 выводятся номера документов, описания которых соответствуют запросу.Использование предлагаемого устройства в структуре ЭВМ ЕС поз воляет сократить время поиска информации в 10 .раз. При этом производительность машины на данных классах задач поиска возрастает не менее, чем на 60. Заформула изобретения1. Ассоциативное запоминающее уст- з ройство, содержащее ассоциативный на.- копитель регистр признака опроса, .регистр маски, дополнительный и основной сдвигающие регистры, регистр кодов занятости, регистр границ чисел, блок извлечения многозначного ответа, причем входы ассоциативного накопителя подключены к выходам регистра признака опроса, регистрамаски и основного сдвигающего регист ра, а выходы - к входам дополнительного сдвигающего регистра, входы основного сдвигающего регистра соединены с, выходами блока извлечения многозначного ответа, регистра границ чисел, регистра кодов занятости и дополнительного сдвигающего регистра, а выходы - с входами регистров кодазанятости и регистра границ чисел, о т л и ч а ю щ е е с я тем, что, с целью расширения области примене 17 8ния устройства за счет увеличениячисла используемых критериев поиска,оно содержит регистр сегментов информации, адресный накопитель, многофункциональный накопитель, буферныйрегистр и блок управления режимами,вход которого подключен к выходурегистра признака опроса, входы многофункционального накопителя подключены соответственно к одному из выходов блока управления режимами, квыходам адресного накопителя, буферного регистра и регистра сегментовинформации, входы буферного регистраи регистра сегментов информации соединены с выходами основного сдвигающего регистра, входы адресного накопителя подключены к выходам регистрасегментов информации и другому выходу блока управления режимами, управляющие входы буферного регистра соединены с выходами регистра сегментовинформации.2, Устройство по и. 1, о т л и . -ч а ю щ е е с я тем, что блок управления режимами содержит буферный регистр, счетчик, дешифратор, регистрчисла, шифратор и регистр кодов операций, причем выход буферного регистра подключен к входу дешифратора иодному .из входов счетчика, одни извыходов дешифратора соединены с входами регистра кодов операций, другимивходами счетчика, и однимй из входоврегистра числа, другие входы которогоподключены к выходам счетчика и регистра кодов операций, а выход - к входу шифратора, выход которого, а такжедругой выход дешифратора являются выходами блока, входом которого является вход буферного регистра.Источники информации,принятые во внимание при экспертизе1, Заявка Франции М 2216645,.кл. 6 11 С 15/00, опублик. 1974.2, Авторское свидетельство СССРМ 533989, кл. С 11 С 15/00, 1975,прототип).3.Расчет и проектирование элементов ЭВМ. Под. ред. Г.Н, Соловьева,М Атомиздат, 1975, с. 226,Микроэлектроника и однородныеструктуры для построения логическихи вычислительных устройств. Под ред,И,В, Прангишвили, М "Наука", 1967,с. 41,926717Фиг 4Составитель Ф; Руда едактор Е. Папп Техред Ж. Кастелевичорректор Г.Рещетник аказ 2990/44 Тираж 624 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/лиал ППП "Патент", гужгород, ул, Проектная,