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

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

Блок распознавания слова данных был предложен Дадли Аллен Бак в 1955 г.[2]

CAM часто используется в сетевые устройства где скорость база экспедиторской информации и таблица маршрутизации операции.

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

В отличие от стандартной компьютерной памяти, оперативная память (RAM), в котором пользователь предоставляет адрес памяти, а RAM возвращает слово данных, хранящееся по этому адресу, CAM спроектирован таким образом, что пользователь предоставляет слово данных, а CAM просматривает всю свою память, чтобы увидеть, является ли это слово данных хранится где угодно в нем. Если слово данных найдено, CAM возвращает список из одного или нескольких адресов хранения, где было найдено слово. Таким образом, CAM - это аппаратное воплощение того, что в программном плане можно было бы назвать ассоциативный массив.[3]

Стандарты

Основное определение интерфейса для CAM и других сетевые поисковые системы было указано в соглашении о совместимости, которое называется Внешний вид интерфейса (LA-1 и LA-1B), разработанные Форум сетевой обработки. Многочисленные устройства, соответствующие соглашению о совместимости, были произведены Интегрированная технология устройств, Cypress Semiconductor, IBM, Broadcom и другие. 11 декабря 2007 г. OIF опубликовал соглашение о последовательном дополнительном интерфейсе (SLA).[нужна цитата ]

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

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

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

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

Альтернативный подход к реализации основан на наложенных кодовых словах или закодированных словах, которые используются для более эффективных операций с базой данных, поиска информации и логического программирования, с аппаратными реализациями, основанными как на RAM, так и на дисковой технологии мониторинга головки.[5][6]

Тернарные САМ

Двоичный CAM это простейший тип CAM, в котором используются слова для поиска данных, полностью состоящие из 1 и 0. Тернарный CAM (TCAM)[7] позволяет третье соответствующее состояние «X» или «безразлично» для одного или нескольких битов в сохраненном слове данных, что добавляет гибкости поиску. Например, троичный CAM может иметь сохраненное слово «10XX0», которое будет соответствовать любому из четырех поисковых слов «10000», «10010», «10100» или «10110». Дополнительная гибкость поиска требует дополнительных затрат по сравнению с двоичным CAM, поскольку ячейка внутренней памяти теперь должна кодировать три возможных состояния вместо двух для двоичного CAM. Это дополнительное состояние обычно реализуется путем добавления бита маски (бит «забота» или «безразличие») к каждой ячейке памяти.

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

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

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

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

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

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

  1. ^ Пагиамцис и Шейхолеслами (2006), стр. 712–713.
  2. ^ Компьютерное подразделение TRW В архиве 5 августа 2011 г. Wayback Machine, 1963, с. 17.
  3. ^ Hannum et al. (2004)
  4. ^ Storman et al. (1992)
  5. ^ Мудрый, Майкл Дж; Пауэрс, Дэвид М. В. (1984). «Индексирование предложений Пролога с помощью наложенных кодовых слов и закодированных слов». Международный симпозиум по логическому программированию: 203–210.
  6. ^ Коломб, Роберт М (1991). «Повышение унификации в PROLOG за счет индексации пунктов». Журнал логического программирования. 1 (10): 23–44. Дои:10.1016/0743-1066(91)90004-9.
  7. ^ Хьюкаби, Дэвид (2004). CCNP Руководство по сертификации экзаменов BCMSN: самообучение CCNP. ISBN  9781587200779.
  8. ^ Варгезе, Джордж, Сетевая алгоритмика: междисциплинарный подход к разработке быстрых сетевых устройств, Морган Кауфманн, 2005 г.
  9. ^ Хинтон, Джеффри Э. (1984). «Распределенные представительства».

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

внешняя ссылка