Рейтинг@Mail.ru
[Войти] [Зарегистрироваться]

Наши друзья и партнеры

UnixForum
купить дешевый 
компьютер родом из Dhgate.com




Lines Club

Ищем достойных соперников.

Библиотека сайта rus-linux.net

На главную -> MyLDP -> Тематический каталог -> Аппаратное обеспечение

Что каждый программист должен знать о памяти.

Часть 2: Кэш-память процессора

Оригинал: "Memory part 2: CPU caches"
Автор: Ulrich Drepper
Дата публикации: October 1, 2007
Перевод: Н.Ромоданов
Дата перевода: апрель 2012 г.
Назад Оглавление Вперед

3.2 Как работает кэш-память высокого уровня

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

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

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

Поскольку в дополнение к фактически используемой памяти под тег требуется еще место, неэффективно использовать слова в качестве средства поиска данных в кэш-памяти. Для 32-разрядных слов на машине с архитектурой x86 для самого тэга, возможно, потребуется 32 бита памяти или более. Кроме того, поскольку пространственная компактность является одним из принципов, на которых основывается использование кэш-памяти, было бы плохо не принимать это во внимание. Поскольку есть вероятность, что фрагменты памяти, расположенные по соседству, могут использоваться совместно, они должны загружаться в кэш память вместе. Вспомните также о том, что мы узнали в разделе 2.2.1: использование модулей оперативной памяти будет еще более эффективным, если в них перемещаются по рядам подряд сразу много слов данных, причем без подачи нового сигнала CAS и даже сигнала RAS. Таким образом, данные хранятся в кэш-памяти не в виде отдельных слов, а, наоборот, в виде "строк", состоящих из нескольких смежных слов. В ранних вариантах кэш-памяти длина этих строк была 32 байта, теперь нормой является 64 байта. Если ширина шины памяти равна 64 бита, то это значит, что передача одной кэш-строки осуществляется за 8 действий. В DDR этот режим транспортировки данных очень эффективен.

Когда содержимое памяти необходимо процессору, то вся кэш-строка загружается в кэш-память L1d. Адрес памяти для каждой кэш-строки вычисляется с помощью маскирования значения адреса, зависящего от размера кэш-строки. Для 64 байтовой кэш-строки это означает, что обнуляются младшие 6 битов. Эти биты используются как смещение в кэш-строке. Оставшиеся биты в некоторых случаях используется для поиска кэш-строки в кэш-памяти, а также в качестве тега. На практике значение адреса делится на три части. Для 32-битного адреса это может выглядеть следующим образом:

Если размер кэш-строки равен 2O, то младшие O битов будут использоваться как смещение в кэш-строке. Следующие S битов рассматриваются как "индекс кэш-набора" ("cache set"). Мы вскоре подробнее рассмотрим, почему для кэш-строк используются кэш-наборы, а не один непрерывный участок. На данный момент достаточно понимать, что есть 2S кэш-наборов, содержащих кэш-строки. В результате остается 32 - S - O = T битов, из которых формируется тег. Эти Т битов представляют собой значение, ассоциированное (связанное) с каждой отдельной кэш-строкой и используемое для того, чтобы можно было различать все алиасы {известно, что все кэш-строки с одинаковым значением части S адреса имеют один и тот же алиас}, которые кэшированы в одном и том же кэш-наборе. Биты S используются для адресации кэш-набора и их не нужно сохранять, поскольку они одинаковы для всех кэш-строк в одном кэш-наборе.

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

