ассоциативная память со смешанным параллельно-последовательным поиском

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

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

2. АЗУ по п.1, в котором каждая строка включает в себя четыре последовательные ячейки АЗУ.

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

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

5. АЗУ по п.1, в котором перед каждой операцией поиска формирователь сконфигурирован предустанавливать линию поиска для последнего столбца последовательных ячеек АЗУ среди по меньшей мере одного столбца последовательных ячеек АЗУ.

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

7. АЗУ по п.1, дополнительно содержащее множество линий совпадения для множества строк параллельных ячеек АЗУ, причем это множество линий совпадения предварительно заряжается перед каждой операцией поиска путем предустановки упомянутой по меньшей мере одной линии поиска.

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

9. АЗУ по п.1, в котором поиск по упомянутому множеству строк выполняется параллельно, при этом для каждой строки поиск по упомянутой по меньшей мере одной последовательной ячейке АЗУ выполняется последовательно, а поиск по упомянутым по меньшей мере двум параллельным ячейкам АЗУ выполняется параллельно.

10. АЗУ по п.9, в котором поиск в каждой строке по упомянутым по меньшей мере двум параллельным ячейкам АЗУ выполняется только в случае, если упомянутая по меньшей мере одна последовательная ячейка АЗУ в строке дает совпадение.

11. АЗУ по п.9, в котором для каждой строки поиск по упомянутым по меньшей мере двум параллельным ячейкам АЗУ выполняется параллельно и одновременно с последовательным поиском по упомянутой по меньшей мере одной последовательной ячейке АЗУ.

12. АЗУ по п.1, в котором каждая из упомянутого множества ячеек АЗУ включает в себя ячейку памяти, предназначенную для хранения значения данных, и схему сравнения, предназначенную для сравнения хранящегося значения данных с входным значением данных.

13. АЗУ по п.1, в котором каждая из упомянутого множества ячеек АЗУ включает в себя первый и второй КМОП-вентили, причем эти первый и второй КМОП-вентили подключены к дифференциальной линии поиска и управляются по значению данных, хранящемуся в ячейке АЗУ.

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

15. Кэш-память по п.14, в которой процессор сконфигурирован для выполнения обработки для беспроводной связи.

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

17. Способ по п.16, дополнительно содержащий этап, на котором осуществляют поиск по упомянутому множеству строк ячеек АЗУ параллельно.

18. Способ по п.16, в котором при предустановке упомянутой по меньшей мере одной линии поиска для упомянутой по меньшей мере одной последовательной ячейки АЗУ в строке, чтобы предварительно зарядить линию совпадений для упомянутых по меньшей мере двух параллельных ячеек АЗУ в строке.

19. Способ по п.16, в котором при выборочном параллельном поиске по упомянутым по меньшей мере двум параллельным ячейкам АЗУ в строке, выполняют поиск по упомянутым по меньшей мере двум параллельным ячейкам АЗУ в строке, только если упомянутая по меньшей мере одна последовательная ячейка АЗУ в строке дает совпадение.

20. Способ по п.16, в котором при выборочном параллельном поиске по упомянутым по меньшей мере двум параллельным ячейкам АЗУ в строке осуществляют поиск по упомянутым по меньшей мере двум параллельным ячейкам АЗУ в строке параллельно, одновременно с поиском по упомянутой по меньшей мере одной последовательной ячейке АЗУ в строке.

21. Способ по п.16, дополнительно включающий в себя этап, на котором для каждой из упомянутого множества строк ячеек АЗУ выполняют управление линией виртуального заземления для упомянутых по меньшей мере двух параллельных ячеек АЗУ в строке с тем, чтобы разблокировать и заблокировать поиск по упомянутым по меньшей мере двум параллельным ячейкам АЗУ.

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

23. Устройство по п.22, в котором средства для выборочного поиска по упомянутым по меньшей мере двум параллельным ячейкам АЗУ в строке параллельно включают в себя средства для поиска по упомянутым по меньшей мере двум параллельным ячейкам АЗУ в строке, только если упомянутая по меньшей мере одна последовательная ячейка АЗУ в этой строке дает совпадение.

24. Устройство по п.22, в котором средства для выборочного поиска по упомянутым по меньшей мере двум параллельным ячейкам АЗУ в строке параллельно включают в себя средства для поиска по упомянутым по меньшей мере двум параллельным ячейкам АЗУ в строке параллельно, одновременно со средствами для поиска по упомянутой по меньшей мере одной последовательной ячейке АЗУ в строке.

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

I. Область техники, к которой относится изобретение

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

II. Предшествующий уровень техники

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

АЗУ используется в различных вариантах применения, например, в составе кэш-памяти. Доступ к кэш-памяти может быть осуществлен быстрее, чем к другим типам памяти, и она используется для хранения данных, к которым процессор осуществит доступ с большей вероятностью. Кэш-память может включать в себя оперативное запоминающее устройство (ОЗУ, RAM), которое хранит данные, и ассоциативное запоминающее устройство (АЗУ), которое содержит адреса данных. Чтобы установить, содержится ли заданное слово данных в кэш-памяти, по АЗУ проводится поиск для определения того, совпадает ли адрес данного слова с каким-либо из адресов, хранящихся в АЗУ. В случае совпадения нужное слово может быть извлечено из оперативной памяти для использования.

Поиск в АЗУ может производится экстенсивно - например, для каждой команды процессора с обращением к памяти. Следовательно, функциональные характеристики АЗУ обычно существенно влияют на качество функционирования процессора. Высокая скорость поиска может быть достигнута путем параллельного поиска по всем строкам АЗУ. Однако параллельный поиск требует больших затрат энергии, что нежелательно во многих вариантах применения.

