Измерение и метрика производительности кэша

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

Производительность компьютерной системы зависит от производительности всех отдельных блоков, включая блоки исполнения, такие как целочисленные, ветви и с плавающей точкой, блоки ввода-вывода, шину, кэши и системы памяти. Разрыв между скоростью процессора и скоростью основной памяти рос экспоненциально. До 2001–2005 годов скорость ЦП, измеряемая тактовой частотой, ежегодно росла на 55%, тогда как скорость памяти росла только на 7%. ^[1] Эта проблема известна как «стена памяти». Мотивация для кэша и его иерархии заключается в том, чтобы преодолеть этот разрыв в скорости и преодолеть стену памяти.

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

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

Введение в типы кэш-промахов

Увеличение производительности процессора за счет иерархии кэша зависит от количества обращений к кэшу, удовлетворяющих запросы на блокировку из кэша (попадания в кэш) по сравнению с теми, которые этого не делают. Неудачные попытки чтения или записи данных из кэша (промахи кэша) приводят к доступу к более низкому уровню или основной памяти, что увеличивает задержку. Существует три основных типа промахов кэша, известных как 3C [ ^2] , и некоторые другие менее популярные промахи кэша.

Обязательные промахи

Каждый блок памяти при первом обращении вызывает обязательный промах. Это означает, что число обязательных промахов равно числу отдельных блоков памяти, на которые когда-либо ссылались. Иногда их также называют холодными промахами . Холодных промахов нельзя избежать, если блок не будет предварительно выбран .

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

Конфликт промахивается

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

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

Промахи по емкости

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

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

Вышеуказанные три вида промахов касаются только однопроцессорных промахов.

Промахи по согласованности

Группа 3Cs промахов кэша может быть расширена до 4Cs , когда задействована многопроцессорная система с кэшем, четвертым C являются промахи когерентности. Количество промахов когерентности — это количество промахов доступа к памяти, которые пропущены из-за того, что строка кэша, которая в противном случае присутствовала бы в кэше потока, была аннулирована записью из другого потока. ^[3] Когерентность в многопроцессорной системе сохраняется, если присутствует только одна копия блока памяти или все копии имеют одинаковое значение. Даже если все копии блока памяти не имеют одинакового значения, это не обязательно приводит к промаху когерентности. Промах когерентности происходит, когда потоки выполняют загрузки таким образом, что они наблюдают разные значения блока памяти. ^[4]

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

Промахи в освещении

Группа промахов кэша 4Cs может быть расширена до 5Cs , когда многопроцессорная система включает в себя каталог когерентности, организованный как кэш, т. е. который может заменять записи. Пятый C означает Coverage (Покрытие). ^[5] Количество промахов покрытия — это количество пропущенных обращений к памяти, которые пропускаются из-за того, что строка кэша, которая в противном случае присутствовала бы в кэше процессора, была аннулирована в результате вытеснения каталога. Если каталог не может отслеживать строку кэша из-за своей ограниченной емкости, эта строка должна быть аннулирована из кэша процессоров для поддержания Coherence .

Ошибки, связанные с системой

Системные действия, такие как прерывания , переключения контекста и системные вызовы, приводят к приостановке процесса и изменению его состояния кэша. Когда выполнение процесса возобновляется, он терпит промахи кэша, чтобы восстановить измененное состояние кэша. Эти промахи называются системными промахами. ^[2]

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

Замененные промахи

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

Переупорядоченные промахи

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

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

Среднее время доступа к памяти

Эти промахи кэша напрямую коррелируют с увеличением числа циклов на инструкцию (CPI). Однако степень влияния промахов кэша на CPI также зависит от того, какая часть промаха кэша может перекрываться вычислениями из-за параллелизма на уровне инструкций (ILP ) и какая часть может перекрываться другими промахами кэша из-за параллелизма на уровне памяти . ^[2] Если мы проигнорируем оба этих эффекта, то среднее время доступа к памяти станет важной метрикой. Оно обеспечивает меру производительности систем памяти и иерархий. Оно относится к среднему времени, которое требуется для выполнения доступа к памяти. Это сложение времени выполнения инструкций памяти и циклов простоя памяти. Время выполнения — это время доступа к кэшу, а циклы простоя памяти включают время обслуживания промаха кэша и доступа к более низким уровням памяти. Если известны задержка доступа, скорость промаха и штраф за промах, среднее время доступа к памяти можно рассчитать с помощью:

