Способ снижения энергопотребления в n-мерной контекстно-адресуемой памяти

Авторы патента:


Способ снижения энергопотребления в n-мерной контекстно-адресуемой памяти
Способ снижения энергопотребления в n-мерной контекстно-адресуемой памяти
Способ снижения энергопотребления в n-мерной контекстно-адресуемой памяти
Способ снижения энергопотребления в n-мерной контекстно-адресуемой памяти
Способ снижения энергопотребления в n-мерной контекстно-адресуемой памяти
Способ снижения энергопотребления в n-мерной контекстно-адресуемой памяти
Способ снижения энергопотребления в n-мерной контекстно-адресуемой памяти

 


Владельцы патента RU 2453935:

Лихачев Николай Иванович (RU)
Валов Сергей Геннадьевич (RU)

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

 

1. Область техники

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

2. Уровень техники

Контекстно-адресуемая память (Content-addressable memory - CAM) выполняет поиск элемента данных по значению. САМ состоит из регистров для хранения различных элементов данных и компараторов для одновременного сравнения искомого элемента данных со всеми хранимыми элементами данных. Если результат сравнения «истина», искомый элемент данных хранится в памяти, то возвращают либо адрес ячейки, в которой хранится искомый элемент данных, либо сигнал “Значение есть”, либо адрес ячейки и сигнал “Значение есть” одновременно.

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

Известно [2], что контекстно-адресуемая ячейка памяти содержит семь транзисторов, объединенных в столбец линией данных (прямой и инверсный) и в строку линиями, выборки столбца, синхронизации и сравнения. Ячейка содержит транзисторы элемента памяти, схемы сравнения и транзистор синхронизации и подключения ячейки к линии сравнения.

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

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

Известно [4], что в контекстно-адресуемой памяти линия сравнения заменена схемой суммирования.

Известно [5], что в контекстно-адресуемой памяти каждый столбец матрицы ячеек имеет раздельные линии записи данных и поиска. Столбцы ячеек разделены на блоки равного размера. Схема сравнения объединяет распределенное «И» при каскадном подключении ячеек внутри блока и централизованного «ИЛИ» блоков, составляющих строку.

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

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

Известно [8], что контекстно-адресуемая память выполнена в виде N сдвиговых регистров, регистра поиска, компаратора в виде схемы «исключающее ИЛИ» и счетчика ошибок. Поиск осуществляется последовательным сдвигом всех данных, находящихся во всех сдвиговых регистрах, и одного регистра поиска, и подсчетом числа несовпадений на выходе компаратора и накоплением числа несовпадений на протяжении всего цикла, когда кольцевой сдвиговый регистр совершит полный оборот.

Известно [9], что в контекстно-адресуемой памяти свободные строки матрицы ячеек по сигналу управления отключают от цепей питания для целей экономии потребляемой энергии.

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

3. Сущность изобретения

Сущность изобретения заключается в том, что способ снижения энергопотребления в N-мерной контекстно-адресуемой памяти,

имеющей N-мерную ячейку, состоящую из N регистров памяти, (N+1) ключей, N блоков сравнения и схемы суммирования с (N+1) входом, где N - целое число в диапазоне от 0 до, например, 2^20, но не ограниченное этим значением,

имеющей матрицу 1.1÷S.L N-мерных ячеек, где S целое число в диапазоне от 32 до, например, 2^20, но не ограниченное этим значением, а L = 2^R, где R целое число,

соединяющей столбцы матрицы линиями ввода и поиска данных, а строки матрицы входами «запись» и выходами схем сравнения,

разделяющей строку матрицы на группы разного размера,

определяющей размер M группы как m N-мерных ячеек 4.1, где m принимает значения [2, 2, 4, 8, 16, 32, … log(L)], то есть первая и вторая группы содержат по 2 ячейки, третья группа - 4 ячейки, четвертая группа - 8, пятая - 16, шестая - 32, а последняя группа содержит m=log(L) ячеек;

записывающей элементы данных с линий ввода данных и хранящей элементы данных в N-регистрах памяти,

сравнивающей искомый элемент данных, поступивший с линий поиска данных, с хранимыми элементами данных,

