Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Асинхронное параллельное выполнение блоков



 

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

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

       При распараллеливании блоков возникает задача выделения в программе тех блоков, которые могли бы выполняться параллельно. Для повышения параллельности можно рассматривать задачу разбиения больших программных блоков на более мелкие блоки. С другой стороны, чтобы не тратить время на частые инициализации параллельных процессов, можно некоторые мелкие блоки склеивать в более крупные. Чтобы параллельно работающие процессоры были равномерно загружены, можно решать задачу загрузочного баланса (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

}

}

 

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

 

 

Асинхронное распараллеливание циклов с независимыми итерациями

 

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

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

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

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

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

 

Пример 272. В данном примере имеются циклически порожденные зависимости относительно внешнего цикла.

 

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

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

{    

a[j] = b[i, j]*c[i, j]

x[i, j] = a[j]*d[i, j];

}

 

Повышение размерности массивов удаляет циклически порожденные зависимости и приводит внешний цикл к параллельно выполняемому виду.

 

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

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

{               

aa[i, j] = b[i, j]*c[i, j]

x[i, j] = aa[i, j]*d[i, j];

}

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

{               

   a[j] = aa[N, j];

}

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

 

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

           

Пример 273. Предположим, что вычислительная архитектура имеет p асинхронно работающих вычислительных устройств и пусть N = p*R. Рассмотрим фрагмент кода из предыдущего примера

 

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

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

{               

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

x[i, j] = a[j]*d[i, j];

}

 

Выполнив гнездование внешнего цикла, получим следующий фрагмент

 

for(k=1; k < = p; ++k)

for(l=1; l < = R; ++l)

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

{               

i = (k-1)*R+l

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

  x[i, j] = a[j]*d[i, j];

}

 

Теперь к внешнему циклу можно применить повышение размерности массивов

 

for(k=1; k < = p; ++k)

for(l=1; l < = R; ++l)

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

{               

i = (k-1)*R+l

aa[k, j] = aa[k, j]+b[i, j]*c[i, j]

x[i, j] = aa[k, j]*d[i, j];

}

 

В данном примере, в отличие от предыдущего, первая координата массива aa имеет длину p, а не N.

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

 

 


Поделиться:



Последнее изменение этой страницы: 2019-05-17; Просмотров: 425; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.036 с.)
Главная | Случайная страница | Обратная связь