Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

См. Также [ править ]

  • Сеть с адресацией по содержанию
  • Параллельный процессор с адресацией по содержанию
  • Контент-адресное хранилище или файловая система
  • Редкая распределенная память
  • Пространство кортежа

Ссылки [ править ]

  1. ^ Pagiamtzis и Шейхолесла (2006), стр. 712-713
  2. ^ TRW Computer Division архивации 5 августа 2011, в Wayback Machine , 1963, стр. 17.
  3. ^ Hannum et al. (2004)
  4. ^ Сторман и др. (1992)
  5. ^ Хьюкаби, Дэвид (2004). CCNP Руководство по сертификации экзаменов BCMSN: самообучение CCNP . ISBN 9781587200779.
  6. ^ Варгезе, Джордж , Сетевая алгоритмика: междисциплинарный подход к разработке быстрых сетевых устройств , Морган Кауфманн, 2005
  7. ^ Хинтон, Джеффри Э. (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 - очень маленькая машина Больцмана с ограничениями , включающая алгоритм обучения, который представляет собой разновидность адресуемой памяти битовых векторов.