Протоколы наблюденияВ протоколах наблюдения (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% для протоколов сквозной, обратной и однократной записи соответственно. Таким образом, показатели протокола однократной записи по сравнению с протоколами сквозной и обратной записи несколько лучше. Протокол Synapse. Данный протокол, реализованный в отказоустойчивой мультипроцессорной системе Synapse N+1, представляет собой версию протокола однократной записи, где вместо состояния R используется состояние D. Кроме того, переход из состояния D в состояние V при промахе, возникшем в ходе чтении данных другим процессором, заменен достаточно громоздкой последовательностью. Связано это с тем, что при первом кэш-промахе чтения запросивший процессор не может получить достоверную копию непосредственно из той локальной кэш-памяти, где произошло изменение данных и вынужден обратиться к данным из основной памяти [ARCH87, JAME90]. Протокол Berkeley. Протокол Berkeley [KATZ85] был применен в мультипроцессорной системе Berkeley, построенной на базе RISC-процессоров. Снижение издержек, возникающих в результате кэш-промахов, обеспечивается благодаря реализованной в этом протоколе идее прав владения на строку кэша. Обычно владельцем прав на все блоки данных считается основная память. Прежде чем модифицировать содержимое строки в своей кэш-памяти, процессор должен получить права владения на данную строку. Эти права приобретаются с помощью специальных операций чтения и записи. Если при доступе к блоку, владельцем которого в данный момент не является основная память, происходит кэш-промах, процессор, являющийся владельцем строки, предотвращает чтение из основной памяти и сам снабжает запросивший процессор данными из своей локальной кэш-памяти. Другое улучшение — введение состояния совместного использования (shared). Когда процессор производит запись в одну из строк своей локальной кэш-памяти, он обычно формирует сигнал аннулирования копий изменяемого блока в других кэшах. В протоколе Berkeley сигнал аннулирования формируется только при условии, что в других кэшах имеются такие копии. Это позволяет существенно снизить непроизводительный трафик шины. Возможны следующие сценарии. Прежде всего, каждый раз, когда какой-либо процессор производит запись в свою кэш-память, изменяемая строка переводится в состояние «измененная, частная» (PD, Private Dirty). Далее, если строка является совместно используемой, на шину посылается сигнал аннулирования и во всех локальных кэшах, где есть копия данного блока данных, эти копии переводятся в состояние «недействительная» (I, Invalid). Если при записи возник промах, процессор получает копию блока из кэша текущего владельца запрошенного блока. Лишь после этих действий процессор производит запись в свой кэш. При кэш-промахе чтения процессор посылает запрос владельцу блока с тем, чтобы получить наиболее свежую версию блока и переводит свою новую копию в состояние «только для чтения» (RO, Read Only). Если владельцем строки был другой процессор, он изменяет состояние своей копии блока на «разделяемая измененная» (SD, Shared Dirty). Диаграмма состояний протокола Berkeley показана на рис. 11.10.
Рис. 11.10. Протокол Berkeley Сравнивая протоколы однократной записи и Berkeley можно отметить следующее. Оба протокола используют стратегию обратной записи, при которой измененные блоки удерживаются в кэш-памяти как можно дольше. Основная память обновляется только при удалении строки из кэша. Верхняя граница общего количества транзакций записи на шине определяется той частью протокола однократной записи, где реализуется сквозная запись, так как стратегия сквозной записи порождает на шине операцию записи при каждой записи, инициированной процессором [KATZ85]. Поскольку первая операция записи в протоколе однократной записи является сквозной, она производится даже если данные не являются совместно используемыми. Это порождает дополнительный трафик шины, который возрастает с увеличением емкости кэш-памяти. Доказано, что протокол однократной записи приводит к большему трафику шины, по сравнению с протоколом Berkeley [KATZ85]. Для постоянно читаемой и обновляемой строки в протоколе однократной записи необходимо считывание этой строки в кэш, ее локальная модификация в кэше и обратная запись в память. Эта процедура требует двух операций на шине: чтения из основной памяти и обратной записи в основную память. С другой стороны, протокол Berkeley требует получения прав на строку. Далее блок модифицируется в кэше. Если до удаления из кэша к строке не производилось обращение, число циклов шины будет таким же как и в протоколе однократной записи. Однако, более вероятно, что строка будет запрошена опять, тогда с позиций одиночной кэш-памяти, обновление строки кэша требует только одной операции чтения на шине. Таким образом, протокол Berkeley пересылает строки непосредственно между кэшами, в то время как протокол однократной записи передает блок из исходного кэша в основную память, а затем из основной памяти в запросившие кэши, что приводит к общей задержке системы памяти [KATZ85]. Протокол Illinois. Протокол Illinois, предложенный Марком Папамаркосом [PAPA84], также направлен на снижение трафика шины и, соответственно, времени ожидания процессором доступа к шине. Здесь, как и в протоколе Berkeley, используется идея прав владения блоком, но несколько измененная. В протоколе Illinois правом владения обладает любой кэш, где есть достоверная копия блока данных. В этом случае у одного и того же блока может быть несколько владельцев. Когда такое происходит, каждому процессору назначается определенный приоритет и источником информации становится владелец с более высоким приоритетом. Как и в предыдущем случае, сигнал аннулирования формируется лишь когда копии данного блока имеются и в других кэшах. В протоколе Illinois (рис. 11.11) возможны следующие сценарии.
Рис. 11.11. Протокол Illinois Каждый раз, когда какой-либо процессор производит запись в свою кэш-память, изменяемая строка переводится в состояние «измененная частная» (PD, Private Dirty). Если блок данных является совместно используемым, на шину посылается сигнал аннулирования и во всех локальных кэшах, где есть копия данного блока, эти копии переводятся в состояние «недействительная» (I, Invalid). Если при записи возник промах, процессор получает копию из кэша текущего владельца запрошенного блока. Лишь после этих действий процессор производит запись в свой кэш. Как видно, в этой части имеет место полное совпадение с протоколом Berkeley. При кэш-промахе чтения процессор посылает запрос владельцу блока с тем, чтобы получить наиболее свежую версию и переводит свою новую копию в состояние «эксклюзивная» (E, Exclusive), если он является единственным владельцем строки. В противном случае состояние меняется на «разделяемая» (S, Shared). Существенно, что протокол является расширяемым и тесно привязан к коэффициенту кэш-промахов и объему данных, которые совместно используются процессорами мультипроцессорной системы. Протокол Firefly. Протокол был предложен Такером и др. [THAC88] и реализован в мультипроцессорной системе Firefly Multiprocessor Workstation, разработанной в исследовательском центре Digital Equipment Corporation. В протоколе Firefly используется запись с обновлением. Возможные состояния строки кэша совпадают с состояниями протокола Illinois (рис. 11.12). Отличие состоит в том, что стратегия обратной записи применяется только к тем строкам, которые находятся в состоянии PD или E, в то время как применительно к строкам в состоянии S используется сквозная запись. Наблюдающие кэши при обновлении своих копий используют процедуру сквозной записи. Кроме того, наблюдающие кэши, обнаружившие у себя копию строки, возбуждают специальную «разделяемую» линию шины с тем, чтобы записывающий контроллер мог принять решение о том, в какое состояние переводить строку, куда была произведена запись. «Разделяемая» линия при кэш-промахе чтения служит для информирования контроллера локальной кэш-памяти о том, откуда поступила копия строки: из основной памяти или другого кэша. Таким образом, состояние S применяется только к тем данным, которые действительно используются совместно [THAK90, MANU92].
Рис. 11.12. Протокол Firefly Протокол имеет преимущества перед ранее описанными в том, что стратегия сквозной записи используется лишь по логической необходимости. Когда ячейка перестает быть совместно используемой, нужна только одна дополнительная операция записи, которая производится последней кэш-памятью, содержащей эту ячейку. Это приводит к тому, что протокол Firefly существенно экономнее по трафику шины по сравнению с другими протоколами [THAC88]. С другой стороны, стратегия сквозной записи остается в силе до тех пор, пока строка кэша будет совместно используемой, даже если фактически чтение строки и запись в нее производит только один процессор. Это приводит к увеличению трафика шины и доказывает неперспективность использования данного протокола в последующих разработках протоколов когерентности кэш-памяти. Протокол Dragon. Протокол применен в мультипроцессорной системе Xerox Dragon, и представляет собой независимую версию протокола Firefly. В протоколе используется процедура записи с обновлением. Строка кэша может иметь одно из пяти состояний [THAK90, MANU92]: l Invalid(I) — копия, хранящаяся в кэше недействительна; l Read Private (RP) — существует лишь одна копия блока и она совпадает с содержимым основной памяти; l Private Dirty(PD) — существует лишь одна копия блока и она не совпадает с содержимым основной памяти; l Shared Clean(SC) — имеется несколько копий блока и все они совпадают с содержимым основной памяти; l Shared Dirty(SD) — имеется несколько копий блока, не совпадающих с содержимым основной памяти.
Рис. 11.13. Протокол Dragon Дополнительное состояние SDиспользуется для предотвращения записи в основную память. Диаграмма состояний для данного протокола приведена на рис. 11.13.
|