Для того, чтобы в кэш-память можно было загрузить новые данные, почти всегда сначала необходимо освободить место. При удалении из кэш памяти L1d кэш-строка перемещается вниз — в кэш-память L2 (в которой используется тот же самый размер кэш-строки). Конечно, это означает, что в кэш-памяти L2 должно быть место. А это, в свою очередь, может быть причиной перемещения содержимого в кэш-память L3 и, в конце концов, в основную память. Каждое последующее выталкивание содержимого из кэш-памяти будет все более дорогостоящим. То, что здесь описано, является моделью эксклюзивной или исключающей кэш-памятью (exclusive cache), предпочтение которой отдается в современных процессорах AMD и VIA. В Intel реализуется инклюзивная или включающая кэш-память (inclusive caches) {Это обобщение не вполне корректно. Некоторые варианты кэш-памяти являются исключающими, а некоторые включающие варианты кэш-памяти имеют свойства исключающей кэш-памяти}, в котором каждая кэш-строка, имеющаяся в кэш-памяти L1d, также присутвует в кэш-памяти L2. Поэтому удаление из кэш-памяти L1d происходит гораздо быстрее. При достаточном размере кэш-памяти L2 накладные расходы, вызванные хранением содержимого в двух местах, будут минимальными, а при выталкивании содержимого из кеш-памяти дадут выигрыш. Возможным преимуществом исключающей кэш-памяти в том, что загрузка новой кэш-строки выполняется только в кэш-память L1d, а не в L2, что может происходить быстрее.

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

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

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

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

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

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

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

Наконец, мы должны иметь общее представление о расходах, связанных попаданиями и промахами, возникающими при использовании кэш-памяти. Ниже приведены цифры для процессора Intel Pentium M:

ГдеЦиклы

Регистр

<= 1

Кэш-память L1d

~3

Кэш-память L2

~14

Основная память

~240

Это фактическое время доступа, измеренное в циклах процессора. Интересно отметить, что для кэш-памяти L2, реализованной в виде микросхемы, основная часть (возможно, даже большая) времени доступа связана с передачей сигналов по проводникам. Это физическое ограничение, которое может только ухудшиться по мере увеличения размера кэш-памяти. Эти цифры могут улучшиться только при смене технологического процесса (например, в линейке Intel переход от технологии 60 нм для Merom на технологию 45 нм для Penryn).

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

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

Когда выполняется операция записи, процессор не обязан ждать, пока значение будет надежно сохранено в памяти. Если значение, запоминаемое в памяти, не будет сказываться на выполнении следующих инструкций, то нет причин, которые бы мешали процессору продолжать выполнение дальше. Он может достаточно рано начать выполнение следующей команды. Если используются теневые регистры (shadow registers), в которых могут находиться значения, уже недоступные в обычном регистре, процессор даже может изменять значение, которое должно быть запомнено с помощью еще не полностью выполненной операции записи.

Рис.3.4: Время доступа для операций записи, выполняемых случайным образом

Иллюстрация влияния использования кэш-памяти приведена на рис.3.4. Далее мы расскажем о программе, которая генерирует данные; это простая имитация программы, случайным образом обращающаяся к некоторым областям памяти, которые можно переконфигурировать. Каждый элемент данных имеет фиксированный размер. Количество элементов зависит от размера выбранного рабочего набора. По оси Y указывается среднее число циклов процессора, необходимое для обработки одного элемента; обратите внимание, что шкала оси Y логарифмическая. В диаграммах подобного вида то же самое касается и оси X. Размер рабочего набора всегда указывается в виде степеней числа 2.

На графике показано три различных участка. Это не удивительно: в конкретном процессоре есть кэш-память L1d и L2 , но нет кэш-памяти L3. Исходя из некоторого опыта, мы можем сделать вывод, что размер кэш-памяти L1d равен 213 байтов, а размер кэш-памяти L2 равен 220 байтов. Если весь рабочий набор помещается в кэш-память L1d, то количество циклов на одну операцию для каждого элемента меньше 10. Как только он превышает размер кэш-памяти L1d, процессор будет загружать данные из кэш-памяти L2 и среднее время возрастет примерно до 28. Как только кэш-памяти L2 станет недостаточно, затрачиваемое время резко увеличится до 480 циклов и более. Это время, в течение которого большинству операций придется загружать данные из основной памяти. И хуже того: поскольку данные изменяются, грязные кэш-строки должны также записываться обратно в память.

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


Назад Оглавление Вперед


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

Комментарии отсутствуют