Память с адресацией по содержимому ( CAM ) — это особый тип компьютерной памяти, используемый в некоторых приложениях высокоскоростного поиска. Она также известна как ассоциативная память или ассоциативное хранилище и сравнивает входные данные поиска с таблицей сохраненных данных и возвращает адрес совпадающих данных. [1]
CAM часто используется в сетевых устройствах , где он ускоряет операции пересылки информационной базы и таблицы маршрутизации . Этот вид ассоциативной памяти также используется в кэш-памяти. В ассоциативной кэш-памяти и адрес, и содержимое хранятся рядом. Если адрес совпадает, соответствующий контент извлекается из кэш-памяти.
Дадли Аллен Бак изобрел концепцию содержательно-адресуемой памяти в 1955 году. Баку приписывают идею единицы распознавания . [2]
В отличие от стандартной компьютерной памяти, оперативной памяти (ОЗУ), в которой пользователь указывает адрес памяти, а ОЗУ возвращает слово данных, хранящееся по этому адресу, CAM спроектирована таким образом, что пользователь вводит слово данных, а CAM ищет его. всю память, чтобы увидеть, сохранено ли где-нибудь в ней это слово данных. Если слово данных найдено, CAM возвращает список из одного или нескольких адресов хранения, где это слово было найдено. Таким образом, CAM — это аппаратное воплощение того, что с точки зрения программного обеспечения можно было бы назвать ассоциативным массивом .
Похожую концепцию можно найти в блоке распознавания слов данных , предложенном Дадли Алленом Баком в 1955 году. [3]
Основное определение интерфейса для CAM и других сетевых поисковых систем было указано в соглашении о совместимости, называемом Look-Aside Interface (LA-1 и LA-1B), разработанном Network Processing Forum . [4] Многочисленные устройства, соответствующие соглашению о совместимости, были произведены компаниями Integrated Device Technology , Cypress Semiconductor , IBM , Broadcom и другими. 11 декабря 2007 г. OIF опубликовал соглашение о серийном интерфейсе (SLA). [ нужна цитата ]
CAM намного быстрее, чем RAM в приложениях поиска данных. Однако у CAM есть недостатки в стоимости. В отличие от чипа ОЗУ , который имеет простые ячейки памяти, каждый отдельный бит памяти в полностью параллельном CAM должен иметь свою собственную связанную схему сравнения для обнаружения совпадения между сохраненным битом и входным битом. Кроме того, выходные данные совпадения каждой ячейки в слове данных должны быть объединены для получения полного сигнала совпадения слов данных. Дополнительная схема увеличивает физический размер и стоимость производства CAM-чипа. Дополнительная схема также увеличивает рассеиваемую мощность, поскольку каждая схема сравнения активна в каждом такте. Следовательно, CAM используется только в специализированных приложениях, где скорость поиска не может быть достигнута менее затратным методом. Одной из успешных ранних реализаций была интегральная схема и система ассоциативного процессора общего назначения. [5]
В начале 2000-х годов несколько компаний-производителей полупроводников, включая Cypress , IDT , Netlogic , Sibercore [6] и MOSAID, представили продукты CAM, ориентированные на сетевые приложения. Эти продукты назывались «Сетевые поисковые системы» (NSE), «Ускорители сетевого поиска» (NSA) и «Процессоры на основе знаний» (KBP), но по сути представляли собой CAM со специализированными интерфейсами и функциями, оптимизированными для работы в сети. В настоящее время Broadcom предлагает несколько семейств KBP. [7]
Чтобы достичь другого баланса между скоростью, объемом памяти и стоимостью, некоторые реализации эмулируют функцию CAM, используя стандартные конструкции поиска по дереву или хеширования в аппаратном обеспечении, используя аппаратные приемы, такие как репликация или конвейерная обработка, для повышения эффективной производительности. Эти конструкции часто используются в маршрутизаторах . [ нужна цитация ] Алгоритм Лулеа является эффективной реализацией поиска совпадений по самым длинным префиксам, как это требуется в таблицах маршрутизации Интернета.
Двоичный CAM — это самый простой тип CAM, в котором используются слова поиска данных, полностью состоящие из единиц и нулей . Тернарная CAM ( TCAM ) [8] допускает третье состояние соответствия X или не учитывает один или несколько битов в сохраненном слове, тем самым добавляя гибкости поиску. Например, сохраненное слово 10XX0 в троичном CAM будет соответствовать любому из четырех поисковых слов: 10000 , 10010 , 10100 или 10110 . Дополнительная гибкость поиска достигается за дополнительную плату по сравнению с двоичной CAM, поскольку ячейка внутренней памяти теперь должна кодировать три возможных состояния вместо двух для двоичной CAM. Это дополнительное состояние обычно реализуется путем добавления бита маски ( бит заботы или безразличия ) к каждой ячейке памяти. В 2013 году IBM изготовила энергонезависимый TCAM с использованием ячеек с 2 транзисторами и 2 резистивными запоминающими устройствами (2T-2R). [9] Конструкция TCAM с использованием гибридного сегнетоэлектрического FeFET была недавно опубликована группой международных ученых. [10]
Содержимо-адресуемая память часто используется в компьютерных сетевых устройствах . Например, когда сетевой коммутатор получает кадр данных с одного из своих портов, он обновляет внутреннюю таблицу, указывая MAC-адрес источника кадра и порт, на котором он был получен. Затем он ищет MAC-адрес назначения в таблице, чтобы определить, на какой порт необходимо переслать кадр, и отправляет его через этот порт. Таблица MAC-адресов обычно реализуется с помощью двоичного CAM, поэтому порт назначения можно найти очень быстро, что снижает задержку коммутатора.
Тройные CAM часто используются в сетевых маршрутизаторах , где каждый адрес состоит из двух частей: префикса сети , размер которого может меняться в зависимости от конфигурации подсети , и адреса хоста, занимающего оставшиеся биты. Каждая подсеть имеет маску сети, которая определяет, какие биты адреса являются сетевым префиксом, а какие — адресом хоста. Маршрутизация осуществляется путем обращения к таблице маршрутизации, поддерживаемой маршрутизатором, которая содержит каждый известный префикс сети назначения, соответствующую маску сети и информацию, необходимую для маршрутизации пакетов к этому месту назначения. В простой программной реализации маршрутизатор сравнивает адрес назначения маршрутизируемого пакета с каждой записью в таблице маршрутизации, выполняя побитовое «И» с маской сети и сравнивая ее с сетевым префиксом. Если они равны, для пересылки пакета используется соответствующая информация о маршрутизации. Использование троичного CAM для таблицы маршрутизации делает процесс поиска очень эффективным. Адреса сохраняются с использованием без учета хостовой части адреса, поэтому поиск адреса назначения в CAM немедленно возвращает правильную запись маршрутизации; и маскирование, и сравнение выполняются аппаратным обеспечением CAM. Это работает, если (а) записи сохраняются в порядке уменьшения длины маски сети и (б) оборудование возвращает только первую совпадающую запись; таким образом, используется совпадение с самой длинной маской сети ( совпадение самого длинного префикса ). [11]
Другие приложения CAM включают:
TLB — это небольшая ассоциативная память, которая отображает виртуальные адреса в реальные.