Материал: Уч_пос_АрхКомп_2017

9. Организация кэш-памяти.

Использование кэш-памяти основано на свойстве локальности программ по обращению, имющем три составляющих:

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

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

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

Идея использования кэша как буферной памяти заключается в наличии двух видов памяти:

быстрой памяти малой емкости М₁ (n₁, tобр₁) и медленной памяти большой емкости М₂ (n₂, tобр₂), параметры которых: число ячеек - n_i и время обращения tобр_i характеризуются неравенствами

n₁ << n₂ и t _обр1 << t _обр2.

Если данные имеются в быстрой кэш-памяти, то они выбираются за время t _обр1, а если отсутствуют, то за время t _обр1 + t _обр2 данные выбираются из основной памяти и одновременно подгружаются в кэш-память.

Если благодаря свойству локальности удается исполняемый фрагмент программы и обрабатываемый массив данных разместить в кэш-памяти, то вероятность 0 <  << 1 отсутствия команд или данных в кэш - памяти удается сделать достаточно малой - обычно   0.02…0.05. Тогда среднее время обращения к такой системе буферизованной памяти будет

М {t _обр} = (1 - ) * t _обр1 +  * (t _обр1 + t _обр2) = t _обр1 +* t _обр2  t _обр1

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

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

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

С_оп = 256 Кслов=2¹⁸ слов, С_кэш = 2 Кслов=2¹¹ слов, С_блока = 16 слов (С - емкость);

М_оп = N_бл.оп. = 256К/16 = 16K = 2¹⁴ блоков., М_кэш = 2К/16 = 128 = 2⁷ блоков (М – число блоков);

L_адр.оп = 18бит = 14бит (адрес блока ОП) { 7бит (тег) +7бит (строка кэша)} + 4бит (слово в блоке)

L_{адр.кэш} = 11бит= 7бит (адрес строки кэша) + 4бит (слово в блоке) (L – длина адреса в битах)

Прямое отображение блоков оп на кэш-память

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

i = j mod M_кэш

В нашем примере i = j mod 128, где i = [0,127], j = [0,16383] и на строку КЭШа с номером i отображается каждый 128 блок ОП, начиная с блока i , что поясняется на рис. 6.6 . Здесь 14-битный адрес блока ОП разбивается на два поля: 7-битный тег (7 старших разрядов адреса) и 7-битный номер строки кэш-памяти, на которую может быть отображен этот блок ОП. При этом поле тега определяет, какой из списка блоков ОП, закрепленных за данной строкой кэша, сейчас адресуется. Когда блок ОП фактически заносится в соответствующую строку кэш-памяти, в поле тегов этой строки нужно записать тег именно этого блока, в качестве тега служат 7 старших разрядов адреса блока.

Память Память Тег

тегов данных 0 1 2 . . . . . . 127 Строка

7 бит 4 бит

К э ш п а м я т ь О с н о в н а я п а м я т ь

Рис.6.6

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

Ассоциативное отображение блоков ОП на Кэш-память

Такой способ отображения, иллюстрируемый рис.6.7, позволяет производить загрузку любого блока ОП в любую строку кэш-памяти. В кэш-памяти используется поле тегов, содержащее 2 тега: тег1 (14 бит), соответствющий адресу блока ОП, и тег2 (7 бит), определяющий адрес блока в КЭШе, а также поле данных, определяющее адрес слова в блоке. Контроллер кэш-памяти выделяет в адресе ОП два поля: поле тегов и поле слова. Поле тега совпадает с 14-битным адресом блока ОП. Для проверки наличия копии блока ОП в кэш-памяти логика управления контроллера кэша должна одновременно сравнить теги 1 всех строк КЭШа на совпадение с полем тега адреса ОП. Это обеспечивается использованием ассоциативной памяти для хранения тегов КЭШа. После нахождения строки КЭШа, тег1 которой совпал с адресом искомого блока ОП, по тегу 2 определяется размещение искомого блока в КЭШе.

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

Наборно-ассоциативное отображение блоков оп на Кэш-память

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

Адрес блока Адрес блока

в ОП (14б) в КЭШе (7б)

Тег1(14 бит) Тег2(7 бит) (4 бит)

Т е г и Данные

К э ш - п а м я т ь О с н о в н а я п а м я т ь

Рис.6.7

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

1. Замещение блока в строке кэш-памяти на новый блок ОП при необходимости загрузки последнего в полностью занятую кэш-память. Эта проблема возникает только для ассоциативного и наборно-ассоциативного способов отбражения блоков ОП на строки кэш-памяти. В настоящее время в основном используется два способа замещения блоков ОП в КЭШе:

1. LRU (Least-Recently-Used) – производится замена в кэш-памяти блока ОП, к которому дольше всего не обращались; этот способ требует поддерживать историю обращения к блокам (с помощью счетчиков).

2. FIFO (Fist-in, Fist-out) или обычная очередь – производится замена в кэш-памяти блока ОП, который загружался раньше всех других; это более дешевая, но не столь эффективная стратегия замены блоков в КЭШе по сравнению с LRU-стратегией.

2. Согласование данных в КЭШе и основной памяти.

1. Store through (Write through) – сквозная запись (одновременная запись данного в блок кэша и в блок основной памяти), при этом происходит трата ресурсов и времени на обновление основной памяти. Достоинство: надежный способ согласования данных.

2. Store In (Write back) – обратная запись, обновление блока ОП происходит только при выгрузке строки из КЭШа в ОП. Достоинство - более высокая производительность. Недостаток - временное различие данных в ОП и в КЭШе может привести к конфликтам (проявляется в многопроцессорных компьютерах с общей памятью).