Параллельная ассоциативная память

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

 

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

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

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

На фиг.13 показана функциональная блок-схема, иллюстрирующая конфигурацию обычного СЗУПВ (статического запоминающего устройства с произвольной выборкой) с функцией контроля по четности. Как показано на фиг.13, СЗУПВ 1 содержит n (натуральное число) ячеек 2 хранения данных, одну ячейку 3 хранения четности и дешифратор 4 адреса. Указанные элементы предусматриваются во множестве наборов одинаковой конфигурации. Такое СЗУПВ 1 дополнительно содержит генератор 5 четности при записи, схему 6 усиления чтения, генератор 7 четности при чтении и блок 8 сравнения четности.

Во время записи данных дешифратор 4 адреса выбирает n ячеек 2 хранения данных и соответствующую ячейку 3 хранения четности в соответствии с адресом i записи. В выбранные ячейки 2 хранения данных записываются введенные извне n-разрядные записываемые данные WD. В этот момент генератор 5 четности при записи вычисляет четность при записи WP на основании введенных n-разрядных записываемых данных WD. Вычисленная четность при записи WP записывается в ячейку 3 хранения четности.

С другой стороны, во время чтения данных, дешифратор 4 адреса выбирает n ячеек 2 хранения данных и соответствующую ячейку 3 хранения четности в соответствии с адресом i чтения. Затем из выбранных ячеек 2 хранения данных считываются n-разрядные считываемые данные RD, а из выбранной ячейки 3 хранения четности считывается четность при чтении RP, при этом для считывания и усиления используется схема 6 усиления чтения. Генератор 7 четности при чтении вычисляет расчетную четность CP на основании считанных n-разрядных считываемых данных RD. Блок 8 сравнения четности сравнивает расчетную четность CP и четность при чтении RP, считанную из ячейки 3 хранения четности, и выводит сигнал ошибки четности PE при несовпадении двух четностей друг с другом.

Тем самым осуществляют контроль по четности путем считывания считываемых данных RD из каждой ячейки и вычисления их расчетной четности CP, что является достаточным для СЗУПВ 1, поскольку считываемые данные RD считываются только по адресу одной указанной ячейки СЗУПВ 1.

С другой стороны, известна параллельная ассоциативная память, или параллельная контентно-адресуемая память (далее - параллельная АП (ассоциативная память)), которая способна одновременно осуществлять поиск по всем адресам и выводить адрес(-а), по которому(-ым) хранятся те же данные, что и введенные данные, или считывать ассоциативные данные, связанные с такими данными. Желательно, чтобы параллельная АП также обладала функцией контроля по четности. В частности, желательно, чтобы контроль по четности осуществлялся в процессе операции поиска данных, что является неотъемлемой и основной функцией параллельной АП.

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

В патенте US 7010741 (патентный документ 1) и в патенте US 7350137 (патентный документ 2) описана АП с функцией контроля по четности, при этом контроль по четности осуществляется путем считывания данных, а не во время поиска данных.

Кроме того, в патентной заявке JP 63-177242, выложенной до проведения экспертизы (патентный документ 3), описан способ контроля по четности ассоциативной памяти. Там же, на стр.2, строки 1-11, левый нижний столбец указано, что "согласно известному уровню техники, контроль по четности при поиске данных в матрице ячеек памяти осуществляется путем считывания искомых данных из матрицы ячеек памяти, генерации четности данных и ее сравнения с ранее сохраненной информацией о четности. Иными словами, для осуществления контроля по четности требуется последовательность операций, включающая получение доступа к матрице ячеек памяти, генерацию четности и сравнение, из-за чего контроль по четности занимает слишком много времени. В основу изобретения положена задача создания способа контроля по четности, позволяющего с высокой скоростью обнаруживать ошибку в данных".

