Введение

Последовательно-параллельный алгоритм известен давно и используется, главным образом, как эрзац блочного метода 1 , там, где есть возможность использовать свойство ассоциативности операций. К последним, например, можно отнести довольно широкий класс алгоритмов, содержащих последовательные рекуррентные вычисления с линейными и дробно-линейными формулами. В данной статье автор исследует и предлагает использовать свойства последовательно-параллельного метода для раскрытия большего потенциала параллелизма, чем обычно принято видеть в ряде алгоритмов.

Последовательно-параллельный метод для алгоритмов с одним результатом

Последовательно-параллельный алгоритм изначально придуман для таких подзадач, где из большого поля данных нужно получить всего одно число, характеризующее всё это поле, например, одну из норм -максимальный модуль элемента или сумму модулей всех элементов. Не будем пока конкретизировать операции, а предположим, что нужно вычислить результат (1) где -обозначение некой ассоциативной операции над данными некоторого типа, к которому как раз и принадлежит любой из элементов . Для вычисления этого выражения последовательно-параллельным методом весь диапазон натуральных чисел от 1 до n разбивается на q промежутков -от k 0 =1 до k 1 , от k 1 +1 до k 2 , ..., от k q-1 +1 до k q =n. В каждом из этих промежутков выражение

(2) вычисляется последовательно, с возрастанием индекса, а потом последовательно же вычисляется (3) При возможности деления n на количество устройств q обычно используют равномерное разделение на промежутки. В этом случае граф получающегося алгоритма имеет вид, показанный на Рис. 1. Нетрудно понять, что длина его критического пути будет равна (4) то есть при будет достигнут её минимум, равный (5) Естественно, что этот метод значительно уступает по длине критического пути графа (по организации вычислений и передач между устройствами он всё же проще) методу сдваивания, показанному на Рис. 1 и имеющему длину критического пути (6) Перед тем, как перейти к более сложным задачам, отметим для себя одну важную вещь. В случае вычисления выражения (1) как последовательно-параллельный метод, так и метод сдваивания использовали одно и то же общее количество операций , равное . Избыточных по отношению к исходному последовательному алгоритму вычислений оба они не используют.

Последовательно-параллельный метод для алгоритмов с нужными промежуточными результатами

Перейдём теперь к рассмотрению задачи более сложного типа. Пусть опять -обозначение некой ассоциативной операции над данными некоторого типа, к которому принадлежит любой из элементов , и пусть нам нужно вычислить все выражения (7) для всех возможных значений m от 1 до n. Для решения такой задачи с помощью последовательно-параллельного метода мы опять весь диапазон натуральных чисел от 1 до n разбиваем на q промежутков -от k 0 =1 до k 1 , от k 1 +1 до k 2 , ..., от k q-1 +1 до k q =n. В каждом из этих промежутков последовательно определяем выражения (8)

Перераспределение интервалов в последовательно-параллельном методе

На Рис. 1 нетрудно заметить, что при равномерном разделении интервала на части операции, находящиеся на нижней линии (и на критическом пути графа), начиная с третьей, вынуждены "простаивать" в ожидании результата операции слева от себя. Поэтому последовательнопараллельный метод можно оптимизировать, перераспределив интервалы так, чтобы их длины

Исследование свойств последовательно-параллельного метода и их приложения

Рассмотрим теперь свойства последовательно-параллельного метода, которые можно както использовать при конструировании новых алгоритмов. В [6] автором предложен на основе старого метода Стоуна [7], которым на основе приёма сдваивания были распараллелено старое LU-разложение трёхдиагональной матрицы [1,2], новый параллельный алгоритм, с помощью которого можно разложить на двухдиагональные множители трёхдиагональную матрицу. При этом характеристики его устойчивости, в отличие от метода сдваивания Стоуна, не хуже, чем у последовательного варианта разложения. Рассмотрим, что именно позволило автору сохранить устойчивость при использовании последовательно-параллельного метода.

Как видно на Рис. 13, Рис. 15 и Рис. 16, последовательно-параллельный метод содержит в себе набор ветвей последовательных вычислений. Это те участки последовательности операций исходного последовательного алгоритма, которые либо оставили без изменений, либо заменили на последовательности более сложных ассоциативных операций. В эти части и можно вставить типичный для последовательных алгоритмов приём обеспечения устойчивости вычисленийнормировку. Её добавление в обычный последовательный алгоритм можно видеть на примере обратной подстановки с нормировкой, например, в [2]. Посмотрим, можно ли использовать её, сконструировав с её помощью по последовательно-параллельной схеме вычислений новый параллельный алгоритм.

Пример использования последовательно-параллельного метода

Заключение

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

Поэтому автор рекомендует читателю обратить внимание на последовательнопараллельную схему вычислений там, где схемы сдваивания не дают возможности построить устойчивые алгоритмы. Не исключено, что подобные замены могут помочь и в других аналогичных случаях, где применяется целочисленная дихотомия диапазонов, а не только для ассоциативных операций. Сам автор предполагает заняться ревизией других алгоритмов, опирающихся на сдваивание [4], с целью получения на их основе, возможно, и не столь быстрых, но Рис. 8. Алгоритм последовательно-параллельного метода для вычисления решения СЛАУ (1) при n=30, степень "тяжести" операций показана градациями серого цвета.