Следовательно, имеется потребность в АЗУ с высокой производительностью и низким энергопотреблением.

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

Здесь приводится описание смешанного последовательно-параллельного АЗУ, которое достигает высокой производительности при небольшом энергопотреблении. АЗУ включает в себя последовательные и параллельные ячейки АЗУ, упорядоченные во множество (N) столбцов и множество (М) строк. Каждая строка включает в себя по меньшей мере одну последовательную ячейку АЗУ, по меньшей мере две параллельные ячейки АЗУ, линию совпадений и линию виртуального заземления для параллельных ячеек АЗУ в этой строке. Поиск по М строкам проводится параллельно. В каждой строке поиск по последовательным ячейкам АЗУ проводится последовательно, а поиск по параллельным ячейкам АЗУ выборочно проводится параллельно. Поиск по параллельным ячейкам АЗУ в каждой строке может проводиться одновременно (1) только в том случае, если происходит совпадение в последовательных ячейках, что уменьшает энергопотребление, или (2) одновременно с поиском по последовательным ячейкам АЗУ, что увеличивает скорость поиска. Для каждой строки осуществляется управление линией виртуального заземления, чтобы разблокировать или заблокировать поиск по параллельным ячейкам АЗУ в этой строке.

АЗУ дополнительно включает в себя формирователь, который формирует N линий поиска для N столбцов ячеек АЗУ - по одной линии поиска на каждый столбец. Формирователь устанавливает N линий поиска в N-битное значение для поиска в АЗУ. Перед каждой операцией поиска формирователь предусматривает по меньшей мере одну линию поиска для по меньшей мере одного столбца последовательных ячеек АЗУ с тем, чтобы предварительно зарядить линию совпадения для каждой строки. Предварительной зарядкой называется установка или приведение строки в заранее определенное логическое значение (допустим, в низкий логический уровень ( L )). Например, если каждая строка включает в себя четыре последовательные ячейки АЗУ, то формирователь может предустанавливать линию поиска для второй или четвертой ячейки АЗУ в строке, как описано ниже. Предустановка по меньшей мере одной линии поиска позволяет избежать необходимости в синхронизирующем сигнале для последовательной секции АЗУ. Отсутствие такого синхронизирующего сигнала может увеличить скорость поиска.

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

Перечень фигур чертежей

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

Фиг.1 - смешанная последовательно-параллельная АЗУ.

Фиг.2А и 2В - две типовые схемы последовательной ячейки АЗУ.

Фиг.2С и 2D - две типовые схемы параллельной ячейки АЗУ.

Фиг.3 - одна строка ячеек в смешанном последовательно-параллельном АЗУ.

Фиг.4, 5 и 6 - три примера реализации одной строки ячеек АЗУ в смешанном последовательно-параллельном АЗУ без каких-либо синхронизирующих сигналов для последовательной секции АЗУ.

Фиг.7 - процесс выполнения смешанного последовательно-параллельного поиска.

Фиг.8 - схема беспроводного устройства в сети беспроводной связи.

Подробное описание

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

На Фиг.1 изображена блок-схема смешанной последовательно-параллельной АЗУ 100. АЗУ 100 включает в себя массив 110 АЗУ, формирователь 140 линий поиска и выходные цепи 150. Массив 110 АЗУ является двумерным массивом из М строк и N столбцов ячеек 120 и 122 АЗУ, где М и N могут принимать целочисленные значения. Каждая строка в массиве 110 АЗУ состоит из N ячеек АЗУ, которые совместно хранят запись, например значение адреса. Каждая строка ассоциирована с линией совпадения, имеющей логическое значение, определяемое всеми ячейками АЗУ этой строки. Каждый из N столбцов соответствует отличающейся от других позиции бита в N-битном входном адресе. Каждый столбец ассоциирован с дифференциальной линией поиска, которая подключена ко всем ячейкам АЗУ этого столбца. Каждая линия поиска имеет логическое значение, определяемое одним битом входного адреса. Логическое значение в каждой линии поиска может сравниваться с логическим значением, хранящимся в каждой из М ячеек АЗУ, подключенных к этой линии поиска. N битный входной адрес может подаваться на все М строк массива АЗУ и одновременно сравниваться со всеми М записями, которые хранятся в массиве АЗУ.

Формирователь 140 линий поиска принимает входной адрес и формирует линии поиска для N столбцов ячеек АЗУ. Выходные цепи 150 получают линии совпадения для всех М строк и обеспечивают требующийся выходной сигнал. Например, выходные цепи 150 могут выполнить кодирование и выдать К-битную величину, которая указывает конкретную строку, совпадающую с входным адресом, где К=log₂ M , где указывает на операцию округления до ближайшего большего целого числа.

