Пусть мультикомпьютер выполняет некоторое множество параллельных программ 
. В каждой программе 
имеется множество ветвей (участков) 
, которые находятся в отношениях параллельности, альтернативы либо предшествования (следования). Формально состояние ветви 
задается индикаторной функцией 
такой, что: 
, если ветвь 
в момент 
активна (т. е. выполняется некоторым модулем 
), 
в противном случае.
Пусть 
– множество барьеров программы 
. Обозначим через 
множество ветвей, сходящихся в барьере 
. Определим для каждого барьера 
индикаторную функцию 
, удовлетворяющую следующим условиям: 
, если хотя бы одна ветвь 
в момент 
активна, 
иначе, полагая 
. Ясно, что 
.
Синхронизация ветвей 
считается обеспеченной, если в некоторый момент 
, 
, выполняется условие синхронизации:
, (1)
где запись 
(
) означает переход значения функции из 0 в 1 (из 1 в 0).
Учитывая возможность циклического выполнения барьеров, необходимо, чтобы после достижения условия синхронизации выполнялось следующее условие восстановления:
. (2)
Временные интервалы формирования условий (1) и (2) называются соответственно фазой синхронизации и фазой восстановления.
Каждому процессорному модулю 
сопоставляется двоичный вектор 
, устанавливающий соответствие между модулями и барьерами данной программы. Назовем 
вектором соответствия:
,
где n – число физических слоев (разрядность) координирующей среды, а p – число виртуальных слоев в каждом физическом слое (глубина виртуализации ВМКС), причем 
, если за модулем 
закреплена ветвь программы, завершающаяся барьером 
, в противном случае 
(в этом случае модуль 
не должен оказывать влияния на процесс синхронизации ветвей, сходящихся в барьере 
).
Пусть 
– некоторая ветвь, назначенная на модуль 
. Тогда состояние модуля 
по отношению к барьеру 
представляется следующим образом:
, (3)
где 
. Тогда согласно формуле (3) условие синхронизации (1) будет обеспечено в момент 
завершения последней ещё не завершенной ветви множества 
, назначенной на некоторый модуль 
: 
.
Таким образом, для обеспечения синхронизации в ОММК необходимо вычисление множества индикаторных функций 
для всех барьеров по текущим значениям признаков 
и оперативная рассылка «уведомлений» о наступлении события 
всем модулям, ожидающим завершение барьера 
.
Топология физического слоя ВМКС определяется по следующим правилам. Пусть 
– физический слой координирующей среды, 
, и 
– множество его ячеек. Ячейку слоя 
, соответствующую модулю 
, условно обозначим как 
. Введем на множестве ячеек 
координирующей среды сети синхронизации 
и восстановления 
соответственно. Вершины, соответствующие ячейкам 
и 
, свяжем в сетях 
и 
дугами, если и только если соответственно:
;
.
Сети 
и 
определяют порядок распространения условий (1) и (2) в слое 
соответственно. На рис. 1 в качестве иллюстрации представлены сети 
и 
для двумерного матричного мультикомпьютера.
|
|
Рис. 1. Сети синхронизации (а) и восстановления (б) слоя 
двумерного ОММК
Логика функционирования ячеек 
в фазе синхронизации определяется выражением
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