схема суммирования 1 группы получает на вход сигнал результата сравнения равным «соответствие»,

суммирующей сигналы результатов сравнения от всех N-мерных ячеек, входящих в текущую группу, и сигнал результата сравнения от m-1 группы и подающей суммарный сигнал результата сравнения на m+1 группу,

обеспечивающей электропитанием только группы от 1 до m N-мерных ячеек, где сигнал результата сравнения равен «соответствие», а в группах от m+1 до M электропитание с блоков сравнения и схемы суммирования снимают, чем достигают снижение энергопотребления N-мерной контекстно-адресуемой памяти,

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

4. Перечень фигур

Фигура 1. Контекстно-адресуемая ячейка.

Фигура 2. Строка контекстно-адресуемых ячеек.

Фигура 3. N-я ячейка.

Фигура 4. N-мерная контекстно-адресуемая ячейка.

Фигура 5. Строка N-мерных контекстно-адресуемых ячеек.

Фигура 6. m группа N-мерных контекстно-адресуемых ячеек.

Фигура 7. Строка из M групп N-мерных контекстно-адресуемых ячеек.

5. Сведения, подтверждающие возможность осуществления изобретения

Матрица 1.1÷S.L N-мерной контекстно-адресуемой памяти на фигурах 2, 5 и 7 для наглядности представлена только одной строкой. Столбцы матрицы соединяют линиями ввода и поиска данных, а строки матрицы соединяют входами «записи» и выходами схем сравнения.

Функциональная схема ячейки 1 контекстно-адресуемой памяти, показанная на фигуре 1, состоит из регистра 10, компаратора 11, сумматора 12 и двух ключей 13.1 и 13.2, соединяет вход 1 ячейки 1 с входом 1 регистра 10, вход 2 с входом 3 регистра 10, вход 3 ячейки 1 с входом 3 компаратора 11, выход 5 сумматора 12 с выходом 5 ячейки 1, соединяет вход 7 ячейки 1 с входом 2 регистра 10, входом 1 ключа 13.1 и входом 1 ключа 13.2, соединяет выход 6 ячейки 1 с выходом 4 регистра 10, выходом 4 компаратора 11 и выходом 4 сумматора 12, соединяет выход 5 регистра 10 с входом 1 компаратора 11, соединяет выход 5 компаратора 11 с входом 1 сумматора 12, соединяет вход 4 ячейки 1 с входом 3 сумматора 12, входом 2 ключа 13.1 и входом 2 ключа 13.2, соединяет выход 3 ключа 13.1 с входом 2 компаратора 11, соединяет выход 3 ключа 13.2 с входом 2 сумматора 12.

Элемент данных поступает на вход 1 ячейки 1 и по сигналу «запись» на входе 2 ячейки 1 сохраняет элемент данных в регистре 10.

Сигнал результата сравнения поступает на вход 4 ячейки 1, если сигнал равен «соответствие», то ключи 13.1 и 13.2 подключают компаратор 11 и сумматор 12 к входу 7 ячейки 1, в противном случае ключи 13.1 и 13.2 отключают компаратор 11 и сумматор 12 от входа 7 ячейки 1 и с выхода 5 сумматора 12 сигнал результата сравнения, равный «несоответствие», поступает на выход 5 ячейки 1.

Искомый элемент данных поступает на вход 3 ячейки 1 на вход 3 компаратора 11. Компаратор 11 при включенном ключе 13.1 сравнивает хранимый элемент данных с входа 1 с искомым элементом данных с входа 3. Сумматор 12 при включенном ключе 13.2 суммирует сигнал результата сравнения на входе 1 с сигналом результата сравнения на входе 3 и выдает сигнал результата сравнения на выход 5 ячейки 1.

