stringtranslate.com

Память с адресацией по содержимому

Память с адресацией по содержимому

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

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

История

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

Аппаратный ассоциативный массив

В отличие от стандартной компьютерной памяти, оперативной памяти (RAM), в которой пользователь вводит адрес памяти, а RAM возвращает слово данных, хранящееся по этому адресу, 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 опубликовал соглашение о последовательном интерфейсе Look-aside (SLA). [ требуется ссылка ]

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

Двоичная ячейка CMOS CAM, состоящая из ячейки 6T SRAM и 4 транзисторов сравнения. Когда данные на линиях поиска (SL) отличаются от данных, хранящихся в ячейке через битовые линии (BL), линия сопоставления (ML) будет переведена в низкий уровень, чтобы указать на несовпадение. Если ни одна из ячеек на линии сопоставления не указывает на несовпадающий бит, линия сопоставления останется высокой на уровне предварительной зарядки, чтобы указать на совпадение слова. Обе линии поиска могут удерживаться на логическом «0» в качестве условия поиска «не важно». Линии поиска и битовые линии могут быть объединены в одну пару линий данных.

CAM намного быстрее RAM в приложениях поиска данных. Однако у CAM есть недостатки в стоимости. В отличие от микросхемы RAM , которая имеет простые ячейки хранения, каждый отдельный бит памяти в полностью параллельной CAM должен иметь свою собственную связанную схему сравнения для обнаружения соответствия между сохраненным битом и входным битом. Кроме того, выходные сигналы соответствия из каждой ячейки в слове данных должны быть объединены для получения полного сигнала соответствия слова данных. Дополнительная схема увеличивает физический размер и стоимость производства микросхемы CAM. Дополнительная схема также увеличивает рассеивание мощности, поскольку каждая схема сравнения активна в каждом такте. Следовательно, CAM используется только в специализированных приложениях, где скорость поиска не может быть достигнута с использованием менее дорогостоящего метода. Одной из успешных ранних реализаций была ИС и система ассоциативного процессора общего назначения. [5]

В начале 2000-х годов несколько полупроводниковых компаний, включая Cypress , IDT , Netlogic , Sibercore, [6] и MOSAID, представили продукты CAM, ориентированные на сетевые приложения. Эти продукты были обозначены как Network Search Engines (NSE), Network Search Accelerators (NSA) и Knowledge-based Processors (KBP), но по сути были CAM со специализированными интерфейсами и функциями, оптимизированными для работы в сети. В настоящее время Broadcom предлагает несколько семейств KBP. [7]

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

Чтобы достичь другого баланса между скоростью, объемом памяти и стоимостью, некоторые реализации эмулируют функцию CAM, используя стандартный поиск по дереву или хеширование в аппаратном обеспечении, используя аппаратные трюки, такие как репликация или конвейеризация, для ускорения эффективной производительности. Эти разработки часто используются в маршрутизаторах . [ необходима цитата ] Алгоритм Лулео является эффективной реализацией для поиска соответствия самого длинного префикса, как требуется в таблицах маршрутизации Интернета.

Тройные CAM-модули

Ячейка CMOS Ternary CAM, состоящая из двух ячеек SRAM 6T и 4 транзисторов сравнения. Обычно противоположные логические уровни, либо '0' и '1', либо '1' и '0', будут храниться в двух ячейках. Для состояния безразличия '0' будет храниться в обеих ячейках, так что линия соответствия ML не будет переведена в низкий уровень для любой комбинации данных линии поиска (SL).

Двоичный CAM является простейшим типом CAM и использует слова поиска данных, состоящие полностью из 1 и 0. Троичный CAM ( TCAM ) [8] допускает третье совпадающее состояние X или do n't care для одного или нескольких битов в сохраненном слове, тем самым добавляя гибкости поиску. Например, сохраненное слово 10XX0 в троичном CAM будет соответствовать любому из четырех поисковых слов 10000 , 10010 , 10100 или 10110. Дополнительная гибкость поиска имеет дополнительные затраты по сравнению с двоичным CAM, поскольку внутренняя ячейка памяти теперь должна кодировать три возможных состояния вместо двух для двоичного CAM. Это дополнительное состояние обычно реализуется путем добавления бита маски ( бит care или don't care ) к каждой ячейке памяти. В 2013 году IBM изготовила энергонезависимый TCAM с использованием ячеек 2-транзистор/2-резистивного хранения (2T-2R). [9] Недавно группа международных ученых опубликовала проект TCAM с использованием гибридного сегнетоэлектрика FeFET . [10]

Примеры приложений

Содержимое адресуемой памяти часто используется в сетевых устройствах компьютеров . Например, когда сетевой коммутатор получает кадр данных с одного из своих портов, он обновляет внутреннюю таблицу с исходным MAC-адресом кадра и портом, на который он был получен. Затем он ищет MAC-адрес назначения в таблице, чтобы определить, на какой порт необходимо переслать кадр, и отправляет его на этот порт. Таблица MAC-адресов обычно реализуется с помощью двоичного CAM, поэтому порт назначения можно найти очень быстро, что сокращает задержку коммутатора.

