Ассоциативная память. Развитие ассоциативной памяти. Память с ассоциативным доступом

Однако зонтик, конечно же, остается на полке, потому что сознание человека, стоящего на пороге своей квартиры, заполнено совсем иными проблемами...

В попытках как-то объяснить этот обескураживающий феномен нейробиологи из Института биологических исследований Солка (Salk Institute for Biological Studies) в пригороде Сан-Диего (США, штат Калифорния) провели серию интересных экспериментов. Институт Солка - это независимая некоммерческая организация, занимающаяся фундаментальными исследованиями, лечением людей и обучением будущих специалистов, а назван этот институт по имени его основателя (1965) - иммунолога Джонаса Эдвардса Солка (Jonas Edward Salk (1914-1995), в свое время одержавшего победу над полиомиелитом). О полученных результатах сообщается в выпуске журнала Neuron ("Нейрон") от 20 октября. Грубо говоря, удалось впервые показать, что мозг помнит про грозовую угрозу, даже если мы ее игнорируем и оставляем зонтик дома.

"Впервые при взгляде на мозговую активность обезьяны резус мы научились отгадывать, что в действительности знает животное", - говорит Томас Д. Олбрайт (Thomas D. Albright), что руководит Vision Center Laboratory. А основной автор исследования, Адам Мессинджер (Adam Messinger), бывший аспирант Олбрайта, который ныне трудится в американском Национальном институте психического здоровья (National Institute of Mental Health - NIMH), сравнивает предмет своего изучения с подсознательным знанием. Это знание остается у нас даже в том случае, если оно недоступно непосредственно сознанию. Он приводит такой пример: "Вы знаете, что встретили жену вашего коллеги по работе, хотя и не способны вспомнить ее лицо".

Человеческая память полагается главным образом на ассоциации ; когда мы пытаемся восстановить какую-либо информацию, один предмет напоминает нам о каком-то другом, который в свою очередь напоминает нам о третьем, и так далее... Как раз на учете этого обстоятельства и основаны, например, феноменальные успехи рекордсменов по запоминанию цифровых рядов, увязывающих с каждой цифрой какие-то более привычные предметы из окружающего мира - это так называемые мнемонические приемы. Разумеется, нейробиологи уже давно и весьма активно пытаются разобрать устройство всей этой ассоциативной памяти "по винтикам". Некоторые специалисты вообще утверждают, что внутри нас запрятано по меньшей мере два типа памяти (а кто-то насчитывает их до десяти разновидностей, но это уже скорее из области курьезов). Первая - основная память - функционально связана с работой фронтальной коры головного мозга, а вторая, гораздо более емкая, - ютится в специфической области мозга, получившей название нижней височной коры (inferior temporal cortex - ITC). Именно там хранится информация едва ли не обо всех событиях нашей жизни. Правда, памятные следы в височной коре окружены неработающими участками мозга, они как бы замурованы. И активизировать, пробудить эту память можно, например, в состоянии гипнотического транса с помощью особых наводящих вопросов.

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

"Мы старались, чтобы обезьяны не ошибались в ходе этих тестов, однако случались и серии ошибок, - поясняет Олбрайт. - И нам стало интересно, что же происходит в их мозгу, когда обезьяны делают явно неверный выбор, несмотря на то, что они наверняка должны были бы помнить правильную связь пары символов". И вот в то время как обезьяны пробовали вспомнить - то есть восстановить правильные ассоциативные связи - и делали-таки свой ошибочный выбор, ученые стали наблюдать сигналы от невроцитов (нервных клеток, нейронов) в этой самой нижней височной коре головного мозга. А теперь уже точно известно, что эта область критически важна для процессов визуального распознавания различных структур и к тому же отвечает за работу именно этого типа памяти.

После того, как Олбрайт и его группа проанализировали картины активности мозговых клеток в нижней височной коре, они сделать вывод о том, что более 50 процентов тамошних активных невроцитов можно смело отнести к особому новому классу нейронов, в которых, как считают исследователи, и закодирована память о правильных соединениях "стимула" и связанного с ним символа.

