Алгоритмы замещения строк кэш-памяти

Лабораторная работа №5

Тема: Алгоритмы замещения строк кэш-памяти.

Цель: проверка работы различных алгоритмов замещения при различных режимах записи.

Время выполнения: 2 часа.

Теоретические сведения

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

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

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

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

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

Процесс замещения при промахе

Промах – это событие, которое наступает в случае обращения к памяти по чтению, при котором требуемые данные отсутствуют в СОП.

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

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

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

-            Случайная - заменяется случайно выбранная строка;

-            FIFO–Firstin,firstout– заменяется строка, записанная в кэш раньше остальных;

-            LRU – Leastrecentlyused- заменяется строка, к которой дольше всего не было обращений;

-            LFU-Leastfrequentlyused- заменяется строка,cнаименьшей частотой обращения.

Запись в кэш-память

Организация кэш-памяти может отличаться и стратегией выполнения записи. Когда выполняется запись в кэш-память имеются две базовые возможности:

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

-            запись с обратным копированием (write back, copy back, store in) - информация записывается только в блок кэш-памяти. Модифицированный блок кэш-памяти записывается в основную память, только когда он замещается.

Для сокращения частоты копирования блоков при замещении обычно с каждым блоком кэш-памяти связывается так называемый бит модификации (dirty bit). Этот бит состояния показывает, был ли модифицирован блок, находящийся в кэш-памяти. Если он не модифицировался, то обратное копирование отменяется, поскольку более низкий уровень памяти (например, ОП) содержит ту же самую информацию, что и кэш-память.

Программная модель кэш-памяти учебной эвм

Конкретная реализация кэш-памяти в описываемой программной модели показана на рис. 3.

Кэш-память содержит N ячеек (в модели N может выбираться из множества {4, 8, 16, 32}), каждая из которых включает трехразрядное поле тега (адреса ОЗУ), шестиразрядное поле данных и три однобитовых признака (флага):

-            Z— признак занятости ячейки;

-            U— признак использования;

-            W— признак записи в ячейку.

Таким образом, каждая ячейка кэш-памяти может дублировать одну любую ячейку ОЗУ, причем отмечается ее занятость (в начале работы модели все ячейки кэш-памяти свободны, "Z, = 0 ), факт записи информации в ячейку во время пребывания ее в кэш-памяти, а также использование ячейки (т. е. любое обращение к ней).

Рисунок 3 – Структура модели кэш-памяти

Текущее состояние кэш-памяти отображается на экране в отдельном окне в форме таблицы, причем количество строк соответствует выбранному числу ячеек кэш. Столбцы таблицы определяют содержимое полей ячеек, например, так, как показано в табл. 10.

Таблица 10

Пример текущего состояния кэш-памяти

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

Напомним, что при сквозной записи при кэш-попадании в процессорных циклах записи осуществляется запись как в ячейку кэш-памяти, так и в ячейку ОЗУ, а при обратной записи — только в ячейку кэш-памяти, причем эта ячейка отмечается битом записи (W:= 1). При очистке ячеек, отмеченных битом записи, необходимо переписать измененное значение ноля данных в соответствующую ячейку ОЗУ.

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

В модели реализованы три различных алгоритма замещения строк:

-            случайное замещение, при реализации которого номер ячейки кэш-памяти выбирается случайным образом;

-            бит использования, случайный выбор осуществляется только из тех ячеек, которые имеют нулевое значение флага использования;

-            очередь (LRU), при которой выбор замещаемой ячейки определяется временем пребывания ее в кэш-памяти/

Напомним, что бит использования устанавливается в 1 при любом обращении к ячейке, однако, как только все биты U установятся в 1, все они тут же сбрасываются в 0, так что в кэш всегда ячейки разбиты на два непересекающихся подмножества по значению бита U— те, обращение к которым состоялось относительно недавно (после последнего сброса вектора U) имеют значение U= 1, иные — со значением U= 0 являются "кандидатами на удаление" при использовании алгоритма замещения "бит использования".

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

Задания к лабораторной работе

Задание 1. Выполнить задание, представленное некоторой короткой "программой" (табл. 10), которую необходимо выполнить с подключенной кэш-памятью (размером 4 и 8 ячеек) в шаговом режиме для следующих двух вариантов алгоритмов замещения указанных в (табл. 11). Номер задания определяется номером варианта.

Таблица 11

Варианты задания:

* Напомним, что программа определяется как последовательность команд, выполнение которых позволяет получить некоторый результат.

Таблица 12

Пояснения к вариантам задания:

Где: СЗ – случайное замещение запись; О – очередь; БИ – бит использования.

Задание 2. Ввести в модель учебной ЭВМ текст своего варианта программы (табл. 12), ассемблировать его и сохранить на диске в виде txt-файла. Установить параметры кэш-памяти размером 4 ячейки, выбрать режим записи и алгоритм замещения в соответствии с первой строкой своего варианта из табл. 11. В шаговом режиме выполнить программу, фиксируя после каждого шага состояние кэш-памяти.

Контрольные вопросы:

1)       Что такое кэш-память? Для чего она используется?

2)       Каков принцип работы кэш-памяти?

3)       Где находятся в BIOS настройки кэш-памяти?

Скачано с www.znanio.ru