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

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

Иллюстрации

Показать все

Реферат

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). По меньшей мере одну линию поиска для по меньшей мере одной последо