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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) . (И) 3(51) G 11 С 15/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

1

Р

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н ABTOPCKOMY СВИДЕТЕЛЬСТВУ (21 ) 3477921/18-24 (22) 03.08.82 (46) 23.11.83. Вюл, 9 43 (72) Ю.A. Тимошенко и С.A. Тимошенко (71) Одесский ордена Трудового Красного Знамени политехнический институт и Киевский ордена Ленина политехнический институт (53) 681.327.6(088.8) (56) 1. Авторское свидетельство СССР

)) 610175, кл. G 11 С 15/00, 1977.

2. Фет Н.И. Параллельные процессы для управляющих систем. М., "Энергоиздат", 1981, с. 112-114 (прототип). (54 )(57 ) 1 . АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее блок оперативной памяти, выход которого подключен к первому входу блока сравнения, второй вход которого и вход блока сравнения являются одними из входов устройства, одним из выходов которого является вы од блока сравнения, состоящего из регистра опроса, вход которого является вторым входом блока сравнения, и последовательно соединенных логического блока и регистра результата поиска, выход которого является выходом блока сравнения, первым входом которого является один из входов логического блока, о т л.и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены счетчик импульсов, регистры сдвига, дешифратор и дополнительные блоки сравнения, первые входы которых подключены к выходу блока оперативной памяти, вторые входы являются одними из входов устройства, а выходы - други.ми выходами устройства, третьи входы блоков сравнения соединены с выходом счетчика импульсов, четвертые входы подключены к выходам дешифратора, входы которого соединены с выходами регистров сдвига, первые входы которых и вход счетчика соединены с одними из входов устройства, другие входы которого являются вторыми входами регистров сдвига, причем в каждый блок сравнения введен мультиплексор, один из входов которого подключен к выходу регистра опроса, другой вход является третьим входом блока сравнения, а выход подключен к другому входу логического блока. щ

Р

2. Устройство по п.1, о т л и ч а ю цт е е с я тем, что блок оперативной памяти содержит последовательно соеднненнее осноеной н дололнительный накопители, дополнительный счетчик импульсов, триггер, элементы ф

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

1056269

20

45.

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

Известно АЗУ, содержащее сдвиговый регистр признака опроса, выход которого подключен к одной группе входов логического блока, соединенного с блоком детекторов, блок оперативной памяти, подключенный к.другой группе входов логического блока f1) .

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

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

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

Целью изобретения является повышение быстродействия ассоциативного запоминаюцего устройства .

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

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

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

На фиг. 1 изображена. структурная схема предложенного АЗУ; на фнг. 2 и 3— возможные примеры выполнения блока оперативной памяти с последовательной по разрядам и параллельной по словам выборкой.

АЗУ содержит (фиг.1) блок 1 оперативной памяти, счетчик 2 импульсов, дешифратор 3, группу регистров 4 сдвига, управляюцие входы которых, а также вход счетчика 2,и регистров

4 подключены к управляюцему входу 5 устройства, блоки 6 сравнения, каждый из которых состоит из регистра 7 опроса, логического блока 8, регистра 9 результата поиска (индикатора ) и мультиплексора 10.

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

1056269

Другой вариант блока 1 (фиг. 3) ,включает основной 12 и дополнительный 13 накопители памяти, выполненные на запоминающих элементах с разрушающим считыванием, элементы

ИЛИ 14, дополнительный счетчик 15 импульсов, триггер 16, первый 17 и второй 18 элементы И, основной 19 и дополнительный 20 распределители импульсов. Устройство имеет входы

21 и 22 и выход 23.

Устройство работает следующим образом.

Пусть в исходном состоянии счетчик 2, регистры 4 установлены -в состояние "0". На выходе 22 устройства зафиксирован код запроса на проведение ассоциативного поиска, признак которого записан в регистр 7 соответствующего блока б, а все индикаторы

9 данного блока б находятся в состоянии "1".

При этом 8 регистров 4 имеют разрядность m; в частности, при двоичном кодировании величина 2 (разрядность кода запроса) .определяется из равенства

10 где J Et — наименьшее целое число Е удовлетворяющее условию (> 1о8дИ;

N — верхняя граница числа одно.временно обрабатываемых запросов к АЗУ, Нулевое состояние регистров 4 означает, что запросов к АЗУ нет.

Работа устройства йачинается с приходом первого тактового импульса на вход 5. При этом счетчик 2 устанавливается в состояние "1", в регистрах 4 происходит сдвиг информации на 1 разряд вправо, так что в первые разряды всех регистров 4 оказывается записан код обрабатываемого запроса (в первый регистр — первый разряд кода, во второй — второй разряд кода и т.д.). На этом же такте в соответствие с состоянием счетчика

2 на один из входов логического блока 8 соответствующего блока б поступают первые разряды всех слов из массива памяти блока 1, а на другие входы через мультиплексор 10 - первый разряд признака опроса из регистра 7 °

Блок 8 реализует логическую функцию сложения по модулю два. Несовпадение кода признака опроса с содержимым ячеек блока 1 устанавливает соответствующие индикаторы 9 в состояние ".0". Далее изменяется состояние счетчика 2 и происходит сравнение следующего разряда признака опроса и содержимого ячеек памяти блока 1, при этом в регистре 4 происходит очередной сдвиг на 1 разряд вправо

2 = )log Н(; n ) 2, 15

