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

Память с адресацией по содержимому ( 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, в котором используются слова поиска данных, полностью состоящие из единиц и нулей . Тройная 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 включают:

Полностью ассоциативные контроллеры кэша и резервные буферы трансляции. ^[12]
баз данных Механизмы
сжатия данных Аппаратное обеспечение
Искусственные нейронные сети ^[13]
Системы предотвращения вторжений
Сетевые процессоры
Несколько специализированных компьютеров, таких как Goodyear STARAN , были созданы для реализации CAM.

См. также

Ссылки

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

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

Анаргирос Крикелис, Чарльз К. Уимс (редакторы) (1997). Ассоциативная обработка и процессоры , IEEE Computer Science Press. ISBN 0-8186-7661-2
США 6823434 , Ханнум и др., «Система и способ сброса и инициализации полностью ассоциативного массива до известного состояния при включении питания или через состояние, специфичное для машины», опубликовано в 2004 г.
Пагиамтис, К.; Шейхолеслами, А. (2006). «Схемы и архитектуры памяти с адресацией по содержимому (CAM): учебное пособие и обзор» (PDF) . Журнал IEEE твердотельных схем . 41 (3): 712–727. Бибкод : 2006IJSSC..41..712P . дои : 10.1109/JSSC.2005.864128 . S2CID 11178331 .
Стормон, CD; Труллинос, Северная Каролина; Салех, Э.М.; Чаван, А.В.; Брюле, MR; Олдфилд, СП; ИС и система ассоциативного процессора КМОП общего назначения, Coherent Research Inc., Ист-Сиракьюс, Нью-Йорк, США, IEEE Micro, декабрь 1992 г., том: 12, выпуск: 6.

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

[1] «К. Пагиамцис * и А. Шейхолеслами, Схемы и архитектуры с адресуемой по содержимому памятью (CAM): учебное пособие и обзор, журнал IEEE Journal of Solid-State Circuits, стр. 712–727, март 2006 г.» (PDF) . Архивировано (PDF) из оригинала 15 марта 2007 г.

[2] Компьютерный отдел TRW. (1963). Первый промежуточный отчет по оптимальному использованию компьютеров и вычислительной техники в системах управления корабельным вооружением . (BuWeps-Проект RM1004 М88-3У1). Александрия, Вирджиния: Центр оборонной документации научной и технической информации.

[3] TRW Computer Division. Архивировано 5 августа 2011 г., в Wayback Machine , 1963, стр. 17.

[4] Соглашение о реализации интерфейса Look-Aside (LA-1B) (PDF) , 4 августа 2004 г.

[5] Стормон, CD; Труллинос, Северная Каролина; Салех, Э.М.; Чаван, А.В.; Брюле, 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 — это небольшая ассоциативная память, которая отображает виртуальные адреса в реальные.

[Hinton,_Geoffrey_E_19842-13] Хинтон, Джеффри Э. (1984). «Распределенные представления» . Архивировано из оригинала 2 мая 2016 г. Проверено 14 декабря 2017 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]