АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО Российский патент 1995 года по МПК G11C15/00 

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

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

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

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

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

Кроме того, ассоциативный элемент памяти содержит триггер, элементы И-НЕ с первого по пятый, элемент 2И-ИЛИ-НЕ, входы установки триггера в "1" и "0" подключены соответственно к выходам первого и второго элементов И-НЕ, первые входы которых соединены со вторыми входами третьего и четвертого и с первым входом пятого элементов И-НЕ и являются пятым входом ассоциативного элемента памяти, первый и второй входы которого подключены соответственно ко вторым входам первого и второго элементов И-НЕ, третий вход соединен с первыми входами третьего элемента И-НЕ и элемента 2И-ИЛИ-НЕ, четвертый вход подключен к первому входу четвертого элемента И-НЕ и четвертому входу элемента 2И-ИЛИ-НЕ, шестой и седьмой входы ассоциативного элемента памяти присоединены к третьим входам соответственно третьего и четвертого элементов И-НЕ, первый и второй входы/выходы ассоциативного элемента памяти подключены соответственно ко второму и пятому входам элемента 2И-ИЛИ-НЕ, третий вход которого соединен с четвертым входом третьего и вторым входом пятого элементов И-НЕ и подключен к прямому выходу триггера, инверсный выход которого присоединен к четвертому входу четвертого элемента И-НЕ и шестому входу элемента 2И-ИЛИ-НЕ, выход которого является вторым выходом ассоциативного элемента памяти, первым выходом которого является выход пятого элемента И-НЕ.

На фиг.1 представлена схема ассоциативного запоминающего устройства; на фиг.2 схема ассоциативного элемента памяти; на фиг.3 схема блока селектора и дешифратора адреса; на фиг. 4 схема блока регистров опроса и маскирования данных; на фиг.5 схема блока задания режимов ассоциативного поиска.

Устройство (фиг.1) содержит ассоциативный накопитель 1, в состав которого входят ассоциативные элементы 2 памяти со входами с первого 3 по седьмой 9, с первым 10 и вторым 11 выходами, с первым 12 и вторым 13 входами/выходами. Устройство также содержит блок 14 селектора и дешифратора адреса, блок 15 регистров опроса и маскирования данных, выходной регистр 16, регистр 17 фиксации реакций, анализатор 18 многократного совпадения, шифратор 19, блок 20 задания режимов ассоциативного поиска.

Выходы с первого 21 по четвертый 24 каждой группы блока 15 подключены соответственно ко входам с первого 3 по четвертый 6 ассоциативных элементов 2 памяти соответствующего столбца накопителя 1.

Первый 25 и второй 26 выходы каждой группы блока 20 соединены соответственно с шестыми 8 и седьмыми 9 входами ассоциативных 2 элементов памяти соответствующего столбца накопителя 1, а первый 27 и второй 28 выводы каждой группы этого блока подключены соответственно к первым 12 и вторым 13 входам/выходам элементов 2 соответствующего столбца накопителя 1.

29 первая группа входов данных устройства; 30 вторая группа входов данных устройства; 31 адресные входы устройства; 32 выход состояния устройства, указывающий на наличие "некоторого числа" совпадений в результате проведения ассоциативного поиска; 33 адресные выходы устройства; 34 выходы данных устройства.

На устройство подаются следующие управляющие сигналы:
35 сигнал записи в накопитель 1;
36 сигнал опроса накопителя 1;
37 сигнал выборки дешифратора блока 14;
38 сигнал записи в регистр блока 14;
39 сигнал сброса в "0" регистра блока 14;
40 сигнал записи в регистр опроса блока 15;
41 сигнал записи в регистр маскирования блока 15;
42 сигнал сброса в "0" регистров опроса и маскирования блоков 15 и 20;
43 сигнал стробирования отработанной и выборки следующей активной линии блоком 18, а также выдачи шифратором 19 на адресные выходы 33 адреса активной линии;
44 сигнал записи в регистр блока 20;
45 сигнал стробирования ассоциативного поиска по внешнему поисковому аргументу.

На фиг. 2 приведен пример реализации ассоциативного элемента 2 памяти, состоящего из RS-триггера 46, элементов И-НЕ с первого 47 по пятый 51, элемента 2И-ИЛИ-НЕ 52. На фиг.2 также представлены, не показанные на фиг.1 ограничительные элементы с первого 53 по четвертый 56 в виде резисторов, реализующие функцию "Монтажное И".

Блок 14 селектора и дешифратора адреса (фиг.3) содержит регистр 57, дешифратор адреса 58, группу элементов ИЛИ 59.

Блок 15 регистров опроса и маскирования данных (фиг.4) состоит из регистра 60 опроса, регистра 61 маскирования, первой 62 и второй 63 групп инверторов, первой 64 и второй 65 групп элементов И, группы элементов ИЛИ 66.

Блок 20 задания режимов ассоциативного поиска (фиг.5) содержит регистр 67, элементы ИЛИ первой 68 и второй 69 групп.