В общем, АЗУ может быть спроектировано так, чтобы выполнить последовательный поиск, параллельный поиск или смешанный последовательно-параллельный поиск. Для всех трех схем поиска, поиск по всем М строкам массива АЗУ может осуществляться параллельно на предмет каких-либо совпадений с входным адресом. В случае схемы параллельного поиска, осуществляется параллельный поиск по всем N битам каждой строки, чтобы определить, совпадает ли эта строка с входным адресом. Параллельная схема поиска обеспечивает наименьшее время поиска среди всех трех схем, но потребляет наибольшую мощность из-за параллельных сравнений. Для схемы последовательного поиска проводится последовательный поиск по N битам в каждой строке, обычно начиная с самого младшего бита (LSB). Последовательный поиск для каждой строки заканчивается, как только обнаруживается несовпадение бита входного адреса с битом, который хранится в памяти. Схема последовательного поиска потребляет наименьшую мощность среди всех трех схем поиска, так как сравнение очередного хранящегося бита происходит, только если все предшествующие хранящиеся биты совпадают с соответствующими им битами адреса. Однако в случае реализации схемы последовательного поиска требуется наибольшее время для получения результатов поиска среди всех трех вариантов поиска из-за последовательных сравнений. Для того чтобы добиться одновременно высокой скорости и низкого энергопотребления, в смешанной параллельно-последовательной схеме сравнения выполняется последовательный поиск для некоторого количества битов и параллельный поиск для оставшихся битов. Ниже описана смешанная параллельно-последовательная схема поиска.

В варианте реализации, показанном на фиг.1, массив АЗУ 110 включает в себя четыре столбца последовательных ячеек 120 АЗУ и N-4 столбцов параллельных ячеек 122 АЗУ. В общем, АЗУ может состоять из любого количества столбцов последовательных ячеек и любого количества столбцов параллельных ячеек. Общее количество столбцов N определяется обычно вариантом применения, где используется АЗУ. Количество столбцов последовательных ячеек АЗУ может быть выбрано исходя из компромисса между энергопотреблением и скоростью поиска. Каждая последовательная ячейка АЗУ 120 и каждая параллельная ячейка АЗУ 122 могут быть реализованы, как описано ниже.

На Фиг.2А дано схематическое изображение последовательной ячейки 120х АЗУ, которое может быть использовано для реализации любой из последовательных ячеек 120 АЗУ на фиг.1. Ячейка 120х АЗУ включает в себя ячейку памяти 210, которая хранит бит данных, и цепь 220х сравнения, которая сравнивает сохраненные данные и бит адреса. Ячейка 210 памяти включает в себя пару инверторов 212 и 214 с перекрестными обратными связями. Выход инвертора 212 подключен ко входу инвертора 214, стоку полевого транзистора с каналом n-типа (N-FET) 216 и линии q данных. Выход инвертора 214 подключен ко входу инвертора 212, стоку N-FET 218 и дополнительной линии qb данных. Затворы транзисторов N-FET 216 и 218 подключены к числовой линии, исток N-FET 216 подключен к разрядной линии, исток N-FET 218 подключен к дополнительной разрядной линии bb. Числовая линия используется, чтобы выбрать и активировать строку ячеек АЗУ для программирования. Дифференциальная разрядная линия используется, чтобы записывать бит данных в ячейку памяти 210. Инверторы 212 и 214 сохраняют этот бит данных с помощью механизма положительной обратной связи. Способ программирования ячейки 210 памяти широко известен.

Цепь 220х сравнения включает в себя три N-FET 222, 224 и 226 и полевого транзистора с каналом р-типа (Р-FET) 228. Затворы N-FET 222 и 224 подключены к линии q данных и дополнительной линии qb данных соответственно, их истоки подключены к линии s поиска и дополнительной линии sb поиска соответственно, их стоки подключены друг к другу, а затем к затворам полевых транзисторов 226 и 228. Исток N-FET 226 подключен к входной линии совпадений match_in, а его сток - к выходной линии совпадений match_out. Исток Р-FET 228 подключен к выходной линии совпадений, а его сток - к напряжению питания Vdd.

Цепь 220х сравнения работает следующим образом. Дифференциальная линия поиска, s и sb, устанавливается в значение бита адреса. Если бит адреса совпадает с битом данных, который хранится в ячейке 210 памяти, то линия s поиска совпадает со строкой q данных, дополнительная линия sb поиска совпадает с дополнительной строкой qb данных, и один из N-FET 222 и 224 включен, а узел eq переведен на высокий логический уровень посредством N-FET, который включен.

Высокий логический уровень на узле eq выключает Р-FET 228 и включает N-FET 226, который передает логическое значение с входной линией совпадений на выходную линию совпадений. Альтернативно, если бит адреса не совпадает с сохраненным битом данных, то один из N-FET 222 и N-FET 224 включен, и узел eq переводится на низкий логический уровень посредством N-FET, который включен. N-FET 226 выключен, Р-FET 228 включен, и выходная линия совпадений переведена на высокий логический уровень. Цепь 220х сравнения, таким образом, передает логическое значение по входной линии совпадений на выходную линию совпадений в случае, если есть совпадение, и обеспечивает значение, соответствующее высокому логическому уровню ( H ), по выходной линии совпадений, если имеет место несовпадение.

На Фиг.2В дано схематическое изображение последовательной ячейки 120y АЗУ, которое может быть использовано для реализации любой из последовательных ячеек 120y АЗУ на Фиг.1. Ячейка 120y АЗУ включает в себя ячейку 210 памяти, в которой хранится бит данных, и цепь сравнения 220y, которая сравнивает значение хранящегося бита данных с битом адреса. Цепь 220y сравнения включает в себя транзисторы N-FET 222, 224, 226 и Р-FET 228, которые подключены тем же способом, который описан выше при описании цепи 220х сравнения на Фиг.2A. Цепь 220y сравнения также включает в себя транзисторы Р-FET 232 и 234, затворы которых подключены к дополнительной строке qb данных и строке q данных соответственно, их истоки подключены к линии s поиска и дополнительной линии sb поиска соответственно, а их стоки соединены между собой и дополнительно подключены к затворам транзисторов FET 226 и 228. N-FET 222 и Р-FET 232 образуют вентиль на основе комплементарной МОП (металл-оксид-полупроводник) структуры (КМОП, CMOS), который контролируется посредством линий q и qb. N-FET 224 и Р-FET 234 составляют еще один КМОП-вентиль, который контролируется посредством линий qb и q.

