Память с адресацией по содержимому ( CAM ) - это особый тип компьютерной памяти, используемый в некоторых приложениях для очень высокоскоростного поиска. Он также известен как ассоциативная память или ассоциативное хранилище и сравнивает входные данные поиска с таблицей сохраненных данных и возвращает адрес совпадающих данных. [1]
Блок распознавания слов данных был предложен Дадли Алленом Баком в 1955 г. [2]
CAM часто используется в сетевых устройствах, где он ускоряет операции с базой информации пересылки и таблицами маршрутизации . Этот вид ассоциативной памяти также используется в кэш-памяти. В ассоциативной кэш-памяти адрес и контент хранятся рядом. Когда адрес совпадает, соответствующий контент извлекается из кэш-памяти.
Аппаратный ассоциативный массив [ править ]
В отличие от стандартной компьютерной памяти, оперативной памяти (RAM), в которой пользователь предоставляет адрес памяти, а RAM возвращает слово данных, хранящееся по этому адресу, CAM спроектирован таким образом, что пользователь предоставляет слово данных, а CAM ищет его. всю память, чтобы увидеть, хранится ли это слово данных где-нибудь в ней. Если слово данных найдено, CAM возвращает список из одного или нескольких адресов хранения, где было найдено слово. Таким образом, CAM является аппаратным воплощением того, что в программном плане можно было бы назвать ассоциативным массивом . [3]
Стандарты [ править ]
Основное определение интерфейса для 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 используется только в специализированных приложениях, где скорость поиска не может быть достигнута менее дорогостоящим методом. Одной из первых успешных реализаций была ИС и система ассоциативного процессора общего назначения. [4]
Альтернативные реализации [ править ]
Чтобы достичь другого баланса между скоростью, объемом памяти и стоимостью, некоторые реализации эмулируют функцию CAM с помощью стандартного поиска по дереву или схем хеширования в оборудовании, используя аппаратные приемы, такие как репликация или конвейерная обработка, для повышения эффективной производительности. Эти конструкции часто используются в маршрутизаторах . [ необходима цитата ]
Ternary CAMs [ править ]
Двоичный CAM - это простейший тип CAM, в котором используются слова поиска данных, состоящие полностью из единиц и нулей . Тройной САМ ( ТСЫ ) [5] позволяет третье состояние соответствия из X или не заботитьсядля одного или нескольких битов в сохраненном слове, что добавляет гибкости поиску. Например, сохраненное слово «10XX0» в троичном CAM будет соответствовать любому из четырех поисковых слов «10000», «10010», «10100» или «10110». Дополнительная гибкость поиска требует дополнительных затрат по сравнению с двоичным CAM, поскольку ячейка внутренней памяти теперь должна кодировать три возможных состояния вместо двух для двоичного CAM. Это дополнительное состояние обычно реализуется путем добавления бита маски (бит «забота» или «безразличие») к каждой ячейке памяти.
Примеры приложений [ править ]
Память с адресацией по содержимому часто используется в компьютерных сетевых устройствах . Например, когда сетевой коммутатор получает фрейм данных от одного из своих портов, он обновляет внутреннюю таблицу с указанием MAC-адреса источника фрейма и порта, на котором он был получен. Затем он ищет MAC-адрес назначения в таблице, чтобы определить, на какой порт нужно переадресовать кадр, и отправляет его на этот порт. Таблица MAC-адресов обычно реализуется с помощью двоичного CAM, поэтому порт назначения можно найти очень быстро, что снижает задержку коммутатора.
Тернарные CAM часто используются в сетевых маршрутизаторах , где каждый адрес состоит из двух частей: префикса сети , размер которого может варьироваться в зависимости от конфигурации подсети , и адреса хоста, занимающего оставшиеся биты. Каждая подсеть имеет сетевую маску, которая указывает, какие биты адреса являются префиксом сети, а какие - адресом хоста. Маршрутизация выполняется путем просмотра таблицы маршрутизации, поддерживаемой маршрутизатором, которая содержит каждый известный префикс сети назначения, соответствующую маску сети и информацию, необходимую для маршрутизации пакетов к этому месту назначения. Без CAM маршрутизатор сравнивает адрес назначения маршрутизируемого пакета с каждой записью в таблице маршрутизации, выполняя побитовое Ис маской сети и сравнив ее с префиксом сети. Если они равны, соответствующая информация маршрутизации используется для пересылки пакета. Использование троичного CAM для таблицы маршрутизации делает процесс поиска очень эффективным. Адреса сохраняются с использованием "безразлично" для хостовой части адреса, поэтому поиск адреса назначения в CAM немедленно дает правильную запись маршрутизации; и маскирование, и сравнение выполняются аппаратным обеспечением CAM. Это работает, если (а) записи хранятся в порядке уменьшения длины сетевой маски, и (б) оборудование возвращает только первую совпадающую запись; таким образом, используется совпадение с самой длинной сетевой маской (совпадение по самому длинному префиксу ). [6]
Другие приложения CAM включают:
- Полностью ассоциативные контроллеры кеш-памяти ЦП и резервные буферы трансляции (TLB)
- База данных двигателей
- Аппаратное сжатие данных
- Искусственные нейронные сети [7]
- Система предотвращения вторжений
- Несколько специализированных компьютеров, таких как Goodyear STARAN , были построены для реализации CAM.
См. Также [ править ]
- Сеть с адресацией по содержанию
- Параллельный процессор с адресацией по содержанию
- Контент-адресное хранилище или файловая система
- Редкая распределенная память
- Пространство кортежа
Ссылки [ править ]
- ^ Pagiamtzis и Шейхолесла (2006), стр. 712-713
- ^ TRW Computer Division архивации 5 августа 2011, в Wayback Machine , 1963, стр. 17.
- ^ Hannum et al. (2004)
- ^ Сторман и др. (1992)
- ^ Хьюкаби, Дэвид (2004). CCNP Руководство по сертификации экзаменов BCMSN: самообучение CCNP . ISBN 9781587200779.
- ^ Варгезе, Джордж , Сетевая алгоритмика: междисциплинарный подход к разработке быстрых сетевых устройств , Морган Кауфманн, 2005
- ^ Хинтон, Джеффри Э. (1984). «Распределенные представительства» .
Библиография [ править ]
- Анаргирос Крикелис, Чарльз К. Уимс (редакторы) (1997). Ассоциативная обработка и процессоры , IEEE Computer Science Press. ISBN 0-8186-7661-2
- Ханнум и др .. (2004). Система и метод для сброса и инициализации полностью ассоциативного массива в известное состояние при включении или через определенное состояние машины . Патент США 6,823,434. Доступно при поиске на http://patft.uspto.gov/netahtml/PTO/search-bool.html
- Pagiamtis, K .; Шейхолеслами, А. (2006). «Схемы и архитектуры адресуемой памяти (CAM): учебное пособие и обзор» (PDF) . Журнал IEEE по твердотельным схемам . 41 (3): 712–727. Bibcode : 2006IJSSC..41..712P . DOI : 10.1109 / JSSC.2005.864128 .
- Стормон, компакт-диск; Troullinos, NB; Салех, EM; Чаван А.В.; Брюле, MR; Олдфилд, СП; ИС и система ассоциативного процессора CMOS общего назначения, Coherent Research Inc., Ист-Сиракузы, Нью-Йорк, США, IEEE Micro, декабрь 1992 г., том: 12 Выпуск: 6.
- Компьютерное подразделение TRW. (1963). Первый промежуточный отчет об оптимальном использовании компьютеров и вычислительной техники в системах управления вооружением на борту корабля . (BuWeps-Project RM1004 M88-3U1). Александрия, Вирджиния: Центр оборонной документации по научной и технической информации.
Внешние ссылки [ править ]
- CAM Primer
- Схемы и архитектуры контентно-адресуемой памяти (CAM): учебное пособие и обзор
- Aspex - компьютерная архитектура, построенная на ассоциативной памяти
- Инициирование работы по спецификации последовательного резервного копирования (внизу страницы 1)
- Соглашение о последовательном внешнем интерфейсе OIF
- Арифметическая обработка с использованием ассоциативной памяти
- SimpleRBM - очень маленькая машина Больцмана с ограничениями , включающая алгоритм обучения, который представляет собой разновидность адресуемой памяти битовых векторов.