Ассоциативное запоминающее устройство
Союз Советских
Социалистических
Республик
ОП ИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
G 11 С 15/00 с присоединением заявки ¹â€” Государственный комитет СССР IIo делам изобретений и открытий (23) Приоритет Опубликовано 2 Ы0.81. Бюллетень М 39 (53) УДК 681. 327 (088. 8) Дата опубликования описания 231081 (72) Автор изобретения С. К. Колубай у Харьковский институт радиоэлектроникЪ" (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО Изобретение относится к. запомннающим устройствам. Известно ассоциативное запоминающее устройство (АЗУ), содержащее входной блок, выходной блок, блок управления, ячейки памяти основной информации и ассоциативнык признаков, шины опроса записи, шины считывания, шины совпадения, шины разрешения записи и шины разрешения считывания 1.1). Недостатком этого устройства является низкое быстродействие при необходимости считывания содержимого каждой ячейки памяти в количестве, равном минимальному числу из числа 15 совпадений первого и второго ассоциативных признаков, хранящихся в ячейке, с признаками из некоторого произвольного набора признаков опроса. Наиболее близким техническим реше- 20 нием к"изобретению является АЗУ, содержащее входной регистр, выходной регистр, блок управления, адресные элементы памяти, ассрциатнвные элементы памяти, служащие для хранения первых и вторых признаков, формирователи сигналов состояния ячеек памяти, шины разрешения записи, шины разрешения считывания, шины опросаэаписи, шины считын.ания, шины совпа- 30 дения, причем первые входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы — с шинами разрешения считывания, третьи — с шинами раэрещения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным со входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления, первые н вторые входы формирователей сигналов состояния ячеек памяти соединены с соответствующими шинами совпадения, третьи входы - с шинами разрешения считывания, четвертые входы - с шинами разрешения записи, а пятые и шестые — с другими выходами блока управления, первые и вторые выходы формирователей сигналов состояния ячеек памяти подключены к соответствующим входам блока управления. Кроме того, каждый формирователь сигналов состояния ячеек памяти содер-! жит триггеры, элементы И и ИЛИ,причем 875459 выходу первого и второго элементов И подключены к единичным входам первого и второго триггеров, нулевые входы которых соединены с выходом элемента ИЛИ, а выходы — со входами третьего элемента И, выход третьего триггера подклю5 чен к одним из входов первого и второго элементов И и первому выходу формирователя сигналов состояния ячеек памяти, второй выход которого соединен с выходом третьего элемента И, а входы подключены к другим входам первого и второго элементов И к входам элемента ИЛИ и третьего триггера(2) . Недостатком этого АЗУ является невысокое быстродействие, а также 15 то, что оно не позволяет обеспечить считывание содержимого каждой. ячейки памяти в количестве равном минимальному числу из числа совпадений первого и второго ассоциативных признаков, 20 хранящихся в ячейке, с признаками из некоторого произвольного набора признаков опроса, а решает эту задачу только для частного случая, если все признаки в наборе признаков опроса различные. Цель изобретения — повышение быстродействия и расширение области применения устройства путем обеспечения считывания содержимого каждой ячейки памяти в количестве, равном минимальному числу из числа совпадений первого и второго ассоциативных признаков, хранящихся в ячейке, с признаками из некоторого произвольного набора признаков опроса, содержащего К признаков (K 1) и осуществление необходимого ассоциативного поиска за К опросов. Поставленная цель дост )гается тем, что в ассоциативное запоминаю- 40 щее устройство, содержащее входной и выходной регистры, блок управления, накопитель, состояший из адресных и ассоциативных элементов памяти, формиров атели си гн алов состояния 4 ячеек памяти, каждый из которых содержит первый, второй и третий элементы И, триггер, единичный выход которого подключен к первым входам BTopol o H TpeTbeI o элементов И H первому выходу формирователя сигна- . лов состояния ячеек памяти, второй выход которого соединен с выходом первого элемента И, первый вход формирователя сигналов состояния ячеек памяти соединен со вторым входом второго элемента И, второй вход— со вторым входом третьего элемента И, третий вход — с шиной разрешения считывания, четвертый и пятый входы соответственно с единичным и нуле- 60 вым входами триггера, шестой входс третьими входами второго и третьего элементов И, первые входы элемен тов памяти подключены к соответствующим шинам опроса-записи, которые 5 соединены с выходами входного регистраа, вт орые входы — с шин ами раз решения считывания, третьи — с шинами разрешения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным со входами выходного регистра, вторые.выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и шины разрешения записи подключены к одним из выходов блока управления, первые и вторые входы формирователей сигналов состояния ячеек памяти соединены с соответствующими шинами совпадения, четвертые с шинами разрешения записи, а пятые и шестые — с другими выходами блока управления, первые и вторые выходы формирователей сигналов состояния ячеек памяти подключены к соответствующим входам блока управления, введены в каждый формирователь сигналов состояния ячеек памяти, четвертый и пятый элементы И, элементы ИЛИ, и реверсивные счетчики, причем выходы первого и второго реверсивных счетчиков соединены соответственно с вхо дами первого и второго элементов ИЛИ, первые входы соответственно — с выходами второго и третьего элементов И, вторые — с выходами четвертого и пятого элементов И, третьи входы — с пятым входом формирователя сигналов состояния ячеек памяти, третий вход которого подключен к одним из входов четвертого и пятого элементов И, другие входы которых соединены соответственно с выходами первого и второго элементов ИЛИ и с входами первого элемента И. На фиг; 1 изображена структурная схема АЗУ; на фиг. 2 — структурная схема формирователя сигналов состояния ячеек памяти. АЗу содержит (фиг.1) входной регистр 1, выходной регистр 2, блок 3 управления, накопитель, состоящий из адресных 4 и ассоциативных 5 и б элементов памяти, служащих для хранения первых и вторых признаков, шины 7 раз решения записи, шины 8 разрешения считывания,шины 9 опроса-записи, шины 10 считывания, шины 11 совпадения, формирователи 12 сигналов состояния ячеек памяти с входами 13-18 и выходами 19-20, причем каждый формирователь сигналов состояния ячеек памяти содержит (фиг.2) триггер 21, первый 22, второй 23, третий 24, четвертый 25 и пятый 26 элементы И, первый 27 и второй 28 элементы ИЛИ, вырабатывающие единичный сигнал, если информация на их входе не равна нулю, и вырабатывающие нулевой сигнал в противном случае, первый 29 .и второй 30 реверсивные счетчики с первыми входами 31 и 32, служащими для прибавле875459 ния "1" к содержимому счетчиков, и вторыми входами 33 и 34, служащими для вычитания ."1", и третьими входами 35 и 36, служащими для установки в нулевое состояние, и выходами 37 и 38. Первые 13 и вторые 14 входы формирователей 12 соединены с соответствующими шинами 11 совпадения, третьи входы 15 — с шинами 8 разрешения считывания, четвертые входы 16 — с шинами 7 разрешения записи, пятые 17 и шестые 18 — с соответствчвмими яыходами блока 3 управления, а первые 19 и вторые 20 выходы формирователей 12 подключены к соответствующим входам блока 3 управления. Кроме того, в каждом из формирователей 12 единичный выход триггера 21 подключен к первым входам элементов И 23 и 24 и к выходу 19 формирователя, выход 20 которого соединен с выходом элемента И 22, вход 13 формирователя 12 соединен со вторым входом элемента И 23, вход 14 — со вторым входом элемента И 24, входы 16 и 17 — соответственно с единичным и нулевым входами триггера 21, вход 18 — с третьими входами элементов И 23 и 24, выходы 37 и 38 реверсивных счетчиков 29 и 30 соединены соответственно с входами элементов ИЛИ 27 и 28, входы 31 и 32 - с выходами элементов И 23 и 24, входы 3О 33 и 34 — с выходами элементов И 25 и 26, а входы 35 и 26 соединены между собой и с входом 17 формирователя 12 сигналов состояния ячеек памяти, вход 15 которого подключен к одним из 35 входов элементов И 25 и 26, другие входы которых соединены соответственно с выходами элементов ИЛИ 27 и 28 и с входами элемента И 22. АЗУ работает следукшим образом. Начальная установка состояния всех ячеек памяти АЗУ. Иэ блока 3 управления на входы 17 всех формирователей 12 выдается сигнал "Сброс". В результате триггер 21 и реверсивные счетчики 29 и 30 каждого формирователя 12 перейдут в нулевое состояние. На выходах элементов ИЛИ 27 и 28 установятся нулевые сигналы; так как содержимое каждого из реверсивных счетчиков 29 и 30 равно нулю. Поэтому на выходах 19 и 20 всех формирователей 12 устано-. вятся нулевые значения сигналов. Значения сигналов на выходах любого формирователя 12 будем обозначать парой (S„, S ) где 5„, S< - значения сигналов на выходах 19 и 20. При описании работы АЗУ будем также считать, что элементы памяти, расположенные в одной строке (т.е. соединен- Щ ные с одним и тем же формирователем 12), составляют одну ячейку памяти, соответствующую одному слову. Таким образом, после посылки сиг нана "Сброс" на все формирователи 65 12, на их выходах установятся сигналы равные (0,0), означающие, что все ячейки памяти находятся в состоянии "свободна". Режим записи. Запись производится только в ячейки, находящиеся в состоянии "свободна" . Блок 3 управления выбирает одну из этих ячеек памяти и вырабатывает сигнал по соответствующей шине 7 разрешения записи. Одновременно основная информация и признаки выдаются из входного регистра 1 на соответствующие шины 9 опроса-записи. В результате основная информация и признаки записываются в выбранную ячейку памяти. Сигнал с шины 7 разрешения записи поступает также на вход 16 формирователя 12 и устанавливают ( триггер 21 в единичное состояние.. На выходах этого формирователя, сформируется сигнал (1, 0), означающий, что ячейка памяти находится в состоянии "занято".. В режиме записи из блока 3 управления на входы 18 всех формирователей 12 подается нулевой сигнал, для того чтобы предотвратить появление сигналов на выходах элементов И 23 и 24,в результате возможного поступления сигналов с шин 11 совпадения. Основная информация и признаки записываются в другие ячейки памяти аналогично. Таким образом, все ячейки памяти, в которые будет .осуществлена запись, перейдут в состояние "занято". Режим поиска. Пусть множество признаков опроса содержит К признаков. Для поиска всех слов, которые должны быть считаны и обеспечения необходимого числа считывания по каждому иэ слов необходимо осуществить К опросов. При каждом опросе содержимое всех элементов памяти 5 и 6 сравнивается с соответствующим признаком опроса, выдаваемым из входного регистра 1 на шины 9 опроса-записи. Одновременно из блока 3 управления подается единичный сигнал на входы 18 всех формирователей 12. В результате сравнения на некоторых шинах 11 совпадения появятся единичные сигналы, которые поступят на соответствующие входы формирователей 12. Если формирователь 12 индицирует состояние "занято" и на его входе 13 или 14 появится единичный сигнал, то на выходе элемента И 23 и 24 появится сигнал, который поступит на вход 31 или 32 реверсивного счетчика 29 или 30. В результате содержимое соответствующего счетчика увеличится на единицу. Тем саум в реверсивном счетчике 29 или 30 запомнится, что имело место совпадение признака опроса с соответствующим признаком слова. В результате К опросов признаками из набора признаков опроса 875459 в реверсивных счетчиках формирователей будет запомнено число совпадений признаков слова с признаками опроса. Если содержимое реверсивного счетчика 29 или 30 не равно нулю, то на выходе элементов ИЛИ 27 или 28 установится единичный сигнал. Поэтому те формирователи, содержимое реверсив-. ных счетчиков 29 и 30 которых одновременно окажется не равно нулю в результате опросов, сформируют на выходах 20 единичный сигнал, т ° е. на выходах этих формирователей установится сигнал (1, 1), означающий, что данная ячейка памяти находится в состоянии "готова". После К опросов в такое состояние установятся все 15 ячейки памяти, из которых должна быть считана информация, а число считываний будет храниться в реверсивных счетчиках 29 и 30 формирователей 12 этих ячеек памяти. 20 Режим считывания. Считывание осуществляется только из ячеек памяти в состоянии "готова". для этого на ячейку памяти подается сигнал по шине 8 разрешения считыва- 25 ния. Считываемая информация принимаефся выходным регистром 2. Одновременно сигнал с шины разрешения считывания поступает на вход 15 соответ.ствующе го формирователя 12 и через элементы И 25 и .26 на входы 33 и 34 реверсквных счетчиков 29 и 30. В результате содержимое каждого реверсивного счетчика 29 и 30 уменьшается на единицу. Если после опросов содер- З жимое реверсивного счетчика 29 было равно Р а содержимое ревероивного счетчика 30-m, и пусть Й меньше m, то после E считываний содержимое счетчика 29 станет равно нулю." Поэтому после Р считываний на выходе элемен- 4О та ИЛИ 27 появится нулевой сигнал, что приведет к формированию нулевого сигнала на выходе 20 формирователя. Таким образом, после считывания содержимого ячейки памяти в количест- 45 ве равном минимальному числу из чис ла совпадений первого и второго признаков, хранящихся в ячейке, с признаками из набора признаков опроса, на выходах формирователя 12 соответст- щ вующего этой ячейке установится сиг.нал (f.,0), означающий, что ячейка находится в состоянии "занято" и считывание из нее невозможно. Предлагаемое изобретение. позволяет:5 1. За счет организации запоминания аисла.совпадений ассоциативных признаков слова с признаками из набора признаков опроса и запоминания числа считываний обеспечить считывание содержимого каждой ячейки памяти в количестве, равном минимальному числу из числа, совпадений первого и второго ассоциативных признаков,хранящихся в ячейке, с признаками из некоторого произвольного набора приз- 65 наков опроса, причем если в наборе К (К i 1) признаков, то необходимый ассоциативный поиск осуществляется за К опросов. 2. Чередовать опросы признаков и считывание из ячеек в состоянии "готова", т.е. решать поставленную задачу в процессе поступления признаков опроса, когда неизвестен момент времени поступления последнего К-ro признака. Формула изобретения Ассоциативное запоьынающее устройство, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и ассоциативных элементов памяти, формирователи сигналов состояния ячеек памяти, каждый из которых содержит первый, второй и третий элементы И, триггер единичный выход которого подключен к первым входам второго и третьего элементов . И и к первому выходу формирователя сигналов состояния ячеек памяти, второй выход которого соединен с выходом первого элемэйта И,,первый вход формирователя сигналов состояния ячеек йамяти соединен со вторым входом вто-. рого элемента И, второй вход - со вторым входом третьего элемента И, третий вход — с шиной разрешения считывания, четвертый и пятый входысоответственно с единичным и нулевым входами триггера, шестой вход - с третьими входами второго и третьего элементов И, первые входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения считывания, третьи - с шинаМи разрешения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным со входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и шины разрешения записи подключены к одним иэ выходов блока управления, первые и вторые входы формирователей сигналов состояния ячеек памяти соединены с соответствующими шинами совпадения, четвертые — с шинами разрешения записи, а пятые и шестыес другими выходами блока управления, первые H вторые выходы формирователей сигналов состояния ячеек памяти подключены к соответствующим входам блока управления, о т л и ч а ю— щ е е с я тем, что, с целью повышения быстродействия устройства, в нем формирователь сигналов состояния ячеек памяти содержит четвертый и пятый элементы И, элементы ИЛИ и реверсивные счетчики, причем выходы 875459 /Я /8 ВНИИПИ Заказ 9356/78 Тираж 648 Подписное Филиал ППП Патент,.г.ужгород,ул.Проектная,4 первого и второго реверсивных счетчиков соединены соответственно с входами первого и второго элементов ИЛИ, первые входЫ соответственнос выходами второго и третьего элементов Х, вторые входы — с выходами четвертого и пятого элементов И, третьи входы с пятым входом формирователя сигналов состояния ячеек памяти, третий вход которого подключен к одним из входов четвертого и пятого элементов И, другие входы которых соединены соответственно с выходами первого и второго элементов ИЛИ и с входами первого элемента И. Источники информации, принятые во внимание при экспертизе 1, Однородные микроэлектронные ассоциативные процессоры. Под ред. И. В. Прангишвили . М., "Советское радио", 1973, с. 11. 2. Авторское свидетельство СССР по заявке Р 2745595/18-24, кл. G 11 С 15/00, 1979 (прототип), 
