Особенности функционирования кэш-памяти

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

Реферат

По дисциплине: Вычислительные машины, сети и системы телекоммуникаций

На тему: «Кэш – память»

Выполнила:

Студентка 2 курса, ГФ

Андрусенко Галина

Проверила:

Литвиненко О.А.

Санкт-Петербург, 2011 г.

Оглавление

Введение

1. Цели и задачи кэш-памяти

2. Обеспечение быстрого доступа к интенсивно используемым данным

3. Согласование интерфейсов процессора и контроллера памяти

4. Упреждающая загрузка данных

5. Отложенная запись данных

6. Принцип действия кэш-памяти

7. Проблема согласования данных

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

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

Вывод

Введение

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

Рис.1.

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

На следующем уровне располагается более быстродействующая (время доступа равно примерно 10-20 наносекундам) и менее объемная (от десятков мегабайт до нескольких гигабайт) оперативная память, реализуемая на относительно медленной динамической памяти DRAM. Для хранения данных, к которым необходимо обеспечить быстрый доступ, используются компактные быстродействующие запоминающие устройства на основе статической памяти SRAM, объем которых составляет от нескольких десятков до нескольких сотен килобайт, а время доступа к данным обычно не превышает 8 нс.

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

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

Кэш-память, или просто кэш (cache), — это способ совместного функционирования двух типов запоминающих устройств, отличающихся временем доступа и стоимостью хранения данных, который за счет динамического копирования в «быстрое» ЗУ наиболее часто используемой информации из «медленного» ЗУ позволяет, с одной стороны, уменьшить среднее время доступа к данным, а с другой стороны, экономить более дорогую быстродействующую память.

Кэш-памятью, или кэшем, часто называют не только способ организации работы двух типов запоминающих устройств, но и одно из устройств — «быстрое» ЗУ – высокоскоростное запоминающее устройство небольшой емкости для временного хранения данных, не адресуемое непосредственно и не "видимое" для программиста. Оно стоит дороже и, как правило, имеет сравнительно небольшой объем.

«Медленное» ЗУ далее будем называть основной памятью, противопоставляя ее вспомогательной кэш-памяти.

кеш память данные интерфейс

1. Цели и задачи кэш-памяти

В задачи кэша входит:

· обеспечение быстрого доступа к интенсивно используемым данным;

· согласование интерфейсов процессора и контроллера памяти;

· упреждающая загрузка данных;

· отложенная запись данных.

2. Обеспечение быстрого доступа к интенсивно используемым данным

Архитектурно кэш-память расположена между процессором основной оперативной памятью (см. рис.) и охватывает все (реже часть) адресного пространства. Перехватывая запросы к основной памяти, кэш-контроллер смотрит: есть ли действительная (валидная от английского valid) копия затребованных данных в кэше. Если такая копия там действительно есть, то данные наскоро извлекаются из сверхоперативной памяти и происходит так называемое кэш-попадание (cache hit). В противном случае говорят о промахе – (cache miss), и тогда запрос данных переадресуется к основной оперативной памяти.

Рис.2. Расположение кэша в иерархии оперативной памяти

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

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

Поиск наименее нужных данных называется стратегией замещения. Можно принимать решение, основываясь на количестве обращений к каждой порции данных (частотный анализ), можно – на времени последнего обращения, выбрав ту, к которой дольше всего не обращались (алгоритм LRU – Least Recently Used), можно – на времени загрузки из основной памяти, вытеснив ту, которая была загружена раньше всех (алгоритм FIFO – First Input First Output), а можно просто случайно (randomize-алгоритм) (кстати, именно такая стратегия замещения использовалась в процессорах AMD K5).

В современных процессорах семейства x86 встречаются исключительно стратегии FIFO и LRU, частотный же анализ ввиду сложности его реализации в них не используется.

3. Согласование интерфейсов процессора и контроллера памяти

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

4. Упреждающая загрузка данных

