Реферат: Механизм когерентности обобщенного кольцевого гиперкуба с непосредственными связями

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

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

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

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

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

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

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

Для поддержки когерентности строк кэш-памяти при операциях вво­да/вывода и обращениях в основную память других процессоров на шине генерируются специальные циклы опроса состояния кэш-памятей. Эти циклы опрашивают кэш-памяти на предмет хранения в них строки, ко­торой принадлежит адрес, используемый в операции, инициировавшей циклы опроса состояния. Возможен режим принудительного перевода строки в состояние I, который задается сигналом INV.

1.2.2.2. Физически распределенная память

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

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

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

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

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

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

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

в каком-либо модуле.

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

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

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

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

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

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

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

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

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

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

1.3. КС типа обобщенного кольцевого гиперкуба

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

Для простоты понимания будем рассматривать частный случай – трехмерную среду с кольцевыми связями. Каждый узел представляет собой совокупность двух процессоров – обрабатывающего и коммуникационного. Обрабатывающий процессор – это общее понятие, под которым понимается любое устройство обработки информации, но которое не может осуществить самостоятельную передачу данных в среде. А коммуникационный процессор является инструментом для обрабатывающего процессора, предоставляющим ему возможность осуществить обмен информацией с другими узлами среды.

Каждый узел среды имеет 6 двунаправленных каналов ввода/вывода, которые используются в качестве непосредственных связей с соседними узлами (Рис.1). Возможно, применение двух встречных однонаправленных каналов вместо одного двунаправленного, что позволяет увеличить пропускную способность при незначительном увеличении аппаратных затрат. Каждый узел также имеет 6 магистральных каналов ввода/вывода – по два в каждом измерении. Коммуникационный процессор производит прием/передачу информации по каналам ввода/вывода, причем может использоваться как коммутация пакетов, так и коммутация каналов.

1.3.1. Расчет параметров