4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 26: | Строка 26: | ||
Для определения количества неуспешных обращений к кэшу для задачи с N элементами данных производится анализ использования кэша. Для чтения или записи N элементов данных алгоритм должен совершить | Для определения количества неуспешных обращений к кэшу для задачи с N элементами данных производится анализ использования кэша. Для чтения или записи N элементов данных алгоритм должен совершить <math>\Omega(N/B)</math> неуспешных обращений к кэшу. Эти неуспешные обращения называются ''обязательными промахами'' или ''промахами по первой ссылке''. В задаче организации доступа к нескольким последовательностям с помощью кэш-памяти для заданных значений M и B одной из целей является нахождение наибольшего k, такого, что из N обращений к данным O(N/B) будут неуспешными. Любопытно проанализировать неуспешные обращения к кэшу для важного случая кэша с прямым отображением, а также для общего случая множественно-ассоциативного кэша. | ||
Большое количество алгоритмов было разработано на основе модели внешней памяти [ ], и эти алгоритмы оптимизируют количество передач данных между основной памятью и диском. Представляется естественным использовать эти алгоритмы для минимизации неуспешных обращений к кэшу, но из-за ограниченной ассоциативности кэшей это оказывается не так просто. В модели внешней памяти передача данных находится под контролем программиста, и задача организации доступа к нескольким последовательностям имеет тривиальное решение. Алгоритм просто выбирает k < | Большое количество алгоритмов было разработано на основе модели внешней памяти [9], и эти алгоритмы оптимизируют количество передач данных между основной памятью и диском. Представляется естественным использовать эти алгоритмы для минимизации неуспешных обращений к кэшу, но из-за ограниченной ассоциативности кэшей это оказывается не так просто. В модели внешней памяти передача данных находится под контролем программиста, и задача организации доступа к нескольким последовательностям имеет тривиальное решение. Алгоритм просто выбирает <math>k \le M_e/B_e</math>, где <math>B_e</math> – размер блока, а <math>M_e</math> – объем основной памяти в модели внешней памяти. Для <math>k \le M_e/B_e</math> имеется <math>O(N/B_e)</math> обращений к внешней памяти. Поскольку кэши управляются аппаратно, задача становится нетривиальной. Например, рассмотрим случай, когда начальные адреса последовательностей равной длины k > a отображаются на i-й элемент одного и того же множества, а доступ к последовательностям осуществляется в порядке круговой очереди. В кэше со стратегией замены LRU или FIFO все обращения к последовательностям будут неуспешными. Такие патологические случаи можно преодолеть путем рандомизации начальных адресов последовательностей. | ||
правка