Файл: 481-550.pdf

Мультипроцессорная когерентность кэш-памяти  5 0 1

Мультипроцессорная

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

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

программы, либо независимую программу. Все процессоры обращаются к коман-

дам и данным, хранящимся в общей основной памяти. Поскольку память является

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

чивается. Для сокращения такой задержки каждому процессору придается локаль-

ная кэш-память, которая, обслуживая локальные обращения к памяти, во многих

случаях предотвращает необходимость доступа к совместно используемой основ-

ной памяти. В свою очередь, оснащение каждого процессора локальной кэш-памя-

тью приводит к так называемой

 проблеме когерентности

 или обеспечения

 согласо-

ванности кэш-памяти.

 Согласно [93, 215], система является когерентной, если

каждая операция чтения по какому-либо адресу, выполненная любым из процес-

соров, возвращает значение, занесенное в ходе последней операции записи по это-

му адресу, вне зависимости от того, какой из процессоров производил запись по-

следним.

В простейшей форме проблему когерентности кэш-памяти можно пояснить

следующим образом (рис 11.5). Пусть два процессора Р

1

 и Р

2

 связаны с общей па-

мятью посредством шины. Сначала обаC процессора читают переменную

 х.

 Копии

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

 Р

1

 выполняет опера-

цию увеличения значения переменной x на единицу. Так как копия переменной

уже находится в кэш-памяти данного процессора, произойдет кэш-попадание
и значение

 х

 будет изменено только в кэш-памяти 1. Если теперь процессор Р

2

 вновь

выполнит операцию чтения

 х,

 то также произойдет кэш-попадание и Р

2

 получит

хранящееся в его кэш-памяти «старое» значение

 х

 (рис. 11.5,5).

Поддержание согласованности требует, чтобы при изменении элемента данных

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

в общей памяти. Схожая проблема возникает, кстати, и в однопроцессорных сиc- .

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

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

и аппаратный. В некоторых системах применяют стратегии, совмещающие оба под-

хода.

Программные способы решения

проблемы когерентности

Программные приемы решения проблемы когерентности позволяют обойтись без

дополнительного оборудования или свести его к минимуму [72]. Задача возлага-

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

5 0 2 Глава 11. Организация памяти вычислительных систем

а б

Рис. 11.5. Иллюстрация проблемы когерентности памяти:

 а —

 содержимое памяти

до изменения значения х;

 б —

 после изменения

однако принятые компилятором решения могут в целом отрицательно сказаться

на эффективности кэш-памяти.

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

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

В процессе выполнения программы операционная система или соответствующая

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

ходится обращаться к «медленной» основной памяти. Учитывая, что некогерент-
ность возникает только в результате операций записи, происходящих значительно

реже, чем чтение, рассмотренный прием следует признать недостаточно удачным.

Более эффективными представляются способы, где в ходе анализа программы

определяются безопасные периоды использования общих переменных и так назы-

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

Аппаратные способы решения

проблемы когерентности

Большинство из предложенных способов борьбы с некогерентностью ориентиро-

ваны на динамическое (в процессе вычислений) распознавание и устранение не-

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

ность, поскольку издержки, связанные с некогерентностью, имеют место только
при возникновении ситуации некогерентности. Кроме того, непрограммный под-
ход прозрачен для программиста и пользователя [215]. Аппаратные механизмы

Мультипроцессорная когерентность кэш-памяти  5 0 3

преодоления проблемы когерентности принято

 называть протоколами когерент-

ности кэш-памяти.

Как известно, для обеспечения идентичности копий данных в кэше и основной

памяти в однопроцессорных системах применяется одна из двух стратегий:

 сквоз-

ная запись

 (write through) или

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

 (write back). При сквозной записи

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

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

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

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

когерентность всех копий. Ни сквозная, ни обратная запись не предусматривают

такой ситуации, и для ее разрешения опираются на другие приемы, а именно:

 за-

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

 (write invalidate) и

 запись с обновлением

 (write update). По-

следняя известна также под названием

 записи с трансляцией

 (write broadcast).

В варианте записи с аннулированием, если какой-либо процессор производит

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

 х

 имеет-

ся во всех кэшах (рис. 11.6,

 а),

 а также ее состояние после записи нового значения

х

 в кэш с номером 2 (рис 11.6,

 б).

а

 б

Рис. 11.6. Запись с аннулированием: а — исходное состояние;

 6 —

 после изменения

значений х в кэш-памяти 2

Если впоследствии другой процессор попытается прочитать данные из своей

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

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

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

такая возможность отсутствует, новая копия берется из основной памяти. В слу-

5 0 4 Глава 11. Организация памяти вычислительных систем

чае сквозной записи это может быть сделано сразу же, а при использовании обрат-
ной записи модифицированный блок предварительно должен быть переписан в

основную память.

Запись с обновлением предполагает, что любая запись в локальный кэш немед-

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

ным). Этот случай иллюстрирует рис. 11.7.

а 6

Рис. 11.7. Запись с обновлением:

 в —

 исходное состояние;

 б —

 после изменения

значения х в кэш-памяти 2

Стратегия записи с обновлением требует широковещательной передачи новых

данных по сети межсоединений, что осуществимо не при любой топологии сети.

В общем случае для поддержания когерентности в мультипроцессорных систе-

мах имеются следующие возможности:

-

 совместно используемая кэш-память;

^- некэшируемые данные;

-

 широковещательная запись;

-

 протоколы наблюдения;

-

 протоколы на основе справочника.

Совместно используемая кэш-память.

 Первое и наиболее простое решение -

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

коммуникационной сети. Хотя данный прием обеспечивает когерентность копий

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

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

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

согласно которому процессор и кэш-память должны располагаться как можно бли-

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

Мультипроцессорная когерентность кэш-памяти  5 0 5

туп к кэш-памяти. Тем не менее общая задержка обращения к памяти в целом умень-
шается.

Некэшируемые данные.

 Проблема когерентности имеет отношение к тем дан-

ным, которые в ходе выполнения программы могут быть изменены. Одно из веро-

ятных решений — это запрет кэширования таких данных. Технически запрет на

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

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

Если кэш-система состоит из раздельных кэшей команд и данных, сказанное

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

ды к программированию не рекомендуют модификацию команд программы. Сле-
довательно, по отношению к информации в кэше команд применяется только опе-

рация чтения, что не влечет проблемы когерентности.

В отношении того, какие данные не должны кэшироваться, имеется несколько

подходов.

В первом варианте запрещается занесение в кэш лишь той части совместно ис-

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

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

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

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

Естественно, что для доступа к таким данным приходится обращаться к медлен-

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

данных, модифицируемых процессором в ходе выполнения критической секции

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

 очистки кэш-

памяти

 (cache flush). Очистка необходима для того, чтобы к моменту очередного

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

изводительность процессора за счет увеличения времени, нужного для восстанов-

ления копий в кэш-памяти. Ситуацию, можно несколько улучшить, если вместо

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

точно очищать только эти помеченные блоки.

Широковещательная запись.

 При широковещательной записи каждый запрос

на запись в конкретную кэш-память направляется также и всем остальным кэшам

системы. Это заставляет контроллеры кэшей проверить, нет ли там копии изменяе-