На Фиг.2C дано схематическое изображение параллельной ячейки 122x АЗУ, которое может быть использовано для реализации любой из параллельных ячеек 122 АЗУ на Фиг.1. Ячейка 122x АЗУ включает в себя ячейку 210 памяти, которая хранит бит данных, и цепь 240х сравнения, которая сравнивает хранимый бит данных с битом адреса. Цепь 240х сравнения включает в себя три транзистора N-FET 242, 244 и 246. Затворы транзисторов N-FET 242 и 244 подключены к линии q данных и дополнительной линии qb данных соответственно, их истоки подключены к дополнительной линии sb поиска и линии поиска s соответственно, их строки соединены между собой и, кроме того, подключены к затвору N-FET 246. Сток N-FET 246 подключен к линии совпадений, а его исток подключен к виртуальному заземлению цепи match_gnd.

Р-FET 256 используется для предварительной зарядки линии совпадений. Сток Р-FET 256 подключен к напряжению питания V_DD, его исток подключен к линии совпадений, а его затвор - к линии предустановки pre.

Цепь 240х сравнения работает следующим образом. Перед выполнением поиска пo строке ячеек АЗУ, линия pre переводится на низкий логический уровень, Р-FET 256 включается, линия совпадений предварительно заряжается до напряжения питания V_DD, линия pre затем переводится на высокий логический уровень, и Р-FET 256 выключается. Дифференциальная линия поиска, s и sb, устанавливается в значение бита адреса. Если бит адреса совпадает с хранящимся битом данных, тогда один из N-FET 242 и 244 включается и переводит узел eq на низкий логический уровень, N-FET 246 выключается, и линия совпадений не приводится к виртуальному заземлению цепи. В противном случае, если бит адреса не совпадает с хранимым битом данных, то один из N-FET 242 и 244 включается и переводит узел eq на высокий логический уровень, N-FET 246 включается, и линия совпадений приводится к виртуальному заземлению цепи. Любая ячейка АЗУ, которая дает несовпадение, переводит линию совпадений на низкий логический уровень. Если все ячейки АЗУ в строке дают совпадение, то линия совпадений остается в предварительно заряженном состоянии высокого логического уровня.

На Фиг.2D дано схематическое изображение параллельной 122y ячейки АЗУ, на основе которого может быть построена любая из параллельных ячеек 122 АЗУ на Фиг.1. Ячейка 122y АЗУ включает в себя ячейку памяти 210, которая хранит бит данных, и цепь 240y сравнения, которая сравнивает хранимый бит данных с битом адреса. Цепь 240y сравнения включает в себя три транзистора N-FET 242, 244 и 246, которые подсоединены, как описано выше для цепи 240х сравнения на Фиг.2C. Цепь 240y сравнения также включает в себя транзисторы Р-FET 252 и 254, затворы которых подключены к дополнительной линии qb данных и линии q данных, соответственно, их истоки подключены к дополнительной линии sb поиска и линии s поиска соответственно, и их стоки соединены вместе и, кроме того, подключены к затвору N-FET 246. N-FET 242 и Р-FET 252 образуют КМОП-вентиль, который контролируется посредством линий q и qb. N-FET 244 и Р-FET 254 образуют еще один КМОП-вентиль, который контролируется посредством линий qb и q.

На Фиг.2A-2D изображены типовые конструкции последовательной и параллельной ячеек АЗУ. Конструкция этих ячеек может быть выполнена и по-другому.

Для параллельной схемы поиска линии совпадений для всех М строк предварительно заряжаются перед выполнением поиска. Обычно, совпадение со входным адресом происходит только в одной строке (если вообще происходит), и линия совпадения для этой строки остается на высоком логическом уровне. Совпадения для прочих строк не происходит, и линии совпадения для этих строк разряжены до низкого логического уровня. Каждая строка обладает довольно большой паразитной емкостью. Непрерывная предварительная зарядка и разрядка линий совпадения, обладающих высокой емкостью, является причиной высокого энергопотребления при параллельной схеме поиска.

Для последовательной схемы поиска входная линия совпадений для самой левой (или соответствующей LSB) последовательной ячейки АЗУ в каждой строке устанавливается в низкий логический уровень. Поиск по всем M строкам происходит параллельно, но для каждой строки единовременно осуществляется поиск только в отношении одного бита, до тех пор пока не произойдет несовпадение или поиск в отношении всех битов в строке не будет выполнен. Энергопотребление снижено, поскольку обладающая высокой емкостью линия совпадений не разряжается, когда имеется несовпадение для любого заданного бита. Однако скорость поиска невысока и зависит от количества ячеек АЗУ в строке. Кроме того, обычно необходимы синхронизирующие сигналы для управления последовательным поиском битов в каждой строке.

При смешанной последовательно-паралелльной схеме поиска делается попытка достичь и низкого энергопотребления, и высокой скорости поиска. Вероятность совпадения для любого заданного бита может быть принята за 50 процентов. Если биты в каждой строке независимы, что обычно верно для более младших битов, то вероятность совпадения после n битов равняется (1/2) ⁿ, а вероятность несовпадения после n битов равняется 1-(1/2) ⁿ. Например, вероятность несовпадения равняется 75% после двух битов, 87,5% после трех битов, 93,75% после четырех битов и так далее. Для достижения низкого энергопотребления может быть выполнен последовательный поиск для небольшого количества (например, четырех) битов. После поиска по этому небольшому количеству битов в большей части строк будет несовпадение, и параллельный поиск можно выполнить для оставшихся битов в каждой строке, который дает совпадение с последовательной частью.

