Принцип однородности памяти 4 страница

Рисунок 27 – Организация обращения к основной памяти на основе циклической схемы

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

Обычно B равно 2-16, но в некоторых случаях число банков памяти может достигать 64-128.

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

20. Кэш-память. Принципы кэширования памяти.

Кэш-память предназначена для повышения быстродействия процесса обращения к основной памяти.

Основная память, как правило, реализуется на относительно медленной и дешевой динамической памяти (DRAM), обращение к которой приводит к простою процессора – появляются такты ожидания. Статическая память (SRAM), построенная, как и процессор, на триггерных ячейках, имеет быстродействие, соизмеримое с быстродействием процессора, и способна сделать ненужными такты ожидания или сократить их количество, но имеет высокую стоимость. Разумным компромиссом для построения экономичных и производительных МПС является иерархический способ организации основной памяти. Идея заключается в сочетании основной памяти большого объема на DRAM с относительно небольшой буферной памятью на основе быстродействующей SRAM, т.е. в использовании двухуровневой памяти, когда между ОП и процессором размещается небольшая, но быстродействующая буферная память. В процессе работы в буферную память копируются те участки ОП, к которым производится обращение со стороны процессора. Производится отображение участков ОП на буферную память и переадресация на нее всех обращений в пределах скопированного участка. Выигрыш в быстродействии достигается за счет ранее рассмотренного свойства локальности.

Для обозначения рассмотренной буферной памяти получил распространение термин кэш-память (от английского слова cache – убежище, тайный склад, тайник, заначка), поскольку такая память обычно скрыта от программиста в том смысле, что он не может ее адресовать и может даже вообще не знать о ее существовании.

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

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

Кэш-память состоит из (рис. 28): массива данных, справочника или каталога (cache directory) и контроллера (устройства управления).

Рисунок 28 – Структура кэш-памяти

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

ОП состоит из 2ⁿ адресуемых слов, где каждое слово имеет уникальный n-разрядный адрес. При взаимодействии с кэшем эта память рассматривается как M блоков фиксированной длины по k слов в каждом (M = 2ⁿ/k). Кэш-память состоит из m блоков аналогичного размера (блоки в кэш-памяти принято называть строками), причем их число значительно меньше числа блоков в основной памяти (m << M). При считывании слова из какого-либо блока ОП этот блок копируется в одну из строк кэша. Поскольку число блоков ОП больше числа строк, отдельная строка не может быть выделена постоянно одному и тому же блоку ОП.

С каждой строкой кэша связана информация об адресе скопированного в нее блока основной памяти и ее состоянии. Информация о том, какой именно блок основной памяти занимает данную строку называется тегом (tag) и хранится в связанной с данной строкой ячейке памяти тегов. В качестве тега обычно используется часть адреса ОП. Здесь же хранится и информация о состоянии строки. Строка может быть действительной (valid), если в ней в текущий момент времени хранится (присутствует) копия соответствующего блока основной памяти, или недействительной. Строка может достоверно отражать соответствующий блок основной памяти или быть модифицированной (говорят строка «грязная» – dirty). Таким образом, кроме адресной части тега с каждой строкой кэша связаны биты признаков действительности (присутствия) V и модифицированности M данных. Память тегов представляет собой каталог или справочник кэш-памяти. В операциях обмена с основной памятью строка участвует целиком. Такой кэш называется несекторированным. Возможен и вариант секторированного кэша, при котором одна строка содержит несколько смежных секторов, размер которых соответствует минимальной порции обмена данными кэша с основной памятью. При этом в записи каталога, соответствующей каждой строке, должны храниться биты действительности для каждого сектора данной строки. Секторирование позволяет экономить память, необходимую для хранения каталога при увеличении объема кэша, так как при этом увеличивается количество разрядов каждого элемента каталога, а не количество самих элементов (размер каталога).

На эффективность применения кэш-памяти в иерархической системе памяти влияет целый ряд моментов. К наиболее существенным из них можно отнести:

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

Емкость кэш-памяти

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

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

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

Размер строки

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

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

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

21. Способы отображения основной памяти на кэш-память. Архитектуры кэш-памяти.

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

Способ отображения должен одновременно отвечает трем требованиям:

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

Способы отображения оперативной памяти на кэш-память будем рассматривать на следующем примере:

емкость основной памяти 256 Кслов;
емкость кэш-памяти 2 Кслова;
ОП разбивается на блоки по 16 слов в каждом (размер строки кэш-памяти 16 слов).