Троичные CAM часто используются в сетевых маршрутизаторах , где каждый адрес состоит из двух частей: сетевого префикса , который может различаться по размеру в зависимости от конфигурации подсети , и адреса хоста, который занимает оставшиеся биты. Каждая подсеть имеет сетевую маску, которая определяет, какие биты адреса являются сетевым префиксом, а какие биты являются адресом хоста. Маршрутизация выполняется путем обращения к таблице маршрутизации, поддерживаемой маршрутизатором, которая содержит каждый известный сетевой префикс назначения, связанную сетевую маску и информацию, необходимую для маршрутизации пакетов к этому месту назначения. В простой программной реализации маршрутизатор сравнивает адрес назначения пакета, который должен быть маршрутизирован, с каждой записью в таблице маршрутизации, выполняя побитовое И с сетевой маской и сравнивая ее с сетевым префиксом. Если они равны, соответствующая информация о маршрутизации используется для пересылки пакета. Использование троичного CAM для таблицы маршрутизации делает процесс поиска очень эффективным. Адреса хранятся с использованием не заботясь о хостовой части адреса, поэтому поиск адреса назначения в CAM немедленно извлекает правильную запись маршрутизации; И маскирование, и сравнение выполняются аппаратным обеспечением CAM. Это работает, если (a) записи хранятся в порядке убывания длины сетевой маски, и (b) оборудование возвращает только первую соответствующую запись; таким образом, используется соответствие с самой длинной сетевой маской ( соответствие с самым длинным префиксом ). [11]

Другие приложения CAM включают в себя:

Смотрите также

Ссылки

  1. ^ "К. Пагиамтзис* и А. Шейхолеслами, Схемы и архитектуры памяти с адресацией по содержимому (CAM): Учебное пособие и обзор, Журнал твердотельных схем IEEE, стр. 712-727, март 2006 г." (PDF) . Архивировано (PDF) из оригинала 2007-03-15.
  2. ^ TRW Computer Division. (1963). Первый промежуточный отчет об оптимальном использовании компьютеров и вычислительных методов в системах управления корабельным оружием. (BuWeps-Project RM1004 M88-3U1). Александрия, Вирджиния: Центр документации по научной и технической информации Министерства обороны.
  3. ↑ TRW Computer Division. Архивировано 5 августа 2011 г., Wayback Machine , 1963 г., стр. 17.
  4. ^ Соглашение о внедрении интерфейса Look-Aside (LA-1B) (PDF) , 2004-08-04
  5. ^ Стормон, CD; Труллинос, NB; Салех, EM; Чаван, AV; Брюле, MR; Олдфилд, JV (декабрь 1992 г.). «Универсальная ассоциативная ИС КМОП-процессора и система». IEEE Micro . 12 (6): 68–78. doi :10.1109/40.180249. S2CID  206432751.
  6. ^ "Sibercore Technologies - Silicon Solutions for Cyberspace". Архивировано из оригинала 2003-04-19.
  7. ^ "16 нм гетерогенные процессоры на основе знаний (KBP)". Архивировано из оригинала 2017-05-19.
  8. ^ Хакаби, Дэвид (2004). Руководство по сертификации экзамена CCNP BCMSN: Самостоятельное обучение CCNP. Cisco Press. ISBN 9781587200779.
  9. ^ Цзин Ли, Р. Монтойе, М. Ишии, К. Ставиас, Т. Нисида, К. Малони, Г. Дитлоу, С. Льюис, Т. Маффитт, Р. Джордан, Леланд Чанг, П. Сонг, «Энергонезависимая TCAM-память размером 1 Мб, 0,41 мкм2, с ячейками 2T-2R, двухбитным кодированием и тактируемым самоссылочным зондированием», Симпозиум IEEE по технологии СБИС, 2013 г.
  10. ^ Сюньчжао Инь, Юй Цянь, М. Имани, К. Ни, Чао Ли, Грейс Ли Чжан, Бин Ли, Ульф Шлихтман, Чэн Чжо, «Сегнетоэлектрические троичные запоминающие устройства с адресацией содержимого для энергоэффективного ассоциативного поиска», Труды IEEE по автоматизированному проектированию интегральных схем и систем, апрель 2023 г.
  11. ^ Варгезе, Джордж , Сетевые алгоритмы: междисциплинарный подход к проектированию быстрых сетевых устройств , Морган Кауфманн, 2005
  12. ^ Смит, Алан Джей (сентябрь 1982 г.). «Кэш-память» (PDF) . Computing Surveys . 14 (3): 473–530. doi :10.1145/356887.356892. S2CID  6023466. Архивировано из оригинала (PDF) 2022-04-03 . Получено 3 апреля 2022 г. . TLB — это небольшая ассоциативная память, которая отображает виртуальные адреса в реальные.
  13. ^ Хинтон, Джеффри Э. (1984). "Распределенные представления". Архивировано из оригинала 2016-05-02 . Получено 2017-12-14 .

Библиография

Внешние ссылки