На Фиг.3 показан одна строка 300 ячеек АЗУ для смешанной последовательно-паралелльной АЗУ. Строка 300 включает в себя последовательную секцию из четырех последовательных ячеек АЗУ, начиная с ячейки 120a и заканчивая ячейкой 120d и параллельную секцию из параллельных ячеек 122 АЗУ. Каждая из последовательных ячеек 120a-120d АЗУ может быть реализована, как показано на Фиг.2A или 2B. Каждая параллельная ячейка 122 АЗУ может быть реализована, как показано Фиг.2C или 2D.

Четыре последовательные ячейки 120a-120d АЗУ организованы в две пары, чтобы ограничить количество проходных транзисторов 226, которые соединены последовательно, и чтобы уменьшить паразитную емкость на входных и выходных линиях совпадения между последовательными ячейками АЗУ. Меньшее количество проходных транзисторов 226 уменьшает потерю напряжения на этих транзисторах, когда они включены. Меньшая паразитная емкость улучшает характеристики переходного режима на входных и выходных линиях совпадения, что позволяет уменьшить время прохождения сигнала и достичь большей скорости функционирования. На логическую схему ИЛИ-НЕ (NOR) 330 идет выходная линия m2b совпадения от ячейки 120b АЗУ, а также сигнал preB, и логическая схема ИЛИ-НЕ 330 приводит в действие затворы N-FET 332 и Р-FET 334. Исток N-FET 332 подключен к заземлению цепи, а его сток подключен к входной линии совпадений для последовательной ячейки 120c АЗУ. Исток Р-FET 334 подключен к заземлению цепи, а его сток подключен к выходной линии m4b совпадений для ячейки 120d АЗУ. На инвертор 340 идет выходная линия m4b совпадения из ячейки 120d АЗУ, и он обеспечивает линию совпадений для последовательной секции match_s. Затворы транзисторов N-FET 342 и 344 подключены к выходу инвертора 340 и линии par соответственно, их истоки подключены к заземлению цепи, и их стоки подключены к виртуальному заземлению цепи для параллельной секции match_gnd. К логической схеме И-НЕ (NAND) 350 идет выходная линия m4b совпадения из ячейки 120d АЗУ и сигнал parB. Затворы транзисторов Р-FET 352 и 354 подключены к выходу логической схемы И-НЕ 350 и к шине pre соответственно, их истоки подключены к линии совпадения для параллельной секции match_p, a их стоки подключены к напряжению питания V_DD. На логическую схему И (AND) 360 идут линии совпадения для последовательной и параллельной секций match_s и match_p, и она обеспечивает линию совпадения для строки.

Значительная часть совокупной потребляемой энергии для АЗУ обычно уходит на непрерывное предварительное заряжание и разряжание линий совпадения и линий поиска. Энергопотребление может быть уменьшено за счет поиска только по небольшой процентной доле строк, в которых происходит совпадение в последовательных секциях, как отмечено выше. В этом случае, только в небольшой процентной доле строк происходит предварительная зарядка и разрядка линий совпадений. Энергопотребление также может быть уменьшено невыполнением предварительного заряжания и разряжания линии поиска. Обычно линия s поиска и дополнительная линия sb поиска предустановлены на низкий логический уровень во время предварительной зарядки линий совпадений для того, чтобы избежать короткого замыкания напряжения питания V_DD на заземление цепи, например, с помощью Р-FET 256 и N-FET 246, показанных на Фиг.2C. Линия s или sb затем устанавливается в высокий логический уровень в зависимости от значения бита входного адреса. Предустановка линий s и sb на низкий логический уровень влечет за собой предварительное заряжание и разряжание одной из этих двух шин. Такой предустановки можно избежать посредством холостой работы линии match_gnd во время предварительной зарядки линии match_p, что предотвращает короткое замыкание напряжения питания на заземление цепи. Без предустановки линий поиска мощность рассеивается, только когда меняется значение бита входного адрес, а не для каждого поиска.

Архитектура, показанная на Фиг.3, поддерживает два режима смешанного последовательно-параллельного поиска. При последовательном режиме проводится последовательный поиск по четырем последовательным ячейкам АЗУ, а параллельный поиск по параллельным ячейкам проводится только в том случае, если происходит совпадение во всех последовательных ячейках АЗУ. При параллельном режиме проводится последовательный поиск по последовательным ячейкам АЗУ поиск по параллельным ячейкам АЗУ проводится параллельно, и последовательный и параллельный поиски выполняются одновременно, так что результаты поиска могут быть получены раньше. Для обоих режимов линия совпадений match_s для последовательной секции и линия совпадений match_p для параллельной секции объединены операцией «И» вместе, чтобы сформировать линию совпадения для целой строки, как показано на Фиг.3.

Для последовательного режима сигнал par находится на низком логическом уровне, а сигнал parB - на высоком логическом уровне. N-FET 344 выключен, линия match_gnd контролируется N-FET 342, и выход логической схемы И-НЕ 350 соответствует линии match_s. При наличии совпадения по всем последовательным ячейкам АЗУ, линия match_s находится на высоком логическом уровне, а линия match_gnd сбрасывается ни низкий логический уровень. И наоборот, если последовательные ячейки АЗУ не дают совпадения, тогда сигнал match_s находится на низком логическом уровне, Р-FET 352 включен, и линия match_p предварительно заряжается.