А самым удивительным во всей этой истории кажется то, что эти специализированные мозговые клетки продолжали посылать свои "правильные" импульсы даже тогда, когда обезьяны выбирали символы неверные. "В этом смысле мозговые клетки "знают" больше, чем обезьяны обнаруживают своим поведением", - говорит Олбрайт. Ведь в реальном мире обезьян (как и людей) все время что-нибудь отвлекает, то есть не дает как следует сосредоточиться и сбивает с правильных мыслей, не позволяет обратиться к истинной памяти...

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

Адресная память. В памяти с адресной организацией разме­щение и поиск информации в ЗМ основаны на использовании адреса хранения слова (числа, команды и т. п.), адресом служит номер ячейки ЗМ, в которой это слово размещается.

При записи (или считывании) слова в ЗМ инициирующая эту операцию команда должна указывать адрес (номер ячейки), по которому производится запись (считывание).

Типичная структура адресной памяти, показанная на рис. 4.2, содержит запоминающий массив из N n-разрядных ячеек и его аппаратурное обрамление, включающее регистр адреса РгА, имеющий k {k > log 2 N) разрядов, информационный регистр РгИ, блок адресной выборки БАВ, блок усилителей считывания БУС, блок разрядных усилителей-формирователей сигналов за­писи БУЗ и блок управления памятью БУП.

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

По коду адреса в РгА БАВ формирует в соответствующей ячейке памяти сигналы, позволяющие произвести в ячейке считывание или запись слова.

Цикл обращения к памяти инициируется поступлением в БУП извне сигнала Обращение. Общая часть цикла обраще­ния включает в себя прием в РгА с шины адреса ША адреса обращения и прием в БУП и расшифровку управляющего сиг­нала Операция, указывающего вид запрашиваемой операции (считывание или запись).

Далее при считывании БАВ дешифрирует адрес, посылает сигналы считывания в заданную адресом ячейку ЗМ, при этом код записанного в ячейке слова считывается усилителями считывания БУС и передается в РгИ. Затем в памяти с разру­шающим считыванием (при считывании все запоминающие элементы ячейки устанавливаются в нулевое состояние). про­изводится регенерация информации в ячейке путем записи в нее из РгИ считанного слова. Операция считывания завер­шается выдачей слова из РгИ на выходную информационную шину ШИВых.

При записи помимо выполнения указанной выше общей ча­сти цикла обращения производится прием записываемого сло­ва с входной информационной шины ШИВх в РгИ. Сама за­пись состоит из двух операций: очистки ячейки (сброса в 0) и собственно записи. Для этого БАВ сначала производит вы­борку и очистку ячейки, заданной адресом в РгА. Очистка вы­полняется сигналами считывания слова в ячейке, но при этом блокируются усилители считывания и из БУС в РгИ информа­ция не поступает. Затем в выбранную БАВ ячейку записывается слово из РгИ.

Блок управления БУП генерирует необходимые последова­тельности управляющих сигналов, инициирующих работу от­дельных узлов памяти. Цепи передачи управляющих сигналов показаны тонкими линиями на рис. 4.2.

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

Типичная структура ассоциативной памяти представлена на рис. 4.3. Запоминающий массив содержит N (п + 1) -разрядных ячеек. Для указания занятости ячейки используется служебный n-й разряд (0 - ячейка свободна, 1 - в ячейке записано слово).

По входной информационной шине ШИВх в регистр ассо­циативного признака РгАП в разряды 0-и-1 поступает п- разрядный ассоциативный запрос, а в регистр маски РгМ - код маски поиска, при этом п-й разряд РгМ устанавли­вается в 0. Ассоциативный поиск производится лишь для сово­купности разрядов РгАП, которым "соответствуют 1 в РгМ (незамаскированные разряды РгАП). Для слов, в которых цифры в разрядах совпали с незамаскированными разрядами РгАП, комбинационная схема КС устанавливает 1 в соответ­ствующие разряды регистра совпадения РгСв и 0 в остальные разряды. Таким образом, значение j-ro разряда в РгСв опреде­ляется выражением

