=Paper=
{{Paper
|id=Vol-1482/176
|storemode=property
|title=Использование последовательно-параллельного метода для распараллеливания алгоритмов с ассоциативными операциями
(Serial-parallel method using for partial associative operation parallelizing)
|pdfUrl=https://ceur-ws.org/Vol-1482/176.pdf
|volume=Vol-1482
}}
==Использование последовательно-параллельного метода для распараллеливания алгоритмов с ассоциативными операциями
(Serial-parallel method using for partial associative operation parallelizing)==
https://ceur-ws.org/Vol-1482/176.pdf
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Использование последовательно-параллельного метода для
распараллеливания алгоритмов с ассоциативными
операциями*
А.В. Фролов
ИВМ РАН
Автором исследуются возможности использования последовательно-параллельного
метода конструирования новых параллельных версий известных численных методов,
а также вопросы сбалансированности получаемых методов - как по части распреде-
ления вычислений, так и по их устойчивости.
1. Введение
Последовательно-параллельный алгоритм известен давно и используется, главным обра-
зом, как эрзац блочного метода1, там, где есть возможность использовать свойство ассоциатив-
ности операций. К последним, например, можно отнести довольно широкий класс алгоритмов,
содержащих последовательные рекуррентные вычисления с линейными и дробно-линейными
формулами. В данной статье автор исследует и предлагает использовать свойства последова-
тельно-параллельного метода для раскрытия большего потенциала параллелизма, чем обычно
принято видеть в ряде алгоритмов.
2. Последовательно-параллельный метод для алгоритмов с одним ре-
зультатом
Последовательно-параллельный алгоритм изначально придуман для таких подзадач, где из
большого поля данных нужно получить всего одно число, характеризующее всё это поле, на-
пример, одну из норм – максимальный модуль элемента или сумму модулей всех элементов. Не
будем пока конкретизировать операции, а предположим, что нужно вычислить результат
(1)
где – обозначение некой ассоциативной операции над данными некоторого типа, к кото-
рому как раз и принадлежит любой из элементов . Для вычисления этого выражения после-
довательно-параллельным методом весь диапазон натуральных чисел от 1 до n разбивается на
q промежутков – от k0=1 до k1, от k1+1 до k2, ..., от kq-1+1 до kq=n. В каждом из этих проме-
жутков выражение
(2)
вычисляется последовательно, с возрастанием индекса, а потом последовательно же вы-
числяется
(3)
При возможности деления n на количество устройств q обычно используют равномерное
разделение на промежутки. В этом случае граф получающегося алгоритма имеет вид, показан-
ный на Рис. 1. Нетрудно понять, что длина его критического пути будет равна
(4)
*
Исследование выполнено при частичной финансовой поддержке гранта Российского научного фонда
(проект N14-11-00190).
1
Полноценным блочным методом можно, на взгляд автора, считать только такой, где количество ариф-
метических операций, используемых одной блочной операцией, существенно больше, чем количество
входных и выходных данных. В последовательно-параллельном методе это не так, отсюда и использова-
ние слова "эрзац".
176
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
то есть при будет достигнут её минимум, равный
(5)
Естественно, что этот метод значительно уступает по длине критического пути графа (по
организации вычислений и передач между устройствами он всё же проще) методу сдваивания,
показанному на Рис. 1 и имеющему длину критического пути
(6)
Перед тем, как перейти к более сложным задачам, отметим для себя одну важную вещь. В случае вычис-
ления выражения (1) как последовательно-параллельный метод, так и метод сдваивания использовали
одно и то же общее количество операций , равное . Избыточных по отношению к исходному по-
следовательному алгоритму вычислений оба они не используют.
Рис. 1. Последовательно-параллельный метод для вычисления (1) через (2) и (3) при n=30
Рис. 2. Метод сдваивания для вычисления (1) при n=16
3. Последовательно-параллельный метод для алгоритмов с нужными
промежуточными результатами
Перейдём теперь к рассмотрению задачи более сложного типа. Пусть опять – обозначе-
ние некой ассоциативной операции над данными некоторого типа, к которому принадлежит
любой из элементов , и пусть нам нужно вычислить все выражения
(7)
для всех возможных значений m от 1 до n. Для решения такой задачи с помощью последо-
вательно-параллельного метода мы опять весь диапазон натуральных чисел от 1 до n разбива-
ем на q промежутков – от k0=1 до k1, от k1+1 до k2, ..., от kq-1+1 до kq=n. В каждом из этих
промежутков последовательно определяем выражения
(8)
177
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
(8')
где l меняется в диапазоне от до . После окончания этого этапа на первом про-
межутке
(9)
а на остальных
(9')
где l также меняется в диапазоне от до . Граф вычислений показан на Рис. 1 Не-
трудно видеть, что он, как и в случае с одним нужным результатом, имеет длину критического
пути, выведенную в (4) и (5).
Рис. 3. Алгоритм последовательно-параллельного метода для вычисления всех частичных результатов
при n=25 и равномерном разделении интервала, чёрным обозначены операции, результаты которых
нужны на выходе алгоритма. Операции (8) и (9), как пустые, не показаны.
Рис. 4. Алгоритм сдваивания для вычисления всех частичных результатов при n=8, чёрным обозначе-
ны операции, результаты которых нужны на выходе алгоритма
От внимательного взгляда читателя наверняка не ускользнуло появление в алгоритме1
«лишних» операций. Для данного метода они необходимы, но по сравнению с исходным – из-
быточны. При больших n коэффициент избыточности2 данного метода стремится к 2. С одной
стороны, это означает, что последовательно-параллельный метод вряд ли кто-то будет приме-
1
по сравнению с последовательной версией
2
Коэффициентом избыточности будем называть отношение количества операций нового алгоритма к
количеству операций исходного, который мы как раз и распараллеливаем заменой на новый
178
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
нять на однопроцессорном компьютере (в отличие от задачи из части 2, где его применение
может быть обусловлено не распараллеливанием, а другими соображениями, типа минимиза-
ции промахов кэша), и что для его реализации нужно хотя бы несколько параллельных уст-
ройств. Однако сравнение с методом сдваивания для данной задачи показывает, что 2 – не та-
кое уж большое число. У метода сдваивания коэффициент избыточности равен с точностью
до главного члена (это несложно показать, если вспомнить, что в методе сдваивания всего
операций, а в исходном последовательном – только n-1). Вкупе с более простой органи-
зацией распределения и пересылки данных это, несмотря на сравнительно большую длину кри-
тического пути, делает последовательно-параллельный метод более предпочтительным, чем
метод сдваивания, для задач, где нужны и промежуточные результаты.
Рис. 5. Алгоритм последовательно-параллельного метода для вычисления всех частичных результатов
при n=23, чёрным обозначены операции, результаты которых нужны на выходе алгоритма, числа рядом
с ними – номера вычисляемых частных выражений
4. Перераспределение интервалов в последовательно-параллельном
методе
На Рис. 1 нетрудно заметить, что при равномерном разделении интервала на части опера-
ции, находящиеся на нижней линии (и на критическом пути графа), начиная с третьей, вынуж-
дены "простаивать" в ожидании результата операции слева от себя. Поэтому последовательно-
параллельный метод можно оптимизировать, перераспределив интервалы так, чтобы их длины
179
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
росли на 1 при возрастании номера. При таком распределении граф алгоритма будет выглядеть
как на Рис. 15. Если на первом интервале вычисляется i частных выражений, а всего k интерва-
лов, то
а длина критического пути графа алгоритма равна . Если проделать ряд вы-
кладок, то, как и следовало ожидать, окажется, что наименьшим значение q=k будет при i=1.
При таком распределении граф алгоритма будет выглядеть как на Рис. 16.
Рис. 6. Алгоритм последовательно-параллельного метода для вычисления всех частичных результатов
при n=16, чёрным обозначены операции, результаты которых нужны на выходе алгоритма. Числа при
вершинах обозначают номер яруса в наискорейшей ярусно-параллельной форме
При указанной разбивке уравнение, связывающее q с n, в предположении, что такая раз-
бивка существует, можно записать как
или
Решая его, получаем для положительного корня
что даёт экономию в раз по сравнению с равномерным разбиением интервала. Коэффи-
циент избыточности при таком делении интервала остаётся менее 2. Кроме экономии на длине
критического пути, при таком разбиении можно выбрать такое распределение операций по яру-
сам параллельной формы, что ширина всех ярусов окажется одинаковой (это хорошо видно на
Рис. 16, где количество вершин с одинаковым номером яруса равно 5), что тоже даёт преиму-
щества при реализации метода.
180
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
5. Исследование свойств последовательно-параллельного метода и их
приложения
Рассмотрим теперь свойства последовательно-параллельного метода, которые можно как-
то использовать при конструировании новых алгоритмов. В [6] автором предложен на основе
старого метода Стоуна [7], которым на основе приёма сдваивания были распараллелено старое
LU-разложение трёхдиагональной матрицы [1,2], новый параллельный алгоритм, с помощью
которого можно разложить на двухдиагональные множители трёхдиагональную матрицу. При
этом характеристики его устойчивости, в отличие от метода сдваивания Стоуна, не хуже, чем у
последовательного варианта разложения. Рассмотрим, что именно позволило автору сохранить
устойчивость при использовании последовательно-параллельного метода.
Как видно на Рис. 13, Рис. 15 и Рис. 16, последовательно-параллельный метод содержит в
себе набор ветвей последовательных вычислений. Это те участки последовательности операций
исходного последовательного алгоритма, которые либо оставили без изменений, либо заменили
на последовательности более сложных ассоциативных операций. В эти части и можно вставить
типичный для последовательных алгоритмов приём обеспечения устойчивости вычислений –
нормировку. Её добавление в обычный последовательный алгоритм можно видеть на примере
обратной подстановки с нормировкой, например, в [2]. Посмотрим, можно ли использовать её,
сконструировав с её помощью по последовательно-параллельной схеме вычислений новый па-
раллельный алгоритм.
6. Пример использования последовательно-параллельного метода
Пусть нам нужно решить систему линейных алгебраических уравнений (здесь и далее бу-
дем использовать сокращение СЛАУ)
(14)
где
(15)
– ленточная нижняя треугольная матрица с единичной диагональю и с поддиагональной
лентой ширины 2, и
(16)
– вектор правой части. Если теперь расписать прямую подстановку, то мы получим
, , , (17)
или, вводя вектор
соотношение
, (19)
где
181
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
(20)
Если теперь выполнить в (19) подстановку до некоторого i