Ассоциативное запоминающее устройство
1, АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее блок управления и накопители, отличающееся тем, что, с целью повышения быстродействия и надежности, в него введены блоки управления поиском и блоки обработки данных, причем входы накопителей подключены к выходам соответствующих блоков управления поиском, выходы накопителей соединены с входами соответствующих блоков обработки данных, выходы которых подключены к входам соответствующих блоков управления поиском, управляющие входы и выходы блока управления соединены с соответствующими входами и выходами блоков управления поиском, а входы/выходы сопряжения блока управления и блоков управления поиском являются входами / выходами устройства. (Л о ;о о to со ui.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (5D 4 G 11 С 15/00
ОПИСАНИЕ ИЗОБРЕТ
Н АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3558705/24-24 (22) 28.02.83 (46) 23.07.85. Бюл. № 27 (72) М. Н. Жуков (71) Таганрогский радиотехнический институт им. В. Д. Калмыкова (53) 681.327.6 (088.8) (56) Зарубежная радиоэлектроника, 1980, № 5, с. 13, рис. 2.
Кохонен Т. Ассоциативные запоминающие устройства. М., «Мир», 1982, с. 330, рис. 6.4. (54) (57) I. АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОИСТВО, содержащее блок управления и накопители, отличающе„,ЯЦ„„1169023 д еся тем, что, с целью повышения быстродействия и надежности, в него введены блоки управления поиском и блоки обработки данных, причем входы накопителей подклк>чеHbl к выходам соответствующих блоков управления поиском, выходы накопителей соединены с входами соответствующих блоков обработки данных, выходы которых подключены к входам соответствующих блоков управления поиском, управляющие входы и выходы блока управления соединены с соответствующими входами и выходами блоков управления поиском, а входы/выходы сопряжения блока управления и блоков управления поиском являются входами / выходами устройства.
1169023
2. Устройство Ito и. 1, отличающееся тем, что накопитель с одномерной выборкой содержит блок памяти, первый и второй селекторы, первый и второй элементы ИЛИ, причем адресные входы первой и нторой групп блока памяти подключены к входам первого и второго селекторов соответственно и являются входами накопителя, выходы селекторов соединены с входами первого элемента ИЛИ, первый вход второго элемент" ИЛИ подключен к выходу блока памяти, второй вход соединен с выходом первого элемента ИЛИ, а выход является выхс)дом накопителя.
3. Устройство по и. 1, отличающееся тем, что накопитель с многомерной выборкой со,!ер)кит блок памяти, первый и второй !
)ь г, i3I !Р и,» )-) )1» сс tel 11 <(i
li)li (хпике и может быть ис<гользовано lip!1 пог. :ро«нии сг!Стс м хранения и поиска инфо!))<а!1ии и банков данных с ассоциатинt!biÌ !IO 1ель!О It»o()ðñгения является повышени(. бь!стролс:"i:.тния и надежности устройства. Н»
< x(м» !<(Сi) t,tt )т 1н< ОГО запом и на IО!цего х ст ройств» для слов, состоящих из четырех букв; на фиг. 2 схл<а накопителя с Олtioв!!(м(! Ioé ныооркой; на фи!. 3 — cx(. м» и» ко Устройство (фиг. 4) содержит накопите,
Обр»ботки дdllliblx. блок 4 управления, входь: пыхо ibl 5 и 6 сопряжения соответcTb(tit!() блоков 3 обработки данных и блока 4 у !ранлсния, управляюшие входы и выходы 7. Н содержит первую группу адресных входов 8, блок 9 памяти, первый селектор 10, первый эдеме! т ИЛИ 1, втору(О t I)yt! Itv адрес:It>tx Bxo;toí 12, второй селектор 13, второй элемент ИЛИ 14 и выход !5. 11 it 5 ! О 30 триггер, элемент И, причем адресные входы блока памяти подключены к выходам первого мультиплексора, входы первой группы которого соединены с входами первого селектора, входы второй группы подключены к входам второго селектора, а вход управления соединен с выходом триггера и входом управления блока памяти, выходы которого подключены к входам первой группы второго мультиплексора, выходы которого являются выходами накопителя, входы второй группы соединены с шиной логической единицы, а вход управления подключен к выходу элемента И, входы которого соединены с выходами первого и второго селекторов, первый и второй входы триггера и входы селекторов являются соответственно входами накопителя. Блоки 2 управления поиском. блоки 3 обработки данных и блок 4 управления представляет собой управляющие автоматы, например, на основе микро-3ВМ. Массив запоминающих ячеек накопителя (фиг. 4) представляет собой прямоугольную матрицу, строки и столбцы которой соответствуют символам алфавитов i u i букв соответственно. Ненулевому значению запоминаемого отношения соответствует единица, 3аписанная на пересечении соответстнуюших строки и столбца. Например, если н запоминаемом слове i u j буквы являк)тся А и 8 соответственно, то единица записывается на пересечении строки, соответствуюшей букве Л, и столбца, соответстнуюшего букве В. На фиг. 5 показан пример кодирования слов н ассоп,иативном запоминающем устройстве, где Rq,! — множество i, j отношений, храняшихся в поле памяти i, j накопителя. Горизонтальные и верти кальные линии отражают информационнь(е связи между отношениями, в ассоциативном запоминаю!цем устройстве им соответствуют горизонтальные и вертикальные входы. Матрицы отношений расположены так, что для каждой букны слова сушествует одна информационная связь по всем отношениям, включаю<цим эту букву. Шкалы «1 буква», »II буква» и так далее отражают соотношения соответствуюших горизонтальных и вертикальных входов и соответствуют состояниям выходных сигналов процессоров второго вида. При записи слова в намять соответственно значениям всех его букв возбуждают все горизонтальные и вер1169023 тикальные линии. При этом в каждом из накопителей одна ячейка памяти. Импульсом записи, подаваемым одновременно во все накопители, осуществляется запись единиц в выбранные ячейки памяти. Этим единицам соответствуют ненулевые отношения в записываемом c;Ioh(. Если в словах имеются одинаковь1е отношения, то эти Отн01г>ени51 ж)диру10тся Одинаково и хранятся в одних и тех же ячейках памяти, т. е. без избыточности. Например, в слова «Сеть», и «Суть» отношения R1.3, Rl.4 и R3.4 одинаковы, и они хранятся в одних и тех же ячейках памяти для обоих слов. Ассоциативная выборка информации осуществляется следующим образом. ! 1редположим, рсоуется в1>п>рать из памяти слово, первая и вторая буки1 которого с и у соответственно (фиг. 6) . Сначалаа г1 ровг>дят горизонтальную . i H HHþ на уровне буквы с Ог шкалы, соответствующей первой букве, а также п>ризон гальну>о и вертикальную линии на уровне Оуквы у от шкалы, соответствую цей второй букве. Если на пересечении этих л1>ний заг1исана единица, т. е, Отношение Й l>2> =- 1. значит в ассопиати H и Ом за пом и на кяцем устройстве присутствуют слова с заданным поисковым признаком. !иле<- просматривают пары отношений R !.3 — -К2.3 и К! .4-- К2.4 пересекая их вертикальными линиями. При этом запоминают все такие сочетания Отношений когда оба отношения в паре одновременно равняются еди ни i! å. После этого, 11сходя из полученных наооров. проводят вертикальные линии, соответствующие третьей и четвертой буквам, и горизонтальную линию, соответству ющую третьей букве. П ри этом, если R3.4=-1, поиск прекращают и считывают искомые буквы. В противном случае устанавливают другое сочетание третьей и четвертой букв и внои> проверяют отношение R3.4. Накопитель с одномерной выборкой работает следующим образом. Г1ри подаче на входы 8 и 12 кодов букв в блоке 9 памяти выбирается соответствующая ячейка памяти, содержимое которой появляется на выходе блока 9. На выходах селекторов !О и 1,3 появляется сигнал логической «1» в случае, если на соответствующем входе !2 или 8 появляется код, означающий, что поиск по данной букве не производится. Сигнал с выхода блока 9 памяти появляется на выходе 15 лишь в случае, если на горизонтальный 12 и вертикальный 8 входы поданы коды букв из соответствующих алфавитов. В противном случае на выходе 15 накопителя постоянно присутствует сигнал логической «1». Накопитель с многомерной выборкой работает следующим образом. 1О Ьлок 20 памяти с многомерной выборкой представляет собой квадратный массив запоминающих ячеек и имеет столько инфор;1 ационных выходов и входов, сколько запомпнак>щих ячеек содержится B ее строке либо столбце. В зависимости от управляюи;его сигнала i!3 выходах блока 20 1тоявляется содержимое всей строки либо столбца и ас сп па запоминающих ячеек, адрес которых установлен íà его адресных входах Триггер 19 управляется сигналами от горизонтального 21 и вертикального 6 Входов и служит для подключения к адресным входам блока 20 памяти посредством мультиплексора 17 сигналов k13 горизонтального 21 либо вертикального 16 вх1>дов, а также для управления направi с.: и:,:бор>си в запоминающем устройстве 20. Селекторы 8 и 22 предназначены для обнаружения кода запрета выборки на г >!lI! "Опталь«ом 21 и вертикальном !6 вхогах соогветственно и совместно с элеменго>1 l i 25 и мультиплексором 23 осуществляк>г подк,>Io«I."HHe к выходам 24 выходов блока 20 памяти либо сигналов логической «I». При этом выходы блока 20 памяти подключены к выходам накопителя лишь в том случае, если или по горизонтальному вхо.i 2!, или по вертикальному входу 16 , пр :шел код запрета выборки. Л, с1>1,11ативное запоминающее устройство работает следующим образом. Перед началом работы на входах 5 блоков,> усг 11е содержит буквы в данной позиции слова, То на входе 5 соответствующего данной 1п>з1>ни и слова блока 3 устанавливают код запрета. После установления на входах 5 всех Олоков 3 нужных кодов подают управл> юший сигнал по входу 6 блока 4 i ïðàâIeHII>l, который, в свою очередь, по входам 7 осуп!Оo Tâ >Iÿåò загрузку блоков 3 установле>иными на их входах 5 кодами. При этом блоки 3 возбуждают вертикальные и горизонтальные входы, соединенные с их первымп и вторыми выходами соответственно, кодами, соответствующих букв. В результате этого на выходах накопителей на ос>>ове запоминающего устройства с одновременной выборкой (фиг. 2), расположенных на пересечениях входов, возбужденных кодами букв, появляется содержимое выбранных ячеек памяти, отражающее наличие или отсутствие в ассоциативном запоминающем устройстве отношений, определенных ключом. На выходах накопителей,, на одну или на обе группы адресных входов которых поступил код запрета, устанавливаются сигналы логической «1». Таким образом. если выходы всех накопителей 1169023 10 находятся в состоянии логической «1», значит слово или слова с заданным поисковым признаком присутствуют в ассоциативном запоминающем устройстве. Проверка этой ситуации осуществляется с помощью блоков 2, которые в простейшем случае представляет собой схемы И. Дальнейший поиск может производиться двумя путями, Если элементы ключа расположены преимущественно в начале словя, блок 4 управления посредством входа 7 выдан в блоки 3 управляющий сигнал, по которому последние начинают просмогр столбцов. При этом каждый блок 3 возбуждает вертикальный вход, соединенный с его первым выходом, кодами различных букв. всякий раз опрашивая при этом выхо., блока 2, входы которого соедиiicпы с выходами накопителей расположенных в данном столбце. Поскольку часть горизОIITc!iiüHI Iõ вхîi)ов уже возбуждена колями букв поискового ключа, часть наконитслсй. рясI!оло)кенных на пересечении эгих -Орнзонтяльных BxofloB с вертикальнымн, ныдяет в блоки 2 информацию о хранимы.. н них отгннпениях для соответствующих соче яний букв. Выходы остальных H»HOI1H Г(ЛЕИ НЯ ХОДЯТСЯ В СОСТОЯНИИ ЛОГИческой «!». 1!я вход блока 3 с выхода блока 2 ьосгупяст сигнал логической «1» в том лишь случае. если все выбранные для установле ного кода буквы отношения в столбце ненулевые. Последовательно возбуждая ВЕРТИ I При этом он выдает на вход 7 сигнал об окон гя н;) и росм отр а. 11оc;Ie получения от всех блоков 3 сигналов Об окончании просмотра блок 4 упряь.".е ия посредством выхода 7 выдает блок::, -> управляющий сигнал, по которому по..)слние начиняют просмотр строк. Просмотр строк осуществляется так же, как и и1н)с, отр столбцов. Если его результатом является такая комбинация букв слова, для каждой из которых блок 2 соответствующей строки выдал сигнал логической «1», бло;:, 4 выдает сигнал, извещающий, что первое слово с заданным поисковым ключом найдено и его буквы могут быть считаны с входов 5 блоков 3. После этого, а такжс в слу яе, «сли первый просмотр горизонтяльных шин не дает искомого результата, блок 4 управления посредством входа 7 выдает в блоки 3 управляющий сигнал, по кс то рому последние уста навливают ня своих вертикальных шинах другую комбиняцик) кодов букв из числа найденных Нр» первсм просмотре столбцов. После 55 этого осуществляется второй просмотр горизонтальных шин и т. д. Таким образом, в результате последовательных итераций находятся все слова с заданным поисковым признаком. Сигналом окончания поиска является исчерпание всех комбинаций кодов букв на вертикальных шинах. найденных при первом просмотре. Если элементы ключа расположены преимущественно в конце слова, поиск производят описанным способом, но начинают с просмотра строк. Если в ассоциативном запоминающем устройстве используют накопители с многомерной выборкой, поиск информации производится следующим образом. На входах 5 соответствующих блоков 3 устанавливают либо коды букв ключа, либо коды запрета. Сигнал «Пуск» подают по входу 6 блока 4 управления, который посредством выхода 7 выдает управляющие сигналы в блоки 3. При этом, если элементы ключа расположены преимущественно в начале слова, блоки 3, на входы 5 которых поданы коды букв, составляющих ключ, возбуждают этими кодами свои горизонтальные входы, вертикальные входы эти же блоки 3 возбуждают кодами запрета. Блоки 3, на входах 5 которых установлены коды запрета, возбуждают этими кодами и горизонтальные и вертикальны входы, соединенные с их первыми и вторыми выходами соответственно. В результате этого на выходах накопителей, содержащих, входящие в поисковый ключ, появляется содержимое выбранных в них строк. Все выходы остальных накопителей находятся в состоянии логической «1». Далее блоки 3 опрашивают выходы блоков 2 о столбцах. Блоки 2, в этом случае, выполняют логические операции «И» над одноименными выходами всех накопителей столбца либо строки, Выход определенного разряда блока 2 находится в состоянии логической «!» лишь в том случае, если эти же разряды на выходах всех накопителей 1 столбца либо строки одновременно равны единице. В результате опроса >выходов блоков 2 блок 3 запоминает коды букв, соответствующих единичным разрядам на выходах первых. При этом блоки 3, обрабатывающие элементы ключа, сравнивают эти коды с кодами букв ключа. Если коды равны для всех позиций букв в ключе, значит слова с данным поисковым признаком имеются в ассоциативном запоминающем устройстве. В этом случае блок 4 управления выдает в блоки 3 управляющий сигнал, по которому последние устанавливают на своих горизонтальных входах коды запрета, на вертикальных входах блоки 3, обрабатывающие элементы ключа, устанавливают коды соответствующих 1169023 букв, составляющих ключ, остальные блоки 3 устанавливают на своих вертикальных входах коды букв, найденных при первом просмотре. Далее блоки 3 оп рапп и ва ют выходы блоков 2, расположенных в строках матрицы накопителей 1. Все возможные комбинации букв, соответс гвующих единичным разрядам на выходах строчных блоков 2, являются словами, выбранными из ассоциативного запоминающего устройст ва для данного ключа. После этого, а также в случае, когда во всех разрядах хотя бы одного строчного блока 2 окажутся записанными нули, блок 4 управления выдает в блоки 3 управляющий сигнал, по которому последние возбуждают свои вертикальные входы другой комбинацией букв, найденных при первом просмотре. Далее по сигналу из блока 4 управления блоки 3 вновь опраnlивают выходы строчных блоков 2 и т.д. Таким образом, в результате последовательных операций из ассоциативного запои и нающего устройства исключаются все слова с заданным поисковым признаком. Процесс поиска прекращается по исчерпании всех комбинаций букв на вертикальных вхо.. lx, полученных при первом просмотре. Если элементы ключа расположены преимущественно в конце слова, поиск проводят описанным способом, начиная с просм отр а ст ро к. Таким образом, использование в ассо15 циативном запоминающем устройстве накопителя с многомерной выборкой существен,о снижает время поиска. 1169023 I дзк3п ° Ы адк//а Фиг. 5 Редактор И. Николайчук За каз 4620/46 i ая букба 3 Ю Л,./ -ая уИа Состав ител ь О. Исаев Техред И. Верес Корректор О. Луговая Тираж 584 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, ж — 35, Раушская наб., д. 4/5 Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4