В случае параллельного режима, сигнал par находится на высоком логическом уровне, а сигнал parB - на низком логическом уровне. N-FET 344 включен, линия match_gnd сбрасывается на низкий логический уровень каждый раз, и параллельная секция работает в то время, когда происходит последовательный поиск. Выход логической схемы И-НЕ 350 находится на высоком логическом уровне, Р-FET 352 выключен, а линия match_p предварительно заряжается через Р-FET 354 с помощью сигнала pre.

Смешанный последовательно-параллельный поиск для строки 300 может быть выполнен следующим образом. По последовательной секции выполняется последовательный поиск - либо последовательно по одной ячейке АЗУ за раз, начиная с ячейки CAM 120a, либо параллельно по всем ячейкам АЗУ в последовательной секции. В случае совпадения каждая последовательная ячейка АЗУ передает результат поиска от предыдущей последовательной ячейки АЗУ и передает высокий логический уровень, если совпадения нет.

Если совпадение происходит во всех последовательных ячейках 120a-120d АЗУ, тогда выходная линия совпадения m4b из ячейки АЗУ 120d находится на низком логическом уровне, выход инвертора 340 будет на высоком логическом уровне, N-FET 342 включен, а линия match_gnd приведена к заземлению цепи. Линия match_p предварительно заряжена во время предыдущего поиска, и ячейки АЗУ в параллельной секции активированы, когда линия match_gnd приведена к заземлению цепи. Если происходит совпадение по всем параллельным ячейкам 122 АЗУ, то линия match_p остается на высоком логическом уровне. Выход логической схемы И 360 находится на высоком логическом уровне, если происходит совпадение и в последовательной, и в параллельной секциях.

Обратно, если какая-нибудь одна из последовательных ячеек 120a-120d АЗУ не дает совпадения, тогда выходная линия m4b совпадений ячейки 120d АЗУ будет на высоком логическом уровне, выход инвертора 340 будет на низком логическом уровне, N-FET 342 выключен, линия match_p работает вхолостую, и параллельная секция деактивируется. Линия parB находится на высоком логическом уровне для последовательного режима поиска, и низкий логический уровень на линии m4b дает в результате низкий логический уровень нa выходе логической схемы «И-НЕ» 350. Р-FET 352 включен и предварительно заряжает линию match_p. Если параллельная секция не была активирована при предыдущем поиске из-за того, что все последовательные ячейки АЗУ дали несовпадение, то Р-FET 352 требуется только небольшая подзарядка, чтобы устранить утечку заряда, которая могла произойти с момента предыдущего предварительного заряжания.

Если линия match_p только предварительно подзаряжается, когда последовательные ячейки АЗУ дают несовпадение, тогда линия match_p в некоторых случаях может давать ошибку. Одна такая ситуация возможна в случае, когда последовательные ячейки АЗУ дают совпадение, а параллельные ячейки АЗУ не дают совпадения для заданного поиска; и линия match_p не будет предварительно заряжена, как описано выше. Если и последовательные, и параллельные ячейки АЗУ дадут совпадение при следующем поиске, то параллельная секция может ошибочно показать несовпадение из-за того, что шина match_p не была предварительно заряжена при предыдущем поиске. Чтобы избежать ошибочного обнаружения для случая, описанного выше, линия match_p может быть предварительно заряжена перед каждым поиском с помощью сигнала preB. Эта предварительная зарядка может быть получена путем обеспечения высокого логического уровня на линии preB, что приводит к низкому логическому уровню на выходе логической схемы ИЛИ-НЕ 330. Низкий логический уровень от логической схемы ИЛИ-НЕ 330 включает Р-FET 334 и задает высокий логический уровень на шине m4b, что в свою очередь включает Р-FET 352 и предварительно заряжает линию match_p.

Линия preB также предотвращает установку линии match_gnd в низкий логический уровень в течение предварительной зарядки линии match_p. Если линия preB отсутствует и линия m2b находится на низком логическом уровне, то выход логической схемы «ИЛИ-НЕ» 330 находится на высоком логическом уровне, N-FET 332 включается, входная линия совпадений для последовательной ячейки 120c АЗУ находится на низком логическом уровне, линия m4b может быть на высоком логическом уровне, и линия match_s может быть на высоком логическом уровне, что затем могло бы привести линию match_gnd на низкий логический уровень. Параллельная секция затем могла бы быть активирована и закоротить линию match_p, которая предварительно заряжена до напряжения питания V_DD . Если линия preB присутствует и установлена в высокий логический уровень во время предварительной зарядки, тогда предотвращается сброс линии match_gnd на низкий логический уровень. Работающая вхолостую шина match_gnd блокирует секцию параллельных ячеек во время предварительной зарядки шины match_p.

Чтобы гарантировать, что логическая схема «ИЛИ-НЕ» 330 обеспечивает желаемое логическое значение для предварительной зарядки, сигнал preB генерируется с значительным запасом по времени. В частности, логическое состояние сигнала m2b должно быть задано до установления линии preB, чтобы гарантировать действительный выходной сигнал из логической схемы «ИЛИ-НЕ» 330. Этот запас по времени для линии preВ ограничивает скорость поиска по последовательной секции, что ограничивает скорость поиска по всей строке ячеек АЗУ.

