Степенной закон промахов в кэше - Power law of cache misses
 | Эта статья нужно больше ссылки на другие статьи помочь интегрировать в энциклопедию. (Октябрь 2016) (Узнайте, как и когда удалить этот шаблон сообщения) |
А сила закона представляет собой математическое соотношение между двумя величинами, в котором одна прямо пропорциональна некоторой степени другой. В степенной закон для промахов в кэше был впервые установлен К. К. Чоу в его статье 1974 г.,[1] подтверждены экспериментальными данными по коэффициентам попаданий для обработки стека Ричард Мэттсон в 1971 г.[2] Степенный закон промахов в кэше можно использовать для сужения размеров кеш-памяти до практических диапазонов, учитывая допустимую частоту промахов, как один из первых шагов при разработке иерархия кеша для однопроцессорной системы.[3]
Степенной закон для промахов кэша можно сформулировать как
куда M частота промахов для кэша размером C и M0 это частота промахов базового кэша. Показатель α зависит от рабочей нагрузки и обычно составляет от 0,3 до 0,7.[4]
Предостережения
Степенной закон может дать оценку частоты промахов только до определенного значения размера кэша. Достаточно большой кэш исключает пропуски емкости, а дальнейшее увеличение размера кеша не приведет к дальнейшему снижению частоты промахов, вопреки предсказанию закона мощности.[3]
Достоверность степенного закона промахов в кэше также зависит от размера рабочей памяти, установленной в данном процессе, а также от временного шаблона повторной ссылки блоков кеша в процессе. Если процесс имеет небольшой набор рабочей памяти по сравнению с размером кэша, пропуск емкости маловероятен, и степенной закон не выполняется.
Хотя количество случаев конфликта уменьшается по мере увеличения ассоциативности, Hartstein et al.[4] показал, что степенной закон выполняется независимо от ассоциативности множества.
Hartstein et al. построили график числа повторных обращений к блоку кеша в зависимости от времени их повторного обращения для большого количества рабочих нагрузок и обнаружили, что большинство из них также имеют экспоненциальную зависимость.[4]
куда р(т) - это скорость реферирования. Оказалось, что показатель степени β колеблется от 1,7 до 1,3. Теоретически было доказано, что степенные законы переориентации кэша и частоты промахов кэша связаны уравнением . Это означает, что для рабочих нагрузок, которые не соблюдают степенной закон повторной ссылки, степенной закон промахов кэша не выполняется.
Многоуровневая иерархия кеша
В многоуровневой иерархии кэша шаблон промахов кэша более высокого уровня становится шаблоном повторной ссылки кэша непосредственного более низкого уровня. Hartstein et al.[4] Было обнаружено, что в то время как промахи в кэше для более низких уровней не подчиняются строгому степенному закону, до тех пор, пока кэш нижнего уровня значительно больше, чем кэш более высокого уровня, функция частоты промахов может быть аппроксимирована степенным законом.
Смотрите также
Рекомендации
- ^ Чоу, К. К. (май 1974 г.). «Об оптимизации иерархии хранения». Журнал исследований и разработок IBM. 18 (3): 194–203. Дои:10.1147 / rd.183.0194.
- ^ Маттсон, Р. (декабрь 1971 г.). «Оценка многоуровневых воспоминаний». IEEE Transactions on Magnetics. 7 (4): 814–819. Дои:10.1109 / TMAG.1971.1067237.
- ^ а б Солихин, Ян. Основы параллельной многоядерной архитектуры. Чепмен и Холл. ISBN 978-1482211184.
- ^ а б c d Hartstein, A .; Srinivasan, V .; Пузак, Т. Р .; Эмма, П. Г. (01.01.2006). "Поведение мисс из кеша: это √2?". Труды 3-й конференции по компьютерным границам. CF '06. Нью-Йорк, Нью-Йорк, США: ACM: 313–320. Дои:10.1145/1128022.1128064. ISBN 1595933026.