кэширование

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

Кэширование памяти.Типы кэша. Управление кэшированием.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Размер строки, тэга и индекса 

Любая кэш-память подразделяется на так называемые строки (lines).

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

ПОЧЕМУ??


потому что это привело бы к очень тяжёлым последствиям с точки зрения производственных затрат.

ЗАЧЕМ??

Обоснуй?!

?Если рассмотреть 32-битное линейное физическое адресное пространство, позволяющее непосредственно поддерживать до 4Гб оперативной памяти, каждый байт в кэш-памяти должен обслуживаться 4 адресными байтами!
?Кроме того, такая кэш-память была бы очень плоха с точки зрения производительности

Поэтому куда удобнее адресовать некоторые группы из соседствующих байт, которые и будут формировать строки кэш-памяти. На практике широко используются строки по 32 или 64 байта, хотя их размер может достигать даже 1024 байт. Естественно, размер строки должен быть эквивалентен двойке в некоторой целой положительной степени

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Размер строки, тэга и индекса 

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

Nota Bene: не путать с динамическими и статическими ячейками памяти, это другое.

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

Коля в теме!

Другими словами, группа соседствующих байт может помещена в строку кэш-памяти тогда и только тогда, если её начальный адрес выровнен по границе, равной размеру строки. Например, 32-байтная строка может быть заполнена информацией из оперативной памяти, находящейся по шестнадцатеричным (десятичным) адресам 00-1F (00-31), 20-3F (32-63), 40-5F (64-95) и т. д.
? Кроме иных преимуществ, это простое правило позволяет сократить число адресных бит в расчёте на одну строку. Если точнее, то на 5 в вышеприведённом примере, т. е. log2(32) = 5.

Каждое адресное поле состоит из двух основных частей:

статическая (index),
которая содержит младшие биты адреса:
значение зафиксировано

динамическая (tag),
которая содержит старшие биты адреса:
может быть изменена в процессе работы

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Размер строки, тэга и индекса 

Для объяснения их функционального назначения необходимо ввести понятие логической сегментации оперативной памяти

Допустим,что:
имеется некоторое физическое пространство оперативной памяти, состоящее из M сегментов памяти одинакового размера, каждый из которых равен по размеру сегменту кэш-памяти.
Каждый сегмент памяти состоит из N строк одинакового размера, каждая из которых равна по размеру строке кэш-памяти.
Таким образом, чтобы получить адрес какой-либо строки памяти, необходимо сначала определить номер её сегмента памяти, затем номер данной строки в этом сегменте и объединить оба номера.
Для полноты картины осталось лишь подставить тэг вместо номера сегмента и индекс вместо номера строки.

Размер тэга строки кэш-памяти зависит от 3 основных факторов:
размера кэш-памяти;
ассоциативности кэш-памяти;
кэшируемого размера оперативной памяти.

Этот размер рассчитывается по следующей формуле:

Stag — размер одного тэга кэш-памяти, в битах;
Smemory — максимальный кэшируемый размер оперативной памяти, в байтах;
Scache — размер кэш-памяти, в байтах;
A — ассоциативность кэш-памяти, в каналах.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Размер строки, тэга и индекса 

?Следует уточнить, что ровно столько бит на тэг необходимо для кэширования именно 1Гб оперативной памяти при данной организации кэш-памяти.
Если сократить количество бит, то такой кэш останется работоспособным, однако кэшируемый размер оперативной памяти уменьшится. Например, 8 бит на тэг позволят адресовать уже только 28 = 256 сегментов памяти по 512Кб, что позволит кэшировать лишь 128Мб оперативной памяти.
Информация, находящаяся выше этой границы, кэшироваться не будет.

Таким образом, для абстрактной системы с максимальным кэшируемым объёмом оперативной памяти в 1Гб и кэш-памятью (неважно какого уровня) размером в 1Мб с 2-канальной ассоциативностью потребуется ровно 11 бит для каждого тэга. Другими словами, для адресации любым отдельным тэгом 1Гб / 512Кб = 2048 сегментов памяти потребуется log2(2048) = 11 бит.

Размер индекса зависит от размеров сегмента кэш-памяти и строки. Фактически, его должно быть достаточно для нумерации всех строк в пределах отдельно взятого сегмента. Например, если имеется сегмент кэш-памяти в 512Кб с 32-байтными строками, то размер индекса составит log2(512Кб / 32б) = 14 бит.

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Размер строки, тэга и индекса 

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

2.Как правило, поля данных защищаются либо проверкой чётности (parity checking) на уровне отдельных байт, либо одним из протоколов проверки и коррекции ошибок (ECC — Error Checking and Correcting) на уровне целого поля, большинство из которых основывается на алгоритме Хэмминга (the Hamming algorithm).

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

4.Тем не менее, какой бы из алгоритмов защиты информации ни был выбран, его обслуживающая логика привнесёт сложности в существующую разработку и неминуемо отразится на задержках при работе.

5.Если точнее, то при каждой операции чтения контрольная сумма поля данных должна быть сосчитана и сверена с сохранённой. Наиболее тяжёлым является случай частичной записи в действительную строку, так как контрольная сумма должна быть сосчитана дважды: до и после изменения строки.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

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

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

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

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

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

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

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

случайное отображение

детерминированное отображение

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

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

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

Выбор данных на выгрузку осуществляется среди всех записей кэша.

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

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

Ассоциативный поиск в кэше со случайным отображением

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

