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

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

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

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

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

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

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

Входы 22 и 23 являются соответственно первой и второй группами информационных входов устройства, а выходы 24 и 25 соответственно первой и второй группами информационных выходов устройства. На фиг.1 26 вход сигнала опроса и считывания из накопителя 1, 27 вход сигнала записи в накопитель, 28 вход сигнала установки устройства в начальное состояние, 29 и 30 входы сигналов записи соответственно аргумента и маски в блок 15 опроса и маскирования, 31 входы задания кода смещения по столбцам и управления смещением аргумента опроса и маски в блоке 15, 32, 33 входы сигналов записи соответственно аргумента и маски в блок 16 опроса и маскирования, 34 входы задания кода смещения по строкам и управления смещением аргумента опроса и маски в блоке 16, 35 входы выборки и задания кода смещения в регистре 17, 36 входы выборки и задания кода смещения в регистре 18, 37 входы сигналов записи и задания кода конфигурации в регистре 21.

На фиг. 2 приведен пример реализации элемента 3 памяти, состоящего из RS-триггера 38 с инверсными входами установки в "1" и "0", элемента И 39, первого 40 и второго 41 элементов И-НЕ, первого 42 и второго 43 элементов 2И-ИЛИ-НЕ. На фиг.2 также представлены не показанные на фиг.1 ограничительные элементы 44 в виде резисторов.

Регистр 17 (18) адреса (фиг.3) может быть выполнен на основе блока 45 (регистр и дешифратор) и элементов ИЛИ 46. При записи и дешифрации кода смещения блоком 45 выходы регистра 17 (18) адреса смещения, расположенные выше дешифрированного выхода (включительно), установлены в состояние логической "1".

На фиг.4 и 5 показаны соответственно первый 15 и второй 16 блоки опроса и маскирования, состоящие из блоков 47 опроса, блоков 48 маскирования и групп элементов И 49. Блоки 47 и 48 могут быть выполнены либо на основе сдвиговых регистров и устройств фиксации кода смещения и управления сдвигами в регистрах, либо на основе мультиплексоров, обеспечивающих переключение выходов блоков 47 и 48 в соответствии с кодами смещений. Управление смещениями аргумента опроса в блоке 47 и маски в блоке 48 может быть реализовано независимо друг от друга. Выводы 50, 51 и 52, 53 являются выводами расширения слева соответственно блоков 47 опроса и 48 маскирования первого 15 и второго 16 блоков опроса и маскирования. Выводы 54, 55 и 56, 57 являются выводами расширения справа соответственно блоков 47 опроса и 48 маскирования первого 15 и второго 16 блоков опроса и маскирования. Благодаря этому удается наращивать емкость систем ассоциативной памяти каскадированием таких устройств.

Размерность подматрицы 2 накопителя 1 nхn, где n разрядность первого 15 и второго 16 блоков опроса и маскирования.

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

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

Выбор нужных подматриц и задание их фрагментов осуществляется в результате записи кода конфигурации в регистр 21 и кодов смещения по столбцам СМ1 в первый 17 регистр адреса и по строкам СМ2 во второй 18 регистр адреса. При записи и дешифрации кодов смещения в регистрах 17 и 18 их выходы, расположенные выше дешифрированного выхода (фиг.3), установлены в состояние логической "1", а расположенные ниже в состояние логического "0", подготавливая тем самым задание фрагментов подматриц, которые будут активизированы.

При записи кода конфигурации в регистр 21 логические уровни сигналов на его выходах с первого i (1) по четвертый i(4) каждой группы (i=1.Р, где Р количество подматриц накопителя) определяют выбор подматриц и задание их фрагментов.

На фиг. 6 рассмотрены примеры задания отдельного фрагмента в выбранной i-й подматрице размеров 3х3 ассоциативного накопителя, на фиг.7 двух фрагментов, на фиг.8 четырех фрагментов подматрицы для различных значений сигналов на выходах i-й группы регистра 21 и кодов смещения по строкам и столбцам.

На основе приведенных примеров можно рассмотреть случаи инициализации различных фрагментов сложной конфигурации в подматрицах (фиг.9).