На Фиг.4 изображена одна строка 400 ячеек АЗУ для последовательно-параллельного АЗУ без каких-либо синхронизирующих сигналов для последовательной секции. Строка 400 включает в себя последовательную секцию из четырех последовательных ячеек 120a-120d АЗУ и параллельную секцию из множества параллельных ячеек 122 АЗУ, как показано на Фиг.3. Строка 400 дополнительно включает в себя все вспомогательные схемы для строки 300 на Фиг.3, за исключением логической схемы «ИЛИ-НЕ» 330. Для примера реализации, показанного на Фиг.4, инвертер 430 заменяет логическую схему «ИЛИ-НЕ 330», и его вход подключен к линии m2b из последовательной ячейки 120b АЗУ, а его выход подключен к затворам транзисторов N-FET 332 и 334. Инвертер 430 и N-FET 332 образуют буферную цепь для линии m2b. Схемотехническое решение буферной цепи может быть и другим.

Смешанный последовательно-параллельный поиск для строки 400 может быть выполнен следующим образом. Перед выполнением поиска линия match_p предварительно заряжается путем предустановки линии поиска для второй последовательной ячейки 120b АЗУ, так что обе линии s2 и s2b находились в низком логическом уровне. Низкий логический уровень на линиях s2 и s2b включает N-FET либо 222, либо 224, что приводит узел eq2 на низкий логический уровень. Низкий логический уровень на узле eq2 включает Р-FET 228, что переводит шину m2b на высокий логический уровень и приводит выход инвертора 430 на низкий логический уровень. Низкий логический уровень на выходе инвертора 430 включает Р-FET 334, что переводит линию m4b на высокий логический уровень, приводит выход инвертора 340 на низкий логический уровень и устанавливает выход логической схемы «И-НЕ» 350 в низкий логический уровень. Низкий логический уровень на выходе инвертора 340 выключает N-FET 342, что приводит к холостой работе линии match_gnd. Низкий логический уровень нa выходе логической схемы «И-НЕ» 350 включает Р-FET 352, что предварительно заряжает линию match_p. После предварительной зарядки линии match_p, линии s2 и s2b для последовательной ячейки 120b АЗУ высвобождаются и принимают значение второго бита входного адреса. Затем может быть выполнен последовательный поиск по последовательной секции так, как было показано на Фиг.3. Предварительная зарядка может быть выполнена за одну стадию (например, в течение высокого логического уровня) тактового сигнала, а сравнение может быть выполнено в течение другой стадии (например, в течение низкого логического уровня) тактового сигнала.

Для примера реализации, показанного на Фиг.4, только дифференциальная линия поиска s2 и s2b для второй последовательной ячейки 120b АЗУ предустанавливается перед каждым поиском для предварительной зарядки линии match_p. Линии поиска для всех из остальных последовательных ячеек АЗУ в строке могут и не предустанавливаться. Например, первая последовательная ячейка 120a АЗУ может также быть предустановлена, но этого не требуется для предварительной зарядки линии match_p. При другом примере реализации линия поиска для последней последовательной ячейки АЗУ 120d предустанавливается перед каждым поиском, а линии поиска для всех остальных последовательных ячеек АЗУ могут и не предустанавливаться. При еще одном примере реализации линии поиска всех последовательных ячеек АЗУ предустанавливаются перед каждым поиском. В общем, линии поиска для любого количества последовательных ячеек АЗУ могут быть предустановлены, чтобы предварительно зарядить линию match_р. Так как мощность рассеивается при предустановке каждой линии поиска, желательно предустанавливать минимально возможное количество линий (например, одну) перед каждым поиском.

Фиг.5 иллюстрирует одну строку 500 ячеек АЗУ смешанного последовательно-параллельного АЗУ, которое поддерживает только последовательный режим поиска без каких-либо синхронизирующих сигналов для последовательной секции. Строка 500 включает в себя последовательную секцию из четырех последовательных ячеек 120a-120d АЗУ и параллельную секцию с множеством параллельных ячеек 122 АЗУ, как показано на Фиг.3 и 4. Строка 500 дополнительно включает в себя те же вспомогательные схемы, что и для строки 400 на Фиг.4, за исключением того, что логическая схема «ИЛИ-НЕ» 350, N-FET 344 и Р-FET 354 исключены из-за того, что параллельный поиск не поддерживается. Затвор Р-FET 352 подключен к выходу инвертора 340.

Для примера реализации, изображенного на Фиг.5, один из N-FET 342 и Р-FET 352 включен в любой заданный момент. Перед каждым поиском, линии s2 и s2b для второй последовательной ячейки АЗУ предустанавливаются, на выходе инвертора 340 формируется низкий логический уровень, Р-FET 352 включен, и линия match_p предварительно заряжена. Далее, Р-FET 352 выключается, N-FET 342 включается, линия match_gnd сбрасывается на низкий логический уровень, и параллельная секция активируется.

На Фиг.6 изображена одна строка 600 ячеек АЗУ для смешанного последовательно-параллельного АЗУ, которая поддерживает только последовательный режим поиска без каких-либо синхронизирующих сигналов для последовательной секции. Строка 600 включает в себя последовательную секцию из К последовательных ячеек 120a-120k АЗУ и параллельную секцию из множества параллельных ячеек 122 САМ. В общем случае, k>1 (т.е. k может быть 2, 3, 4 и так далее). Строка 600 включает в себя те же вспомогательные схемы, что и для строки 500 на Фиг.5, кроме инвертора 430, N-FET 332 и Р-FET 334. Для примера реализации, приведенного на Фиг.6, выходная линия совпадений для каждой последовательной ячейки АЗУ подключена напрямую к входной линии совпадений следующей последовательной ячейки АЗУ. Линии sk и skb для последней последовательной ячейки АЗУ предустанавливаются перед каждым поиском, чтобы предварительно зарядить линию match_р.

