Протокол Дракона

Протокол Дракона ^[1] на основе обновлений, — это протокол когерентности кэша используемый в многопроцессорных системах. Распространение записи выполняется путем прямого обновления всех кэшированных значений на нескольких процессорах. Протоколы, основанные на обновлении, такие как протокол Dragon, работают эффективно, когда за записью в блок кэша следует несколько операций чтения, выполняемых другими процессорами, поскольку обновленный блок кэша легко доступен во всех кэшах, связанных со всеми процессорами.

Штаты

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

Эксклюзивная очистка (E) : это означает, что блок кэша был сначала получен текущим процессором и с тех пор к нему не обращался ни один другой процессор.
Общая очистка (Sc) : это означает, что блок кэша определенно существует в кэшах нескольких процессоров и что текущий процессор не является последним, кто записывает этот блок. Состояния E и Sc поддерживаются протоколом отдельно, чтобы предотвратить операции чтения и записи в блоках кэша, которые не являются общими, от запуска транзакций шины и, следовательно, замедления выполнения. Это обычное явление в однопоточных программах.
Совместное изменение (Sm) : это означает, что блок существует в кэшах нескольких процессоров, и текущий процессор является последним, который модифицировал блок. Следовательно, текущий процессор называется владельцем блока. В отличие от протоколов аннулирования, блок не обязательно должен быть обновлен в основной памяти, а только в процессоре. Процессор несет ответственность за обновление основной памяти при удалении блока кэша.
Модифицировать (M) : Это означает, что только один процессор имеет блок памяти, а также что он изменил значение, поскольку оно было извлечено из памяти.

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

	И	наук	см	М
И	Н	Н	Н	Н
наук	Н	И	И	Н
см	Н	И	Н	Н
М	Н	Н	Н	Н

Транзакции

Имеется 4 транзакции процессора и 2 транзакции шины.

Чтение процессора (PrRd) : это происходит, когда процессор завершает успешное чтение определенного блока кэша, помещенного в его кэш.

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

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

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

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

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

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

также Общая строка необходима для указания того, доступен ли определенный блок кэша в нескольких кэшах. Это необходимо, поскольку один из кэшей может удалить блок без необходимости обновления других блоков. Общая линия помогает уменьшить количество транзакций памяти и шины в некоторых случаях, когда блок доступен только в одном кэше и, следовательно, обновление шины не требуется. Такая выделенная линия для обнаружения совместного использования используется в протоколах обновления записи, таких как протокол Firefly , и реализована на основе стандартов шины, таких как Futurebus (стандарт IEEE P896.1). ^[2]

Переходы

Переходы, инициируемые процессором

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

Когда происходит промах чтения процессора ( PrRdMiss ), а блок кэша не используется совместно, состояние переходит в монопольное.
Когда происходит промах чтения процессора ( PrRdMiss ) и блок кэша является общим, состояние переходит в состояние Shared Clean.
Когда происходит ошибка записи процессора ( PrWrMiss ) и блок кэша является общим, состояние переходит в Shared Modified , и процессор становится владельцем.
Когда происходит ошибка записи процессора ( PrWrMiss ), а блок кэша не используется совместно, состояние переходит в «Изменено».
При попадании операции чтения процессора ( PrRd ) состояние блока кэша не меняется и сохраняется значение. Это связано с тем, что это всего лишь команда чтения, которая не генерирует никаких транзакций шины.
Если блок кэша находится в состоянии «Изменено» , и процессор записывает ( PrWr ) блок, перехода нет, поскольку блок не используется совместно.
Когда блок кэша находится в состоянии Shared Modified и процессор осуществляет запись ( PrWr ), но общая строка не утверждается, состояние переходит в Modified .
Если блок кэша находится в состоянии Shared Modified , когда происходит запись ( PrWr ) и активируется общая линия, обновление шины ( BusUpd ) для обновления другого блока кэша. генерируется
Если блок кэша находится в состоянии Shared Clean , когда происходит запись ( PrWr ) и утверждается общая линия, генерируется обновление шины ( BusUpd ) для обновления другого блока кэша, и состояние меняется на Shared Modified .
Но если блок кэша находится в состоянии Shared Clean , когда происходит запись ( PrWr ), но общая линия не утверждается, состояние переходит в Modified и транзакции шины не генерируются.
Когда блок находится в состоянии Exclusive и процессор записывает в него ( PrWr ), он будет изменен на состояние Modified .

Переходы, инициируемые шиной

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

Если блок кэша находится в состоянии Modified и операция чтения по шине ( BusRd выдается ), выдается Flush для обновления основной памяти и переход состояния в Shared Modified , поскольку блок теперь находится в нескольких кэшах.
Если блок кэша находится в состоянии Shared Modified и выполняется чтение по шине ( BusRd ), выдается Flush для обновления основной памяти, и состояние остается прежним.
Если блок кэша находится в состоянии Shared Modified и выдается транзакция обновления шины ( BusUpd ), состояние переходит в Shared Clean , все кэши обновляются.
Если блок кэша находится в состоянии Shared Clean и получает чтение по шине ( BusRd ) или обновление шины ( BusUpd ), он продолжает сохранять свое состояние, поскольку значение все еще является общим. Однако в случае обновления оно обновит значение в блоке кэша.
Если блок кэша находится в состоянии Exclusive и шина считывает значение ( BusRd ), состояние перейдет в Shared Clean, поскольку блок больше не находится только в одном кэше.