В одном из примеров эта ассоциативная память имеет адресный регистр 1, матрицу 2 ячеек памяти для хранения искомых данных, схему 3 считывания для усиления искомых данных, матрицу 2' ячеек хранения четности искомых данных, схему 3' считывания для усиления четности, схему 4 сравнения, схему 5 генерации четности, схему 4' сравнения и схему 6 подтверждения достоверности сигналов, как показано на фиг.1 упомянутой заявки. Старшие биты "a" адреса, выведенные из адресного регистр 1a, представляют собой данные поиска, а младшие биты "b" представляют собой адрес для выбора одной ячейки из матрицы ячеек 2 хранения данных, в которых осуществлялся поиск. Схема 4 сравнения сравнивает данные поиска с искомыми данными "d", считанными и усиленными в соответствии с адресом, и в случае их совпадения выводит сигнал "g" совпадения. Схема 5 генерации четности генерирует сигнал "f1 четности данных "а" поиска. Схема 4' сравнения сравнивает бит "f четности с битом "d" четности, считанным и усиленным в соответствии с адресом. Схема 6 подтверждения достоверности сигналов проверяет достоверность выходного сигнала "h" схемы 4' сравнения с использованием (на основании) сигнала "g" совпадения и выводит сигнал "i" контроля по четности. Поскольку в этом примере бит четности, сгенерированный на основании данных поиска, может использоваться при контроле по четности ячейки памяти искомых данных, операция может осуществляться быстрее, чем при генерации четности на основании искомых данных.

Помимо этого, в другом примере вместо схемы 3 считывания и схемы 4 сравнения из описанного выше примера описана схема 7 для обнаружения совпадения между шиной "c" передачи данных, т.е. сигналом с низким уровнем усиления, выведенным из ячейки памяти, находящейся в матрице 2 ячеек памяти искомых данных, и данными "a" поиска, а также для вывода сигнала "g" совпадения, как показано на фиг.3 этой же заявки. С помощью схемы 7 обнаружения совпадения может быть быстро получен сигнал "g" совпадения, поскольку сигнал с низким уровнем амплитуды не усиливают для обнаружения совпадения. Тем не менее, контроль по четности во всех этих схемах осуществляется с использованием как данных, так и битов четности, считываемых в соответствии с адресом.

В одном из дополнительных примеров вместо схемы 3 считывания и схемы 4' сравнения из описанного выше примера описана схема 7' обнаружения совпадения между шиной "c" передачи данных, т.е. сигналом с низким уровнем усиления, выведенным из ячейки памяти, находящейся в матрице 2' ячеек хранения четности, и битом "f четности, сгенерированным на основании данных "a" поиска, а также для вывода выходного сигнала "h", как показано на фиг.8 той же заявки. С помощью схемы 7' обнаружения совпадения может быть быстрее получен сигнал "i" контроля по четности, поскольку сигнал с низким уровнем амплитуды не усиливают для обнаружения совпадения. Тем не менее, контроль по четности во всех этих схемах осуществляется с использованием как данных, так и битов четности, считываемых в соответствии с адресом.

Эта ассоциативная память является не параллельной ассоциативной памятью для одновременного поиска по всем адресам, а последовательной ассоциативной памятью для поочередного поиска по адресам. Иными словами, из матрицы 2 ячеек памяти искомых данных выбирают один адрес в соответствии с адресом, заданным в адресном регистре 1, и считывают искомые данные по этому адресу. Схема 4 сравнения или схема 7 обнаружения совпадения сравнивает считанные искомые данные с данными поиска, заданными в адресном регистре 1. При этом из матрицы 2' ячеек хранения четности выбирают один адрес в соответствии с адресом, заданным в адресном регистре 1, и считывают бит четности по этому адресу. Схема 4' сравнения или схема 7' обнаружения совпадения сравнивает считанный бит четности с битом четности, сгенерированным схемой 5 генерации четности. Таким образом, поскольку схемы 4, 4' сравнения или схемы 7, 7' обнаружения совпадения расположены вне матриц 2, 2' ячеек памяти, контроль данных и контроль по четности может осуществляться только по одному адресу за один раз. Кроме того, данные должны считываться из ячейки памяти до сравнения четности, как показано на фиг.2B и 2B' этой же заявки.

