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

СОЗУ с прямым доступом

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

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

Т_С Т₀.

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

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

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

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

(Страница128)

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

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

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

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

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

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

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

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

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

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

Рис. 5.3, Кэш с прямым отображением

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис 5.4. Внутренняя кэш-память 80486

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

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

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

□ если последнее обращение в паре L2 — L3 было к строке L2, то бит B2 устанавливается в 1, иначе — сбрасывается в 0.

Выбор заменяемой строки (когда все строки множества достоверны) определяет содержимое битов B0, B1, B2 (табл. 5.1).

Таблица 5.1. Содержимое битов B0, B1, B2

B0	B1	B2	Действие
		X	Заменяется строка L0
		X	Заменяется строка L1
	X		Заменяется строка L2
	X		Заменяется строка L3

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

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

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

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

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

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

□ CD (Cache Disable) — запрещение кэш-памяти;

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

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

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

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

При C0=0 и NW=1 осуществляется работа кэш в режиме обратной записи.

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

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

Дата добавления: 2015-04-25