24 Алгоритмы свопинга и замещения информации в КЭШе

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

Запись в кэш-память может быть осуществлена из двух источников:

· Из процессора.

· Из ОП.

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

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

Наиболее эффективным является алгоритм замещения на основе наиболее давнего использования (LRU — Least Recently Used), при котором замещается та строка кэш-памяти, к которой дольше всего не было обращения. Наиболее известны три способа аппаратурной реализации этого алгоритма. В первом из них с каждой строкой кэш-памяти ассоциируют счетчик. К содержимому всех счетчиков через определенные интервалы времени добавляется единица. При обращении к строке ее счетчик обнуляется. Таким образом, наибольшее число будет в счетчике той строки, к которой дольше всего не было обращений, и эта строка — первый кандидат на замещение. Второй способ реализуется с помощью очереди, куда в порядке заполнения строк кэш-памяти заносятся ссылки на эти строки. При каждом обращении к строке ссылка на нее перемещается в конец очереди. В итоге первой в очереди каждый раз оказывается ссылка на строку, к которой дольше всего не было обращений. Именно эта строка прежде всего и заменяется. Оба способа дают наиболее адекватную оценку, но цена этому является привлечения большого количества дополнительной памяти (либо на хранение счётчиков, либо на поддержание и хранение очереди). Последний вариант, даёт приближённую оценку, но крайне не требовательный с  точки зрения памяти. Он заключается в том, что с каждой записью ассоциировано два бита, обозначим их W и A. Бит W, будем называть битом когерентности с ОП.  Изначально бит W устанавливается в 0. Как только процессор  модифицирует в ассоциированные с флагом данные, то этот бит устанавливается в 1. Использование бита W позволяет выявить те слова в кэше, которые не были модифицированы процессором, а следовательно и копирования их в ОП, при замещении блоков не требуется. Этот подход является основой для алгоритма флаговой обратной записи, рассмотренного ниже. Бит А, устанавливается в 1, как только происходит обращение к блоку. Причем как только биты А, всех блоков установлены в 1, то все они сбрасываются на 0, кроме того, который инициировал данное событие.  Замещение идёт в блок , у которого A и W установлены в 0. То есть обращения к данному блоку со стороны процессора не было после копирования блока в кэш. В случае если таких флагом нет, то алгоритмически выгодно, выбрать блоки с битом W установленным в 0. Так как при этом не нужно будет обновлять данные в ОП. Как видно третий случай самый экономичный с точки зрения памяти, но даёт результат менее адекватный по отношению к предыдущим случаям. То есть может произойти замена блока, к которому часто происходят запросы на операцию чтения, но его биты A и W установлены в 0.  

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

Еще один алгоритм — замена наименее часто использовавшейся строки (Lr и Least Frequently Used). Заменяется та строка в кэш-памяти, к которой было меньше всего обращений. Принцип можно воплотить на практике, связав каждую строку со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик которой содержит наименьшее число.

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

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

Для разрешения первой из рассмотренных ситуаций (когда процессор выполняет операцию записи) в системах с кэш-памятью предусмотрены методы обновления основной памяти, которые можно разбить на две большие группы: метод сквозной записи (write through) и метод обратной записи (write back).

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

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

Определенный выигрыш дает его модификация, известная как метод буферированной сквозной записи. Информация сначала записывается в кэш-память и в специальный буфер, работающий по схеме FIFO. Запись в основную память производится уже из буфера, а процессор, не дожидаясь ее окончания, может сразу же продолжать свою работу. Конечно, соответствующая логика управления должна заботиться о том, чтобы своевременно «опустошать» заполненный буфер. При использовании буферизации процессор полностью освобождается от работы с ОП. Согласно методу обратной записи, слово заносится только в кэш-память. Если соответствующей строки в кэш-памяти нет, то нужный блок сначала пересылается из ОП, после чего запись все равно выполняется исключительно в кэш-память, При замещении строки ее необходимо предварительно переслать в соответствующее место основной памяти. Для метода обратной записи, в отличие от алгоритма сквозной записи, характерно то, что при каждом чтении из основной памяти осуществляются две пересылки между основной и кэш-памятью. У рассматриваемого метода есть разновидность — метод флаговой обратной записи. Когда в какой-то строке кэша производится изменение, устанавливается связанный с этой строкой бит изменения A (флажок). При замещении строка из кэш- памяти переписывается в ОП только тогда, когда ее флажок установлен в 1. Ясно, что эффективность флаговой обратной записи несколько выше. Таким образом, первым кандидатом на замещения являются блоки у которых бит активности установлен в 0, так как не требуется копирования содержимого КЭШа в ОП.

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