Помимо этого, в публикации патентной заявки 9-22595, выложенной до проведения экспертизы (патентный документ 4), описано ассоциативное запоминающее устройство. Там же, на стр.2, строки 24-48, правый столбец указано, что "ассоциативное запоминающее устройство содержит память данных для управления данными обработки объекта поиска и память справочных данных для управления справочными данными, взаимно однозначно соответствующими данным обработки, а после получения данных поиска в справочных данных, управляемых памятью справочных данных, осуществляют поиск соответствующих справочным данным данных поиска и считывают из памяти данных указанные данными поиска данные обработки. В ассоциативном запоминающем устройстве, сконфигурированном таким образом, в памяти данных хранится бит четности данных обработки, соответствующий данным обработки, а при считывании данных обработки, указанных данными поиска, считывают спаренный с ними бит четности, вычисляют бит четности считанных данных обработки, определяют наличие совпадения между расчетным битом четности и считанным битом, и проверяют считанные данные обработки на наличие искажений. Тем не менее, хотя согласно известному уровню техники можно обнаруживать, искажены ли данные обработки, хранящиеся в памяти данных, невозможно обнаруживать, искажены ли справочные данные, управляемые памятью справочных данных, даже в случае их искажения. Соответственно, если согласно известному уровню техники справочные данные искажены, преимущественно осуществляют поиск справочных данных, к которым не следует обращаться, в результате чего из памяти данных выводятся ошибочные данные обработки. Настоящее изобретение создано с учетом этих обстоятельств, а в его основу положена задача создания нового ассоциативного запоминающего устройства, которое способно наверняка обнаруживать, искажены ли данные обработки, совпадающие с данными поиска".

В одном из примеров это ассоциативное запоминающее устройство содержит память 20 данных обработки, память 21 справочных данных для хранения справочных данных, взаимно однозначно соответствующих данным обработки, и вывода сигнала совпадения справочных данных, соответствующих данным поиска, память 22 четности, занимающую то же пространство памяти, что и память 20 данных, для хранения битов четности справочных данных, соответствующих данным обработки, схему 24 генерации четности для генерации бита четности данных поиска и схему 25 контроля по четности для контроля совпадения бита четности, сгенерированного схемой 24 генерации четности, и бита четности, выведенного из памяти 22 четности, как показано на фиг.3 этой же заявки.

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

Перечень ссылок

Патентный документ

Патентный документ 1: US 7010741

Патентный документ 2: US 7350137

Патентный документ 3: публикация патентной заявки 63-177242, выложенной до проведения экспертизы

Патентный документ 4: публикация патентной заявки 9-22595, выложенной до проведения экспертизы

Раскрытие изобретения

Задачи, решаемые в изобретении

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

Средства решения задачи и преимущества изобретения

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

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

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

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

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

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

Краткое описание чертежей

На фиг.1 показа функциональная блок-схема, иллюстрирующая конфигурацию параллельной ассоциативной памяти (АП) согласно первому варианту осуществления настоящего изобретения,

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

на фиг.3 - принципиальная схема, иллюстрирующая конфигурацию запоминающей ячейки АП и ее периферийной ИС, показанных на фиг.1,

на фиг.4 - принципиальная схема, иллюстрирующая конфигурацию ячейки хранения четности и ее периферийной ИС, показанных на фиг.1,

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

на фиг.6 - функциональная блок-схема, иллюстрирующая конфигурацию параллельной АП согласно второму варианту осуществления изобретения,

на фиг.7 - принципиальная схема иллюстрирующая конфигурацию запоминающей ячейки АП и ее периферийной ИС, показанных на фиг.6,

на фиг.8 - функциональная блок-схема, иллюстрирующая конфигурацию параллельной АП согласно третьему варианту осуществления изобретения,

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

на фиг.10 - принципиальная схема, иллюстрирующая конфигурацию ячейки хранения четности и ее периферийной ИС, показанных на фиг.9,

на фиг.11 - функциональная блок-схема, иллюстрирующая конфигурацию параллельной АП согласно пятому варианту осуществления изобретения,

на фиг.12 - принципиальная схема, иллюстрирующая конфигурацию ячейки хранения четности и ее периферийной ИС, показанных на фиг.11, и

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

Описание осуществлений

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

Первый вариант осуществления