Для адресации каждого слова основной памяти необходим 18-разрядный адрес (256К = 2¹⁸). ОП состоит из 256К/16 = 2¹⁸/2⁴ = 2¹⁴ = 16384 блоков. При такой организации 18-разрядный адрес можно условно разделить на две части: младшие 4 разряда определяют адрес слова в пределах блока, а старшие 14 – номер блока. Эти старшие 14 разрядов будем называть адресом блока основной памяти.

В свою очередь, для адресации любого слова в кэш-памяти требуется 11-разрядный адрес (2К = 2¹¹). Кэш-память содержит 2К/16 = 2¹¹/2⁴ = 2⁷ = 128 строк. 11-разрядный адрес слова в кэш-памяти также можно представить состоящим из двух частей: адреса слова в строке – 4 младших разряда и адреса строки кэш-памяти – 7 старших разрядов.

Поскольку процессор всегда обращается к ОП (кэш-память для процессора невидима) и формирует для этого 18-разрядный адрес, необходим механизм преобразования такого адреса в 11-разрядный адрес слова в кэш-памяти. Так как расположение слов в блоке ОП и строке кэш-памяти идентично, для доступа к конкретному слову в блоке ОП или в строке кэш-памяти можно использовать младшие 4 разряда 18-разрядного адреса ОП. Следовательно, остается только задача преобразования 14-разрядного адреса блока основной памяти в 7-разрядный адрес строки кэш-памяти.

Известные варианты отображения основной памяти на кэш можно свести к трем видам:

прямое отображение;
полностью ассоциативное;
частично-ассоциативное.

Прямое отображение. При прямом отображении адрес строки i кэш-памяти, на которую может быть отображен блок j из ОП, однозначно определяется выражением:

i = j mod m,

где m – общее число строк в кэш-памяти.

В нашем примере i =j mod 128, где адрес строки i может принимать значения от 0 до 127, а адрес блока – от 0 до 16383.

Такое отображение означает, что на строку кэша с номером i отображается каждый m-й блок ОП, если отсчет начинать с блока, номер которого равен i.

В нашем примере на строку кэша с номером i отображается каждый 128-й блок ОП. При этом основная память условно разбивается на 16384/m = 16384/128 = 128 страниц по m = 128 блоков и представляется в виде двухмерного массива блоков, в котором количество рядов равно числу строк в кэш-памяти, и в каждом ряду находятся блоки, претендующие (переадресуемые) на одну и ту же строку кэш-памяти (рис. 29).

	Память тегов	Память данных	Страницы
Строки								Ряды
		Блок	Блок	Блок	Блок		Блок
		Блок	Блок	Блок	Блок		Блок
		Блок	Блок	Блок	Блок		Блок
…	…	…	…	…	…	…	…	…
		Блок	Блок	Блок	Блок		Блок
	Кэш-память	Основная память

Рисунок 29 – Организация кэш-памяти с прямым отображением

При реализации такого отображения 14-разрядный адрес блока основной памяти условно разбивается на два поля: 7-разрядный номер страницы и 7-разрядное поле строки. Поле строки указывает на одну из 128 = 2⁷ строку кэш-памяти, в которую может быть отображен блок с заданным адресом. Номер страницы определяет, какой именно блок из закрепленных за данной строкой кэша, отображается в этой строке. Когда блок фактически заносится в память данных кэша, в память тегов кэш-памяти записывается номер страницы, которой принадлежит этот блок. Таким образом, семь старших разрядов адреса блока ОП служат тегом.

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

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

	Память		Память	…
Строки	тегов		данных	Блок 2
			Блок 258	…
			Блок 32	Блок 32
			Блок 2	…
			Блок 16383	Блок 160
…	…		…	…
		Блок 258
			Блок 160	…
				Блок 16383
	Кэш-память		Основная память

Рисунок 30 – Организация кэш-памяти с полностью ассоциативным отображением

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

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

Кэш-память (как тегов, так и данных) разбивается на v подмножеств (наборов), каждое из которых содержит k строк (принято говорить, что набор имеет k входов). Зависимость между набором и блоками ОП такая же, как и при прямом отображении: на строки, входящие в набор i, могут быть отображены только вполне определенные блоки основной памяти, в соответствии с соотношением i = j mod v, где j – адрес блока ОП. В то же время размещение блоков по строкам набора – произвольное, и для поиска нужной строки в пределах набора используется ассоциативный принцип.

