Алгоритмы синхронизации памяти и кэша

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

сквозная запись WT (Write Through) и

обратная запись WB (Write Back).

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

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

Архитектуры Кэш- памяти

В зависимости от способа определения взаимного соответствия строки кэша и области основной памяти различают три архитектуры кэш-памяти:

Ÿ кэш прямого отображения (direct-mapped cache),

Ÿ полностью ассоциативный кэш (fully associative cache);

Ÿ частично - или наборно-ассоциативный кэш (set-associative cache)- комбинация первых двух.

Кэш прямого отображения

В кэш-памяти прямого отображения адрес памяти, по которому происходит обращение, однозначно определяет строку кэша, в которой может находиться требуемый блок. Принцип работы такого кэша поясним на примере несекторированного кэша объемом 256 Кбайт с размером строки 32 байта и объемом кэшируемой основной памяти 64 Мбайт — типичный кэш системной платы для Pentium. Струк­туру памяти в такой системе иллюстрирует рисунок 3.25. Кэшируемая основная память условно разбивается на страницы (в данном случае по 256 Кбайт), размер которых совпадает с размером кэш-памяти (256 Кбайт).

Кэш память (и, условно, страницы основной памяти) делятся на строки (256 Кбайт/32 = 8 Кбайт строк). Архитектура прямого отображения подразумевает, что каждая строка кэша может отображать из любой страницы кэшируемой памяти только соответствующую ей строку (на рисунке они находятся на одном горизонтальном уровне). Поскольку объем основной памяти много больше объема кэша, на каждую строку кэша может претендовать множество блоков памяти с одинаковой младшей частью адреса (смещением внутри страницы). Одна строка в определенный момент может, естественно, содержать копию только одного из этих блоков.

Рисунок 3. 25 – Кэш прямого отображения

 

Строка n

 

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

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

Независимо от объема затребованных данных в кэш из основной памяти строка переписывается вся целиком (поскольку признак действительности относится ко всем ее байтам). Если контроллер кэша реализует упреждающее считывание (read ahead), то в последующие свободные циклы шины также обновится и следующая строка (если она была чистой). Чтение «про запас» позволяет при необходимости осуществлять пакетный цикл чтения из кэша через границу строки.

Такой кэш имеет самую простую аппаратную реализацию и применяется во вторичном кэше большинства системных плат. Однако ему присущ серьезный недостаток, вполне очевидный при рассмотрении рис. 6.х. Если в процессе выполнения программы процессору поочередно будут требоваться блоки памяти, смещенные относительно друг друга на величину, кратную размеру страницы (на рисунке эти блоки расположены на одной горизонтали в разных страницах), то кэш будет работать интенсивно, но вхолостую (cache trashing). Очередное обра­щение будет замещать данные, считанные в предыдущем и необходимые в следу­ющем обращении, — то есть будет сплошная череда кэш-промахов. Переключение страниц в многозадачных ОС также снижает количество кэш-попаданий, что отражается на производительности системы. Увеличение размера кэша при сохранении архитектуры прямого отображения даст не очень существенный эффект, поскольку разные задачи будут претендовать на одни и те же строки кэша. Не увеличивая объема, можно повысить эффективность кэширования изменением структуры кэша, о чем пойдет речь ниже.

Объем кэшируемой памяти (М_коп) при архитектуре прямого отображения оп­ределяется объемом кэш-памяти (V_кэш) и разрядностью памяти тегов (N):

М_кэшоп = V_кэш 2^N, в нашем случае М_кэшоп = 256 Кбайт х 2⁸ = 64 Мбайт.

Наборно-ассоциативный кэш

Наборно-ассоциативная архитектура кэша позволяет каждому блоку кэшируемой памяти претендовать на одну из нескольких строк кэша, объединенных в набор (set). Можно считать, что в этой архитектуре есть несколько параллельно и согласованно работающих каналов прямого отображения, где контроллеру кэша приходится принимать решение о том, в какую из строк набора помещать очередной блок данных. В простейшем случае каждый блок памяти может помещаться в одну из двух строк (Two Way Set-Associative Cache — двухканальный наборно – ассоциативный кэш). Такой кэш должен содержать два банка памяти тегов. Номер набора (индекс), в котором может отображаться затребованный блок данных, однозначно определяется средней частью адреса (как номер строки в кэше прямого отображения). Строка набора, отображающая требуемый блок, определяется сравнением тегов (как и в ассоциативном кэше), параллельно выполняемым для всех каналов кэша. Кроме того, с каждым набором должен быть связан признак, определяющий строку набора, подлежащую замещению новым блоком данных в случае кэш-промаха (на рисунке 3.26 в ее сторону указывает стрелка). Кандидатом на замещение обычно выбирается строка, к которой дольше всего не обращались (алгоритм LRU — Least Recently Used). При относительно большом количестве каналов (строк в наборе) прибегают к некоторому упрощению — алгоритм Pseudo-LRU для четырех строк (Four Way Set Associative Cache) позволяет принимать решения, используя всего 3 бита.

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

Рисунок 3.26 – Двухканальный наборно – ассоциативный кэш

 

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

Ассоциативный кэш

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

Лекция 12

Тема 3.7 Микроконтроллеры

План лекции

– Организация ввода/вывода в вычислительной системе

– Программная модель внешнего устройства

– Состав и функции микросхем системной поддержки

– Северный мост

– Южный мост

– Super I/O

– Hub-архитектура

– Контроллер прямого доступа к памяти:

регистр команд;

блок управления режимом;

схема взаимодействия устройств.

– Тенденции развития

Основная часть лекции

⇐ Предыдущая13141516171819202122Следующая ⇒

Поделиться:

Популярное:

1. Алгоритмы записи произвольной функции, заданной в таблице в виде с помощью элементарных функций.
2. Алгоритмы и модели компоновки
3. Алгоритмы многокритериальной оптимизации.
4. Алгоритмы обновления содержимого заполненных строк, снуппинг
5. Алгоритмы проведения парентеральных манипуляций
6. БЛОК 1. ИССЛЕДОВАНИЕ ОСОБЕННОСТЕЙ ПАМЯТИ, ВНИМАНИЯ И РАБОТОСПОСОБНОСТИ
7. ВИДЫ ПАМЯТИ И ИХ ОСОБЕННОСТИ
8. Другие методы синхронизации.
9. Индивидуальные особенности памяти
10. ИНДИВИДУАЛЬНЫЕ РАЗЛИЧИЯ ПАМЯТИ У ЛЮДЕЙ
11. Индивидуальные различия памяти.