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

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

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

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

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

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

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

На фиг. 1 представлена функциональная

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

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

5 19 и вторые 20 элементы ИЛИ групп. Каждый АЗЭ 4 содержит (фиг. 2) элементы И 21-26, элементы ИЛИ 27-29, элемент НЕ 30 и триггер 31.

Функциональная схема предлагаемого устройства содержит также (фиг. 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)-ю (где l-K- m) заняты информацией, к-я строка свободна, а состояние остальных строк безразлично. На занятость строки указывает наличие сигнала «1 на выходе соответствующего триггера 15. Таким образом, на прямых выходах элементов И 16 групп с первой по (к-1)-ю появляются сигналы «1, а На выходах элементов И-НЕ 16 всех последующих групп - сигналы «О,, так как на выходе к-го триггера 15 находится сигнал «1. В результате будут подготовлены условия для записи только в к-ю строку накопителя 3, так как на два входа элемента И 17 к-ой группы поданы сигналы «1.

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

При подаче сигнала «1 на входы 36 он появляется только на выходе элемента И 17 к-ой группы. Этот сигнал поступает на входы 7 всех АЗЭ 4 к-ой строки накопителя 3 через элемент ИЛИ 19 к-ой группы и разрещает запись в эту строку накопителя 3. Слово, подлежащее записи, подается с регистра 1 на входы 10 и И каждого столбца накопителя 3 таким образом, что прямой код каждого разряда подается на вход 10, а обратный код этого же разряда - на вход

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

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

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

каждого столбца накопителя 3 необходимо 5

подать сигнал «1, а на вход 10 каждого столбца - сигнал «О. После то-, го, как на выходе 6 последнего АЗЭ 4 к-ой строки накопителя 3 появится сигнал «1, на вход 32 к-ой строки подается сигнал «1,

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

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

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

-Технико-экономическое преимущество предлагаемого ассоциативного запоминающего устройства по сравнению с прототипом заключается в том, что оно позволяет

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

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

35

риг.{ 3

Cf)US.l