Измерение и метрика производительности кеша - Cache performance measurement and metric

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

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

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

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

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

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

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

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

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

Конфликт пропускает

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

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

Пропускная способность

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

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

Влияние изменения основных параметров кеша на промахи кеша.^[2]
Параметры	Обязательные промахи	Конфликт пропускает	Пропускная способность
Большой размер кеша	Нет эффекта	Нет эффекта	Снижаться
Большой размер блока	Снижаться	Неопределенный эффект	Неопределенный эффект
Большая ассоциативность	Нет эффекта	Снижаться	Нет эффекта

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

Отсутствует согласованность

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

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

Охват промахов

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

Системные промахи

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

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

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

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

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

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

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

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

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

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

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

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

эту формулу можно расширить и использовать рекурсивно для всех последующих уровней иерархии памяти, чтобы получить ${ displaystyle AMAT}$ .^[6]

Степенной закон промахов в кэше

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

${ Displaystyle M = M_ {0} * C ^ {- alpha}}$

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

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

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

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

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

${ displaystyle miss = C _ {<} A + sum _ {я = A {'} + 1} ^ {A} C_ {i}}$

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

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

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

Примечания

^ Хеннесси, Дж. И Паттерсон, Д. (2003). Компьютерная архитектура: количественный подход, 3-е издание. Издательство Morgan-Kaufmann Publishers, Inc. ISBN 9781558607248.CS1 maint: несколько имен: список авторов (связь)
^ ^а ^б ^c ^d Солихин, Ян (17.11.2015). Основы параллельной многоядерной архитектуры, издание 2016 г.. Чепмен и Холл. ISBN 978-1482211184.
^ «Моделирование нарушений когерентности кэша на многоядерных компьютерах» (PDF). Цитировать журнал требует | журнал = (помощь)
^ Швеция, Мишель Дюбуа, Университет Южной Калифорнии, США, Мурали Аннаварам, Университет Южной Калифорнии, США, Пер Стенстрём, Технологический университет Чалмерса (2012). Параллельная компьютерная организация и дизайн. Кембридж: Издательство Кембриджского университета. ISBN 9781139051224.
^ Рос, Альберто; Куэста, Блас; Фернандес-Паскуаль, Рикардо; Гомес, Мария Э .; Acacio, Manuel E .; Роблес, Антонио; Гарсия, Хосе М .; Дуато, Хосе (2010). EMC2: расширение согласованности Magny-Cours для крупномасштабных серверов. 17-я Международная конференция по высокопроизводительным вычислениям (HiPC). С. 1–10. Дои:10.1109 / HIPC.2010.5713176. ISBN 978-1-4244-8518-5.
^ Паттерсон, Джон Л. Хеннесси, Дэвид А. (2011). Компьютерная архитектура: количественный подход (5-е изд.). Сан-Франциско, Калифорния: Морган Кауфманн. ISBN 978-0-12-383872-8.
^ Hartstein, A .; Srinivasan, V .; Пузак, Т. Р .; Эмма, П. Г. (01.01.2006). Cache Miss Behavior: Is It √2?. Труды 3-й конференции по компьютерным границам. CF '06. С. 313–320. Дои:10.1145/1128022.1128064. ISBN 978-1595933027.
^ Маттсон, Р.; Gecsei, J .; Slutz, D. R .; Трейгер, я (1970). «Методы оценки иерархий хранения». Журнал IBM Systems. 9 (2): 78–117. Дои:10.1147 / sj.92.0078.

[1] Хеннесси, Дж. И Паттерсон, Д. (2003). Компьютерная архитектура: количественный подход, 3-е издание. Издательство Morgan-Kaufmann Publishers, Inc. ISBN 9781558607248.CS1 maint: несколько имен: список авторов (связь)

[:0-2] а ^б ^c ^d Солихин, Ян (17.11.2015). Основы параллельной многоядерной архитектуры, издание 2016 г.. Чепмен и Холл. ISBN 978-1482211184.

[3] «Моделирование нарушений когерентности кэша на многоядерных компьютерах» (PDF). Цитировать журнал требует | журнал = (помощь)

[4] Швеция, Мишель Дюбуа, Университет Южной Калифорнии, США, Мурали Аннаварам, Университет Южной Калифорнии, США, Пер Стенстрём, Технологический университет Чалмерса (2012). Параллельная компьютерная организация и дизайн. Кембридж: Издательство Кембриджского университета. ISBN 9781139051224.

[5] Рос, Альберто; Куэста, Блас; Фернандес-Паскуаль, Рикардо; Гомес, Мария Э .; Acacio, Manuel E .; Роблес, Антонио; Гарсия, Хосе М .; Дуато, Хосе (2010). EMC2: расширение согласованности Magny-Cours для крупномасштабных серверов. 17-я Международная конференция по высокопроизводительным вычислениям (HiPC). С. 1–10. Дои:10.1109 / HIPC.2010.5713176. ISBN 978-1-4244-8518-5.

[6] Паттерсон, Джон Л. Хеннесси, Дэвид А. (2011). Компьютерная архитектура: количественный подход (5-е изд.). Сан-Франциско, Калифорния: Морган Кауфманн. ISBN 978-0-12-383872-8.

[:2-7] Hartstein, A .; Srinivasan, V .; Пузак, Т. Р .; Эмма, П. Г. (01.01.2006). Cache Miss Behavior: Is It √2?. Труды 3-й конференции по компьютерным границам. CF '06. С. 313–320. Дои:10.1145/1128022.1128064. ISBN 978-1595933027.

[:1-8] Маттсон, Р.; Gecsei, J .; Slutz, D. R .; Трейгер, я (1970). «Методы оценки иерархий хранения». Журнал IBM Systems. 9 (2): 78–117. Дои:10.1147 / sj.92.0078.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]