РгСв (j) =

где РгАП [i], РгМ [i] и ЗМ - значения i-го разряда со­ответственно РгАП, РгМ и j-й ячейки ЗМ.

Комбинационная схема формирования результата ассоциа­тивного обращения ФС формирует из слова, образовавшегося в РгСв, сигналы  0 ,  1 ,  2 , соответствующие случаям отсутствия слов в ЗМ, удовлетворяющих ассоциативному признаку, нали­чию одного и более чем одного такого слова. Для этого ФС реализует следующие булевы функции:

 0 =

 1 = РгСв

 2 =  0  1

Формирование содержимого РгСв и сигналов  0 ,  1 ,  2 по содержимому РгАП, РгМ и ЗМ называется операцией контроля ассоциации. Эта операция является составной частью операций считывания и записи, хотя она имеет и самостоятельное значение.

При считывании сначала производится контроль ассоциа­ции по ассоциативному признаку в РгАП. Затем при  0 = 1 считывание отменяется из-за отсутствия искомой информации, при  1 = 1 считывается в РгИ найденное слово, при  2 = 1 в РгИ считывается слово из ячейки, имеющей наименьший номер среди ячеек, отмеченных 1 в РгСв. Из РгИ счи­танное слово выдается на ШИВых.

Рис. 4.3. Структура ассоциа­тивной памяти

При записи сначала оты­скивается свободная ячейка. Для этого выполняется опе­рация контроля ассоциации при РгАП= 111. ..10 и РгМ == 00... 01. При этом свободные ячейки отмечают­ся 1 в РгСв. Для записи вы­бирается свободная ячейка с наименьшим номером. В нее записывается слово, посту­пившее с ШИВх в РгИ.

Рис. 4.4. Стековая память

С помощью операции контроля ассоциации можно, не считывая слов из памяти, определить по содержимому РгСв, сколько в памяти слов, удовлетворяющих ассоциативному при­знаку, например реализовать запросы типа сколько студентов в группе имеют отличную оценку по данной дисциплине. При использовании соответствующих комбинационных схем в ассо­циативной памяти могут выполняться достаточно сложные ло­гические операции, такие, как поиск большего (меньшего) чис­ла, поиск слов, заключенных в определенных границах, поиск максимального (минимального) числа и др.

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

Стековая память, так же как и ассоциативная, является без­адресной. В стековой памяти (рис. 4.4) ячейки образуют одно­мерный массив, в котором соседние ячейки связаны друг с дру­гом разрядными цепями передачи слов. Запись нового слова производится в верхнюю ячейку (ячейку 0), при этом все ранее записанные слова (включая слово, находившееся в ячейке 0), сдвигаются вниз, в соседние ячейки с большими на 1 номера­ми. Считывание возможно только из верхней (нулевой) ячейки памяти, при этом, если производится считывание с удалением, все остальные слова в памяти сдвигаются вверх, в соседние ячейки с большими номерами. В этой памяти порядок считыва­ния слов соответствует правилу: последним поступил - первым обслуживается. В ряде устройств рассматриваемого типа пре­дусматривается также операция простого считывания слова из нулевой ячейки (без его удаления и сдвига слова в памяти). Иногда стековая память снабжается счетчиком стека СчСт, по­казывающим количество занесенных в память слов. Сигнал СчСт = 0 соответствует пустому, стеку, СчСт = N - 1 - заполненному стеку.

Часто стековую память организуют, используя адресную память. Широкое применение стековая память нахо­дит при обработке вложенных структур данных.

