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

Изобретение относится к вычислительной технике и может быть исполь зовано при построении ассоциативных запоминающих устройств (АЗУ) большо емкости и ассоциативных параллельны процессоров в системах массовой обр ботки данных. Известно АЗУ, содержащее сдвиговый регистр признака опроса, выход которого подключен к одной группе в дов логи1еского блока, соединенного .с блоком детекторов, блок оперативной памяти, подключенный к другой группе входов логического блока l Недостатком этого устройства явл ется последовательная обработка запросов к ассоциативной памяти, при которой каждое обращение к АЗУ зани мает весь цикл памяти и следующий опрос может быть выполнен только после окончания предыдущего. Наиболее близким техническим решением к изобретению является АЗУ, содержащее .блок оперативной памяти с последовательной по разрядам и па раллельной по словам выборкой, соетоящей из множества по числу хранш.их слов рециркуляционных регистров сдвига, управляющий вход которых соединен с входом тактовых импульсов устройства, блок сравнения, состоящий из регистра признака опро са, логического блока,одна группа входов которого подключена к выхода блока оперативной памяти, а выходы к информационным входам блока детек торов 2 , Недостатком известного устройств является низкое быстродействие, поскольку -в течение цикла памяти может быть выполнен простой поиск для одного признака опроса, а для выпол нения сложных поисков требуется нес колько циклов памяти. Целью изобретения является.повышение быстродействия ассоциативного запоминающего устройства. Поставленная цель достигается тем что, в. ассоциативное запоминакяцее устройство, содержащее блок оперативной памяти, выход которого подключен к первому входу блбка сравнения, второй вход которого и вход бло ка сравнения являются одними из входов устройства, одним из выходов которого является выход блока сравнения, состоящего из регистра опроса вход которого является вторым входом блока сравнения, и последовательно соединенных логического блока и реги .стра результата поиска, выход которого является выходом блока сравнеЛИЯ, первым входом которого является один из входов логического блока, введены счетчик импульсов, регистры сдпига, дешифратор и дополнительные блоки сравнения, первые входы которых подк :почены к выходу блока оперативной памяти, вторые входы являются одними из входов устройства, а выходы - другими выходами устройства, третьи входы блоков сравнения соединены с выходом счетчика импульсов, четвертые входы подключены к выходам дешифратора, входы которого соединены с выходами регистров сдвига, первые входы которых и вход счетчика соединены с одними из входов устройстЕ а, другие входы которого являются вторыми входами регистров сдвига, причем в каждый блок сравнения введен мультиплексор, один из входов которого подключен к выходу регистра опроса,другой вход является третьим входом бхюка сравнения,а выход подключен к другому входу логического блока. При этом-блок оперативной памяти содержит последовательно соединенные основной и дополнительные накопители, дополнительный счетчик импульсов, триггер, элементы И, элементы ИЛИ и основной и дополнительный распределители импульсов, входы которых подключены к выходам элементов И, а выходы - к одним из входов накопи- , телей, выходы которых соединены с входами элементов ИЛИ, выходы которых являются выходами блока,выход дополнительного накопителя соединен с другим входом основного накопителя, вь1ход дополнительного счетчика подключен к входу триггера, выходы которого соединены с первыми входами элементов И, вторые входы которых и вход дополнительного счетчика импуль.сов объединены и являются входом блока. На фиг. 1 изображена.структурная схема предложенного АЗУ; нафиг. 2 и 3 возможные примеры выполнения блока . , оперативной памяти с последовательной по разрядам и параллельной по словам выборкой. АЗУ содержит (фиг.1) блок 1 оперативной памяти, счетчик 2 импульсов, дешифратор 3, группу регистров 4 сдвига, управляющие входы котсфых, а также вход счетчика 2,и регистров 4 подключены к управлякедему входу 5 устройства, блоки 6 сравнения, каждый из которых состоит из регистра 7 опроса, логического блока 8, регистра 9 результата поиска (индикатора) и мультиплексора 10. Блок 1 оперативной памяти с последовательной по разрядам и параллельной по словам выборкой получил свое название в соответствии со способом организации выборки информации в нем, т.е. функциональным назначением. На фиг, 2 этот блок изображен в виде множества рециркуляционных регистров 11 сдвига. Другой вариант блока 1 (фиг. 3) .включает основной 12 и дополнительный 13 накопители памяти, выполненные на запоминаклдих элементах с разрушанжцим считыванием, элементы ИЛИ 14, дополнительный счетчик 15 импульсов, триггер 16, первый 17 и второй 18 элементы И, основной 19 и дополнительный 20 распределители импульсов. Устройство имеет входы 21 и 22 и выход 23, Устройство работает следующим об разом. Пусть в исходном состоянии счетчик 2, регистры 4 установлены -в сос тояние О. На выходе 22 устройства зафиксирован код запроса на проведе ние ассоциативного поиска, признак которого записан в регистр 7 соотве ствующего блока 6, а все индикаторы 9 данного блока 6 находятся в состо янии 1. При этом О регистров 4 имеют разрядность т; в частности, при двоичном кодировании величина I (разрядность кода запроса) .определяется из равенства г log2N ; п 2, где J - -наименьшее целое число удовлетворяющее условию е logjN; N - Верхняя граница числа одн временно обрабатываемых запросов к АЗУ . Нулевое состояние регистров 4 означает, что запросов к АЗУ нет. Работа устройства начинается с приходом первого тактового импульса на вход 5. При этом счетчик 2 устанавливается в состояние 1, в.регистрах 4 происходит сдвиг информации на 1 разряд вправо, так что в первые разряды всех регистров 4 ока зывается записан код обрабатываемог запроса (в первый регистр - первый разряд кода, во второй - второй раз ряд кода и т.д.). На этом же такте в соответствие с состоянием счетчик 2 на один из входов логического бло ка 8 соответствующего блока 6 посту пают первые разряды всех слов из ма сива памяти блока 1, а на другие вх ды через мультиплексор 10 - первый разряд признака опроса из регистра 7. Блок 8 реализует логическую функ цию сложения по модулю два. Несовпа дение кода признака опроса с содержимым ячеек блока 1 устанавливает соответствующие индикаторы 9 в состоя ние О. Далее изменяется состояние счетчика 2 и происходит сравнение следующего разряда признака опроса и содержимого ячеек памяти блока 1, при этом в регистре 4 происходит очередной сдвиг на 1 разряд вправо одержимого регистров (пp отсутстии кода запроса в первые разряды аждого регистра 4 записываются О). Устройство работает таким образом m тактов, пока не будет проведено сравнение всех разрядов признака опроса с хранимой в блоке 1 информацией . На т-м такте на вход дешифратора 3 поступает код обработанного запроса и на соответствующем выходе дешифратора 3 появляется сигнал, фиксирующий состояние всех индикаторов 9 данного блока 6. Таким образом, в конце цикла ассоциативной выборки состояние 1 наблюдается только в тех индикаторах 9, в которых имелось полное совпадение кодов ассоциативных ячеек с признаком опроса. Работа предложенного устройства не изменяется и при наличии нескольких обращений к АЗУ. Для каждого нового признака опроса на некотором такте ассоциативного поиска происходит начальная установка кода зашроса на вход 22, что определяет выбор соответствующего блока 6, и выполняются запись признака опроса в регистр 7 и установка всех индикаторов 9 в состояние 1. Обработка данного запроса к АЗУ начинается с приходом очередного тактового импульса и происходит аналогично указанному независимо от состояния выполнения ассоциативного поиска в других блоках 6 . Единственное имеющее место отличие заключается в том, что для последующих обращений сравнение признака опроса и кодов хранимых слов происходит не с первого (как раньше)а с некоторого последующего разряда. Такое изменение оказывается возможным, поскольку последовательность выполнения операций поразрядного сравнения при простом поиске является произвольной. Рассмотрим работу устройства, когда блок 1 оперативной памяти выполнен на динамических МДП-схемах (фиг. 3). При этом используются накопители памяти с динамическими запоминающими ячейками на ВДП-транзисторах с разрушением информации при считывании. В исходном состоянии информация записана в основном накопителе 12, а дополнительный накопитель 13 хранит нулевую информацию, триггер 16 находится в состоянии 1. Работа блока 1 начинается с приходом на вход 5 тактовых импульсов, которые через элемент И 17 поступают на вход основного распределителя 19 импульсов. При этом происходит последовательный опрос разрядных столбцов накопителя 12, считанная информация записывается в соответствующие разряды дополнительного накопителя 13 и одновременно поступает через элементы ИЛИ 14 на выход блока 1. По истечению тактов, когда прозведено сравнение всех разрядов признака опроса с хранимой в блоке 1 информацией, основной накопитель 12 оказывается в состоянии хранения О, а вся информация содержится в дополнительном накопителе 13. Сигнал переноса с выхода счетчика 15 переводит триггер 16 в состояние О. В этом примере реализации блока 1 функции счетчиков 2 и 15 аналогичны и они могут быть совмещены. При сле дующем обращении к АЗУ информация в соответствии с поступающими через элемент И 18 на вход распределителя 20 импульсами переписывается из накопителя 13 в накопитель 12 и одновременно .поступает через элементы И 14 на выход блока 1. В целом АЗУ на МДП-схемах функционирует аналогично АЗУ на рециркуляционных регистрах 11 сдвига. Предложенная структура (фиг. 3) позволяет повысить быстродействие блока памяти путем разнесения в про странстве и совмещения во времени операций чтения и записи в основном и дополнительном накопителях. Кроме того, отпадает необходимость проведения периодического цикла регенерации хранимой информации, как это обычно место для запоминающих устройств на динамических МДП-схемах, так как хранимая информация циклически перезаписывается между накопителями. При этом в более общем случае выполнения ассоциативного поиска логический блок 8 включает также операции маскирования, что позволяет проводить сравнение только требуемых разрядов признака опроса и содержимого блока памяти. Таким образом, предлагаемое устройство позволяет применить для построения АЗУ большой емкости запоминающие ячейки с разрушением информации при считывании на основе использования разработанной в промышленности элементной базы .микроэлектронных запоминающих устройств (динамические МДП-схемы, регистры сдвига на ПЗС и др.) и значительно повысить эффективное быстродействие вследствие возможности одновременного проведения циклов простого поиска для ряда признаков опроса.

L

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

Фаг. 2