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

(54) АССОЦИАТИВНОЕ ЗАПОМИНАОДЕЕ УСТРОЙСТВО

, .

Изобретение относится к запоминающим устройствам.

Известно ассоциативное запом€нающее устройство (АЗУ), содержащее входной блок, выходной блок, блок управления , ячейки памяти основной информации и ассоциативных признаков, шины опроса записи, шиш считывания, шины совпадения, шиша разрешения записи и цшнн раз;решения считывания tl.

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

Наиболее близким техническим решением Кизобретению является АЗУ, с6держащее входной регистр, выходной регистр, блок управления, адресные элементы памяти, ассоциативные элементы памяти, служащие для хранения первых и вторых признаков, формирователи сигналов состояния ячеек памяти, шины разрешения записи, шины разрешения считывания, шины опросазаписи, шины считыаания, шины совпадения, причем первые входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разраиения считывания, третьи - с шинами разрешения записи, выходы адресных и первые выходы ассоциативных элементов пгшяти подключены к соответствующим

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

20 третьи входы - с шинами разрешения считывания, четвертые входы - с шинги ш разрешения записи, а пятые и шестые - с другими выходами блока управления, первые и вторые выходы

25 формирователей сигнгшов состояния ячеек памяти подключены к соответствующим входам блока управления.

Кроме того, каждый формирователь сигналов состояния ячеек памяти содер жит триггеры, элементы И и ИЛИ,причем

30

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

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

Цель изобретения - повышение быстродействия и расширение области примнения устройства путем обеспечения считывания содержимого каждой ячейки памяти в количестве,равном минимальному числу из числа совпадений первого и второго ассоциативных признаков, хранящихся в ячейке, с признаками из некоторого произвольного набор признаков опроса, содержащего К признаков .(к 1) и осуществление необходимого ассоциативного поиска за К опросов.

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

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

