Ассоциативная память

Эта статья о компьютерных технологиях; о психологии см.: Ассоциация (психология).

Ассоциативная память (АП) или Ассоциативное запоминающее устройство (АЗУ) является особым видом машинной памяти, используемой в приложениях очень быстрого поиска. Известна также как память, адресуемая по содержимому, ассоциативное запоминающее устройство, контентно-адресуемая память или ассоциативный массив, хотя последний термин чаще используется в программировании для обозначения структуры данных. (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». Добавление гибкости к поиску приходит за счет увеличения сложности памяти, поскольку внутренние ячейки теперь должны кодировать три возможных состояния вместо двух. Это дополнительное состояние обычно осуществляется добавлением бита маски «важности» («важно»/«не важно») к каждой ячейке памяти.

Голографическая ассоциативная память обеспечивает математическую модель для интегрированного ассоциативного воспоминания бита «не важно», используя комплекснозначное представление.К:Википедия:Статьи без источников (тип: не указан) предположительно www.mit.edu/~9.54/fall14/Classes/class07/Plate.pdf and www.mit.edu/~9.54/fall14/Classes/class07/Plate.pdf

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

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

Троичные АП часто используются в тех сетевых маршрутизаторах, в которых у каждого адреса есть две части: (1) адрес сети, который может измениться в размере в зависимости от конфигурации подсети, и (2) адрес хоста, который занимает оставшиеся биты. У каждой подсети есть маска сети, которая определяет, какие биты — адрес сети и какие биты — адрес хоста. Маршрутизация делается путём сверки с таблицей маршрутизации, которую поддерживает маршрутизатор (router). В ней содержатся все известные адреса сети назначения, связанная с ними маска сети и информация, необходимая пакетам, маршрутизируемым по этому назначению. Маршрутизатор, реализованный без АП, сравнивает адрес назначения пакета, который будет разбит, с каждым входом в таблице маршрутизации, выполняя при этом логическое И с маской сети и сравнивая результаты с адресом сети. Если они равны, соответствующая информация направления используется, чтобы отправить пакет. Использование троичной АП для таблицы маршрутизации делает процесс поиска очень эффективным. Адреса хранятся с использованием бита «не важно» в части адреса хоста, таким образом поиск адреса назначения в АП немедленно извлекает правильный вход в таблице маршрутизации; обе операции — применения маски и сравнения — выполняются аппаратно средствами АП.

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

• Диспетчеры кэша центрального процессора и ассоциативные буфера трансляции (TLB)
• Базы данных
• Искусственные нейронные сети
• Системы обнаружения вторжений
• Аппаратура сжатия данных

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

• Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 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). [www.pagiamtzis.com/pubs/pagiamtzis-jssc2006.pdf Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey.] IEEE J. of Solid-State Circuits, 41(3), 712–727.
• [patft.uspto.gov/netahtml/PTO/search-bool.html 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.

Ссылки

• Ассоциативное запоминающее устройство — статья из Большой советской энциклопедии.

На английском:

• [www.pagiamtzis.com/cam/camintro.html CAM Primer]
• [www.pagiamtzis.com/pubs/jssc2006-abstract.html Content-addressable memory (CAM) circuits and architectures: A tutorial and survey]
• [www.ece.uwaterloo.ca/~n2mohan/cam.html Low-power CAM Design Group]
• [www.aspex-semi.com/pages/technology/technology_asprocore.shtml Aspex — Computer architecture built around associative memory]
• [www.oiforum.com/public/documents/Athens_PR_052506_Final.pdf Initiation of Serial Lookaside specification effort (near bottom of page 1)]
• [www.oiforum.com/public/documents/OIF%20SLA%20IA.pdf OIF Serial Lookaside interface agreement]

См. также

• Ассоциативная память на нейронных сетях
• Ассоциативный массив
• Буфер ассоциативной трансляции (TLB)
• Контентно-адресуемое хранилище данных
• Таблица поиска
• en:Content addressable network
• Процессор в памяти, Processor-in-memory (PIM), или Вычисляющее ОЗУ или Computational RAM, C-RAM, также, «Вычисления в памяти»
• Вычисления с памятью, концепция и реализация в виде разновидности ПЛИС

Отрывок, характеризующий Ассоциативная память

– У графини просите, а я не распоряжаюсь.
– Ежели затруднительно, пожалуйста, не надо, – сказал Берг. – Мне для Верушки только очень бы хотелось.
– Ах, убирайтесь вы все к черту, к черту, к черту и к черту!.. – закричал старый граф. – Голова кругом идет. – И он вышел из комнаты.
Графиня заплакала.
– Да, да, маменька, очень тяжелые времена! – сказал Берг.
Наташа вышла вместе с отцом и, как будто с трудом соображая что то, сначала пошла за ним, а потом побежала вниз.
На крыльце стоял Петя, занимавшийся вооружением людей, которые ехали из Москвы. На дворе все так же стояли заложенные подводы. Две из них были развязаны, и на одну из них влезал офицер, поддерживаемый денщиком.
– Ты знаешь за что? – спросил Петя Наташу (Наташа поняла, что Петя разумел: за что поссорились отец с матерью). Она не отвечала.
– За то, что папенька хотел отдать все подводы под ранепых, – сказал Петя. – Мне Васильич сказал. По моему…
– По моему, – вдруг закричала почти Наташа, обращая свое озлобленное лицо к Пете, – по моему, это такая гадость, такая мерзость, такая… я не знаю! Разве мы немцы какие нибудь?.. – Горло ее задрожало от судорожных рыданий, и она, боясь ослабеть и выпустить даром заряд своей злобы, повернулась и стремительно бросилась по лестнице. Берг сидел подле графини и родственно почтительно утешал ее. Граф с трубкой в руках ходил по комнате, когда Наташа, с изуродованным злобой лицом, как буря ворвалась в комнату и быстрыми шагами подошла к матери.
– Это гадость! Это мерзость! – закричала она. – Это не может быть, чтобы вы приказали.
Берг и графиня недоумевающе и испуганно смотрели на нее. Граф остановился у окна, прислушиваясь.
– Маменька, это нельзя; посмотрите, что на дворе! – закричала она. – Они остаются!..
– Что с тобой? Кто они? Что тебе надо?
– Раненые, вот кто! Это нельзя, маменька; это ни на что не похоже… Нет, маменька, голубушка, это не то, простите, пожалуйста, голубушка… Маменька, ну что нам то, что мы увезем, вы посмотрите только, что на дворе… Маменька!.. Это не может быть!..
Граф стоял у окна и, не поворачивая лица, слушал слова Наташи. Вдруг он засопел носом и приблизил свое лицо к окну.
Графиня взглянула на дочь, увидала ее пристыженное за мать лицо, увидала ее волнение, поняла, отчего муж теперь не оглядывался на нее, и с растерянным видом оглянулась вокруг себя.
– Ах, да делайте, как хотите! Разве я мешаю кому нибудь! – сказала она, еще не вдруг сдаваясь.
– Маменька, голубушка, простите меня!
Но графиня оттолкнула дочь и подошла к графу.
– Mon cher, ты распорядись, как надо… Я ведь не знаю этого, – сказала она, виновато опуская глаза.
– Яйца… яйца курицу учат… – сквозь счастливые слезы проговорил граф и обнял жену, которая рада была скрыть на его груди свое пристыженное лицо.
– Папенька, маменька! Можно распорядиться? Можно?.. – спрашивала Наташа. – Мы все таки возьмем все самое нужное… – говорила Наташа.
Граф утвердительно кивнул ей головой, и Наташа тем быстрым бегом, которым она бегивала в горелки, побежала по зале в переднюю и по лестнице на двор.
Люди собрались около Наташи и до тех пор не могли поверить тому странному приказанию, которое она передавала, пока сам граф именем своей жены не подтвердил приказания о том, чтобы отдавать все подводы под раненых, а сундуки сносить в кладовые. Поняв приказание, люди с радостью и хлопотливостью принялись за новое дело. Прислуге теперь это не только не казалось странным, но, напротив, казалось, что это не могло быть иначе, точно так же, как за четверть часа перед этим никому не только не казалось странным, что оставляют раненых, а берут вещи, но казалось, что не могло быть иначе.
Все домашние, как бы выплачивая за то, что они раньше не взялись за это, принялись с хлопотливостью за новое дело размещения раненых. Раненые повыползли из своих комнат и с радостными бледными лицами окружили подводы. В соседних домах тоже разнесся слух, что есть подводы, и на двор к Ростовым стали приходить раненые из других домов. Многие из раненых просили не снимать вещей и только посадить их сверху. Но раз начавшееся дело свалки вещей уже не могло остановиться. Было все равно, оставлять все или половину. На дворе лежали неубранные сундуки с посудой, с бронзой, с картинами, зеркалами, которые так старательно укладывали в прошлую ночь, и всё искали и находили возможность сложить то и то и отдать еще и еще подводы.
– Четверых еще можно взять, – говорил управляющий, – я свою повозку отдаю, а то куда же их?
– Да отдайте мою гардеробную, – говорила графиня. – Дуняша со мной сядет в карету.
Отдали еще и гардеробную повозку и отправили ее за ранеными через два дома. Все домашние и прислуга были весело оживлены. Наташа находилась в восторженно счастливом оживлении, которого она давно не испытывала.
– Куда же его привязать? – говорили люди, прилаживая сундук к узкой запятке кареты, – надо хоть одну подводу оставить.
– Да с чем он? – спрашивала Наташа.
– С книгами графскими.
– Оставьте. Васильич уберет. Это не нужно.
В бричке все было полно людей; сомневались о том, куда сядет Петр Ильич.
– Он на козлы. Ведь ты на козлы, Петя? – кричала Наташа.
Соня не переставая хлопотала тоже; но цель хлопот ее была противоположна цели Наташи. Она убирала те вещи, которые должны были остаться; записывала их, по желанию графини, и старалась захватить с собой как можно больше.


Во втором часу заложенные и уложенные четыре экипажа Ростовых стояли у подъезда. Подводы с ранеными одна за другой съезжали со двора.
Коляска, в которой везли князя Андрея, проезжая мимо крыльца, обратила на себя внимание Сони, устраивавшей вместе с девушкой сиденья для графини в ее огромной высокой карете, стоявшей у подъезда.
– Это чья же коляска? – спросила Соня, высунувшись в окно кареты.
– А вы разве не знали, барышня? – отвечала горничная. – Князь раненый: он у нас ночевал и тоже с нами едут.
– Да кто это? Как фамилия?
– Самый наш жених бывший, князь Болконский! – вздыхая, отвечала горничная. – Говорят, при смерти.
Соня выскочила из кареты и побежала к графине. Графиня, уже одетая по дорожному, в шали и шляпе, усталая, ходила по гостиной, ожидая домашних, с тем чтобы посидеть с закрытыми дверями и помолиться перед отъездом. Наташи не было в комнате.
– Maman, – сказала Соня, – князь Андрей здесь, раненый, при смерти. Он едет с нами.
Графиня испуганно открыла глаза и, схватив за руку Соню, оглянулась.
– Наташа? – проговорила она.
И для Сони и для графини известие это имело в первую минуту только одно значение. Они знали свою Наташу, и ужас о том, что будет с нею при этом известии, заглушал для них всякое сочувствие к человеку, которого они обе любили.
– Наташа не знает еще; но он едет с нами, – сказала Соня.
– Ты говоришь, при смерти?
Соня кивнула головой.
Графиня обняла Соню и заплакала.
«Пути господни неисповедимы!» – думала она, чувствуя, что во всем, что делалось теперь, начинала выступать скрывавшаяся прежде от взгляда людей всемогущая рука.
– Ну, мама, все готово. О чем вы?.. – спросила с оживленным лицом Наташа, вбегая в комнату.
– Ни о чем, – сказала графиня. – Готово, так поедем. – И графиня нагнулась к своему ридикюлю, чтобы скрыть расстроенное лицо. Соня обняла Наташу и поцеловала ее.
Наташа вопросительно взглянула на нее.
– Что ты? Что такое случилось?
– Ничего… Нет…
– Очень дурное для меня?.. Что такое? – спрашивала чуткая Наташа.