Зо

65 содержимого регистров (при отсутствии кода запроса в первые разряды каждого регистра 4 записываются "0", .

Устройство работает таким образом m тактов, пока не будет проведено сравнение всех разрядов признака опроса с хранимой в блоке 1 информацией. На ш-м такте на вход дешифратора 3 поступает код обработанного запроса и на соответствующем вы.ходе дешифратора 3 появляется сиг нал, фиксирующий состояние всех индикаторов 9 данного блока б. Таким образом, в конце цикла ассоциативной выборки состояние "1" наблюдается только в тех индикаторах 9, в которых имелось полное совпадение кодов ассоциативных ячеек с признаком опроса.

Работа предложенного устройства не изменяется и при наличии нескольких обращений к ЛЗУ. Для каждого нового признака опроса на некотором такте ассоциативного поиска происходит начальная установка кода запроса на вход 22, что определяет выбор соответствующего блока б, и выполняются запись признака опроса в регистр 7 и установка всех индикаторов 9 в состояние "1". Обработка данного запроса к АЗУ начинается с приходом очередного тактового импульса и происходит аналогично указанному независимо от состояния выполнения ассоциативного поиска в других блоках 6. Единственное имеющее место отличие заключается в том, что для последующих обращений сравнение признака опроса и кодов хранимых слов происходит не с первого (как раньше) а с некоторого последующего разряда. Такое изменение оказывается возможным, поскольку последовательность выполнения операций поразрядного сравнения прн простом поиске является произвольной.

Рассмотрим работу устройства, когда блок 1 оперативной памяти выполнен на динамических МДП-схемах (фиг. 3). При этом используются накопители памяти с динамическими запоминающими ячейками на МДП-транзисторах с разрушением информации при считывании.

В исходном состоянии информация записана в основном накопите-. ле 12, а дополнительный накопитель 13 хранит нулевую информацию, триггер 16 находится в состоянии

"1". Работа блока 1 начинается с приходом на вход 5 тактовых импульсов, которые через элемент И 17 поступают на вход основного распределителя 19 импульсов. При этом происходит последовательный опрос разрядных столбцов накопителя 12, 1056269 считанная информация записывается в соответствующие разряды дополнительного накопителя 13 и одновременно поступает через элементы ИЛИ

14 на выход блока 1. По истечению тактов, когда прозведено сравнение всех разрядов признака опроса с хранимой в блоке 1 информацией, основной накопитель 12 оказывается в состоянии хранения "0", а вся информация содержится в дойолнительном на- 10 копителе 13. Сигнал переноса с выхо-. да счетчика 15 переводит триггер 16 в состояние "0".

В этом примере реализации блока 1 функции счетчиков 2 и 15 аналогичны, 15 и они могут быть совмещены. При следующем обращении к АЗУ информация в соответствии с поступающими через элемент IE 18 на вход распределителя

20 импульсами переписывается из на- 20 копителя 13 в накопитель 12 и одновременно. поступает через элементы ИЛИ

14 на выход блока 1. В целом АЗУ на

МДП-схемах функционирует аналогично

АЗУ на рециркуляционных РегистРах 25

11 сдвига.

Предложенная структура (фиг. 3) позволяет повысить быстродействие блока памяти путем разнесения в пространстве и совмещения во времени операций чтения и записи в основном и дополнительном накопителях. Кроме того, отпадает необходимость проведения периодического цикла регенерации хранимой информации, как это обычно имеет место для запоминающих устройств на динамических

МДП-схемах, так как хранимая информация циклически перезаписывается между накопителями.

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

Таким образом, предлагаемое устройство позволяет применить для построения АЗУ большой емкости запо-, минающие ячейки с разрушением информации при считывании на основе использования разработанной в промышленности элементной базы микроэлектронных запоминающих устройств (динамические МДП-схемы, регистры сдвига на ПЗС и др. ) и значительно повысить эффективное быстродействие вследствие возможности одновременного проведения циклов простого поиска для ряда признаков опроса.

1056269

Составитель B. Рудаков

Редактор В. Данко Техреду.Гергель Корректор С. Шекмар

Заказ 9315/46 Тираж 594 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4