Лекция 8. 4.3 Кэш с прямым отображением

4.3 Кэш с прямым отображением

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

1) определение, в какое из подмножеств адресов основной памяти попадает адрес строки, выработанный процессором;

2) обращение к единственной соответствующей строке и сравнение ее тега с адресом от центрального процессора для определения, является ли эта строка искомой.

На рис. 27. приведен пример структуры кэш-памяти с прямым отображением. Для простоты на нем представлена ОП, содержащая 16 строк данных, и кэш-память объемом в четыре строки.

Р и с. 27. Кэш-память с прямым отображением

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

Все строки основной памяти, имеющие S одинаковых младших разрядов, объединяются в подмножества, которые могут отображаться в строке кэша с индексом, равным коду этих разрядов. В нашем примере индекс образуют два младших разряда. Следовательно, например, строки 1, 5, 9 и 13 могут находиться только в строке кэша с индексом 01 и ни в какой другой.

В общем случае, если разрядность адреса ОП равна N, а разрядность индекса – n, то адресные теги содержат оставшиеся N-n разрядов адреса строки.

Преимущество кэш-памяти с прямым отображением в простоте организации и низкой стоимости.

Основной недостаток такой памяти - ограниченное число комбинаций строк в кэше, что приводит к увеличению процента кэш-промахов. Например, строки 5 и 9 не могут одновременно находиться в кэш-памяти, даже если есть свободные места в строках с другими индексами.

4.4. Полностью ассоциативный кэш

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

При кэш-попадании найденная строка считывается в шину данных ШД. При кэш-промахе происходит замещение строки в кэш на требуемую, находящуюся в ОП.

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

4.5. Множественно-ассоциативный кэш

Этот вид памяти является промежуточным между двумя рассмотренными выше. В нем сочетаются простота кэша с прямым отображением и скорость ассоциативного поиска.

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

Р и с. 28. Полностью ассоциативная кэш-память

Рассмотрим пример кэш-памяти с двумя подмножествами (рис. 29).

Если 2 ⁿ строк кэша разбивается на 2 ^s непересекающихся подмножеств, то S младших разрядов оперативной памяти показывают, в каком из подмножеств (индексов) должен вестись ассоциативный поиск. Старшие n-s разрядов адреса основной памяти являются тегами. Для рисунка 29 имеем S =1.

Физический адрес 1011, выработанный процессором, разделяется на индекс 1, равный младшему разряду, и тег 101. По индексу выбирается второе подмножество строк в кэш-памяти, а затем происходит ассоциативный поиск среди тегов строк выбранного подмножества. Найденная строка 11 с тегом 101 передается в шину данных ШД. Ассоциативный поиск производится одновременно по всем тегам с помощью комбинационных схем сравнения СС1 и СС2.

Рис. 29. Множественно-ассоциативная кэш-память

4.6 Дисковая кэш-память

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

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

b) используется отдельная дисковая кэш-память объемом от 8 до 64 Мбайт.

Во втором случае контроллер дисковой кэш-памяти пересылает между ОП и винчестером части файлов, содержащие сектора или дорожки диска.

Устройства чтения CD/DVD/BD-дисков также кэшируют прочитанную информацию для ускорения повторного обращения.

Применение кэширования внешних накопителей обусловлено следующими факторами:

a) скорость доступа процессора к оперативной памяти во много раз больше, чем к памяти внешних накопителей;

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

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

4.7 Буфер ассоциативной трансляции

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

Для ускорения в процессоре организуется специальная ассоциативная кэш-память TLB – Translation Look-aside Buffer. Взаимодействие TLB с процессором и памятью показано на рис. 30.

Р и с. 30. Преобразование адресов с использованием TLB

В кружках проставлены номера тактов, соответствующие этапам трансляции адресов через TLB. На каждом такте выполняются следующие операции.

Такт 1 - виртуальный адрес страницы в качестве тега поступает в TLB и преобразователь адреса.

Такт 2:

а) Если произошел промах – то такой страницы в TLB нет и далее используется стандартный цикл: преобразователь адресов и страничная таблица СТ в 3, 4 и 5 тактах возвращают адрес физической страницы и смещение для обращения к памяти. После этого в TLB добавляется новая пара «адрес виртуальной страницы - адрес физической страницы».

