2.3.5 Стратегии обновления ОП и замещения кэш-памяти

При методах сквозной (прямой) записи, если А∈Teg, то запись выполняется параллельно и в СОЗУ данных кэш-памяти, и в ОП, а при чтении данные выбираются из СОЗУ данных.

С распределением WTWA

Если адрес не принадлежит тегу (кэш-памяти), то и при чтении, и при записи нет необходимости удалять строку из кэш-памяти в ОП, а сразу реализуется процедура замещения кэш-памяти по одной из выбранных стратегий, т.е. из ОП считывается строка и записывается в СОЗУ данных на место строки, назначенной кандидатом на удаление, а в память тегов записывается новый тег считанной строки. Затем требуемое слово записывается или считывается из СОЗУ данных по ранее рассмотренному алгоритму, т.к. А∈Teg или при чтении выполняется запись слова в RgDIO с перехватом.

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

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

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

Без распределения WTNWA

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

Существует несколько модификаций данного метода в зависимости от типа хранимых данных (программ или данных).

Методы обратной записи

При методах обратной записи, если А∈Teg, то запись выполняется только в кэш-память, а при чтении данные выбираются из СОЗУ данных.

Простая обратная запись SWB

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

Данный метод проигрывает в быстродействии, если при замещении строк (А∉Teg) удаляется строка, которая не модифицировалась (не изменялась за время пребывания в кэш-памяти (особенно для программ)).

Флаговая обратная запись FWB

Является развитием предыдущего метода. Каждой строке ставится в соответствие бит флага записи слова в строку w, т.е. в структуру кэш-памяти вводится дополнительная одноразрядная память флагов емкостью, равной числу строк. Параллельно с чтением памяти тегов выполняется чтение памяти флагов. Если А∈Teg и выполняется запись в СОЗУ данных, то параллельно в одноименной ячейке памяти флагов устанавливается бит w=1. Если А∉Teg, то анализируется значение бита флага и процедура удаления строки из кэш-памяти в ОП выполняется только в том случае, если бит w был установлен в "1", иначе данная процедура не выполняется, а сразу производится замещение строки из ОП в кэш-память со сбросом бита w замещаемой строки.

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

Регистровая обратная запись PWB

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

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

Флаговая регистровая обратная запись FPWB

Является комбинацией методов PWB и FWB и не требует дополнительных комментариев.

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

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

Счетчик адресов в качестве кандидата на удаление (КНУ) определяет последовательные ячейки памяти тегов от 0 до N.

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

Методы, учитывающие активность строк, позволяют сократить число промахов при назначении кандидата на удаление из кэш-памяти, а следовательно, и повысить эффективность использования кэш-памяти.

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

Обращение к строке: b d a a abcd ⇒ bacd ⇒ dbac ⇒ adbc ⇒ adbc ⇒

Техническая реализация метода псевдо LRU на основе стека весьма проблематична, т.к. сдвиг информации в стеке выполняется не во всех ячейках, а носит случайный характер. Обычно метод псевдо LRU-стека реализуют на основе управляющего автомата с жесткой логикой. Реализация автомата усложняется по мере увеличения числа строк в кэш-памяти, т.к. число возможных комбинаций расположения данных в LRU (число состояний автомата) в общем случае без минимизации составляет n!, где n число замещаемых строк в кэш-памяти. Для 4 строк получим 4!=24 состояния автомата. Поэтому этот метод используется только при частично-ассоциативном распределении, когда число модулей не превышает 2-4, т.е. LRU имеет глубину 4 (для каждой группы строк (модулей)). Ниже приведен пример графа переходов состояний автомата для LRU-стека глубиной 3.

В ЦП i486 реализован следующий алгоритм замещения строк. Пусть В0, В1 и В2 - код текущего состояния автомата с учетом минимизации, однозначно определяющий номер строки в группе, которая подлежит замещению, а L0, L1, L2 и L3 замещаемые строки в группе строк. При каждом попадании в кэш-память биты состояния В0-В2 модифицируются путем изменения кода состояния. В таблице представлен алгоритм выбора замещаемой строки и формирования функций возбуждения для перехода в следующее состояние. После замещения строки новое состояние автомата заносится в блок LRU.

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

На рисунке 2.13 приведен фрагмент схемы памяти бит достоверности и LRU состояний для кэш-памяти с частично-ассоциативным отображением. Рассмотрим алгоритм работы схемы.

