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

 

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

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

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

РЕСПУБЛИК (19) (11) 3 (Я) 1 1 00

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3562023/18-24 (22) 03.03.83 (46) 30.05 .84. Бюл. № 20 (72) А. П. Малышев и С. М. Окулов (53) 681.327(088.8) (56) 1. Авторское свидетельство СССР № 87?616, кл. G 11 С 15/00, 1981.

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

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

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

095237

20

30

40

Изобретение относится к вычислительной технике и может быть использовано при построении ассоциативных запоминающих устройств.

Известно ассоциативное запоминающее устройство, которое содержит входные и выходные регистры, ассоциативные запоминающие матрицы и блоки управления (1).

Однако известное устройство не позволяет выполнять операции поиска и записи информации в первую свободную строку, считывания информации со стиранием строки ассоциативной запоминающей матрицы.

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

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

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

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

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

На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2— функциональная схема ассоциативного запоминающего элемента матричного накопителя.

Предлагаемое ассоциативное запоминающее устройство содержит входной регистр 1, выходной регистр 2, матричный накопитель 3 состояший из ассоциативных запоминаюших элементов (АЗЭ) 4, имеющих управляющие вход 5 и выход 6, вход 7 и выход 8 управления записью, информационные входы 9 — 11 и выходы 12 — 14. Устройство содержит также триггеры 15, элементы И-НЕ 16, первые

17 и вторые 18 элементы И групп, первые

19 и вторые 20 элементы ИЛИ групп. Каждый АЗЭ 4 содержит (фиг. 2) элементы

И 21 — 26, элементы ИЛИ 27 — 29, элемент

НЕ 30 и триггер 31.

1095237

Функциональная схема предлагаемого устройства содержит также (фиг. 1) входы 32 сброса, входы 33 управления считыванием, первый 34 и второй 35 установочные входы и вход 36 управления записью устройства.

Число групп элементов ИЛИ 19 и 20, триггеров 15 элементов И-НЕ 16 и элементов И 17 и 18 равно числу m строк накопителя 3.

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

Ассоциативное запоминающее устройство позволяет производить следующие операции: запись в первую свободную строку; считывание; ассоциативный поиск и поиск максимума, причем дополнительно вводится операция считывания со стиранием строки накопителя 3 (фиг. 1), а операция записи в первую свободную строку не имеет ограничений на порядок расположения свободных строк. Первоначально на все входы ассоциативных зайоминающих элементов 4, а также на все входы 32 — 36 устройства поданы сигналы «О». Для правильного выполнения операций считывания со стиранием строки и записи в первую свободную строку накопителя 3 предварительно необходимо подать на вход 35 и на вход 34 соответственно сигналы «О» и «1». В этом случае осуществляется поиск первой свободной строки накопителя 3, а также подготавливаются условия для выполнения операции считывания со стиранием строки.

Пусть, например, строки накопителя 3 с первой по (к — 1)-ю (где 1«x m) заняты информацией, к-я строка свободна, а состояние остальных строк безразлично. На занятость строки указывает наличие сигнала «1» на выходе соответствующего триггера 15.

Таким образом, на прямых выходах элементов И 16 групп с первой по (к — 1)-ю появляются сигналы «1», а на выходах элементов И-НЕ 16 всех последующих групп — сигналы «О»,, так как на выходе к-го триггера 15 находится сигнал «1». В результате будут подготовлены условия для записи только в к-ю строку накопителя 3, так как на два входа элемента И 17 к-ой группы поданы сигналы «1».

Запись в первую свободную строку.

При подаче сигнала «1» на входы 36 он появляется только на выходе элемента

И 17 к-ой группы. Этот сигнал поступает на входы 7 всех АЗЭ 4 к-ой строки накопителя 3 через элемент ИЛИ 19 к-ой группы и разрешает запись в эту строку накопителя 3.

Слово, подлежащее записи, подается с регистра 1 на входы 10 и 11 каждого столбца накопителя 3 таким образом, что прямой код каждого разряда подается на вход 10, а обратный код этого же разряда — на вход

11 соответствующего столбца накопителя 3.

После записи информации в к-ю строку снимается сигнал «1» на входе 36. При этом к-ый триггер 15 устанавливается в состояние «1» и производится поиск новой свободной строки накопителя 3.

Считывание со стиранием строки.

Пусть необходимо осуществить операцию считывания со стиранием над к-ой строкой накопителя 3. Для этого на вход 5 АЗЭ 4 первого столбца накопителя 3 и на входы 9 и 11 каждого столбца накопителя 3 необ.ходимо подать сигнал «1». а на вход 10 каждого столбца накопителя 3 необходимо подать сигнал «1», а на .вход !0 каждого столбца — сигнал «О». После то-, го, как на выходе 6 последнего АЗЭ 4 к-ой строки накопителя 3 появится сигнал «1», на вход 32 к-ой строки подается сигнал «1», причем этот сигнал распространяется по элементам ИЛИ 20- групп с к-ой по m-ую.

Сигнал «1» на выходе элемента ИЛИ 20 последней m-ой строки разрешает появление сигнала «1» на выходе элемента И 18 к-ой группы, и. следовательно, на входе 7 ассоциативного запоминающего элемента 4 первого столбца к-ой строки накопителя 3:

Этим сигналом осуществляется сброс триггеров 31 (фиг. 2) АЗЭ 4 к-ой строки накопителя 3, а на регистре 2 остается информация, считанная из к-й строки. Наличие задержки (элемент ИЛИ 20) в подаче сигнала «1» на входы 7 ассоциативных запоминающих элементов 4 к-ой строки обеспечивает полное считывание строки накопителя 3 к моменту ее сброса, так как скорость считывания строки по столбцам неодинакова.

В предлагаемом устройстве за счет включения в состав триггеров 15, которые хранят признак состояния строки накопителя 3, исключается сквозной перенос проверки состояния строки, причем, по сравнению с прототипом, в каждом АЗЭ 4 аннулируются один выход и один вход. Сокращение выводов

АЗЭ 4 особенно важно при реализации их в виде интегральных схем. Кроме того, триггеры 5, элементы И 17 и 18, элементы ИЛИ

19 и 20, элементы И-НЕ 16 обладают автономностью по отношению к типу накопите-, ля 3, так как связаны с ним только двумя входами.

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

Таким образом, предлагаемое устройство позволяет выполнять новую операцию считывания со стиранием строки матричного накопителя 3, причем операции, присущие прототипу, сохраняются, а введение новой опе1095237 рации осуществляется без увеличения yrtpaa semих входов ассоциативных запоминающих элементов 4.

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

1095237

Редактор Т. Парфенова

3aказ 3607/34

Составитель Т. Зайцева

Техред И. Верес Корректор Л. Пилипенко

Тираж 575 Подписное

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

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

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