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

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

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

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

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

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

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

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

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

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

Конфликтные промахи [ править ]

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

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

Емкость отсутствует [ править ]

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

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

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

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

Отсутствует согласованность [ править ]

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

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

Покрытие промахов [ править ]

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

Системные промахи [ править ]

Системные действия, такие как прерывания , переключение контекста и системные вызовы, приводят к приостановке процесса и изменению его состояния кэша. Когда выполнение процесса возобновляется, он терпит промахи в кэше, чтобы восстановить измененное состояние кеша. Эти промахи называются системными промахами. ^[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}}$

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

Степенный закон промахов в кэше [ править ]

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

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

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

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

Профиль расстояния стека [ править ]

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

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

$miss=C_{<}A+\sum _{i=A{'}+1}^{A}C_{i}$

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

См. Также [ править ]

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

Заметки [ править ]

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

[1] Перейти ↑ Hennessy, J. and Patterson, D. (2003). Компьютерная архитектура: количественный подход, 3-е издание . ISBN Morgan-Kaufmann Publishers, Inc. 9781558607248.CS1 maint: multiple names: authors list (link)

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

[3] «Моделирование пропусков когерентности кэша на многоядерных компьютерах» (PDF) . Cite journal requires |journal= (help)

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

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

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

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

[:1-8] Mattson, RL ; Gecsei, J .; Slutz, DR; Трейгер, я (1970). «Методы оценки иерархий хранения». IBM Systems Journal . 9 (2): 78–117. DOI : 10.1147 / sj.92.0078 .

[1]