Функциональная схема строки ячеек 1.1÷1.L контекстно-адресуемой памяти показана на фигуре 2, состоит из ячеек 1.1÷1.L, входы 2 ячеек 1.1÷1.L соединены линией 23 сигнала «запись», выходы 6 ячеек 1.1÷1.L соединены линией 26, входы 7 ячеек 1.1÷1.L соединены линией 25, линиями 21.1÷21.L «ввод данных» соединены с входом 3 каждой из ячеек 1.1÷1.L строки в матрице, линиями 22.1÷22.L «поиск данных» соединены с входом 1 каждой из ячеек 1.1÷1.L, линия 20 сигнала результата сравнения «соответствует» соединена с входом 4 ячейки 1.1, выход 5 ячейки 1.L соединен с линией 24 выход сигнала результата сравнения, выход 5 ячейки (1.l) соединен с входом 4 ячейки 1.(l +1), где 1 ≤ l ≤ L.

Элементы данных поступают по линиям 22.1÷22.L «ввод данных» на вход 1 ячеек 1.1÷1.L и по сигналу «запись», подаваемому с линии 23 на вход 2 ячеек 1.1÷1.L, сохраняют элементы данных в ячейках 1.1÷1.L.

Искомый элемент данных поступает по линиям 21.1 ÷ 21.L «поиск данных» на вход 3 1.1÷1.L ячеек. Сигнал результата сравнения, равный «соответствие», с линии 20 поступает на вход 4 ячейки 1.1. Сигнал результата сравнения с выход 5 ячейки (1.l) поступает на вход 4 ячейки 1.(l+1), где 1 ≤ l ≤ L. Результирующий сигнал результата сравнения с выхода 5 ячейки (1.L) поступает в линию 24. Если сигнал результата сравнения с выход 5 ячейки (1.l) станет равным «несоответствие», то блоки сравнения и схемы суммирования ячеек 1.(l+1)÷1.L отключают от электропитания.

Время получения результирующего сигнала результата сравнения равно сумме длительности времени сравнения каждой 1.1÷1.L ячейки.

Функциональная схема N-мерной ячейки 3 контекстно-адресуемой памяти показана на фигурах 3 и 4, состоит из N ячеек 2.1÷2.N, фигура 3, сумматора 14 и ключа 16, фигура 4, а N-я ячейка 2.1÷2.N состоит из регистров 10.1÷10.N, компараторов 11.1÷11.N и ключей 15.1÷15.N, фигура 3,

N-я ячейка 2.1÷2.N, фигура 3, соединяет вход 1 ячейки 3 с входом 1 регистров 10.1÷10.N, вход 2.N ячейки 3 с входом 2 регистров 10.1÷10.N, вход 3 ячейки 3 с входом 3 компараторов 11.1÷11.N, вход 7 ячейки 2.1÷2.N с входом 2 регистров 10.1÷10.N и входом 1 ключей 15.1÷15.N, выход 6 ячейки 2.1÷2.N с выходом 4 регистров 10.1÷10.N и выходом 4 компараторов 11.1÷11.N, соединяет выход 3 ключей 15.1÷15.N с входом 2 компараторов 11.1÷11.N.

N-мерная ячейка 3, фигура 4, соединяет вход 7 с входами 7 N-х ячеек 2.1÷2.N и входом 1 ключа 16, соединяет выход 6 с выходом 6 N-х ячеек 2.1÷2.N и выходом 4 сумматора 14, соединяет вход 4 с входом 4 N-х ячеек 2.1÷2.N, входом 2 ключа 16 и входом 3 сумматора 14, соединяет выходы 5.1-5.N N-х ячеек 2.1÷2.N с входами 1.1-1.N сумматора 14, соединяет выход 3 ключа 16 с входом 2 сумматора 14, соединяет выход 5 сумматора 14 с выходом 5.

Элемент данных поступает на вход 1 N-мерной ячейки 3 и по сигналу «запись» на входах 2.1÷2.N ячейки 3 сохраняет элементы данных в N ячейках 2.1÷2.N.

Сигнал результата сравнения поступает на вход 4 ячейки 3, если сигнал равен «соответствие», то ключи 15.1÷15.N и 16 подключают компараторы 11.1÷11.N и сумматор 14 к входу 7 ячейки 3, в противном случае ключи 15.1÷15.N и 16 отключают компараторы 11.1÷11.N и сумматор 14 от входа 7 ячейки 3 и с выхода 5 сумматора 14, сигнал результата сравнения, равный «несоответствие», поступает на выход 5 ячейки 3.

