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

Степенной закон — это математическое соотношение между двумя величинами, при котором одна из них прямо пропорциональна некоторой степени другой. Степенной закон для промахов в кэше был впервые установлен Ч. К. Чоу в его статье 1974 года: ^[1] подтверждается экспериментальными данными о коэффициентах попаданий при стека обработке Ричардом Мэттсоном в 1971 году. ^[2] Степенной закон промахов кэша можно использовать для сужения размеров кэша до практических диапазонов при условии допустимой частоты промахов в качестве одного из первых шагов при разработке иерархии кэша для однопроцессорной системы . ^[3]

Степенной закон для промахов в кэше можно сформулировать как

M=M_{0}C^{-\alpha }

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

Предостережения

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

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

Хотя конфликтные промахи уменьшаются по мере увеличения ассоциативности , Hartstein et al. ^[4] показал, что степенной закон выполняется независимо от ассоциативности множеств.

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

R(t)=R_{0}t^{-\beta }

где R ( t ) — частота повторных ссылок. Было обнаружено, что показатель степени β находится в пределах от 1,7 до 1,3. Теоретически было доказано, что степенные законы переадресации кэша и частоты промахов кэша связаны уравнением $\alpha =1-\beta$ . Это означает, что для рабочих нагрузок, которые не подчиняются степенному закону повторных ссылок, степенной закон промахов в кэше не выполняется.

Многоуровневая иерархия кэша

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

См. также

Ссылки

^ Чоу, CK (май 1974 г.). «Об оптимизации иерархий хранения». Журнал исследований и разработок IBM . 18 (3): 194–203. дои : 10.1147/rd.183.0194 .
^ Мэттсон, Р. (декабрь 1971 г.). «Оценка многоуровневой памяти». Транзакции IEEE по магнетизму . 7 (4): 814–819. Бибкод : 1971ITM.....7..814M . дои : 10.1109/TMAG.1971.1067237 .
^ Перейти обратно: ^а ^б Солихин, Ян (17 ноября 2015 г.). Основы параллельной многоядерной архитектуры . Чепмен и Холл. ISBN 978-1482211184 .
^ Перейти обратно: ^а ^б ^с ^д Хартштейн, А.; Шринивасан, В.; Пузак, ТР; Эмма, PG (1 января 2006 г.). «Поведение при промахе кэша» . Материалы 3-й конференции по передовым технологиям . CF '06. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 313–320. дои : 10.1145/1128022.1128064 . ISBN 1595933026 . S2CID 17728397 .

[1] Чоу, CK (май 1974 г.). «Об оптимизации иерархий хранения». Журнал исследований и разработок IBM . 18 (3): 194–203. дои : 10.1147/rd.183.0194 .

[2] Мэттсон, Р. (декабрь 1971 г.). «Оценка многоуровневой памяти». Транзакции IEEE по магнетизму . 7 (4): 814–819. Бибкод : 1971ITM.....7..814M . дои : 10.1109/TMAG.1971.1067237 .

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

[:1-4] Перейти обратно: ^а ^б ^с ^д Хартштейн, А.; Шринивасан, В.; Пузак, ТР; Эмма, PG (1 января 2006 г.). «Поведение при промахе кэша» . Материалы 3-й конференции по передовым технологиям . CF '06. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 313–320. дои : 10.1145/1128022.1128064 . ISBN 1595933026 . S2CID 17728397 .

[1]

[2]

[3]

[4]