$AMAT=T_{L1}+MR_{L1}\cdot MP_{L1}$

где — задержка доступа к кэшу первого уровня, — частота промахов кэша первого уровня, — дополнительные циклы, необходимые для обработки промаха на более высоком уровне по сравнению с попаданием на более высокий уровень, и рассчитывается по формуле: $T_{L1}$ $MR_{L1}$ $MP_{L1}$

$MP_{L1}=T_{L2}+MR_{L2}\cdot MP_{L2}$

Эту формулу можно расширить и использовать рекурсивно для всех последующих уровней иерархии памяти, чтобы получить . ^[6] $АМАТ$

Закон степеней кэш-промахов

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

$M=M_{0}*C^{-\альфа}$

где M — это частота промахов для кэша размером C , а M ₀ — это частота промахов базового кэша. Показатель α зависит от рабочей нагрузки и обычно находится в диапазоне от 0,3 до 0,7, со средним значением 0,5. Закон степени был проверен на довольно большом количестве реальных тестов. ^[7]

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

Профиль расстояния стека

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

Приложения, которые демонстрируют более временное поведение повторного использования, обычно получают доступ к данным, которые использовались недавно. Предположим, что ассоциативность кэша равна . Чтобы собрать информацию о профиле расстояния стека этого кэша, предполагая, что он имеет политику замены LRU, счетчики используются, начиная с до и один дополнительный счетчик , который ведет подсчет промахов. Счетчик увеличивается, когда на пути есть попадание , и счетчик увеличивается при каждом промахе. Профиль расстояния стека показывает тенденцию попаданий, уменьшаясь от самых последних использованных данных к наименее недавно использованным. Используя эту информацию о профиле расстояния стека, промах кэша для кэша с ассоциативностью и политикой замены LRU, где можно вычислить как $А$ $А+1$ $C_{0}$ $C_{A}$ $C_{<}A$ $C_{i}$ $я^{й}$ $C_{<}A$ $А{'}$ $А{'}<А$

$промах=C_{<}A+\sum _{i=A{'}+1}^{A}C_{i}$

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

Смотрите также

Иерархия кэша

Примечания

^ Хеннесси, Дж. и Паттерсон, Д. (2003). Архитектура компьютера: количественный подход, 3-е издание . Morgan-Kaufmann Publishers, Inc. ISBN 9781558607248.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ abcd Солихин, Ян (2015-11-17). Основы параллельной многоядерной архитектуры, издание 2016 года . Chapman & Hall. ISBN 978-1482211184.
^ «Моделирование промахов когерентности кэша на многоядерных процессорах» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
^ Швеция, Мишель Дюбуа, Университет Южной Калифорнии, США, Мурали Аннаварам, Университет Южной Калифорнии, США, Пер Стенстрём, Технологический университет Чалмерса (2012). Параллельная организация и проектирование компьютеров . Кембридж: Издательство Кембриджского университета. ISBN 9781139051224.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Рос, Альберто; Куэста, Блас; Фернандес-Паскуаль, Рикардо; Гомес, Мария Э.; Акасио, Мануэль Э.; Роблес, Антонио; Гарсия, Хосе М.; Дуато, Хосе (2010). EMC2: Расширение когерентности Маньи-Кура для крупномасштабных серверов . 17-я Международная конференция по высокопроизводительным вычислениям (HiPC). стр. 1–10. дои : 10.1109/HIPC.2010.5713176. ISBN 978-1-4244-8518-5.
^ Паттерсон, Джон Л. Хеннесси, Дэвид А. (2011). Архитектура компьютера: количественный подход (5-е изд.). Сан-Франциско, Калифорния: Morgan Kaufmann. ISBN 978-0-12-383872-8.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Хартштейн, А.; Шринивасан, В.; Пузак, ТР; Эмма, ПГ (2006-01-01). "Поведение промаха кэша". Труды 3-й конференции по Computing frontiers . CF '06. стр. 313–320. doi :10.1145/1128022.1128064. ISBN 978-1595933027. S2CID 17728397.
^ Мэттсон, Р. Л .; Гечеи, Дж.; Слютц, Д. Р.; Трейгер, И. (1970). «Методы оценки иерархий хранения». IBM Systems Journal . 9 (2): 78–117. doi :10.1147/sj.92.0078.