Фиг.4, 5 и 6 иллюстрируют типовые конструкции АЗУ, которые могут выполнять смешанный последовательно-параллельный поиск без каких-либо синхронизирующих сигналов для последовательной секции. Смешанное последовательно-параллельное АЗУ может также быть реализовано другим способом, основываясь на описании, приведенном здесь.

Фиг.7 иллюстрирует процесс 700 выполнения смешанного последовательно-параллельного поиска по многорядному АЗУ, скомпонованному из множества строк, где каждая строка имеет по меньшей мере одну последовательную ячейку АЗУ и по меньшей мере две параллельные ячейки АЗУ. Выполняют параллельный поиск по строкам АЗУ (этап 710). По меньшей мере одну линию поиска для по меньшей мере одной последовательной ячейки АЗУ в каждой строке предустанавливают для предварительной зарядки линии совпадений для параллельных ячеек АЗУ в строке (этап 712). Например, может быть предустановлена линия поиска для второй последовательной ячейки АЗУ (на Фиг.4 и 5) или последней последовательной ячейки АЗУ (на Фиг.6). Поиск по последовательным ячейкам АЗУ в каждой строке выполняют последовательно (этап 714). Поиск по параллельным ячейкам АЗУ в каждой строке выборочно выполняют параллельно (этап 716). Например, поиск по параллельным ячейкам АЗУ в каждой данной строке может проводиться (1) только, если последовательные ячейки АЗУ в этой строке дают совпадение или (2) одновременно с поиском по последовательным ячейкам АЗУ. Управление линией виртуального заземления для параллельных ячеек АЗУ в каждой строке может осуществляться таким образом, чтобы блокировать или разблокировать поиск по параллельным ячейкам АЗУ.

АЗУ, описанное здесь, может быть использовано для различных вариантов применения. Один иллюстративный вариант применения АЗУ описан ниже.

На Фиг.8 изображена блок-схема беспроводного устройства 800 в сети беспроводной связи. Беспроводное устройство 800 может быть сотовым телефоном, трубкой, беспроводным терминалом, наладонным компьютером (PDA) или любым другим электронным устройством. Беспроводная система может быть системой множественного доступа с кодовым разделением каналов (CDMA), системой множественного доступа с временным рaзделением каналов (TDMA), системой стандарта GSM, системой множественного доступа с частотным разделением каналов (FDMA), системой множественного доступа с ортогональным частотным разделением каналов (OFDMA) и так далее.

Беспроводное устройство 800 выполнено с возможностью обеспечивать двунаправленную связь по приемному тракту и передающему тракту. Для приемного тракта сигналы, передаваемые базовыми станциями, принимаются антенной 812 и поступают на приемный модуль (RCVR) 814. Приемный модуль 814 преобразует (т.е. фильтрует, усиливает и преобразует с понижением частоты) принятый сигнал, оцифровывает преобразованный сигнал и передает выборки данных на специальные микросхемы (ASIC) для дальнейшей обработки. Для передающего тракта подлежащие передаче от беспроводного устройства 800 данные поступают от ASIC 820 в передающий модуль (TMTR) 816. Передающий модуль 816 преобразует (фильтрует, усиливает и преобразует с повышением частоты) данные и формирует модулированный сигнал, который передается через антенну 812 на базовые станции.

ASIC 820 включает в себя различные модули, такие как, например, микропроцессор 822, цифровой сигнальный процессор (DSP) 824 и кэш-память 826. Микропроцессор 822 выполняет обработку общего назначения и может быть компьютером с сокращенным набором команд (RISC) или процессором другого типа. DSP 824 выполняет обработку данных для передающего тракта (кодирование, перемежение, модуляцию, формирование кодовых каналов, разнесение по спектру, фильтрацию и т.д.) и для приемного тракта (фильтрацию, обращенное разнесение по спектру, каналообразование, демодуляцию, обращенное перемежение, декодирование и т.д.). Обработка, которую должен выполнять DSP 824, зависит от системы связи. Кэш-память 830 хранит данные и/или программные коды для микропроцессора 822 и/или DSP 824. Кэш-память 830 может включать в себя АЗУ 832, которое хранит адреса для данных и/или программные коды, и ОЗУ 834, в котором хранятся данные и/или программные коды. Реализация АЗУ 832 может быть основана на любом из приведенных здесь вариантов конструкции, равно как и на любом другом варианте. Контроллер 840 управляет работой ASIC 820 и других модулей беспроводного устройства 800. Основная память 842 хранит программные коды и данные, которые используются контроллером 840.

АЗУ, описанное здесь, может быть реализовано в различных аппаратных модулях, таких как ASIC, DSP, устройство цифровой обработки сигналов (DSPD), программируемое логическое устройство (PLD), вентильная матрица с эксплуатационным программированием (FPGA), контроллер, процессор и другие электронные устройства. АЗУ может быть изготовлено с помощью различных технологий производства интегральных схем, таких как СМОS, N-MOS, P-МОS, биполярная CМОS (Bi-CМОS), биполярная и т.д. С помощью технологии СМОS можно изготавливать и транзисторы N-FET, и транзисторы Р-FET на одном и том же кристалле интегральной схемы, тогда как технология N-MOS позволяет производить только транзисторы N-FET, а технология P-MOS - только транзисторы Р-FET. АЗУ может быть изготовлено с использованием технологии любого размера (например, 130 нм, 65 нм, 30 нм и т.д.)

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