Искомый элемент данных поступает на вход 3 ячейки 3 и на вход 3 N-х ячеек 2.1÷2.N, если ключи 15.1÷15.N включены, то сравнивают искомый элемент данных с хранимыми элементами данных в ячейках 2.1÷2.N, сигналы результатов сравнения с выходов 5.1÷5.N поступают на входы 1.1÷1.N сумматора 14. Сумматор 14 при включенном ключе 16 суммирует сигналы результатов сравнения на входах 1.1÷1.N с сигналом результата сравнения на входе 3 и выдает сигнал результат сравнения на выход 5 ячейки 3.

Функциональная схема строки N-мерных ячеек 3.1÷3.L контекстно-адресуемой памяти показана на фигуре 5, состоит из ячеек 3.1÷3.L, входы 2.1÷2.N ячеек 3.1÷3.L соединены линиями 43.1÷43.N сигналов «запись», выход 6 ячеек 3.1÷3.L соединены линией 26, входы 7 ячеек 3.1÷3.L соединены линией 25, линиями 41.1÷41.L «ввод данных» соединены с входом 1 каждой из ячеек 3.1÷3.L строки в матрице, линиями 42.1÷42.L «поиск данных» соединены с входом 3 каждой из ячеек 3.1÷3.L, линия 20 сигнала результата сравнения «соответствует» соединена с входом 4 ячейки 3.1, линия 44 выход результирующего сигнала результата сравнения соединена с выходом 5 ячейки 3.L, выход 5 ячейки 3.1 соединен с входом 4 ячейки 3.l, где 2≤ l ≤L.

Элементы данных поступают по линиям 42.1 ÷ 42.L «ввод данных» на вход 1 ячеек 3.1÷3.L и по сигналу «запись», подаваемому с линий 43.1÷43.N на входы 2.1÷2.N ячеек 3.1÷3.L, сохраняют элементы данных в ячейках 3.1÷3.L.

Искомый элемент данных поступает по линиям 41.1 ÷ 41.L «поиск данных» на вход 3 ячеек 3.1÷3.L. Сигнал результата сравнения, равный «соответствие», с линии 20 поступает на вход 4 ячейки 3.1. Сигнал результата сравнения с выход 5 ячейки 3.1 поступает на вход 4 ячейки 3.l, где 2 ≤ i ≤ L. Результирующий сигнал результата сравнения с выхода 5 ячейки 3.L поступает в линию 44. Если сигнал результата сравнения с выход 5 ячейки 3.l станет равным «несоответствие», то ячейки 3.(l+1)÷1.L отключают от электропитания.

Время получения результирующего сигнала результата сравнения равно сумме длительности времени сравнения каждой 3.1÷3.L ячейки.

Функциональная схема m группы N-мерных контекстно-адресуемых ячеек 4.m показана на фигуре 6.

Группа состоит из m N-мерных ячеек 4.1, где m принимает значения [2, 2, 4, 8, 16, 32, … log(L)], то есть первая и вторая группы содержат по 2 ячейки, третья группа - 4 ячейки, четвертая группа - 8, пятая - 16, шестая - 32 и т.д. Последняя группа содержит m=log(L) ячеек.

m группа состоит из m N-х ячеек 2.1÷2.N, 17.m сумматора с (m × N)+1 входом и 16.m ключа.

m группа соединяет входы 1.m с входами 1.m N-х ячеек m×(2.1÷2.N), соединяет входы 2.N с входом 2.N N-х ячеек m×(2.1÷2.N), соединяет входы 3.m с входом 3.m N-х ячеек m×(2.1÷2.N), соединяет вход 7 с входом 7 N-х ячеек m×(2.1÷2.N) и входом 1 ключа 16.m, соединяет выход 6 с выходом 6 N-х ячеек m×(2.1÷2.N) и выходом 4 сумматора 17.m, соединяет вход 4 с входом 3 сумматора 17.m и входом 2 ключа 16.m, соединяет выход 3 ключа 16.m с входом 2 сумматора 17.m, соединяет m выходов 5.1÷5.N N-х ячеек m×(2.1÷2.N) с входами m×(1.1÷1.N) сумматора 17.m.