На фиг . 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, служащими для прибавлек содержимому счетчиков, и вторыми входами 33 и 34, служащими для вычитания 1, и третьими входами 35 и 36, служащими для установ ки в нулевое состояние, и выходами 37 и 38. Первые 13 и вторые 14 зходы формирователей 12 соединены с соответст вующими шинами 11 совпадения, третьи входы 15 - с шинами 8 разрешения считывания, четвертые входы 16 - с шинами 7 разрешения записи, пятые 1 и шестые 18 - с cooтвeтcтвvючIими яы ходами блока 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, входы 33 и 34 - с выходами элементов И 25 и 26, а входы 35 и 26 соединены межд собой и с входом 17 формирователя 12 сигналов состояния ячеек памяти, вхо ,15 которого подключен к из входов элементов И 25 и 26, другие входы которых соединены соответствен но с выходами элементов ИЛИ 27 и 28 и с входс№4и элемента И 22. АЗУ работает следующим образом. Начальная установка состояния всех ячеек памяти АЗУ. Из блока 3 управления на входы 17 всех формирователей 12 выдается сигнал Сброс. В результате триггер 21 и реверсивные счетчики 29 и 30 каждого формирователя 12 перейдут в нулевое состояние. На выходах элементов ИЛИ 27 и 28 установятся нулевые сигналы,- так как содержимое каждого из реверсивных счетчиков 29 и 30 равно нулю. Поэтому на выходах 19 и 20 всех формирователей 12 установятся нулевые значения сигналов. Значения сигналов на выходах любого формирователя 12 будем обозначать . парой (S, 5о),где 5, 5 - значения сигналсУв на выходах 19 и 20. При описании работы АЗУ будем также считать, что элементы памяти, расположенные в одной строке (т.е. соединен ные с одним и тем же формирователем 12), составляют одну ячейку памяти, соответствующую одному слову. Таким образом, после посылки сиг нала Сброс на все формирователи 12, на их выходах установятся сигналы равные (0,0), означающие, что все ячейки памяти находятся в состоянии свободна. Режим записи. Запись производится только в ячейки, находящиеся в состоянии свободна. Блок 3 управления Xвыбирает одну из этих ячеек памяти и вырабатывает сигнал по соответствующей шине 7 разрешения записи. Одновременно основная информация и признаки выдаются из входного регистра 1 на соответствующие шины 9 опроса-записи. В результате основная информация и признаки записываются в выбранную ячейку памяти. Сигнал с шины 7 разрешения записи поступает также на вход 16 фор1 1ирователя 12 и устанавливают триггер 21 в единичное состояние.На выходах этого формир1Ователя,сформируется сигнал (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), означакмций, что данная ячейка памяти находится в сос тоянии готова. После К опросов в такое состояние установятся все ячейки памяти, из которых должна быть считана информация, а число считываний будет храниться в реверсивных счетчиках 29 и 30 формирователей 12 этих ячеек памяти. Режим считывания. . Считывание осуществляется только из ячеек памяти в состоянии готова Для этого на ячейку памяти подается сигнал по шине 8 разрешения считывания. Считываемая информация пр инимае±ся выходным регистром 2. Одновременно сигнал с шины разрешения считы вания поступает на вход 15 соответствующего формирователя 12 и через элементы И 25 и .26 на входы 33 и 34 реверсивных счетчиков 29 и 30. В результате содержимое каждого реверсив ного счетчика 29 и 30 уменьшается на единицу. Если после опросов содер жимое реверсивного счетчика 29 было равно содержимое реверсивного счетчика 30-ш, и пусть I меньше т, то после Е считываний содержимое сче чика 29 станет равно нулю.- Поэтоцу после Е считываний на выходе элемента ИЛИ 27 появится нулевой сигнал, что приведет к формированию нулевого сигнала на выходе 20 формирователя. Таким образом, после считывания содержимого ячейки памяти в количест ве равном минимальному числу из числа совпадений первого и второго приз наков, хранящихся в ячейке, с призн ками из набора признаков опроса, на выходах формирователя 12 соответствукмцего этой ячейке установится сигнал (1,0), означающий, что ячейка находится в состоянии занято и . считывание из нее невозможно. Предлагаемое изобретение позволяе 1. За счет организации запоминания числа совпадений ассоциативных признаков слова с признаками из набо ра признаков опроса и запоминания числа считываний обеспечить считыва ние содержимого каждой ячейки памят в количестве, равном минимальному ч лу из числа совпадений первого и второго ассоциативных признаков,хра нящихся в ячейке, с признаками из н которого произвольного набора признаков опроса, причем еспи в наборе К (К 1) признаков, то необходимый ассоциативный поиск осуществляется за К опросов. 2.. Чередовать опросы признаков и считывание из ячеек в состоянии готова, т.е. решать поставленную задачу в процессе поступления признаков опроса, когда неизвестен момент времени поступления последнего К-го признака., Формула изобретения ; Ассоциативное запоминающее устройство, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и ассоциативных элементов памяти, формирователи сигналов состояния ячеек памяти, каждый из которых содержит первый, второй и третий элементы И, триггер единичный выход которого подключен к первым входам второго и третьего элементов И и к первому выходу формирователя сигналов состояния ячеек памяти, втр рой выход соединен с выходом первого эйемейТа И,,первый вход формирователя сигналов состояния ячеек памяти со(еданен со вторым входом второго элемента, И, второй вход - со ВТofSiM входе трётье.гр элемента И, Третий вход - с шинсхй разрешения считывйния, четвертый и пятый входы сбответственно с единичным и нулевым входами триггера, шестой вход - с третьими входами второго и третьего элементов И, первы е входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разр ления; считывания j третьи - с шингйии разрешения записи, выходы адресных и пертаы& выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным со входами выходного регистра, вторые выхоДы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разреиения считывания и шины разройения записи подключены к одним из выходов блока управления, первые и вторые входы формирователей сигналов состояния ячеек памяти соединены с соответствующими шинами совпадения, четвертые - с шинами разрешения записи, а пятые и шестые с другими выходами блока управления, первые и вторые выходы формирователей сигналов состояния ячеек памяти подключены к соответствующим входам блока управления, отличающ ее-с я тем, что, с целью повьииения быстродействия устройства, в нем формирователь сигналов состояния ячеек памяти содержит четвертый и пятый элементы И, элементы ИЛИ и реверсивные счетчики, причем выходы

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

которых соединены соответственно с выходами первого и второго элементов апи и с входами первого элемента И.

Источники информации, принятые во внимание приэкспертизе

o кл, G 11 С 15/00, 1979 (прототип).

Фи2.1