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

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

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

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

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

Так как ассоциативная память содержит только некоторые из записей таблицы страниц, каждая запись в TLB должна включать поле с номером виртуальной страницы. Память называется ассоциативной, потому что в ней происходит одновременное сравнение номера отображаемой виртуальной страницы с соответствующим полем во всех строках этой небольшой таблицы. Поэтому данный вид памяти достаточно дорого стоит. В строке, поле виртуальной страницы которой совпало с искомым значением, находится номер страничного кадра. Обычное число записей в TLB от 8 до 4096. Рост количества записей в ассоциативной памяти должен осуществляться с учетом таких факторов, как размер кэша основной памяти и количества обращений к памяти при выполнении одной команды.

Рассмотрим функционирование менеджера памяти при наличии ассоциативной памяти.

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

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

Число удачных поисков номера страницы в ассоциативной памяти по отношению к общему числу поисков называется hit (совпадение) ratio (пропорция, отношение). Иногда также используется термин «процент попаданий в кэш». Таким образом, hit ratio - часть ссылок, которая может быть сделана с использованием ассоциативной памяти. Обращение к одним и тем же страницам повышает hit ratio. Чем больше hit ratio, тем меньше среднее время доступа к данным, находящимся в оперативной памяти.

Предположим, например, что для определения адреса в случае кэш-промаха через таблицу страниц необходимо 100 не, а для определения адреса в случае кэш-попадания через ассоциативную память - 20 не. С 90% hit ratio среднее время определения адреса - 0,9x20 + 0,1x100 = 28 не.

Вполне приемлемая производительность современных ОС доказывает эффективность использования ассоциативной памяти. Высокое значение вероятности нахождения данных в ассоциативной памяти связано с наличием у данных объективных свойств: пространственной и временной локальности.

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

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

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

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

Принцип работы АЗУ поясняет схема, представленная на рис. 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 битами) адреса считываемого блока. На место удаленной кэш-строки помещается считанный из ОП блок, при этом обновляется соответствующий тег в памяти тегов.

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

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

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

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

Типичная структура адресной памяти, показанная на рис. 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 - заполненному стеку.

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

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

Обычно в запоминающих устройствах доступ к информации требует указания адреса ячейки. Однако значительно удобнее искать информацию не по адресу, а опираясь на какой-нибудь характерный признак, содержащийся в самой информации. Такой принцип лежит в основе ЗУ, известного как ассоциативное запоминающее устройство (АЗУ). В литературе встречаются и иные названия подобного ЗУ: память, адресуемая по содержанию (content addressable memory); память, адресуемая по данным (data addressable memory); память с параллельным поиском (parallel search memory); каталоговая память (catalog memory); информационное ЗУ (information storage); тегированная память (tag memory).

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

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

Ассоциативный признак– признак, по которому производится поиск информации.

Признак поиска– кодовая комбинация, выступающая в роли образца для поиска.

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

Структура ассоциативного ЗУ

АЗУ включает в себя:

• запоминающий массив для хранения N m-разрядных слов, в каждом из которых несколько младших разрядов занимает служебная информация;
• регистр ассоциативного признака, куда помещается код искомой информации (признак поиска). Разрядность регистра k обычно меньше длины слова т ;
• схемы совпадения, используемые для параллельного сравнения каждого бита всех хранимых слов с соответствующим битом признака поиска и выработки сигналов совпадения;
• регистр совпадений, где каждой ячейке запоминающего массива соответствует один разряд, в который заносится единица, если все разряды соответствующей ячейки совпали с одноименными разрядами признака поиска;
• регистр маски, позволяющий запретить сравнение определенных битов;
• комбинационную схему, которая на основании анализа содержимого регистра совпадений формирует сигналы, характеризующие результаты поиска информации.

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

• а0 – не найдена;
• а1 – содержится в одной ячейке;
• а2 – содержится более чем в одной ячейке.

Формирование содержимого регистра совпадений и сигналов a0, a1, а2 носит название операции контроля ассоциации. Она является составной частью операций считывания и записи, хотя может иметь и самостоятельное значение.

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

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

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

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

1. вида поиска информации;
2. техники сравнения признаков;
3. способа считывания информации при множественных совпадениях;
4. способа записи информации.

В каждом конкретном применении АЗУ задача поиска информации может формулироваться по-разному.

Виды поиска информации :

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

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

Техника сравнения признаков:

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

Способ считывания информации при множественных совпадениях:

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

Способ записи информации:

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

Из-за относительно высокой стоимости АЗУ редко используется как самостоятельный вид памяти.