б) Если произошло попадание, то в TLB уже хранится преобразованный адрес физической страницы. В такте 2 этот адрес сразу передается в память, а преобразователь адресов в такте 3 генерирует смещение. В таком случае обращение к СТ не происходит.

5 Целостность данных

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

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

Р и с. 31. Рассогласование данных в кэш-памяти и ОП

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

Р и с. 32. Рассогласование данных в ОП и кэш-памяти
перенос при прямом доступе к ОП

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

1. Сквозная запись со стороны кэша.

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

При сквозной записи в случае удаления строки из кэша переписывать ее в оперативную память нет смысла.

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

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

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

Если адреса блока данных в кэше нет, то он переписывается из ОП в кэш. После этого блок обновляется, и бит достоверности устанавливается в 1.

6. Когерентность данных в мультипроцессорных системах

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

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

Рис.33 Общая структура мультипроцессорной системы
с разделяемой памятью

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

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

Когерентность можно обеспечить при соблюдении следующих условий:

- если чтение и запись в одну и ту же ячейку памяти достаточно отделены друг от друга по времени;

- если несколько операций записи в одну и ту же ячейку выполняются строго последовательно.

Эти условия регламентируются и поддерживаются системными протоколами. Такие протоколы называются протоколами когерентности кэш-памяти. Существует два класса протоколов:

- наблюдения;

- на основе справочников.

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

Каждый кэш хранит строку данных и информацию о ее состоянии (признак). Этот признак показывает:

а) разделяемая строка или нет;

б) модифицирована строка или нет.

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

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

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

В любых системах основные проблемы возникают при записи в разделяемую строку. Эта операция может выполняться одним из двух методов (протоколов):

1) записью с аннулированием;

2) записью с обновлением.

1. Запись с аннулированием.

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

2. Запись с обновлением.

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

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

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

Лекция 9

7. Протокол MESI

Протокол MESI широко распространен в вычислительных системах, в частности, на базе микропроцессоров IBM Power PC и Intel. Протокол используется в кэш-памяти с обратной записью. Его основная функция - откладывание на максимальный срок операции обратной записи данных в основную память. При этом уменьшается число пересылок «кэш - ОП» и «ОП - кэш».

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

По протоколу MESI задаются следующие состояния для строки кэш-памяти.

1. M – Модифицированная строка (Modified). Данные в строке были модифицированы, но измененная информация еще не переписана в ОП. Следовательно, данные в рассматриваемой строке достоверны только в этом кэше, а в основной памяти и кэшах других процессоров недостоверны.

2. E – Эксклюзивная строка (Exclusive). Строка в кэш-памяти не менялась путем записи и совпадает с аналогичной строкой в ОП, но отсутствует в любой другой локальной кэш-памяти. Данные в строке достоверны.

3. S - Разделяемая строка (Shared). Строка в кэш-памяти совпадет с аналогичной строкой в ОП и может присутствовать в других кэшах. Данные достоверны.

4. I – Недействительная строка (Invalid). Строка в кэш-памяти, помеченная как I, не содержит достоверных данных и становится логически недоступной.

Правила перехода строки из одного состояния в другое зависят от следующих факторов:

a) текущий статус строки;

b) выполняемая операция - чтение или запись;

c) попадание или промах в кэше;

d) совместно используемая строка или нет.

На рис. 34 показана диаграмма переходов состояний для протокола MESI.

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

Рис.34. Диаграмма переходов протокола MESI

8. Обеспечение когерентности памяти

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

1. Эксклюзивная организация.

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

Преимущество эксклюзивного кэша в том, что общий размер кэшируемой информации равен суммарному объёму кэшей всех уровней. Это позволяет более эффективно использовать объем кэш-памяти.

2. Инклюзивная организация.

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

В процессорах AMD Phenom используется эксклюзивный кэш L3. В процессорах Intel Core i7/i5 кэш L2 построен инклюзивно по отношению к L3. В последнем случае упрощается проверка когерентности: если данных в L3 нет, то их нет и в L1 и L2. Если блок данных присутствует в кэше L3, то к нему привязаны четыре бита, показывающие, в кэше какого ядра дублируется этот блок.

В процессоре с архитектурой Nehalem при емкости кэша L3, равной 8 Мбайт, на дублирование данных потребуется максимум 1, 25 Мбайт.