Как показано на фиг.1, параллельная АП 10 согласно первому варианту осуществления изобретения одновременно осуществляет поиск по всем адресам и определяет, хранятся ли в памяти те же данные, что и введенные данные. Параллельная АП 10 содержит генератор 12 четности при записи и поиске, множество мест 14 памяти, соответствующее множеству адресов, и схему "И-НЕ" (отрицательную логику) 16. На фиг.1 в качестве примера проиллюстрировано одно место 14 памяти.

Генератор 12 четности при записи и поиске генерирует биты четности WP и SP n-разрядных данных WD и SD, вводимых во время записи и во время поиска, соответственно. Каждое из указанных мест 14 памяти содержит n (натуральное число) запоминающих ячеек 17 ассоциативной памяти, одну ячейку 3 хранения четности, дешифратор 4 адреса, схему-защелку 18, схему 20 "исключающее ИЛИ" и схему 22 "И-НЕ".

Как показано на фиг.2, каждая из запоминающих ячеек 17 ассоциативной памяти содержит сердечник 9 и блок 42 сравнения данных. Кроме того, n запоминающих ячеек 17 ассоциативной памяти обладают функцией сохранения n-разрядных записываемых данных WD, введенных во время записи, и функцией сравнения n-разрядных данных поиска SAID, введенных во время поиска, и хранящихся n-разрядных записываемых данных WD. В каждом сердечнике 9 ячейки хранится соответствующий один бит записываемых данных WD. Каждый блок 42 сравнения данных сравнивает соответствующий один бит данных поиска SD и один бит записываемых данных WD, хранящийся в соответствующем сердечнике 9.

Каждое из указанных мест 14 памяти дополнительно имеет схему обнаружения совпадения слов, предназначенную для активации сигнала DM совпадения слов данных до высокого уровня (потенциала источника питания VDD) при совпадении n-разрядных данных поиска SD, введенных во время поиска, и n-разрядных данных, хранящихся в запоминающих ячейках 17 ассоциативной памяти. Точнее говоря, схема 11 обнаружения совпадения слов содержит шину ML поиска совпадений, схему 13 подзарядки шины совпадений и схему 15 считывания. Схема 13 подзарядки шины совпадений предварительно заряжает шину ML поиска совпадений до высокого уровня. Каждый блок 42 сравнения данных разряжает шину ML поиска совпадений до низкого уровня (нулевого потенциала GND) при отсутствии совпадения соответствующего одного бита данных поиска SD и одного бита данных, хранящихся в соответствующем сердечнике 9 ячейки. Схема 15 считывания определяет и усиливает потенциал шины ML поиска совпадений.

Как показано на фиг.1, в ячейке 3 хранения четности хранится бит четности WP, сгенерированный во время записи генератором 12 четности при записи и поиске.

Схема-защелка 18 фиксирует состояние сигнала DM совпадения слов данных в ответ на синхронизирующий сигнал CLK. Схема 20 "исключающее ИЛИ" определяет, совпадают ли бит четности SP, сгенерированный генератором 12 четности при записи и поиске во время поиска, и бит четности RP (=WP), хранящийся в ячейке 3 хранения четности, и в случае их совпадения активирует сигнал/РМ совпадения по четности в отрицательной логике. Схема 22 "И-НЕ" подтверждает сигнал/РМ совпадения по четности, выведенный из схемы 20 "исключающее ИЛИ", с использованием сигнала DML совпадения слов данных, состояние которого зафиксировано схемой-защелкой 18. Когда сигнал DML совпадения слов данных, состояние которого зафиксировано, активируют до высокого уровня и обнаружено совпадение данных, при деактивации сигнала/РМ совпадения по четности до низкого уровня (нулевого потенциала GND) и наличии совпадении по четности, достоверный сигнал PMV совпадения по четности активируют до высокого уровня, что указывает на совпадение как данных, так и по четности. С другой стороны, когда сигнал DML совпадения слов данных, состояние которого зафиксировано, активируют до высокого уровня и обнаружено совпадение данных, при деактивации сигнала/РМ совпадения по четности до высокого уровня и наличии несовпадения по четности, достоверный сигнал PMV совпадения по четности деактивируют до низкого уровня, что указывает на совпадение данных, но несовпадение по четности.

