Общая среда для иерархий памяти

Какой блок должен быть заменен при промахе обращения к кэш-памяти?

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

Для множественно-ассоциативной и полностью ассоциативной кэш памяти есть іве основные стратегии замены:

♦ Произвольная: блоки-кандидаты выбираются произвольным образом, возможно использование помощи со стороны оборудования. Например, в MIPS поддерживается произвольная замена для промахов при обращениях к TLB.

♦ Замена наименее востребованного элемента (LRUy. заменяется тот блок, который не был востребован длительный период времени.

На практике, LRU — слишком дорогая для реализации стратегия для тех элементов иерархии, степень ассоциативности которых ниже определенного уровня (обычно от двух до четырех), поскольку отслеживание востребованности информации обходится довольно дорого. Даже для четырехканальной ассоциативности, i.RU зачастую имеет приблизительный характер, например отслеживается, какая из двух пар блоков наименее востребована (для чего нужен один бит), а затем отслеживается, какой из блоков в каждой паре наименее востребован (для чего требуется по одному биту на пару).

При более высокой степени ассоциативности используется либо приблизительная стратегия LRU, либо произвольная замена. В кэш-памяти алгоритм замены выполняется оборудованием, из чего следует, что схема должна быть проста в реализации. Произвольная замена довольно легко создается в оборудовании, и для двухканальной ассоциативной кэш-памяти произвольная замена имеет коэффициент промахов примерно в 1,1 раза выше, чем LRU-замена. Чем больше становится кэш-память, тем меньше становится коэффициент промахов для обеих стратегий замены, и абсолютная разница становится незначительной. Фактически, произвольная замена может быть иногда лучше простой приблизительной LRU-замены, которую легче реализовать в оборудовании.