В [3] показаны примеры реализации анализатора многократного совпадения, в [4] регистра фиксации реакций.

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

В режиме записи по заданному адресу записываемое слово поступает со входов 29 и по сигналу 40 фиксируется в регистре 60 опроса блока 15. Затем в регистр 61 этого блока со входов 29 по сигналу 41 заносится маска (единицы в разрядах регистра маски определяют маскирование соответствующих разрядов накопителя). Одновременно с этим на входы 31 дешифратора подается m-разрядный код адреса строки накопителя (М=2.m число слов в накопителе).

И при подаче сигнала 35 записи в накопитель 1 и дешифрации адреса в дешифраторе 58 по сигналу 37 на входе 3 и 4 ассоциативных элементов 2 памяти поступит одна из следующих комбинаций сигналов: "10" код записи единицы, "01" код записи нуля, "00" код маскирования записи, а на входы 7 элементов 2 памяти выбранной строки накопителя подается активный уровень. И, таким образом, производится запись по выбранному адресу.

В случае записи слова по группе адресов в регистр 57 блока 14 со входов 30 по сигналу 38 записывается аргумент, в котором единицы соответствуют активизируемыми строкам накопителя 1.

В режиме считывания информации по заданному адресу на входы 31 дешифратора 58 блока 14 подается код адреса считываемой строки, который дешифрируется по сигналу 38, активизируя входы 7 элементов 2 памяти считываемой строки ассоциативного накопителя. Считываемое слово в инверсном коде фиксируется в выходном регистре 16 по сигналу 36 опроса накопителя. Регистр 57 блока 14 в этом режиме должен быть обнулен.

В режиме ассоциативного маскируемого поиска по внешнему поисковому аргументу аргумент поиска поступает со входов 29 и по сигналу 40 фиксируется в регистре 60 опроса блока 15. Затем в регистр 61 маскирования этого блока записывается маска по сигналу 41. На всех выходах блока 14 должен быть установлен уровень логического нуля, что исключает влияние сигналов на выходах элементов И 49 и 50 на работу устройства в этом режиме. И при подаче сигнала 36 опроса накопителя 1 на входы 5 и 6 всех элементов 2 памяти поступит один из следующих признаков опроса: "01" сравнение с единицей, "10" сравнение с нулем, "00" маскирование сравнения. В первых двух случаях сигнал единичного уровня сохранится на выходе 11 элемента 2 памяти в случае совпадения признака опроса с битом, хранимым в этом элементе 2 памяти, и выход 11 этого элемента 2 памяти обнулится в противном случае. При маскировании сравнения на выходе 11 элемента 2 памяти сохранится единичный уровень вне зависимости от содержимого этой ячейки памяти. Результат ассоциативного поиска фиксируется в регистре 17 фиксации реакций по заднему фронту сигнала 36. При этом, если выявятся слова, совпавшие с аргументом поиска, то соответствующие им разряды регистра 17 установятся в единичное состояние.

Анализатор 18 многократного совпадения служит для приоритетной выборки одной из активных линий регистра 17. При этом наивысшим приоритетом из аргументов обладает аргумент с нулевым адресом.

Адрес активной линии, выбранной анализатором 18 многократного совпадения, кодируется шифратором 19 и выдается на адресные выходы 33 устройства по сигналу 43. Повторной подачей этого сигнала осуществляется стробирование отработанной инициализация следующей активной линии анализатором многократного совпадения.

В режиме ассоциативного маскируемого поиска с использованием слов из ассоциативного накопителя в качестве аргументов поиска перед подачей на устройство сигнала 36 опроса накопителя и сигнала 45 стробирования ассоциативного поиска по внешнему поисковому аргументу в регистр 61 блока 15 записывается маска, определяющая маскирование разрядов накопителя этом режиме. И при подаче сигналов 36, 45 на входы 5 и 6 всех элементов 2 памяти, кроме замаскированных, подается сочетание "11", запрещающее сравнение с внешним поисковым аргументом. Одновременно этим на входы 31 дешифратора 58 подается код адреса строки накопителя, являющейся поисковым аргументом. При дешифрации этого кода по сигналу 37 на входы 7 ассоциативных элементов 2 памяти этой строки накопителя подается уровень логической единицы. При этом, если в элементе памяти источнике бита поискового аргумента записана единица, то обнулится выход элемента И 49 этого элемента 2 памяти, а следовательно, обнулятся выводы 12 элементов 2 памяти соответствующего столбца накопителя, инициируя процесс сравнения с единицей содержимого всех остальных элементов памяти данного столбца накопителя. В том случае, если в каком-либо элементе 2 памяти указанного столбца накопителя хранится нуль, то выход элемента 2И-ИЛИ-НЕ 52, а, следовательно, и выход 11 этого элемента 2 памяти обнулится, указывая на несовпадение; если же в нем хранится единица, то на выходе 11 сохранится единичный потенциал. В случае, если в элементе 2 памяти источнике бита поискового аргумента записан нуль, то обнулится выход элемента И 50 этого элемента 2 памяти, а, следовательно, обнулятся выводы 13 элементов 2 памяти соответствующего столбца накопителя, инициируя процесс сравнения с нулем содержимого всех остальных элементов памяти данного столбца накопителя. В том случае, если в каком-либо элементе 2 памяти указанного столбца накопителя хранится нуль, то на выходе 11 этого элемента 2 памяти сохранится уровень логической единицы; если же в нем хранится единица, то на выходе 11 появится нулевой уровень, указывая на несовпадение. При маскировании на входах 5 и 6 элементов 2 памяти рассматриваемого столбца накопителя будет подано сочетание сигналов "00", фиксирующее на выходах 11 элементов 2 памяти этого столбца уровень логической единицы.

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

