Firefly (протокол согласованности кэша)

Протокол Firefly когерентности кэша — это схема, используемая в многопроцессорной рабочей станции DEC Firefly , разработанная Исследовательским центром систем DEC . Этот протокол представляет собой протокол согласованности кэша обновлений записи с тремя состояниями. В отличие от протокола Dragon , протокол Firefly обновляет основную память, а также локальные кэши при переходе шины обновления записи. Таким образом, состояния Shared Clean и Shared Modified, присутствующие в случае протокола Dragon, не различаются в случае протокола Firefly.

Штаты

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

Valid-Exclusive(V) : блок кэша действителен, чист и находится только в одном кэше.
Общий(S) : блок кэша действителен, чист и может находиться в нескольких кэшах.
Грязный(D) : Блок является единственной копией памяти и является «грязным», т.е. его значение было изменено с момента извлечения из памяти. Это единственное состояние, которое генерирует обратную запись при замене блока в кэше.

Эти состояния соответствуют состояниям Exclusive , Shared и Modified протокола MESI . Этот протокол никогда не приводит к аннулированию, поэтому состояние «Недействительно» здесь не указано.

Запросы на стороне процессора

Запросы на стороне процессора или запросы ЦП — это доступ, который процессор осуществляет к своим собственным кэшам. Их можно разделить на 4 типа запросов, а именно:

PrRdMiss : запрос на стороне процессора на чтение блока кэша, который не находится в кэше.
PrRdHit : запрос на стороне процессора на чтение блока кэша, который уже находится в кэше.
PrWtHit : запрос на стороне процессора на запись в блок кэша, который уже находится в кэше.
PrWtMiss : запрос на стороне процессора на запись в блок кэша, который не находится в кэше.

Запросы на стороне шины

Запросы на стороне шины — это запросы, генерируемые в ответ на запросы на стороне процессора для поддержания согласованности кэша. Они отслеживаются шпионом кэшей и памяти и предпринимаются соответствующие действия. В протоколе Firefly они подразделяются на два типа, а именно:

1. BusRd : запрос, указывающий, что существует запрос на чтение блока кэша, сделанный другим процессором, и этот процессор не имеет данных.

2. BusWr/BusUpdt : запрос, указывающий, что существует запрос на запись в блок кэша, сделанный другим процессором, и все остальные кэши должны обновить свои копии блока.

Переходы

Чтобы определить, какие переходы необходимо выполнить, протокол определяет совместное использование с помощью специальной линии шины с именем CopiesExist . Все остальные кэши отслеживают все операции с памятью и вызывают CopiesExist(C), если они обнаруживают «отслеживание», т. е. если у них есть копия данных в их собственном кэше.

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

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

В случае пропуска процессором чтения блока и отсутствия копии блока в каком-либо другом кэше проверяется строка CopiesExist (C) и C имеет низкий уровень, тогда блок помещается в кэш, а состояние устанавливается как Действительный. . Если в некоторых кэшах уже есть копия (C — HIGH), то блок помещается в кэш в состоянии Shared .

При промахе записи в блок, если ни в одном кэше нет копии блока (C имеет низкий уровень), блок помещается в кэш в состоянии «грязный» . Если в некоторых кэшах уже есть копия блока (C — HIGH), то блок помещается в кэш в состоянии Shared и изменения отражаются в памяти.

Если блок уже кэширован в состоянии «Действительно» , попадание записи процессора меняет состояние на состояние «Грязно» , поскольку ни в одном другом кэше нет копии данных. Эта запись не записывается в память.

Если блок кэшируется в состоянии «Грязный» и происходит попадание записи процессора, то состояние остается в состоянии «Грязный» .

Если блок находится в состоянии «Общий доступ» и произошла ошибка записи процессора, и если в некоторых кэшах уже есть копия (C), блок остается в состоянии «Общий доступ» . Если ни в одном кэше (!C) нет копии блока, блок записывается в допустимом состоянии, поскольку это единственная «действительная» копия, присутствующая в кэшах.

Если происходит попадание чтения ЦП, блок остается в том состоянии, в котором он уже находился — точно так же, как в протоколе Dragon.

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

Если блок находится в состоянии Shared и имеется запрос BusRd или BusWr, блок остается в состоянии Shared.

Если блок находится в состоянии Dirty State , а другой процессор читает или записывает его, по запросу от другого процессора он переходит в состояние Shared и изменения отражаются в основной памяти.

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

В отличие от MESI, в протоколе обновления Firefly распространение записи обеспечивается путем непосредственного обновления всех остальных копий по запросу процессоров на запись (PrWr).

Сравнение с другими политиками

1. Благодаря тому, что обновленные копии данных существуют в кэшах, промахов когерентности меньше, чем в политиках Write – Invalidate.

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

3. Обновление данных при каждой записи приводит к тому, что в кэше остаются ненужные данные, что может привести к удалению некоторых «полезных» данных.

См. также

Ссылки

Хашеми, Б. (1 мая 2011 г.). «Моделирование и оценка протоколов согласованности кэша Snoopy со стратегией обновления в многопроцессорных системах с общей памятью». 2011 Девятый международный симпозиум IEEE по параллельной и распределенной обработке с использованием приложений . Семинары. стр. 256–259. дои : 10.1109/ISPAW.2011.68 . ISBN 978-1-4577-0524-3 . S2CID 2093087 .
Эггерс, С.Дж.; Кац, Р.Х. (1 января 1988 г.). Характеристика совместного использования в параллельных программах и ее применение для оценки протокола согласованности . ИСКА '88. Том. 16. Лос Аламитос, Калифорния, США: Издательство IEEE Computer Society Press. стр. 373–382. дои : 10.1145/633625.52442 . ISBN 978-0818608612 . {{cite book}}: |journal= игнорируется ( помогите )
Арчибальд, Джеймс; Баер, Жан-Лу (1 сентября 1986 г.). «Протоколы когерентности кэша: оценка с использованием многопроцессорной имитационной модели» . АКМ Транс. Вычислить. Сист . 4 (4): 273–298. дои : 10.1145/6513.6514 . ISSN 0734-2071 . S2CID 713808 .