Механизмы неявной реализации когерентности

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

1.2.1. Однопроцессорный подход

Наиболее часто используются три способа организации кэш-памяти, отличающиеся объемом аппаратуры, требуемой для их реализации: кэш-память с прямым отображением, частично ассоциативная кэш-память и ассоциативная кэш­память.

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

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

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

Реализация механизма когерентности чаще всего осуществляется с использованием отслеживания (snooping) запросов на шине, связывающей процессор, память и интерфейс ввода/вывода. Контроллер кэша отслеживает адреса памяти, выдаваемые процессором, и если адрес соответствует данным, содержащимся в одной из строк кэша, то отмечается "попадание в кэш", и данные из кэша направляются в процессор. Если данных в кэше не оказывается, то фиксируется "промах" и инициируются действия по доставке в кэш из памяти требуемой строки.

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

При выводе данных на внешнее устройство также необходимо отслеживать на шине выдачи данных с соблюдением когерентности данных основной памяти и кэш­памяти.

1.2.2. Многопроцессорный подход

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

1.2.2.1. Сосредоточенная память

Первый алгоритм поддержки когерентности кэшей - MESI (Modified, Exclusive, Shared, Invalid), представляет собой организацию когерентности кэш-памяти с обратной записью. Этот алгоритм предотвращает лишние передачи данных между кэш-памятью и основной памятью. Так, если данные в кэш-памяти не изменялись, то незачем их пересылать.

Каждый ВМ имеет собственную локальную кэш-память, имеется общая разделяемая основная память, все ВМ подсоединены к основной памяти посредством

шины.шине подключены также внешние устройства. Все действия с

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

Каждая строка кэш-памяти ВМ может находиться в одном из следующих состояний:

М - строка модифицирована (доступна по чтению и записи только в этом ВМ, потому что модифицирована командой записи по сравнению со строкой основной памяти);

Е - строка монопольно копированная (доступна по чтению и записи в этом ВМ и в основной памяти);

S - строка множественно копированная или разделяемая (доступна по чтению и записи в этом ВМ, в основной памяти и в кэш-памятях других ВМ, в которых содержится ее копия);

I - строка, невозможная к использованию (строка не доступна ни по чтению, ни по записи).

Состояние строки используется, во-первых, для определения процессором ВМ возможности локального, без выхода на шину, доступа к данным в кэш-памяти, а, во-вторых, — для управления механизмом когерентности.

Для управления режимом работы механизма поддержки когерентности используется бит WT, состояние 1 которого задает режим сквозной записи, а состояние 0 - режим обратной записи в кэш-память.

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

Промах чтения в кэш-памяти заставляет вызвать строку из основной памяти и сопоставить ей состояние Е или S. Кэш-память заполняется только при промахах чтения. При промахе записи транзакция записи помещается в буфер и посылается в основную память при предоставлении шины.

При несостоятельной строке в состоянии I команда чтения данного из этой строки вызывает чтение строки из основной памяти, размещение ее в кэш-памяти и изменение состояния этой строки в кэш-памяти на Е или S. Состояние Е будет, если установлен режим сквозной записи, при котором запись производится и в строку кэш-

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

При состоянии I строки команда записи в эту строку изменяет только содержимое строки основной памяти (сквозная запись), но не изменяет содержимое кэш-памяти и сохраняет состояние строки I.

В состоянии S строки чтение данного из этой строки не меняет ее состояние. Если установлен режим сквозной записи, то после завершения записи состояние строки меняется на Е, при режиме обратной записи выполняется сквозная запись, но состояние строки остается прежним S.

Если состояние строки Е, то чтение сохраняет это состояние, а запись переводит строку в состояние М.

Наконец, если состояние строки М, то как команды чтения, так и команды записи не меняют этого состояния.

Конец лекции X

^№1° / 1.2.2.2. Физически распределенная память

v Прямолинейный подход к поддержанию когерентности кэшей в мультипроцессорной системе, основная память которой распределена по ВМ, заключается в том, что при каждом промахе в кэш в любом процессоре инициируется запрос требуемой строки из того блока памяти, в котором эта строка размещена. В дальнейшем этот блок памяти будет по отношению к этой строке называться резидентным. Запрос передается через коммутатор в модуль с резидентным для строки блоком памяти, из которого затем необходимая строка через коммутатор пересылается в модуль, в котором произошел промах. Таким образом, в частности, обеспечивается начальное заполнение кэшей. При этом в каждом модуле для каждой резидентной строки ведется список модулей, в кэшах которых эта строка размещается, либо организуется распределенный по ВМ список этих строк. Строка, размещенная в кэше более чем одного модуля, в дальнейшем будет называться разделяемой.

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

На практике применяют более сложные алгоритмы, обеспечивающие меньшие простои процессоров, например, DASH, который приведен ниже.

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

С каждой строкой в резидентном для нее модуле связаны три ее возможных глобальных состояния:

1) "некэшированная", если копия строки не находится в кэше какого-либо другого модуля, кроме, возможно, резидентного для этой строки;

2)"удаленно-разделенная", если копии строки размещены в кэшах других
модулей;

3)"удаленно-измененная", если строка изменена операцией записи

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

1)"невозможная к использованию";

2)"разделяемая", если есть неизмененная копия, которая, возможно,
размещается также в других кэшах;

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

Если глобальное состояние строки в резидентном модуле "некэшированная" или "удаленно-разделенная", то копия строки посылается в запросивший модуль и в список модулей, содержащих копии рассматриваемой строки, вносится модуль, запросивший копию.

Если состояние строки "удаленно-измененная", то запрос "промах чтения" перенаправляется в модуль, содержащий измененную строку. Этот модуль пересылает требуемую строку в запросивший модуль и в модуль, резидентный для этой строки, и устанавливает в резидентном модуле для этой строки состояние "удаленно-распределенная".

Если процессор выполняет операцию записи и состояние строки, в которую производится запись "измененная", то запись выполняется и вычисления продолжаются. Если состояние строки "невозможная к использованию" или "разделяемая", то модуль посылает в резидентный для строки модуль запрос на захват в исключительное использование этой строки и приостанавливает выполнение записи до получения подтверждений, что все остальные модули, разделяющие с ним рассматриваемую строку, перевели ее копии в состояние "невозможная к использованию".

Если глобальное состояние строки в резидентном модуле "некэшированная", то строка отсылается запросившему модулю, и этот модуль продолжает приостановленные вычисления.

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

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