В последующих параграфах главы описываются различные типы ЗУ с адресной организацией. Ассоциативная память ис­пользуется в аппаратуре динамическо­го распределения ОП, а также для построения КЭШ-памяти.

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

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

В психологии существует несколько направлений, связанных с памятью. Основные среди них – ассоциативная, бихевиористическая, когнитивная, деятельностная. Все они сходятся в том, что память – это процесс запоминания, сохранения и воспроизведения информации и её забывания и в том, что память – основа в процессе становления личности.

В то же время, исходя из своих принципов, каждая из теорий памяти по-своему объясняет суть и закономерности этого процесса.

Одна из таких теорий – ассоциативная теория памяти. Она исходит из представления, что ассоциация – не что иное как связь, имеющая место между психическими явлениями. Такие связи при запоминании устанавливаются между частями запоминаемого или воспроизводимого материала. Дело в том, что в процессе припоминания человек всегда ищет какие-то связи, установленные между тем материалом, который имеется и тем, который необходимо воспроизвести.

Были выявлены некоторые закономерности, на основе которых образуются ассоциации:

— По смежности. Она имеет место в том случае, если воспринимаемый образ ассоциируется с прошлыми пережитыми представлениями или с теми, которые были одновременно пережиты, связаны с данным образом, то есть на основе объединения с предыдущим материалом. Например, вспомнив свою школу, скорее всего, мы вспомним и классную руководительницу или школьного друга и связанные с ними эмоции, а вспомнив коллегу по работе, возможно, вспомним, что следующая суббота – рабочая, и нужно не забыть установить будильник на утро выходного дня.

— По схожести. Замечали, что, например, некоторые люди кого-то напоминают? Может, Вам случалось, взглянув на незнакомого человека, найти в нем некий «типаж» или обнаружить, что его черты (лицо, манера поведения, осанка и т.д.) Вам запомнятся, поскольку он похож на…? Например, неуклюжий, лохматый, с переваливающейся походкой – как медведь; маленькая, невзрачная, пугливая и беззащитная с виду – как воробушек; яркий, важный, с расправленными плечами и медленными важными движениями – как павлин.

— По контрасту. Нам очень легко ассоциировать «белое — чёрное», «добрый — злой», «толстый — тощий». Их тоже производит наша ассоциативная память и использует для закрепления образа. В этом случае воспринимаемые образы извлекают из сознания противоположные представления. Так, столкнувшись с раздражённой соседкой, Вы вспоминаете, какой спокойной кажется её сестра.

Недостаток ассоциативной теории памяти заключается в том, что она не объясняет такую важную характеристику как выборочность памяти (ведь ассоциативный материал не всегда хорошо запоминается). Кроме того, она не учитывает, что процессы памяти находятся в зависимости от организации запоминаемого материала.

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

Тренируется ассоциативная память путем связывания известной, уже усвоенной информации с новым материалом. Для развития ассоциативной памяти можно использовать, например, такое упражнение:

1. Подготовьте 2 листа бумаги и ручку. На 1 листе в столбик по вертикали впишите все натуральные числа от 1 до 100.

2. Выберите любые 10-15 из них, с которыми у Вас связаны стойкие ассоциации, и выпишите их в произвольном порядке на 2 лист. Например, 8 – снеговик, 17 – номер Вашей любимой маршрутки, 18 – возраст совершеннолетия в стране, в которой Вы живете (если это так), и т.д. После того, как закончите работу, подождите 5-7 минут, возьмите 1 листок с числами и запишите все события, которые запомнили, напротив соответствующего числа.

3. В следующий раз проделайте то же с другими, не задействованными прежде числами. Не форсируйте события, не слишком подгоняйте себя поначалу, постарайтесь максимально удачно подобрать такую ассоциацию, которая надежно займёт свое место в списке.

4. Когда весь список чисел будет заполнен, проверьте себя, указав все ассоциации, связанные с числами от 1 до 100.

