Способы отображения кэш память

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

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

Предположим, имеется кэш, состоящий из 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).

Таблица 9.2. Характеристики подсистемы кэш-памяти у ЦП IA-32
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.

Источник

Оцените статью
Разные способы