Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Штаты [ править ]

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

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

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

 E  Sc  См  M 
 E Красный XNКрасный XNКрасный XNКрасный XN
 Sc Красный XNЗеленая галочкаYЗеленая галочкаYКрасный XN
 См Красный XNЗеленая галочкаYКрасный XNКрасный XN
 M Красный XNКрасный XNКрасный XNКрасный XN

Транзакции [ править ]

Есть 4 транзакции процессора и 2 транзакции шины.

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

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

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

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

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

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

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

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

Переходы [ править ]

Протокол Dragon - транзакции, инициированные процессором

Переходы, инициированные процессором [ править ]

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

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

Переходы, инициированные шиной [ править ]

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

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

Выбор дизайна низкого уровня [ править ]

Устранение состояния Shared-Modified [ править ]

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

Трансляция замены блока Sc [ править ]

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

Сравнения [ править ]

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

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

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

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

Ссылки [ править ]

  1. ^ Аткинсон, Рассел Р .; МакКрайт, Эдвард М. (01.01.1987). Процессор Dragon . Труды Второй Международной конференции по архитектурной поддержке языков программирования и операционных систем . АСПЛОС II. Лос-Аламитос, Калифорния, США: IEEE Computer Society Press. С. 65–69. DOI : 10,1145 / 36206,36185 (неактивный 2021-01-10). ISBN 978-0818608056.CS1 maint: DOI неактивен с января 2021 г. ( ссылка )
  2. ^ Штенштрём, Per (1990-06-01). «Обзор схем когерентности кэша для мультипроцессоров». Компьютер . 23 (6): 12–24. DOI : 10.1109 / 2.55497 . ISSN 0018-9162 . 
  3. ^ Каллер, Дэвид; Сингх, Джасвиндер Пал; Гупта, Ануп (1999). Архитектура параллельного компьютера, 1-е издание | Дэвид Каллер, Джасвиндер Пал Сингх, Ануп Гупта | . store.elsevier.com . ISBN 9781558603431. Проверено 24 октября 2016 .
  4. ^ Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Чепмен и Холл / CRC. С. 205–206, 231–232. ISBN 9781482211184.
  5. ^ Арчибальд, Джеймс; Баер, Жан-Лу (1986-09-01). «Протоколы согласованности кэша: оценка с использованием модели многопроцессорного моделирования». ACM Trans. Comput. Syst . 4 (4): 273–298. DOI : 10.1145 / 6513.6514 . ISSN 0734-2071 . S2CID 713808 .  

См. Также [ править ]

  • Протокол согласованности
  • Протокол Firefly
  • Протокол MESI
  • Протокол MOSI
  • Протокол MOESI
  • Протокол MESIF