Автором исследуются возможности использования последовательно-параллельного метода конструирования новых параллельных версий известных численных методов, а также вопросы сбалансированности получаемых методов - как по части распределения вычислений, так и по их устойчивости. 1. Введение Последовательно-параллельный алгоритм известен давно и используется, главным образом, как эрзац блочного метода1, там, где есть возможность использовать свойство ассоциативности операций. К последним, например, можно отнести довольно широкий класс алгоритмов, содержащих последовательные рекуррентные вычисления с линейными и дробно-линейными формулами. В данной статье автор исследует и предлагает использовать свойства последовательно-параллельного метода для раскрытия большего потенциала параллелизма, чем обычно принято видеть в ряде алгоритмов.
то есть при будет достигнут её минимум, равный (5) Естественно, что этот метод значительно уступает по длине критического пути графа (по организации вычислений и передач между устройствами он всё же проще) методу сдваивания, показанному на Рис. 1 и имеющему длину критического пути 3. Последовательно-параллельный метод для алгоритмов с нужными промежуточными результатами
Перейдём теперь к рассмотрению задачи более сложного типа. Пусть опять – обозначение некой ассоциативной операции над данными некоторого типа, к которому принадлежит любой из элементов , и пусть нам нужно вычислить все выражения (7) для всех возможных значений m от 1 доn. Для решения такой задачи с помощью последовательно-параллельного метода мы опять весь диапазон натуральных чисел от 1 доn разбиваем на q промежутков – от k0=1 до 1k, от 1k+1 доk2, ..., отkq-1+1 доkq=n. В каждом из этих промежутков последовательно определяем выражения (8) (8') до . После окончания этого этапа на первом прогде l также меняется в диапазоне от до . Граф вычислений показан на Рис. 1 Нетрудно видеть, что он, как и в случае с одним нужным результатом, имеет длину критического пути, выведенную в (4) и (5). Рис. 3. Алгоритм последовательно-параллельного метода для вычисления всех частичных результатов при n=25 и равномерном разделении интервала, чёрным обозначены операции, результаты которых нужны на выходе алгоритма. Операции (8) и (9), как пустые, не показаны. Рис. 4. Алгоритм сдваивания для вычисления всех частичных результатов при n=8, чёрным обозначены операции, результаты которых нужны на выходе алгоритма От внимательного взгляда читателя наверняка не ускользнуло появление в алгоритме1 «лишних» операций. Для данного метода они необходимы, но по сравнению с исходным – избыточны. При больших n коэффициент избыточности2 данного метода стремится к 2. С одной стороны, это означает, что последовательно-параллельный метод вряд ли кто-то будет приме1 по сравнению с последовательной версией 2 Коэффициентом избыточности будем называть отношение количества операций нового алгоритма к количеству операций исходного, который мы как раз и распараллеливаем заменой на новый нять на однопроцессорном компьютере (в отличие от задачи из части 2, где его применение может быть обусловлено не распараллеливанием, а другими соображениями, типа минимизации промахов кэша), и что для его реализации нужно хотя бы несколько параллельных устройств. Однако сравнение с методом сдваивания для данной задачи показывает, что 2 – не такое уж большое число. У метода сдваивания коэффициент избыточностиравен с точностью до главного члена
(это несложно показать, если вспомнить, что в методе сдваивания всего операций, а в исходном последовательном – только n-1). Вкупе с более простой организацией распределения и пересылки данных это, несмотря на сравнительно большую длину критического пути, делает последовательно-параллельный метод более предпочтительным, чем метод сдваивания, для задач, где нужны и промежуточные результаты. Рис. 5. Алгоритм последовательно-параллельного метода для вычисления всех частичных результатов при n=23, чёрным обозначены операции, результаты которых нужны на выходе алгоритма, числа рядом с ними – номера вычисляемых частных выражений 4. Перераспределение интервалов в последовательно-параллельном методе
На Рис. 1 нетрудно заметить, что при равномерном разделении интервала на части операции, находящиеся на нижней линии (и на критическом пути графа), начиная с третьей, вынуждены "простаивать" в ожидании результата операции слева от себя. Поэтому последовательнопараллельный метод можно оптимизировать, перераспределив интервалы так, чтобы их длины росли на 1 при возрастании номера. При таком распределении граф алгоритма будет выглядеть как на Рис. 15. Если на первом интервале вычисляется i частных выражений, а всего k интервалов, то
а длина критического пути графа алгоритма равна . Если проделать ряд выкладок, то, как и следовало ожидать, окажется, что наименьшим значение q=k будет при i=1. При таком распределении граф алгоритма будет выглядеть как на Рис. 16. Рис. 6. Алгоритм последовательно-параллельного метода для вычисления всех частичных результатов при n=16, чёрным обозначены операции, результаты которых нужны на выходе алгоритма. Числа при вершинах обозначают номер яруса в наискорейшей ярусно-параллельной форме При указанной разбивке уравнение, связывающее q с ,nв предположении, что такая разбивка существует, можно записать как или Решая его, получаем для положительного корня 5. Исследование свойств последовательно-параллельного метода и их приложения
Рассмотрим теперь свойства последовательно-параллельного метода, которые можно
както использовать при конструировании новых алгоритмов. В [6] автором предложен на основе
старого метода Стоуна [
Как видно на Рис. 13, Рис. 15 и Рис. 16, последовательно-параллельный метод содержит в себе набор ветвей последовательных вычислений. Это те участки последовательности операций исходного последовательного алгоритма, которые либо оставили без изменений, либо заменили на последовательности более сложных ассоциативных операций. В эти части и можно вставить типичный для последовательных алгоритмов приём обеспечения устойчивости вычислений – нормировку. Её добавление в обычный последовательный алгоритм можно видеть на примере обратной подстановки с нормировкой, например, в [2]. Посмотрим, можно ли использовать её, сконструировав с её помощью по последовательно-параллельной схеме вычислений новый параллельный алгоритм. 6. Пример использования последовательно-параллельного метода Пусть нам нужно решить систему линейных алгебраических уравнений (здесь и далее будем использовать сокращение СЛАУ) где – ленточная нижняя треугольная матрица с единичной диагональю и с поддиагональной лентой ширины 2, и – вектор правой части. Если теперь расписать прямую подстановку, то мы получим , , , или, вводя вектор соотношение где
, (19) Если теперь выполнить в (19) подстановку до некоторого i<k, то получается Введём обозначение Из вида матрицы
видно, что эти матрицы имеют вид где величины элементов первой и второй строк матрицы связаны рекуррентно по формулам Рис. 7. Алгоритм последовательно-параллельного метода для вычисления решения СЛАУ (1) при n=16, степень «тяжести» операций показана градациями серого цвета. Под «тяжестью» здесь и на следующем рисунке автор понимает, как и в [5], реальное количество выполняемых арифметических операций. (20) (21) (22) (23) (24) (25) (26) (27) (28) Вводим нормировочные коэффициенты Далее для возрастающих k выполняем (30) 7. Заключение
Использование последовательно-параллельной схемы при конструировании новых параллельных методов позволяет использовать некоторые приёмы работы, которые характерны для традиционных последовательных алгоритмов. Это связано с наличием в схеме достаточно длинных последовательных ветвей, которые имеют вычислительную структуру, во многом заимствованную из последовательного метода.
Поэтому автор рекомендует читателю обратить внимание на последовательнопараллельную схему вычислений там, где схемы сдваивания не дают возможности построить устойчивые алгоритмы. Не исключено, что подобные замены могут помочь и в других аналогичных случаях, где применяется целочисленная дихотомия диапазонов, а не только для ассоциативных операций. Сам автор предполагает заняться ревизией других алгоритмов, опирающихся на сдваивание [4], с целью получения на их основе, возможно, и не столь быстрых, но более устойчивых параллельных методов, либо алгоритмов с более регулярными графами. Тут важен ещё тот момент, что даже при равных характеристиках устойчивости алгоритмы, опирающиеся на последовательно-параллельную схему, про мнению автора, будут иметь графы, более близкие к регулярным [3], что может позволить более эффективно отображать их на параллельные архитектуры вычислительных систем. Литература 3. Воеводин В.В. Математические основы параллельных вычислений // М.: Изд. Моск. ун-та, 1991. 4. Открытая энциклопедия свойств алгоритмов. URL: http://algowiki-project.org (дата обращения: 28.05.2015). 5. Фролов А.В. Принципы построения и описание языка Сигма. Препринт ОВМ АН №236. М.: ОВМ АН СССР, 1989. Serial-parallel method using for partial associative operation parallelizing Alexey Frolov Keywords: Serial-parallel method, associative operations, parallelizing Serial-parallel method using for partial associative operations is discussed in this paper.