stringtranslate.com

Содержимо-адресуемая память

Адресуемая память по содержимому

Память с адресацией по содержимому ( 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). [ нужна цитата ]

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

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

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

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

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

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

Тройные CAM

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

Двоичный 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 включают:

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

Рекомендации

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

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

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