Асинхронное параллельное выполнение блоков
Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

 

Рассмотрим препятствия, которые могут возникнуть при преобразовании блоков в параллельные процессы.

       Распараллеливание блоков является более общим преобразованием по отношению к распараллеливанию циклов. Действительно, при распараллеливании циклов параллельно выполняются итерации циклов. Но итерации циклов можно рассматривать, как блоки.

       При распараллеливании блоков возникает задача выделения в программе тех блоков, которые могли бы выполняться параллельно. Для повышения параллельности можно рассматривать задачу разбиения больших программных блоков на более мелкие блоки. С другой стороны, чтобы не тратить время на частые инициализации параллельных процессов, можно некоторые мелкие блоки склеивать в более крупные. Чтобы параллельно работающие процессоры были равномерно загружены, можно решать задачу загрузочного баланса (load balancing).

Для преобразования в процесс блок должен иметь один вход. Чтобы два блока могли параллельно выполняться, они должны быть независимы по управлению. Например, один блок не может быть вложен в другой, не должно быть перехода (условного или безусловного) из одного блока в другой. Для того чтобы два блока могли выполняться параллельно, необходимо, чтобы они в программе были связаны по управлению конкатенацией.

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

 

Пример 270.

 

for(i=1; i <= N; ++i)

{

a = a+b[i]*c[i]

}

If eps < 0 then

for(j=1; j <= M; ++j)

{               

x = x+e[j]*d[j];

}

else

x = a

 

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

 

for(i=1; i <= N; ++i)

{

a = a+b[i]*c[i]

}

for(j=1; j <= M; ++j)

{

x = x+e[j]*d[j];

}

If eps < 0 then

{

}

else

x = a

 

       Конец примера.

 

Граф информационных связей может установить зависимости по данным между вхождениями переменных в блоки.

 

Теорема 58 . Пусть задано гнездо циклов вида

 

for(j1=1; j1 <= M1; ++j1)

for(j2=1; j2 <= M2; ++j2)

   …       

for(jn=1; jn <= Mn; ++jn)

{               

B1(j1,j2,…,jn)

B2(j1,j2,…,jn)

}

 

Предположим, что каждый из блоков B1 и B2 имеет один вход и один выход (в частности, между этими блоками нет условных или безусловных переходов) и между этими блоками нет информационных зависимостей с носителем jn. Тогда асинхронное вычисление этих блоков эквивалентно их последовательному вычислению. 

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

 

Замечание. Можно допустить между блоками B1 и B2 входные циклически независимые зависимости с носителем jn. При наличии общей памяти это никак не повлияет на результат вычислений. При наличии распределенной памяти входные зависимости предполагают предварительные пересылки данных.

 

Теорема 59 . Предположим, что в программе оператор S1 является доминатором оператора S2. Тогда замена оператора S2 блоком {Wait(S1), S2} является эквивалентным преобразованием.

Доказательство. Ясно, что в преобразованной программе S1 является доминатором блока {Wait(S1), S2}. Поэтому, всякий раз, когда при исполнении программы этому блоку будет передаваться управление, оператор S1 уже будет выполнен. Следовательно, оператор Wait(S1) можно заменить пустым оператором и удалить.

 

Теорема 60 . Предположим, что программа F представляет собой конкатенацию фрагментов (блоков) F = { F1 , F2 , … , Fr } и внутри каждого фрагмента нет операторов передачи управления за пределы этого фрагмента. Пусть G – граф зависимости по данным программы F. Построим новую программу F_new, состоящую из новых фрагментов Fi_new, I = 1, 2, …, r, которая будет выполняться параллельно. Для этого, для каждой дуги (S1, S2) графа зависимостей по данным G, такой, что S1 и S2 принадлежат разным фрагментам Fi и Fj , заменим оператор S2 на блок из двух операторов {Wait(S1), S2}. Тогда параллельное асинхронное выполнение фрагментов программы F_new = { F1_new, F2_new, … , Fr_new } эквивалентно последовательному выполнению программы F. 

       Доказательство. Сначала заметим, что последовательное выполнение программы F равносильно последовательному выполнению программы F_new. Отметим, что операторы Wait() не меняют состояние памяти; эти операторы могут только привести к изменению времени исполнения программы, в частности, к тому, что программа не завершится. Теперь отметим, что всякий оператор S2 не выполнится раньше, чем любой такой оператор S1, из которого в S2 направлена дуга графа зависимостей по данным. Но тогда выполняются условия теоремы о перестановке семейства операторов, из которой и вытекает эквивалентность фрагментов F_new и F. 

 

Пример 271. В следующем гнезде циклов между двумя блоками не имеется зависимостей с носителем – самым вложенным циклом. Эти блоки могут выполняться асинхронно. 

 

for(i=1; i <= N; ++i)

for(j=1; j <= M; ++j)

{               

{               

X[j] = Y[i-1,j]*Z[i-1]

}

{               

Y[i,j] = Y[i,j-1]*D[j];

Z[i] = 1

}

}

 

Конец примера.

 

 

Дата: 2018-12-21, просмотров: 284.