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

Союз Советских Социалистическия РеспубликОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и 875459(5)М. Кл.з а 11 С 15/00 с присоединением заявки й 9 -Государственный комитет СССР ио делам изобретений и открытийДата опубликования описания 2 Ы 081(72) Автор изобретения С. К. Колубай руХарьковский институт радиоэлектроникЪ(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО Изобретение относится к запомннающим устройствам.Известно ассоциативное запоминающее устройство (АЗУ), содержащее входной блок, выходной блок, блок управления, ячейки памяти основной информации и ассоциативнык признаков, шины опроса записи, шины считывания, шины совпадения, шина разрешения записи и шины разрешения считывания 1,Недостатком этого устройства является низкое быстродействие при необходимости считывания содержимого каждой ячейки памяти в количестве, равном минимальному числу из числа 15 совпадений первого и второго ассоциативных признаков, хранящихся в ячейке, с признаками из некоторого произвольного набора признаков опроса.Наиболее близким техническим реше нием кфизобретению является АЗУ, со" держащее входной регистр, выходной регистр, блок управления, адресные элементы памяти, ассоциативные элементы памяти, служащие для хранения первых и вторых признаков, формирователи сигналов состояния ячеек памяти, шины разрешения записи, шины разрешения считывания, шины опросаэаписи, шины считывания, шины совпа дения, причем первые входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения считывания, третьи - с шинами разрешения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным со входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления, первые н вторые входы формирователей сигналов состояния ячеек памяти соединены с соответствующими шинами совпадения, третьи входы - с шинами разрешения считывания, четвертые входы - с шинами разрешения записи, а пятые и шестые - с другими выходами блока управления, первые и вторые выходы формирователей сигналов состояния ячеек памяти подключены к соответствующим входам блока управления.Кроме того, каждый формирователь сигналов состояния ячеек памяти.содержит триггеры, элементы И и ИЛИ,причемвыход первого и второго элементов И подключены к единичным входам первого и второго триггеров, нулевые входы которых соединены с выходом элемента ИЛИ, а выходы - со входами третьего элемента И, выход третьего триггера подклю 5 чен к одним из входов первого и второго элементов И и первому выходу формирователя сигналов состояния ячеек памяти, второй выход которого соединен с выходом третьего элемента И, а входы подключены к другим входам первого и второго элементов И к входам элемента ИЛИ и третьего триггера(2 .Недостатком этого АЗУ является невысокое быстродействие, а также 15 то, что оно не позволяет обеспечить считывание содержимого каждой. ячейки памяти в количестве равном минимальному числу из числа совпадений первого и второго ассоциативных признаков, 20 хранящихся в ячейке, с признаками из некоторого произвольного набора признаков опроса, а решает эту задачу только для частного случая, если все признаки в наборе признаков опроса различные.Цель изобретения - повышение быстродействия и расширение области применения устройства путем обеспечения считывания содержимого каждой ячейки памяти в количестве, равном минимальному числу из числа совпадений первого и второго ассоциативных признаков, хранящихся в ячейке, с признаками из некоторого произвольного набора признаков опроса, содержащего К признаков (К1) и осуществление необходимого ассоциативного поиска за К опросов.Поставленная цель достигается тем, что в ассоциативное запоминаю щее устройство, содержащеевходной и выходной регистры, блок управления, накопитель, состояший из адресных и ассоциативных элементов памяти, формирователи сигналов состояния 45 ячеек памяти, каждый из которых содержит первый, второй и третий элементы И, триггер, единичный выход которого подключен к первым входам второго и треьго элементов И и первому выходу формирователя сигна- , лов состояния ячеек памяти, второй выход которого соединен с выходом первого элемента И, первый вход формирователя сигналов состояния ячеек памяти соединен со вторым входом второго элемента И, второй вход - со вторым входом третьего элемента И, третий вход - с шиной разрешения считывания, четвертый и пятый входы соответственно с единичным и нуле- бО вым входами триггера, шестой входс третьими входами второго и третьего элементов И, первые входы элемен тов памяти подключены к соответствующим шинам опроса-записи, которые 65 соединены с выходами входного регистраа, вт орые входы - с шин ами раз решения считывания, третьи - с шинами разрешения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным со входами выходного регистра, вторые.выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и шины разрешения записи подключены к одним из выходов блока управления, первые и вторые входы формирователей сигналов состояния ячеек памяти соединены с соответствующими шинами совпадения, четвертые с шинами разрешения записи, а пятые и шестые - с другими выходами блока управления, первые и вторые выходы формирователей сигналов состояния ячеек памяти подключены к соответствующим входам блока управления, введены в каждый формирователь сигналов состояния ячеек памяти, четвертый и пятый элементы И, элементы ИЛИ, и реверсивные счетчики, причем выходы первого и второго реверсивных счетчиков соединены соответственно с вхофдами первого и второго элементов ИЛИ, первые входы соответственно - с выходами второго и третьего элементов И, вторые - с выходами четвертого и пятого элементов И, третьи входы - с пятым входом формирователя сигналов состояния ячеек памяти, третий вход которого подключен к одним из входов четвертого и пятого элементов И, другие входы которых соединены соответственно с выходами первого и второго элементов ИЛИ и с входами первого элемента И.На фиг; 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, служащими для прибавления "1" к содержимому счетчиков, и вторыми входами 33 и 34, служащими для вычитания "1", и третьими входами 35 и 36, служащими для установки в нулевое состояние, и выходами 37 и 38.5Первые 13 и вторые 14 входы формирователей 12 соединены с соответствующими шинами 11 совпадения, третьи входы 15 - с шинами 8 разрешения считывания, четвертые входы 16 - с шинами 7 разрешения записи, пятые 17 и шестые 18 - с соответствующими выходами блока 3 управления, а первые 19 и вторые 20 выходы формирователей 12 подключены к соответствующим входам блока 3 управления. Кроме того, 15 в каждом из формирователей 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 выдается сигнал Сброс . В результате триггер 4 21 и реверсивные счетчики 29 и 30 каждого формирователя 12 перейдут в нулевое состояние. На выходах элементов ИЛИ 27 и 28 установятся нулевые сигналы; так как содержимое каждого из реверсивных счетчиков 29 и 30 равно нулю, Поэтому на выходах 19 и 20 всех формирователей 12 устано-. вятся нулевые значения сигналов. Значения сигналов на выходах любого формирователя 12 будем обозначать парой (5, 5), где 5, 51 - значения сигналов на выходах 19 и 20. При описании работы АЗУ будем также считать, что элементы памяти, расположенные в одной строке (т.е. соединен- Щ ные с одним и тем же формирователем 12), составляют одну ячейку памяти, соответствующую одному слову.Таким образом, после посылки сиг нана фсбросф на все формирователи 5 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 запомнится, что имело место совпадение признака опроса с соответствующим признаком слова. В результате К опросов признаками из набора признаков опросав реверсивных счетчиках формирователей будет запомнено число совпадений признаков слова с признаками опроса. Если содержимое реверсивного счетчика 29 или 30 не равно нулю, то на выходе элементов ИЛИ 27 или 28 установится единичный сигнал. Поэтому те формирователи, содержимое реверсивных счетчиков 29 и 30 которых одновременно окажется не равно нулю в результате опросов, сформируют на выходах 20 единичный сигнал, те, на выходах этих формирователей установится сигнал (1, 1), означающий, что данная ячейка памяти находится в состоянии "готова"После К опросов в такое состояние установятся все15 ячейки памяти, из которых должна быть считана информация, а число считываний будет храниться в реверсивных счетчиках 29 и 30 формирователей 12 этих ячеек памяти. 20Режим считывания.Считывание осуществляется только из ячеек памяти в состоянии "готова". для этого на ячейку памяти подается сигнал по шине 8 разрешения считыва ния. Считываемая информация принимаеФся выходным регистром 2. Одновременно сигнал с шины разрешения считывания поступает на вход 15 соответ" ствующего формирователя 12 и через элементы И 25 и .26 на входы 33 и 34 реверсквных счетчиков 29 и 30. В результате содержимое каждого реверсивного счетчика 29 и 30 уменьшается на единицу. Если после опросов содер- З жимое реверсивного счетчика 29 было равно Ра содержимое ревереивного счетчика 30-е, и пусть В меньше а, то после 6 считываний содержимое счетчика 29 станет равно нулю, Поэтому после Р считываний на выходе элемен та ИЛИ 27 появится нулевой сигнал, что приведет к формированию нулевого сигнала на выходе 20 формирователя.Таким образом, после считываниясодержимого ячейки памяти в количест ве равном минимальному числу из числа совпадений первого и второго признаков, хранящихся в ячейке, с признаками из набора признаков опроса, на выходах формирователя 12 соответст- щ вующего этой ячейке установится сиг.нал (1.,0), означающий, что ячейка находится в состоянии "занято" и считывание из нее невозможно.Предлагаемое изобретение. позволяет;з1, За счет организации запоминания Фисла.совпадений ассоциативныхпризнаков слова с признаками из набора признаков опроса и запоминания числа считываний обеспечить считывание содержимого каждой ячейки памяти 66в количестве, равном минимальному числу из числа, совпадений первого ивторого ассоциативных признаков,хранящихся в ячейке, с признаками из некоторого произвольного набора приз наков опроса, причем если в наборе К (К1) признаков, то необходимый ассоциативный поиск осуществляется за К опросов.2. Чередовать опросы признаков и считывание из ячеек в состоянии "готова", т.е. решать поставленную задачу в процессе поступления признаков опроса, когда неизвестен момент времени поступления последнего К-го признака.формула изобретенияАссоциативное запоьщнающее устройство, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и ассоциативных элементов памяти, формирователи сигналов состояния ячеек памяти, каждый из которых содержит первый, второй и третий элементы И, триггер единичный выход которого подключен к первым входам второго и третьего элементов . И и к первому выходу формирователя сигналов состояния ячеек памяти, второй выход которого соединен с выходом первого элемэйга. Ипервый вход формирователя сигналов состояния ячеек йамяти соединен со вторым входом второго элемента И, второй вход - со вторым входом третьего элемента И, третий вход - с шиной.разрешения считывания, четвертый и пятый входы- соответственно с единичным и нулевым входами триггера, шестой вход - с третьими входами второго и третьего элементов И, первые входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения считывания, третьи - с шинами разрешения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным со входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и шины разрешения записи подключены к одним иэ выходов блока управления, первые и вторые входы формирователей сигналов состояния ячеек памяти соединены с соответствующими шинами совпадения, четвертые - с шинами разрешения записи, а пятые и шестыес другими выходами блока управления, первые и вторые выходы формирователей сигналов состояния ячеек памяти подключены к соответствующим входам блока управления, о т л и ч а ю - щ е е с я тем, что, с целью повышения быстродействия устройства, в нем формирователь сигналов состояния ячеек памяти содержит четвертый и пятый элементы И, элементы ИЛИ и реверсивные счетчики, причем выходыдо 875459 0 Тираж 648 Подписное ВНИИПИ Заказ 935 алкал ППП Патент,.г.ужгород,ул.Проектна первого и второго реверсивных счетчиков соединены соответственно с входами первого и второго элементовИЛИ, первые входЫ соответственнос выходами второго и третьего элементов Х, вторые входы - с выходамичетвертого и пятого элементов И,третьи входы с пятым входом формирователя сигналов состояния ячеекпамяти, третий вход которого подключен к одним из входов четвертогои пятого элементов И, другие входы которых соединены соответственно свыходами первого и второго элементовИпИ и с входами первого элемента И.Источники информации,принятые во внимание прифэкспертизе1, Однородные микроэлектронныеассоциативные процессоры. Под ред.И. В. Прангишвили, М., фСоветскоерадиоф, 1973, с. 11.2. Авторское свидетельство СССРпо заявке 9 2745595/18-24,кл, О 11 С 15/00, 1979 (прототип),