Cache-coherency #1: Basics, MSI

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

Что такое когерентность кэшей (cache coherence)? Это (применительно к многопроцессорным системам с кэш-памятью) свойство согласованности данных, вообще говоря разбросанных по различным кэшам. Очевидно, что если у нас одни и те же данные могут быть скэшированы в кэш-памяти разных уровней, и в локальных блоках кэш-памяти разных процессоров/ядер -- при модификации этих данных легко может случиться, что существует множество несогласованных версий одних и тех же данных. Можно, конечно, возложить обязанность разруливать все эти конфликты на программиста -- но это слишком жестоко. Поэтому производители процессоров обычно реализуют какой-либо аппаратный механизм поддержания согласованности данных различных кэшей между собой, и с основной памятью. Где-то (как например на Интеллах) этот протокол весьма функционален, и делает для программиста почти все, кроме, разве что, минета. Где-то (тут я затрудняюсь с точными примерами, на ум приходят только ARM и почившая Alpha) заметная часть работы возложена на программиста (или компилятор) -- от него требуется явно расставлять в коде инструкции барьеров памяти, форсирующие синхронизацию данных.

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

Возможных вариантов организации когерентности -- пруд пруди. Поскольку меня интересуют многоядерные системы -- я буду рассматривать наиболее часто используемую здесь реализацию когерентности через "подслушивание" (snooping).

Что такое подслушивание (snooping): у нас есть общая шина, к которой подключены кэши всех ядер, и к ней же подключен контроллер основной памяти (InterConnect -- это как раз она). Любые запросы отправляются бродкастом на шину, и видны (слышны?) всем участникам вечеринки сразу. Принципы коммуникации через шину:

1. Шина считается надежной средой -- т.е. нет никаких циклов запрос-подтверждение. Если я запустил по шине какую-то транзакцию, и она завершилась -- значит все участники ее видели, и все с ней согласны. Не возможна ситуация, что кто-то мог не получить сообщение, или кто-то мог не успеть ответить. Разумеется, это все с точки зрения высокоуровневых протоколов -- на уровне реализации в железе, возможно, такие циклы и есть, но с этим уровнем я не знаком. При этом, все-таки, довольно очевидно, что это свойство ограничивает масштабируемость snoop-based систем поддержания когерентности -- реализовать надежный протокол без подтверждений в больших масштабах будет сложно.
2. "It's more blessed to ask forgiveness then permission": если я хочу что-то сделать, я не спрашиваю остальных участников "согласны ли вы?" -- я просто начинаю транзакцию, реализующую мое намерение. Начатую мной транзакцию видят все участники, поэтому если кто-то из них имеет что-то сказать против -- он прерывает транзакцию, и начинает свою. Влезать в чужую транзакцию -- это вполне регулярный элемент протоколов кэш-когерентности.
3. При этом все участники действуют все-таки кооперативно -- например, "протестующий" участник не тянет тупо одеяло на себя, а помогает исходной транзакции, которую он прервал -- просто выполняя свою дополнительную транзакцию, он в чем-то подправляет исходную. Другой пример: если я прервал чью-то транзакцию, все участники коммуникации полагают, что мне есть что сказать важного, поэтому, на ближайший такт все (кроме меня) добровольно замолкают, давая мне возможность спокойно высказаться.

MSI: plain and easy

Придумать протокол поддержания когерентности начального уровня не так уж сложно. Особенно это становится просто, когда знаешь ответ. Сколько состояний элементарного блока данных (такой блок называется cache line -- строка кэша) нам нужно для самого минимального протокола кэш-когерентности? Как минимум, нам нужна возможность различать, когда строка в моем локальном кэше "свежая" (т.е. ее содержимое не отличается от содержимого основной памяти), и когда она "несвежая" (изменена мною, и еще не синхронизирована с памятью). Отсюда мы и будем плясать.

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

В протоколе MSI принято решение разрубить этот гордиев узел на корню -- мы просто не допускаем такой ситуации. А именно -- Modified это по смыслу Exclusive Modified, и конкретная строка кэша в каждый момент времени может быть в таком состоянии не более чем в одном из кэшей. Другими словами: если я вижу в кэше процессора №2 строку №42 со статусом M -- я могу утверждать, что сейчас больше ни в чьем другом кэше строка №42 не скэширована.

