Проблема согласованности кэшей в мультипроцессорных системах

Обновлено: 10.01.2025

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

Бит PCD запрещает ( PCD = 1 ) или разрешает ( PCD = 0 ) кэширование страницы. Запрещение кэширования необходимо для страниц, которые содержат порты ввода/вывода с отображением на память . Оно также полезно для страниц, кэширование которых не дает выигрыша в быстродействии, например, страниц, содержащих программу инициализации.

Бит PWT определяет метод обновления ОЗУ и внешней кэш -памяти ( кэш 2-го уровня). Если PWT = 1 , то для данных в соответствующей странице определяется кэширование со сквозной записью, при PWT = 0 применяется способ обратной записи. Используется в микропроцессорах начиная с Pentium. Так как внутренняя кэш - память в МП i486 работает со сквозной записью, состояние бита PWT на нее не влияет. Бит PWT в этом случае действует только на внешнюю КП.

Обеспечение согласованности кэш-памяти микропроцессоров в мультипроцессорных системах

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

Рис. 4.4. Структура мультимикропроцессорной системы с общей оперативной памятью

Предположим, что МП А считал некоторую строку данных из ОЗУ в свою внутреннюю КП и изменил данные в этой строке в процессе работы.

Мы отмечали, что существует два основных механизма обновления оперативной памяти:

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

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

Существует два класса протоколов когерентности :

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

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

Для поддержания когерентности применяется два основных метода.

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

Альтернативой протоколу записи с аннулированием является обновление всех копий элемента данных в случае записи в этот элемент данных .

Этот тип протокола называется протоколом записи с обновлением ( write update protocol ), или протоколом записи с трансляцией ( write broadcast protocol ).

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

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

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

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

измененное состояние ( Modified ): информация, хранимая в кэш-памяти микропроцессора А, достоверна только в этом кэше; она отсутствует в оперативной памяти и в кэш-памяти других микропроцессоров;
исключительная копия ( Exclusive ): информация, содержащаяся в кэше А, содержится еще только в оперативной памяти;
разделяемая информация ( Shared ): информация, содержащаяся в кэше А, содержится в кэш-памяти по крайней мере еще одного МП, а также в оперативной памяти;
недостоверная информация ( Invalid ): в строке кэш-памяти находится недостоверная информация.

Таким образом, состояние признаков потокола MESI отражает следующие состояния (по отношению к МПА) строки кэш -памяти (табл. 4.2):

При работе микропроцессора А с точки зрения обеспечения когерентности памяти возможны следующие ситуации:

RH ( Read Hit ) - кэш-попадание при чтении;
WH ( Write Hit ) - кэш-попадание при записи;
RME ( Read Miss Exclusive ) - кэш-промах при чтении;
RMS ( Read Miss Shared ) - кэш-промах при чтении, но соответствующий блок есть в кэш-памяти другого микропроцессора;
WM ( Write Miss ) - кэш-промах при записи;
SHR ( Snoop Hit Read ) - обнаружение копии блока при прослушивании операции чтения другого кэша;
SHW ( Snoop Hit Write ) - обнаружение копии блока при прослушивании операции записи другого кэша.

Наибольший интерес здесь представляют две последние позиции.

Современные микропроцессоры имеют двунаправленную шину адреса.

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

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

Рис. 4.5. MESI-диаграмма обеспечения когерентности кэш-памяти

Проиллюстрируем некоторые из представленных переходов.

Пусть блок кэш -памяти находится в состоянии Modified , то есть достоверная информация находится только в кэш -памяти данного МП. Тогда в случае обнаружения при прослушивании адресной шины обращения со стороны другого микропроцессора для чтения информации по входящим в данную строку адресам микропроцессор должен передать эту строку кэшпамяти в ОЗУ , откуда она уже будет прочитана другим микропроцессором.

При этом состояние строки в кэш -памяти рассматриваемого микропроцессора изменится с модифицированного на разделяемое ( Shared ).

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

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

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

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

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

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

Обмен записываемыми данными
Процесс миграции
Активность ввода / вывода

Протоколы Snoopy Bus

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

Кэш-события и действия

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

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

Рис. 5.40. Типовая архитектура мультипроцессорной системы с общей памятью

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

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

Рис. 5.41. Иллюстрация проблемы когерентности кэш-памяти

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

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

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

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

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