Помимо того, что потренировали память, Вы создали дополнительные ассоциации, которые помогут при необходимости запоминать коды, номера телефонов и т.д. Просто постарайтесь использовать свои личные ассоциации, не боясь привлекать образы. Например, 40 можно запомнить, представив 4 как квадрат, «телевизор» и 0 как вписанный в него круг, «колобок». Получится смешная ассоциация «колобок в телевизоре». Придумайте свои ассоциации, приемлемые именно для Вас.

Говоря о развитии памяти, необходимо отметить, что она неразрывно связана с вниманием, ведь без сосредоточения внимания на объекте мы не переместим его даже в кратковременную память. Хорошая работа памяти предполагает высокую активность нейронов, слаженную работу когнитивных (познавательных) функций мозга. О развитии памяти и внимания больше можно прочитать .

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

Желаем Вам успехов в саморазвитии!

Фото: Laurelville — Camp & Retreat Center

В ассоциативной памяти элементы выбираются не по адресу, а по содержимому. Поясним последнее понятие более подробно. Для памяти с адресной организацией было введено понятие минимальной адресуемой единицы (МАЕ) как порции данных, имеющей индивидуальный адрес. Введем аналогичное понятие для ассоциативной памяти , и будем эту минимальную единицу хранения в ассоциативной памяти называть строкой ассоциативной памяти (СтрАП). Каждая СтрАП содержит два поля: поле тега (англ. tag - ярлык, этикетка, признак) и поле данных. Запрос на чтение к ассоциативной памяти словами можно выразить следующим образом: выбрать строку (строки), у которой (у которых) тег равен заданному значению.

Особо отметим, что при таком запросе возможен один из трех результатов:

1. имеется в точности одна строка с заданным тегом;
2. имеется несколько строк с заданным тегом;
3. нет ни одной строки с заданным тегом.

Поиск записи по признаку - это действие, типичное для обращений к базам данных, и поиск в базе зачастую чвляется ассоциативным поиском. Для выполнения такого поиска следует просмотреть все записи и сравнить заданный тег с тегом каждой записи. Это можно сделать и при использовании для хранения записей обычной адресуемой памяти (и понятно, что это потребует достаточно много времени - пропорционально количеству хранимых записей!). Об ассоциативной памяти говорят тогда, когда ассоциативная выборка данных из памяти поддержана аппаратно. При записи в ассоциативную память элемент данных помещается в СтрАП вместе с присущим этому элементу тегом. Для этого можно использовать любую свободную СтрАП. Рассмотрим разновидности структурной организации КЭШ-памяти или способы отображения оперативной памяти на КЭШ .

Полностью ассоциативный КЭШ

Схема полностью ассоциативного КЭШа представлена на рисунке (см. рисунок ниже).

Опишем алгоритм работы системы с КЭШ-памятью. В начале работы КЭШ-память пуста. При выполнении первой же команды во время выборки ее код, а также еще несколько соседних байтов программного кода, - будут перенесены (медленно) в одну из строк КЭШа, и одновременно старшая часть адреса будет записана в соответствующий тег. Так происходит заполнение КЭШ-строки.

Если следующие выборки возможны из этого участка, они будут сделаны уже из КЭШа (быстро) - "КЭШ-попадание". Если же окажется, что нужного элемента в КЭШе нет, - "КЭШ-промахом". В этом случае обращение происходит к ОЗУ (медленно), и при этом одновременно заполняется очередная КЭШ-строка.

Схема полностью ассоциативной КЭШ-памяти

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

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

Если произошел КЭШ-промах, а в КЭШе нет свободных строк, необходимо заменить одну строку КЭШа на другую строку.

Основная цель стратегии замещения - удерживать в КЭШ-памяти строки, к которым наиболее вероятны обращения в ближайшем будущем, и заменять строки, доступ к которым произойдет в более отдаленном времени или вообще не случится. Очевидно, что оптимальным будет алгоритм, который замещает ту строку, обращение к которой в будущем произойдет позже, чем к любой другой строке-КЭШ.

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

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

