Суперкомпьютерные дни в России 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