Сделай Сам Свою Работу на 5
 

Аппаратные способы решения проблемы когерентности

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Естественно, что для доступа к таким данным приходится обращаться к медленной основной памяти и производительность процессора падает. На первый взгляд, в варианте, где запрещается кэширование только управляющей информации, производительность процессора будет выше, однако, прежде чем сделать такой вывод, нужно учесть одно обстоятельство. Дело в том, что для сохранения согласованности данных, модифицируемых процессором в ходе выполнения критической секции программы, строки с копиями этих данных в кэш-памяти при выходе из критической секции нужно аннулировать. Данная операция носит название очистки кэш­памяти (cache flush). Очистка необходима для того, чтобы к моменту очередного входа в критическую секцию в кэш-памяти не осталось "устаревших"- данных. Регулярная очистка кэша при каждом выходе из критической секции снижает производительность процессора за счет увеличения времени, нужного для восстановления копий в кэш-памяти. Ситуацию, можно несколько улучшить, если вместо очистки всей кэш-памяти помечать те блоки, к которым при выполнении критической секции было обращение, тогда при покидании критической секции достаточно очищать только эти помеченные блоки.

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

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

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

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

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

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

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

(«грязный»), а в других - Modified («модифицированный» или «измененный»).

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

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

- блок удаляется из той кэш-памяти, где он был изменен;

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

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

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

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

условия, что кэши, которые собираются изменить содержимое совместно используемого блока, должны получить эксклюзивные права на этот блок, как это делается в рассматриваемом позже протоколе Berkeley [141].

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

Протокол однократной записи. Протокол однократной записи (write-once), предложенный Гудменом.[110], - первый из упоминающихся в публикациях протоколов обеспечения когерентности кэш-памяти. Он относится к схемам на основе наблюдения, действующим на принципе записи с аннулированием. Протокол предполагает, что первая запись в любую строку кэш-памяти производится по схеме сквозной записи, при этом контроллеры других кэшей объявляют свои копии измененного блока недействительными. С этого момента только процессор, произведший запись, обладает достоверной копией данных [141]. Последующие операции записи в рассматриваемую строку выполняются в соответствии с протоколом обратной записи [51].

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

Диаграмма состояний протокола показана на рис. 11.9

Для реализации протокола однократной записи каждой строке кэш-памяти приданы два бита. Это позволяет представить четыре состояния, в которых может находиться строка: «недействительная» (I, Invalid), «достоверная» (V, Valid), «резервированная» (R, Reserved) и «измененная» (D, Dirty). В состоянии I строка кэш­памяти не содержит достоверных данных. В состоянии V строка кэша содержит данные, считанные из основной памяти и к данному моменту еще не измененные, то есть строка кэша и блок основной памяти согласованы. Состояние R означает, что с момента считывания из основной памяти в блоке локальной кэш-памяти было произведено только одно изменение, причем оно учтено и в основной памяти. В состоянии R содержимое строки кэша и основной памяти также является согласованным. Наконец, статус D показывает, что строка кэш-памяти модифицировалась более чем один раз и последние изменения еще не переписаны в основную намять.

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

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

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

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

При последующих изменениях строки она помечается как D и работает протокол обратной записи.

В ранее упоминавшейся работе [110] приводятся результаты сравнения протоколов сквозной и обратной записи также и с протоколом однократной записи. Согласно Гудмену, мультипроцессорная система, состоящая из трех компьютеров PDP-11, каждый из которых имеет множественно-ассоциативную четырехканальную кэш-память емкостью 2048 байт при длине строки в 32 байта, показывает следующие показатели трафика шины: 30,76%, 17,55% и 17,38% для протоколов сквозной, обратной и однократной записи соответственно. Таким образом, показатели протокола однократной записи по сравнению с протоколами сквозной и обратной записи несколько лучше.

Протокол Synapse. Данный протокол, реализованный в отказоустойчивой мультипроцессорной системе Synapse N + 1, представляет собой версию протокола однократной записи, где вместо статуса R используется статус D. Кроме того, переход из состояния 0 в состояние V при промахе, возникшем в ходе чтения данных другим процессором, заменен достаточно громоздкой последовательностью. Связано это с тем, что при первом кэш-промахе чтения запросивший процессор не может получить достоверную копию непосредственно из той локальной кэш-памяти, где произошло изменение данных, и вынужден обратиться напрямую к основной памяти[51,138].

Протокол Berkeley. Протокол Berkeley [141] был применен в мультипроцессорной системе Berkeley, построенной на базе RISC-процессоров.

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

Другое улучшение — введение состояния совместного использования (shared).

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