Схема 16 "И-НЕ" активирует сигнал ошибки четности PE, если по меньшей мере один из множества подтвержденных (достоверных) сигналов PMV совпадения по четности, выведенных из множества мест 14 памяти, имеет низкий уровень (неактивен).

Как показано на фиг.3, ассоциативная память 10 дополнительно содержит разрядные шины чтения, записи, поиска BLTRWS и BLCRWS и словарную шину WL. Хотя на фиг.3 в качестве примера проиллюстрирована только одна пара разрядных шин, предусмотрено n пар разрядных шин BLTRWS и BLCRWS по числу n запоминающих ячеек 17 ассоциативной памяти. Хотя на фиг.3 в качестве примера проиллюстрирована только одна словарная шина, предусмотрено множество словарных шин WL, соответствующих множеству мест памяти. Хотя на фиг.3 в качестве примера проиллюстрирована только одна шина поиска совпадений, предусмотрено множество шин ML поиска совпадений, соответствующих множеству мест памяти.

Разрядные шины BLTRWS и BLCRWS предварительно заряжают до высокого уровня во время чтения данных и записи данных и предварительно заряжают до низкого уровня во время поиска данных во время поиска данных. Словарную шину WL активируют до высокого уровня во время чтения данных и записи данных. Шину ML поиска совпадений предварительно заряжают до высокого уровня во время поиска данных.

В случае совпадения всех n-разрядных данных SD, полученных извне, и n-разрядных данных, хранящихся в запоминающих ячейках 17 ассоциативной памяти, шину ML поиска совпадений не разряжают, и поддерживают заряд на высоком уровне. С другой стороны, в случае несовпадения даже на один бит n-разрядных данных, полученных извне, и n-разрядных данных, хранящихся в запоминающих ячейках 17 ассоциативной памяти, шину ML поиска совпадений разряжают до низкого уровня. Схема 15 считывания внутри схемы 11 обнаружения совпадения слов определяет и усиливает потенциал шины ML поиска совпадений, как показано на фиг.2, при этом в случае совпадения данных сигнал DM совпадения слов данных устанавливают на высоком уровне, а в случае несовпадения данных сигнал DM совпадения слов данных устанавливают на низком уровне.

Сердечник 9 ячейки содержит схему-защелку 24 для фиксации одного бита данных и входные транзисторы TNA0 и TNA1, образованные соответствующим n-канальным МОП-транзистором. Схема-защелка 24 содержит КМОП-инверторы (на основе комплементарных металло-оксидных полупроводников) 26 и 28 с перекрестными обратными связями. Входной узел 30 КМОП-инвертор 26 соединен с запоминающим узлом SNC, а его выходной узел 32 соединен с запоминающим узлом SNT. Входной узел 34 КМОП-инвертора 28 соединен с запоминающим узлом SNT, его выходной узел 36 соединен с запоминающим узлом SNC.

КМОП-инвертор 26 содержит нагрузочный транзистор ТР0, образованный p-канальным МОП-транзистором, и задающий транзистор TN0, образованный n-канальным МОП-транзистором. Затвор нагрузочного транзистора ТР0 соединен с входным узлом 30, его исток соединен с источником 38 питания, а его сток соединен с выходным узлом 32. Затвор задающего транзистора TN0 соединен с входным узлом 30, его исток соединен с заземлением 40, а его сток соединен с выходным узлом 32.

КМОП-инвертор 28 содержит нагрузочный транзистор ТР1, образованный n-канальным МОП-транзистором, и задающий транзистор TN1, образованный n-канальным МОП-транзистором. Затвор нагрузочного транзистора ТР1 соединен с входным узлом 34, его исток соединен с источником 38 питания, а его сток соединен с выходным узлом 36. Затвор задающего транзистора TN1 соединен с входным узлом 34, его исток соединен с заземлением 40, а его сток соединен с выходным узлом 36.

Затвор входного транзистора TNA0 соединен со словарной шиной WL, одна из его областей, включающих истоковую область и стоковую область, соединена с разрядной шиной BLTRWS, а другая из его областей, включающих истоковую область и стоковую область, соединена с запоминающим узлом SNT. Затвор входного транзистора TNA1 соединен со словарной шиной WL, одна из его областей, включающих истоковую область и стоковую область, соединена с разрядной шиной BLCRWS, а другая из его областей, включающих истоковую область и стоковую область, соединена с запоминающим узлом SNC.