Варианты дизайна низкого уровня

Устранение состояния Shared-modified

Процессор с блоком кэша в состоянии Sm отвечает за обновление основной памяти при замене блока кэша. Но если основная память обновляется всякий раз, когда происходит транзакция обновления шины, нет необходимости в отдельных состояниях Sm и Sc, и протокол может позволить себе одно общее состояние. Однако это вызывает гораздо больше транзакций с памятью. ^[3] что может замедлить работу системы, особенно когда несколько процессоров записывают в один и тот же блок кэша.

Трансляция замены блока Sc

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

Сравнения

Дракон против протоколов записи недействительных

Write Invalidate — это еще один набор протоколов согласованности кэша , в которых после изменения блока кэша другие значения того же блока в других кэшах не обновляются, а становятся недействительными. ^[4] Протоколы аннулирования записи более эффективны в случаях, когда происходит много последующих записей в один и тот же блок кэша, поскольку аннулирование происходит один раз, и дальнейшие транзакции шины со стороны других процессоров избегаются. Однако протокол обновления записи более эффективен в тех случаях, когда за записью в блок следует несколько операций чтения в один и тот же блок. Поскольку мы обновляем другие кэшированные значения после их записи, они сразу же получают доступ к данным. В таком случае. Протокол отмены записи крайне невыгоден, поскольку каждый раз, когда блок кэша изменяется в другом кэше, остальные необходимые кэши будут сталкиваться с промахом когерентности и инициировать транзакцию шины для чтения нового значения. Напротив, протокол обновления записи имеет тенденцию иногда сохранять значения блока обновленными дольше, чем необходимо, что приводит к увеличению других типов промахов, то есть конфликтов и промахов емкости .

Протокол Дракон против Светлячка

В случае Firefly передача измененных блоков из кэша в кэш также одновременно записывается обратно в основную память. Но поскольку доступ к основной памяти происходит на порядки медленнее по сравнению с кэшами, требуется дополнительная сложность выполнения обратной записи как отдельной операции шины. В любом случае это приводит к снижению производительности. ^[5] Эта проблема полностью исключена в случае протокола Dragon, поскольку общие блоки вообще не записываются обратно в память. Однако за это приходится платить одним добавленным состоянием (Shared-modified).

Ссылки

^ Аткинсон, Рассел Р.; МакКрайт, Эдвард М. (1 января 1987 г.). «Процессор дракона». Материалы второй международной конференции по Архитектурной поддержке языков программирования и операционных систем . АСПЛОС II. Лос-Аламитос, Калифорния, США: Издательство IEEE Computer Society Press. стр. 65–69. дои : 10.1145/36206.36185 . ISBN 978-0818608056 . S2CID 7019821 .
^ Стенстрём, Пер (1 июня 1990 г.). «Обзор схем когерентности кэша для мультипроцессоров». Компьютер . 23 (6): 12–24. дои : 10.1109/2.55497 . ISSN 0018-9162 .
^ Каллер, Дэвид; Сингх, Джасвиндер Пал; Гупта, Ануп (1999). Архитектура параллельных компьютеров, 1-е издание | Дэвид Каллер, Джасвиндер Пал Сингх, Ануп Гупта | , Галф Профессионал. ISBN 9781558603431 . Проверено 24 октября 2016 г. {{cite book}}: |website= игнорируется ( помогите )
^ Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Чепмен и Холл/CRC. стр. 205–206, 231–232. ISBN 9781482211184 .
^ Арчибальд, Джеймс; Баер, Жан-Лу (1 сентября 1986 г.). «Протоколы когерентности кэша: оценка с использованием многопроцессорной имитационной модели» . АКМ Транс. Вычислить. Сист . 4 (4): 273–298. дои : 10.1145/6513.6514 . ISSN 0734-2071 . S2CID 713808 .

См. также

[1] Аткинсон, Рассел Р.; МакКрайт, Эдвард М. (1 января 1987 г.). «Процессор дракона». Материалы второй международной конференции по Архитектурной поддержке языков программирования и операционных систем . АСПЛОС II. Лос-Аламитос, Калифорния, США: Издательство IEEE Computer Society Press. стр. 65–69. дои : 10.1145/36206.36185 . ISBN 978-0818608056 . S2CID 7019821 .

[2] Стенстрём, Пер (1 июня 1990 г.). «Обзор схем когерентности кэша для мультипроцессоров». Компьютер . 23 (6): 12–24. дои : 10.1109/2.55497 . ISSN 0018-9162 .

[3] Каллер, Дэвид; Сингх, Джасвиндер Пал; Гупта, Ануп (1999). Архитектура параллельных компьютеров, 1-е издание | Дэвид Каллер, Джасвиндер Пал Сингх, Ануп Гупта | , Галф Профессионал. ISBN 9781558603431 . Проверено 24 октября 2016 г. {{cite book}}: |website= игнорируется ( помогите )

[4] Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Чепмен и Холл/CRC. стр. 205–206, 231–232. ISBN 9781482211184 .

[5] Арчибальд, Джеймс; Баер, Жан-Лу (1 сентября 1986 г.). «Протоколы когерентности кэша: оценка с использованием многопроцессорной имитационной модели» . АКМ Транс. Вычислить. Сист . 4 (4): 273–298. дои : 10.1145/6513.6514 . ISSN 0734-2071 . S2CID 713808 .

[1]

[2]

[3]

[4]

[5]