Прежде всего, каждый раз, когда какой-либо процессор производит запись в свою кэш-память, изменяемая строка переводится в состояние «измененная, частная» (PD, Private Dirty). Далее, если строка является совместно используемой, на шину посылается сигнал аннулирования, и во всех локальных кэшах, где есть копия данного блока данных, эти копии переводятся в состояние «недействительная» (I, Invalid). Если при записи имел место промах, процессор получает копию блока из кэша текущего хозяина запрошенного блока. Лишь после этих действий процессор производит запись в свой кэш.

При кэш-промахе чтения процессор посылает запрос владельцу блока, с тем чтобы получить наиболее свежую версию последнего, и переводит свою новую копию в состояние «только для чтения» (RO, Read Only). Если владельцем строки был другой процессор, он помечает свою копию блока как «разделяемую измененную» (SD, Shared Dirty).

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

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

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

Протокол Illinois. Протокол Illinois, предложенный Марком Папамаркосом

[175], также направлен на снижение трафика шины и, соответственно, времени

ожидания процессором доступа к шине. Здесь, как и в протоколе Berkeley, главен­

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

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

В этом случае у одного и того же блока может быть несколько владельцев. Когда

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

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

Как и в предыдущем случае, сигнал аннулирования формируется, лишь когда

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

кола Illinois представлены на рис. 11.11,

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

изменяемая строка переводится в состояние «измененная частная» (PD, Private

Dirty). Если блок данных является совместно используемым, на шину посылается

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

эти копии переводятся в состояние «недействительная» (I, Invalid). Если при за­

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

запрошенного блока. Лишь после означенных действий процессор производит за­

пись в свой кэш. Как видно, в этой части имеет место полное совпадение с прото­

колом Berkeley,

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

чтобы получить наиболее свежую версию последнего, и переводит свою новую

копию в состояние «эксклюзивная»- (Е, Exclusive) при условии, что он является

единственным владельцем строки. Б противном случае статус меняется на «разде­

ляемая» (S, Shared).

Существенно, что протокол расширяем и тесно привязан как к коэффициенту

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

типроцессорной системы.

Протокол Firefly. Протокол был предложен Такером и др. [211] и реализован

в мультипроцессорной системе Firefly Multiprocessor Workstation, разработанной

в исследовательском центре Digital Equipment Corporation.

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

строки кэша совпадают с состояниями протокола Illinois (рис. 11,12). Отличие со­

стоит в том, что стратегия обратной записи применяется только к тем строкам,

которые находятся в состоянии PD или Е, в то время как применительно к строкам

в состоянии S действует сквозная запись. Наблюдающие кэши при обновлении своих копий используют процедуру сквозной записи. Кроме того, наблюдающие кэши, обнаружившие у себя копию строки, возбуждают специальную «разделяемую» линию шины с тем, чтобы записывающий контроллер мог принять решение о том, в какое состояние переводить строку, в которую была произведена запись. «Разделяемая» линия при кэш-промахе чтения служит для информирования контроллера локальной кэш-памяти о месте, откуда поступила копия строки: из основной памяти или другого кэша. Таким образом, состояние S применяется только к тем данным, которые действительно используются совместно [162, 212].

Протокол имеет преимущества перед ранее описанными в том, что стратегия

сквозной записи привлекается лишь по логической необходимости. Когда ячейка

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

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

ячейку. Это приводит к тому, что протокол Firefly существенно экономнее по тра­

фику шины по сравнению с прочими протоколами [211]. С другой стороны, стра­

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

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

только один процессор. Отсюда — увеличение трафика шины, что доказывает не­

перспективность использования данного протокола в будущих разработках про­

токолов обеспечения когерентности кэш-памяти.

Протокол Dragon. Протокол применен в мультипроцессорной системе Xerox

Dragon и представляет собой независимую версию протокола Firefly.

17 Зак. 470 ;

В протоколе реализована процедура записи с обновлением. Строка кэша может

иметь одно из пяти состояний [162,212]:

- Invalid (I) - копия, хранящаяся в кэше, недействительна;

- Read Private (RP) — существует лишь одна копия блока, и она совпадает с содер­

жимым основной памяти;

- Private Dirty (PD) — существует лишь одна копия блока, и она не совпадает с со­

держимым основной памяти;

- Shared Clean (SC) — имеется несколько копий блока, и все они идентичны со­

держимому основной памяти;

- Shared Dirty (SO) — имеется несколько копий блока, не совпадающих с содер­

жимым основной памяти.

Дополнительное состояние SO предназначено для предотвращения записи

в основную память. Диаграмма состояний для данного протокола приведена на

рис. 11.13.

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

популярным является протокол MESI (Modified/Exclusive/Shared/Invalid). Про­

токол MESI широко распространен в коммерческих микропроцессорных систе­

мах, например на базе микропроцессоров Pentium и PowerPC. Так, его можно обна­

ружить во внутреннем кэше и контроллере внешнего кэша i82490 микропроцессора

Pentium, в процессоре i860 и контроллере кэш-памяти МС88200 фирмы Motorola,

Протокол был разработан для кэш-памяти с обратной записью. Одной из ос­

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

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

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

ВС. Это позволяет улучшить производительность системы за счет минимизации

ненужных пересылок информации между кэшами и основной памятью.

Протокол MESI приписывает каждой кэш-строке одно из четырех состояний,

которые контролируются двумя битами состояния MESI в теге данной строки.

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

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

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

логические устройства. Одна из версий протокола предусматривает использова­

ние ранее рассмотренной схемы однократной записи.

Согласно протоколу MESI, каждая строка бывает в одном из четырех возмож­

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

М , Е, S и I):

-Модифицированная (М, Modified) - данные в кэш-строке, помеченной как М,

были модифицированы, но измененная информация пока не переписана в ос­

новную память. Это означает, что информация, содержащаяся в рассматривае­

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

кэшах — недостоверна.

- Эксклюзивная (Е, Exclusive) — данная строка в кэше не подвергалась измене­

нию посредством запроса на запись, совпадает с аналогичной строкой в основ­

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

она достоверна в этом кэше и недостоверна в любом другом.

Разделяемая (S, Shared) - строка в кэше совпадает с аналогичной строкой в ос­

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

Недействителъная (I, Invalid) - кэш-строка, помеченная как недействитель­

ная, не содержит достоверных данных и становится логически недоступной.

Порядок перехода строки кэш-памяти из одного состояния в другое зависит от:

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

обращения в кэш (попадание или промах) и, наконец, от того, является ли строка

совместно используемой или нет. На рис. 11.14 приведена диаграмма основных

переходов без учета режима однократной записи.

Предположим, что один из процессоров делает запрос на чтение из строки, ко­

торой в текущий момент нет в его локальной кэш-памяти (промах при чтении).

Запрос будет широковещательно передан по шине. Если ни в одном из кэшей не

нашлось копии нужной строки, то ответной реакции от контроллеров наблюдения

других процессоров не последует, строка будет считана в кэш запросившего про­

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

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

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

Все копии рассматриваемой строки во всех кэшах будут переведены в состояние S,

вне зависимости от того, в каком состоянии они были до этого (М, Е или S).

Когда процессор делает запрос на запись в строку, отсутствующую в его ло­

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

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

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

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

отсутствует модифицированная копия данной строки. Формируемая в этом слу­

чае последовательность операций носит название чтения с намерением модифика­

ции (RWITM, Read With Intent To Modify). Если в одном из кэшей обнаружилась

копия нужной строки, причем в состоянии М, то процессор, обладающий этой ко­

пией, прерывает RWITM-последовательность и переписывает строку в ОП, после

чего меняет состояние строки в своем кэше на I. Затем RWITM-последователь­

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

тывания обновленной строки. Окончательным состоянием строки будет М, при

котором ни в ОП, ни в других кэшах нет еще одной достоверной ее копни. Если

копия строки существовала в другом кэше и не имела состояния М, то такая копия

аннулируется и доступ к основной памяти производится немедленно.

Кэш-попадание при чтении не изменяет статуса читаемой строки. Если про­

цессор выполняет доступ для записи в существующую строку, находящуюся в со­

стоянии S, он передает на шину широковещательный запрос, с тем чтобы инфор­

мировать другие кэши, обновляет строку в своем кэше и присваивает ей статус М.

Все остальные копии строки переводятся в состояние I. Если процессор произво­

дит доступ по записи в строку, находящуюся в состоянии Е, единственное, что он

должен сделать, — это произвести запись в строку и изменить ее состояние на М,

поскольку другие копии строки в системе отсутствуют.

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

процессоров, запрашивающих доступ к ячейке х. Обращение к любой ячейке стро­

ки кэш-памяти рассматривается как доступ ко всей строке.

Проиллюстрируем этапы, когда процессор 2 пытается прочитать содержимое

ячейки х" (рис. 11.16). Сперва наблюдается кэш-промах по чтению и процессор

пытается обратиться к основной памяти. Процессор 1 следит за шиной, обнаружи­

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

состоянии М, поэтому он блокирует операцию чтения от процессора 2. Затем

процессор 1 переписывает строку, содержащую х", в ОП и освобождает про­

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

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

сор 2 получает строку, содержащую х", и загружает ее в свою кэш-память. Обе

копии помечаются как S.

До сих пор рассматривалась версия протокола MESI без однократной записи.

С учетом однократной записи диаграмма состояний, изображенная на рис. 11.14,

немного видоизменяется. Все кэш-промахи при чтении вызывают переход в состо­

яние S. Первое попадание при записи сопровождается переходом в состояние Е

(так называемый переход однократной записи). Следующее попадание при записи

влечет за собой изменение статуса строки на М.

 



©2015- 2022 stydopedia.ru Все материалы защищены законодательством РФ.