Блок 42 сравнения данных сравнивает входные, или введенные, данные, поступившие посредством разрядных шин BLTRWS и BLCRWS, с данными, хранящимися в схеме-защелке 24. В частности, блок 42 сравнения данных содержит сравнивающие транзисторы TNC0 и TNC1, образованные соответствующим n-канальным МОП-транзистором, и согласующий транзистор TNM, образованный n-канальным МОП-транзистором. Затвор сравнивающего транзистор TNC0 соединен с запоминающим узлом SNC, одна из его областей, включающих истоковую область и стоковую область, соединена с разрядной шиной BLTRWS, а другая из его областей, включающих истоковую область и стоковую область, соединена с узлом MN согласования битов. Затвор сравнивающего транзистора TNC1 соединен с запоминающим узлом SNT, одна из его областей, включающих истоковую область и стоковую область, соединена с разрядной шиной BLCRWS, а другая из его областей, включающих истоковую область и стоковую область, соединена с узлом MN согласования битов. Затвор согласующего транзистора TNM соединен с узлом MN согласования битов, его исток соединен с заземлением 40, а его сток соединен с шиной ML поиска совпадений.

Как показано на фиг.4, ячейка 3 хранения четности имеет такой же сердечник 9 ячейки, что и запоминающие ячейки 17 ассоциативной памяти. Вместе с тем, ячейка 3 хранения четности не имеет блока 42 сравнения данных, содержащегося в запоминающих ячейках 17 ассоциативной памяти. Кроме того, потенциал запоминающего узла SNT непосредственно считывают как четность RP. Помимо этого, разрядные шины BLTRW и BLCRW используют как для чтения, так и записи, при этом их предварительно заряжают до высокого уровня во время чтения данных и записи данных, и не изменяют зарядовое состояние во время поиска данных. Предусмотрено в общей сложности (n+1) пар разрядных шин, включая разрядные шины чтения и записи BLTRW и BLCRW и разрядные шины чтения, записи, поиска BLTRWS и BLCRWS.

Хотя, как показано на фиг.3, четность RP считывают из запоминающего узла SNT, она может считываться из другого запоминающего узла SNC, как показано на фиг.5. В этом случае предусмотрен КМОП-инвертор 43 для корректировки логического уровня.

Далее будет описана работа ассоциативной памяти 10.

Операции записи и чтения преимущественно не отличаются от обычных операций записи и чтения. Если обрисовать их в общих чертах, при операции записи введенные n-разрядные данные WD записывают в n запоминающих ячеек 17 ассоциативной памяти. Одновременно генератор 12 четности при записи и поиске вычисляет бит четности WP на основании n-разрядных данных WD. Вычисленный бит четности WP записывают в ячейку 3 хранения четности. С другой стороны, при операции чтения считывают n-разрядные данные из n запоминающих ячеек 17 ассоциативной памяти. Во время чтения осуществляют контроль по четности обычным способом, описанным в разделе "Уровень техники".

Операция поиска отличается от обычной операции поиска и будет подробно описана далее. Для поиска данных, хранящихся в запоминающих ячейках 17 ассоциативной памяти, сначала предварительно заряжают до высокого уровня шину ML поиска совпадений и предварительно заряжают до низкого уровня разрядные шины BLTRWS и BLCRWS. В это время включают сравнивающий транзистор TNC0 или TNC1 в зависимости от того, для какого запоминающего узла SNT или SNC установлен высокий уровень, при этом для узла MN согласования битов установлен низкий уровень. Соответственно, согласующий транзистор TNM выключен. Если в этом состоянии в разрядные шины BLTRWS и BLCRWS поступают искомые данные SD, поддерживают низкий уровень узла MN согласования битов в запоминающих ячейках 17 ассоциативной памяти, в которых искомые данные SD и хранящиеся данные совпадают, при этом уровень узла MN согласования битов повышается до высокого в запоминающих ячейках 17 ассоциативной памяти, в которых они не совпадают. Соответственно, в запоминающих ячейках 17 ассоциативной памяти, в которых данные не совпадают, включают согласующий транзистор TNM, при этом уровень шины ML поиска совпадений снижается до низкого, что указывает на несовпадение данных. Иными словами, при совпадении n-разрядных данных SD, введенных во время поиска, и n-разрядных данных, хранящихся в запоминающих ячейках 17 ассоциативной памяти, сигнал DM совпадения слов данных активируют до высокого уровня. С другой стороны, при несовпадении этих данных даже на один бит, сигнал DM совпадения слов данных деактивируют до низкого уровня. Сигнал DM совпадения слов данных фиксируется схемой-защелкой 18.