Второй, детерминированный способ отображения предполагает, что любой элемент основной памяти всегда отображается в одно и то же место кэш-памяти.
В этом случае кэш-память разделена на строки, каждая из которых предназначена для хранения одной записи об одном элементе данных1 и имеет свой номер.
Между номерами строк кэш-памяти и адресами оперативной памяти устанавливается соответствие «один ко многим»: одному номеру строки соответствует несколько (обычно достаточно много) адресов оперативной памяти.

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

Например, пусть в кэш-памяти может храниться 1024 записи, то есть кэш имеет 1024 строки, пронумерованные от 0 до 1023.
Тогда любой адрес оперативной памяти может быть отображен на адрес кэш-памяти простым отделением 10 двоичных разрядов.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

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

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

Например, пусть в кэш-памяти может храниться 1024 записи, то есть кэш имеет 1024 строки, пронумерованные от 0 до 1023.
Тогда любой адрес оперативной памяти может быть отображен на адрес кэш-памяти простым отделением 10 двоичных разрядов.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

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

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

Например, пусть в кэш-памяти может храниться 1024 записи, то есть кэш имеет 1024 строки, пронумерованные от 0 до 1023.
Тогда любой адрес оперативной памяти может быть отображен на адрес кэш-памяти простым отделением 10 двоичных разрядов.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

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

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

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

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

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

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

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

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

Комбинирование прямого и случайного отображения

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш прямого отображения

ПРИНЦИП

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш прямого отображения

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Наборно-ассоциативный кэш

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Наборно-ассоциативный кэш

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

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

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Наборно-ассоциативный кэш

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

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

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

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память: Кэш прямого отображения

Direct Mapped Cache
Introduction
Let's assume, as we did for fully associate caches that we have:
128 slots
32 bytes per slot
Parking Lot Analogy
Suppose we have 1000 parking spots. However, instead of being unnumbered, each parking spot is given a 3 digit number from 000 to 999.

Your parking spot is based on the first 3 digits of your student ID number.

What problem can occur? If you received your social security number (student ID) in Maryland, the first three digits of your student ID is likely to be in the low 200's.

Thus, there's a much higher chance someone will be in your parking spot. There's also a chance that parking spots numbered in the 900's might be mostly empty since few students may have student IDs with the first 3 digits in that range.

This is basically the direct-mapped scheme. The advantages of this scheme are that it's simple to find your parking spot. It can only be in one location.
Direct Mapped Scheme
In a direct mapped cache, we treat the 128 slots as if they were an array of slots. We can index into the array using binary numbers. For 128 slots, you need 7 bits. Thus, the index of the array is from 0000000two up to 1111111two.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память:

How do we decide which slot the cache line associated with address A31-0 should go into?

Here's how we do it:



Since we have 128 slots, we need to specify which one slot we need the cache line to go in. This requires lg 128 = 7 bits. Where do we get the bits from? Directly from the address itself.

Bits A4-0 is still the offset. The slot number are the next 7 bits, Bits A11-5. The remaining bits, A31-12 is the tag.
Finding the Slot
Finding a slot is now easy. Suppose you have address B31-0.
Use bits B11-5 to find the slot.
See if bits B31-12 match the tag of the slot.
If so, get the byte at offset B4-0.
If not, fetch the 32 bytes from memory, and place it in the slot, updating valid bit, dirty bit, and tag as neededx
Drawbacks
The drawback of this scheme is obvious. Effectively, we have a hash table with a very simple hash function (use bits B11-5). This can cause collisions at that particular slot.

Unlike a hash table, we do not resolve such collisions by finding the next free slot. Instead, we overwrite the value in the slot.

Just think of the parking lot analogy. A direct mapped scheme works poorly if many students have permits for the same spot, while other spots have very few permits.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Кэш-память:

The data you have might simply map to the same slot, and you could have cache lines going in and out all the time.
Advantages
If there's an advantage to the scheme, it's that it's very simple. You don't have to simultaneously match tags with all slots. You just have one slot to check.

If the data isn't in the slot, it's obvious that this is the slot to get evicted.
Why the Middle Bits?
We can pick any bits we want in the address, instead of the middle bits nearest the offset. Why did we pick those bits.

The problem with picking the high bits is that data and program tend to occupy a small section of memory. Because of that, they tend to share the same high bits.

This isn't so surprising. Consider a 10,000 page book, where each page has 5 digits (thus, there are pages 03401 and pages 00023). Grab any 100 consecutive pages, and the top two digits are highly like to be the same.

This can happen with data too. All the data will have very similar high bits. You want the bits as low as possible, so you get enough variation so that data can go into each slot with equal likelihood (so you hope).

You can't pick the low bits, because you need them to serve as the offset.
Summary
A direct-mapped cache scheme makes picking the slot very simple. It treats the slot as a large array, and the index of the array is picked from bits of the address (which is why we need the number of slots to be a power of 2---otherwise we can't select bits from the address)

The scheme can suffer from many addresses "colliding" to the same slot, thus causing the cache line to be repeatedly evicted, even though there may be empty slots that aren't being used, or being used with less frequency.

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

http://www.intuit.ru/department/hardware/csorg/9/2.html
http://www.zcub.ru/blog/org_comp_system/naborno-associativnyj-kesh.php
http://www.ord.com.ru/files/book3/p421.html
http://alasir.com/articles/cache_principles/cache_line_condition_rus.html
http://education.aspu.ru/view.php?olif=gl5

Анимация работы наборно-ассоциативного кэша:
http://www.scss.tcd.ie/~jones/vivio/caches/cache.htm

Используемые Интернет-ресурсы:

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

Книга «Архитектура ЭВМ»,автор Мюллер
Книга «Процессоры Pentium4, Athlon и Duron», авторы Михаил Гук, Виктор Юров
Книга «Архитектура ЭВМ», автор Танненбаум