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

Формула изобретения

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-мерных ячеек САМ.

Описание изобретения к патенту

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.