До осуществления режима коньюнктивного ассоциативного маскируемого поиска регистр 67 блока 20 должен быть обнулен, в регистр 61 блока 15 записана маска, а в регистр 57 блока 14 аргумент, в котором единицы соответствуют словам накопителя, участвующим в формировании поискового аргумента. И при подаче на устройство сигнала 36 опроса накопителя и сигнала 45 стробирования ассоциативного поиска по внешнему поисковому аргументу в регистре 17 фиксации реакций запишется результат коньюнктивного ассоциативного маскируемого поиска.

Рассмотрим подробнее работу устройства в этом режиме на примере ассоциативных элементов памяти какого-либо столбца накопителя. На входы 5 и 6 этих элементов памяти подается сочетание сигналов "11". В начальном состоянии на входы 8 и 9, а также входы/выходы 12 и 13 подается уровень логической единицы. Единичный уровень подается также на входы 7 ассоциативных элементов памяти столбца накопителя, являющихся источниками битов поискового аргумента. При этом, если во всех элементах памяти источниках рассматриваемого столбца накопителя записаны единицы, то на входах/выходах 12 и 13 всех элементов памяти столбца установится комбинация сигналов "01", что соответствует единичному значению бита поискового аргумента. И содержимое всех элементов памяти данного столбца накопителя сравнивается с единицей (см. предыдущий режим). Если же хотя бы в одном элементе памяти источнике записан нуль, то на выходе элемента И-НЕ 50 этой и, следовательно, на входе/выходе 13 установится нулевой потенциал, и на третий вход элементов И-НЕ 49 со входа 8 всех элементов памяти указанного столбца накопителя с соответствующего выхода 25 блока 20 поступит сигнал нулевого уровня, устанавливающий на входах/выходах 12 элементов памяти столбца нулевой потенциал. Таким образом, на входах/выходах 12 и 13 элементов памяти данного столбца установится комбинация сигналов "10", соответствующая нулевому значению бита поискового аргумента. И содержимое всех элементов памяти данного столбца накопителя в этом случае будет сравниваться с нулем.

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

До осуществления режима дизъюнктивного ассоциативного маскируемого поиска во все разряды регистра 67 блока 20 должны быть занесены единицы, в регистр 61 блока 15 записана маска, а в регистр 57 блока 14 аргумент, в котором единицы соответствуют словам накопителя, участвующим в формировании поискового аргумента. И при подаче на устройство сигнала 36 опроса накопителя и сигнала 45 стробирования ассоциативного поиска по внешнему поисковому аргументу в регистре 17 фиксации реакций запишется результат дизъюнктивного ассоциативного маскируемого поиска.

Рассмотрим подробнее работу устройства в этом режиме на примере ассоциативных элементов памяти какого-либо столбца накопителя. На входы 5 и 6 этих элементов памяти подается сочетание сигналов "11". В начальном состоянии на входы 8 и 9, а также входы/выходы 12 и 13 подается уровень логической единицы. Единичный уровень подается также на входы 7 ассоциативных элементов памяти столбца накопителя, являющихся источниками битов поискового аргумента. При этом, если во всех элементах памяти источниках рассматриваемого столбца накопителя записаны нули, то на входах/выходах 12 и 13 всех элементов памяти столбца установится комбинация сигналов "10", что соответствует нулевому значению бита поискового аргумента. И содержимое всех элементов памяти данного столбца накопителя сравнивается с нулем. Если же хотя бы в одном элементе памяти источнике записана единица, то на выходе элемента И-НЕ 49 этой и, следовательно, на входе/выходе 12 установится нулевой потенциал, и на третий вход элементов И-НЕ 50 со входа 9 всех элементов памяти указанного столбца накопителя с соответствующего выхода 26 блока 20 поступит сигнал нулевого уровня, устанавливающий на входах/выходах 13 элементов памяти столбца единичный потенциал. Таким образом, на входах/выходах 12 и 13 элементов памяти данного столбца установится комбинация сигналов "01", соответствующая единичному значению бита поискового аргумента. И содержимое всех элементов памяти данного столбца накопителя в этом случае будет сравниваться с единицей.

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

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

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

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