Существует несколько стратегий загрузки данных из основной оперативной памяти в кэш-память. Простейший алгоритм загрузки, называемый загрузкой по требованию (on demand), предписывает обращаться к основной памяти только после того, как затребованных процессором данные не окажется в кэше (то есть, попросту говоря, после возникновения кэш-промаха). Использование такой стратегии приводитк тому, что в кэш попадают действительно нужные нам данные (и это плюс!), однако, при первом обращении к ячейке, процессору придется очень долго ждать – приблизительно 20 тактов системной шины, что есть несомненный минус! Стратегия спекулятивной (speculative) загрузки, напротив, предписывает помещать данные в кэш задолго то того, как к ним произойдет реальное обращение. Откуда же кэш-контроллеру знать, какие именно ячейки памяти потребуется процессору в ближайшем будущем? Наверняка знать этого он этого не может, но может попробовать угадать. Алгоритмы угадывания делятся на интеллектуальные и неинтеллектуальные. Типичный пример неинтеллектуального алгоритма – опережающая загрузка. Исходя из предположения, что данные из оперативной памяти обрабатываются последовательно в порядке возрастания адресов, кэш-контроллер, перехватив запрос на чтение первой ячейки, в порядке собственной инициативы загружает некоторое количество ячеек, последующих за ней. Если данные действительно обрабатываются последовательно, то остальные запросы процессора будут выполнены практически мгновенно, ведь запрошенные ячейки уже присутствуют в кэше. Следует заметить, что стратегия опережающей загрузки возникает уже в силу необходимости согласования разрядности оперативной памяти и процессора.

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

Интеллектуальный кэш-контроллер предсказывает адрес следующей запрашиваемой ячейки не по слепому шаблону, а на основе анализа предыдущих обращений. Исследуя последовательность кэш-промахов, контроллер пытается установить, какой именно зависимостью связны ее элементы и, если это ему удается, предвычисляет ее последующие члены. Если обращение к памяти происходит по регулярному шаблону, интеллектуальная стратегия спекулятивной загрузки при благоприятном стечении обстоятельств может полностью ликвидировать задержки, возникающие при ожидании загрузки данных из основной памяти. До недавнего прошлого интеллектуальные кэш-контроллеры использовались разве что в суперкомпьютерах, но теперь они реализованы в процессорах P-4 и AMD Athlon XP.

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

5. Отложенная запись данных

Наличие временного хранилища данных позволяет накапливать записываемые данные и затем, дождавшись освобождения системой шины, выгружать их в оперативную память "одним махом". Это ликвидирует никому не нужные задержки и значительно увеличивает производительность подсистемы памяти (подробнее об этом см. "Политики записи и поддержка когерентности"). В x86 процессорах механизм отложенной записи реализован начиная с Pentium и AMD K5. Более ранние модели были вынужденные непосредственно записывать в основную память каждую модифицируемую ячейку, что серьезно ограничивало их быстродействие. К счастью, сегодня такие процессоры практически не встречаются и об этой проблеме уже можно забыть.

6. Принцип действия кэш-памяти

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

- значение элемента данных;

- адрес, который этот элемент данных имеет в основной памяти;

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

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

Далее возможен один из двух вариантов развития событий:

- если данные обнаруживаются в кэш-памяти, то есть произошло кэш-попадание (cache-hit), они считываются из нее и результат передается источнику запроса;

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

Рис.3.Схема функционирования кэш-памяти

Понятно, что эффективность кэширования зависит от вероятности попадания в кэш. Покажем это путем нахождения зависимости среднего времени доступа к основной памяти от вероятности кэш-попаданий. Пусть имеется основное запоминающее устройство со средним временем доступа к данным t1 и кэш-память, имеющая время доступа t2, очевидно, что t2<t1. Пусть t — среднее время доступа к данным в системе с кэш-памятью, ар — вероятность кэш-попадания. По формуле полной вероятности имеем:

t - t1(d - р) + t2p - (t2 -t1)p+ t1

Среднее время доступа к данным в системе с кэш-памятью линейно зависит от вероятности попадания в кэш и изменяется от среднего времени доступа в основное запоминающее устройство t1 при р=0 до среднего времени доступа непосредственно в кэш-память t2 при р=1. Отсюда видно, что использование кэш-памяти имеет смысл только при высокой вероятности кэш-попадания.

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

Временная локальность. Если произошло обращение по некоторому адресу, то следующее обращение по тому же адресу с большой вероятностью произойдет в ближайшее время.

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

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

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

7. Проблема согласования данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вывод

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