Элемент данных поступает на вход 1 m группы N-мерных ячеек 4 и по сигналу «запись» на входе 2.N сохраняет элемент данные в N-й ячейке m×(2.1÷2.N).

Сигнал результата сравнения поступает на вход 4 m группы, если сигнал равен «соответствие», то 15.1÷15.N ключи N-й ячейки m×(2.1÷2.N) и 16.m ключ m группы подключают 11.1÷11.N компараторы N-й ячейки m×(2.1÷2.N) и сумматор 17.m к входу 7 m группы, в противном случае отключают 11.1÷11.N компараторы N-й ячейки m×(2.1÷2.N) и сумматор 17.m от входа 7 m группы и с выхода 5 сумматора 17.М сигнал результата сравнения, равный «несоответствие», поступает на выход 5 m группы.

Искомый элемент данных поступает на вход 3.m m группы, если ключи 15.1÷15.N и 16.m включены, то сравнивают искомый элемент данных с хранимыми элементами данных в N-х ячейках m×(2.1÷2.N), а сигналы результатов сравнения с выходов 5.1-5.N в N-х ячейках m×(2.1÷2.N) поступают на входы m×(1.1÷1.N) сумматора 17.m. Сумматор 17.m суммирует сигналы результатов сравнения c входов m×(1.1-1.N) с сигналом результата сравнения на входе 3 и выдает сигнал результата сравнения на выход 5 m группы.

Функциональная схема строки из M групп N-мерных ячеек 4.1÷4.M контекстно-адресуемой памяти показана на фигуре 7.

Строка из M групп N-мерных ячеек 4.1÷4.М соединяет входы 2.N с линиями 43.1÷43.N, соединяет выход 6 M с линией 26, соединяет входы 7 с линией 25, соединяет линиями 61.1 ÷ 61.М «ввод данных» вход 1 каждой М группы строки матрицы, соединяет линиями 62.1 ÷ 62.М «поиск данных» вход 3 каждой М группы, соединяет линией 20 сигнала результата сравнения «соответствует» с входом первой группы, соединяет выход 5 M группы с линией 64 результирующего сигнала результата сравнения, соединяет выход 5 m группы с входом 4 m+1 группы, где 1 ≤ m ≤ log(L).

Время получения результирующего сигнала результата сравнения равно сумме длительностей времени сравнения каждой M группы N-мерных ячеек 4.1÷4.М строки.

САМ реализуют на базе программируемой пользователем логической схемы типа (field-programmable gate array - FPGA) фирм Altera, Lattice, Xilinx или на базе специализированной (заказной) интегральной схемы.

Библиография

1. US 3353159, 14 Nov 1967, Edwin S. Lee III.

2. GB 2192507, 13 Jan 1988, Imel.

3. US 5517441, 14 May 1996, Dietz et al.

4. US 6188629, 13 Feb 2001, Kaplinsky.

5. US 6349049, 19 Feb 2002, Schoy.

6. US 6879532, 12 Apr 2005, Proebsting et al.

7. US 7486531, 3 Feb. 2009, Park.

8. US 2004/0120174, 24 Jun. 2004, Regev et al.

9. PCT/US05/032986, 16 Sep. 2005.