Наиболее эффективным является алгоритм замещения на основе наиболее давнего использования (LRU - Least Recently Used ), при котором замещается та строка КЭШ-памяти, к которой дольше всего не было обращения. Проводившиеся исследования показали, что алгоритм LRU, который "смотрит" назад, работает достаточно хорошо в сравнении с оптимальным алгоритмом, "смотрящим" вперед.

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

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

Другой возможный алгоритм замещения - алгоритм, работающий по принципу "первый вошел, первый вышел" (FIFO - First In First Out ). Здесь заменяется строка, дольше всего находившаяся в КЭШ-памяти. Алгоритм легко реализуется с помощью рассмотренной ранее очереди, с той лишь разницей, что после обращения к строке положение соответствующей ссылки в очереди не меняется.

Еще один алгоритм - замена наименее часто использовавшейся строки (LFU - Least Frequently Used). Заменяется та строка в КЭШ-памяти, к которой было меньше всего обращений. Принцип можно воплотить на практике, связав каждую строку со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик которой содержит наименьшее число.

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

Кроме тега и байтов данных в КЭШ-строке могут содержаться дополнительные служебные поля, среди которых в первую очередь следует отметить бит достоверности V (от valid - действительный имеющий силу) и бит модификации M (от modify - изменять, модифицировать). При заполнении очередной КЭШ-строки V устанавливается в состояние "достоверно", а M - в состояние "не модифицировано". В случае, если в ходе выполнения программы содержимое данной строки было изменено, переключается бит M, сигнализируя о том, что при замене данной строки ее содержимое следует переписать в ОЗУ. Если по каким-либо причинам произошло изменение копии элемента данной строки, хранимого в другом месте (например в ОЗУ), переключается бит V. При обращении к такой строке будет зафиксирован КЭШ-промах (несмотря на то, что тег совпадает), и обращение произойдет к основному ОЗУ. Кроме того, служебное поле может содержать биты, поддерживающие алгоритм LRU.

Оценка объема оборудования

Типовой объем КЭШ-памяти в современной системе - 8…1024 кбайт, а длина КЭШ-строки 4…32 байт. Дальнейшая оценка делается для значений объема КЭШа 256 кбайт и длины строки 32 байт, что характерно для систем с процессорами Pentium и PentiumPro. Длина тега при этом равна 27 бит, а количество строк в КЭШе составит 256К/ 32=8192. Именно столько цифровых компараторов 27 битных кодов потребуется для реализации вышеописанной структуры.

Приблизительная оценка затрат оборудования для построения цифрового компаратора дает значение 10 транз/бит, а общее количество транзисторов только в блоке компараторов будет равно:

10*27*8192 = 2 211 840,

что приблизительно в полтора раза меньше общего количества транзисторов на кристалле Pentium. Таким образом, ясно, что описанная структура полностью ассоциативной КЭШ-памяти () реализуема только при малом количестве строк в КЭШе, т.е. при малом объеме КЭШа (практически не более 32…64 строк). КЭШ большего объема строят по другой структуре.

Материал из Википедии - свободной энциклопедии

Ассоциативная память (АП) или (АЗУ) является особым видом машинной памяти, используемой в приложениях очень быстрого поиска. Известна также как память, адресуемая по содержимому , ассоциативное запоминающее устройство , контентно-адресуемая память или ассоциативный массив , хотя последний термин чаще используется в программировании для обозначения структуры данных. (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). IEEE J. of Solid-State Circuits , 41(3), 712–727.
• . U.S. Patent 6,823,434.

Напишите отзыв о статье "Ассоциативная память"

Примечания

Ссылки

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

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

См. также

• Процессор в памяти , Processor-in-memory (PIM), или Вычисляющее ОЗУ или Computational RAM, C-RAM, также, «Вычисления в памяти»
• Вычисления с памятью , концепция и реализация в виде разновидности ПЛИС

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

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

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