1. При чтении из памяти тегов параллельно по номеру индекса группы строк (поле b) из памяти LRU состояний считываются и загружаются в регистры бит достоверности строк Rgd и состояний RgS автомата содержимое бит достоверности строк данной группы (4 бита) и 3-разрядный код B0-B2 LRU состояния автомата для группы строк подлежащих замещению.
2. Если хотя бы один бит достоверности d=0, то удаление строки из кэш-памяти не производится, а запрашиваемая строка считывается из ОП и записывается в модуль, выбираемый сигналом ~CSi, формируемым с выходов дешифратора DC. После замещения строки в память тегов в одноименный модуль записывается новый тег загруженной строки, а в регистре бит достоверности Rgd устанавливается соответствующий бит. Переход к пункту 4.
3. Если все биты достоверности строк в группе равны "1" и А∉Teg, то на выходе КС1 формируется код (номер) модуля памяти тегов строки, подлежащей замещению в двоичном или унитарном коде и на выходах MS2 формируется сигнал ~CSi выбора модуля из группы. В зависимости от принятой стратегии обновления ОП (сквозная или обратная запись) выполняется процедура удаления выбранной (одной из четырех) строк из кэш-памяти в ОП (при простой обратной записи), а затем процедура замещения затребованной строки из ОП в кэш-память.
4. Выполнить требуемую операцию чтения или записи информации с кэш-памятью и параллельно на выходах КС2 в зависимости от набора входных сигналов ~CSi формируется код следующего состояния автомата, определяющего нового кандидата на замещение, и этот код состояния записывается в RgS, а затем в память LRU состояний параллельно со считанными ранее битами достоверности группы строк. По признаку неиспользования: для каждой строки кэш-памяти вводится бит активности строки, который устанавливается при каждом обращении к строке при чтении или записи в кэш-память. При частично-ассоциативном распределении память бит неиспользования строится по аналогии памяти бит достоверности в предыдущем примере (рисунок 2.13).

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

На рисунке 2.14 приведен пример реализации схемы для полностью ассоциативной кэш-памяти с флагов ой обратной записью и назначением кандидата на удаление по признаку неиспользования. Регистр битов активности можно построить на асинхронных RS-триггерах. Унитарный код, формируемый с выходов схем сравнения АЗУ при ассоциативном поиске, служит источником для установки бита активности по входу Si Rg BN. Биты активности, установленные в "0", определяют строки кэш-памяти, как кандидата на удаление из кэш-памяти в ОП или на замещение.

1. Если А∈Teg, то по адресу, сформированному схемой CD1 или выбираемому из памяти тегов (поле [f]), при выполнении записи в СОЗУ данных параллельно выполняется запись в память флагов кода "1".
2. Если А∉Teg, то по адресу, формируемому схемой CD2, назначается строка в качестве кандидата на удаление из кэш-памяти. По этому адресу из памяти флагов считывается значение бита w в триггер Tw для определения необходимости выполнения процедуры обновления ОП (при Tw=0 обновление ОП не выполняется).
3. Если Tw=1, то по этому же адресу строка считывается из СОЗУ данных и записывается в ОП по адресу RgTeg[a].
4. Из ОП считывается новая строка по адресу из RgФА[a] и загружается на место удаленной строки, а в памяти флагов соответствующий бит w сбрасывается, и параллельно в память тегов загружается новый тег из RgФА. Выполнить пункт 1.

Если в регистре признака неиспользования все биты будут установлены в "1", то произойдет автоматический сброс всех бит Rg BN и подсчет активности строк начинается сначала.

При увеличении емкости кэш-памяти для полностью ассоциативного и секторного распределений биты активности строк можно также хранить в отдельной одноразрядной памяти бит неиспользования, построенной на основе АЗУ. В качестве эталона для сравнения выступает код нуля, а с выходов АЗУ (поле [f]) будет сниматься код адреса строки, подлежащей замещению, если А∉Teg. Однако, такой подход требует значительных аппаратурных затрат и имеет высокую стоимость.

Выбор стратегии замещения тесно связан с реализованным методом распределения кэш-памяти. Например, при прямом распределении кандидат на удаление однозначно определяется номером индекса, метод псевдо LRU-стека и биты неиспользования, как правило, применяется только для частично-ассоциативной кэш-памяти, FIFO - совместно с битом неиспользования для частично-ассоциативного распределения и для полностью ассоциативного или секторного распределений при небольшой емкости АЗУ и т.д.

На рисунках 2.4, 2.5, 2.6, 2.8 и 2.12 на входах ОП показаны схемы мультиплексирования адреса: при сквозной записи операнда в ОП или при выполнении процедуры обновления ОП старшие разряды адреса выбираются из памяти тегов, а остальные в зависимости от метода распределения кэш-памяти (поле [b]) из RgФА и организации расслоения обращений ОП (счетчик слов в строке СТ S). При выполнении процедуры замещения кэш-памяти адрес строки берется из RgФА.

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