Одновременно генератор 12 четности при записи и поиске вычисляет бит четности SP на основании n-разрядных данных поиска SD. Кроме того, из ячейки 3 хранения четности считывают бит четности RP. Схема 20 "исключающее ИЛИ" сравнивает вычисленный бит четности SP и считанный бит четности RP. При совпадении битов четности SP и RP для сигнала/РМ совпадения по четности устанавливают низкий уровень, а при несовпадении битов четности SP и четности RP для сигнала/РМ совпадения по четности устанавливают высокий уровень. Поскольку сигнал/РМ совпадения по четности является незначащим (бессмысленным) в месте 14 памяти, в котором данные не совпадают, если сигнал DML совпадения слов данных, зафиксированный схемой-защелкой 18, находится на высоком уровне, схема 22 "И-НЕ" проверяет достоверность сигнала РМ совпадения по четности, т.е. подтверждает его. При совпадении бита четности SP и бита четности RP для подтвержденного сигнала PMV совпадения по четности устанавливают высокий уровень, а при несовпадении бита четности SP и бита четности RP для достоверного сигнала PMV совпадения по четности устанавливают низкий уровень.

Поскольку n-разрядные данные поиска SD одновременно поступают во все места 14 памяти, описанная операция одновременно осуществляется во всех местах 14 памяти. В местах 14 памяти, в которых введенные n-разрядные данные поиска SD и хранящиеся n-разрядные данные совпадают, сигнал DM совпадения слов данных устанавливают на высоком уровне. Соответственно, из этого места 14 памяти выводят значащий подтвержденный сигнал PMV совпадения по четности. Если по меньшей мере один из множества подтвержденных сигналов PMV совпадения по четности, выведенный из множества мест 14 памяти, имеет низкий уровень, указывающий на несовпадение по четности, сигнал ошибки четности PE устанавливают на высоком уровне.

В описанном выше варианте осуществления изобретения во время поиска данных вместо сравнения бита четности, вычисленного на основании данных, считанных из запоминающих ячеек 17 ассоциативной памяти, с битом четности RP, хранящимся в ячейке 3 хранения четности, сравнивают друг с другом бит четности SP, вычисленный генератором 12 четности при записи и поиске, и бит четности RP, хранящийся в ячейке 3 хранения четности, за счет чего контроль по четности может осуществляться с высокой скоростью. Кроме того, поскольку контроль данных и контроль по четности одновременно осуществляется во всех местах 14 памяти, соответствующих всем адресам, контроль по четности может осуществляться с более высокой скоростью.

Помимо этого, подтверждение (проверку достоверности) сигнала/РМ совпадения по четности, выведенного из схемы 20 "исключающее ИЛИ", осуществляют только при совпадении данных поиска SD, введенных извне, и данных, хранящихся в запоминающих ячейках 17 ассоциативной памяти, за счет чего из места 14 памяти, в котором обнаружено несовпадение данных, не выводят незначащий сигнал/РМ совпадения по четности.

К тому же, если по меньшей мере один из множества достоверных сигналов PMV совпадения по четности имеет низкий уровень, устанавливают высокий уровень сигнала ошибки четности PE, за счет чего можно определять, что в параллельной ассоциативной памяти 10 содержатся ошибочные данные, когда в любом из мест 14 памяти, в котором хранятся достоверные данные, присутствует ошибки четности.

Второй вариант осуществления изобретения

