Алгоритм замещения строк в КЭШ памяти.

Среднее время доступа к КЭШ памяти можно определить следующим образом:

t_ср = t_обр + Р_пр * t_пр,

где:

t_обр - время обращения при попадании;

Р_пр - потери времени при промахе;

t_пр – вероятность промаха.

Из приведенной формулы видно, что для уменьшения среднего времени доступа t_ср к КЭШ необходимо уменьшить потери времени при промахе, время обращения при попадании и вероятность промахов. При увеличении объема КЭШ памяти вероятность промахов как правило уменьшается. Кроме объема КЭШ памяти на вероятность промахов влияет так же и алгоритм замещения строк КЭШа. Наиболее простой алгоритм замещения используется в КЭШ памяти с прямым отображением, когда замещается та строка, к которой было неудачное обращение (КЭШ промах). Этот алгоритм имеет простое аппаратное решение и существенный недостаток, который ведет к увеличению вероятности промахов, если две строки ОЗУ, претендующих на одну и ту же строку КЭШа, используются одинаково часто.

В полностью ассоциативной и множественно ассоциативной КЭШ памяти имеется возможность использовать более сложные алгоритмы замещения, которые позволяют устранить недостаток организации КЭШа с прямым отражением. На практике наиболее часто используются случайные и LRU алгоритмы замещения строк памяти.

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

В алгоритме LRU удаляется из КЭШ памяти та строка, которая дольше всех не использовалась. Least – Recently Used (LRU) – это алгоритм, имеющий более сложную аппаратную реализацию, поскольку необходимо фиксировать все обращения к строкам для определения той строки, к которой дольше всех не было обращения.

При увеличении объема КЭШ памяти алгоритм LRU становится все более сложным и дорогим, а главное, не позволяет существенно снизить вероятность промахов по сравнению со случайным алгоритмом. Уже при объеме КЭШ памяти 256 кБ, алгоритм LRU практически не имеет преимуществ по сравнению со случайным алгоритмом, и поэтому при больших размерах КЭШа не используется, а используется случайный алгоритм.