Ассоциативная память
Ассоциативная память (АП) или ассоциативное запоминающее устройство (АЗУ) — специальный вид машинной памяти, используемый в приложениях очень быстрого поиска. Известна также под терминами «память, адресуемая по содержимому», «ассоциативное запоминающее устройство», «контентно-адресуемая память» или «ассоциативный массив», хотя последний термин чаще используется в программировании для обозначения структуры данных (Hannum и др., 2004).
Аппаратный ассоциативный массив
В отличие от обычной машинной памяти (памяти произвольного доступа, или RAM), в которой пользователь задает адрес памяти и ОЗУ возвращает слово данных, хранящееся по этому адресу, АП разработана таким образом, чтобы пользователь задавал слово данных, и АП осуществляла его поиск, чтобы выяснить, хранится ли оно где-либо в памяти. Если слово данных найдено, АП возвращает список одного или более адресов хранения, где слово было найдено (и в некоторых архитектурах также возвращает само слово данных или другие связанные части данных). Таким образом, АП — аппаратная реализация того, что в терминах программирования назвали бы ассоциативным массивом.
Промышленные стандарты адресуемой содержанием памяти
Определение основного интерфейса для АП и других Сетевых элементов поиска (Network Search Elements, NSE) было специфицировано в Соглашении о возможности взаимодействий (Interoperability Agreement), названном Интерфейс предысторий (Look-Aside Interface) (LA-1 и LA-1B), который был разработан Форумом сетевой обработки, который позже был объединен с Оптическим межсетевым форумом (Optical Internetworking Forum, OIF). Многочисленные устройства были произведены компаниями Integrated Device Technology, Cypress Semiconductor, IBM, Netlogic Micro Systems и другими по этим соглашениям LA. 11 декабря 2007 OIF издал соглашение об интерфейсе Последовательной предыстории (Serial Lookaside, SLA).
Реализация на полупроводниках
Из-за того, что АП разработана, чтобы искать во всей памяти одной операцией, это получается намного быстрее, чем поиск в RAM фактически во всех приложениях поиска. Однако, есть и минус в большей стоимости АП. В отличие от чипа RAM, у которого хранилища простые, у каждого отдельного бита памяти в полностью параллельной АП должна быть собственная присоединенная схема сравнения, чтобы обнаружить совпадение между сохраненным битом и входным битом. К тому же, выходы сравнений от каждой ячейки в слове данных должны быть объединены, чтобы привести к полному результату сравнения слова данных. Дополнительная схема увеличивает физический размер чипа АП, что увеличивает стоимость производства. Дополнительная схема также увеличивает рассеиваемую мощность, так как все схемы сравнений активны на каждом такте. Как следствие, АП используется только в специализированных приложениях, где скорость поиска не может быть достигнута, используя другие, менее дорогостоящие, методы.
Альтернативные реализации
Для того, чтобы достигнуть другого баланса между скоростью, размером памяти и стоимостью, некоторые реализации эмулируют функции АП путём использования стандартного поиска по дереву или алгоритмов хеширования, реализованных аппаратно, также используя для ускорения эффективной работы такие аппаратные трюки, как репликация и конвейерная обработка. Эти проекты часто используются в маршрутизаторах.
Троичная ассоциативная память
Двоичная АП — простейший тип ассоциативной памяти, который использует слова поиска данных, состоявшие полностью из единиц и нулей. В троичной АП (ternary content-addressable memory, TCAM) добавляется третье значение для сравнения «X», или «не важно», для одного или более битов в сохраненном слове данных, добавляя дополнительную гибкость поиску.
Например, в троичной АП могло бы быть сохранено слово «10XX0», которое выдаст совпадение на любое из четырёх слов поиска «10000», «10010», «10100» или «10110». Добавление гибкости к поиску приходит за счёт увеличения сложности памяти, поскольку внутренние ячейки теперь должны кодировать три возможных состояния вместо двух. Это дополнительное состояние обычно осуществляется добавлением бита маски «важности» («важно»/«не важно») к каждой ячейке памяти.
Примеры приложений
Адресуемая содержанием память часто используется в компьютерных сетевых устройствах. Например, когда сетевой коммутатор (switch) получает фрейм данных на один из своих портов, это обновляет внутреннюю таблицу с источником MAC-адреса фрейма и порта, на который он был получен. Потом он ищет MAC-адрес назначения в таблице, чтобы определить, на какой порт фрейм должен быть отправлен, и отсылает его на этот порт. Таблица MAC- адресов обычно реализована на двоичной АП, таким образом порт назначения может быть найден очень быстро, уменьшая время ожидания коммутатора.
Троичные АП часто используются в тех сетевых маршрутизаторах, в которых у каждого адреса есть две части: (1) адрес сети, который может измениться в размере в зависимости от конфигурации подсети, и (2) адрес хоста, который занимает оставшиеся биты. У каждой подсети есть маска сети, которая определяет, какие биты — адрес сети и какие биты — адрес хоста. Маршрутизация делается путём сверки с таблицей маршрутизации, которую поддерживает маршрутизатор (router). В ней содержатся все известные адреса сети назначения, связанная с ними маска сети и информация, необходимая пакетам, маршрутизируемым по этому назначению. Маршрутизатор, реализованный без АП, сравнивает адрес назначения пакета, который будет разбит, с каждым входом в таблице маршрутизации, выполняя при этом логическое И с маской сети и сравнивая результаты с адресом сети. Если они равны, соответствующая информация направления используется, чтобы отправить пакет. Использование троичной АП для таблицы маршрутизации делает процесс поиска очень эффективным. Адреса хранятся с использованием бита «не важно» в части адреса хоста, таким образом поиск адреса назначения в АП немедленно извлекает правильный вход в таблице маршрутизации; обе операции — применения маски и сравнения — выполняются аппаратно средствами АП.
Другие приложения АП включают
- Диспетчеры кэша центрального процессора и ассоциативные буфера трансляции (TLB)
- Базы данных
- Искусственные нейронные сети
- Системы обнаружения вторжений
- Аппаратура сжатия данных
См. также
- Ассоциативный массив
- Буфер ассоциативной трансляции (TLB)
- Таблица поиска
- [англ.]
- Процессор в памяти, Processor-in-memory (PIM), или Вычисляющее ОЗУ или Computational RAM, C-RAM, также, «Вычисления в памяти»
- Вычисления с памятью, концепция и реализация в виде разновидности ПЛИС
Примечания
- CCNP BCMSN Exam Certification Guide: CCNP Self-study — David Hucaby — Google Книги. Дата обращения: 7 апреля 2015. Архивировано 4 марта 2016 года.
Литература
- Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982. — 384 с.
На английском языке
- Anargyros Krikelis, Charles C. Weems (editors) (1997) Associative Processing and Processors, IEEE Computer Science Press. ISBN 0-8186-7661-2
- Pagiamtis, K. & Sheikholeslami, A. (2006, March). Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey. IEEE J. of Solid-State Circuits, 41(3), 712—727.
- Hannum et al. (2004) System and method for resetting and initializing a fully associative array to a known state at power on or through machine specific state. U.S. Patent 6,823,434.
Ссылки
- Ассоциативное запоминающее устройство — статья из Большой советской энциклопедии.
На английском:
- CAM Primer
- Content-addressable memory (CAM) circuits and architectures: A tutorial and survey
- Low-power CAM Design Group
- Aspex — Computer architecture built around associative memory
- Initiation of Serial Lookaside specification effort (near bottom of page 1)
- OIF Serial Lookaside interface agreement
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Ассоциативная память, Что такое Ассоциативная память? Что означает Ассоциативная память?
Eta statya o kompyuternyh tehnologiyah o psihologii sm Associaciya psihologiya Associativnaya pamyat AP ili associativnoe zapominayushee ustrojstvo AZU specialnyj vid mashinnoj pamyati ispolzuemyj v prilozheniyah ochen bystrogo poiska Izvestna takzhe pod terminami pamyat adresuemaya po soderzhimomu associativnoe zapominayushee ustrojstvo kontentno adresuemaya pamyat ili associativnyj massiv hotya poslednij termin chashe ispolzuetsya v programmirovanii dlya oboznacheniya struktury dannyh Hannum i dr 2004 Apparatnyj associativnyj massivV otlichie ot obychnoj mashinnoj pamyati pamyati proizvolnogo dostupa ili RAM v kotoroj polzovatel zadaet adres pamyati i OZU vozvrashaet slovo dannyh hranyasheesya po etomu adresu AP razrabotana takim obrazom chtoby polzovatel zadaval slovo dannyh i AP osushestvlyala ego poisk chtoby vyyasnit hranitsya li ono gde libo v pamyati Esli slovo dannyh najdeno AP vozvrashaet spisok odnogo ili bolee adresov hraneniya gde slovo bylo najdeno i v nekotoryh arhitekturah takzhe vozvrashaet samo slovo dannyh ili drugie svyazannye chasti dannyh Takim obrazom AP apparatnaya realizaciya togo chto v terminah programmirovaniya nazvali by associativnym massivom Promyshlennye standarty adresuemoj soderzhaniem pamyatiOpredelenie osnovnogo interfejsa dlya AP i drugih Setevyh elementov poiska Network Search Elements NSE bylo specificirovano v Soglashenii o vozmozhnosti vzaimodejstvij Interoperability Agreement nazvannom Interfejs predystorij Look Aside Interface LA 1 i LA 1B kotoryj byl razrabotan Forumom setevoj obrabotki kotoryj pozzhe byl obedinen s Opticheskim mezhsetevym forumom Optical Internetworking Forum OIF Mnogochislennye ustrojstva byli proizvedeny kompaniyami Integrated Device Technology Cypress Semiconductor IBM Netlogic Micro Systems i drugimi po etim soglasheniyam LA 11 dekabrya 2007 OIF izdal soglashenie ob interfejse Posledovatelnoj predystorii Serial Lookaside SLA Realizaciya na poluprovodnikahIz za togo chto AP razrabotana chtoby iskat vo vsej pamyati odnoj operaciej eto poluchaetsya namnogo bystree chem poisk v RAM fakticheski vo vseh prilozheniyah poiska Odnako est i minus v bolshej stoimosti AP V otlichie ot chipa RAM u kotorogo hranilisha prostye u kazhdogo otdelnogo bita pamyati v polnostyu parallelnoj AP dolzhna byt sobstvennaya prisoedinennaya shema sravneniya chtoby obnaruzhit sovpadenie mezhdu sohranennym bitom i vhodnym bitom K tomu zhe vyhody sravnenij ot kazhdoj yachejki v slove dannyh dolzhny byt obedineny chtoby privesti k polnomu rezultatu sravneniya slova dannyh Dopolnitelnaya shema uvelichivaet fizicheskij razmer chipa AP chto uvelichivaet stoimost proizvodstva Dopolnitelnaya shema takzhe uvelichivaet rasseivaemuyu moshnost tak kak vse shemy sravnenij aktivny na kazhdom takte Kak sledstvie AP ispolzuetsya tolko v specializirovannyh prilozheniyah gde skorost poiska ne mozhet byt dostignuta ispolzuya drugie menee dorogostoyashie metody Alternativnye realizaciiDlya togo chtoby dostignut drugogo balansa mezhdu skorostyu razmerom pamyati i stoimostyu nekotorye realizacii emuliruyut funkcii AP putyom ispolzovaniya standartnogo poiska po derevu ili algoritmov heshirovaniya realizovannyh apparatno takzhe ispolzuya dlya uskoreniya effektivnoj raboty takie apparatnye tryuki kak replikaciya i konvejernaya obrabotka Eti proekty chasto ispolzuyutsya v marshrutizatorah Troichnaya associativnaya pamyatDvoichnaya AP prostejshij tip associativnoj pamyati kotoryj ispolzuet slova poiska dannyh sostoyavshie polnostyu iz edinic i nulej V troichnoj AP ternary content addressable memory TCAM dobavlyaetsya trete znachenie dlya sravneniya X ili ne vazhno dlya odnogo ili bolee bitov v sohranennom slove dannyh dobavlyaya dopolnitelnuyu gibkost poisku Naprimer v troichnoj AP moglo by byt sohraneno slovo 10XX0 kotoroe vydast sovpadenie na lyuboe iz chetyryoh slov poiska 10000 10010 10100 ili 10110 Dobavlenie gibkosti k poisku prihodit za schyot uvelicheniya slozhnosti pamyati poskolku vnutrennie yachejki teper dolzhny kodirovat tri vozmozhnyh sostoyaniya vmesto dvuh Eto dopolnitelnoe sostoyanie obychno osushestvlyaetsya dobavleniem bita maski vazhnosti vazhno ne vazhno k kazhdoj yachejke pamyati Primery prilozhenijAdresuemaya soderzhaniem pamyat chasto ispolzuetsya v kompyuternyh setevyh ustrojstvah Naprimer kogda setevoj kommutator switch poluchaet frejm dannyh na odin iz svoih portov eto obnovlyaet vnutrennyuyu tablicu s istochnikom MAC adresa frejma i porta na kotoryj on byl poluchen Potom on ishet MAC adres naznacheniya v tablice chtoby opredelit na kakoj port frejm dolzhen byt otpravlen i otsylaet ego na etot port Tablica MAC adresov obychno realizovana na dvoichnoj AP takim obrazom port naznacheniya mozhet byt najden ochen bystro umenshaya vremya ozhidaniya kommutatora Troichnye AP chasto ispolzuyutsya v teh setevyh marshrutizatorah v kotoryh u kazhdogo adresa est dve chasti 1 adres seti kotoryj mozhet izmenitsya v razmere v zavisimosti ot konfiguracii podseti i 2 adres hosta kotoryj zanimaet ostavshiesya bity U kazhdoj podseti est maska seti kotoraya opredelyaet kakie bity adres seti i kakie bity adres hosta Marshrutizaciya delaetsya putyom sverki s tablicej marshrutizacii kotoruyu podderzhivaet marshrutizator router V nej soderzhatsya vse izvestnye adresa seti naznacheniya svyazannaya s nimi maska seti i informaciya neobhodimaya paketam marshrutiziruemym po etomu naznacheniyu Marshrutizator realizovannyj bez AP sravnivaet adres naznacheniya paketa kotoryj budet razbit s kazhdym vhodom v tablice marshrutizacii vypolnyaya pri etom logicheskoe I s maskoj seti i sravnivaya rezultaty s adresom seti Esli oni ravny sootvetstvuyushaya informaciya napravleniya ispolzuetsya chtoby otpravit paket Ispolzovanie troichnoj AP dlya tablicy marshrutizacii delaet process poiska ochen effektivnym Adresa hranyatsya s ispolzovaniem bita ne vazhno v chasti adresa hosta takim obrazom poisk adresa naznacheniya v AP nemedlenno izvlekaet pravilnyj vhod v tablice marshrutizacii obe operacii primeneniya maski i sravneniya vypolnyayutsya apparatno sredstvami AP Drugie prilozheniya AP vklyuchayutDispetchery kesha centralnogo processora i associativnye bufera translyacii TLB Bazy dannyh Iskusstvennye nejronnye seti Sistemy obnaruzheniya vtorzhenij Apparatura szhatiya dannyhSm takzheAssociativnyj massiv Bufer associativnoj translyacii TLB Tablica poiska angl Processor v pamyati Processor in memory PIM ili Vychislyayushee OZU ili Computational RAM C RAM takzhe Vychisleniya v pamyati Vychisleniya s pamyatyu koncepciya i realizaciya v vide raznovidnosti PLISPrimechaniyaCCNP BCMSN Exam Certification Guide CCNP Self study David Hucaby Google Knigi neopr Data obrasheniya 7 aprelya 2015 Arhivirovano 4 marta 2016 goda LiteraturaKohonen T Associativnye zapominayushie ustrojstva M Mir 1982 384 s Na anglijskom yazyke Anargyros Krikelis Charles C Weems editors 1997 Associative Processing and Processors IEEE Computer Science Press ISBN 0 8186 7661 2 Pagiamtis K amp Sheikholeslami A 2006 March Content Addressable Memory CAM Circuits and Architectures A Tutorial and Survey IEEE J of Solid State Circuits 41 3 712 727 Hannum et al 2004 System and method for resetting and initializing a fully associative array to a known state at power on or through machine specific state U S Patent 6 823 434 SsylkiAssociativnoe zapominayushee ustrojstvo statya iz Bolshoj sovetskoj enciklopedii Na anglijskom CAM Primer Content addressable memory CAM circuits and architectures A tutorial and survey Low power CAM Design Group Aspex Computer architecture built around associative memory Initiation of Serial Lookaside specification effort near bottom of page 1 OIF Serial Lookaside interface agreement
