Организация ЭВМ и систем

         

Методы замещения строк кэш-памяти


Способ определения строки, удаляемой из кэш-памяти, называется стратегией замещения. Для замещения строк кэш-памяти существует не­сколько методов: метод замещения наиболее давнего по использованию объ­екта — строки, метод LRU (замещение наименее используемой информации);

метод FIFO (первым пришёл — первым вышел) и метод произвольного за­мещения.. В первом случае среди строк, являющихся объектами замещения, выбирается строка, к которой наиболее длительное время не было обраще­ний. По методу FIFO среди всех строк, являющихся объектами замещения, выбирается та, которая самой первой была переслана в кэш-память. И нако­нец, по последнему методу строка выбирается произвольно. Реализация этих методов упрощается в указанной последовательности, но наибольшим эф­фектом обладает метод замещения наиболее давнего по использованию объ­екта (строки).

Для реализации этого метода необходимо манипулировать строками, ко­торые являются объектами замещения, с помощью LRU-стека. При каждой загрузке в этот стек помещается строка, в результате чего при замене исполь­зуется строка, хранящаяся в наиболее глубокой позиции стека, и эта строка удаляется из стека. При доступе к строке, которая уже содержится в LRU-стеке, эта строка удаляется из стека и заново загружается в него. Стек типа LRU устроен таким образом, что, чем дольше к строке не было доступа, тем в более глубокой позиции она располагается. Реализация стека типа LRU, по­зволяющего с высокой скоростью выполнять такую операцию, усложняется

по мере увеличения числа строк.

По методу частично ассоциативного распределения число строк в каж­дом стеке LRU равно числу строк в одной группе, и так как это число мало (порядка 2 - 4), то для каждой группы необходимо использовать свой стек. Если число групп сравнительно велико, то оснащение каждой из них стеко­вым механизмом приводит к повышению стоимости.



Содержание раздела