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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Промахи покрытия

Группа промахов кэша 4Cs может быть расширена до 5Cs , если многопроцессорная система включает в себя каталог согласованности, организованный как кэш, т. е. который может заменять записи. Пятый C означает покрытие. ^[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^{-\alpha }$

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

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

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

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

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

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

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

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

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

Примечания

^ Хеннесси, Дж. и Паттерсон, Д. (2003). Компьютерная архитектура: количественный подход, 3-е издание . ISBN Morgan-Kaufmann Publishers, Inc. 9781558607248.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ abcd Солихин, Ян (17 ноября 2015 г.). Основы параллельной многоядерной архитектуры, издание 2016 г. Чепмен и Холл. 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-е изд.). Сан-Франциско, Калифорния: Морган Кауфманн. ISBN 978-0-12-383872-8.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Хартштейн, А.; Шринивасан, В.; Пузак, ТР; Эмма, PG (1 января 2006 г.). «Поведение промаха кэша». Материалы 3-й конференции по передовым технологиям . CF '06. стр. 313–320. дои : 10.1145/1128022.1128064. ISBN 978-1595933027. S2CID 17728397.
^ Мэттсон, РЛ ; Гечеи, Дж.; Слуц, ДР; Трейгер, я (1970). «Методы оценки иерархий хранения». IBM Systems Journal . 9 (2): 78–117. дои : 10.1147/sj.92.0078.