Лекция 12. Внутренний параллелизм алгоритма План

1. Понятие внутреннего параллелизма алгоритма и его использование

2. О выборе расположения вершин графа алгоритма

3. Особенности алгоритма решения системы линейных алгебраических уравнений

1. Понятие внутреннего параллелизма алгоритма и его использование

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

Возьмем любой алгоритм, записанный в виде математических соотношений, последовательных программ или каким-либо иным способом. Допустим, что по этой записи для него удалось построить граф алгоритма. Предположим, что для этого графа обнаружена параллельная форма с достаточной шириной ярусов. Тогда рассматриваемый алгоритм принципиально можно реализовать на параллельном компьютере. Очень важно, что параллельная реализация алгоритма будет иметь такие же вычислительные свойства, как и любая другая [Воеводин]. В частности, если исходный алгоритм был численно устойчив, то он останется таким и в параллельной форме. Подобный параллелизм в алгоритмах называется внутренним.

В старых, давно используемых и хорошо отработанных алгоритмах довольно часто удается обнаружить хороший запас внутреннего параллелизма.

Использование внутреннего параллелизма имеет

• достоинство: не нужно тратить дополнительные усилия на изучение вычислительных свойств вновь создаваемых алгоритмов;

• недостатки: необходимость определять и исследовать графы алгоритмов.

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

Пример. Необходимо вычислить произведение

,

где - -матрицы с элементами соответственно. Элементы матрицы будем обозначать :

. (25)

Формула (25) не определяет алгоритм вычисления элементов матрицы однозначно, т.к. не определен порядок суммирования произведений . Отсутствие указания о соблюдении какого-либо порядка перебора индексов говорит о возможном параллелизме вычислений.

Допустим, что выбран следующий алгоритм реализации (25):

(35)

Построим граф алгорима (35). Будем считать, что вершины графа соответствуют операциям вида . При построении графа не будем сначала показывать вершины и инцидентные им дуги, связанные с вводом элементов матриц и с присвоением элементам матрицы вычисленных значений Чтобы не вносить в исследование графа алгоритма дополнительные трудности, вершины графа нельзя располагать произвольно. Рассмотрим прямоугольную решетку в трехмерном пространстве с координатами . Во все целочисленные узлы решетки для поместим вершины графа. Анализируя (35), видно, что в вершину с координатами для будет передаваться результат выполнения операции, соответствующей вершине с координатами .

Граф алгоритма распадается на не связанных между собой подграфов. Каждый подграф содержит вершин и представляет один путь, расположенный параллельно оси . Для граф алгоритма представлен на рис. 12.1(а). В полном графе имеется множественная рассылка данных. Элемент рассылается по всем вершинам, имеющим те же самые значения координат . Элемент рассылается по всем вершинам, имеющим те же самые координаты . Для все рассылки учтены на рис. 12.1(б).

Этот пример хорошо иллюстрирует, насколько важно правильно выбрать расположение вершин графа алгоритма. Если, например, расположить вершины на прямой без какой-либо связи с индексами , то вряд ли в таком графе удалось бы разглядеть параллелизм. При выбранном расположении вершин параллелизм очевиден. Легко описать любой ярус любой параллельной формы.

Рис. 12.1