Теперь мы можем перейти к первому состоянию -- когда строка "свежая", не модифицированная. Или, что то же самое, ее содержимое совпадает с содержимым основной памяти. Это состояние (неожиданно) называется S(hared). Почему "разделяемое"? -- потому что в этом состоянии есть важное свойство: строка с таким состоянием может быть свободно скэшированной в хоть во всех кэшах сразу. Что дает возможность эффективно читать одни и те же данные хоть всем ядрам одновременно, не мешая друг другу -- просто каждый получит свою копию в своем персональном кэше. Это свойство "разделяемости" для нас очень важно, поэтому и Shared, а не, скажем, Clean (хотя можно читать и как Sync'ed, при желании).

Третье, и последнее состояние -- I(nvalid). Это, по смыслу, просто отсутствие такой строки в кэше. Флаг "removed".

MSI в движении

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

...Итак, процессор №1 делает запрос на блок данных №42. Его локальный кэш обнаруживает, что таких данных в нем нет (либо нет вообще, либо они есть в состоянии Invalid). Кэш открывает на шине транзакцию "дайте мне кто-нибудь блок данных №42". Если больше ни у кого этот блок не скэширован, то на запрос отвечает основная память -- просто пересылает ему нужный блок. То же самое происходит, если блок у кого-нибудь скэширован, и находится в состоянии Shared: на запрос по-прежнему отвечает основная память, остальные участники молчаливо со всем соглашаются.

Жизнь становится чуть сложнее, если блок есть у кого-нибудь в состоянии Modified. Если процессор №2, слушая шину, видит на ней транзакцию чтения строки, которая у него в состоянии M -- он отменяет транзакцию (посылает на шину всем стоять, трамвай, прижаться к стенке #ABORT). Транзакция чтения отменяется, в следующий такт (в который -- помните? -- все остальные будут вежливо молчать) процессор №2 начинает процедуру write-back -- транзакцию сохранения измененных им данных в основную память. Завершив ее, процессор №2 изменит состояние своей копии строки №42 на Shared. Процессор №1, дождавшись освобождения шины, повторит запрос на чтение строки №42 -- и теперь уже беспрепятственно получит ее от основной памяти (т.е. мы возвращаемся к предыдущему абзацу).

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

Отдельного внимания достоин вопрос о том, когда же я все-таки сброшу свои M-строки в основную память. Один из таких случаев рассмотрен выше -- я вынужден это сделать немедленно, если кто-то другой потребует модифицированные мною данные. Другой, довольно очевидный случай -- когда строка будет вытесняться из кэша другими данными (кэш-то, увы, не резиновый). Собственно, в простейшем варианте этих двух триггеров достаточно. Как видно, мы стараемся отложить запись в основную память насколько возможно. Такая стратегия называется "отложенная запись" (write back). Есть более раритетная стратегия "сквозной записи" (write through) -- при этом каждая запись в кэш сразу же дублируется в основную память. Сейчас, насколько мне известно, этот способ почти не применяется

Вернемся к модификации -- она чуть сложнее, если строка у меня в данный момент в состоянии Shared. Тогда я уже не могу быть уверен, что ее больше нет ни у кого (S это не "гарантированно shared", это "может быть shared"). Поэтому я вынужден, на всякий случай, оповестить всех о своих гнусных планах испортить девственно чистую строку: я объявляю по шине что-то вроде "я модифицирую строку №42". Если у кого-то эта строка есть (а если она есть -- она может быть только тоже в Shared) -- эти кэши, услышав мое оповещение, переводят ее в Invalid (==удаляют).

Последний вариант: если строки в моем кэше еще вообще нет. Простейшим способом здесь будет вылить чайник на плиту и свести задачу к предыдущей: начать так же, как в случае чтения, получить строку в S, и потом, отдельной транзакцией, перевести ее в M.

Собственно, на этом про MSI, в его простейшем варианте -- все. Продолжение (MESI, MESIF, MOESI) в следующих сериях...


UPD:

А, собственно, зачем нам что-то лучшее?

Недостатков и возможностей оптимизации в описанной версии протокола -- не счесть. Для затравки -- парочка самых интересных.

Во-первых, передача строки из одного кэша в другой получается нерационально дорогой. Пусть у нас есть простейшая модель Поставщик-Потребитель, когда один процессор пишет данные в какую-то область памяти, а второй их оттуда читает. Как эта штука будет выглядеть с точки зрения протокола: сначала Поставщик затребует себе строку в S, потом объявит по шине что хочет перевести ее в M, потом запишет в нее данные. Затем Потребитель дойдет до этого же участка памяти, запросит строку из памяти. Поставщик вмешается, и отменит транзакцию чтения, взамен ее запустит транзакцию сброса своей строки в основную память. Потребитель дожидается окончания этой транзакции, запрашивает данные из памяти -- и получает их в Shared. Итого: 5 транзакций, из них 2 чтения из основной памяти и одна запись в нее. При этом легко себе представить идеальный протокол, который, в этом случае, потребует одного чтения, одной пересылки кэш-кэш, и одной записи в основную память, отложенной на неопределенное время.

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