Протоколы обеспечения когерентности

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

1. Протоколы на основе справочника. Информация о состоянии блока физической оперативной памяти содержится только в одном месте, называемом справочником (физически справочник может быть распределен по узлам многоядерной системы).

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

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

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

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

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

Разница в производительности между протоколами записи с обновлением и с аннулированием определяется тремя характеристиками:

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

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

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

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

Основы реализации протоколов обеспечения когерентности

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

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

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

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

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

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

Чтобы отследить, является ли блок общим (разделяемым), вводят дополнительный разряд состояния (shared - разделяемый), связанный с каждым блоком, точно также как это делается для разрядов достоверности (valid) и модификации (modified или dirty) блока. Добавив разряд состояния, определяющий является ли блок общим (разделяемым), можно решить вопрос о том, должна ли запись генерировать операцию аннулирования в протоколе с аннулированием, или операцию трансляции при использовании протокола с обновлением. Если происходит запись в блок, находящийся в состоянии «разделяемый» при использовании протокола записи с аннулированием, кэш-память формирует операцию аннулирования и помечает блок как частный (private). Никаких последующих операций аннулирования этого блока данное ядро выполнять больше не будет. Кэш-память с исключительной (exclusive) копией блока обычно называется «владельцем» owner) блока.

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

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

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

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

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