Необходимость строго последовательного выполнения операций записи является более тонким, но также очень важным свойством. Представим себе, что строго последовательное выполнение операций записи не соблюдается. Тогда процессор P1 может записать данные в ячейку, а затем в эту ячейку выполнит запись процессор P2. Строго последовательное выполнение операций записи гарантирует два важных следствия для этой последовательности операций записи. Во-первых, оно гарантирует, что каждый процессор в машине в некоторый момент времени будет наблюдать запись, выполняемую процессором P2. Если последовательность операций записи не соблюдается, то может возникнуть ситуация, когда какой-нибудь процессор будет наблюдать сначала операцию записи процессора P2, а затем операцию записи процессора P1, и будет хранить это записанное P1 значение неограниченно долго. Более тонкая проблема возникает с поддержанием разумной модели порядка выполнения программ и когерентности памяти для пользователя: представьте, что третий процессор постоянно читает ту же самую ячейку памяти, в которую записывают процессоры P1 и P2; он должен наблюдать сначала значение, записанное P1, а затем значение, записанное P2. Возможно он никогда не сможет увидеть значения, записанного P1, поскольку запись от P2 возникла раньше чтения. Если он даже видит значение, записанное P1, он должен видеть значение, записанное P2, при последующем чтении. Подобным образом любой другой процессор, который может наблюдать за значениями, записываемыми как P1, так и P2, должен наблюдать идентичное поведение. Простейший способ добиться таких свойств заключается в строгом соблюдении порядка операций записи, чтобы все записи в одну и ту же ячейку могли наблюдаться в том же самом порядке. Это свойство называется последовательным выполнением (сериализацией) операций записи (write serialization). Вопрос о том, когда процессор должен увидеть значение, записанное другим процессором достаточно сложен и имеет заметное воздействие на производительность, особенно в больших машинах.

Альтернативные протоколы

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

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

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

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

Основы реализации

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

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

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

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

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

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

Рис. 5.42. Примеры протоколов наблюдения

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

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

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

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

Согласованные кеши: значение во всех копиях кешей одинаково.

СОДЕРЖАНИЕ

Обзор

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

Ниже приведены требования к согласованности кеша:

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

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

Определение

Согласованность определяет поведение чтения и записи в одно место адреса.

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

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

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

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

Многопроцессорная система состоит из четырех процессоров - P1, P2, P3 и P4, каждый из которых содержит кэшированные копии общей переменной S , начальное значение которой равно 0. Процессор P1 изменяет значение S (в своей кэшированной копии) на 10, после чего процессор P2 изменяет значение S в своей собственной кэшированной копии на 20. Если мы гарантируем только распространение записи, то P3 и P4 обязательно увидят изменения, внесенные в S P1 и P2. Однако, P3 могут видеть изменения , внесенные P1 после просмотра изменения , внесенные P2 и , следовательно , возвращение 10 на чтение к S . Р4 с другой стороны , могут видеть изменения , сделанные P1 и P2 в том порядке , в котором они сделаны и , следовательно , возвращение 20 на чтение к S . Процессоры P3 и P4 теперь имеют несогласованный взгляд на память.

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

Запись в одно и то же место должна быть упорядочена. Другими словами, если местоположение X получило два разных значения A и B в этом порядке от любых двух процессоров, процессоры никогда не смогут прочитать местоположение X как B, а затем прочитать его как A. Местоположение X должно отображаться со значениями A и B в таком порядке.

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

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

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

Механизмы согласованности

Слежка

Впервые представленный в 1983 году, отслеживание - это процесс, при котором отдельные кэши отслеживают адресные строки для доступа к ячейкам памяти, которые они кэшировали. Эти протоколы записи ТЕРЯЕТСЯ и протоколы записи обновления использовать этот механизм. Для механизма отслеживания фильтр отслеживания уменьшает трафик отслеживания путем поддержания множества записей, каждая из которых представляет строку кэша, которая может принадлежать одному или нескольким узлам. Когда требуется замена одной из записей, фильтр отслеживания выбирает для замены запись, представляющую строку или строки кэша, принадлежащие наименьшему количеству узлов, как определено из вектора присутствия в каждой из записей. Временной или другой тип алгоритма используется для уточнения выбора, если более чем одна строка кэша принадлежит наименьшему количеству узлов.

На основе справочника

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

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

Протоколы согласованности

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

Протокол должен реализовывать основные требования к согласованности. Он может быть адаптирован для целевой системы или приложения.

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

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

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

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

Однако масштабируемость - один из недостатков широковещательных протоколов.

Для поддержания согласованности были разработаны различные модели и протоколы, такие как MSI , MESI (также известный как Иллинойс), MOSI , MOESI , MERSI , MESIF , однократная запись , Synapse, Беркли, Firefly и протокол Dragon . В 2011 году ARM Ltd предложила AMBA 4 ACE для обеспечения согласованности в SoC . Спецификация AMBA CHI (интерфейс согласованного концентратора) от ARM Ltd , которая принадлежит к группе спецификаций AMBA5, определяет интерфейсы для подключения полностью согласованных процессоров.

Читайте также: