Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




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

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

В простейшей форме проблему когерентности кэш-памяти можно пояснить следующим образом (рис 11.5). Пусть два процессора P1 и P2 связаны с общей памятью посредством шины. Сначала оба процессора читают переменную x. Копии блоков, содержащих эту переменную, пересылаются из основной памяти в локальные кэши обоих процессоров (рис. 11.5 а). Далее процессор P1 выполняет операцию увеличения значения переменной x на единицу. Так как копия переменной уже находится в кэш-памяти данного процессора, произойдет кэш-попадание и значение x будет изменено только в кэш-памяти 1. Если теперь процессор P2 вновь выполнит операцию чтения x, то также произойдет кэш-попадание и P2 получит хранящееся в его кэш-памяти «старое» значение x (рис. 11.5 б).

Рис. 11.5. Иллюстрация проблемы когерентности памяти: содержимое памяти а — до изменения значения x; б — после изменения

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

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

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

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

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

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

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

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

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

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

Рис. 11.6. Запись с аннулированием: а — исходное состояние; б — после изменения значения x в кэш-памяти 2

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

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

Рис. 11.7. Запись с обновлением: а — исходное состояние; б — после изменения значения x в кэш-памяти 2


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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

Рис. 11.8. Кэш-память с контроллером наблюдения за шиной

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 11.9. Протокол однократной записи

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

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

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

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


Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...