В режиме записи после настройки устройства на информационные входы 22 блока 15 подается записываемое слово, которое фиксируется в блоке 47 опроса. Затем сюда же в блок 48 маскирования записывается маска (процедуру маскирования определяют единицы в соответствующих разрядах блока 48). Далее в соответствии с кодом смещения по столбцам, поступающим с входов 31 на блок 15, осуществляется сдвиг либо перекоммутация (в зависимости от исполнения блоков 47 и 48) записываемого слова и маски. При этом на входы 4 и 5 всех элементов 3 памяти с первого и второго выходов соответствующей группы блока 15 поступает одна из следующих комбинаций сигналов: 10 код единицы, 01 код нуля, 00 код маски. Одновременно с этим в блок 47 опроса блока 16 записывается дешифрированный адрес строки, который также может быть смещен в соответствии с кодом смещения по строкам, поступающим с входов 34. При подаче сигнала 27 записи в накопитель 1 осуществляется маскируемая запись слова в заданный фрагмент выбранной подматрицы.

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

В режиме считывания строки заданного фрагмента выбранной подматрицы в прямом коде в соответствующий разряд блока 47 опроса блока 16 должна быть занесена единица. Остальные разряды маскируются маской из блока 48. После смещения на входы 7 и 8 элементов 3 памяти соответствующей строки заданного фрагмента выбранной подматрицы накопителя подана комбинация 10. На входы всех остальных строк фрагмента подматрицы поступит сочетание 00. В результате этого слово, считываемое с выходов 12 элементов 3 памяти этой строки заданного фрагмента выбранной подматрицы, фиксируется а регистре 20 по сигналу 26. Этот результат может быть в случае необходимости сдвинут в соответствии с кодом смещения по столбцам. При считывании строки в инверсном коде в разряд блока 47 опросам блока 16, соответствующий этой строке, должен быть записан ноль при прочих прежних условиях.

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

В режиме считывания столбца (разрядного среза) заданного фрагмента выбранной подматрицы в прямом коде в соответствующий разряд блока 47 опроса блока 15 должна быть занесена единица, в случае считывания столбца в инверсном коде ноль. Остальные разряды маскируются маской из блока 48. После смещения на входы 4 и 5 элементов 3 памяти соответствующего столбца всех подматриц накопителя подана комбинация 10 при считывании в прямом коде или 01 при считывании в инверсном. На входы 4 и 5 остальных столбцов всех подматриц накопителя поступает сочетание 00. В результате этого разрядный срез, считываемый с выходов 11 элементов 3 памяти данного столбца заданного фрагмента выбранной подматрицы, фиксируется в регистрах 19 по сигналу 26 и может быть в случае необходимости сдвинут в соответствии с кодом смещения по строкам.

В режиме столбцового конъюнктивного считывания до подачи сигнала 26 в разряды блока 47 опроса блока 15, соответствующие считываемым столбцам заданного фрагмента выбранной подматрицы в прямом коде, заносятся единицы, а в разряды, соответствующие считываемым столбцам в инверсном коде, нули. Остальные разряды блока 47 должны быть замаскированы маской из блока 48. Результатом этой операции является конъюнкция считываемых столбцов, взятых либо в прямом, либо в инверсном коде, зафиксирования в регистре 19. При активизации нескольких подматриц в этом режиме осуществляется конъюнкция считываемых столбцов в заданных фрагментах всех выделенных подматриц.

В режиме ассоциативного маскируемого поиска по строкам заданного фрагмента выбранной подматрицы после записи поискового аргумента-строки и маски-строки в блок 15 и их сдвига в соответствии с кодом смещения по столбцам на входы 4 и 5 всех элементов 3 памяти поступает одна из следующих комбинаций сигналов: 10 сравнение с единицей; 01 сравнение с нулем, 00 маскирование сравнения. По сигналу 26 результат ассоциативного поиска по строкам заданного фрагмента выбранной подматрицы накопителя записывается в регистр 19.

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

В режиме ассоциативного маскируемого поиска по столбцам заданного фрагмента выбранной подматрицы после записи поискового аргумента-столбца и маски-столбца в блок 16 и их сдвига в соответствии с кодом смещения по строкам на входы 7 и 8 всех элементов 3 памяти поступает одна из следующих комбинаций сигналов: 10 сравнение с единицей, 01 сравнение с нулем, 00 маскирование сравнения. По сигналу 26 результат ассоциативного поиска по столбцам заданного фрагмента выбранной подматрицы накопителя записывается в регистр 20.

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

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

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

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

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