Если в первом варианте осуществления изобретения порт записи и порт поиска объединены друг с другом, во втором варианте осуществления порт записи и порт поиска выполнены независимо друг от друга. В частности, как показано на фиг.6, генератор 44 четности при записи и генератор 46 четности при поиске выполнены по отдельности. Генератор 44 четности при записи генерирует бит четности WP входных n-разрядных записываемых данных WD. Генератор 46 четности при поиске генерирует бит четности SP входных n-разрядных данных поиска SD. Во время записывают записи записываемые данные WD в запоминающие ячейки 17 ассоциативной памяти, вычисляют бит четности WP на основании записываемых данных WD и записывают в ячейку 3 хранения четности. Во время поиска одновременно осуществляют поиск в местах 14 памяти, соответствующих всем адресам, и определяют, хранятся ли в запоминающих ячейках 17 ассоциативной памяти данные, совпадающие с данными поиска SD, в то время как вычисляют бит четности SP на основании данных поиска SD, и определяют, совпадает ли бит четности SP с битом четности RP, хранящимся в ячейке 3 хранения четности.

Кроме того, разрядные шины делятся на разрядные шины чтения и записи и специализированные разрядные шины поиска. В частности, как показано на фиг.7, отдельно предусмотрены разрядные шины чтения и записи BLTRW и BLCRW и специализированные разрядные шины поиска BLTS и BLCS. Входные данные WD записывают в запоминающие ячейки 17 ассоциативной памяти посредством разрядных шин чтения и записи BLTRW и BLCRW, а данные, считанные из запоминающих ячеек 17 ассоциативной памяти, выводят посредством разрядных шин чтения и записи BLTRW и BLCRW. Входные данные поиска SD поступают в специализированные разрядные шины поиска BLTS и BLCS.

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

Третий вариант осуществления изобретения

Схема-защелка 18, предусмотренная в первом варианте осуществления изобретения, в третьем варианте осуществления изобретения отсутствует. В частности, как показано на фиг.8, сигнал DM совпадения слов данных поступает непосредственно в схему 22 "И-НЕ".

Четвертый вариант осуществления изобретения

Вместо схемы 20 "исключающее ИЛИ" из первого варианта осуществления изобретения, в четвертом варианте осуществления предусмотрено, что функцией, эквивалентной схеме 20 "исключающее ИЛИ", обладает каждая ячейка 3 хранения четности. В частности, как показано на фиг.9 и 10, в разрядные шины BLTRWS и BLCRWS, соответствующие ячейке 3 хранения четности, вводят бит четности SP, а в ячейке 3 хранения четности предусмотрен блок 48 сравнения четности. Блок 48 сравнения четности, который содержит сравнивающие транзисторы TNC0 и TNC1, образованные соответствующим n-канальным МОП-транзистором, и КМОП-инвертор 50, образованный p-канальным МОП-транзистором ТРС и n-канальным МОП-транзистором TNC, определяет, совпадают ли бит четности SP, полученный посредством разрядных шин BLTRWS и BLCRWS, и бит четности, хранящийся в ячейке 3 хранения четности, и активирует сигнал/РМ совпадения по четности до низкого уровня в случае их совпадения или деактивирует сигнал/РМ совпадения по четности до высокого уровня в случае их несовпадения. Этот сигнал/РМ совпадения по четности подают в схему 22 "И-НЕ".

В четвертом варианте осуществления изобретения схема-защелка 18 может отсутствовать, как и в третьем варианте осуществления изобретения, показанном на фиг.8

Пятый вариант осуществления изобретения

Второй вариант осуществления изобретения, показанный на фиг.6 и 7, и четвертый вариант осуществления изобретения, показанный на фиг.9 и 10, могут быть объединены. В частности, как показано на фиг.11 и 12, в пятом варианте осуществления изобретения в разрядные шины BLTS и BLCS, соответствующие ячейке 3 хранения четности, подают бит четности SP, сгенерированный генератором 46 четности при поиске, а блок 48 сравнения четности находится внутри ячейки 3 хранения четности.

В пятом варианте осуществления изобретения, как и в третьем варианте осуществления изобретения, показанном на фиг.8, схема-защелка 18 может отсутствовать.

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

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

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

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