Ассоциативная память человека. Адресная, ассоциативная и стековая организации памяти. Аппаратный ассоциативный массив

Ассоциативная методика диагностики личностной зрелости Авторы: Е. В. Каляева, Т. В. ПрокофьеваИнструкция. Вашему вниманию предлагается ряд слов. Подумайте, какие ассоциации вызывает каждое из этих слов, запишите их.Предлагаются 35 характеристик, раскрывающих понятие

«Повседневная» память и долговременная память Рассмотрим еще два вопроса, имеющих отношение к теме «Память». До сих пор основное внимание уделялось стандартным лабораторным методам, часто исполь-зуемым при изучении памяти в любой возрастной период. Два последних

8. Ассоциативная психология В процессе формирования психологии стал преобладать ассоцианистский подход к восприятию. Ассоциативная психология – одно из основных направлений в психологии XVII–XIX вв. Главным объяснительным принципом психической жизни являлось понятие

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

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

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

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

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

Двоичная АП - простейший тип ассоциативной памяти, который использует слова поиска данных, состоявшие полностью из единиц и нулей. В троичной АП добавляется третье значение для сравнения «X» или «не важно», для одного или более битов в сохраненном слове данных, добавляя таким образом большей гибкости поиску. Например, в троичной АП могло бы быть сохранено слово «10XX0», которое выдаст совдпадение на любое из четырех слов поиска «10000», «10010», «10100», или «10110». Добавление гибкости к поиску приходит за счет увеличения цены двоичной АП, поскольку внутренняя ячейка памяти должна теперь закодировать три возможных состояния вместо двух. Это дополнительное состояние обычно осуществляется добавлением бита маски «важности»(«важно»/«не важно») к каждой ячейке памяти.

Голографическая ассоциативная память обеспечивает математическую модель для интегрированного ассоциативного воспоминания бита «не важно», используя комплекснозначное представление.

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

