Выбор рационального количества уровней и объема кэш-памяти

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

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

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

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

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

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

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

 

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

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

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

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

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

Рис. 5.27. Прямое отображение

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

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

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

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

 

Схемы выполнения запросов в системах с кэш-памятью

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

Рис. 5.29. Схема выполнения запроса к памяти в системе, использующей кэширование

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

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

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

Рис. 5.30. Двухуровневое кэширование

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

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

Рис. 5.31. Схема выполнения запроса на чтение в системе с двухуровневым кэшем

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

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

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

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

Рис. 5.32. Схема выполнения запроса на запись в системе с двухуровневым КЭШем

                          Для чего нужна кэш-память процессора?

Как уже упоминалось выше, главное назначение кэш-памяти –  это хранение данных, которые часто  используются процессором. Кэш является буфером, в который загружаются  данные, и, несмотря на его небольшой  объём, (около 4-16 Мбайт) в современных процессорах, он дает значительный прирост производительности в любых приложениях.

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

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

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

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

 

                               Уровни кэш-памяти процессора.

Современные процессоры, оснащены кэшем, который состоит, зачастую из 2 –ух или 3-ёх уровней. Конечно же, бывают и исключения, но зачастую это именно так.

В общем, могут быть такие  уровни: L1 (первый уровень), L2 (второй уровень), L3 (третий уровень). Теперь немного подробнее  по каждому из них:

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