Лекции по параллельным вычислениям. Гергель В.П - 36 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

36
ния ее выполнения. Если эти индексы перенести на вершины графа алгоритма,
то мы получим каноническую форму.
Ограничивая число операций, которые могут выполняться параллельно,
можно получить отличающиеся строгие параллельные формы. В предельном
случае, когда на каждом шаге вычислительного процесса может выполняться
только одна операция, т.е. все ярусы имеют ширину, равную 1, будет получена
так называемая линейная форма, т.е. граф упорядочивается линейно.
На рис. 3.1 и 3.2 приведены примеры ориентированных графов, описы-
вающих алгоритмы нахождения суммы последовательности числовых значений
1
n
i
i
S x
, (3.2)
где n – количество суммируемых значений. В частности, на рис. 3.1 показан
ориентированный граф
SSS
R,VG
(3.3)
алгоритма последовательного суммирования элементов числового набора.
Здесь
n,n,S
v,...,v,v,...,vV
111001
– множество операций (ввода –
i,
v
0
и суммиро-
вания –
i
v
1
,
1
1
n
), а
11
11110
ni,v,v,v,vR
i,i,i,i,S
– множество
дуг, определяющих информационные зависимости операций. В данном случае
операции ввода обозначены цифрами 1-4, а операции суммирования – цифрами
5-7. Нетрудно заметить, что этот граф является линейной формой и не допуска-
ет параллельную реализацию на многопроцессорной системе.
Параллельная реализация алгоритма суммирования возможна, например, в
случае, когда алгоритм строится в виде каскадной схемы:
- на первой итерации каскадной схемы все исходные данные разбиваются на
пары, и для каждой пары вычисляется сумма их значений;
- полученные суммы также разбиваются на пары, и снова выполняется сумми-
рование значений пар и т.д.

Страницы