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

элементов И первой группы, управляющие входы второго накопителя соединены с десятым и со вторым выходами блока управления, одиннадцатый и двенадцатый выходы которого являются управляющими выходами устройства.

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

1. АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее первый накопитель, первый и второй регистры слов, первый регистр признака опроса, первый элемент ИЛИ, первый регистр маски, выходы которого подключены к входам мас-кирования первого накопителя, регистр сдвига, выход которого является информацио нным выходом устройства, первую и вторую группы элементовИ, причем управляющие выходы первого накопителя подключены к первым входам элементов И первой группы, отличающееся тем, что, с целью расщирения области применения устройства за счет обеспечения поиска слов по различным критериям поиска, в него введены второй накопитель, второй регистр маски, второй регистр признака опроса, регистр начального слова, регистр конечного слова, регистр адреса, коммутаторы, группы элементов НЕ, блок сравнения и блок управления, первый вход которого является управляющим входом устройства, информационными входами которого являются входы регистра начального слова и одни из входов регистра конечного слова, выходы которого подключены ко .входам регистра сдвига, управляющий вход которого соединен с первым выходом блока управдения, второй выход которого подключен к управляющему входу регистра конечного слова, выходы которого соединены с одними из входов первого коммутатора, а другие входы - с выходами первого регистра слова и одними из входов блока сравнения, выход которого подключен ко второму входу блока управления, а другие входы соединены с выходами регистра начального слова и другими входами первого коммутатора, выходы которого подключены к входам первого регистра признака опроса, выход которого соединен с входом опроса первого накопителя, причем управляющие входы первого коммутатора подключены к третьему и четвертому выходам блока управления, пятый и щестой выходы которого соединены с входами первого регистра маски, а седьмой и первый выходы - с управляющими входами первого накопителя, информационные выходы которого подключены к входам первого регистра .слова, выходы, элементов И (О первой группы соединены с входами второго коммутатора и входами первого элемента ИЛИ, выход которого подключен к третьему входу блока управления, восьмой и девятый выходы которого соединены с управляю- ; щими входами второго коммутатора, одни из выходов которого подключены к входам со регистра адреса, а другие выходы - к входам второго регистра маски и входам элеСП ментов НЕ первой группы, выходы которых ю соединены с входами второго регистра присо знака опроса, выходы KOTOpoi o подключены 00 к первым входам элементов И второй группы и входам опроса второго накопителя, информационные выходы которого соединены с входами второго регистра слова, выходы которого подключены ко.вторым входам элементов И второй группы, выходы которых соединены с адресными входами первого накопителя, выходы регистра адреса и второго регистра маски подключены соответственно к адресным входам и к входам маскирования второго накопителя, выходы результата поиска которого соединены с вхо.дамИ; элементов НЕ второй группы, выходы которых подключены ко вторым входам

1

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

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

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

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

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

Недостатком этого устройства является

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

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

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

5 второй регистры слов, первый регистр признака опроса, первый элемент ИЛИ, первый регистр маски, выходы которого подключены ко входам маскирования первого

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

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

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

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

Ассоциативное запоминающее устройство содержит (фиг. 1) первый 1 и второй 2 информационные входы устройства, регистр 3 начального слова, регистр 4 конечного слова, первый коммутатор 5, первый регистр 6 признака опроса, первый накопитель 7, первый регистр 8 маски, первый регистр 9 слова, блок сравнения 10, регистр 11 сдвига с информационным выходом 12 устройства, первую группу элементов И (где р - число строк накопителя 7), первый элемент ИЛИ 14, второй коммутатор 15, регистр 16 адреса, второй регистр 17 маски, первую группу элементов НЕ 18i-18р, второй регистр 19 признака опроса, второй накопитель 20, вторую группу элементов НЕ 21j-21j,, второй регистр 22 елова, вторую группу элементов И 23i-23р, управляющий вход 24 устройства, предназначенный для управления началом работы, блок 25 управления со входами 26-28 с первого по третий и выходами 29-40 с первого по, двенадцатый. На фиг. 1 обозначены управляющие входы 41, 42 первого 7 и второго 20 накопителей соответственно, управляющие выходы 43 и 44 устройства. Блок 25 управления содержит (фиг. 2) второй элемент ИЛИ 45, первый элемент задержки 46, третий элемент ИЛИ 47, первый элемент И 48, второй 49 и третий 50 элементы задержки, второй элемент И 51 четвертый 52 и пятый 53 элементы задержки, элементы И 54-56 с третьего по пятый, шестой элемент задержки 57, шестой элемент И 58, первый 59 и второй 60 элементы НЕ, элементы ИЛИ 61-63 с четвертого по щестой. Устройство работает следующим обраПеред началом работы все регистры устройства сбрасываются в нуль. Информация, хранимая в ассоциативном запоминающем устройстве, задана в виде семантических отношений, каждое из которых может быть задано в виде упорядоченной тройки (а, п, Ь) где а, b входят во множество D идентификаторов слов, для которых заданы семантические отнощения, идентификатор связи п входит в множестко идентификаторов связи, задающих отношения между элементами множества D. В ячейках накопителя 7 (фиг. 1) хранятся информационные слова, каждое из которых состоит из двух частей, первая из которых представляет собой идентификатор слова, а вторая - идентификатор его связи. Каждому идентификатору слова в накопителе 7 соответствует столько строк, сколько различнь1х связей к нему примыкает. Так, если связи некоторого идентификатора слова а заданы совокупностью отнощения (anjc), (anj,k), (anje), (anjb), где b, с, е, k входят в множество D, PI, Пя, Пз входят в множество идентификаторов связи, то этим отношениям соответствуют три строки в накопителе 7 - aiij апг, аПз. Общее число слов, записанных в накопителе 7, составляет М (). В накопителе 20 хранится ММ-разрядных слов, причем в i-TOM разряде j-го слова (где ij от 1 до М) накопителя 20 записана единица а случае. если идентификатор слова, записанный в первой части j-ой строки накопителя 7, связан связью, с идентификатором слова, записанным в первой части j-ой строки накопителя 7 (т. е. во вто.рых частях i-ой и j-ой строк накопителя 7 записан один и тот же идентификатор связи). При поиске информации, заданной в виде семантических отношений, задается начальный и конечный элементы - идентификаторы слова - и извлекаются идентификаторы слов и связей, лежащие между заданными начальным и конечным словами (т.е. в «контексте). Операция поиска начинается подачей через вход 1 на регистр 3 идентификатора начального слова контекста и через вход 2 - на регистр 4 идентификатора конечного слова контекста. По сигналу начала операции, подаваемому на вход 24, блоком 25 формируются сигналы на выходах 31 и 33, по которым идентификатор начального слова через коммутатор 5 записывается на регистр 6, и в регистре 8 разряды, соответствующие начальному слову, устанавливаются в единичное состояние, разрешая ассоциативный поиск по этому первому слову регистра 6. После того, как сигнал сформируется, на выходе элемента ИЛИ 47 (фиг. 2) блок 25 на выход 35 выдает сигнал разрешения ассоциативного поиска в накопителе 7, на управляющих выходах которого формируются сигналы, соответствующие идентификаторам связи начального слова, которые, пройдя через открытые элементы И 13i, 13г ... 13р, поступают на вход элемента ИЛИ 14. Если в результате описанного поиска на выходе элемента ИЛИ 14 сформирован сигнал нулевого уровня, что соответствует тому, что начальное слово не связано с другими словами и задача не имеет решения, единичный сигнал формируется на выходе элемента И 55 и блок 25 выдает на выход 44 устройства сигнал отсутствия решения. Если же сигнал на выходе элемента ИЛИ 14 имеет единичный уровень, то блок 25 формирует на выходе 36 сигнал, по которому сигналы с выходов накопителя 7 через элементы И 13, ... 13р и коммутатор 15 записываются на регистр 17, а через э.тементы НЕ 18i ... 18р - в инверсном коде заносятся на регистр 19 как признак опроса накопителя 20. Блок 25 на выходе 38 формирует сигнал, разрешающий ассоциативный поиск в накопителе 20. Так как информация в регистре 19 записана в инверсном коде, то нулевой сигнал на выходах результата поиска накопителя 20 формируется в случае, если в соответствующей строке, хотя бы в одном незамаскированном разряде, зафиксировано хотя бы одно несовпадение записанной в этом разряде единицы с нулем того же разряда регистра 19 (т.е.

если нули в незамаскированных разрядах регистра 19 соответствуют некоторому подмножеству слов семантической структуры, то нулевые сигналы на выходах результата поиска накопителя 20 соответствуют словам, связанным со словами этого подмножества). Сигналы, снимаемые с выходов результата поиска накопителя 20, инвертируются элементами НЕ 21i-21р и поступают на входы элементов И IS, 13 ..., Шр. Сигналом, снимаемым с выхода элемента задержки 49 через выход 32 блока 25, коммутатор 5 пропускает код, записанный на регистре 4, на регистр 6. Сигналом, снимаемым с выхода 35 блока 25, производится ассоциативньж опрос накопителя 7, при-этом регистр 8 задает маскирование идентификаторов связи, обеспечивая поиск в накопителе 7 всех строк, в полях идентификатора слова которых записан идентификатор конечного слова, в результате на соответствующих управляющих выходах накопителя 7 формируются сигналы единичного уровня, которые поступают на входы, элементов И 13i, 13 ... 13р, и если на их выходах зафиксирован элементом ИЛИ 14 хотя бы один сигнал единичного уровня, то тем самым устанавливается факт, что среди слов, связанных с начальным словом одной связью, будет и конечное слово. В случае, если на выходе элемента ИЛИ 14 зафиксирован сигнал нулевого уровня, то сигнал с выхода элемента НЕ 60 через открытый элемент И 56 и выход 34 поступает на вход регистра 8, обеспечивая маскирование всего конечного слова. Пройдя через элемент задержки 57 и элемент ИЛИ 47, сигнал с выхода 35 подается на управляющий вход накопителя 7, разрешая ассоциативный поиск в нем. Так как все слово замаскировано, то со всех управляющих выходов накопителя 7 снимаются сигналы единичного уровня, которые разрешают прохождение сигналов с выходов элементов НЕ 21, 21г ... 21р через элементы И 13, 13 ..., 13р, поступающих на входы элемента ИЛИ 14 и коммутатора 15. Если на выходе элемента ИЛИ 14 в- этом случае сформирован сигнал нулевого уровня (что соответствует отсутствию сигналов на выходах элементов НЕ 2Ц, 212, Ц, т.е. случаю, когда начальное слово не связано ни с каким другим словом, то с выхода элемента И 55 на выходе 40 блока 25 формируется сигнал неразрешимости задачи, который поступает на выход 44 устройства. В случае, если сигнал на выходе элемента ИЛИ 14 имеет единичный уровень, то сигнал с выхода 37 блока 25 подается на вход коммутатора 15, коммутирующего сигналы с выходов элементов И 13j, 132, . 13 на входы элементов НЕ 18i ..: 18р и регистра 17. В дальнейшем цикл работы устройства повторяется, причем на втором цикле выделяются слова, связанные с начальным словом двумя связями (через промежуточный идентификатор слова), на третьем цикле связанные тремя связями и так далее. В случае, если на каком-либо цикле при опросе накопителя 7 (в регистре 6 при этом находится конечное слово) зафиксирован хотя бы один единичный сигнал на выходах элементов И 13j, 132, 13р, элементом ИЛИ 14 формируется единичный сигнал, который, пройдя через открытый элемент И 51, поступает с выхода 37 блока 25 на управляющий вход коммутатора 15, через который на регистр 16 записывается код, зафиксированный на выходах элементов И ISj-pВ регистре 16 при этом фиксируется в виде единицы в одном из разрядов адрес последнего конечного слова. С выхода блока 25 на вход 42 выдается сигнал опроса накопителя 20 по адресу, зафиксированному в регистре 16, в результате чего на регистр 22 записывается слово, в котором фиксируются в виде единиц в соответствующих разрядах

0 те идентификаторы слов, которые связаны с конечным словом. А в регистре 19 в этот момент хранятся зафиксированные в виде единиц в соответствующих разрядах идентификаторы слов, связанные с начальным словом. Элементами И 23, 23j,, ..., 23р выделяется идентификатор слова, связанный непосредственно с конечным, и связанный с начальными идентификаторами слов, т.е. являющийся предоконечным словом.

Сигналы с выходов элементов И 23j, ...,

Q 23р поступают на адресные входы накопителя 7. Сигнал с выхода элемента задержки 53 поступает через выход блока 25 на вход 41 накопителя 7, разрешая считывание слова по поступившему адресу. На регистр 9 при этом считывается идентификатор предоконечного слова и идентификатор связи, связывающей его с конечным словом. Одновременно код конечного слова из регистра 4 заносится на регистр 11 сигналом на аыходе 30 и сдвигается сигналом на выходе 29. Затем код предоконечного слова записыва ется на регистр 4. Одновременно найденный идентификатор предоконечного слова сравнивается с начальным словом на блоке 10. Если предоконечное слово совпадает с начальным, то поиск окончен и с выхода эле5 мента И 54 через выход 39 блока 25 на выход 43 устройства выдается сигнал окончания операции поиска. Если совпадение не имеет места, то вновь начинается поиск, аналогичный описанному, с той разницей, что в качестве конечного слова используется

0 предоконечное. В результате этого поиска находится следующее предоконечное слово, и так далее, пока не будет найдена вся цепочка элементов семантической цепи, связывающей начальное и конечное слова. Таким образом, предложенное ассоциа5 тивное запоминающее устройство позволяет производить ассоциативный поиск слов по нескольким различным критерям поиска (например, идентификаторам слов и идентификаторам связей) и таким путем выполнять поиск слов, связанных семантическими отношениями, что позволяет расширить область применения ассоциативной памяти. -J 35 }2328Ы j ULJJL

Технико-экономическое преимущество от использования предлагаемого устройства заключается в более широкой области его применения по сравнению с прототипом. 2г7 ф. /. / iftf Cp(/.f

35 29 28 36 J7

26 29

tfO 39

(риг. 2