Алгоритмы замещения информации

Алгоритм замены данных в кэш-памяти существенно влияет на ее эффективность. Алгоритм должен, во-первых, быть максимально быстрым, чтобы не замедлять работу кэш-памяти, а во-вторых, обеспечивать максимально возможную вероятность кэш-попаданий. Поскольку из-за непредсказуемости вычислительного процесса ни один алгоритм замещения данных в кэш- памяти не может гарантировать идеальный результат, разработчики ограничиваются рациональными решениями, которые по крайней мере, не сильно замедляют работу кэш. Наличие в ЭВМ двух копий данных - в основной памяти и в кэш -

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

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

Обратная запись (write back). Аналогично, при возникновении запроса к памяти выполняется просмотр кэш, и если строка с запрашиваемым адресом там отсутствует, то запись выполняется только в основную память. В противном же случае запись производится только в кэш-память, при этом в поле управления делается специальная отметка (признак модификации), которая указывает на то, что при вытеснении этих данных из кэш необходимо переписать их в подходящий момент в основную память, чтобы обновить устаревшее содержимое основной памяти. Очевидно, что в этом случае в соответствии с принципами временной и пространственной локальности, обращения будут происходить преимущественно к кэш-памяти, а малая их доля упадёт на основную память. Поэтому временная эффективность метода обратной записи высокая, хотя требует применения более сложных алгоритмов согласования данных. Контроллер кэш-памяти осуществляет копирование модифицированной строки при любых замещениях строки. Модифицированные данные могут выгружаться не только при освобождении места в кэш-памяти для новых данных, но и в «фоновом режиме», то есть в промежутках, когда шинный интерфейс не занят процессором или другими устройствами. В некоторых алгоритмах замещения предусматривается первоочередная выгрузка модифицированных, или, как еще говорят, «грязных» данных.

Когда кэш-память заполнена, занесение в нее нового блока связано с замещением содержимого одной из строк. При прямом отображении каждому блоку основной памяти соответствует только одна определенная строка в кэш-памяти, и никакой иной выбор удаляемой строки здесь невозможен. При полностью и частично ассоциативных способах отображения требуется какой-либо алгоритм замещения (выбора удаляемой из кэш-памяти строки). Основная цель стратегии замещения — удерживать в кэш-памяти строки, к которым наиболее вероятны обращения в ближайшем будущем, и заменять строки, доступ к которым произойдет в более отдаленном времени или вообще не случится. Очевидно, что оптимальным будет алгоритм, который замещает ту строку, обращение к которой в будущем произойдет позже, чем к любой другой строке кэша. К сожалению, такое предсказание практически нереализуемо, и приходится использовать алгоритмы, уступающие оптимальному. Существует множество алгоритмов замещения, которые кратко рассмотрены ниже:

Наиболее эффективным является алгоритм замещения на основе наиболее давнего использования (LRU — Least Recently Used), при котором замещается та строка кэш-памяти, к которой дольше всего не было обращения. Общая реализация производит отслеживание наименее использованной строки. Этот алгоритм реализуется путем добавления дополнительных бит «возраста», а отслеживание сделано при помощи сравнения этих бит.

Алгоритм замещения на основе наименее давнего использования (MRU - Most Recently Used), в отличие от LRU, в первую очередь вытесняется последний использованный элемент. Для схем случайного доступа и циклического сканирования больших наборов данных (схемы циклического доступа), алгоритмы кэширования MRU – имеют больше попаданий по сравнению с LRU за счет из стремления к сохранению старых данных. Алгоритмы MRU наиболее полезны в случаях, когда чем старше элемент, тем больше обращений к нему происходит. [20]

Сегментированный LRU (SLRU – Segmented LRU) – SLRU кэш состоит из двух секций: пробной и защищенной. Пробная секция реализована по алгоритму LRU, защищенная - по алгоритму MRU. При промахе, данные сначала поступают в пробную секцию. Из этой секции, в результате редкого использования данные попадают в защищенную секцию. Такой перенос строки из пробного сегмента в защищенный сегмент может вызвать перенос последней использованной (LRU) строки в защищенном сегменте в MRU-область пробного сегмента, давая этой линии второй шанс быть использованной перед вытеснением.

Кэш прямого отображения (Direct-mapped cache) используется для высокоскоростных кэшей процессора, где не хватает быстродействия 2-канального ассоциативного кэширования. Адрес нового элемента используется для вычисления местонахождения в кэше (в отведенной для этого области). Все, что было ранее, — вытесняется.

Другой возможный алгоритм замещения-алгоритм, работающий по принципу «первый вошел-первый вышел»(FIFO-First In-First Out). Здесь заменяется строка, дольше всего находившаяся в кэш-памяти.

Виртуальная (от virtual - "кажущийся") память (ВП) - это система организации памяти, при которой процессору (программе) предоставляется адресное пространство, превышающее физическое адресное пространство ОЗУ системы за счет внешней памяти. Задачей построения ВП является сведение к минимуму потерь производительности при вынужденном обращении к внешней памяти. ВП может быть организована программно, программно - аппаратно и аппаратно. Как правило, в современных ВС программно-аппаратная организация ВП заключается в использовании операционной системой аппаратной поддержки ВП, заложенной в процессорах общего назначения.

ВП может иметь страничную, сегментную или странично–сегментную организацию. При страничной организации память представляется совокупностью страниц фиксированной длины (2-16 Кбайт). При сегментной организации память представляет собой набор сегментов, то есть логически связанных блоков памяти различного размера.

Методы распределения памяти не требуют непрерывных областей пространства для размещения задачи, но они требуют для реализации соответствующей аппаратной поддержки в виде относительной адресации. При такой адресации адрес программы состоит из двух частей – базового адреса (фактический адрес начала размещения программы в памяти) и смещения (множества адресов ячеек программы, отсчитываемого от базового адреса).