Рассмотрим пример 4-входовой кэш-памяти с множественно-ассоциативным отображением (рис. 31). Память данных кэш-памяти разбита на 32 набора по 4 строки в каждом. Память тегов также содержит 32 набора, в каждом из которых может храниться 4 значения тегов по одному на каждую строку набора. 14-разрядный адрес блока ОП представляется в виде двух полей: 9-разрядного поля тега и 5-разрядного поля номера набора. Номер набора однозначно указывает на один из наборов кэш-памяти. Он также позволяет определить номера тех блоков ОП, которые можно отображать на этот набор. Такими являются блоки ОП, номера которых при делении на 2⁵ = 32 дают в остатке число, совпадающее с номером данного набора кэш-памяти. Так, блоки 0, 32, 64, 96 и т. д. основной памяти отображаются на набор с номером 0; блоки 1, 33, 65, 97 и т. д. отображаются на набор 1 и т. д. Любой из блоков в последовательности может быть загружен в любую из четырех строк соответствующего набора.

Набор

Память тегов

Память данных

Тег

Блок

…

Блок

Кэш-память

Основная память

Рисунок 31 – Организация кэш-памяти с четырехканальным наборно-ассоциативным отображением

Роль тега выполняют 9 старших разрядов адреса блока ОП, в которых содержится порядковый номер блока в последовательности блоков, отображаемых на один и тот же набор кэш-памяти. Например, блок 65 в последовательности блоков, отображаемых на набор 1, имеет порядковый номер 2 (отсчет ведется от 0).

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

В предельных случаях, когда v = m, k = 1, множественно-ассоциативное отображение сводится к прямому, а при v = 1, k = m – к ассоциативному.

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

В зависимости от способа отображения основной памяти на кэш-память различают три архитектуры кэш-памяти:

кэш прямого отображения (direct-mapped cache);
полностью ассоциативный кэш (fully associative cache);
наборно- (частично- или множественно-) ассоциативный кэш (set associative cache).

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

Реализация полностью ассоциативного кэша является сложной аппаратной задачей, которая решается только для небольших объемов, т.е. полностью ассоциативный кэш из-за своей сложности не может иметь большой объем и используется, как правило, для вспомогательных целей. Например, в процессорах Intel Pentium MMX полностью ассоциативный кэш используется в блоке страничной переадресации (осуществляет трансляцию линейного адреса в физический страницами размером 4 Кбайт или 4 Мбайт) для построения буфера ассоциативной трансляции TLB (Translation Look aside Buffer), предназначенного для ускорения доступа к интенсивно используемым страницам размером 4 Кбайт: TLB команд – 32 вхождения, TLB данных – 64 вхождения.

Промежуточным между полностью ассоциативным кэшем и кэшем прямого отображения является наборно-ассоциативный кэш, который в основном и используется в современных микропроцессорах. Например, в процессоре Intel Core 2 Duo E6400: L1 D-Cache, L1 I-Cache – 32 KB × 2 8-way set associative (8WSA – 8-канальный наборно-ассоциативный кэш), L2 Cache – 2048 KB 8WSA.

22. Алгоритмы замещения информации в заполненной кэш-памяти.

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

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

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

1. Алгоритм замещения на основе наиболее давнего использования (LRU – Least Recently Used). Является наиболее эффективным алгоритм замещения. В соответствии с этим алгоритмом замещается та строка кэш-памяти, к которой дольше всего не было обращения. Проводившиеся исследования показали, что алгоритм LRU работает достаточно хорошо в сравнении с оптимальным алгоритмом.

Наиболее известны два способа аппаратной реализации этого алгоритма.

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

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

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

3. Алгоритм замены наименее часто использовавшейся строки (LFU – Least Frequently Used). В соответствии с этим алгоритмом заменяется та строка в кэш-памяти, к которой было меньше всего обращений. Аппаратная реализация алгоритма: каждая строка связывается со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик которой содержит наименьшее число.

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

23. Алгоритмы согласования содержимого кэш-памяти и основной памяти.

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

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

метод сквозной записи WT (write through);
метод обратной записи WB (write back).

По методу сквозной записи, прежде всего, обновляется слово, хранящееся в основной памяти. Если в кэш-памяти существует копия этого слова, то она также обновляется. Если же в кэш-памяти отсутствует нужная копия, то возможны два варианта:

сквозная запись с отображением – из основной памяти в кэш-память пересылается блок, содержащий обновленное слово;
сквозная запись без отображения – пересылка блока в кэш-память не производится.

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