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