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

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

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

Естественное решение проблемы ускорения - снабдить компьютер аппаратным устройством для отображения виртуальных страниц в физические без обращения к таблице страниц, то есть иметь небольшую, быструю кэш-память, хранящую необходимую на данный момент часть таблицы страниц. Это устройство называется ассоциативной памятью, иногда также употребляют термин буфер поиска трансляции (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 не.

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

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

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

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

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

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

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

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

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

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

Простой (требуется полное совпадение всех разрядов признака поиска с одноименными разрядами слов, хранящихся в запоминающем массиве).
Сложный:

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

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

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

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

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

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

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

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

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

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

Ассоциативная память (АП) или (АЗУ) является особым видом машинной памяти, используемой в приложениях очень быстрого поиска. Известна также как память, адресуемая по содержимому , ассоциативное запоминающее устройство , контентно-адресуемая память или ассоциативный массив , хотя последний термин чаще используется в программировании для обозначения структуры данных. (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, – сказала Соня, – князь Андрей здесь, раненый, при смерти. Он едет с нами.
Графиня испуганно открыла глаза и, схватив за руку Соню, оглянулась.
– Наташа? – проговорила она.
И для Сони и для графини известие это имело в первую минуту только одно значение. Они знали свою Наташу, и ужас о том, что будет с нею при этом известии, заглушал для них всякое сочувствие к человеку, которого они обе любили.
– Наташа не знает еще; но он едет с нами, – сказала Соня.
– Ты говоришь, при смерти?
Соня кивнула головой.
Графиня обняла Соню и заплакала.
«Пути господни неисповедимы!» – думала она, чувствуя, что во всем, что делалось теперь, начинала выступать скрывавшаяся прежде от взгляда людей всемогущая рука.
– Ну, мама, все готово. О чем вы?.. – спросила с оживленным лицом Наташа, вбегая в комнату.
– Ни о чем, – сказала графиня. – Готово, так поедем. – И графиня нагнулась к своему ридикюлю, чтобы скрыть расстроенное лицо. Соня обняла Наташу и поцеловала ее.
Наташа вопросительно взглянула на нее.
– Что ты? Что такое случилось?
– Ничего… Нет…
– Очень дурное для меня?.. Что такое? – спрашивала чуткая Наташа.

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

Наименование параметра	Значение
Тема статьи:	Ассоциативная память
Рубрика (тематическая категория)	Компьютеры

Таблица страниц

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

Итак, виртуальный адрес состоит из виртуального номера страницы (high-order bits) и смещения (low-order bits). Номер виртуальной страницы используется как индекс в таблице страниц для нахождения записи (entry) о виртуальной странице. Из этой записи в таблице страниц находится номер кадра (page frame number), затем прибавляется смещение и формируется физический адрес. Помимо этого запись в таблице страниц содержит информацию об атрибутах страницы, в частности биты защиты.

Основную проблему для эффективной реализации таблицы страниц создают большие размеры виртуальных адресных пространств современных компьютеров, которые обычно определяются разрядностью архитектуры процессора. Самыми распространенными на сегодняшний день являются 32-разрядные процессоры, позволяющие создавать виртуальные адресные пространства такого размером 4 Гб (для 64-разрядных компьютеров эта величина равна 2**64б).

Подсчитаем примерный размер таблицы страниц. В 32-битном адресном пространстве при размере страницы 4К (Intel) получаем 1М страниц, а в 64-битном и того более. Т.о. таблица должна иметь 1М строк (entry), причем запись в строке состоит из нескольких байт. Заметим, что каждый процесс, нуждается в своей таблице страниц (а в случае сегментно-страничной схемы по одной на каждый сегмент). Итак, в данном случае таблица страниц должна быть чересчур большой.

Вместе с тем, отображение должно быть быстрым. Отображение должно быть быстрым, так как оно делается при каждом обращении к памяти, ĸᴏᴛᴏᴩᴏᴇ происходит практически в каждой машинной инструкции. Эта проблема решается главным образом за счёт реализации ассоциативной памяти.

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

Рассмотрим модельный пример (рис.10.4). Предположим, что 32-разрядный адрес делится на 10-разрядное поле Рtr1, 10-разрядное поле Рtr2 и 12-разрядное смещение Offset. 12 разрядов смещения позволяют локализовать байт внутри страницы размером 4К (2**12), а всего имеем 2**20 страниц. Как видно из рис. 9.4 1024 строки в таблице верхнего уровня при помощи поля Ptr1 ссылаются на 1024 таблицы второго уровня, каждая из которых содержит также 1024 строки. При помощи поля Ptr2 каждая строка таблицы второго уровня указывает на конкретную страницу. Смысл такой организации в том, чтобы избежать поддержки всех таблиц второго уровня (а их 1024) в памяти постоянно. Рассмотрим пример с круглыми цифрами. Допустим, что процессу нужны 12М памяти: 4М в нижней части памяти для кода, 4М в нижней части для данных и 4М в верхней части памяти для стека. Между дном стека и верхом данных гигантское пространство размером 4Gb-12Mb, ĸᴏᴛᴏᴩᴏᴇ не используется. Для этого случая необходимы лишь 1 таблица верхнего уровня и 3 таблицы второго уровня. Такой подход естественным образом обобщается на три и более уровней таблицы.

Рассмотрим одну из записей таблицы страниц. Ее размер колеблется от системы к системе, но 32 бита - наиболее общий случай. Самое важное поле - номер кадра. Цель страничного отображения - локализовать эту величину. Далее бит присутствия, биты защиты (к примеру, 0 - read/write, 1 - read only ...), биты модификации (если на нее писали) и биты ссылки, которые помогают выделить мало используемые страницы, биты разрешающие кэширование. Заметим, что адреса страниц на диске не являются частью таблицы страниц.

Рисунок 10.4 - Пример двухуровневой таблицы страниц.

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

Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры. Можно привести примеры реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) paging"а, а также paging"а с задаваемым количеством уровней (Motorola). Функционирование RISC процессора MIPS R2000 осуществляется вообще без таблицы страниц. Здесь поиск нужной страницы, в случае если эта страница отсутствует в ассоциативной памяти, должна взять на себя ОС (так называемый zero level paging).

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

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

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

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

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

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

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

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

Процент раз, когда номер страницы находится в ассоциативной памяти, принято называть hit (совпадение) ratio (пропорция, отношение). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, hit ratio - часть ссылок, которая должна быть сделана с использованием ассоциативной памяти. Обращение к одним и тем же страницам повышает hit ratio.

К примеру, предположим, что для доступа к таблице страниц крайне важно 100 нс, а для доступа к ассоциативной памяти 20 нс. С 90% hit ratio среднее время доступа - 0.9*20+0.1*100 = 28 нс.

Необходимо обратить внимание на следующий факт. При переключении процессов нужно добиться того, чтобы новый процесс не видел в ассоциативной памяти информацию, относящуюся к предыдущему процессу, к примеру, очищать ее. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, использование ассоциативной памяти увеличивает время переключения контекстов.

Ассоциативная память - понятие и виды. Классификация и особенности категории "Ассоциативная память" 2017, 2018.

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

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

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

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

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

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

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

При записи помимо выполнения указанной выше общей части цикла обращения производится прием записываемого слова с входной информационной шины ШИВх и РгИ . Затем в выбранную БАВ ячейку записывается слово из РгИ .

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

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

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