Адресуемая содержанием память часто используется в компьютерных сетевых устройствах. Например, когда сетевой коммутатор (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

• 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.

Ссылки

Wikimedia Foundation . 2010 .

Смотреть что такое "Ассоциативная память" в других словарях:

В информатике безадресная память, в которой поиск информации производится по ее содержанию (ассоциативному признаку). См. также: Память компьютера Прикладное программное обеспечение Финансовый словарь Финам … Финансовый словарь

ассоциативная память - Память, в которой адресация определяется не местом расположения объекта, а его содержанием. Для нахождения адреса проводится анализ объекта и совпадение его названия (по определенным словам) с другими адресами. Использование ассоциативной памяти… … Справочник технического переводчика

ассоциативная память - ассоциативное запоминающее устройство; ассоциативная память Запоминающее устройство, в котором место обращения определяется содержанием хранящейся информации … Политехнический терминологический толковый словарь

ассоциативная память - asociatyvioji atmintis statusas T sritis automatika atitikmenys: angl. associative memory vok. assoziativer Speicher, m; Durchsuchspeicher, m rus. ассоциативная память, f pranc. mémoire associative, f … Automatikos terminų žodynas

АССОЦИАТИВНАЯ ПАМЯТЬ - См. память, ассоциативная … Толковый словарь по психологии

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Человеческая память ассоциативна, то есть некоторое воспоминание может порождать большую связанную с ним область. Один предмет напоминает нам … Википедия

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

Принцип работы АЗУ поясняет схема, представленная на рис. 3.8.Запоминающий массив, как и в адресных ЗУ, разделен на m -разрядные ячейки, число которых n . Как правило, в состав АЗУ входят:

· запоминающий массив (ЗМ);

· регистр ассоциативных признаков (РгАП);

· регистр маски (РгМ);

· регистр индикаторов адреса со схемами сравнения на входе.

В АЗУ могут быть и другие элементы, наличие и функции которых определяются способом использования АЗУ.

Рис. 3.8. Ассоциативное запоминающее устройство

Выборка информации из АЗУ происходит следующим образом. В регистр ассоциативных признаков из устройства управления передается образец для поиска - код признака искомой информации (иногда его называют компарандом ). Код может иметь произвольное число разрядов – от 1 до m . Если код признаков используется полностью, то он без изменения поступает на схему сравнения, если же необходимо использовать только часть кода, тогда ненужные разряды маскируются с помощью регистра маски. Перед началом поиска информации в АЗУ все разряды регистра индикаторов адреса устанавливаются в состояние 1 .После этого производится опрос первого разряда всех ячеек запоминающего массива, и содержимое сравнивается с первым разрядом регистра ассоциативных признаков. Если содержимое первого разряда i -й ячейки не совпадает с содержимым первого разряда РгАП, то соответствующий этой ячейке разряд регистра индикаторов адреса Т i сбрасывается в состояние 0 , если совпадает – разряд Т i остается 1 . Затем эта операция повторяется со вторым, третьим и последующими разрядами до тех пор, пока не будет произведено сравнение со всеми разрядами РгАП. После поразрядного опроса и сравнения в состоянии 1 останутся те разряды регистра индикаторов адреса, которые соответствуют ячейкам, содержащим информацию, совпадающую с записанной в регистре ассоциативных признаков. Эта информация может быть считана в той последовательности, которая определяется устройством управления.

Заметим, что время поиска информации в ЗМ по ассоциативному признаку зависит только от числа разрядов признака и от скорости опроса разрядов, но совершенно не зависит от числа ячеек ЗМ. Этим и определяется главное преимущество АЗУ перед адресными ЗУ: в адресных ЗУ при операции поиска необходим перебор всех ячеек запоминающего массива. Кроме того, существуют реализации АЗУ, выполняющих поиск одновременно над всеми разрядами всех слов, записанных в память, т.е. время поиска в подобных устройствах не превышает времени цикла памяти.

Запись новой информации в ЗМ производится без указания номера ячейки. Обычно один из разрядов каждой ячейки используется для указания ее занятости, т.е. если ячейка свободна для записи, то в этом разряде записан 0 , а если занята, – 1 . Тогда при записи в АЗУ новой информации устанавливается признак 0 в соответствующем разряде регистра ассоциативных признаков, и определяются все ячейки ЗМ, которые свободны для записи. В одну из них устройство управления помещает новую информацию.

Нередко АЗУ строятся таким образом, что кроме ассоциативной допускается и прямая адресация данных, что представляет определенные удобства при работе.

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

Отмеченные выше свойства АЗУ характеризуют преимущества АЗУ для обработки информации. Формирование нескольких потоков идентичной информации с помощью АЗУ осуществляется быстро и просто, а с большим числом операционных элементов можно создавать высокопроизводительные системы. Надо учитывать еще и то, что на основе ассоциативной памяти легко реализуется изменение места и порядка расположения информации. Благодаря этому АЗУ является эффективным средством формирования наборов данных.

Исследования показывают, что целый ряд задач, таких, как обработка радиолокационной информации, распознавание образов, обработка различных снимков и других задач с матричной структурой данных, эффективно решается ассоциативными системами. К тому же программирование таких задач для ассоциативных систем гораздо проще, чем для традиционных.

К сожалению, устройства памяти с ассоциативным доступом имеют высокие сложность изготовления и стоимость, превышающие аналогичные показатели как динамических, так и статических ОЗУ. Ассоциативная память является основой для построения параллельных ассоциативных систем, а также для ВС, управляемых потоком данных. Наиболее же широко ассоциативный доступ применяется в подсистемах кэш-памяти.

Кэш-память

Впервые двухуровневое построение памяти было предложено М.Уилксом в 1965 году при построении ЭВМ Atlas. Суть подхода заключалась в размещении между ЦП и ОП быстродействующей буферной памяти небольшого размера. В процессе работы ЭВМ те участки ОП, к которым ведется обращение, копируются в буферную память. За счет соблюдения принципа локальности по обращению получается существенный выигрыш в производительности.

Новый вид памяти получил название кэш-память (от англ. cache – «тайник, убежище»), поскольку такая память скрыта, «невидима» для ЦП, который не может непосредственно обратиться к ней. В свою очередь, программист может вообще не знать о существовании кэш-памяти. В серийных ЭВМ кэш-память впервые была применена в системах модели 85 семейства IBMS/360. Сегодня кэш-память наличествует в любом классе ЭВМ, причем зачастую имеет многоуровневую структуру.

Все термины, которые были определены раньше, могут быть использованы и для кэш-памяти, хотя слово «строка » (line ) часто употребляется вместо слова «блок » (block ).

Как правило, кэш-память строится на основе сверхбыстродействующих и дорогостоящих ОЗУ статического типа, при этом ее быстродействие в 5-10 раз превышает быстродействие ОП, а объем – в 500-1000 раз меньше. Заметим, что увеличению объема кэш-памяти по отношению к емкости ОП препятствует не только и не столько высокая стоимость статических ОЗУ. Дело в том, что при увеличении емкости кэш-памяти возрастает сложность схем управления, что, в свою очередь, ведет к падению быстродействия. Многочисленные исследования показали, что указанное соотношение объемов кэш-памяти и ОП является оптимальным и будет сохраняться в процессе развития ЭВМ при увеличении быстродействия обоих видов памяти.

Как уже было сказано, ЦП не имеет непосредственного доступа к кэш-памяти. За организацию взаимодействия ЦП, ОП и кэш-памяти отвечает специальный контроллер. Вся ОП разбивается на блоки фиксированного объема, при этом старшая часть адреса ОП определяет адрес блока , а младшая часть – адрес слова внутри блока . Обмен информации между ОП и кэш-памятью осуществляется блоками. Кэш-память также имеет свою внутреннюю адресацию, и каждый считанный из ОП блок размещается в кэш-памяти по определенному адресу блока в кэш-памяти . Часто блоки кэш-памяти называются строками или кэш-строками .

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

Не менее важным является вопрос о том, в какой момент нужно помещать в кэш-память копию блока из ОП. Данный вопрос решается с помощью стратегии выборки .

При записи в кэш-память существует несколько методов замещения старой информации, которые определяются стратегией обновления основной памяти .

Часто возникает ситуация, когда несмотря на выборку из ОП необходимого блока, в кэш-памяти нет места для его размещения. В этом случае необходимо выбрать одну из кэш-строк и заменить ее новым блоком. Способ определения удаляемой кэш-строки называется стратегией замещения .

Стратегии размещения

Существуетследующие способы размещения данных в кэш-памяти:

· прямое распределение;

· полностью ассоциативное распределение;

· частично (множественно) ассоциативное распределение.

Допустим, разрядность шины адреса n , тогда емкость ОП V ОП = 2 n слов. Без ограничения общности определим размер кэш-строки в 256 слов, таким образом, вся ОП будет поделена на 2 n-8 блоков. В адресе ОП старшие n-8 битов будут определять адрес блока, а младший байт – адрес слова в блоке. Пусть емкость кэш-памяти V кэш в 1024 раза меньше емкости ОП, т.е. V кэш = 2 n-10 слов или 2 n-18 блоков (кэш-строк).

Прямое распределение

Если каждый блок основной памяти имеет только одно фиксированное место, на котором он может появиться в кэш-памяти, то такая кэш-память называется кэшем с прямым распределением (direct mapped cache). Это наиболее простая организация кэш-памяти, при которой для отображения адресов блоков ОП на адреса кэш-памяти просто используются младшие разряды адреса блока. Таким образом, все блоки ОП, имеющие одинаковые младшие разряды в своем адресе, попадают в одну кэш-строку, т.е.

(адрес кэш-строки) = (адрес блока ОП) mod (число блоков в кэш-памяти)

В нашем примере адрес кэш-строки c будут составлять младшие n-18 бит адреса блока ОП (см. рис. 3.9). Преобразование адреса блока ОП в адрес кэш-строки осуществляется путем выборки этих младших n-18 бит. По этому адресу кэш-строки может быть помещен любой из 1024 блоков ОП, имеющих одинаковые n-18 младших бит. Между собой эти блоки будут различаться старшими 10-ю битами t , называемыми тегом . Для того, чтобы определить, какой именно блок ОП хранится в данное время в кэш-памяти, используется еще одна память – так называемая память тегов(теговая память) . Теговая память адресуется пословно, причем каждое слово имеет размер, равный размеру тега. Емкость памяти тегов – это произведение размера тега на общее число кэш-строк, для нашего примера составляет 10·2 n-18 бит. Адресом памяти тегов является адрес кэш-строки с . В отличие от памяти тегов, память, в которой хранятся блоки, помещенные в кэш, называется памятью данных . Память данных адресуется пословно, ее адрес образуется из адреса кэш-строки и адреса слова внутри блока (кэш-строки).

Рис. 3.9. Структура адреса памяти при прямом распределении

Рис. 3.10. Организация кэш-памяти с прямым распределением

При доступе к A -му адресу ОП (рис. 3.10) младшие n-18 бит адреса блока (поле c ), где содержится этот адрес, используются в качестве адреса кэш-строки. По адресу кэш-строки из теговой памяти считывается тег (поле t ). Параллельно этому осуществляется доступ к памяти данных с помощью n-10 младших бит адреса A (поля c и w ). Если считанный тег и старшие 10 бит адреса A совпадают, то это означает, что блок, содержащий адрес A , существует в памяти данных, и в слове, к которому осуществляется доступ, хранится копия A -го адреса ОП.

Если тег отличается от старших 10 бит адреса A , то из основной памяти считывается блок, содержащий адрес A , а из кэш-памяти удаляется кэш-строка, чей адрес определяется полем c (младшими n-18 битами) адреса считываемого блока. На место удаленной кэш-строки помещается считанный из ОП блок, при этом обновляется соответствующий тег в памяти тегов.

Достоинством прямого распределения является простота реализации, однако из-за того, что адрес кэш-строки однозначно определяется адресом блока ОП, высока вероятность сосредоточения областей блоков в некоторой части кэш-памяти. Замена блоков в этой части будет происходить довольно часто, в то же время другие области кэш-памяти могут простаивать. В такой ситуации эффективность кэш-памяти заметно снижается.