Способы отображения оперативной памяти на кэш-память
Сущность отображения блока оперативной памяти на кэш-память состоит в копировании его в какой-то блок кэша. После этого все обращения к блоку в ОЗУ должны переадресовываться на соответствующий блок кэша. Удачным является только такой способ отображения, который одновременно обеспечивает быструю проверку кэш-памяти на наличие в ней копии блока оперативной памяти; обеспечивает быстрое преобразование адреса блока ОП в адрес блока кэша и является наиболее экономичным.
Предположим, имеется кэш, состоящий из 512 блоков по 4 слова в каждом, т.е. Vкэш = 2К слов, и ОЗУ, адресуемое 16-разрядным адресом. ОЗУ имеет размер 64К слов, который будем рассматривать как 16К блоков по 4 слова. Будем считать для простоты, что последовательные адреса указывают на последовательные слова. При такой организации 16-разрядный адрес можно условно разделить на две части: младшие 2 разряда определяют адрес слова в пределах блока, а старшие – номер одного из 4096 блоков. Эти старшие 14 разрядов будем называть адресом блока ОЗУ. В свою очередь, для адресации любого слова кэш-памяти требуется 11-разрядный адрес (2 11 = 2К). Кэш-память разбита на блоки такого же размера, что и в ОЗУ, то есть содержит 128=27 блоков. 11-разрядный адрес слова в кэш-памяти также можно представить состоящим из двух частей: адреса слова в блоке (2 младших разряда) и адреса блока в кэш-памяти (7 старших разрядов).
Поскольку ЦП всегда обращается как бы к ОЗУ (кэш-память для ЦП невидима) и формирует для этого 16-разрядный адрес, необходим механизм преобразования такого адреса в 11-разрядный адрес слова в кэше. Так как расположение слов в блоке ОЗУ и блоке кэш-памяти идентично, для доступа к конкретному слову в блоке ОП в блоке кэш-памяти можно использовать младшие 2 разряда 16-разрядного адреса. Следовательно, остается лишь задача преобразования 14-разрядного адреса блока оперативной памяти в 7-разрядный адрес блока кэша.
Известные варианты отображения оперативной памяти на кэш можно свести к трем видам: полностью ассоциативному, прямому и множественно — ассоциативному
Полностью ассоциативный кэш
Построение кэш-памяти как ассоциативного ЗУ, рассмотренного ранее, дает так называемое ассоциативное отображение или полностью ассоциативный кэш (см. рис.4). В качестве тэга используется все разряды адреса за исключением разрядов, адресующих слово в блоке и байт в слове. В полностью ассоциативной кэш-памяти любой блок ОЗУ может быть помещён в любой блок кэша.
Полностью ассоциативный кэш имеет высокое быстродействие, обеспечивает гибкость при выборе блока для вновь записываемого блока. В момент обращения программе доступен весь кэш, а не его отдельные части, как при других способах отображения.
Принципиальный недостаток – необходимость использования дорогостоящей ассоциативной памяти и сложность замещения блоков, существенно возрастающая при увеличении ёмкости такого кэша.
Кэш с прямым отображением
Прямое отображение является простейшим способом отображения ОЗУ в кэш (рис.5). В этом случае j-й блок ОЗУ отображается на j-й блок кэша по модулю, равному количеству блоков в кэше. Для рассмотренного ранее примера–по mod 128.
Адрес в кэше интерпретируется следующим образом: старшие разряды содержат тэг, средние указывают на блок данных, а младшие — на слово в блоке. Можно сказать, что кэш с прямым отображением является адресно–ассоциативным. На рис.6 приведена упрощенная структура кэша с прямым отображением в режиме чтения.
Память тэгов и память данных выполнены как обычная адресная статическая память. Номер блока поступает на их адресные входы. Прочитанный тэг сравнивается с тэгом, указанным в адресе. В случае совпадения тэгов указанное в адресе слово передается через мультиплексор в процессор.
Что изменится, если в адресе, поступающем в кэш, поменять местами поле тэга и номера блока? Будет плохо! Перебор последовательных адресов приводит к переходу от блока к блоку. Если же эти поля поменять местами, то пока не перебраны значения тэга от 00…0 до11…1, обращения происходят к одному и тому же блоку. А это приводит к резкому падению количества попаданий и росту количества замещений.
Кэш с прямым отображением требует минимальных затрат оборудования, алгоритм замещения очень прост, но в момент обращения емкость кэша равна одному блоку, поэтому желательно блок делать длиной 8 или 16 слов.
Источник
21. Способы отображения основной памяти на кэш-память. Архитектуры кэш-памяти.
Сущность отображения блока основной памяти на кэш-память состоит в копировании этого блока в какую-то строку кэш-памяти, после чего все обращения к блоку в ОП должны переадресовываться на соответствующую строку кэш-памяти.
Способ отображения должен одновременно отвечает трем требованиям:
1. обеспечивать быструю проверку кэш-памяти на наличие в ней копии блока основной памяти;
2. обеспечивать быстрое преобразование адреса блока ОП в адрес строки кэша;
3. реализовывать достижение первых двух требований наиболее экономичными средствами.
Способы отображения оперативной памяти на кэш-память будем рассматривать на следующем примере:
• емкость основной памяти 256 Кслов;
• емкость кэш-памяти 2 Кслова;
• ОП разбивается на блоки по 16 слов в каждом (размер строки кэш-памяти 16 слов).
Для адресации каждого слова основной памяти необходим 18-разрядный адрес (256К = 218). ОП состоит из 256К/16 = 218/24 = 214 = 16384 блоков. При такой организации 18-разрядный адрес можно условно разделить на две части: младшие 4 разряда определяют адрес слова в пределах блока, а старшие 14 – номер блока. Эти старшие 14 разрядов будем называть адресом блока основной памяти.
В свою очередь, для адресации любого слова в кэш-памяти требуется 11-разрядный адрес (2К = 211). Кэш-память содержит 2К/16 = 211/24 = 27 = 128 строк. 11-разрядный адрес слова в кэш-памяти также можно представить состоящим из двух частей: адреса слова в строке – 4 младших разряда и адреса строки кэш-памяти – 7 старших разрядов.
Поскольку процессор всегда обращается к ОП (кэш-память для процессора невидима) и формирует для этого 18-разрядный адрес, необходим механизм преобразования такого адреса в 11-разрядный адрес слова в кэш-памяти. Так как расположение слов в блоке ОП и строке кэш-памяти идентично, для доступа к конкретному слову в блоке ОП или в строке кэш-памяти можно использовать младшие 4 разряда 18-разрядного адреса ОП. Следовательно, остается только задача преобразования 14-разрядного адреса блока основной памяти в 7-разрядный адрес строки кэш-памяти.
Известные варианты отображения основной памяти на кэш можно свести к трем видам:
1. прямое отображение;
2. полностью ассоциативное;
Прямое отображение. При прямом отображении адрес строки i кэш-памяти, на которую может быть отображен блок j из ОП, однозначно определяется выражением:
где m – общее число строк в кэш-памяти.
В нашем примере i =j mod 128, где адрес строки i может принимать значения от 0 до 127, а адрес блока – от 0 до 16383.
Такое отображение означает, что на строку кэша с номером i отображается каждый m-й блок ОП, если отсчет начинать с блока, номер которого равен i.
В нашем примере на строку кэша с номером i отображается каждый 128-й блок ОП. При этом основная память условно разбивается на 16384/m = 16384/128 = 128 страниц по m = 128 блоков и представляется в виде двухмерного массива блоков, в котором количество рядов равно числу строк в кэш-памяти, и в каждом ряду находятся блоки, претендующие (переадресуемые) на одну и ту же строку кэш-памяти (рис. 29).
При реализации такого отображения 14-разрядный адрес блока основной памяти условно разбивается на дваполя: 7-разрядный номер страницы и 7-разрядное поле строки. Поле строки указывает на одну из 128 = 2 7 строку кэш-памяти, в которую может быть отображен блок с заданнымадресом. Номер страницы определяет, какой именно блок из закрепленных за данной строкой кэша, отображается в этой строке. Когда блок фактически заносится в памятьданных кэша, в память теговкэш-памяти записывается номер страницы,которой принадлежит этот блок. Таким образом, семь старших разрядов адреса блока ОП служат тегом.
Прямое отображение – простой и недорогой в реализации способ отображения. Основной его недостаток – жесткое закрепление за определенными блоками ОП одной строки в кэш-памяти. Поэтому если программа поочередно обращается к словам из двух различных блоков, отображаемых на одну и тут же строку кэш-памяти, то постоянно будет происходить обновление данной строки и вероятность попадания будет низкой.
Полностью ассоциативное отображение. Полностью ассоциативное отображение позволяет преодолеть недостаток прямого отображения, разрешая загрузку любого блока ОП в любую строку кэш-памяти. При этом в адресе ОП выделяются два поля: поле адреса блока и поле слова вблоке. Когда блок фактически заносится в память данных кэша, в память теговкэш-памяти записывается адрес этого блока (рис. 30). Таким образом, адрес блока ОП служат тегом. Для проверки наличия копии блока вкэш-памяти контроллер кэш-памяти должен одновременно проверить теги всех строк на совпадение с полем адреса блока. Этому требованию наилучшим образом отвечает ассоциативная память.
Рисунок 30 – Организация кэш-памяти с полностью ассоциативным отображением Ассоциативное отображение обеспечивает гибкость при выборе строки для вновь записываемого блока. Принципиальный недостаток этого способа – необходимость использования дорогостоящей ассоциативной памяти.
Множественно-ассоциативное отображение. Множественно-ассоциативное отображение относится к группе методов частично- ассоциативного отображения. Оно является одним из возможных компромиссов, сочетающим достоинства прямого и ассоциативного способов отображения и, в известной мере, свободным от их недостатков.
Кэш-память (как тегов, так и данных) разбивается на v подмножеств (наборов), каждое из которых содержит k строк (принято говорить, что набор имеет k входов). Зависимость между набором и блоками ОП такая же, как и при прямом отображении:на строки, входящие в набор i, могут быть отображены только вполне определенные блоки основной памяти, в соответствии с соотношением i = j mod v,где j – адрес блока ОП. Вто же время размещение блоков по строкам набора – произвольное,и для поиска нужной строки в пределах набора используется ассоциативный принцип.
Рассмотрим пример 4-входовой кэш-памяти с множественно-ассоциативным отображением (рис. 31). Память данных кэш-памяти разбита на 32 набора по 4 строки в каждом. Память тегов также содержит 32 набора, в каждом из которых можетхраниться 4 значения теговпо одному на каждую строку набора. 14-разрядный адрес блока ОП представляется в виде двух полей: 9- разрядного поля тега и 5-разрядного поля номера набора. Номер набора однозначно указывает на один из наборов кэш-памяти.
Он также позволяет определить номера тех блоков ОП, которые можно отображать на этот набор. Такими являются блоки ОП, номера которых при делении на 2 5 = 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 – к ассоциативному.
Упрощенно можно считать,что кэш с множественно-ассоциативным отображениемпредставляет собой несколько параллельно и согласовано работающих каналов прямого отображения, в которых строки с одинаковыми номерами образуют соответствующий набор.
В зависимости от способа отображения основной памяти на кэш-память различают три архитектуры кэш-памяти:
1.кэш прямого отображения (direct-mapped cache);
2.полностью ассоциативный кэш (fully associative cache);
3.наборно- (частично- или множественно-) ассоциативный кэш (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,L1I-Cache – 32 KB × 2 8-way set associative (8WSA – 8-канальный наборно-ассоциативный кэш), L2 Cache – 2048 KB 8WSA.
Источник
Организация памяти вычислительной системы
Кэш-память
Кэш- память представляет собой быстродействующее ЗУ, размещенное на одном кристалле с ЦП или внешнее по отношению к ЦП. Кэш служит высокоскоростным буфером между ЦП и относительно медленной основной памятью. Идея кэш-памяти основана на прогнозировании наиболее вероятных обращений ЦП к оперативной памяти . В основу такого подхода положен принцип временной и пространственной локальности программы .
Если ЦП обратился к какому-либо объекту оперативной памяти , с высокой долей вероятности ЦП вскоре снова обратится к этому объекту. Примером этой ситуации может быть код или данные в циклах. Эта концепция описывается принципом временной локальности , в соответствии с которым часто используемые объекты оперативной памяти должны быть «ближе» к ЦП (в кэше ).
Для согласования содержимого кэш-памяти и оперативной памяти используют три метода записи:
- Сквозная запись (write through) — одновременно с кэш-памятью обновляется оперативная память .
- Буферизованная сквозная запись (buffered write through) — информация задерживается в кэш-буфере перед записью в оперативную память и переписывается в оперативную память в те циклы, когда ЦП к ней не обращается.
- Обратная запись (write back) — используется бит изменения в поле тега, и строка переписывается в оперативную память только в том случае, если бит изменения равен 1.
Как правило, все методы записи, кроме сквозной, позволяют для увеличения производительности откладывать и группировать операции записи в оперативную память .
В структуре кэш-памяти выделяют два типа блоков данных:
- память отображения данных (собственно сами данные, дублированные из оперативной памяти );
- память тегов (признаки, указывающие на расположение кэшированных данных в оперативной памяти ).
Пространство памяти отображения данных в кэше разбивается на строки — блоки фиксированной длины (например, 32, 64 или 128 байт ). Каждая строка кэша может содержать непрерывный выровненный блок байт из оперативной памяти . Какой именно блок оперативной памяти отображен на данную строку кэша , определяется тегом строки и алгоритмом отображения. По алгоритмам отображения оперативной памяти в кэш выделяют три типа кэш-памяти:
- полностью ассоциативный кэш ;
- кэш прямого отображения;
- множественный ассоциативный кэш .
Для полностью ассоциативного кэша характерно, что кэш-контроллер может поместить любой блок оперативной памяти в любую строку кэш-памяти (рис. 9.1). В этом случае физический адрес разбивается на две части: смещение в блоке (строке кэша ) и номер блока. При помещении блока в кэш номер блока сохраняется в теге соответствующей строки. Когда ЦП обращается к кэшу за необходимым блоком, кэш-промах будет обнаружен только после сравнения тегов всех строк с номером блока.
Одно из основных достоинств данного способа отображения — хорошая утилизация оперативной памяти , т.к. нет ограничений на то, какой блок может быть отображен на ту или иную строку кэш-памяти. К недостаткам следует отнести сложную аппаратную реализацию этого способа, требующую большого количества схемотехники (в основном компараторов), что приводит к увеличению времени доступа к такому кэшу и увеличению его стоимости.
Альтернативный способ отображения оперативной памяти в кэш — это кэш прямого отображения (или одновходовый ассоциативный кэш ). В этом случае адрес памяти (номер блока) однозначно определяет строку кэша , в которую будет помещен данный блок. Физический адрес разбивается на три части: смещение в блоке (строке кэша ), номер строки кэша и тег . Тот или иной блок будет всегда помещаться в строго определенную строку кэша , при необходимости заменяя собой хранящийся там другой блок. Когда ЦП обращается к кэшу за необходимым блоком, для определения удачного обращения или кэш-промаха достаточно проверить тег лишь одной строки.
Очевидными преимуществами данного алгоритма являются простота и дешевизна реализации. К недостаткам следует отнести низкую эффективность такого кэша из-за вероятных частых перезагрузок строк. Например, при обращении к каждой 64-й ячейке памяти в системе на рис. 9.2 кэш-контроллер будет вынужден постоянно перегружать одну и ту же строку кэш-памяти, совершенно не задействовав остальные.
Несмотря на очевидные недостатки, данная технология нашла успешное применение, например, в МП Motorola MC68020, для организации кэша инструкций первого уровня (рис. 9.3). В данном микропроцессоре реализован кэш прямого отображения из 64 строк по 4 байт . Тег строки, кроме 24 бит , задающих адрес кэшированного блока, содержит бит значимости , определяющий действительность строки (если бит значимости 0, данная строка считается недействительной и не вызовет кэш-попадания). Обращения к данным не кэшируются.
Компромиссным вариантом между первыми двумя алгоритмами является множественный ассоциативный кэш или частично-ассоциативный кэш (рис. 9.4). При этом способе организации кэш-памяти строки объединяются в группы, в которые могут входить 2, 4, : строк. В соответствии с количеством строк в таких группах различают 2-входовый, 4-входовый и т.п. ассоциативный кэш . При обращении к памяти физический адрес разбивается на три части: смещение в блоке (строке кэша ), номер группы (набора) и тег . Блок памяти , адрес которого соответствует определенной группе, может быть размещен в любой строке этой группы, и в теге строки размещается соответствующее значение . Очевидно, что в рамках выбранной группы соблюдается принцип ассоциативности. С другой стороны, тот или иной блок может попасть только в строго определенную группу, что перекликается с принципом организации кэша прямого отображения. Для того чтобы процессор смог идентифицировать кэш-промах, ему надо будет проверить теги лишь одной группы (2/4/8/: строк).
Данный алгоритм отображения сочетает достоинства как полностью ассоциативного кэша (хорошая утилизация памяти, высокая скорость), так и кэша прямого доступа (простота и дешевизна), лишь незначительно уступая по этим характеристикам исходным алгоритмам. Именно поэтому множественный ассоциативный кэш наиболее широко распространен (табл. 9.2).
Intel486 | Pentium | Pentium MMX | P6 | Pentium 4 | |
---|---|---|---|---|---|
L1 кэш команд | |||||
Тип | 4-вх. ассоц. | 2-вх. ассоц. | 4-вх. ассоц. | 4-вх. ассоц. | 8-вх. ассоц. |
Размер строки, байт | 16 | 32 | 32 | 32 | — |
Общий объем, Кбайт | 8/16 | 8 | 16 | 8/16 | 12Кmops |
L1 кэш данных | |||||
Тип | Общий с кэш инструкций | 2-вх. ассоц. | 4-вх. ассоц. | 2/4-вх. ассоц. | 4-вх. ассоц. |
Размер строки, байт | 32 | 32 | 32 | 64 | |
Общий объем, Кбайт | 8 | 16 | 8/16 | 8 | |
L2 кэш | |||||
Тип | Внешний | внешний 4-вх. ассоц. | 4-вх. ассоц. | 8-вх. ассоц. | |
Размер строки, байт | 32 | 32 | 64 | ||
Общий объем, Кбайт | 256/512 | 128-2048 | 256/512 |
Примечания: В Intel-486 используется единый кэш команд и данных первого уровня. В Pentium Pro L1 кэш данных — 8 Кбайт 2-входовый ассоциативный, в остальных моделях P6 — 16 Кбайт 4-входовый ассоциативный. В Pentium 4 вместо L1 кэша команд используется L1 кэш микроопераций ( кэш трассы).
Для организации кэш-памяти можно использовать принстонскую архитектуру (смешанный кэш для команд и данных, например, в Intel-486). Это очевидное (и неизбежное для фон-неймановских систем с внешней по отношению к ЦП кэш-памятью) решение не всегда бывает самым эффективным. Разделение кэш-памяти на кэш команд и кэш данных ( кэш гарвардской архитектуры) позволяет повысить эффективность работы кэша по следующим соображениям:
- Многие современные процессоры имеют конвейерную архитектуру, при которой блоки конвейера работают параллельно. Таким образом, выборка команды и доступ к данным команды осуществляется на разных этапах конвейера, а использование раздельной кэш-памяти позволяет выполнять эти операции параллельно.
- Кэш команд может быть реализован только для чтения, следовательно, не требует реализации никаких алгоритмов обратной записи, что делает этот кэш проще, дешевле и быстрее.
Именно поэтому все последние модели IA-32 , начиная с Pentium, для организации кэш-памяти первого уровня используют гарвардскую архитектуру.
Критерием эффективной работы кэша можно считать уменьшение среднего времени доступа к памяти по сравнению с системой без кэш-памяти. В таком случае среднее время доступа можно оценить следующим образом:
где Thit — время доступа к кэш-памяти в случае попадания (включает время на идентификацию промаха или попадания), Tmiss — время, необходимое на загрузку блока из основной памяти в строку кэша в случае кэш-промаха и последующую доставку запрошенных данных в процессор , Rhit — частота попаданий.
Очевидно, что чем ближе значение Rhit к 1, тем ближе значение Tср к Thit . Частота попаданий определяется в основном архитектурой кэш-памяти и ее объемом. Влияние наличия и отсутствия кэш-памяти и ее объема на рост производительности ЦП показано в табл. 9.3.
Источник