1. Способ снижения энергопотребления в N-мерной контекстно-адресуемой памяти (САМ), предназначенной для поиска элемента данных по значению, содержащей регистры памяти, сохраняющие элементы данных, и содержащий блоки сравнения, сравнивающие искомый элемент данных с сохраненными элементами данных, объединяющей результаты сравнения в выходной сигнал наличия или отсутствия значения искомого элемента данных в контекстно-адресуемой памяти, и соединяющей столбцы матрицы линиями ввода и поиска данных, а строки матрицы входами «записи» и выходами схем сравнения, отличающийся тем, что
ячейка САМ состоит из регистра памяти, двух ключей, блока сравнения и схемы суммирования,
L ячеек САМ объединяют в строку, где L - целое число, кратное степени 2, схема суммирования с 2 входами, суммирует сигнал сравнения с выхода блока сравнения и сигнал результата сравнения с выхода ячейки l-1 САМ, первая схема суммирования получает на вход сигнал результата сравнения равным «соответствие»,
сигнал результата сравнения последовательно поступает с выхода схемы суммирования ячейки 1.l на вход ячейки 1.(l+1) и далее до ячейки 1.L, где 1≤l≤L, если обнаружено несоответствие между искомым элементом и хранимыми элементами в ячейке 1.l, то сигнал результата сравнения, равный «несоответствие», подают на входы ключей и схему суммирования ячейки 1.(l+1), отключают напряжение питания с блоков сравнения и схем суммирования в ячейках с 1.(l+1) до 1.L, где 1≤l≤L.

2. Способ снижения энергопотребления в N-мерной контекстно-адресуемой памяти по п.1, отличающийся тем, что N-мерная ячейка САМ состоит из N регистров памяти, N+1 ключей, N блоков сравнения и схемы суммирования с N+1 входом, где N - целое число, L N-мерных ячеек САМ объединяют в строку, где L - целое число, кратное степени 2,
схема суммирования с N+1 входом, суммирует сигналы сравнения с N выходов блоков сравнения и сигнал результата сравнения с выхода N-мерной ячейки 1.(l-1) и подает суммарный сигнал результата сравнения на вход N-мерной ячейки 1.(l+1), где 1≤l≤L,
первая схема суммирования с N+1 входом получает на вход сигнал результата сравнения равным «соответствие»,
сигнал результата сравнения последовательно поступает с выхода схемы суммирования N-мерной ячейки 1.l на вход N-мерной ячейки 1.(l+1) и далее до N-мерной ячейки 1.L, где 1≤l≤L,
если обнаружено несоответствие между искомым элементом и хранимыми элементами в N-мерной ячейке 1.l, то сигнал результата сравнения, равный «несоответствию», подают на входы ключей и схему суммирования N-мерной ячейки 1.(l+1), отключают напряжение питания с N блоков сравнения и схемы суммирования в N-мерных ячейках с 1.(l+1) до 1.L, где 1<l<L.

3. Способ снижения энергопотребления в N-мерной контекстно-адресуемой памяти по п.2, отличающийся тем, что
N-мерные ячейки САМ объединяют в М групп,
группа состоит из m N-мерных ячеек САМ, где m принимает значения [2, 2, 4, 8, 16, 32, … log(L)],
первая и вторая группа содержат по 2 N-мерных ячейки САМ,
третья группа - 4 N-мерных ячейки САМ,
четвертая группа - 8, пятая - 16, шестая - 32 и т.д., а
последняя группа содержит M=log(L) N-мерных ячейки САМ,
схема суммирования m группы с (m·N)+1 входами, суммирует сигналы результата сравнения с m·(1.1÷1.N) выходов блоков сравнения и сигнал результата сравнения с выхода m-1 группы N-мерных ячеек САМ, и подает суммарный сигнал результата сравнения на вход m+1 группы N-мерных ячеек САМ,
первая схема суммирования с (m·N)+1 входом получает на вход сигнал результата сравнения равным «соответствие»,
сигнал результата сравнения последовательно поступает с выхода схемы суммирования m-й группы N-мерных ячеек САМ, на вход m+1 группы N-мерных ячеек САМ, и далее до М-группы N-мерных ячеек САМ,
если обнаружено несоответствие между искомым элементом и хранимыми элементами в m-й группе N-мерных ячеек САМ, то сигнал результата сравнения подают на входы ключей и схему суммирования m+1 группы N-мерных ячеек САМ, отключают напряжение питания с блоков сравнения и схемы суммирования с m+1 до М группы N-мерных ячеек САМ.



 

Похожие патенты:

Изобретение относится к архитектуре памяти и, более конкретно, к способам и системам для ассоциативной памяти (САМ). .

Изобретение относится к блокам ассоциативной памяти. .

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

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

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

Изобретение относится к способам внешнего хранения данных, обработанных устройством обработки данных. .

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

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

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

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

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

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