Анализ неуспешных обращений к кэшу: различия между версиями

Для определения количества неуспешных обращений к кэшу для задачи с N элементами данных производится анализ использования кэша. Для чтения или записи N элементов данных алгоритм должен совершить £2(N/B) неуспешных обращений к кэшу. Эти неуспешные обращения называются принудительными промахами или промахами по первой ссылке. В задаче организации доступа к нескольким последовательностям с помощью кэш-памяти для заданных значений M и B одной из целей является нахождение наибольшего k, такого, что из N обращений к данным O(N/B) будут неуспешными. Любопытно проанализировать неуспешные обращения к кэшу для важного случая кэша с прямым отображением, а также для общего случая множественно-ассоциативного кэша.

Большое количество алгоритмов было разработано на основе модели внешней памяти [ ], и эти алгоритмы оптимизируют количество передач данных между основной памятью и диском. Представляется естественным использовать эти алгоритмы для минимизации неуспешных обращений к кэшу, но из-за ограниченной ассоциативности кэшей это оказывается не так просто. В модели внешней памяти передача данных находится под контролем программиста, и задача организации доступа к нескольким последовательностям имеет тривиальное решение. Алгоритм просто выбирает k < Me/Be, где Be – размер блока, а Me – объем основной памяти в модели внешней памяти. Для k < Me/Be имеется O(N/Be) обращений к внешней памяти. Поскольку кэши управляются аппаратно, задача становится нетривиальной. Например, рассмотрим случай, когда начальные адреса последовательностей равной длины k > a отображаются на i-й элемент одного и того же множества, а доступ к последовательностям осуществляется в порядке круговой очереди. В кэше со стратегией замены LRU или FIFO все обращения к последовательностям будут неуспешными. Такие патологические случаи можно преодолеть путем рандомизации начальных адресов последовательностей.