Введение

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

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

История

Дадли Аллен Бак изобрел концепцию памяти с адресным доступом по содержимому в 1955 году. Баку приписывают идею распознающего устройства.

Ассоциативный массив оборудования

В отличие от стандартной компьютерной памяти, памяти с произвольным доступом (RAM), в которой пользователь указывает адрес памяти, а RAM возвращает слово данных, хранящееся по этому адресу, в CAM пользователь предоставляет слово данных, а CAM осуществляет поиск по всей своей памяти, чтобы определить, содержится ли это слово данных где-либо в ней. Если слово данных найдено, CAM возвращает список одного или нескольких адресов хранения, по которым это слово было обнаружено. Таким образом, CAM представляет собой аппаратную реализацию того, что в программных терминах называется ассоциативным массивом. Схожая концепция встречается в устройстве распознавания данных, предложенном Дадли Алленом Баком в 1955 году.

Стандарты

Основное определение интерфейса для CAM и других сетевых поисковых механизмов было специфицировано в соглашении о взаимодействии под названием Look Aside Interface (LA 1 и LA 1B), разработанном Форумом сетевой обработки. Многочисленные устройства, соответствующие этому соглашению о взаимодействии, были произведены компаниями Integrated Device Technology, Cypress Semiconductor, IBM, Broadcom и другими. 11 декабря 2007 года OIF опубликовало соглашение об интерфейсе последовательного поиска (SLA).

Полупроводниковые реализации

CAM значительно быстрее, чем RAM в приложениях поиска данных. Однако у CAM есть и недостатки по стоимости. В отличие от чипа RAM, который имеет простые ячейки хранения, каждый отдельный бит памяти в полностью параллельной CAM должен иметь собственную схему сравнения для обнаружения совпадения между сохраненным и входным битами. Кроме того, сигналы совпадения из каждой ячейки в слове данных должны быть объединены для формирования сигнала полного совпадения слова данных. Эта дополнительная схема увеличивает физический размер и стоимость производства чипа CAM. Также дополнительная схема повышает энергопотребление, поскольку каждая схема сравнения активна на каждом тактовом цикле. Следовательно, CAM используется только в специализированных приложениях, где скорость поиска нельзя обеспечить менее дорогостоящим способом. Одной из первых успешных реализаций была интегральная схема и система ассоциативного процессора общего назначения. В начале 2000-х годов несколько полупроводниковых компаний, включая Cypress, IDT, Netlogic, Sibercore и MOSAID, представили продукты CAM, предназначенные для сетевых приложений. Эти продукты назывались сетевыми поисковыми движками (NSE), сетевыми поисковыми ускорителями (NSA) и процессорами, основанными на знаниях (KBP), но по сути представляли собой CAM со специализированными интерфейсами и функциями, оптимизированными для сетевых задач. В настоящее время Broadcom предлагает несколько семейств KBP.

Альтернативные варианты реализации

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

Трехмерные КАМ

Бинарный CAM является самым простым типом CAM и использует поисковые слова, состоящие исключительно из 1 и 0. Троичный CAM (TCAM) допускает третье состояние соответствия – X или "не важно" – для одного или нескольких битов в хранимом слове, что повышает гибкость поиска. Например, хранимое слово 10XX0 в троичном CAM будет соответствовать любому из четырех поисковых слов: 10000, 10010, 10100 или 10110. Эта повышенная гибкость поиска достигается за счет дополнительных затрат по сравнению с бинарным CAM, поскольку внутренняя ячейка памяти теперь должна кодировать три возможных состояния вместо двух в бинарном CAM. Это дополнительное состояние обычно реализуется путем добавления бита маски (бита выбора или игнорирования) к каждой ячейке памяти. В 2013 году компания IBM создала энергонезависимую TCAM, используя ячейки с 2 транзисторами и 2 резистивными запоминающими элементами (2T2R). Недавно группа международных ученых опубликовала конструкцию TCAM на основе гибридного ферроэлектрического FeFET.