СОЗУ с ассоциативным доступом

Применение СОЗУ с ассоциативным доступом позволяет автоматизировать процесс размещения данных в СОЗУ, обеспечивая "подмену" активных в данный момент ячеек ОЗУ ячейками СОЗУ. Эффективность такого подхода существенно зависит от выбранной стратегии замены информации в СОЗУ, причем использование ассоциативного СОЗУ имеет смысл только при условии Т_c << T₀.

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

Признаки равенства всех элементов одной ячейки поля признаков объединяются по "И" и устанавливают в 1 индикатор совпадения ИС, если информация, хранимая в поле признака ячейки, совпадает с информацией, подаваемой в качестве признака на вход Р накопителя.

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

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

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

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

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

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

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

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

Наличие АСОЗУ в ЭВМ позволяет (при достаточном его объеме и правильно выбранной стратегии загрузки) значительно увеличить производительность системы. При этом наличие или отсутствие АСОЗУ никак не отражается на построении программы. АСОЗУ не является программно-доступным объектом, оно скрыто от пользователя. Недаром в литературе для обозначения АСОЗУ часто используется термин "кэш-память" (cache — тайник).

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

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

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

Однако предложенная выше структура имеет существенный недостаток. Если проводить разбиение памяти на множества, как показано на рис. 5.3, то в большинстве случаев кэш будет использоваться крайне неэффективно.

Во-первых, хотя адресное пространство физической памяти 32-разрядных

микропроцессоров составляет 2³² байтов, в современных ПЭВМ обычно используют намять объемом 2²⁵ — 2²⁹ байтов. Следовательно, строки кэш, отображаемые на старшие (физически отсутствующие) множества памяти, никогда не будут использованы.

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

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

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

Например, внутренняя кэш-память процессоров i80486 и Pentium — ассоциативная по множеству. Вся физическая память разбивается на 128 множеств, а каждому множеству соответствуют 4 строки кэш. Рассмотрим подробнее организацию внутренней кэш-памяти процессора 80486 [3].

Внутренняя кэш 80486 (рис. 5.4) имеет объем 8 Кбайт и предназначена для хранения как команд, так и данных — копий информации ОЗУ. Информация перемещается из ОЗУ в кэш выровненными 16-байтовыми блоками (4 младшие бита физического адреса — нули). Кэш имеет четырех направленную (или четырехканальную) ассоциативную по множеству организацию, что является компромиссом между быстродействием и экономичностью кэш- памяти с прямым отображением и большим коэффициентом попаданий полностью ассоциативной кэш-памяти.

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

• 7 битов поля индекса (А4 — А10) определяют номер множества, в котором проводится поиск;

• старшие 21 бит адреса являются полем тега (признака), по которому осуществляется ассоциативный поиск (внутри множества из четырех блоков);

• четыре младшие бита адреса определяют позицию байта в блоке.

Когда при чтении возникает промах, в кэш копируется из ОЗУ 16-байтовый

блок (строка), содержащий запрошенную информацию.

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

Если недостоверных строк нет, то реализуется алгоритм замещения строк "nceвдo LRU" ("наиболее давно используемый"). Для каждого множества в блоке отведено три бита LRU, которые обновляются при каждом кэш-

попадании или заполнении строки. Они используются для реализации алгоритма замещения строки следующим образом.

Обозначим строки в множестве как L0, L1, L2, L3. Каждому множеству в блоке LRU соответствуют три бита В0, Вl, В2, которые модифицируются при каждом кэш-попадании или заполнении строки множества следующим образом:

• если последнее обращение было к строке L0 или Ll, то бит В0 устанавливается в 1, иначе — сбрасывается в 0;

• если последнее обращение в паре L0 —L1 было к строке L0, то бит B l устанавливается в 1, иначе — сбрасывается в 0;

• если последнее обращение в паре L2 — LЗ было к строке L2, то бит В2 устанавливается в 1, иначе — сбрасывается в О.

Выбор заменяемой строки (когда все строки множества достоверны) определяет содержимое битов ВО, B l, В2 (табл. 5.1).

Цикл записи при наличии кэш-памяти может реализоваться по-разному. Различают кэш со сквозной записью и кэш с обратной записью.

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

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

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

Конфигурацией кэш-памяти управляют два бита регистра CRO состояния машинам

NW (Not Write-through) — несквозная (обратная) запись.

При CD = 1 и NW = 1 запрещено заполнение строк, сквозная запись и объявление кэш-памяти недостоверной. Такая конфигурация позволяет использовать внутреннюю кэш-память как быстродействующее ЗУПВ.

При CD = 1 и NW = 0 заполнение строк запрещено, а сквозная запись и объявление кэш-памяти недостоверной разрешено. Эта конфигурация позволяет программе запрещать кэш-память на короткое время, а затем разрешать без очистки содержимого.

При С0 = 0 и NW = 0 заполнение строк, сквозная запись и объявление кэш- памяти недостоверной разрешены. Такая конфигурация является обычной рабочей для кэш-памяти.

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

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

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

Выше были рассмотрены способы организации сверхоперативной памяти и ее взаимодействия с оперативной. Не менее, а порой и более важной проблемой является организация взаимодействия в паре ОЗУ — ВЗУ.

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

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

При использовании этого метода вся память ЭВМ (ОЗУ и ВЗУ) рассматривается как единая виртуальная память. Адрес в этой памяти называется виртуальным или логическим. Вся виртуальная память делится на фрагменты одинакового размера, называемые виртуальными страницами. Размер страницы обычно составляет 0,5 — 4 Кбайт. Виртуальный адрес представляется состоящим из двух частей — номера страницы и номера слова на странице (смещения).

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

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

Поскольку размер СТ достаточно велик, она хранится целиком в ОЗУ и модифицируется операционной системой всякий раз, когда в распределении памяти происходят изменения.

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

Если в результате преобразования виртуального адреса в физический оказывается, что требуемая физическая страница располагается в ВЗУ, то выполнение программы становится невозможным, пока не произойдет "подкачка" требуемой страницы в ОЗУ. Такая ситуация называется страничным сбоем и должна формировать внутреннее прерывание, по которому запускается подпрограмма чтения страницы из ВЗУ в ОЗУ.

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

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

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

Теоретически доказано, что минимальное число страничных сбоев будет получено, если в алгоритме замещения использовать информацию о потоке обращений к страницам в будущем (алгоритм Михновского — Шopa) или, по крайней мере, о вероятности обращений к страницам в будущем.

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

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

Эффективность эвристического алгоритма можно характеризовать отношением:

где N₀ — число страничных сбоев при решении данной задачи с применением физически нереализуемого алгоритма; N_e, — то же с применением исследуемого эвристического алгоритма.

Эвристический алгоритм можно считать выбранным удачно (для данного

класса задач), если коэффициент k близок к 1. Значение N₀ может быть получено путем моделирования решения задачи (повторное) с предварительно зафиксированным потоком обращений к страницам.

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

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

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

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

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

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: